数据结构线性表.ppt

《数据结构线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构线性表.ppt（57页珍藏版）》请在优知文库上搜索。

1、 CH2 线性表线性表n2.1 线性表的逻辑结构线性表的逻辑结构 n2.2 线性表的顺序存储及运算实现线性表的顺序存储及运算实现n2.3 线性表的链式存储和运算实现线性表的链式存储和运算实现n2.4 线性表的两种存储结构的比较线性表的两种存储结构的比较n2.5 线性表的应用举例线性表的应用举例n教学目标教学目标n线性表的逻辑结构特征；线性表上定义的基本运算，并线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。利用基本运算构造出较复杂的运算。n掌握顺序表的含义及特点，顺序表上的插入、删除操作掌握顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简

2、单应用问题。及其平均时间性能分析，解决简单应用问题。n掌握链表如何表示线性表中元素之间的逻辑关系；单链掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。定义和相关算法。

3、利用链表设计算法解决简单应用问题。n领会顺序表和链表的比较，以及如何选择其一作为其存领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。储结构才能取得较优的时空性能。n教学重点与难点教学重点与难点n本章的重点是掌握顺序表和单链表上实现的各种本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；基本算法及相关的时间性能分析；n难点是使用本章所学的基本知识设计有效算法解难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。决与线性表相关的应用问题。n教学方法教学方法n课堂讲授课堂讲授n提问互动提问互动n实验实验n定义定义:n线性表（线性表（

4、linear list） （ a1，a2， ， an ） 其中其中:n ：数据元素的个数或：数据元素的个数或线性表的长度线性表的长度；ai ： 是一个抽象的符号，它的数据类型设定为是一个抽象的符号，它的数据类型设定为ElemType，表示某一种具体的已知数据类型（表示某一种具体的已知数据类型（1in） 。2.1 线性表的类型定义线性表的类型定义n非空线性表的特征（非空线性表的特征（P18）n 有且仅有一个开始结点有且仅有一个开始结点(表头结点表头结点 head)a1，它没有直，它没有直接前驱，只有一个直接后继接前驱，只有一个直接后继;n 有且仅有一个终端结点有且仅有一个终端结点(表尾结点表尾结

5、点tail)an，它没有直接，它没有直接后继，只有一个直接前驱后继，只有一个直接前驱;n 其它结点都有一个直接前驱和直接后继；其它结点都有一个直接前驱和直接后继；n 元素之间为元素之间为一对一一对一的线性关系。的线性关系。线性表的抽象数据类型定义（线性表的抽象数据类型定义（P18 ） ADT List 数据对象：数据对象：D=ai|aiElemSet;1in,n0; 数据关系：数据关系：R=| ai, ai+1D,i=1,2,n-1 基本操作：基本操作：InitList(&L) ListLength(L) GetElem(L,i,&e) PriorElem(L,cur_e,&pre_e) Ne

6、xtElem(L,cur_e,&next_e)LocateElem(L,e,compare() ListInsert(&L,i,e) ListDelete(&L,i,&e) ADT List算法算法2.1（线性表的首尾合并）（线性表的首尾合并）void union(List &La,List Lb) La_len=ListLength(La);Lb_len=ListLength(Lb) ; for(i=1;i=Lb_len;i+) GetElem(Lb,i,e); if (!LocateElem(La,e,equal) ListInsert(La,+La_len,e); /union 算法分析

7、：算法分析： 设设LocateElem的执行时间与表长成正比，的执行时间与表长成正比， 即：算法的时间复杂度为：即：算法的时间复杂度为：O(ListLength(La) * ListLength(Lb)算法算法2.2（有序线性表的合并）（有序线性表的合并）void MergeList(List La,List Lb,List &Lc) InitList(Lc); i=j=1;k=0; La_Len=ListLength(La);Lb_Len=ListLength(Lb); while (i=La_Len)&(j=Lb_Len) GetElem(La,i,ai); GetElem(Lb,j,bj

8、); if (ai=bj) ListInsert(Lc,+k,ai); +i; else ListInsert(Lc,+k,bj);+j; while (i=La_len) GetElem(La,i+;ai); ListInsert(Lc,+k,ai); while (j=Lb_len) GetElem(Lb,j+;bj); ListInsert(Lc,+k,bj);/MergeList2.2 线性表的顺序存储结构线性表的顺序存储结构n一、特点一、特点1.用一组地址用一组地址连续连续的存储单元依次存放线性的存储单元依次存放线性表中的元素；表中的元素；2.以元素在机内的以元素在机内的“物理位置相

9、邻物理位置相邻”来表示来表示数据之间的逻辑关系数据之间的逻辑关系: LOC(ai+1) LOC(ai)L3.是一种是一种随机存取随机存取的存储结构的存储结构; LOC(ai)LOC(a1)(i1)*L4.插入删除时需移动大量元素插入删除时需移动大量元素;a1a2aiai+1anLOC( )LOC( )LOC()2.2 线性表的顺序存储结构线性表的顺序存储结构n二、描述方式二、描述方式#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemType *elem; int length; int listsize; S

10、qList2.2 线性表的顺序存储结构线性表的顺序存储结构n三、基本操作的算法描述三、基本操作的算法描述 n初始化顺序表初始化顺序表 （算法（算法 2.3）n插入元素插入元素 （算法（算法 2.4）n 删除元素删除元素 （算法（算法 2.5）n 元素的查找元素的查找（算法（算法 2.6）n 顺序表的合并顺序表的合并 （算法（算法 2.7）n算法算法2.3 （初始化顺序表）（初始化顺序表） Status InitList_Sq(SqList &L)L.elem=(ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType)if (!L.elem) exit

11、（OVERFLOW）;L.length=0;L.listsize=LIST_INIT_SIZE;return OK;/InitList_Sq算法算法2.4 ：顺序表中插入一个元素：顺序表中插入一个元素Status ListInsert_Sq(SqList &L,int i,ElemType e) if (iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(ElemType *) realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) e

12、xit (OVERFLOW); L.elem=newbase;L.listsize+=LISTINCREMET; q=&(L.elemi-1); for (p=&(L.elemL.length-1);p=q;- -p) *(p+1)=*p;*q=e; +L.length; return OK;/ListInsert_Sq for (j=L.length-1;j=i-1;j-) L.elemj+1=L.elemja1a2aiai+1anL.elem01i-1i下标下标a1a2aian-1ane顺序表的插入.swf插入算法的时间复杂度分析插入算法的时间复杂度分析n插入算法花费的时间，主要在于循环中

13、元素的向后移动上面，插入算法花费的时间，主要在于循环中元素的向后移动上面，而元素的移动次数与插入的位置而元素的移动次数与插入的位置i有关：有关： (设设L.length=n)n当当i=1时，全部元素都得移动，需时，全部元素都得移动，需n次移动，次移动，n当当i=n+1时，不需移动元素，时，不需移动元素，n一般地：在一般地：在i位置插入时移动次数位置插入时移动次数ci为为n-i+1，n假设在每个位置插入的概率为假设在每个位置插入的概率为pi （不妨设为等概率）（不妨设为等概率） ，则，则平均移动元素的次数为：平均移动元素的次数为： 故时间复杂度为故时间复杂度为O(n)。 11111(1)12nn

14、iiiinpcnin 算法算法2.5 顺序表中删除元素顺序表中删除元素Status ListDelete_Sq(Sqlist &L,int i,ElemType & e) if (iL.length) return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; for (+p;p=q;+p) *(p-1)=*p; - -L.length; return OK;/ListDelete_Sq顺序表的删除运算顺序表的删除运算.swf e=L.elemi-1;For (j=i;j=L.length-1;j+) L.elemj-1=L.elemj；删

15、除算法的时间复杂度分析删除算法的时间复杂度分析n删除算法花费的时间，主要在于循环中元素的前移上，而元删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置素的移动次数与删除的位置i有关：有关： (设设L.length=n)n当当i=1时，其后的全部元素都得移动，需时，其后的全部元素都得移动，需n-1次移动，次移动，n当当i=n时，不需移动元素，时，不需移动元素，n一般地：在一般地：在i位置删除元素时的移动次数位置删除元素时的移动次数ci为为n-in假设在每个位置删除的概率为假设在每个位置删除的概率为pi （不妨设为等概率）（不妨设为等概率） ，则，则平均移动元素的次数为：

16、平均移动元素的次数为：故时间复杂度为故时间复杂度为O(n)。 21)(111ninncpniniii算法算法2.6 顺序表中元素的查找顺序表中元素的查找int LocateElem_Sq(Sqlist L, ElemType e, status (*compare)(ElemType ,ElemType) i=1; p=L.elem; while (iL.length & !(*compare)(*p+,e) +i; if (i=L.length) return i; else return 0; /ListDelete_Sq注注 ： 设设L.length=n，则则T(n)=O(n)算法算法2.6-1 顺序表中元素的查找顺序表中元素的查找int LocateElem_Sq(Sqlist L, ElemType e) i=0; while (iL.length & L.elemi!=e) +i; if (iL.length) return i+1; else return 0; /LocateElem_Sq注注 ： 设设L.length=n，则则T(n)=O(n) 算法算法2.7 顺序表