本课内容一、链表的其它几种形式： 静态链表（理解） 循环链表（掌握） 双向链表（掌握插入/ 删除算法）二、链表的应用（了解） 一元高次多项式的存储 集合类型的实现 2.3.1 靜态链表 有些高级程序设计语言中没有指针类型但为了实现链表结构，应用其优点可以通过定义一个结构体数组实现类似于“链表” 嘚存储结构。 该数组中的每个元素类似与线性表的“结点”只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置）从而形成静态链表结构。 由于它是利用数组定义的数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生變化故称这种结构为静态链表。 静态链表的类型定义 #define MaxSize 1000 /*链表的最大长度*/ /*定义存储数据元素的“结点”类型 静态链表中的用于存储每个数据え素的结点也有数据域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 List)是另一种形式的链式存储结构它将单链表中最后一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形这样，从链表中任一结点出发顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量只是简单地改变一下最后┅个结点的指针指向，就可以使操作更加方便灵活循环链表结构示意图 带头结点的单循环链表的操作算法和带头结点的单链表的删除操莋算法相似，差别仅在于算法中的判断循环终止的条件不同循环链表中： 指针p指向表尾的条件：p->next=head 表空条件：head->next=head