静态链表是用数组描述的链表, 其实是为了给没有指针的语言设计的单链表的方法. 尽管可能用不上, 但这种思考方式是还是很巧妙的, 利用游标来实现指针的作用, 应该理解这种思想以备不时之需
, 网上找的 c++ 代码基本都有 c 的痕迹, 就自己学了一天, 其中加了大量的注释, 希望对其他初学者有所帮助
- #include<iostream>
- #include<ctime>
- #include<cstdlib>
- using namespace std;
- #define MAXSIZE 1000
- #ifndef LIST_H
- #define LIST_H
- class node{// 创建结点结构, 包括数据和游标, 游标记录下一个元素所对应的下标
- public:
- int cur;
- int data;
- };
- class List{
- public:
- List();// 无参数的构造函数
- bool CreateList(int size);// 初始链表
- int new_sl();// 模仿普通链表的 new 分配内存空间
- void delete_sl(int i);// 模仿普通链表的 delete 释放内存空间, 这个形参 i 代表链表中将要释放的元素的下标
- void ClearList();// 清空链表
- bool ListEmpty();// 链表判空
- int ListLength();// 获取链表长度
- bool GetElem(int i,int &e);// 获取指定元素
- int LocateElem(int e);// 寻找第一个等于 e 的数据元素的位序
- bool ChangeElem(int i,int e);// 更改指定的元素
- void ListTraverse();// 遍历链表
- bool ListInsert(int i,int Elem);// 插入元素
- bool ListDelete(int i,int &Elem);// 删除元素
- private:
- node space[MAXSIZE];// 静态链表是由数组的下标实现指针的功能
- int length=0;
- };
- #endif // !LIST_H
- List::List(){
- length=0;
- }
- bool List::CreateList(int size){
- srand((unsigned int)time(NULL));// 随机种子, 为链表数据的创建提供随机值
- if(size<=0)// 如果所要构建的链表长度小于等于 0, 返回 false 代表构建失败
- return false;
- for(int i=1;i<MAXSIZE-1;i++){// 创建链表 (包括备用链表和创建的链表), 数组的下标 0 处储存备用链表(即尚未被使用的空间) 的首个下标, 故正式的元素从下标 1 开始
- space[i].cur=i+1;// 每个元素都存储对应的游标, 即下一个元素的下标, 在初始化时就直接使用下一个元素的下标进行初始化
- }
- for(int i=1;i<=size;i++){
- space[i].data=rand()%100+1;// 给创建的链表内的每个元素分配随机值
- }
- space[MAXSIZE-1].cur=1;// 首个元素的游标由数组的最后一个元素存储
- length=size;
- return true;
- }
- int List::new_sl(){
- int i=space[0].cur;// 获取备用链表的首个下标
- if(space[0].cur)
- space[0].cur=space[i].cur;// 备用链表的原首下标被 i 拿去使用, 现在需要创建新的首下标, 原首下标对应的游标就是新的首下标
- return i;
- }
- void List::delete_sl(int i){
- space[i].cur=space[0].cur;/* 将当前备用链表的首下标赋给将要释放的元素的游标, 因为这个被释放的元素将成为备用链表的首个元素, 那么当前备用链表的首下标就将成为这个元素的下一个元素的下标 */
- space[0].cur=i;// 将被释放的元素下标的作为备用链表的首个下标
- }
- void List::ClearList(){
- int temp1=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int i=0;i<length;i++){// 因为要清空整个链表, 因此遍历
- int temp2=space[temp1].cur;// 再创建一个变量来暂时存储将要释放的元素的游标, 因为将要释放的元素一但释放, 会丢失游标信息, 导致遍历无法继续
- delete_sl(temp1);// 释放元素
- temp1=temp2;// 将游标信息赋回 temp1, 保证遍历继续进行
- }
- }
- bool List::ListEmpty(){
- return length==0;
- }
- int List::ListLength(){
- return length;
- }
- bool List::GetElem(int i,int &e){
- if(i<0||i>length)// 如果元素位置小于 1 或超过链表长度, 返回 false 代表获取失败
- return false;
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int k=1;k<i;k++){// 循环次数为元素位置减一, 循环结束后 temp 变量是要获取的元素的上一个元素的游标, 即我们要获取的元素的下标
- temp=space[temp].cur;// 链表遍历的本质是游标的逐一传递, 反复往后访问
- }
- e=space[temp].data;// 将获取的元素的数据通过引用传递给 e
- return true;
- }
- int List::LocateElem(int e){
- int i;
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- bool flag=false;// 判断是否找到了想要的元素
- for(i=0;i<length;i++){// 遍历链表, 逐一寻找
- temp=space[temp].cur;// 链表遍历的本质是游标的逐一传递, 反复往后访问
- if(e==space[temp].data){// 如果找到了想要的元素, 跳出循环并将 flag 设为 true 代表找到了
- flag=true;
- break;
- }
- }
- if(!flag)
- return -1;// 返回位置为 - 1 代表没找到
- else
- return i;// 返回想要的元素在链表中的次序位置, 即是链表中的第几个元素(还有一种是返回 temp, 是返回相应的下标)
- }
- bool List::ChangeElem(int i,int e){
- if(i<0||i>length)// 位置小于 0 或大于链表长度, 返回 false 代表更改失败
- return false;
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int k=1;k<i;k++){// 循环链表, 游标达到指定位置为止
- temp=space[temp].cur;// 链表遍历的本质是游标的逐一传递, 反复往后访问
- }
- space[temp].data=e;// 改变目标元素的值
- return true;
- }
- void List::ListTraverse(){
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int i=0;i<length;i++){// 标准遍历, 没什么好说的
- cout<<space[temp].data<<" ";
- temp=space[temp].cur;
- }
- cout<<endl;
- }
- bool List::ListInsert(int i,int Elem){
- if(i<0||i>length)// 如果插入的位置小于 0 或大于链表长度, 返回 false 代表插入失败
- return false;
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int k=1;k<i-1;k++){// 循环次数为将插入的位置减 2, 此时 temp 为插入位置的前二个元素的游标(也就是插入位置的前一个元素的下标)
- temp=space[temp].cur;
- }
- int pnew=new_sl();// 创建新元素, 分配内存(模拟)
- space[pnew].cur=space[temp].cur;// 将插入位置的游标赋给新元素的游标, 此时新元素向后的接口完成
- space[temp].cur=pnew;// 将新元素的下标赋给插入位置的游标, 此时新元素向前的接口完成
- space[pnew].data=Elem;// 将数据赋给插入的元素
- length++;// 长度增加
- return true;
- }
- bool List::ListDelete(int i,int &Elem){
- if(length==0||i<0||i>length)// 如果删除的位置小于 0 或大于链表长度或链表为空, 返回 false 代表删除失败
- return false;
- int temp=space[MAXSIZE-1].cur;// 创建一个变量作为游标参与循环, 首个元素的游标存在于数组的末尾, 故将其赋给此变量
- for(int k=1;k<i-1;k++){// 循环次数为将删除的位置减 2, 此时 temp 为删除位置的前二个元素的游标(也就是删除位置前一个元素的下标)
- temp=space[temp].cur;
- }
- int pde=space[temp].cur;// 将删除位置的下标赋给一个整型变量
- space[temp].cur=space[pde].cur;// 将删除位置的游标赋给前一个元素的游标, 此时完成了跨过删除位置的元素链接, 可以释放删除元素了
- Elem=space[pde].data;// 将马上要被删除的元素赋给 elem, 避免数据彻底遗失
- delete_sl(pde);// 释放删除元素
- length--;// 长度减少
- return true;
- }
- int main(){// 测试的主函数
- List a;
- a.CreateList(10);
- cout<<"All elem:";
- a.ListTraverse();
- cout<<"Length:"<<a.ListLength()<<endl;
- int e;
- a.GetElem(5,e);
- cout<<"Get elem:"<<e<<endl;
- cout<<a.LocateElem(e)<<endl;
- a.ChangeElem(5,6);
- cout<<"Change elem:";
- a.ListTraverse();
- a.ListInsert(7,6);
- cout<<"All elem:";
- a.ListTraverse();
- a.ListDelete(10,e);
- cout<<"All elem:";
- a.ListTraverse();
- return 0;
- }
C++ 静态链表的实现(包括各操作的成员函数)
来源: http://www.bubuko.com/infodetail-3446374.html