数据结构线性表.pptx

《数据结构线性表.pptx》由会员分享，可在线阅读，更多相关《数据结构线性表.pptx（91页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构课程的起点第1页/共91页线性结构的定义：若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直直接接前前趋趋和和一一个个直直接后继。接后继。可表示为：（可表示为：（a a1 1,a,a2 2 ,a,an n）简言之，线性结构反映结点间的逻辑关系是1对1的。特点特点 只有一个首结点和尾结点；只有一个首结点和尾结点；特特点点 除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个个直接后继。直接后继。线性结构包括：线性结构包括：线性表、堆栈、队列、

2、字符串、数组线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是等，其中最典型、最常用的是-线性表线性表第2页/共91页2.1线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n n 0 0线性终点2.1线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n n 0 0空表空表线性终点（

3、a1,a2,ai-1，ai,ai1,an）第3页/共91页（A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级012004011401朱朱原原女女19电子信息工程电子信息工程200401班班012004011402魏喜燕魏喜燕女女18电子信息工程电子信息工程200401班班012004011403章巧娟章巧娟女女19电子信息工程电子信息工程200401班班012004011405张张政政男男19电子信息工程电子信息工程200401班班012004011410刘刘琰琰男 19 19电子信息工程电子信息工程200401班班：例例2分析学生情况登记表是什么结构。分析学生情况登记表是什么结构

4、。分析：分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。分析：分析：数据元素都是同类型（数据元素都是同类型（字母字母），），元素间关系是线性的。元素间关系是线性的。注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性注意：同一线性表中的元素必定具有相同特性！例1分析26个英文字母组成的英文表是什么结构。第4页/共91页2.1.22.1.2抽象数据类型线性表的定义ADT ListADT List 数据对象：D=ai|aiElemSet,i=1,2,.,n,n=0D=ai|ai

5、ElemSet,i=1,2,.,n,n=0 数据关系：R1=|ai-1,aiD,i=2,.,nR1=|ai-1,aiD,i=2,.,n 基本操作：1.IiniList(&L)/1.IiniList(&L)/构造空的线性表L L 2.LengthList(L)/2.LengthList(L)/求L L的长度 3.GetElem(L,i,&e)/3.GetElem(L,i,&e)/取L L中元素ai,ai,由e e返回aiai 4.PriorElem(L,ce,&pre_e)/4.PriorElem(L,ce,&pre_e)/求cece的前驱,由pre_epre_e返回 5.InsertElem(

6、&L,i,e)/5.InsertElem(&L,i,e)/在元素aiai之前插入新元素e e 6.DeleteElem(&L,i)/6.DeleteElem(&L,i)/删除第i i个数据元素 7.EmptyList(L)/7.EmptyList(L)/判断L L是否为空表 8.ClearList(&L)/8.ClearList(&L)/置L L为空表 .ADT List ADT List第5页/共91页算法2.1步骤：1从线性表LB中依次取得每个数据元素;GetElem(LB,i)e2依值在线性表LA中进行查访;LocateElem(LA,e,equal()3若不存在，则插入之。ListIn

7、sert(LA,n+1,e)第6页/共91页算法2.2步骤：1分别从LA和LB中取得当前元素ai和bj；2若aibj，则将ai插入到LC中，否则将bj插入到LC中。第7页/共91页算法时间复杂度算法2.1的时间复杂度为 O(ListLength(LA)ListLength(LB)算法2.2的时间复杂度为 O(ListLength(LA)+ListLength(LB)第8页/共91页2.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析第9页/共91页2.2.1顺序表的表示顺序表的表

8、示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存储线性表的元素。存储线性表的元素。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或顺序映像或顺序映像顺序存储定义：顺序存储方法：特点：逻辑上相邻的元素，物理上也相邻逻辑上相邻的元素，物理上也相邻可以利用可以利用数组数组VnVn来实现来实现注意：在注意：在C C语言中数组的下标是从语言中数组的下标是从0 0开始，即：开始，即：VnVn的有效范围是从的有效范围是从V0V0Vn-1Vn-1第10页

9、/共91页1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元素若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出存放位置亦可求出（利用数组VnVn的的下标）。设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为（称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai+1)=LOC(ai)+LLOC(LOC(a aii)=LOC()=LOC(a a11)+L*)+L*（

10、i-1i-1）对上述公式的解释如图所示线性表顺序存储特点第11页/共91页(a1,a1,a2,.an)(a1,a1,a2,.an)顺序存储结构的一般形式 序号 存储状态 存储地址 1 b1 b 2 b+p 2 b+p i b+(i-1)*p i b+(i-1)*p n b+(n-1)*p n b+(n-1)*p 自由区 maxleng b+(maxleng-1)*pmaxleng b+(maxleng-1)*p其中:b-:b-表的首地址/基地址/元素a1a1的地址。p-1p-1个数据元素所占存储单元的数目。maxleng-maxleng-最大长度,为某个常数。a1a1 a2a2 .aiai .

11、anan/第12页/共91页线性表顺序结构在C C语言中的定义例2.2.元素所占空间和表长合并为C C语言的一个结构类型：#define maxleng 100#define maxleng 100 typedef struct typedef struct ElemType elemmaxleng ElemType elemmaxleng；/下标:0,1,.,maxleng-1:0,1,.,maxleng-1 int length int length；/表长 SqList SqList；SqList LaSqList La；.其中：typedef-typedef-定义自己的数据类型，SqL

12、ist-SqList-结构类型名 La-La-结构类型变量名 La.length-La.length-表长 La.elem0-a1La.elem0-a1 La.elemLa.length-1-an La.elemLa.length-1-an 第13页/共91页顺序存储结构的寻址公式 i=1 2 i n i=1 2 i n 地址=b b+p b+(i-1)p b+(n-1)p=b b+p b+(i-1)p b+(n-1)p 假设:线性表的首地址为b,b,每个数据元素占p p个存储 单元,则表中任意元素ai(1in)ai(1in)的存储地址是:LOC(i)=LOC(1)+(i-1)*p LOC(i

13、)=LOC(1)+(i-1)*p =b+(i-1)*p (1in)=b+(i-1)*p (1in)例:假设 b=1024,p=4,i=35 b=1024,p=4,i=35 LOC(i)=b+(i-1)*p LOC(i)=b+(i-1)*p =1024+(35-1)*4 =1024+(35-1)*4 =1024+34*4 =1024+34*4 =1160 =1160 a1a1a2a2.aiai.anan/第14页/共91页设有一维数组设有一维数组，下标的范围是，下标的范围是到到，每个数组元素用，每个数组元素用相邻的相邻的个字节个字节存储。存储器按字节编址，设存储数组元存储。存储器按字节编址，设存

14、储数组元素素 的第一个字节的地址是的第一个字节的地址是9898，则，则 的第一个字的第一个字节的地址是多少？节的地址是多少？答案：113但此题要注意下标起点是从但此题要注意下标起点是从0 0开始：开始：LOC(M3)=98+5(4-1)=113解：解：已知地址计算通式为：已知地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）第15页/共91页2.2.2顺序表的实现（或操作）顺序表的实现（或操作）数据结构的基本运算：数据结构的基本运算：修改、插入、删除、查找、排序1)1)修改修改 通过数组的下标便可访问某个特定元素并修改之。通过数组的下标便可访问某个特定元素并修改之。核心语句核心语句

15、:Vi=x;显然，顺序表修改操作的时间效率是O(1)第16页/共91页在线性表的第在线性表的第i i个位置个位置前前插入一个元素插入一个元素实现步骤：实现步骤：将第将第n至第至第i位的元素向后移动一个位置；位的元素向后移动一个位置；将要插入的元素写到第将要插入的元素写到第i个位置；个位置；表长加表长加1。注意：注意：注意：注意：事先应判断事先应判断:插入位置插入位置i是否合法是否合法?表是否已满表是否已满?应当符合条件：应当符合条件：1in+1或或i=1,n+1for(j=n;j=i;j-)aj+1=aj;ai=x;n+;/元素后移一个位置元素后移一个位置/插入插入x x/表长加表长加1 1

16、核核心心语语句：句：2)2)插入插入第17页/共91页在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：12132124283042771213212425252830427712345678123456789插入插入25252525第18页/共91页实现步骤：实现步骤：将第将第i+1至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长减表长减1。注意：事先需要判断，删除位置注意：事先需要判断，删除位置i是否合法是否合法?应当符合条件：应当符合条件：1in或或i=1,n删除线性表的第删除线性表的第i i个位置上的元素个位置上的元素f

17、or(j=i+1;j=n;j+)aj-1=aj;n-;/元素前移一个位置元素前移一个位置/表长减表长减1 1 核心语句：核心语句：3)3)删除删除第19页/共91页123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：第20页/共91页2.2.3顺序表的运算效率分析顺序表的运算效率分析算法时间主要耗费在算法时间主要耗费在移动元素移动元素的操作上，因此的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动移动

18、元素次数元素次数)而移动元素的个数取决于插入或删除元素的位置而移动元素的个数取决于插入或删除元素的位置.思考：思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共应当考虑在各种位置插入（共n+1种可能）的种可能）的平均平均移动次数才合理。移动次数才合理。讨论讨论1：若在长度为若在长度为n的线性表的第的线性表的第i位前位前插入插入一个元素，则一个元素，则向后移动元素的次数向后移动元素的次数f(n)为为:f(n)=ni+1时

19、间效率分析时间效率分析:第21页/共91页插入操作移动元素次数的分析 在（a1,a2,.,ai,.an)中ai之前插入新元素e (1=i=n+1)当i=1 2 3 j n n+1移动元素次数个数:n n-1 n-2 n-i+1 1 0 假定pi是在各位置插入元素的概率相同，则插入一个元素时移动元素的平均值是：n+1 Eis=pi(n-i+1)=1/(n+1)*(n+(n-1)+.+1+0)=n/2 i=1 其中：p1=p2=.=pn=p(n+1)=1/(n+1)a1 a2 .ai.an 1 2 i n n+1 第22页/共91页删除操作移动元素次数的分析 当 i=1 2 3.i .i=1 2

20、3.i .n n 移动元素次数个数=n-1 n-2 .n-i.=n-1 n-2 .n-i.0 0 假定qiqi是在各位置插入元素的概率相同，则删除一个元素时移动元素的平均值是:n n Edl=qi(n-i)=1/n*(n-1)+.+1+0)=(n-Edl=qi(n-i)=1/n*(n-1)+.+1+0)=(n-1)/21)/2 i=1i=1 其中：q1=q2=.=qn=1/n q1=q2=.=qn=1/n 第23页/共91页深入讨论1：顺序表各种操作算法的顺序表各种操作算法的“通式通式”该如何书该如何书写？写？采用采用抽象数据类型抽象数据类型来表示来表示第24页/共91页线性表的抽象数据类型定

21、义（见教材见教材P19）ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R=|ai1,aiD,i=2,n基本操作：l初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；l插入、删除ADTList第25页/共91页InitList(&L);/建空表，初始化建空表，初始化DestoryList(&L);/撤销表，释放内存撤销表，释放内存intLengthList(L);/求表中元素个数，即表长求表中元素个数，即表长POSITIONLocateElem(L,ElemTypee，compare()/查找查找ePriorElem

22、(L,cur_e,&pre_e);/求当前元素求当前元素e的前驱的前驱NextElem(L,cur_e,&next_e);/求当前元素求当前元素e的后继的后继ListInsertBefore(&L,i,e);/把把e插入插入到第到第i个元素之前个元素之前ListDelete(&L,i,&e);/删除删除第第i个元素并个元素并“看看”此元素此元素ListTraverse(L,Visit();/“看看”表中全部元素（遍历）表中全部元素（遍历）l初始化、撤销、清空、判空；l求表长、表头、表尾、前趋、后继；l读元素、查找（含定位）、遍历；l插入、删除第26页/共91页深入讨论2：顺序表的存储结构是一维

23、数组，如果插入的顺序表的存储结构是一维数组，如果插入的元素个数元素个数超过超过数组定义的数组定义的长度长度怎么办？怎么办？采用采用动态分配动态分配的一维数组的一维数组第27页/共91页动态数组简介动态数组简介先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因插入元素而插入元素而空间不足空间不足时，可为顺序表增加一个时，可为顺序表增加一个固定长固定长度的空间增量度的空间增量。#defineLIST_INIT_SIZE100/存储空间的初始分配量存储空间的初始分配量#defineLISTINCREMENT10/存储空间的分配增量存储空间的分配增量 Typedefstr

24、uctElemType*elem;/表表基址基址(用指针用指针*elemelem表示表示）intlength;/表表长度（长度（表中有多少个元素表中有多少个元素）intlistsize;/当前当前分配的表尺寸分配的表尺寸（字节单位字节单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：第28页/共91页sizeof(x)sizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开函数的意思是：新开

25、一片大小为一片大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。StatusInitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序 L.length=0;/暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量 ReturnOK;/InitList_Sq/Init

26、List_Sq动态创建一个动态创建一个空空顺序表的算法：顺序表的算法：第29页/共91页realloc(*p,newsize)函数的意思是：新开一函数的意思是：新开一片大小为片大小为newsize的连续空间，并把以的连续空间，并把以*p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法 StatusListInsert_Sq(SqList&L,inti,ElemTypee)/在顺序线性表中第在顺序线性表中第i i个位置之前插入新的元素个位置之前插入新的元素e eif(iL.length+1)returnERROR;/检验检验i值的合法性值的合法

27、性if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTLISTINCREMENTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错分配失败则退出并报错 L.elem=newbase;/重置新基址重置新基址 L.listsize=L.listsize+LISTINCREMENTLISTINCREMENT;/增加表尺寸增加表尺寸第30页/共91页q=&L.e

28、lemi-1;/q为插入位置。这是没有头结点的情况为插入位置。这是没有头结点的情况for(p=L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位置为元素位置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1returnOK;/ListInsert_Sq动态数组的核心是动态数组的核心是reallocrealloc(void*ptr,newsize)(void*ptr,newsize)函数！函数！第31页/共91页动态顺序表的删除算法动态顺序表的删除算法StatusL

29、istDelete_Sq(SqList&L,inti,ElemType&e)/在顺序表在顺序表L中删除第中删除第i个元素，用个元素，用e返回其值返回其值if(iL.length)returnERROR;/i值不合法，返回值不合法，返回p=&L.elemi-1;/p是被删除元素的位置是被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给eq=L.elem+L.length-1;/q是表尾的位置是表尾的位置for(+p;p=q;p+)*(p-1)=*p;/待删元素后面的统统前移待删元素后面的统统前移-L.length;/表长表长-1returnOK;/ListDelete_Sq第32页

30、/共91页链式存储结构链式存储结构2.22.2节小结节小结线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的两个元：逻辑关系上相邻的两个元素在物理存储位置上也相邻；素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素，方便快捷；可以随机存取表中任一元素，方便快捷；缺点：缺点：在插入或删除某一元素时，需要移动大量元素。在插入或删除某一元素时，需要移动大量元素。解决问题的思路：解决问题的思路：改用另一种线性存储方式：改用另一种线性存储方式：第33页/共91页思考题：一、单项选择题()1.()1.一个数据对象是_的集合。A.A.相同类型的数据项 B.B.相同类型的数据元素 C.

31、C.不同类型的数据项 D.D.不同类型的数据元素()2._()2._是一个线性表。A.(1,3,5,7)B.(1,2,3,4,.)A.(1,3,5,7)B.(1,2,3,4,.)C.A,B,C,D,E D.a,b,c C.A,B,C,D,E D.a,b,c 二、简要回答问题：1.1.一个算法具有哪几个特点？举例说明之。2.2.对单链表可以进行哪几种操作？3.3.线性表的顺序存储结构有什么优点和缺点?第34页/共91页三、算法设计题设顺序表a中的数据元素递增有序，试写一算法，将X插入到顺序表的适当位置，以保持该表的有序性步骤提示：1、查找X在顺序表a.elema.length中的插入位置，即求满

32、足a.elemixdatahead-data不放元素，head-nexthead-next指向首结点a1,a1,当head-next=NULL,head-next=NULL,为空表；否则为非空表。第42页/共91页TypedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;教材P28P28对于线性表的单链表存储结构描述:Q1Q1：第一行的第一行的LnodeLnode与最后一行的与最后一行的LnodeLnode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LnodeLnode是结构名，后者是结构名，后者LnodeLn

33、ode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种，是一种“新定义名新定义名”，它只，它只是对现有类型名的补充，而不是取代。是对现有类型名的补充，而不是取代。请注意：请注意：TypedefTypedef不可能创造不可能创造任何新的数据类型，而仅仅是任何新的数据类型，而仅仅是在原有的数据类型中命名一个在原有的数据类型中命名一个新名字，其目的是使你的程序新名字，其目的是使你的程序更易阅读和移植。更易阅读和移植。第43页/共91页TypedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;Q2Q2

34、：那为何两处要同名那为何两处要同名(Lnode和和Lnode）？太不严谨了吧？）？太不严谨了吧？A2A2：同名是为了表述起来方便。例如，若结构名为同名是为了表述起来方便。例如，若结构名为studentstudent，其新定义名缩写也最好写成，其新定义名缩写也最好写成studentstudent，因为描述的对象相，因为描述的对象相同，方便阅读和理解。同，方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstructLnodeLnode是何意？是何意？A3A3：在：在“缩写缩写”LnodeLnode还没出现之前，只能用原始的还没出现之前，只能用原始的structstructL

35、nodeLnode来进行变量说明。此处说明了指针分量的来进行变量说明。此处说明了指针分量的数据类型是数据类型是structstructLnodeLnode。Typedefstructstudentcharname;intage;student,*pointer;第44页/共91页3.单链表的实现单链表的实现（1 1）单链表的建立和输出单链表的建立和输出 （2 2）单链表的修改单链表的修改 （3 3）单链表的插入单链表的插入 （4 4）单链表的删除单链表的删除 第45页/共91页（1）单链表的建立和输出单链表的建立和输出例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写出C

36、语言程序。实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要空间并及时赋值，后继结点的地址要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”,后种后种“萝萝卜卜”！第46页/共91页#include#include#include#includetypedefstructnodechardata;structnode*next;node;将全局变量及函数提前说明：node*p,*q,*head;/一般需要一般需要3 3个指针变量个指针变量 intn;/数据元素的个数数据元素的个数 intm=sizeof(node)

37、;/*/*结构类型定义好之后，结构类型定义好之后，每个每个nodenode类型类型的长的长度就固定了，度就固定了，m m求一次即可求一次即可*/第47页/共91页新手特别容易忘记！新手特别容易忘记！inti;head=(node*)malloc(m);/m=sizeof(node)前面已求出前面已求出p=head;for(i=1;idata=i+a-1;/第一个结点值为字符第一个结点值为字符ap-next=(node*)malloc(m);/为后继结点为后继结点“挖坑挖坑”！p=p-next；/让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1;/最后一个元素要单独处理

38、最后一个元素要单独处理p-next=NULL;/单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build()/字母链表的生成。要一个个慢慢链入要一个个慢慢链入第48页/共91页（2）单链表的修改单链表的修改(或读取）或读取）思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p-data=new_value。修改第第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：StatusGetElem_L(LinkListL,inti,ElemType&e)p=L-next;j=1;/带头结点的链表带头结点的链表while(p&jnext;+j;

39、if(!p|ji)returnERROR;p-data=e;/若是读取则为：若是读取则为：e=p-data;returnOK;/GetElem_L缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开始逐一个元素，只能从头指针开始逐一查询（查询（顺藤摸瓜顺藤摸瓜），无法随机存取），无法随机存取 。第49页/共91页在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xsabp链表插入的核心语句：链表插入的核心语句：StepStepStepStep 1 1 1 1：s-next=s-next=p-p-nextnext;StepStepStepStep 2

40、2 2 2：p-nextp-next=s=s；p-nexts-next思考：思考：思考：思考：Step1Step1Step1Step1和和和和2 2 2 2能互换么？能互换么？能互换么？能互换么？X X 结点的生成方式：结点的生成方式：s=(node*)malloc(m);s-data=X X;s-next=?bap插插插插 入入入入 X X（3）单链表的插入单链表的插入第50页/共91页在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：cabp删除动作的核心语句删除动作的核心语句（要借助辅助指针变量（要借助辅助指针变量q q）：）：q=p-next;/首先保存首先保存b

41、b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next;/将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q)；/彻底释放彻底释放b b结点空间结点空间p-next思考：思考：省略省略free(q)语句语句行不行？行不行？(p-next)-nextq（4）单链表的删除单链表的删除第51页/共91页4.链表的运算效率分析链表的运算效率分析（1）查找查找因线性链表只能顺序存取，即在查找时要从头指针找起，查因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为找的时间复杂度为O(n)。时间效率分析（2）插入和删除插入和删除因线性链表不

42、需要移动元素，只要修改指针，一般情况下时间因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为复杂度为O(1)。但是，如果要在单链表中进行但是，如果要在单链表中进行前前插或删除操作，因为要插或删除操作，因为要从头查找前驱从头查找前驱结点，所耗时间复杂度将是结点，所耗时间复杂度将是O(n)。第52页/共91页53算法要求：算法要求：已知：已知：线性表线性表 A A和和B B，分别由，分别由单链表单链表 LaLa和和LbLb 存储，其中存储，其中数据元素按值数据元素按值非递减有序非递减有序排列排列（即已经有序）（即已经有序）；要求：要求：将将A A和和B B归并归并为一个新的线性表为一个

43、新的线性表C C,C C的数据元素仍的数据元素仍按值非递减排列。设线性表按值非递减排列。设线性表C C由由单链表单链表 LcLc 存储。存储。假设：假设：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）预测：预测：合并后的合并后的C C=（2,3,5,6,8,8,9,112,3,5,6,8,8,9,11，1111）例：例：两个链表的归并两个链表的归并（教材教材P31P31例例）第53页/共91页54链表示意图：3 5 11/8 LaLa 2 6 11/8 LbLb 9 2 3 6 5 LcLc 8 头结点头结点第54页/共91页55算法设计

44、：算法主要包括搜索、比较、插入三个操作：搜索：需要设立需要设立三个指针来三个指针来指向指向La、Lb和和Lc c链表；链表；比较：比较比较La a和和Lb b表中表中结点数据的大小；结点数据的大小；插入：将将La a和和Lb b表表中数据较小的结点插入新链表中数据较小的结点插入新链表Lc c。请注意链表的特点，仅改变指针请注意链表的特点，仅改变指针便可实现数据的移动便可实现数据的移动,即即 “数据不动，指针动数据不动，指针动”第55页/共91页56La35811Lb268119PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb，PcPc指向新链表当前结点。指向新链表当前结点

45、。归并过程示意如下：归并过程示意如下：Lc=LaPbPaPaPb第56页/共91页算法实现：VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/已知单链线性表已知单链线性表LaLa和和LbLb的元素的元素按值非递减排列。归并为按值非递减排列。归并为LcLc后也按值非递减排列。后也按值非递减排列。free(Lb);/释放释放LbLb的头结点的头结点 /MergeList_Lpc-next=pa?pa:pb;/插入非空表的剩余段插入非空表的剩余段while(pa&pb)/将将pa pa、pbpb结点按大小依次插入结点按大小依次插入Lc中中 if

46、(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pa=LaLa-next;pb=LbLb-next;Lc=pc=La；/有头结点有头结点见见P31P31算法算法2.122.12?是条件运算符（是条件运算符（为真则取第为真则取第1 1项，项，见见P10P10条件赋值条件赋值）注：注：注：注：LcLcLcLc用的是用的是用的是用的是LaLaLaLa的头指针的头指针的头指针的头指针第57页/共91页58课下请思考：1、不用Lc，直接把La表插到Lb表中；或者把Lb表插到La表中，怎么修改？2、重复的数据

47、元素不需要插入，怎么修改？第58页/共91页若某种高级语言没有指针类型，能否实现链式存储和运算？如何实现？答：答：答：答：能！能！能！能！虽然链表通常用动态级联方式存储，但虽然链表通常用动态级联方式存储，但虽然链表通常用动态级联方式存储，但虽然链表通常用动态级联方式存储，但也可以用一片连续空间（一维数组）实现链式存也可以用一片连续空间（一维数组）实现链式存也可以用一片连续空间（一维数组）实现链式存也可以用一片连续空间（一维数组）实现链式存储，这种方式称为储，这种方式称为储，这种方式称为储，这种方式称为静态链表静态链表静态链表静态链表。具体实现方法：具体实现方法：定义一个结构型数组（每个元定义一

48、个结构型数组（每个元素都含有素都含有数据域数据域和和指示域指示域），就可以完全描述），就可以完全描述链表，链表，指示域指示域就相当于动态链表中的指针。就相当于动态链表中的指针。指示域也常称指示域也常称为“游游标”第59页/共91页动态链表样式：动态链表样式：静态链表样式：静态链表样式：指针指针数据数据指针指针数据数据指针指针数据数据指示指示数据数据指示指示数据数据指示指示数据数据指示指示数据数据指示指示数据数据数组中每个元素数组中每个元素都至少有两个分都至少有两个分量，属于量，属于结构型结构型数组数组。常用于无指针类型常用于无指针类型的高级语言中。的高级语言中。第60页/共91页 静态单链表的

49、类型定义如下：静态单链表的类型定义如下：#defineMAXSIZE1000/预分配最大的元素个数（连续空间预分配最大的元素个数（连续空间 typedefstructElemTypedata;/数据域数据域 intcur;/指示域指示域 component,SLinkListMAXSIZE;/这是一维结构型数组这是一维结构型数组若此分量定义为若此分量定义为指针型指针型，属于，属于动态链表（题目中是指针）动态链表（题目中是指针）；若此分量定义为若此分量定义为整型整型（通常存放下标），则属于（通常存放下标），则属于静态链表静态链表。ZZ47474747Y Y3131V V23232323XX171

50、7U U0505100100100100119119119119104104104104108108108108116116116116112112112112第61页/共91页一线性表S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用静态链表如何表示？教材P32例题data1 1 1 1ZHAOZHAO3LILI5QIANQIAN6WUWU0ZHOUZHOU4SUNSUN20 01 12 23 34 45 56 6 10001000cur说明说明1 1：假设假设S S为为SLinkListSLinkList型变量，则型变量，则SMAXSIZESMAXSIZE 为一个静态链表；为一个