当前位置:网站首页>使用C语言实现静态链表
使用C语言实现静态链表
2022-08-09 23:28:00 【Keep_Trying_Go】
目录
1.静态链表
单链表是不要求地址是连续的,也就是各个节点之间是离散的分布在内存中的。
静态链表则是分配一整片连续的内存空间,各个节点的地址是连续的,集中存放。
注:静态链表也是通过遍历查找到删除的节点位置和插入节点的位置。
其中上面的空闲表头的指针域为6,表示指向的数组下标为6的位置空闲;而头结点的指针域为2,表示头结点的下一个节点在数组下标为2的地方。
2.静态链表的相关操作
(1)数据结构
#include<stdio.h>
#include<stdlib.h>
#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<MAXSIZE-1;i++){
space[i].cur=i+1;
}
//确定链尾
space[MAXSIZE-1].cur=0;
//申请头结点
headNode=MallocSLinkList(space);
}
(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<i-1){
j++;
k=space[k].cur;
}
return k;
}
//在第i个节点之前插入节点e
void InsertNode(SLinkList&space,int headNode,int i,ElemType e){
int k=FindNode(space,i,headNode);
if(k==0)return;
int m=MallocSLinkList(space);
if(m!=0){
//将节点e插入到位置k后
space[m].data=e;
//将m的指针指向k的指针后继
space[m].cur=space[k].cur;
//将k指针指向m
space[k].cur=m;
printf("插入节点成功!\n");
return ;
}else{
printf("插入节点失败!\n");
return ;
}
}
(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("%d\t",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("删除的节点 = %d\n",e);
break;
case 5:
PrintSLinkListNode(space,headNode);
break;
default:
printf("结束操作\n");
}
if(flag==6){
break;
}
}
return 0;
}
(10)测试
边栏推荐
猜你喜欢
随机推荐
下班后用微信处理工作时发病身亡,法院判决:工伤!
When knowledge and action are one
In-depth understanding of multithreading (Part 1)
【SSL集训DAY3】控制棋盘【二分图匹配】
阿雷的血压有些低
Creo5.0入门教程赠素材
【集训DAY3】石油储备计划【树形DP】
AUTOCAD——形位公差如何标注、CAD打断于点的操作
The technical aspects of the byte have been passed, and the salary has been negotiated for 20K*13, but the result is still being brushed. I asked the HR why...
《GB5084-2021》PDF下载
ECCV 2022 | 微软开源TinyViT :搞定小模型的预训练能力
《MySQL入门很轻松》第4章:数据表中存放的数据类型
arm-4-裸板开发
CST Studio Suite 2021软件安装包和安装教程
go语言的并发原理(goroutine)
【集训DAY5】快速排序【模拟】【数学】
CAD 连接两个相交线
Distributed database problem (2): data replication
微信小程序获取微信用户步数
直播app开发搭建,flutter 实现自适应、自动换行、相对布局