C++怎么实现静态链表

这篇文章主要介绍了C++怎么实现静态链表，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

C++ 实现静态链表的简单实例

用数组描述的链表，即称为静态链表。

在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标cur。

这种存储结构，仍需要预先分配一个较大的空间，但在作为线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。

下图表示了静态链表的一中存储结构：

图中用彩色途上的是两个头结点，不存放数据，分别用来记录第一个备用节点和第一个数据节点的下标。
下面给出静态链表的C++实现代码：

首先给出头文件：StaticList.h:

#include<iostream> #include<assert.h> using namespace std; #define MAXSIZE 20    // 静态链表（数组）默认长度 #define ElemType int   // 值类型 class StaticList; //节点类 typedef class StaticListNode  // 静态链表的节点类型（数组元素类型） {   friend class StaticList; private:   ElemType data;       // 值域   int   cur;        // 游标 （指示当前节点的下一个元素下标） }StaticListNode; // 静态链表类</strong></span> class StaticList { public:   StaticList()   {     for(int i = 2; i<MAXSIZE-1; ++i)       space[i].cur = i+1;     space[i].cur = 0;    //整个链表结束     space[0].cur = 2;     space[1].cur = 0;    //数据节点头的游标为空，没有数据   }   ~StaticList()   {} // 尾部插入法   void push_back(const ElemType &x)   {     int i = Malloc_SL();     if(0 == i)       // 空间申请失败     {       cout<<"已满！"<<x<<"不能插入"<<endl;         return ;     }     space[i].data = x;     space[i].cur = 0;     int k = 1;     while(0!=k && 0!=space[k].cur) // 找到最后一个节点       k = space[k].cur;     space[k].cur = i;       // 把刚申请的下标为i的节点链到最后一个节点后面          } // 头部插入法   void push_front(const ElemType &x)   {     int i = Malloc_SL();     if(0 == i)      // 同上，空间申请失败     {       cout<<"已满！"<<x<<"不能插入"<<endl;       return ;     }     space[i].data = x;  // 把x放入刚申请的节点中     space[i].cur = space[1].cur;  // 此时刚申请的节点i的游标指向第一个数据节点，称为第一个结点     space[1].cur = i;       // 使头结点指向第一个数据节点   } // 尾部删除   void pop_back()   {     int i = space[1].cur;     int j = 0;     for(; 0!=space[i].cur; j = i, i = space[i].cur)     {}  // 找到最后一个节点以及倒数第二个节点     space[j].cur = 0;   // 倒数第二个节点的游标赋空     Free_SL(i);      // 最后一个节点被释放   } // 头部删除   void pop_front()   {     int i = space[1].cur;  // i是第一个数据节点的下标     space[1].cur = space[i].cur; // 头结点指向第二个数据节点的下标     Free_SL(i);       // i 节点被释放   }   void show_list()   {     for(int i = space[1].cur; i!=0; i = space[i].cur)       cout<<space[i].data<<" ";     cout<<"Over"<<endl;   }   /* 静态链表从小到大排序的前提下，插入x */   void insert_val(const ElemType &x)   {     int k = 1;     while(0!=k && 0!=space[k].cur && space[space[k].cur].data<x)       k = space[k].cur;    //在下标k之后插入     if(0 == space[k].cur)  // 如果k指向最后一个节点，执行尾插       push_back(x);     else if(k == 1)     // 如果k指向第一个节点，执行头插       push_front(x);     else           // 在中间任意位置插入x     {         int i = Malloc_SL();       assert(0 != i);       space[i].data = x;       space[i].cur = space[k].cur;  // i节点的游标指向k节点后面的一个节点       space[k].cur = i;       // k节点的游标指向新开辟的i节点     }   }   /* 返回key的前一个节点下标*/   int find(const ElemType &key)       {     int i = 1;     while(0!=i && space[space[i].cur].data!=key)       i = space[i].cur;     if(0 == i)     {       cout<<"没找到 "<<key<<endl;       return -1;     }     return i;   }   /* 删除给定的值key所在节点，若没找到则返回 */   void delete_val(const ElemType &key)   {     int i = find(key);     if(-1 == i)   // 说明静态链表中没有元素key       return ;     else if(1 == i) // key 处于下标为2的节点(第一个数据节点)       pop_front();     else if(0 == space[i].cur) // key处于最后一个节点       pop_back();     else       // key 处于中间任意位置     {       int k = space[i].cur;  // 记录要删除位置的下标       space[i].cur = space[k].cur; // 脱离出要删除节点       Free_SL(k); // 删除key所在节点     }   }   /* sl1 和 sl2已存在，把它们糅合到另一个链表，使之按非递减排列 */   void merge(StaticList &sl1, StaticList &sl2)   {     sl1.sort();       sl2.sort();     if(0==sl1.length() || 0==sl2.length())       return ;     int p = sl1.space[1].cur;     int q = sl2.space[1].cur;     while(0!=p && 0!=q)     {           // 哪个数据较小，就把该数据尾插到新链表中，并使游标指向下一个       if(sl1.space[p].data < sl2.space[q].data)       {               push_back(sl1.space[p].data);         p = sl1.space[p].cur;       }       else       {         push_back(sl2.space[q].data);         q = sl2.space[q].cur;       }     }     while(0!=p)     {    // 因为sl1已经有序，如果sl1还没有全部插入新链表，就把剩下的全部插入       push_back(sl1.space[p].data);       p = sl1.space[p].cur;     }     while(0!=q)     {    // 因为sl2已经有序，如果sl2还没有全部插入新链表，就把剩下的全部插入       push_back(sl2.space[q].data);       q = sl2.space[q].cur;     }   }   /* 如果静态链表无序，使其按非递减顺序排列 */   void sort()   {     int s = space[1].cur;     int p = space[s].cur;     if(0 == p)       return ;     space[s].cur = 0;     int k = 1;     int k1 = 0;     while(0 != p)     {       s = p;       p = space[p].cur;       k = 1;   // 找到一个位置k, 在k后插入s所指节点的数据       while(0!=k && space[space[k].cur].data < space[s].data)       {         k1 = k;         //如果k==0,用k1记录最后一个数据节点         k = space[k].cur;    //在下标k之后插入       }       if(0 == k)  //尾插       {         space[k1].cur = s;         space[s].cur = 0;       }       else     //头插和中间插       {         space[s].cur = space[k].cur;         space[k].cur = s;       }     }   }   /* 逆置静态链表 */   void reserve()   {     int s = space[1].cur;     int p = space[s].cur;     if( 0==p )       return ;     space[s].cur = 0;     while(0 != p)     {       s = p;       p = space[p].cur;       space[s].cur = space[1].cur;  // 把s所指节点 头插进原有链表       space[1].cur = s;       // s成为第一个数据节点     }   }   /* 清空静态链表 */   void clear()   {     for(int i = 2; i<MAXSIZE-1; ++i)       space[i].cur = i+1;     space[i].cur = 0;     space[0].cur = 2;   // 下标2成为第一个备用节点     space[1].cur = 0;   // 第一个数据节点为空   }   /* 返回表长 */   int length()   {     if(0 == space[1].cur)       return 0;     int i = 1;     int count = -1;     do     {       ++count;       i = space[i].cur;     }while(0 != i);     return count;   }   /* 返回下标为k的节点的下一个节点下标 在静态链表中用处不大*/   int next(const int k)   {     if(0==k || 1==k)       return -1;     return space[k].cur;   }   /* 返回下标为k的节点的上一个节点下标 */   int prio(const int k)   {     if(0==k || 1==k)       return -1;     int p = 1;     while(0!=p && space[p].cur!=k)       p = space[p].cur;     return p;   } protected:   /* 用来申请一个空间，返回该节点的下标 */   int Malloc_SL()     {     int i = space[0].cur;  // 0下标的游标指向第一个备用节点     if(space[0].cur) space[0].cur = space[i].cur; // 修改头结点保存的第一个备用节点下标      return i;   }   /* 释放下标为k的节点 */   void Free_SL(int k)     {     space[k].cur = space[0].cur;  // 该节点的游标指向第一个备用节点     space[0].cur = k;        // 该节点称为第一个备用节点   } private:   StaticListNode space[MAXSIZE]; };

下面是测试代码：Main.cpp

#include"StaticList.h" void main() {   StaticList SL;   StaticList SL1;  //测试merge()   StaticList SL2;   SL1.push_back(1);   SL1.push_back(9);   SL1.push_back(0);   SL1.push_back(6);   SL1.push_back(999);   SL2.push_back(5);   SL2.push_back(8);   SL2.push_back(100);   ElemType Item = 0;   int select = 1;   while(select)   {     cout<<"********************************************"<<endl;     cout<<"*[1] push_back      [2] push_front  *"<<endl;     cout<<"*[3] show_list      [4] pop_back   *"<<endl;     cout<<"*[5] pop_front      [6] insert_val  *"<<endl;     cout<<"*[7] length       [8] find     *"<<endl;     cout<<"*[9] merge        [10] delete_val  *"<<endl;     cout<<"*[11] sort        [12] reserve   *"<<endl;     cout<<"*[13] next        [14] prio     *"<<endl;     cout<<"*[15] clear       [16] destroy   *"<<endl;     cout<<"*[0] quit_sys               *"<<endl;     cout<<"********************************************"<<endl;     cout<<"请选择：》";     cin>>select;     switch(select)     {     case 1:       cout<<"输入要尾插的数据:(-1结束)>";       while(cin>>Item && -1 != Item)         SL.push_back(Item);       break;     case 2:       cout<<"输入要头插的数据:(-1结束)>";       while(cin>>Item && -1 != Item)         SL.push_front(Item);       break;     case 3:       SL.show_list();       break;     case 4:       SL.pop_back();       break;     case 5:       SL.pop_front();       break;     case 6:       cout<<"输入要插入的数据:>";       cin>>Item;       SL.insert_val(Item);       break;     case 7:       cout<<"链表长度为："<<SL.length()<<endl;       break;     case 8:       cout<<"输入要查找的数据:>";       cin>>Item;       SL.find(Item);       break;     case 9:       SL.merge(SL1, SL2);       break;     case 10:       cout<<"输入要删除的数据:>";       cin>>Item;       SL.delete_val(Item);       break;     case 11:       SL.sort();       break;     case 12:       SL.reserve();       break;     case 13:       SL.next(0);       break;     case 14:       SL.prio(0);       break;     case 15:       SL.clear();       break;     case 16:       SL.~StaticList();       break;     default:       break;     }   } }

下面是测试截图：

感谢你能够认真阅读完这篇文章，希望小编分享的“C++怎么实现静态链表”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!