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

一、基础知识题 1. 请说明在线性链表中设置头结点的意义。 2. 顺序表有哪些优点？请分析在什么情况下使用顺序表较好。 3. 请分析链式结构的优缺点。 一、思考与练习 （1）顺序结构线性表的特点是__________________________，在顺序表中插入一个元素，平均需要移动________个元素，移动个数与_______________有关。但是，在顺序表中进行查找比较方便，可以实现________查找。 （2）在单链表中，逻辑上相邻的元素物理上____________，在表中插入或删除一个元素只需____________无须移动元素，但是查找链表中的元素都必须从________开始，只能进行________查找。 （3）带头结点的线性链表为空的条件是____________________，带头结点的循环链表为空的条件是___________________。 作业 1. 设线性表A和B为递增有序的单链表，试编写算法，将二表归并为一个递减有序的线性表，并利用原来的结点空间存放新表 Linklist MerageSort(Linklist La,Linklist Lb) 2. 设计一算法，将带头结点的线性链表进行逆置。 即逻辑关系为(a,b,c,d,e) 的表，逆置后变为(e,d,c,b,a) LinkList ReverList(Lnode *Head) status InsertElem(DuLinkList L,int i, ElemType e) { DNode *p=L,*s; int pos=0; /*找待插入结点的位置i，令变量p指向它*/ while (p posi) { p=p-next; pos++; } if (p==null|| posi) return error; /*插入位置i非法*/ /*生成新结点,并填充数据*/ s=(DNode *)malloc(sizeof(DNode)); s-data=e; s-next=p; s-prior=p-prior; /*修改新结点的前驱的next 域指向s*/ s-prior-next=s; p-prior=s; return ok; } 人有了知识，就会具备各种分析能力， 明辨是非的能力。 所以我们要勤恳读书，广泛阅读， 古人说“书中自有黄金屋。 ”通过阅读科技书籍，我们能丰富知识， 培养逻辑思维能力； 通过阅读文学作品，我们能提高文学鉴赏水平， 培养文学情趣； 通过阅读报刊，我们能增长见识，扩大自己的知识面。 有许多书籍还能培养我们的道德情操， 给我们巨大的精神力量， 鼓舞我们前进。 * 本课内容 一、链表的其它几种形式： 静态链表（理解） 循环链表（掌握） 双向链表（掌握插入/ 删除算法） 二、链表的应用（了解） 一元高次多项式的存储 集合类型的实现 有些高级程序设计语言中没有指针类型，但为了实现链表结构，应用其优点，可以通过定义一个结构体数组实现类似于“链表” 的存储结构。 该数组中的每个元素类似与线性表的“结点”，只是将结点中的指针改为下标，用于指出后继在数组中的序号（相对位置），从而形成静态链表结构。 由于它是利用数组定义的，数组的长度在编译时就确定，因此在整个运算过程中链表存储空间的大小不会发生变化，故称这种结构为静态链表。 2.3.1 静态链表 静态链表的类型定义 #define MaxSize 1000 /*链表的最大长度*/ /*定义存储数据元素的“结点”类型 ——Snode*/ typedef struct { ElemType data; /*存储数据元素的值*/ int cur ; /*存储元素直接后继的下标*/ } Snode; /*定义静态链表类型SlinkList—结构体数组类型*/ typedef Snode SlinkList[MaxSize]; 理解： 静态链表中的用于存储每个数据元素的结点也有数据域data和指向下个元素存储位置的域cur，不过这里的cur是个下标,是相对数组第一个元素的偏移,属于相