第2章4-数据结构-教程.ppt

六、双向链表;;2、双向链表的操作实现;;例:已知P结点是双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。;(1)P-next=P-next-next; (10) P-prior-next=P; (2)P-prior=P-prior-prior; (11) P-next-prior =P; (3) P-next=S; (12)P-next-prior=S; (4) P-prior=S; (13) P-prior-next=S; (5)S-next=P; (14) P-next-prior=P-prior (6)S-prior=P; (15)Q=P-next; (7) S-next= P-next; (16)Q= P-prior; (8) S-prior= P-prior; (17)free(P); (9) P-prior-next=p-next; (18)free(Q); ; 静态单链表的类型定义如下： #define MAXSIZE 1000 //预分配最大的元素个数（连续空间 typedef struct { DataType data ; //数据域 int next ; //指示域 }component , SLinkList[MAXSIZE] ; //这是一维结构型数组;例 2：一线性表 S = ( ZHAO, QIAN, SUN, LI, ZHOU, WU )，用静态链表如何表示？;说明3：静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。;例3：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。;解： void SortA(SeqList *L) { int i=0, zerosum =0;if(L-size= =0) return(0); //空表则结束else { for( i=0; iL.-size; i++) {if (L-list[i]0) L-list[i- zerosum]= L-list[i]; else zerosum++; } }for( i= L-size-zerosum; i=L.-size; i++)L-list[i]=0; //表的后部补0};若考虑表完全非空的情况，则程序要变长很多。 解： void SortA(SeqList *L) { int i=0,zerosum =0; if(L-size= =0) return(0); //空表则不执行 for( i; i=L-size; i++) {if (L-list[i]0zerosum!=0)L-list[i- zerosum]= L-list[i]; else zerosum++ }; //适当移动非零元素,是零则增加计数 for( i= L-size-zerosum+1; i=L-size; i++) L-list[i]=0; //表的后部补0 return( )??? };本章小结;循环链表的特点：从任一结点出发均可找到表中其他结点;讨论1： 顺序存储和链式存储的区别和优缺点？ 　　顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。 　　链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。;讨论2：什么是指针？指针的作用？