数据结构第二章后半.ppt

//删除cp所指向的结点 if (ap == NULL){ //删除表头 HL = HL -next; }else{ //删除ap和cp之间的结点 ap-next = cp -next; } delete cp; return true; } 在链表中删除结点的实现: 有序对x, y 和 y, z 改变为 x, z ap-next=cp-next; x y z cp ap cp-next 11、对单链表进行数据排序 void SortList(LNode* HL) {//插入排序 LNode* SL; InitList(SL); LNode* r=HL; while(r!=NULL) { LNode* t=r-next; LNode* cp=SL; LNode* ap=NULL; while(cp!=NULL) { if(r-datacp-data) break; else { ap=cp; cp=cp-next; } } if(ap= = NULL) { r-next=SL; SL=r; } else { r-next=cp; ap-next=r; } r=t; } HL=SL; } (1)-(11)各个算法的时间复杂度如下： (1)(4)：O(1) (2)(3)(5)(6)(7)(8)(9)(10)：O(n) (11)：O(n2) 由于单链表的插入和删除操作只进行元素的比较，不进行元素的移动，而顺序表的插入和删除操作既需要元素的比较，又需要元素的移动，所以当处理的数据量较大，同时每个数据占用的字节数较多时，在相同数量级的情况下，顺序表操作往往比单链表操作要花费更多的时间 这11个算法均已在Visual C++6.0版本上调试通过，请同学们课后自己动手上机实现 思考: 在由元素结点构成的单链表上的实现 请思考在由元素结点构成的单链表上这11种算法的实现,课堂上不做具体要求 补充简单应用举例 编写一个程序实现如下功能: 让计算机产生20个0-9之间的随机整数并依次保存到单链表中; 输出遍历单链表; 从单链表中删除与给定值相等的所有结点; 输出遍历单链表; 输出单链表的长度. 补充简单应用举例 #includeiostream.h #includestdlib.h typedef int ElemType; struct LNode { ElemType data; LNode* next; }; #include”link.h” void main() { LNode *head; InitList (head); int i,j; for (i=0; i20; i++) { j= rand() %10; InsertList(head, j,-1 ); } TraverseList (head); cout“输入0－9之间的一个整数”; cinj; while(DeleteList(head,j,0)) {}; TraveseList (head); coutLenthList(head)endl; } 保存线性表操作在动态独立结点构成的单链表中的所有操作实现 本章小结 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。 3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。 (!!)2.1 请认真独立完成该题 (!) 2.2 感兴趣同学思考解答 (!) 2.3 第1,2小题必须所有同学全部掌握(!!)。其余的思考其算法描述，有能力者上机实现(!)。 (!) 2.4 第1,2小题必须所有同学全部掌握(!!)。其余的思考其算法描述，有能力者上机实现(!)。 本章课后(1) 第二章 线性表 书面回答, 要求整洁清楚，