数据结构课件第2章线性表.ppt

《数据结构课件第2章线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第2章线性表.ppt（114页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章线性表线性表题目一：狐狸逮兔子实验题目一：狐狸逮兔子实验【问题描述】【问题描述】围绕着山顶有围绕着山顶有1010个圆形排列的洞，狐狸要吃兔个圆形排列的洞，狐狸要吃兔子，兔子说：子，兔子说：“可以，但必须找到我，我就藏可以，但必须找到我，我就藏身于这十个洞中，你先到号洞找，第二次隔身于这十个洞中，你先到号洞找，第二次隔个洞（即个洞（即3 3号洞）找，第三次隔个洞（即号洞）找，第三次隔个洞（即6 6号洞）找，以后如此类推，次数不限。号洞）找，以后如此类推，次数不限。”但狐但狐狸从早到晚进进出出了狸从早到晚进进出出了10001000次，仍没有找到兔次，仍没有找到兔子。问兔子究竟藏在哪个洞

2、里？子。问兔子究竟藏在哪个洞里？学习目标学习目标l掌掌握握线线性性表表的的顺顺序序存存储储结结构构及及具体操作实现；具体操作实现；l掌掌握握线线性性表表的的单单、双双向向链链接接存存储结构及具体操作实现；储结构及具体操作实现；l掌握算法时间复杂度分析。掌握算法时间复杂度分析。线性结构线性结构的定义：的定义：若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前前趋趋和和一一个个直直接接后后继继。可可表表示示为为：（a1,a2 ,an）特点：特点：1集合中必存在唯一的一个集合中

3、必存在唯一的一个“第一元素第一元素”；2集合中必存在唯一的一个集合中必存在唯一的一个“最后元素最后元素”；3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继；4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。简言之，线性结构反映结点间的逻辑关简言之，线性结构反映结点间的逻辑关系是系是 的。的。线性结构包括：线性结构包括：线性表、堆栈、队列、线性表、堆栈、队列、字符串、数组字符串、数组等，其中最典型、最常等，其中最典型、最常用的是用的是-一对一一对一(1:1)线性表线性表2.1 线性表的类型定义线性表的类型定义2.3 线性表类型的实现线性表类型的实现 链式映象链式映

4、象2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象2.1线性表的类型定义线性表的类型定义2.1 线性表的基本概念线性表的基本概念、线性表线性表它是一种最简单的线性结构。是一它是一种最简单的线性结构。是一种可以在任意位置进行插入和删除数据种可以在任意位置进行插入和删除数据元素操作的，由元素操作的，由n（n0)个个相同类型相同类型数据数据元素元素a0,a1,an-1组成的线性结构。组成的线性结构。（a0,a1,ai-1，ai,ai1，,an-1）线性表的逻辑结构：线性表的逻辑结构：n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标

5、，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总为元素总个数，即表个数，即表长。长。n0n0空表空表线性终点线性终点 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012003010622陈建武陈建武男男 192003级信息级信息0301班班012003010704赵玉凤赵玉凤女女 182003级信息级信息0302班班012003010813王王 泽泽男男 192003级信息级信息0303班班012003010906薛薛 荃荃男男 192003级信息级信息0304班班012003011018王 春男 19 192003级信息级信息0305班班：例

6、例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。分析分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。抽象数据类型线性表线性表的定义如下：ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R

7、1|ai-1,aiD,i=2,.,n 基本操作：基本操作：结构初始化操作结构初始化操作结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 ADT List InitList(&L)操作结果：操作结果：构造一个空的线性表L。初始化操作初始化操作 结构销毁操作结构销毁操作DestroyList(&L)初始条件：操作结果：线性表 L 已存在。销毁线性表 L。ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)GetElem(L,i,&e)LocateElem(L,e,compare()

8、ListTraverse(L,visit()引用型操作引用型操作:ListEmpty(L)初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。（线性表判空）ListLength(L)初始条件：操作结果：线性表L已存在。返回L中元素个数。（求线性表的长度）PriorElem(L,cur_e,&pre_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但不是第一个，则用pre_e 返回它的前驱，否则操作失败，pre_e无定义。（求数据元素的前驱）NextElem(L,cur_e,&next_e)初始条件：操作结果：线性表L已存在。若cur_e是L的元素，但

9、不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。（求数据元素的后继）GetElem(L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)。用 e 返回L中第 i 个元素的值。（求线性表中某个数据元素）LocateElem(L,e,compare()初始条件：操作结果：线性表L已存在，e为给定值，compare()是元素判定函数。返回L中第中第1个个与e满足满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。（定位函数）ListTraverse(L,visit()初始条件：操作结果：线性表L已存在，Visit()

10、为某个访问函数。依次依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。（遍历线性表）加工型操作加工型操作 ClearList(&L)PutElem(&L,i,&e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。（线性表置空）PutElem(&L,i,&e)初始条件：操作结果：线性表L已存在，且 1iLengthList(L)。L中第i个元素赋值同e的值。（改变数据元素的值）ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在，且 1iLengt

11、hList(L)+1。在L的第i个元素之前插入插入新的元素e，L的长度增1。（插入数据元素）ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在且非空，1iLengthList(L)。删除L的第i个元素，并用e返回其值，L的长度减1。（删除数据元素）利用上述定义的线性表线性表 可以实现其它更复杂的操作例例 2-2例例 2-3例例 2-1 假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合现要求一个新的集合AAB。例例 2-1 要求对线性表作如下操作：扩大线性表 LA，将存在于线性表存

12、在于线性表LB 中中而不存在于线性表不存在于线性表 LA 中中的数据元素插入到线性表插入到线性表 LA 中中去。上述问题可演绎为：1从线性表LB中依次察看每个数据元素;2依值在线性表LA中进行查访;3若不存在，则插入之。GetElem(LB,i)e LocateElem(LA,e,equal()ListInsert(LA,n+1,e)操作步骤：操作步骤：GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之

13、相同的数据元素，则插入之void union(List&La,List Lb)La_len=ListLength(La);/求线性表的长度求线性表的长度 Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)/union 已知已知一个非纯集合非纯集合 B，试构造构造一个纯集合纯集合 A，使使 A中只包含中只包含 B 中所有值各中所有值各不相不相 同的数据元素同的数据元素。仍选用线性表线性表表示集合。例例 2-2集合集合 B集合集合 A从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件以上同样物件不能有两件以上因此，算法的策略应该和例算法的策略应该和例2

14、-1相同相同void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);/union GetElem(Lb,i,e);/取取Lb中第中第 i 个数据元素赋给个数据元素赋给 e if(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之for(i=1;i=Lb_len;i+)InitList(La);/构造(空的)线性表LA若线性表中的数据元素相互之间可以比比较较，并且数据元素在线性表中依值

15、非递依值非递减或非递增有序减或非递增有序排列，即 aiai-1 或 aiai-1(i=2,3,n)，则称该线性表为有序表有序表(Ordered List)(Ordered List)。试改变结构，以有序表有序表表示集合。例如例如：如果集合 B，（2，3，3，5，6，6，6，8，12）对集合 B 而言，值相同的数据元素必定相邻；值相同的数据元素必定相邻；如果构造一个纯集合 A，对集合 A 而言，数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。因此，数据结构改变了，数据结构改变了，解决问题的策略也相应要改变。解决问题的策略也相应要改变。void purge(List&La,List

16、 Lb)InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);/求线性表的长度求线性表的长度 for(i=1;i=Lb_len;i+)/purge GetElem(Lb,i,e);/取取Lb中第中第i个数据元素赋给个数据元素赋给 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之线性表的存储结构是指为它开辟的计算机线性表的存储结构是指为它开辟的计算机存储空间、存储空间的联系以及所采用的存

17、储空间、存储空间的联系以及所采用的程序实现方法。线性表的存储结构主要有程序实现方法。线性表的存储结构主要有如下两类：如下两类：(1)顺序存储结构顺序存储结构(2)(2)链式存储结构链式存储结构2.22.2 线性表类型的实现线性表类型的实现 顺序映像顺序映像 1、用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 （逻辑关系相邻（逻辑关系相邻,物理位置相邻。）物理位置相邻。）a1 a2 ai-1 ai an线性表的线性表的起始地址起始地址称作线性表的基地址基地址(1)逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；(2)若已知表中首元素在存储器中的位

18、置，则其他若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出元素存放位置亦可求出。设首元素设首元素a0的存放地址为的存放地址为LOC(a0)（称称为首地址为首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+L LOC(LOC(a ai i )=LOC()=LOC(a a0 0)+L*i)+L*i 对上述公式的解释如图所示对上述公式的解释如图所示2、线性表顺序存储特点：a a0 0a a1 1a ai ia ai+1i+1a an-1n-

19、1 地址地址 内容内容 元素在表中的位序元素在表中的位序0 0i i1 1n-1n-1空闲区空闲区i+1i+1Lb=LOC(a0)b+L Lb+i+iL Lb+(n-1)+(n-1)L Lb+(MaxSize-1)+(MaxSize-1)L LLOC(aLOC(ai i )=LOC(a)=LOC(a0 0)+L*i)+L*i3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图4、顺序映像的、顺序映像的 C 语言描述语言描述typedef struct SqList;/俗称 顺序表顺序表#define LIST_INIT_SIZE 80 /线性表存储空间的初始分配量#define LIST

20、INCREMENT 10 /线性表存储空间的分配增量ElemType*elem;/存储空间基址int length;/当前长度int listsize;/当前分配的存储容量 /(以sizeof(ElemType)为单位)5、线性表的基本操作在顺序表中的实现、线性表的基本操作在顺序表中的实现InitList(&L)/结构初始化结构初始化LocateElem(L,e,compare()/查找查找ListInsert(&L,i,e)/插入元素插入元素ListDelete(&L,i)/删除元素删除元素Status InitList_Sq(SqList&L)/构造一个空的线性表 /InitList_Sq

21、算法时间复杂度时间复杂度：O(1)L.elem=(ElemType*)malloc(LIST_ INIT_SIZE sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturn OK;定位：判断某个元素是否存在，存在给出其定位：判断某个元素是否存在，存在给出其位置，否则为位置，否则为0 023 75 41 38 54 62 17L.elemL.lengthL.listsizee=38pppppi 1 2 3 4 1 850p可见，基本操作是：将顺序表中的元素逐个和给定值 e 相比较。i

22、nt LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂度为：为：i=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(

23、*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;(*compare)(*p+,e)int LocateElem_Sq(SqList L,ElemType e,)p=L.elem;for(i=1;i=L.length;i+)if(*p+=e)return i;else return 0;/LocateElem_Sq时间复杂性：时间复杂性：(找到找到)最好最好 1 1次次 O(1)O(1)最坏最坏 n n次次 O(n)O(n)平均平均 n/2 n/2次次 O(n)O(n)(找不到找不到)最好最好 n+1 n+1次次 O(n)O(n)最

24、坏最坏 n+1 n+1次次 O(n)O(n)平均平均 n+1 n+1次次 O(n)O(n)线性表操作 ListInsert(&L,i,e)的实现：首先分析首先分析:插入元素时，线性表的逻辑结构逻辑结构发生什么变化发生什么变化？(a1,ai-1,ai,an)改变为 (a1,ai-1,e,ai,an)a1 a2 ai-1 ai ana1 a2 ai-1 ai ean,表的长度增加 Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序表L的第 i 个元素之前插入新的元素e,/i 的合法范围为 1iL.length+1/ListInsert_Sq 算法

25、时间复杂度算法时间复杂度为为:O(ListLength(L)q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移元素右移*q=e;/插入e+L.length;/表长增1return OK;元素右移元素右移21 18 30 75 42 56 8721 18 30 75例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elemi-1);/q 指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p

26、;*q=66;/插入插入e ep线性表操作 ListDelete(&L,i,&e)的实现：首先分析：删除元素时，线性表的逻辑结构发生什么变化？(a1,ai-1,ai,ai+1,an)改变为 (a1,ai-1,ai+1,an)ai+1 an,表的长度减少a1 a2 ai-1 ai ai+1 ana1 a2 ai-1 Status ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1return OK;算

27、法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移21 18 30 75 42 56 8721 18 30 75L.length-10pppq8756p=&(L.elemi-1);q=L.elem+L.length-1;for(+p;p if(L-lenghthlenghth=0)return

28、(0);/=0)return(0);/空表则结束空表则结束 else else for(i=0;ilenghth-1;i+)for(i=0;ilenghth-1;i+)if(L-elemi0)if(L-elemi0)L-elemi-zerosum=L-elemi;L-elemi-zerosum=L-elemi;else zerosum+;else zerosum+;for(i=L-lenghth-zerosum;ilenghth;for(i=L-lenghth-zerosum;ilenghth;i+)i+)L-elemi=0;/L-elemi=0;/表的后部补表的后部补0 06 6、其它一些操

29、作实现、其它一些操作实现1、清空操作清空操作 void ClearList(SqList&L)L.length=0;删除删除L中所有元素，使之成为一个中所有元素，使之成为一个空表空表2.判空操作判空操作 bool ListEmpty(SqList&L)return(L.length=0);/if （L.length=0）/return true;/else return false;若若L为空表，返回真，否则返回假为空表，返回真，否则返回假3、有关查表的操作、有关查表的操作 1.遍历一个线性表遍历一个线性表 void TraverseList(SqList&L)for(int i=0;iL.l

30、ength-1;i+)coutL.elemi;coutendl;依次访问依次访问L中每一个元素一次中每一个元素一次 2.查找指定序号的元素查找指定序号的元素 ElemType GetElem(SqList&L,int pos)if(posL.length)cerrpos is out range!next;j=1;/p p指向第一个结点，指向第一个结点，j j为计数器为计数器while(p&jnext;+j;/顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素个元素 /或或 p p 为空为空if(!p|ji)return ERROR;/第第 i i 个元素不存在个元

31、素不存在e=p-data;/取得第取得第 i i 个元素个元素return OK;ai-1 线性表的操作 ListInsert(&L,i,e)在单链表中的实现：有序对有序对 改变为改变为 和和 eaiai-1 Status ListInsert_L(LinkList L,int i,ElemType e)/L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 /在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e /LinstInsert_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p&j next;+

32、j;/寻找第寻找第 i-1 个结点个结点if(!p|j i-1)return ERROR;/i 大于表长或者小于大于表长或者小于1 s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;p-next=s;/插入return OK;eai-1aiai-1sp线性表的操作ListDelete(&L,i,&e)在链表中的实现:有序对有序对 和和 改变为改变为 ai-1aiai+1ai-1 在单链表中删除第删除第 i i 个结点个结点的基本基本操作操作为:找到线性表中第找到线性表中第i-1i-1个结点，修个结点，修改其指向后继的指针

33、。改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;free(q);pq Status ListDelete_L(LinkList L,int i,ElemType&e)/删除以 L 为头指针(带头结点)的单链表中第 i 个结点 /ListDelete_L算法的算法的时间复杂度时间复杂度为:O(ListLength(L)p=L;j=0;while(p-next&j next;+j;/寻找第 i 个结点，并令 p 指向其前趋if (!(p-next)|j i-1)return ERROR;/删除位置不合理q=p-next;p-next

34、=q-next;/删除并释放结点e=q-data;free(q);return OK;操作 ClearList(&L)在链表中的实现:void ClearList(&L)/将单链表重新置为一个空表P=L;while(P)p=L-next;L-next=p-next;/ClearListfree(p);算法时间复杂度：O(ListLength(L)如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要预分配空链表是一个动态的结构，它不需要预分配空间，因此间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个逐个插入插入”的过程。的过程。实现思路：实现思路：先开辟头

35、指针，然后陆续为每个结先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址点开辟存储空间并及时赋值，后继结点的地址要要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”,”,后种后种“萝萝卜卜”！新手特别容易忘记！新手特别容易忘记！L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表p=L;for(i=1;inext=(LinkList)malloc(sizeof(LNode);p=p-next；/让让指指针针变变量量P指指向向后后一个结点一个结点cinp-data;/输入数据输入数据p-next=NUL

36、L;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void CreateList_L(LinkList&L,int n)/顺序输入 n 个数据元素，建立带头结点的单链表要一个个慢慢链入要一个个慢慢链入例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值，建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an，建立结点并插入；建立结点并插入；三、输入数据元素三、输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a a1

37、 1为止。为止。void CreateList_L(LinkList&L,int n)/逆序输入 n 个数据元素，建立带头结点的单链表/CreateList_L算法的算法的时间复杂度时间复杂度为:O(Listlength(L)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i 0;-i)p=(LinkList)malloc(sizeof(LNode);cinp-data;/输入元素值 p-next=L-next;L-next=p;/插入作业：作业：用单链表结构来存放用单链表结构来存放2626个英文字母组成个英

38、文字母组成的线性表（的线性表（a a，b b，c c，z z）,请写出请写出完整的完整的C/C+C/C+语言程序。语言程序。四、用单链表实现线性表上其它的操作四、用单链表实现线性表上其它的操作 1.1.初始化单链表初始化单链表 void InitList(LNode*&HL)void InitList(LNode*&HL)HL=NULL;/O(1)HL=NULL;/O(1)2.2.检查单链表是否为空检查单链表是否为空 bool ListEmpty(LNode*HL)bool ListEmpty(LNode*HL)return(HL=NULL);return(HL=NULL);/O(1)/O(1

39、)3.3.删除单链表中结点，使之成为空表删除单链表中结点，使之成为空表void ClearList(LNode*&HL)void ClearList(LNode*&HL)LNode*cp,*np;LNode*cp,*np;cp=HL;cp=HL;while(cp!=NULL)while(cp!=NULL)np=cp-next;cp-next=np-np=cp-next;cp-next=np-next;next;delete cp;delete cp;HL=NULL;HL=NULL;/O(n)/O(n)4.4.得到单链表的长度得到单链表的长度 int ListSize(LNode*HL)/int

40、 ListSize(LNode*HL)/带头结点带头结点 P=HL-next;P=HL-next;int i=0;int i=0;while(P!=NULL)while(P!=NULL)i+;i+;P=P-next;P=P-next;return i;return i;/O(n)/O(n)5.5.得到单链表中第得到单链表中第pospos个结点中的元素个结点中的元素 ElemType GetElem(LNode*HL,int pos)ElemType GetElem(LNode*HL,int pos)if(pos1)if(pos1)cerrpos is out range!endl;cerrpo

41、s is out range!next;i=0;P=HL-next;while(P!=NULL)while(P!=NULL)i+;i+;if(i=pos)break;if(i=pos)break;P=P-next;P=P-next;if(P!=NULL)return P-data;if(P!=NULL)return P-data;else cerrpos is out range!endl;else cerrpos is out range!next;P=HL-next;while(while(P P!=NULL)!=NULL)coutdata;coutdatanext;-next;coute

42、ndl;coutdata=item)if (p-data=item)return i;return i;else p=p-next;i+;else p=p-next;i+;return false;return false;O(n)O(n)五、单链表的操作效率分析五、单链表的操作效率分析（1 1）查找查找 ：因线性链表只能顺序存取，即在查找时：因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为要从头指针找起，查找的时间复杂度为 O(n)O(n)。时间效率分析时间效率分析（2 2）插入和删除：因线性链表不需要移动元素，只要插入和删除：因线性链表不需要移动元素，只要修改指针，仅就

43、插入或删除而言，时间复杂度为修改指针，仅就插入或删除而言，时间复杂度为 O(1)O(1)。但是，如果要在单链表中进行在某结点但是，如果要在单链表中进行在某结点前前插或删插或删除操作，因为要除操作，因为要从头查找前驱从头查找前驱结点，所以一般情结点，所以一般情况下，况下，单链表插入和删除操作单链表插入和删除操作的时间复杂度是的时间复杂度是 O(n)（同顺序表）。（同顺序表）。1.双向链表双向链表六、其它形式的链表六、其它形式的链表typedef struct DuLNode ElemType data;/数据域 struct DuLNode *prior;/指向前驱的指针域 struct DuL

44、Node *next;/指向后继的指针域 DuLNode,*DuLinkList;双向链表双向链表：链表中每个结点除后继指针域和数据域链表中每个结点除后继指针域和数据域外还有一个前驱指针域。外还有一个前驱指针域。最后一个结点的指针域的指针又指回第一个结点的链表 a1 a2 .an 2.循环链表循环链表 和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。双向循环链表双向循环链表空表空表非空表非空表 a1 a2 .an双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。和单链表相同。“插入插入”和和“删除删除”时需要同时修时需要同时修

45、改两个方向上的指针。改两个方向上的指针。ai-1aies-next=p-next;p-next=s;s-next-prior=s;s-prior=p;psai-1ai插入插入ai-1删除删除aiai+1p-next=p-next-next;p-next-prior=p;pai-1七、七、静态链表静态链表静态链表：静态链表：在数组中增加一个（或两在数组中增加一个（或两个）指针域，这些指针域用来存放下个）指针域，这些指针域用来存放下一个（或上一个）数据元素在数组中一个（或上一个）数据元素在数组中的下标，从而构成用数组构造的单链的下标，从而构成用数组构造的单链表（或双链表）。静态链表中的指针表（或双

46、链表）。静态链表中的指针又称仿真指针。又称仿真指针。静态单链表的类型定义如下：静态单链表的类型定义如下：#define MAXSIZE 1000#define MAXSIZE 1000 /预分配最大的元素个数（连续空间预分配最大的元素个数（连续空间typedef typedef struct struct DataType data;DataType data;/数据域数据域 int next;int next;/指示域指示域 component,SLinkListMAXSIZEcomponent,SLinkListMAXSIZE;/这是一维结构型数组这是一维结构型数组例例 2：一：一线性表线

47、性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？，用静态链表如何表示？data1 1 1 1ZHAOZHAO3LILI5QIANQIAN6WUWU0ZHOUZHOU4SUNSUN20 01 12 23 34 45 56 610001000next说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一个静态链表；为一个静态链表；S0.nextS0.next则表示第则表示第1 1个结点在数组中的个结点在数组中的位置。位置。说明说明2 2：如果数组的第如果数组的第i i个分量表示链表个分量表

48、示链表的第的第k k个结点，则：个结点，则：Si.dataSi.data表示第表示第k k个结点的数据；个结点的数据；Si.nextSi.next 表示第表示第k+1k+1个结点个结点(即即k k的直的直接后继接后继)的位置。的位置。i头结点头结点头结点头结点说明说明3 3：静态链表的插入与删除操作与普通链表一样，不需要移静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器就可以了。动元素，只需修改指示器就可以了。例如：在线性表例如：在线性表 S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的的QIAN,SUN之间之间插入新元素插入新元素插入新元素插入新元素LIU，可

49、以这样实现：，可以这样实现：SSSS7 7 7 7.next=S3.next.next=S3.next.next=S3.next.next=S3.next；Step2:Step2:将将QIANQIAN的游标换为新元素的游标换为新元素LIULIU的的下标：下标：S3.next=S3.next=S3.next=S3.next=7 7 7 7Step1:Step1:将将QIANQIAN的游标值存入的游标值存入nextnext的游的游标中：标中：data2SUNSUN4ZHOUZHOU0WUWU6QIANQIAN5LILI3ZHAOZHAO1 1 1 10 01 12 23 34 45 56 6100

50、01000curi头结点头结点头结点头结点LIULIU6 67 77 7本章小结本章小结1.1.线性结构线性结构(包括表、栈、队、数组）的定义和特点包括表、栈、队、数组）的定义和特点：2.2.仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。直接后继。2.2.线性表线性表逻辑结构逻辑结构：“一对一一对一”或或“1:1”“1:1”存储结构：存储结构：顺序、链式顺序、链式运运 算：算：修改、插入、删除修改、插入、删除 查找和排序另述查找和排序另述 3.3.顺序存储顺序存储特征：特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：