循环链表及应用PPT学习教案.pptx

会计学
1
循环链表及应用
有些高级程序设计语言中没有指针类型，但为了实现链表结构，应用其优点，可以通过定义一个结构体数组实现类似于“链表” 的存储结构。
该数组中的每个元素类似与线性表的“结点”，只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置），从而形成静态链表结构。
由于它是利用数组定义的，数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生变化，故称这种结构为静态链表。
静态链表
第1页/共33页
静态链表的类型定义
#define MaxSize 1000 /*链表的最大长度*/
/*定义存储数据元素的“结点”类型 ——Snode*/
typedef struct
{ ElemType data; /*存储数据元素的值*/
int cur ; /*存储元素直接后继的下标*/
} Snode;
/*定义静态链表类型SlinkList—结构体数组类型*/
typedef Snode SlinkList[MaxSize];
第2页/共33页
理解：
静态链表中的用于存储每个数据元素的结点也有数据域data和指向下个元素存储位置的域cur，不过这里的cur是个下标,是相对数组第一个元素的偏移,，因此称为静态指针。
为了简化链表操作算法,静态链表也可以设表头结点.
设有变量s定义:
Slinklist s; /*s 为一个静态链表 */
则s[0]表示头结点,s[0].cur指示第一个元素结点的位置
s[i].data 表示第i个数据元素的值
s[i].cur 指示第i个元素的直接后继,即第i+1个元素的存储位置
第3页/共33页
如图（a) 在链表没有使用前，各个结点已经形成一个链，变量AV指示链表的首地址(头结点)。由AV指向的链表称为可利用空间表，可用于管理结点的分配和回收。
∧
∧
∧
∧
∧
∧
第4页/共33页
带头结点的静态链表操作的 算法逻辑与线性链表相似,不过有以下区别:
.
:p=p->next
改为k =s[i].cur
:管理分配给链表的空闲结点
:实现结点的分配，即从空白表获取一个结点
:实现结点的回收，即将删除的结点链接到空白表
静态链表的操作实现
第5页/共33页
将链表空间初始化为一个空白链表/*将数组space的各分量链成一空白链表，space[0].cur为头指针*/void InitSpaceSL(SLinkList space) { int i;  for (int i=0; i<MAXSIZE-1; ++i)  space[i].cur = i+1; /*置链表结束标志,cur为0表示尾结点*/  space[MAXSIZE-1].cur = 0; }
第6页/共33页
——malloc函数/*若备用空间链表非空，则返回分配的结点下标，否则返回0int Malloc_SL(SLinkList space) {  int i = space[0].cur; /*获取空白链表第一个结点的下标*/ if (i>0) /*备用空间不为空*/ space[0].cur = space[i].cur; /*从表中摘下第一个结点*/ return i;} ——将下标为k的空闲结点回收到备用链表void Free_SL(SLinkList space, int k) {  space[k].cur = space[0].cur; /*链接到头结点后*/  space[0].cur = k;}
第7页/共33页
循环链表(Circular Linked List)是另一种形式的链式存储结构。它将单链表中最后一个结点的指针指