第2章 线性表n.ppt

学习目标 掌握线性表的顺序存储结构及具体操作实现； 掌握线性表的单、双向链接存储结构及具体操作实现； 掌握算法时间复杂度分析。 2.1 线性表的基本概念 １、线性表 　　　它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据元素操作的，由n（n≥0)个相同类型数据元素a0, a1, … , an-1组成的线性结构。 例：试用C或类C语言编写一高效算法，将一顺序存储的线性表（设元素均为整型量）中所有零元素向表尾集中，其他元素则顺序向表头方向集中。 6、其它一些操作实现 1、 清空操作 void ClearList(SqList L) 2. 判空操作 bool ListEmpty(SqList L) 2. 查找指定序号的元素 ElemType GetElem(SqList L, int pos) 7、 顺序表操作的效率分析 算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置. 教材P25有对执行效率的推导：（与课本略有区别） 四、用单链表实现线性表上其它的操作 1. 初始化单链表 void InitList(LNode* L) { L=NULL; }//O(1) 2. 检查单链表是否为空 bool ListEmpty(LNode* L) { return ( L==NULL); } // O(1) 3. 删除单链表中结点，使之成为空表 void ClearList(LNode* L) { LNode *cp, *np; cp= L; while(cp!=NULL) { np=cp-next; cp-next=np-next; delete cp;} L=NULL; } //O(n) 4. 得到单链表的长度 int ListSize(LNode* L) //带头结点? { P= L-next; int i=0; while(P!=NULL) { i++; P = P -next; } return i; } //O(n) 5. 得到单链表中第pos个结点中的元素 ElemType GetElem(LNode* L, int pos) { if(pos1) { cerrpos is out range!endl; exit(1); } i=0; P= L-next; while(P!=NULL){ i++; if(i==pos) break; P = P -next; } if(P!=NULL) return P -data; else{ cerrpos is out range!endl; exit(1);} } //O(n) 6. 遍历一个单链表 void TraverseList(LNode* L) { P= L-next; while(P!=NULL) { cout P-data ; P = P -next; } coutendl; } O(n) 7. 查找具有给定值的第一个元素 bool Find(LNode* L, ElemType item) { LNode* p= L;int i=1; while(p!=NULL) if (p-data==item) { return i; } else {p=p-next;i++;} return false; } O(n) 五、单链表的操作效率分析 （1） 查找 ：因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。 七、 静态链表 静态链表：在数组中增加一个（或两个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针又称仿真指针。 本章小结 作业：试用C/C++语言编写一个算法，将一循环单链表就地逆置。 操作前： （a1, a2, … ai-1，ai