数据结构（线性表）

大二学c++都快忘没了，写点数据结构来复习一下，写的不好，不喜勿喷。

直接上代码，这是模板类的写法，必须全部写在头文件里。因为编译器不知道你会使用什么类型的数据，所以无法确定要分配的存储空间大小。

---

开发环境：codeblocks

#ifndef linear_list_h_included
#define linear_list_h_included

#include <cstdio>

template <class t>
class list
{
private:
    int s;  //线性表空间大小
    
    int length; //线性表元素个数
    
    t* head;    //空间首地址

public:
    list<t>() { }
    
    list<t>(int size) : s(size), head(null) { }
    
    ~list<t>() { destroylist(); }
    
    void initlist();    //初始化线性表
    
    void destroylist(); //销毁线性表
    
    void clearlist();   //线性表置空
    
    bool listempty();   //判断线性表是否存在
    
    int listlength();   //返回线性表长度
    
    bool getelem(int i, t &e);  //通过e得到第i个元素
    
    int locateelem(t e, bool (*compare)(t list_e, t e));    //通过compare函数进行比较，得到第一个符合的元素
    
    bool priorelem(t cur_e, t &pre_e);  //通过pre_e得到cur_e的前驱
    
    bool nextelem(t cur_e, t &next_e);  //通过next_e得到cur_e的后继
    
    bool listinsert(int i, t e);    //在第i个位置前插入新元素e
    
    bool listdelete(int i, t &e);   //删除第i个元素，用e返回它的值
    
    bool insert(t); //向尾部插入一个元素
    
    bool listtraverse(bool (*visit)(t e));  //依次对每个元素执行visit()操作
    
};

template <class t>
void list<t>::initlist()
{
    if(head == null)
    {
        head = new t[s];
        length = 0;
    }
}

template <class t>
void list<t>::destroylist()
{
    if(head != null)
    {
        delete head;
        head = null;
    }
}

template <class t>
void list<t>::clearlist()
{
    length = 0;
}

template <class t>
bool list<t>::listempty()
{
    if(head == null) return true;
    else return false;
}

template <class t>
int list<t>::listlength()
{
    if(head == null) return -1;
    return length;
}

template <class t>
bool list<t>::getelem(int i, t &e)
{
    if(head == null || length == 0) return false;
    e = head[i];
    return true;
}

template <class t>
int list<t>::locateelem(t e, bool (*compare)(t list_e, t e))
{
    if(head == null || length == 0) return -1;
    for(int i = 0; i < length; i++)
        if(compare(head[i], e))
            return i;
    return -1;
}

template <class t>
bool list<t>::priorelem(t cur_e, t &pre_e)
{
    if(head == null || length == 0 || head[0] == cur_e)
        return false;
    for(int i = 0; i < length; i++)
    {
        if(head[i] == cur_e)
        {
            pre_e = head[i-1];
            return true;
        }
    }
    return false;

}

template <class t>
bool list<t>::nextelem(t cur_e, t &next_e)
{
    if(head == null || length == 0 || head[length] == cur_e)
        return false;
    for(int i = 0; i < length; i++)
    {
        if(head[i] == cur_e)
        {
            next_e = head[i+1];
            return true;
        }
    }
    return false;
}

template <class t>
bool list<t>::listinsert(int i, t e)
{
    if(head == null || length == 0 || length-1 < i || length == s)
        return false;
    for(int j = length-1; j >= i; j--)
        head[j+1] = head[j];
    head[i] = e;
    length++;
    return true;
}

template <class t>
bool list<t>::listdelete(int i, t &e)
{
    if(head == null || length == 0 || length-1 < i)
        return false;
    if(i == length-1)
    {
        length--;
        e = head[i];
        return true;
    }
    e = head[i];
    length--;
    for(int j = i; j < length; j++)
        head[j] = head[j+1];
    return true;
}

template <class t>
bool list<t>::insert(t e)
{
    if(head == null || length == s) return false;
    head[length] = e;
    length++;
    return false;
}

template <class t>
bool list<t>::listtraverse(bool (*visit)(t e))
{
    if(head == null || length == 0)
        return false;
    for(int i = 0; i < length; i++)
        if(!visit(head[i]))
            return false;
    return true;
}

#endif // linear_list_h_included