数据结构——静态链表模板类实现

左手的ㄟ右手 2022-06-07 06:41 237阅读 0赞

**数据结构笔记2.6**  
最近总算把静态链表的模板class整理出来了，之所以耽误时间，一方面是因为……，另一方面是静态链表和普通链表在思考上还是有差别的，把无序的东西（普通链表的每个节点）联系起来，还比较自然，但是把有序的东西（静态链表的物理存储）硬生生拆分成不按照其常规顺序的总是感觉别扭，但是认真想一下，其实二者在道理上是统一的。例如，在静态链表中Insert一个节点，其实就是在空闲数组中拿出一个节点（这里的节点就是指数组中的一个元素的位置），通过类似于“偷梁换柱”的思想，把其前驱与后继的链接信息更改一下。所以在某些情况下，其实静态链表的优势要高于普通链表，接下来就贴出代码：  
模板class代码：

//静态链表——结构体数组练习
    #include <iostream>
    using namespace std;
    
    const int maxSize = 100;            //静态链表的大小
    template<class T>
    struct SLinkNode {
        T data;
        int link;                       //用int型数据的顺序来链接
    };
    
    template<class T>
    class StaticList {
    private:
        SLinkNode<T> elem[maxSize];
        int avil;                       //当前可分配空间首地址
    public:
        void Initial();
        int Length();                   //计算静态链表的长度
        int Search(T x);                //在静态链表中查找具有给定值的节点
        int Locate(int i);              //在静态链表中查找第i个节点
        bool Append(T x);               //在静态链表的表尾追加一个新节点
        bool Insert(int i, T x);        //在静态链表的第i个节点后插入新节点
        bool Remove(int i);             //在静态链表中释放掉第i个节点
        bool IsEmpty();                 //判断静态链表是否为NULL
        void output();                  //输出各个节点的数据
        void physcialOutput();          //静态链表的实际物理顺序输出
    };
    
    //函数定义
    template<class T>
    void StaticList<T>::Initial() {
        //将链表空间初始化
        elem[0].link = -1;                                              //结尾的link标记成-1
        avil = 1;
        //当前可分配空间从1开始建立带表头节点的空链表
        for (int i = 1; i < maxSize - 1; i ++) {                        //开始构成链接
            elem[i].link = i + 1;
        }
        elem[maxSize - 1].link = -1;                                    //结尾标志设置成-1
    }
    
    template<class T>
    int StaticList<T>::Length() {
        //计算静态链表的长度
        int p = elem[0].link;
        int i = 0;
        while (p != -1) {
            p = elem[p].link;
            i++;
        }
        return i;
    }
    
    template<class T>
    bool StaticList<T>::IsEmpty() {
        //判断链表是否为NULL
        if (elem[0].link == -1) {
            return true;
        }
        else {
            return false;
        }
    }
    
    template<class T>
    int StaticList<T>::Search(T x) {
        //在静态链表中查找具有给定值的节点
        int p = elem[0].link;
        while (p != -1) {
            if (elem[p].data == x) {
                break;
            }
            else {
                p = elem[p].link;
            }
        }
    
        return p;
    }
    
    template<class T>
    int StaticList<T>::Locate(int i) {
        //在静态链表中查找第i个节点
        if (i < 0) {
            return -1;
        }
        if (0 == i) {
            return 0;
        }
        int j = 1, p = elem[0].link;
        while (p != -1 && j < i) {
            p = elem[p].link;
            j++;
        }
        return p;
    }
    
    template<class T>
    bool StaticList<T>::Append(T x) {
        //在静态链表的表尾追加一个新节点
        if (-1 == avil) {                                               //追加失败,数组已满     
            return false;
        }
        int q = avil;
        avil = elem[avil].link;                                         //将尾标识向后移动
        elem[q].data = x;
        elem[q].link = -1;                                              //将新的结尾的link标记成-1
        int p = 0;                                                      //查找尾节点(即没有值与有值的交界处)
        while (elem[p].link != -1) {
            p = elem[p].link;
        }
        elem[p].link = q;                                               //更新尾节点（即追加操作）
        return true;
    }
    
    template<class T>
    bool StaticList<T>::Insert(int i, T x) {
        //在静态链表第i个节点后面插入新的节点
        int p = Locate(i);                                              //定位到相应的节点
        if (-1 == i) {
            return false;
        }
        int q = avil;                                                   //分配节点
        avil = elem[avil].link;                                         //更新尾部标记
        elem[q].data = x;                                               //给新节点赋值
        elem[q].link = elem[p].link;                                    //链接
        elem[p].link = q;
        return true;
    }
    
    template<class T>
    bool StaticList<T>::Remove(int i) {
        //在静态链表中释放第i个节点
        int p = Locate(i - 1);                                          //定位到待删除节点的前面节点
        if (-1 == p) {                                                  //找不到节点
            return false;
        }
        int  q = elem[p].link;                                          //标记待删除节点
        elem[p].link = elem[q].link;                                    //重新连接
        elem[q].link = avil;                                            
        avil = q;                                                       //更新尾指针
        return true;
    }
    
    template<class T>
    void StaticList<T>::output() {
        //通过顺序输出各个节点的数值
        for (int i = 1; i <= Length(); i ++) {
            cout << elem[Locate(i)].data << ' ';
        }
        cout << endl;
    }
    
    //这个函数只是为了在main() 函数中做比照用，并无实际的意义
    template<class T>
    void StaticList<T>::physcialOutput() {
        //根据链表的实际存储顺序输出
        cout << "链表的实际物理存储顺序是 ： ";
        for (int i = 1; i <= Length(); i ++) {
                cout << ' ' << elem[i].data;
        }
        cout << endl;
    }

主函数测试代码：

int main()
    {
        StaticList<int> fir_stat;                   //定义一个静态链表
        fir_stat.Initial();
        fir_stat.Append(1);                         //此处通过追加方式建立静态链表的逐个节点
        fir_stat.Append(2);
        fir_stat.Append(3);
        fir_stat.Append(4);
        fir_stat.Append(5);
        fir_stat.output();                          //输出
        fir_stat.Append(100);                       //追加测试
        fir_stat.output();
        fir_stat.Insert(3, 200);                    //插入测试
        fir_stat.output();
        fir_stat.physcialOutput();                  //因为此处在插入操作之后，所以逻辑顺序与物理顺序在此处不一致
        fir_stat.Remove(1);                         //删除测试
        fir_stat.output();
    
        system("pause");
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast]  
越来越发现数据结构这门课的魅力所在，希望大家以后一起交流数据结构、算法……相关的问题。

[SouthEast]: /images/20220607/3b616e640ea3445aba81457bf36833af.png