静态链表借助数组来描述线性表的链式存储结构，结点有数据域data和游标cur
需要注意的地方有如下几点：
1.数组的第一个元素和最后一个元素的data不存放数据。
2.数组第一元素的cur为第一个未使用 数组元素的下标 。
3.数组的最后一个元素的cur为已使用数组元素的下标，开始为0。
4.未使用的数组元素称之为备用链表。
5.有数据的最后一个数组的游标为0。
1.声明结构体
typedef struct { ElemType data; //数据 int cur; //逻辑里下一个元素的位置下标 }component,staticLinkList[MAXSIZE];
2.初始化静态链表
void init(staticLinkList space) { int i; for(i=0;i<MAXSIZE-1;i++) { space[i].cur=i+1; } space[MAXSIZE-1].cur=0; //一开始没有数据 }
3.插入元素分为两步： 获取空闲分量的下标 插入数据
//获取空闲分量的下标 int mallocElem(staticLinkList space) { int i=space[0].cur; //备用链表第一个元素储存第一个未使用数组元素的下标 if(space[0].cur) //当备用数组不为空时 { space[0].cur=space[i].cur; //把i的下一个分量用来做备用 } return i; //返回空闲分量的下标 } //插入数据 在静态链表L中第i个元素前插入元素e void insertElem(staticLinkList T,int i,char e) { int j,k; k=MAXSIZE-1; //k为数组的最后一个元素的下标 //对i范围进行判断 if(i<1||i>getLength(T)+1) { printf("无法插入 "); } else { j=mallocElem(T); //j是第一个空闲分量的下标 if(j) //还有空闲分量 { T[j].data=e; for(int l=1;l<i;l++) //k的下标变成第i-1个元素的下标 { k=T[k].cur; } T[j].cur=T[k].cur; T[k].cur=j; } } }
4.删除元素 第i个位置元素
void deleteElem(staticLinkList T,int i) { int j,k; k=MAXSIZE-1; //k为数组的最后一个元素的下标 //对i范围进行判断 if(i<1||i>getLength(T)) { printf("无法删除 "); } else { for(j=1;j<i;j++) //将k的下标变成第i-1个元素的下标 { k=T[k].cur; } j=T[k].cur; T[k].cur=T[j].cur; //第i-1个元素游标为i+1个元素 freeElem(T,j); //释放第i个位置元素 } }
完整的代码如下
#include<stdio.h> #include<stdlib.h> //数组的第一个元素和最后一个元素的data不存放数据。 //数组第一元素的cur为第一个未使用 数组元素的下标 #define MAXSIZE 20 //数组的最后一个元素的cur为已使用数组元素的下标，开始为0 typedef char ElemType; // 未使用的数组元素称之为备用链表 // 有数据的最后一个数组的游标为0 typedef struct { ElemType data; //数据 int cur; //逻辑里下一个元素的位置下标 }component,staticLinkList[MAXSIZE]; int getLength(staticLinkList T); //初始化静态链表 void init(staticLinkList space) { int i; for(i=0;i<MAXSIZE-1;i++) { space[i].cur=i+1; } space[MAXSIZE-1].cur=0; //一开始没有数据 } //获取空闲分量的下标 int mallocElem(staticLinkList space) { int i=space[0].cur; //备用链表第一个元素储存第一个未使用数组元素的下标 if(space[0].cur) //当备用数组不为空时 { space[0].cur=space[i].cur; //把i的下一个分量用来做备用 } return i; //返回空闲分量的下标 } //插入数据 在静态链表L中第i个元素前插入元素e void insertElem(staticLinkList T,int i,char e) { int j,k; k=MAXSIZE-1; //k为数组的最后一个元素的下标 //对i范围进行判断 if(i<1||i>getLength(T)+1) { printf("无法插入 "); } else { j=mallocElem(T); //j是第一个空闲分量的下标 if(j) //还有空闲分量 { T[j].data=e; for(int l=1;l<i;l++) //k的下标变成第i-1个元素的下标 { k=T[k].cur; } T[j].cur=T[k].cur; T[k].cur=j; } } } //释放元素为空分量 ,第i位置的 void freeElem(staticLinkList space,int k) { space[k].cur=space[0].cur; space[0].cur=k; } //删除元素 第i个位置元素 void deleteElem(staticLinkList T,int i) { int j,k; k=MAXSIZE-1; //k为数组的最后一个元素的下标 //对i范围进行判断 if(i<1||i>getLength(T)) { printf("无法删除 "); } else { for(j=1;j<i;j++) //将k的下标变成第i-1个元素的下标 { k=T[k].cur; } j=T[k].cur; T[k].cur=T[j].cur; //第i-1个元素游标为i+1个元素 freeElem(T,j); //释放第i个位置元素 } } //查找 第i个位置 int getElem(staticLinkList T,int i) { int j,k; k=MAXSIZE-1; //k为数组的最后一个元素的下标 //对i范围进行判断 if(i<1||i>getLength(T)) { printf("无法查找 "); } else { for(j=0;j<i;j++) { k=T[k].cur; } return T[k].data; } } // 打印数据 void print(staticLinkList T) { int k=MAXSIZE-1; //k为数组的最后一个元素的下标 for(int i=0;i<getLength(T);i++) { k=T[k].cur; printf("%c ",T[k].data); } printf(" "); } int main() { staticLinkList T; init(T); //初始化静态链表 int num; //输入指令 char e; //添加的字母数值 int i; //位置 printf("结束操作-----0 "); printf("链表插入操作-----1 "); printf("链表删除操作-----2 "); printf("链表查找操作-----3 "); printf("链表打印操作-----4 "); printf("你的指令为 "); scanf("%d",&num); while(num!=0) { switch(num) { case 1: //插入操作 printf("输入你想要插入的数值"); getchar(); //必须，不然下面一行getchar失效 e=getchar(); printf("输入你想要插入第几个位置"); scanf("%d",&i); insertElem(T,i,e); break; case 2: //删除操作 printf("输入你想要删除第几个位置"); scanf("%d",&i); deleteElem(T,i); break; case 3: //查找操作 printf("输入你想要查找第几个位置"); scanf("%d",&i); e=getElem(T,i); printf("第i个位置的值为: %c ",e); break; case 4: //打印操作 print(T); break; default: printf("你输入的指令不正确 "); } printf("你的下一步指令为 "); scanf("%d",&num); } } int getLength(staticLinkList T) { int j=0; int i=T[MAXSIZE-1].cur; //i为第一个储存元素的下标 while(i>0) { i=T[i].cur; //向下搜索 j++; } return j; }
在百度上查静态链表很久，看别人的写的文章，一直看不懂。最后通过看静态链表的教学视频，自己重新写一片，才勉强搞清楚
主要是网上没有搜索到完整可以跑的静态链表，写完后分享一下。