静态链表的实现代码：
说是静态链表实质就是用数组来模拟，如果学过算法课就知道数组模拟很常用，没有这算法练习的经历就要好好推敲
基础线性表用静态链表模拟，我直接搞成一个小系统方便查看各类操作
#include<iostream>
#define OK 10
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 1000
using namespace std;
/*静态链表构建线性表:数组模拟链表法(无指针游标指向法)*/
typedef char ElemType;
typedef struct
{
ElemType data;
int cur; /*游标(Cursor),为0时表示无指向*/
/*用cur来模拟指针,适用于无指针的编程语言*/
}Component,LinkList[MAXSIZE];
/*Compoenet:组成成分;LinkList:数组模拟链表*/
/*建表&初始化*/
bool InitLinkList(LinkList& space)
{
int i;
for(i = 0;i < MAXSIZE - 1;i ++) /*将空的静态链表各个游标初始化*/
{
space[i].cur = i + 1;
space[i].data = 0;
}
space[MAXSIZE-1].cur = 0; /*目前静态链表为空,最后一个元素的cur为0*/
/*最后一个存储单元作用相当于头结点*/
FLAG:/*跳跃FLAG*/
char choice; /*用于询问是否赋值操作的变量*/
cout<<"是否对静态链表赋值?\n(是:Y/y,否:N/n)";
cin>>choice;
if(choice == 'Y'||choice == 'y')
{
int n;
cout<<"请设置表长 : "<<endl;
cin>>n;
for(int i = 1;i <= n;i ++)
{
cout<<"第"<<i<<"个数据:";
cin>>space[i].data;
}
space[MAXSIZE-1].cur = 1; /*让最后一个"头结点"时刻指向链表首游标*/
cout<<"赋值完成!"<<endl;
return OK;
}
else
if(choice == 'N'||choice =='n')
{
return OK;
}
else
{
cout<<"!!!!!!!!请您审清题意,重新输入!!!!!!!!!"<<endl;
goto FLAG;
}
}
/*备用链表函数:判断此时内存中是否还有备用的空间,若存在返回对应下标*/
int Malloc_SLL(LinkList space)
{
int i = space[0].cur; /*当前数组第一个元素的cur存的值
就是要返回的第一个备用的空闲的下标*/
if(space[0].cur) /*若还有备用空间先更新再返回*/
space[0].cur = space[i].cur;/*由于要拿出一个份量来使用了,所以我们
就得把它的下一个分量用来做备用*/
return i;
}
/*统计链表长度*/
int ListLength(LinkList L)
{
int sum = 0;
int i = L[MAXSIZE-1].cur;
while(i) /*遍历链表统计个数*/
{
i = L[i].cur;
sum++;
}
cout<<"表长为:"<<sum<<endl;
return sum;
}
/*插入操作*/
bool ListInsert(LinkList L,int i,ElemType e)
{
int j,k,l;
k = MAXSIZE - 1; /*k做最后一个元素的下标*/
if(i < 1||i > ListLength(L) + 1)
{
return ERROR;
}
j = Malloc_SLL(L);
if(j) /*判断此时备用链表中是否还有备用空间*/
{
L[j].data = e;
for(l = 1;l <= i - 1;l ++)/*找到第i个元素之前的cur*/
k = L[k].cur;
L[j].cur = L[k].cur;/*把第i个元素之前的cur赋值给新元素的cur*/
L[k].cur = j; /*把新元素的下标赋值给第i个元素之前元素的cur*/
return OK;
}
return ERROR;
}
/*回收函数*/
void Free_SSL(LinkList space,int k)
{
space[k].cur = space[0].cur;/*把第一个元素cur值赋给要删除的分量cur*/
space[0].cur = k; /*把要删除的分量下标赋值给第一个元素的cur*/
}
/*删除表中第i个元素*/
bool ListDelete(LinkList L,int i)
{
int j,k;
if(i < 1||i > ListLength(L))
{
return ERROR;
}
k = MAXSIZE - 1;
for(j = i;j <= i - 1;j ++)/*用j做循环变量来遍历到i的前一位下表值返给k*/
{
k = L[k].cur;
}
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SSL(L,j); /*回收重利用删除的结点*/
return OK;
}
/*显示表中所有数据*/
bool ShowLinkList(LinkList L)
{
int i = L[MAXSIZE-1].cur;
while(i)
{
cout<<"第"<<i<<"个数据:"<<L[i].data<<endl;
i = L[i].cur;
}
return OK;
}
/*查找第i个数据*/
bool Search(LinkList L,char i)
{
int j = MAXSIZE-1;
int n = 0,sum;
sum = ListLength(L);
while(L[L[j].cur].data)
{
j = L[j].cur;
}
if(L[L[j].cur].data)
{
cout<<"第"<<i<<"个数据为:"<<L[i].data<<endl;
return OK;
}
return ERROR;
}
/*菜单*/
void menu()
{
LinkList L;
int choice;
while(1)
{
cout<<"\t*************静态链表系统****************"<<endl;
cout<<"\t 1-------建立空的线性表 "<<endl;
cout<<"\t 2-------往线性表中插入元素 "<<endl;
cout<<"\t 3-------对线性表中进行指定删除 "<<endl;
cout<<"\t 4-------显示当前内存中的所有数值"<<endl;
cout<<"\t 5-------查找线性表中具体元素 "<<endl;
cout<<"\t 6-------显示当前线性表的长度 "<<endl;
cout<<"\t 7-------退出界面 "<<endl;
cout<<"\t******************************************"<<endl;
cout<<endl<<"请输入菜单号<0~6> : ";
cin>>choice;
switch(choice)
{
case 1:
if(InitLinkList(L)) cout<<"创建完成!"<<endl;
else cout<<"创建失败!"<<endl;
if(L){cout<<"地址为空!"<<endl;}
break;
case 2:
int i;
cout<<"请输入你想要插入表中的位置 :"; cin>>i;
char e;
cout<<"请输入你想要插入的数据 :"; cin>>e;
if(ListInsert(L,i,e)) cout<<"插入完成!"<<endl;
else cout<<"插入失败!"<<endl;
break;
case 3:
int j;
cout<<"请输入你想要删除表中第 "<<j<<"个数据"<<endl; cin>>j;
if(ListDelete(L,j)) cout<<"删除完成!"<<endl;
else cout<<"删除失败!"<<endl;
break;
case 4:system("cls");
if(L[MAXSIZE-1].cur) {cout<<"内存为空!"<<endl;break;}
if(ShowLinkList(L)) cout<<"打印完成!"<<endl;
else cout<<"打印失败!"<<endl;
break;
case 5:
int d,b;
cout<<"请输入你想要查找的第具体数据:";cin>>d;
b = Search(L,d);
if(b) cout<<"查找成功!"<<endl;
else cout<<"查找失败!"<<endl;
break;
case 6:
if(ListLength(L))
cout<<"统计成功!"<<endl;
else
cout<<"统计失败!"<<endl;
break;
case 7:
exit(0);
break;
default:cout<<"输入指令不存在!"<<endl;break;
}
}
}
int main()
{
menu();
return 0;
}
考研数据结构目录:
https://www.acwing.com/file_system/file/content/whole/index/content/5394132/
