2.数据结构与算法--线性表(定义)，链式存储结构（静态链表）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了2.数据结构与算法--线性表(定义)，链式存储结构（静态链表），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4052字，纯文字阅读大概需要6分钟。
内容图文
1.静态链表（用数组描述的链表称为静态链表，这种描述方法叫游标实现法）
1.1静态链表存储结构
静态链表的一些规则：
-
元素中有两个部分，一个是放数据，一个是游标，然后把这个结构声明为StaticLinkList的数组形式，
-
静态链表有两个元素是特殊的，第0个元素 ：下标为0，数据是不存放任何东西的，游标的值 是“第一个没有数据的元素的下标”。 另一个特殊的元素：最后一个元素，下标为999，数据是不存放任何东西的，游标的值 是第一个有数据的元素的下标“”。如下图所示
-
通常把未使用的数组元素称为备用链表
-
数组的第0个元素，即下标为0的那个元素的cur 就存放备用链表的第一个节点的下标
-
数组的最后一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中头结点作用
-
游标用来存放下一个待索引元素的下标
-
其他元素的游标，都是指向下一个节点的下标。我们通过游标2，找到下一个元素，元素的下标是2，数据是C，游标是3。通过游标3再找下一个节点，节点的下标是3，数据是D，游标是4。依次可以找到后续的节点。
-
实际上就是通过 游标 索引 下标，从而找到数据
1.2静态链表进行初始化（相当于初始化数组）
bool InitList(StaticLinkList space)
{
int i;
for(i=0; i<MAXSIZE-1; i++)
{
space[i].cur = i + 1; //设置最初的游标
}
space[MAXSIZE-1].cur = 0; //把最后一个数组的游标赋值为0
return true;
}- 创建一个空链表，设置了游标，和最后一个元素的游标
1.3静态链表的插入操作
在插入之前示意图：
第0个元素的游标始终是指向第一个备用元素的下标
要想在数据A 和C 之间插入一个新元素的数据B， 该如何插入操作？
- 在备用链表的第一个元素位置写入新元素的数据B， 此时下标为5，还要让数据A可以找到数据B , 就要把A的游标改为新元素的下标。
- 再将新元素的游标赋值为2，目的是：让新元素找到下一个元素的数据C
- 同时第0个元素的游标始终要指向 “备用链表的第一个元素位置的下标”
/*首先获得空闲分量的下标*/ int Malloc_SLL(StaticLinkList space) { int i = space[0].cur; if(space[0].cur) //链表不为空表 { space[0].cur = space[i].cur //使第一个元素的游标始终指向“备用链表的第一个元素的下标” } return i; //返回 第一个元素的游标 } /*返回L中元素的个数*/ int ListLenth(StaticLinkList L) { int i,j=0; i = L[MaxSize-1].cur; //从最后一个元素的游标开始索引 while(i==0) //i=0时，已经索引到最后一个元素了 { i=L[i].cur; j++; } return j; } bool InsertElem(StaticLinkList L, int i, ElemType e) { int k,j,w; k = MaxSize-1; if(i>ListLength(L)+1 || i<1) { return false; } j = Malloc_SLL(L); if(j) { L[j].data = e; for(w=1; w<i; w++) { k=L[k].cur; } L[j].cur = L[k].cur; L[K].cur = j; } }
代码思路：
- 获取到最后一个元素的下标 k，从而可以得到最后一个元素的游标 L[k].cur
- 判断插入的位置是否合法
- 获取空闲分量的下标，返回第0个元素的游标 i， 其中 i = space[0].cur; Malloc_SLL()函数把“原来第0个元素的游标” 改成了“待插入元素位置的游标”，并且把原来第0个位置元素的游标返回给 i （这里的 i 是Malloc_SLL()函数中的变量 i ）
- 那么通过返回的 j = Malloc_SLL(L); 对j下标所在的data进行赋e值。
- 通过最后一个元素的游标 L[k].cur，可以索引到下一个元素的下标，通过遍历，从而找到第 i-1 个位置的元素游标，即 k = L[k].cur;
- 那么前一个元素的游标就要 赋值 给 待插入元素的游标
- 再把前一个元素的游标 赋值为 待插入元素下标
1.3静态链表的删除操作
例如要删除第3个元素的数据C;
那么就要：
- 第3个位置的数据C先删掉（代码上并不是删除，是把游标和下标的指向关系从新建立而已），在让数据B的游标 赋值为 C当前所在的游标
- 那么既然C的数据空了，就要将备用链表的游标重新回收一下
- 下标为0的游标 要指向 数据C的位置
- 数据C位置的游标要指向 下一个数据为空的下标
代码思路：要删除第3个元素的数据C;
- 获取最后一个元素的下标MaxSize-1，在判断删除的i个元素的合法性
- 要删除元素，其实就是改变游标，让游标无法索引到“待删除的元素”
- 通过下标MaxSize-1，循环索引 i-1 次 k = L[k].cur; 循环后的k为 5
- 把下标为k的游标赋值给j， 将j所在的游标 赋值给 k的游标。（目的是：把待删除元素的游标赋值给下标为5的游标）
- 重新整理备用链表（把数据为空的元素都连在一起）Free_SLL(StaticLinkList space, int i) //把第i个空元素整理进备用链表
- 首先将第0个元素的游标赋值给第i个元素的游标
- 再将 i 赋值给第0个元素的游标
bool ClearELem(StaticLinkList L, int i) //删除链表L的第i个元素
{
int k = MaxSize - 1;
int j;
if(i<1 || i>ListLength(L))
{
return false;
}
for(j=0; j<i-1; j++)
{
k = L[k].cur;
}
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SLL(L, j);
return true;
}
bool Free_SLL(StaticLinkList space, int i) //把第i个空元素整理进备用链表
{
space[i].cur = space[0].cur;
space[0].cur = i;
}
1.4静态链表的优缺点
内容总结
以上是互联网集市为您收集整理的2.数据结构与算法--线性表(定义)，链式存储结构（静态链表）全部内容，希望文章能够帮你解决2.数据结构与算法--线性表(定义)，链式存储结构（静态链表）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】