目录
1.静态链表
2.静态链表的相关操作
(1)数据结构
(2)初始化操作
(3)分配空闲节点
(4)释放节点(回收)
(5)插入节点
(6)在第i个位置处插入节点
(7)删除第i个节点
(8)定位元素和打印
(9)主函数
(10)测试
1.静态链表
单链表是不要求地址是连续的,也就是各个节点之间是离散的分布在内存中的。
静态链表则是分配一整片连续的内存空间,各个节点的地址是连续的,集中存放。
注:静态链表也是通过遍历查找到删除的节点位置和插入节点的位置。
其中上面的空闲表头的指针域为6,表示指向的数组下标为6的位置空闲;而头结点的指针域为2,表示头结点的下一个节点在数组下标为2的地方。
2.静态链表的相关操作
(1)数据结构
#include
#include
#define MAXSIZE 10
typedef int ElemType;
typedef struct Node {
ElemType data;
int cur;
}SLinkList[MAXSIZE];
(2)初始化操作
#include#include #define MAXSIZE 10 typedef int ElemType; typedef struct Node { ElemType data; int cur; }SLinkList[MAXSIZE];
(2)初始化操作
注:这里的空闲表头指针指向的是下一个空闲的位置,在申请节点空间的时候只需要找到空闲表头指针指向的位置即可。
//初始化 void InitSLinkList(SLinkList&space,ElemType&headNode){ //初始化游标 for(int i=0;i(3)分配空闲节点
//判断备用空间链表非空,则返回分配的节点下标,否则返回0 int MallocSLinkList(SLinkList&space){ //从头结点开始 int i=space[0].cur; if(space[0].cur){ space[0].cur=space[i].cur; } return i; }(4)释放节点(回收)
比如现在释放节点a5,其数组下标为7,那么k=7:
(1)首先是将数组下标为7的位置的指针域修改为空闲表头指针指向的空闲位置:space[7].cur=space[0].cur=6;
(2)其次是将空闲表头的指针域修改为刚才释放的节点位置:space[0].cur=7.
//将空闲节点收回到备用链表 void FreeSLinkList(SLinkList&space,int k){ space[k].cur=space[0].cur; space[0].cur=k; }(5)插入节点
//创建一个静态链表 int CreateList(SLinkList&space,ElemType e,int j){ int k=j; //申请空间 int r=MallocSLinkList(space); //将节点插入到r位置 space[r].data=e; //将前驱指针k指向r space[k].cur=r; //移动指针k到r位置 k=r; space[k].cur=0; printf("插入节点成功!n"); return k; }(6)在第i个位置处插入节点
//查找第i-1节点 int FindNode(SLinkList&space,int i,int headNode){ if(i<1||i>MAXSIZE){ printf("插入位置不合法!n"); return -1; } int k=headNode; int j=0; //从头结点开始找到第i-1指针指向的位置 while(k!=0&&j(7)删除第i个节点
//删除节点 void DeleteNode(SLinkList&space,int headNode,int i,ElemType&e){ int k=FindNode(space,i,headNode); if(k==0)return; int m=space[k].cur; //将k指针指向m指针的后继 space[k].cur=space[m].cur; //获取要删除的元素 e=space[m].data; //释放 FreeSLinkList(space,m); printf("删除节点成功!n"); return ; }(8)定位元素和打印
//定位元素的位置 int LocateElem(SLinkList space,ElemType e,int headNode){ int i=space[headNode].cur; while(i&&space[i].data!=e){ i=space[i].cur; } return i; } //打印操作 void PrintSLinkListNode(SLinkList space,int headNode){ int i=space[headNode].cur; while(i!=0){ printf("%dt",space[i].data); i=space[i].cur; } printf("n"); }(9)主函数
int main(){ SLinkList space; int i; int j; ElemType e; ElemType headNode; InitSLinkList(space,headNode); j=headNode; while(1){ int flag=0; MenuSLinkList(); printf("请输入操作: "); scanf("%d",&flag); switch(flag){ case 1: InitSLinkList(space,headNode); printf("初始化成功!n"); break; case 2: printf("请输入元素(-1_end): "); scanf("%d",&e); while(e!=-1){ j=CreateList(space,e,j); printf("请输入元素(-1_end): "); scanf("%d",&e); } break; case 3: printf("请输入插入的位置: "); scanf("%d",&i); printf("请输入插入的值: "); scanf("%d",&e); InsertNode(space,headNode,i,e); break; case 4: printf("请输入删除的节点位置: "); scanf("%d",&i); DeleteNode(space,headNode,i,e); printf("删除的节点 = %dn",e); break; case 5: PrintSLinkListNode(space,headNode); break; default: printf("结束操作n"); } if(flag==6){ break; } } return 0; }(10)测试