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; } }}
下面是测试截图：
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
望着它们，我睡着了。今天已经过去——我生命中所有天中的一天，
