数据结构 第2章课件.pptVIP

《数据结构》 任课教师：王继州 （江南大学 计算机硕士） 联系电话：138 3811 0107 电子邮箱：yylb99@126.com 《上课期间请关闭或静音手机》 Status ListDelete_DuL(DuLinkList L，int i，ElemType e) { if（!（p=GetElemP_DuL（L，i））） e=p-data; p-prior-next=p-next; p-next-prior=p-prior; free(p); return OK; } 算法：2.19 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=prior-; p-prior-next=s; s-next=p; p-prior=s; return OK; } 算法：2.18 双向链表的删除操作 图2.15 双向链表的删除操作 双向链表的前插操作 图2.16 双向链表插入操作 P26：顺序表的合并： 有两个顺序表LA和LB，其元素均为非递减有序排列， 编写一个算法，将它们合并成一个顺序表LC， 要求LC也是非递减有序排列。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 则LC=(1, 2, 2, 3, 3, 3, 4)。 算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、 j分别指向表LA和LB中的元素， 若LA.elem［i］LB.elem［j］， 则当前先将LB.elem［j］插入到表LC中; 若LA.elem［i］≤LB.elem［j］，则当前先将LA.elem［i］插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中。 Void MergeList_Sq(SqList La, SqList Lb, SqList Lc ){ Pa=La.elem; pb=Lb.elem; Lc.listsize=Lc.length=La.length+Lb.length; Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe)); If (!Lc.elem) exit (OVERFLOW); pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; While (pa=pa_last pb=pb_last){ If (*pa=*pb) *pc++=*pa++; Else *pc++=*pb++; } while(pa=pa_last) *pc++=*pa++; while(pb=pb_last) *pc++=*pb++; } 算法2.7：时间复杂度：O(Listlength(LA)+Listlength(LB)) 由上面的讨论可知， 线性表顺序表示的优点是：  (1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；  (2）可方便地随机存取表中的任一元素。  其缺点是： 插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，其效率较低。 由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。 2.3 线性表的链式表示和实现 2.3.1 单链表（线性链表） 线性表的链式存储：用一组任意的存储单元存放线性表的 数据元素（这组存储单元可以连续，也可不连续）。为表示数 据元素之间的逻辑关系，还需有存储一个指示后继的信息—— 指针。由数据域和指针域构成数据元素的存储映象，称为结点 （Nod