【静态链表】
程序员文章站
2024-01-19 09:52:58
...
本文围绕以下四个部分展开:
一、静态链表
二、插入
三、删除
四、优缺点
一、静态链表
1. 概念
C语言有指针,Java、C#等有对象引用机制,因此也间接实现了指针的某些作用。但对于像Basic、Fortran等早期的高级语言,是没有指针的。
若不使用指针,如何处理链表结构?使用数组来代替指针,来描述单链表。
这种用数组描述的链表叫做静态链表。(给没有指针的高级语言设计的一种实现单链表能力的方法。)
游标实现法:
让数组的元素均由两个数据域组成:data(数据域)和cur(游标)。即:数组的每个下标都对应一个data和一个cur。
data:用来存放数据元素(要处理的数据)。
cur:相当于单链表的next指针,存放该元素的后继在数组中的下标。
2. 静态链表存储结构
3. 注意
(1)通常将数组建立得大一些,以便有一些空闲空间可以便于插入时不至于溢出。
(2)数组的第一个和最后一个元素不存数据,作为特殊元素处理。
4. 例子
二、插入
例子:上图中,在乙和丁之间插入丙。
(1)动态链表中,结点的申请使用的是malloc()函数。在静态链表中,操作的是数组,因此必须自己实现这样的函数,用来做插入操作。
解决办法:将所有未被使用过的及已被删除的分量用游标链成一个备用链表。每当插入时,从备用链表上取得第一个结点作为待插入的新结点。
(2)插入的算法如下:
三、删除
例子:上图中,删除甲。
(1)动态链表中,结点的申请使用的是free()函数。在静态链表中,操作的是数组,因此必须自己实现这样的函数,用来做删除操作。
其中,j=L[999].cur=1, L[k].cur=L[j].cur,即:L[999].cur=L[1].cur=2。意思是:甲已删除,现在乙是第一个元素。
代码中的:Free_SSL(L,j);如下。
代码中,space[1].cur=space[0].cur=8,意思是:把8给“甲”所在下标为1的分量的cur。space[0].cur=k=1,意思是:让删除的位置成为第一个优先空位,把它存入第一个元素(下标为0)处的cur中。
四、优缺点
整理时重点参考:《大话数据结构》程杰著
一、静态链表
二、插入
三、删除
四、优缺点
一、静态链表
1. 概念
C语言有指针,Java、C#等有对象引用机制,因此也间接实现了指针的某些作用。但对于像Basic、Fortran等早期的高级语言,是没有指针的。
若不使用指针,如何处理链表结构?使用数组来代替指针,来描述单链表。
这种用数组描述的链表叫做静态链表。(给没有指针的高级语言设计的一种实现单链表能力的方法。)
游标实现法:
让数组的元素均由两个数据域组成:data(数据域)和cur(游标)。即:数组的每个下标都对应一个data和一个cur。
data:用来存放数据元素(要处理的数据)。
cur:相当于单链表的next指针,存放该元素的后继在数组中的下标。
2. 静态链表存储结构
3. 注意
(1)通常将数组建立得大一些,以便有一些空闲空间可以便于插入时不至于溢出。
(2)数组的第一个和最后一个元素不存数据,作为特殊元素处理。
4. 例子
二、插入
例子:上图中,在乙和丁之间插入丙。
(1)动态链表中,结点的申请使用的是malloc()函数。在静态链表中,操作的是数组,因此必须自己实现这样的函数,用来做插入操作。
解决办法:将所有未被使用过的及已被删除的分量用游标链成一个备用链表。每当插入时,从备用链表上取得第一个结点作为待插入的新结点。
(2)插入的算法如下:
三、删除
例子:上图中,删除甲。
(1)动态链表中,结点的申请使用的是free()函数。在静态链表中,操作的是数组,因此必须自己实现这样的函数,用来做删除操作。
其中,j=L[999].cur=1, L[k].cur=L[j].cur,即:L[999].cur=L[1].cur=2。意思是:甲已删除,现在乙是第一个元素。
代码中的:Free_SSL(L,j);如下。
代码中,space[1].cur=space[0].cur=8,意思是:把8给“甲”所在下标为1的分量的cur。space[0].cur=k=1,意思是:让删除的位置成为第一个优先空位,把它存入第一个元素(下标为0)处的cur中。
四、优缺点
整理时重点参考:《大话数据结构》程杰著