欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构(线性表)

程序员文章站 2022-07-04 22:20:01
大二学C++都快忘没了,写点数据结构来复习一下,写的不好,不喜勿喷。 直接上代码,这是模板类的写法,必须全部写在头文件里。因为编译器不知道你会使用什么类型的数据,所以无法确定要分配的存储空间大小。 开发环境:CodeBlocks c++ ifndef LINEAR_LIST_H_INCLUDED d ......

大二学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