数据结构与算法——线性表 1

数据结构与算法——线性表 1

今天学习了一下线性表，线性表是常用的一种数据结构，以下变为其代码，此代码是顺序存储+固定长度的， 编译器为gcc version 6.1.0 (GCC)， 亲测可用，但效率就不知道了。。。

//List_my.h
//顺序存储+固定长度

#ifndef _LIST_MY_H_
#define _LIST_MY_H_

#define LIST_MAX_SIZE       (100)

template<typename   T>

class       List_my{
public:
    typedef unsigned int    uint;

    List_my():length_l(0){};
    List_my(T* d, uint id);

    bool        empty(void);
    bool        full(void);
    bool        insert(const T &d, uint id);
    bool        remove(T &d, int id);
    bool        find(const T &d, uint& loc);
    bool        locate(uint id, uint& loc);

    uint        size(void)const{
         
  return LIST_MAX_SIZE;}
    uint        length(void){
         
  return length_l;}
    T       get_data(uint id)const{
         
  return data[id-1];}
    bool        set_data(const T &d, uint id){data[id-1] = d;}  

private:
    T   data[LIST_MAX_SIZE];
    uint    length_l;
};

template<typename T>
List_my<T>::List_my(T* d, uint len){
    for(int i=0;i<len;i++)data[i] = d[i];
    length_l = len;
}

template<typename T>
bool        List_my<T>::empty(void){
    if(length_l)return false;
    return true;
}

template<typename T>
bool        List_my<T>::full(void){
    if(length_l <= LIST_MAX_SIZE)return false;
    return true;
}

template<typename T>
bool        List_my<T>::find(const T &d, uint& loc){    
    for(int i= 0;i<length_l;i++){
        if(d == data[i]){
            loc = i;
            return true;
        }
    }
    return true;
}

template<typename T>
bool        List_my<T>::locate(uint id, uint& loc){ 
    if(id>length_l || id<1) return false;
    loc = id-1;
    return true;
}

template<typename T>
bool        List_my<T>::insert(const T &d, uint id){
    if(id>length_l+1  || full() ) return false;
    for(unsigned int i = length_l;i>id; --i)
        data[i+1] = data[i];
    data[id-1] = d;
    length_l++;
    return true;
}

template<typename T>
bool        List_my<T>::remove(T &d, int id){   
    if(id>length_l || empty()) return false;
    d = data[id-1];
    for(unsigned int i=d-1; i<=length_l;++i)
        data[i] = data[i+1];
    length_l--;
    return true;
}

#endif

测试代码

//测试代码
#include <iostream>
#include "List_my.h"

using namespace std;

template<typename T>
void    display(List_my<T>& l){
    for(unsigned int i=1;i<=l.length();++i)
        cout<<l.get_data(i)<< " ";
    cout<<endl;
    cout<<l.length()<<endl;
}

int main(void){
    int a[]={
         
  1,2,3,4,5};
    List_my<int>    l1;
    List_my<int>    l2(a, 5);
     unsigned int   num;
    int m;

    cout<<l2.length()<<endl;
    display(l2);

    cout<<l2.size()<<endl;
    cout<<l2.get_data(2)<<endl;
    l2.set_data(0, 1);
    display(l2);
    for(unsigned int i=1;i<5;++i)   l1.insert(i, i);
    display(l1);
    display(l2);
    l2.remove(m, 2);
    cout<<m<<endl;
    display(l2);
    m = 4;
    l1.find(m, num);
    cout<<num<<endl;
    l1.locate(3,num);
    cout<<num<<endl;

    return(EXIT_SUCCESS);
}