静态链表的总结

1.静态链表的定义：用数组描述的链表就叫做静态链表

2.为什么有静态链表：因为有些高级语言没有向c语言的指针，有人想出来用数组来代替指针，来描述单链表。

3.怎样定义静态链表：

typedef struct { int data;//数据 int cursor;//游标 }Componet,StaticLinkList[MAXSIZE];

静态链表最基本的两部分就是：

第一部分：数据（data）,存放数据

第二部分：游标(cursor)，存放该元素的后继在数组中的下标，相当于单链表中的next指针。

对于静态链表：下面的内容非常的重要：

静态链表的第一个元素和最后一个元素要作为特殊的元素处理，这两个元素是不存数据的。

我们首先知道一个概念：

备用链表：我们把未被使用的数组元素称为备用链表。

1）静态链表中第一个元素的游标cursor(下标为0)：存放备用链表的第一个结点的下标。

2）静态链表中最后一个元素的游标cursor：存放第一个有数值的元素的下标。

例如：如图

静态链表的总结

其中黑色(1,2,3,4)即是data，红色（用绿色圈的）即是cursor。最下面的为下标

从图中我们可以得知：备用链表的第一个下标应该是4，则第一个元素的cursor=4，第一个有数值的下标1，则最后一个元素的cursor=1，有数值的元素的cursor则为它后继元素的下标。所以值为2的元素的cursor=2，值为3的元素的cursor=3，因为数值为4的元素为最后一个元素，所以它的cursor=0，不指向其他元素。

静态链表的一些基本操作

1）定义一个静态链表结构：

typedef struct { int data;//数据 int cur;//游标 }Componet,StaticLinkList[MAXSIZE];

1）初始化静态链表

/* 初始化静态链表 */ bool initLinkList(StaticLinkList space) { int i; for(i=0;i

上面的是初始化一个空的静态链表，此时整个数组就是一个备用链表，备用链表的cursor都是下一个元素的的下标，所以space[i].cur = i+1，因为我们要关注第一个元素和最后一个元素的cursor，上面的例子，第一个元素的cursor是备用链表的第一个元素，即下标为1，space[0].cur =1,最后一个元素的cursor是存放第一个有数值元素的下标，因为此时这个初始化静态链表还没有数值，所以最后一个元素为0，即space[MAXSIZE-1].cur = 0.

2）静态链表的插入

在动态链表中我们利用c语言的malloc函数来申请结点，但是静态链表操作的是数组，所有我们需要自己实现malloc。

malloc的函数如下：

int malloc_LL(StaticLinkList space) { int i = space[0].cur; if(space[0].cur) space[0].cur = space[i].cur; return i; }

我们知道，对于静态链表，我们要着重关注第一个元素和最后一个元素，第一个元素的cursor是备用链表的第一个元素的下标，最后一个元素的cursor是第一个存放数值元素的下标，在malloc_LL中

int i = space[0].cur,i指的就是备用链表第一个元素的下标，在第一个图中i=4，当插入一个元素时，这是第一个元素的cursor就需要改变，即第一个元素的cursor等于这个元素的cursor，即space[0].cur = space[i].cur,在第一个图中如果只插入值1，解释上面的代码

int i = space[0].cur=1 if(true) { space[0].cur=space[1].cur=2 } return 1;

下面是插入的代码：

/* 插入静态链表 */ bool insertLinkList(StaticLinkList space,int pos,int val) { int j,k,l; k = MAXSIZE-1; if(pos<1||pos>ListLength(space)+1) return false; j = malloc_LL(space); if(j) { space[j].data = val; for(l=1;l<=pos-1;l++) k = space[k].cur; space[j].cur = space[k].cur; space[k].cur = j; return true; } return false; }

解释上面的代码

第10行：j=malloc_LL(space);分配一个空间，用来存放将要插入的值，返回的就是备用链表的第一个元素下标

第13行：space[j].data = val,把下标为j的元素赋值为val

第14-15行：循环直到指定位置的上一个元素的下标，k=space[k].cur:k的值就是pos上一个元素cursor的值，例如第一张图如果在第pos=3插入，则如下循环

for(l=1;l<=2;l++) { k=space[MAXSIZE-1].cur=1 } for(l=2;l<=2;l++) { k=space[1].cur=2 }

此时l=3时，会跳出循环，此时k=2,即pos=3的上一个元素的下标。

第16-17行：如图解释

静态链表的总结

上图的22就是要插入的数据，插入的位置pos=3，所以我们只需做如下两步即可

第一步：将pos上一个元素k=2的cursor=3赋值给值为22，下标为4的cursor，即space[j].cur=space[k].cur,space[4].cur=space[2].cur=3

第二步：将将pos上一个元素k=2的cursor指向值为22，下标为4，j=4.最终的图为上图的下面

3）显示静态链表的数据

/* 显示静态链表中所有的数据 */ void showLinkList(StaticLinkList space) { int k = MAXSIZE-1; while(space[k].cur) { k = space[k].cur; printf("%d ",space[k].data); } printf("\n"); }

对代码的解释：

我们知道，对于静态链表，我们要着重关注第一个元素和最后一个元素，第一个元素的cursor存放的是备用链表的第一个元素的下标，最后一个元素存放的是第一个有数值元素的下标，所以我们要遍历元素，需要找到第一个存放元素的下标，即从最后一个元素的cursor中可以获取。当space[k].cur不等于0时，说明还有存放数值的元素。k=space[k].cur循环存放值得下标

4）获取静态链表的长度

int ListLength(StaticLinkList space) { int j=0; int i = space[MAXSIZE-1].cur; while(i) { i = space[i].cur; j++; } return j; }

5）静态链表的删除

删除时我们要释放被删除的元素，

free_LL函数

/* 删除指定的结点 */ bool deleteLinkList(StaticLinkList space,int pos) { int j,k; if(pos<1||pos>ListLength(space)) return false; k = MAXSIZE-1; for(j=1;j<=pos-1;j++) k = space[k].cur; j = space[k].cur; space[k].cur = space[j].cur; free_LL(space,pos); return true; } /* 释放删除的结点 */ void free_LL(StaticLinkList space,int k) { space[k].cur = space[0].cur; space[0].cur = k; }
 

  
 










                                                        版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227042.html原文链接：https://javaforall.net