数据结构课件1第2章线性表幻灯片.ppt

国际教育学院 双向链表的插入 1. s-prior=p-prior; 2. p-prior-next=s; 3. s-next=p; 国际教育学院 双向链表的插入 4. p-prior=s; a b x ... ... 1 2 3 4 p s 1. s-prior=p-prior; 2. p-prior-next=s; 3. s-next=p; 国际教育学院 Status ListInsert_DuL(DuLinkList L,int i,ElemType e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR; s-data=e; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return OK; } 双向链表的插入（算法2.18） 国际教育学院 双向链表的删除 国际教育学院 1. p-prior-next=p-next; 双向链表的删除 国际教育学院 双向链表的删除 1. p-prior-next=p-next; 2. p-next-prior=p-prior; 国际教育学院 Status ListDelete_DuL(DuLinkList L,ini i,ElemType e){ if(!(p=GetElemP_DuL(L,i))) return ERROR; e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return OK; } 双向链表的删除（算法2.19） 国际教育学院 typedef struct{ //链表类型 Link head,tail; //分别指向头结点和最后一个结点 int len; //指示线性链表中数据元素的个数 }LinkList; typedef struct LNode{//结点类型 ElemType data; struct LNode *next; }*Link,*Position; 链表类型的重定义（了解） 国际教育学院 1、了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。 2、熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。 小结 国际教育学院 3、掌握顺序表的查找、插入和删除算法 4、掌握链表的查找、插入和删除算法 5、能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合 小结 国际教育学院 1.将两个非递减的有序链表合并为一个非递减的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 作业 国际教育学院 3.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 4. 设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。　 作业 国际教育学院 作业提示 第1题参考讲稿和教材中的算法2.12 要单独考虑pa-data = =pb-data La(Lc) 1 2 4 6 7 8 8 10 11 国际教育学院 (1)Lc指向La (2) 依次从 La 或 Lb 中“摘取”元素值较小的结点插入到 Lc 表的表头结点之后，直至其中一个表变空为止 (3) 继续将 La 或 Lb 其中一个表的剩余结点插入在 Lc 表的表头结点之后 (4) 释放 Lb 表的表头结点 作业提示 第2题参考讲稿和教材中的算法2.12，步骤如下： 国际教育学院 12 23 34 45 56 11 32 43 48 54 La Lb Lc ∧ pa pb q pb ∧ q pa q pa q 第2题实现过程动态演示 国际教育学院 作业提示 第3题:确定单链表中值最大的结点 思想类似于求n个数中的最大数，可假设第一个结点最大，用指针pmax指向，然后用pmax依次和后面的结点进行比较，发现大者则用pmax指向该结点，这样将链表从头到尾遍历一遍时，pmax所指向的结点就是最大者。 其中的比较语句形式如下： if(p-