数据结构静态链表特别篇

本教程来自 本人博客 越行勤‘s Blog &＃xff0c;欢迎大家访问
域名 https://yingwiki.top

静态链表

我在《 数据结构 第二章 :双链表&＃xff0c;循环链表&＃xff0c;静态链表以及对比总结》&＃xff0c;初步认识了静态链表。

第一次去理解代码&＃xff0c;其实有一点点费力。但是也不是那么复杂&＃xff0c;主要抓住下面这一点

静态链表&＃xff1a;分配一整个连续内存空间每个节点&＃xff0c;每个节点集中安置&＃xff1b;静态链表中没有用指针&＃xff0c;但是数组的索引值 Index充当了指针的作用。

静态链表就是为那行没有指针的编程语言二存在的&＃xff0c;存储数据用的是连续的空间&＃xff0c;但是逻辑上连续的空间&＃xff0c;在物理上无需连续&＃xff0c;还是抓住了链表的特点。

typedef struct
{ElemType data;int cur;//其实可以把它看着指针&＃xff0c;指针也不少一个数吗&＃xff1f;
}SLinkList[MaxSize];


cur: 就是下一个结点的数组下标&＃xff0c;其实可以把它看着指针&＃xff0c;指针也不少一个数吗&＃xff1f;

算法解析

第一次实现静态链表&＃xff0c;我面对的一个问题就是 如何寻找到没有使用的数据结点&＃xff0c;我给出的解决方案是&＃xff1a;

• cur &＃61; 0&＃xff0c;表示结尾
• cur &＃61;MaxSize &＃xff0c;表示没有使用该段空间

所以需要开辟一个没有存储数据&＃xff08;插入结点等操作需要开辟空间&＃xff09;的结点就需要使用循环扫描出cur&＃61;&＃61; MaxSize 的结点&＃xff08;没有使用的结点&＃xff09;。

有没有不需要循环的方法呢&＃xff1f;当然是有的&＃xff0c;我们来看看书上的一个例子。

题目

实现集合运算 $(A-B)U(B-U)$ 来讨论静态链表的算法。

初步理解

为了更好的理解&＃xff0c;我想提讲述出它的具体原理

在静态链表中 存着两个链表

1. 链表1&＃xff08;备用链表&＃xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点
2. 链表2&＃xff08;数据链表&＃xff09;. 头结点为 SLinkList[1] &＃xff08;也可以不是 SLinkList[1] &＃xff0c;只要是空闲结点就可以了&＃xff09;,存储着有数据的结点&＃xff0c;

当然它是如何他是如何存储两个链表在一个数组中呢&＃xff1f;

回想我们单链表是如何找到链表的呢&＃xff1f; 找到头结点

那很简单&＃xff0c;我们也只需要规定&＃xff0c; L[0]为备用链表的头结点&＃xff0c;L[1]为存储数据的头结点

开辟一个存储数据的结点&＃xff1a;从备用链表中取出–>一个结点到数据链表中

删除回收一个存储数据的结点&＃xff1a;从将被删除的结点–>插入到备用链表中

是不是很有启发性呢&＃xff0c;经典的空间换取时间&＃xff0c;当然我们这样多花费了1个空间&＃xff08;备用链表的头结点&＃xff09;&＃xff0c;就避免了时间复杂度为O(n)的大循环。

代码

InitSpace _SL

函数功能&＃xff1a;初始化链表&＃xff0c;由于此时没有存储数据&＃xff0c;其实就是创建 备用链表

void InitSpace _SL(SLinkList &space)
{for(i&＃61;0;i<MaxSize-1;i&＃43;&＃43;) //数组下标从0开始&＃xff0c;只需要循环到 MaxSize-2space[i].cur&＃61;i&＃43;1;space[MaxSize - 1]&＃61;&＃61;0;//0表示NULL ,space[MaxSize - 1]也就是 备用链表的尾结点
}


如上图&＃xff0c;每个cur指向下一个结点。

Malloc_SL

函数功能&＃xff1a;从备用链表中取出&＃xff08;拿出来并在备用链表中删除&＃xff09;一个可以存储数据的新结点&＃xff0c;返回其的数组下标&＃xff08;地址&＃xff09;&＃xff0c;返回0表示分配空间失败

int Malloc_SL(SLinkList &space)
{i&＃61;space[0].cur;//备用链表的第一个结点取出if(space[0].cur)//如果 space[0].cur&＃61;&＃61;0 说明备用链表被使用完了&＃xff0c;分配空间失败space[0].cur&＃61;space[i].cur;//将取出的结点从备用链表中删除return i;
}


Free_SL

函数功能&＃xff1a; 将被删除的结点k,连接到备用链表的头结点之后&＃xff08;回收K结点&＃xff09;

Free_SL(SLinkList &space ,int k)
{space[k].cur&＃61;space[0].cur;sapce[0].cur&＃61;k;
}


画的太丑了

difference

函数作用&＃xff1a;依次此输入 A,B的元素&＃xff0c;计算$(A-B)U(B-U)$&＃xff0c; &＃xff0c;计算结果到space ,S返回数据链表的头结点。

此函数使用许多功能&＃xff0c;插入元素&＃xff0c;删除元素等功能都在这里有体现

当然你要理解 $(A-B)U(B-U)$

void difference(SLinkList &space,int &S)
{InitSpace_SL(space); //初始化静态链表&＃xff08;创建备用链表&＃xff09;S&＃61;Malloc_SL(space); //生成数据链的头结点r&＃61;S; //r为当前A集合链表的表尾scanf(m,n); //输入数据链表的大小 m :A n: B//生成链表A,并填入数据 for(j&＃61;1;j<&＃61;m;&＃43;&＃43;j){i&＃61;Malloc_SL(space);Scanf(space[i].data);//输入数据 space[r].cur&＃61;i; //插入数据到数据链表r&＃61;i; //r为当前A集合链表的表尾}space[r].cur&＃61;0; //数据链尾结点为NULL(0)for(j&＃61;1;j<&＃61;n;j&＃43;&＃43;){scanf(b);p&＃61;S; //p存储着要删除结点前驱结点k&＃61;space[S].cur; //k指向集合A元素的下一个结点//遍历A集合 数据b是否也在A中&＃xff08;是否重复&＃xff09;while(k!&＃61;space[r].cur&&space[k].data!&＃61;b) // k!&＃61;space[r].cur 到达存储A集合链表的表尾 space[k].data!&＃61;b b不在元素 A{p&＃61;k;//p存储着要删除结点前驱结点k&＃61;space[k].cur;//遍历下一个结点}if(k&＃61;&＃61;Space[r].cur)//数据b没有重复&＃xff0c;加入数据b//数据b插入到 r结点之后{i&＃61;Malloc_SL(space);space[i].data&＃61;b; space[i].cur&＃61;space[r].cur;space[r].cur&＃61;i; }else//数据B重复了{space[p].cur&＃61;space[k].cur; //此时K删除点if(r&＃61;&＃61;k) //如果删除的是r结点&＃xff0c;需要改r的指向r&＃61;p;}}
}


看不明白&＃xff0c;多阅读几遍&＃xff0c;就明白了。

假设A集合为 {c,b,e,g,f,d} B为 {a,b,n,f}

那样运行结构为

静态链表代码

上述算法&＃xff0c;创建链表&＃xff0c;插入数据都是整合在difference() 中的。根据上述算法的基本思路&＃xff0c;可以实现一下静态链表的基本操作。可以对比我在《 数据结构 第二章 :双链表&＃xff0c;循环链表&＃xff0c;静态链表以及对比总结》,中实现的静态链表&＃xff0c;插入数据平均时间复杂度不在是O(n)&＃xff0c;经典的空间换时间。

对于链表&＃xff0c;无非就三种操作&＃xff0c;遍历元素&＃xff0c;插入元素&＃xff0c;删除元素&＃xff0c;

在我实现的方法中&＃xff0c;规定

1. 链表1&＃xff08;备用链表&＃xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点
2. 链表2&＃xff08;数据链表&＃xff09;. 头结点为 SLinkList[1],存储着有数据的结点&＃xff0c;

代码

#include/**
关于如何判断 节点是否被使用其实有两种实现方法
1. 专门设置一个数值例如 cur&＃61;-1 表示改节点没有被使用当然这个时有一定的缺点的&＃xff0c;在插入元素的时候也需要去遍历一个元素去找那个节点没有被使用。2. 在静态链表中 存着两个链表
链表1&＃xff08;备用链表&＃xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点
链表2&＃xff08;数据链表&＃xff09;. 头结点为 SLinkList[1],存储着有数据的结点&＃xff0c; 插入元素&＃xff0c;需要从备用链表中取一个元素---到数据链表&＃xff0c;
删除一个结点&＃xff0c;需要从数据链表中被删除结点---链接到备用链表这样&＃xff0c;我们多花费一个空间就可以减少 不少的时间复杂度
**/#define MaxSize 100
typedef struct
{char data;int cur;
}SLinkList[MaxSize];bool Init_SLinkList(SLinkList& L); //初始化链表
bool Insert_SLinkList(SLinkList& L, int i, char e); //按位插入元素
int Locate_SLinkList(SLinkList L, char e); //返回元素e的索引,返回0则不存在
bool GetElem_SLinkList(SLinkList L, int i, char& e);// 按索引查找元素
bool Delte_SLinkList(SLinkList& L, int i, char& e);//删除 第i个元素&＃xff0c;删除数据返回到eint MallocNode(SLinkList& L);//寻找到一个可用 结点 ,返回0&＃xff0c;表示空间用完
bool GetNode_SLinkList(SLinkList L, int i, int& k); //获取第i个结点Node的地址k
bool InsertNext_SLinkList(SLinkList& L, char e, int k);//在任意k结点之后插入元素
bool DeleteNode_SLinkList(SLinkList& L, int k); //删除指定结点,k为删除结点的地址void test()
{SLinkList L;Init_SLinkList(L);char e;//插入数据测试for (int i&＃61;1; i < 10; i&＃43;&＃43;){InsertNext_SLinkList(L, &＃39;a&＃39;&＃43;i-1, i);}printf("插入数据完成^_^\n \n");int i&＃61;L[1].cur;int j&＃61;1;while (i){printf("第%3d个数据为 %3c cur为%3d\n", j, L[i].data,L[i].cur );i &＃61; L[i].cur;j&＃43;&＃43;;}//获取修改数据测试GetElem_SLinkList(L, 4, e);printf("第 4个数据为 %3c\n\n", e);Insert_SLinkList(L, 3, &＃39;z&＃39;);printf("在第3个数据插入 z 完成\n");GetElem_SLinkList(L, 3, e);printf("第 3个数据为 %3c\n\n", e);GetElem_SLinkList(L, 4, e);printf("第 4个数据为 %3c\n\n", e);printf("z是第%3d个元素\n", Locate_SLinkList(L, &＃39;z&＃39;));//删除数据测试printf("删除第 3个元素\n");Delte_SLinkList(L, 3, e);i &＃61; L[1].cur;j &＃61; 1;while (i){printf("第%3d个数据为 %3c cur为%3d\n", j, L[i].data, L[i].cur);i &＃61; L[i].cur;j&＃43;&＃43;;}getchar();
}
int main()
{test();return 0;
}/*
初始化静态链表&＃xff0c;其实就在创建备用链表
*/
bool Init_SLinkList(SLinkList& L)
{//备用连的头结点 L[0]&＃xff0c;创建备用链表for (int i &＃61; 2; i < MaxSize - 1; i&＃43;&＃43;) //遍历到MaxSize -2即可L[i].cur &＃61; i&＃43;1;//第一个结点从2开始L[0].cur &＃61; 2;//备用链表表尾L[MaxSize-1].cur &＃61; 0;//创建数据链表的头结点 L[1]L[1].cur &＃61; 0;return true;
}
/*
返回一个备用链表里的地址
0表示链表已满
*/
int MallocNode(SLinkList& L)
{int i &＃61; L[0].cur;//从备用链表取出的结点if (L[0].cur)//如果备用链表没有满L[0].cur &＃61; L[i].cur;//该结点从备用链表中删除return i;
}bool DeleteNode_SLinkList(SLinkList& L, int k)
{//将k结点和后面一个结点交换数据int p &＃61; L[k].cur;L[k].data &＃61; L[p].data;L[k].cur&＃61; L[p].cur;//删除结点pL[p].cur &＃61; L[0].cur; L[0].cur &＃61; p;return true;
}bool GetNode_SLinkList(SLinkList L, int i, int& k)
{if (i<1 || i>MaxSize - 2)return false;int p &＃61; L[1].cur;int j &＃61; 1;//计数器//遍历数据链表while (p && j < i){p &＃61; L[p].cur;j&＃43;&＃43;;}if (!p && j > i)//i<0或者第i个数据不存在return false;k &＃61; p;return true;
}bool InsertNext_SLinkList(SLinkList& L, char e, int k)
{if (k<1 || k >&＃61; MaxSize) //结点不存在return false;int p &＃61; MallocNode(L);if (!p)//如果分配失败return false;L[p].data &＃61; e;L[p].cur &＃61; L[k].cur;L[k].cur &＃61; p;return false;
}bool Insert_SLinkList(SLinkList& L, int i, char e)
{int k;if (!GetNode_SLinkList(L, i-1, k))return false;return InsertNext_SLinkList(L, e, k);
}int Locate_SLinkList(SLinkList L, char e)
{int k &＃61; L[1].cur;int i &＃61; 1;while (k && L[k].data !&＃61; e){k &＃61; L[k].cur;i&＃43;&＃43;;}if (k &＃61;&＃61; 0)//如果e不存在i &＃61; 0;return i;
}bool GetElem_SLinkList(SLinkList L, int i, char& e)
{int k;if (!GetNode_SLinkList(L, i, k))return false;e &＃61; L[k].data;return false;
}
bool Delte_SLinkList(SLinkList& L, int i, char& e)
{int k;if (!GetNode_SLinkList(L, i,k ))return false;e &＃61; L[k].data;DeleteNode_SLinkList(L, k);return false;
}