第4课--循环链表及应用.ppt

本课内容 一、链表的其它几种形式： 静态链表（理解） 循环链表（掌握） 双向链表（掌握插入/ 删除算法） 二、链表的应用（了解） 一元高次多项式的存储 集合类型的实现 有些高级程序设计语言中没有指针类型，但为了实现链表结构，应用其优点，可以通过定义一个结构体数组实现类似于“链表” 的存储结构。 该数组中的每个元素类似与线性表的“结点”，只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置），从而形成静态链表结构。 由于它是利用数组定义的，数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生变化，故称这种结构为静态链表。 静态链表的类型定义 #define MaxSize 1000 /*链表的最大长度*/ /*定义存储数据元素的“结点”类型 ——Snode*/ typedef struct { ElemType data; /*存储数据元素的值*/ int cur ; /*存储元素直接后继的下标*/ } Snode; /*定义静态链表类型SlinkList—结构体数组类型*/ typedef Snode SlinkList[MaxSize]; 理解： 静态链表中的用于存储每个数据元素的结点也有数据域data和指向下个元素存储位置的域cur，不过这里的cur是个下标,是相对数组第一个元素的偏移,属于相对地址.但是所起的作用与线性链表中的指针next相同，因此称为静态指针。 为了简化链表操作算法,静态链表也可以设表头结点. 设有变量s定义: Slinklist s; /*s 为一个静态链表 */ 则s[0]表示头结点,s[0].cur指示第一个元素结点的位置 s[i].data 表示第i个数据元素的值 s[i].cur 指示第i个元素的直接后继,即第i+1个元素的存储位置 如图（a) 在链表没有使用前，各个结点已经形成一个链，变量AV指示链表的首地址(头结点)。由AV指向的链表称为可利用空间表，可用于管理结点的分配和回收。 静态链表的操作实现 带头结点的静态链表操作的 算法逻辑与线性链表相似,不过有以下区别: 1.需要用户自己实现类似于malloc和free函数的操作. 2.线性表中向后移动指针的操作:p=p-next 改为k =s[i].cur 算法2.14:管理分配给链表的空闲结点 算法2.15:实现结点的分配，即从空白表获取一个结点 算法2.16:实现结点的回收，即将删除的结点链接到空白表 算法2.14 将链表空间初始化为一个空白链表/*将数组space的各分量链成一空白链表，space[0].cur为头指针*/void InitSpaceSL(SLinkList space) { int i;  for (int i=0; iMAXSIZE-1; ++i)  space[i].cur = i+1; /*置链表结束标志,cur为0表示尾结点*/  space[MAXSIZE-1].cur = 0; }  算法2.15——malloc函数/*若备用空间链表非空，则返回分配的结点下标，否则返回0int Malloc_SL(SLinkList space) {  int i = space[0].cur; /*获取空白链表第一个结点的下标*/ if (i0) /*备用空间不为空*/ space[0].cur = space[i].cur; /*从表中摘下第一个结点*/ return i;} 算法2.16——将下标为k的空闲结点回收到备用链表void Free_SL(SLinkList space, int k) {  space[k].cur = space[0].cur; /*链接到头结点后*/  space[0].cur = k;}  例： 求线性表长度Getlen(L)函数、查找运算locate(L,x)函