《线性表-课件.ppt》由会员分享，可在线阅读，更多相关《线性表-课件.ppt（144页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 *数据结构数据结构第二章第二章线性表线性表 *第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串、数组和广串、数组和广义表义表 线性结构线性结构若若结结构构是是非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1,a,a2 2 ,a,an n）线性结构的定义：线性结构的定义：线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）*线性结构的特点：线性结构的特点：只有一个
2、首结点和尾结点；只有一个首结点和尾结点；除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的 *第第2 2章章线性表线性表1.了解线性结构的特点了解线性结构的特点2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定义、查找、插入和删除掌握链表的
3、定义、查找、插入和删除 4.4.能够从时间和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标 *2.1线性表的类型定义线性表的类型定义2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.4线性表的应用线性表的应用教学内容教学内容 *L=（a1,a2,ai-1，ai,ai1，,an）线线性性表表的的定定义义：由由n（n=0）个个类类型型相相同同的的数数据据元素组成的有限序列元素组成的有限序列n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai
4、i的直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义 *例例例例11分析分析分析分析2626个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表个英文字母组成的英文表 （A,B,C,D,Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20
5、 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 190404级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班：例例例例22分析学生情况登记表分析学生情况登记表分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性1:11:1 *例例例例33某校从某校从某校从某校从19781978年到年到年到
6、年到19831983年各种型号的计算机拥年各种型号的计算机拥年各种型号的计算机拥年各种型号的计算机拥有量的变化情况。有量的变化情况。有量的变化情况。有量的变化情况。（6，17，28，50，92，188）例例例例4 4一副扑克的点数一副扑克的点数一副扑克的点数一副扑克的点数 数据元素都是字符数据元素都是字符;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性数据元素都是数字数据元素都是数字;元素间关系是线性元素间关系是线性（2，3，4，J，Q，K，A）线性表性表特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中存在存在唯一唯一的一个被称
7、作的一个被称作“第一个第一个”的数据元素的数据元素存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个直接前直接前驱除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个直接后个直接后继相邻结点间的关系相邻结点间的关系 *线性表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L InitList(L)L InitList(L)构造一个空的线性表构造一个空的线性表L L，即表的初始化。，即表的初始化。2.2.销毁线性表销毁线性表L Destor
8、yList(L)L DestoryList(L)其作用是销毁当前线性表其作用是销毁当前线性表L L 3.3.清空线性表清空线性表L ClearList(L)L ClearList(L)清空清空L L使之成为空表使之成为空表 4.4.求线性表求线性表L L的长度的长度 ListLength(L)ListLength(L)返回返回L L的长度，即线性表中数据元素的个数的长度，即线性表中数据元素的个数5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(L)IsEmpty(L)判断判断L L是否为空表，是返回是否为空表，是返回true,true,否返回否返回falsefalse6.6.
9、获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,&e)GetElem(L,i,&e)将将L L中第中第i i个数据元素的值返回到变量个数据元素的值返回到变量e e中中 抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为 *7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e)LocateELem(L,e)判断线性表判断线性表L L中是否存在值为中是否存在值为e e的结点的结点 8.8.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(&L,i,e)ListIns
10、ert(&L,i,e)向线性表向线性表L L的第的第i i个位置之个位置之前前插入一个值为插入一个值为e e的数据元素的数据元素删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(&L,i,&e)ListDelete(&L,i,&e)删除线性表删除线性表L L的第的第i i个数据元素，并将该数据元素的值返回个数据元素，并将该数据元素的值返回e e中中10.10.返回前驱结点返回前驱结点 PriorElem(L,cur_e,&pri_e)PriorElem(L,cur_e,&pri_e)返回返回L L中当前数据元素中当前数据元素cur_ecur_e的前驱结点的前驱
11、结点11.11.返回后继结点返回后继结点NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)7.7.返回返回L L中当前数据元素中当前数据元素cur_ecur_e的的后继结点的的后继结点 *2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn
12、来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。*Loc(元素元素i)=Loc(元素元素1)+（i-1)*m元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容顺序存储顺序存储起始地址起始地址L Lo o顺序表：定义：用一组地址连续的存储单元存放一个线性表定义：用一组地址连续的存储单元存放一个线性表元素地址计算方法：元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*m/任意
13、两个相邻元素间地址相差任意两个相邻元素间地址相差mLOC(ai+1)=LOC(ai)+m特点：特点：实现实现逻辑上相邻逻辑上相邻物理地址相邻物理地址相邻实现实现随机存取随机存取起始地址，基地址起始地址，基地址第第i个元素的地址个元素的地址 每一个数据元素的存每一个数据元素的存储位置都和位置都和线性表的起性表的起始位置相差一个始位置相差一个和数据元素在和数据元素在线性表中的位序性表中的位序成正比的成正比的常数常数，因此只要确定了起始位置，因此只要确定了起始位置，线性表中任一数据元素都可性表中任一数据元素都可随机存取随机存取。顺序表可以随机存取，高序表可以随机存取，高级程序程序设计语言中言中的数的
14、数组也有随机存取的特性。也有随机存取的特性。实现：实现：可用可用C语言的一维数组实现语言的一维数组实现 *#define MAXSIZE 100 /#define MAXSIZE 100 /预定义最大长度预定义最大长度typedef struct typedef struct ElemType ElemMAXSIZE;/ElemType ElemMAXSIZE;/指向数据元素的基地址指向数据元素的基地址 int length;/int length;/线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义线性表基本运算操作有：线性表基本运算操作有：查找、插
15、入、删除查找、插入、删除由于线性表的长度是可变的，所需的存储空间不同，由于线性表的长度是可变的，所需的存储空间不同，所以在所以在C语言中，可用语言中，可用动态分配的一维数组动态分配的一维数组来描述。来描述。*a1a2anbb+lb+（n-1）l12n内存存储地址元素序号b+(maxlen-1)l备用空间#define LIST_INIT_SIZE 100#define LISTINCREMENT 10Typedef struct ElemType *elem;int length;SqList;数据元素不是简单类型时,可定义结构体数组动态申请内存L.elem=(ElemType*)malloc
16、(LIST_INIT_SIZE*sizeof(ElemType);线性表存储空间初始分配量线性表存储空间初始分配量线性表存储空间分配增量线性表存储空间分配增量存储空间基址存储空间基址预定义 *malloc(malloc(m m)：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空间的首地址sizeof(sizeof(x x)：计算变量：计算变量x x的长度的长度free(free(p p)：释放指针：释放指针p p所指变量的存储空间，所指变量的存储空间，即彻底删除一个变量即彻底删除一个变量补充：补充：C C语言的动态分配函数（语言的动态分配函数（）*线性
17、表的基本操作线性表的基本操作1.1.初始化线性表初始化线性表L InitList(L)L InitList(L)2.2.销毁线性表销毁线性表L DestoryList(L)L DestoryList(L)3.3.清空线性表清空线性表L ClearList(L)L ClearList(L)4.4.求线性表求线性表L L的长度的长度 ListLength(L)ListLength(L)5.5.判断线性表判断线性表L L是否为空是否为空 IsEmpty(L)IsEmpty(L)6.6.获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,e)GetElem(L,
18、i,e)7.7.检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e)LocateELem(L,e)8.8.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,e)ListInsert(L,i,e)9.9.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,e)ListDelete(L,i,e)抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为抽象数据类型的定义为 *典型操作的算法实现典型操作的算法实现1.1.初始化线性表初始化线性表L L（参数用引用）（参数用引用）StatusInit
19、List_Sq(SqList&L)/构造一个空的顺序表构造一个空的顺序表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);/为顺序表分配空间为顺序表分配空间if(!L.elem)exit(OVERFLOW);/存储分配失败存储分配失败L.length=0;/空表长度为空表长度为01.returnOK;2.*2.2.销毁线性表销毁线性表L Lvoid DestroyList(SqList&L)void DestroyList(SqList&L)if(L.elem)free(L.elem);/if(L.elem)free(L.ele
20、m);/释放存储空间释放存储空间 return OK;return OK;3.3.清空线性表清空线性表L LvoidClearList(SqList&L)L.length=0;/将线性表的长度置为将线性表的长度置为0 *4.4.求线性表求线性表L L的长度的长度intGetLength(SqListL)return(L.length);5.5.判断线性表判断线性表L L是否为空是否为空intIsEmpty(SqListL)if(L.length=0)return1;elsereturn0;*按序号查找（位置）按序号查找（位置）按值查找按值查找查找查找 *25124789361412345678
21、9L.elem0e=L.elem3 /取第取第4个元素赋给变量个元素赋给变量e查找第查找第 i i 个元素（假设个元素（假设i i=4=4）序号若下标从0开始L.elem1L.elem2L.elem3 *6.6.获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容/根据根据指定位置指定位置i i，获取相应位置数据元素的内容，获取相应位置数据元素的内容int GetElem(SqList L,int int GetElem(SqList L,int i,ElemType&ei,ElemType&e)if(iL.length)return ERROR;if(iL.length)r
22、eturn ERROR;/判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L.elemi-1;/第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;return OK;*查找元素查找元素e e（根据指定数据查找，返回其所在的位置）（根据指定数据查找，返回其所在的位置）顺序查找图示顺序查找图示25 34 57 16 48 09012345data查找查找 16 i25 34 57 16 48 09i25 34 57 16 48 09i25 34 57 16 48 09i查找成功查找成功 *25 3
23、4 57 16 4801234data查找 50i25 34 57 16 48i25 34 57 16 48i25 34 57 16 48i25 34 57 16 48i查找失败查找失败 *7.7.在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素(找到返回其位找到返回其位序，否则返回序，否则返回ERROR)ERROR)int LocateELem(SqList L,ElemType e)for(i=0;i L.length;i+)if(L.elemi=e)return i;return ERROR;*2512478936141234567892512479989361499
24、插入插入251247893614251247893614251247893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）先看个结点之前）先看i i=4=4依次赋值 *（1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。（3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（
25、4 4）将要插入的新元素）将要插入的新元素e e放入第放入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法思想算法思想】*8.8.在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e StatusListInsert_Sq(SqList&L,inti,ElemTypee)if(iL.length+1)returnERROR;/i值不合法值不合法if(L.length=MAXSIZE)returnERROR;/当前存储空间已满当前存储空间已满for(j=L.length-1;j=i-1;j-)L.elemj+
26、1=L.elemj;/插入位置及之后的元素后移插入位置及之后的元素后移L.elemi-1=e;/将新元素将新元素e放入第放入第i个位置个位置+L.length;/表长增表长增1returnOK;【算法描述算法描述】*若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元
27、素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：假设在线性表的任何位置上插入、删除元素都是等概率的，则 *251247893614123456789251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）先看个结点）先看i i=4=4删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次 *（1 1）判断）判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元
28、素保留在e e中。中。（3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【算法思想算法思想】*9.9.将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除StatusListDelete_Sq(SqList&L,inti,ElemType&e)if(iL.length)returnERROR;/i值不合法值不合法e=L.elemi-1;/将欲删除的元素保留在将欲删除的元素保留在e中中for(j=i;j=L.length-1;j+)L.elemj-1=L.elem
29、j;/被删除元素之后的元素前移被删除元素之后的元素前移-L.length;/表长减表长减1returnOK;【算法描述算法描述】*若删除尾结点，则根本无需移动（特别快）；若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中若删除首结点，则表中n-1n-1个元素全部前移（特别慢）；个元素全部前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n n种可能）的平均移动次数，种可能）的平均移动次数，该如何计算？该如何计算？【算法分析算法分析】算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上算法评价设Qi是是删除第除第i个元素的概率，个元素的概率，则在在长度
30、度为n的的线性表性表中中删除一个元素所需移除一个元素所需移动的元素次数的平均次数的元素次数的平均次数为：*查找、插入、删除算法的平均查找、插入、删除算法的平均时间时间复杂度为复杂度为O(n)O(n)故在故在顺序表中插入或删除顺序表中插入或删除一个元素时，平一个元素时，平均移动表的一半元素，当均移动表的一半元素，当n n很大时，很大时，效率效率很低很低例：已知例：已知顺序表序表La和和Lb的数据元素按的数据元素按值非非递减排列，减排列，归并并La和和Lb得到新的得到新的顺序序表表Lc，Lc的元素也按的元素也按值非非递减排列减排列Ch2_3.c合并有序顺序表合并有序顺序表算法思想：算法思想：基本操
31、作是基本操作是“复制复制”，设，设2 2个下标个下标i i和和j j，分别，分别指向指向2 2个表当前处理的元素，比较它们的值，当个表当前处理的元素，比较它们的值，当i i所指向的值不大于所指向的值不大于j j所指向的值时，复制所指向的值时，复制i i所指元所指元素到素到LcLc中，否则复制中，否则复制j j所指元素到所指元素到LcLc中。中。反复进行上述操作，直到反复进行上述操作，直到LALA或或LBLB结束之后，结束之后，再把尚未结束的再把尚未结束的LBLB或或LALA的剩余各元素依次复制到的剩余各元素依次复制到LCLC中中 。*void Mergelist(SqList La,SqLis
32、t Lb,SqList&Lc)void Mergelist(SqList La,SqList Lb,SqList&Lc)InitList(Lc);InitList(Lc);n=ListLength(La);m=ListLength(Lb);n=ListLength(La);m=ListLength(Lb);LC.Length=m+n;LC.Length=m+n;i=j=k=1;i=j=k=1;while (i=n&j=m)while (i=n&j=m)/当当LALA和和LBLB均未完均未完 GetElem(La,i,&ai);/GetElem(La,i,&ai);/取取la la第第i i个元
33、素，放到个元素，放到ai ai中中 GetElem(Lb,j,&bj);GetElem(Lb,j,&bj);if (ai=bj)if (ai=bj)ListInsert_Lc(Lc,k+,ai);i+;ListInsert_Lc(Lc,k+,ai);i+;/LA/LA的当前项较小，将它复制到的当前项较小，将它复制到LCLC中中 *elseelse ListInsert_Lc(Lc,k+,bj);j+;ListInsert_Lc(Lc,k+,bj);j+;/LB/LB的当前项较小，将它复制到的当前项较小，将它复制到LCLC中中 while (in)while (in)/LA/LA还有剩余还有剩余
34、GetElem(La,i+,ai);GetElem(La,i+,ai);ListInsert_Lc(Lc,k+,ai);ListInsert_Lc(Lc,k+,ai);/将将LALA的剩余各元素依次复制到的剩余各元素依次复制到LCLC中中 while (jm)while (jnext=NULLhead-next=NULL *讨论讨论2 2.在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？便于便于首元结点首元结点(第一个结点第一个结点)的处理的处理首元结点的地址保存在头结点的指针域中首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置所以在链表的第一个位置上
35、的操作和其它位置一致，无须进行特殊处理一致，无须进行特殊处理;便于便于空表和非空表空表和非空表的统一处理的统一处理无论链表是否为空，头指针都是指向头结无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就点的非空指针，因此空表和非空表的处理也就统一了。统一了。*讨论讨论3.3.头结点的头结点的数据域数据域内装的是什么？内装的是什么？头结点的头结点的数据域数据域可以为空，也可存放线性表可以为空，也可存放线性表长度长度等附加信息，但此结点不能计入链表长度值。等附加信息，但此结点不能计入链表长度值。头结点的数据域头结点的数据域H H *（1 1）结点在存储器中的位置是结点在存储
36、器中的位置是任意任意的，即的，即逻辑上相逻辑上相邻的数据元素在物理上不一定相邻邻的数据元素在物理上不一定相邻链表（链式存储结构）的特点链表（链式存储结构）的特点（2 2）单链表中，任何两个元素的存储位置之间没有单链表中，任何两个元素的存储位置之间没有固定的联系，每个元素的存储位置都包含在其直固定的联系，每个元素的存储位置都包含在其直接前驱结点的信息中。接前驱结点的信息中。（3）访问时只能通过头指针进入链表，并通过每个）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点结点的指针域向后扫描其余结点(顺藤摸瓜顺藤摸瓜)，所，所以寻找第一个结点和最后一个结点所花费的时间以寻找第一个
37、结点和最后一个结点所花费的时间不等不等这种存取元素的方法被称为这种存取元素的方法被称为顺序存取法顺序存取法 *优点优点数据元素的个数可以自由扩充数据元素的个数可以自由扩充插入、删除等操作不必移动数据，只需插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高修改链接指针，修改效率较高链表的优缺点链表的优缺点 *缺点缺点存储密度小存储密度小存取效率不高，必须采用存取效率不高，必须采用顺序存取顺序存取，即存，即存取数据元素时，只能按链表的顺序进行访问取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）（顺藤摸瓜）链表的优缺点链表的优缺点 *练习练习1.1.链表的每个结点中都恰好包含一个指针。链
38、表的每个结点中都恰好包含一个指针。2.2.顺序表结构适宜于进行顺序存取，而链表顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。适宜于进行随机存取。3.3.顺序存储方式的优点是存储密度大，且插顺序存储方式的优点是存储密度大，且插入、删除运算效率高。入、删除运算效率高。4.4.线性表若采用链式存储时，结点之间和结线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。点内部的存储空间都是可以不连续的。5.5.线性表的每个结点只能是一个简单类型，线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型而链表的每个结点可以是一个复杂类型 *2.3.1 2.3.1 单
39、链表的定义和实现单链表的定义和实现非空表非空表空表空表单链表是由表头唯一确定，因此单链表可单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名以用头指针的名字来命名若头指针名是若头指针名是L，则把链表称为表，则把链表称为表L *typedef struct LNodetypedef struct LNode ElemType data;ElemType data;/数据域数据域 struct LNode *next;struct LNode *next;/指针域指针域LNode,*LinkList;LNode,*LinkList;/*LinkList/*LinkList为为LnodeLn
40、ode类型的指针类型的指针单链表的存储结构定义单链表的存储结构定义LNode*pLinkListp *LNode*p注意区分指针变量和结点变量两个不同的概念注意区分指针变量和结点变量两个不同的概念指针变量指针变量p p：表示结点地址：表示结点地址结点变量结点变量*p p：表示一个结点：表示一个结点注注意意：LinkList和和LNode*是是不不同同名名字字的的同同一一个个指指针针类类型型，LinkList类类型型的的指指针针变变量量head表表示示它它是是单单链链表表的的头头指指针针,LNode*类类型型的的指指针针变变量量p表表示示它它是是指指向向某某一结点的指针。一结点的指针。typed
41、ef struct LNode ElemType data;struct LNode *next;LNode,*LinkList;data nextp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域生成一个新结点：p=(LinkList)malloc(sizeof(Lnode);系统回收p结点：free(p)pab若当前结点由p指向，那么它的下一个结点可表示为p-nextp-next同理，下下个结点可表示为p-next-next *若若p-data=ai,则则p-next-data=ai+1pab指针
42、p后移，p=p-nextp-next *1.1.初始化线性表初始化线性表L L InitListInitList(L)(L)2.2.清空线性表清空线性表L L ClearListClearList(L)(L)3.3.求线性表求线性表L L的长度的长度 ListLengthListLength(L)(L)4.4.判断线性表判断线性表L L是否为空是否为空 IsEmptyIsEmpty(L)(L)5.5.获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElemGetElem(L,i,eL,i,e)6.6.检索值为检索值为e e的数据元素的数据元素 LocateELemLo
43、cateELem(L,eL,e)7.7.在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsertListInsert(L,i,eL,i,e)8.8.删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDeleteListDelete(L,i,eL,i,e)2.3.2 2.3.2 单链表基本操作的实现单链表基本操作的实现 *1.1.初始化初始化(构造一个空表构造一个空表)【算法思想算法思想】（1）生成新结点作头结点，用头指针）生成新结点作头结点，用头指针head指向头结点。指向头结点。（2）头结点的指针域置空。）头结点的指针域置空。【算法描述算法描述】S
44、tatusInitList_L(LinkList*L)L-head=(LinkList)malloc(sizeof(LNode);if(L-head)L-head-next=NULL;reurnOK;returnERROE;*2.2.判断表是否为空判断表是否为空StatusListEmpty(LinkListL)/若若L L为空表，则返回为空表，则返回TURETURE，否则返回，否则返回FALSEFALSE Statusflag=FALSE;/flag初值状态为初值状态为FALSEif(L-head-next=NULL)/空空 flag=TRUE;returnflag;*3.3.求表长求表长i
45、ntListLength_L(LinkListL)/返回返回L L中数据元素个数中数据元素个数inti=0;p=L.head;while(p-next!=NULL)/遍历单链表遍历单链表,统计结点数统计结点数i+;p=p-next;returni;*4.4.清空清空VoidClearList(LinkList*L)/将将L L重置为空表重置为空表 Lnode*p;while(L-head-next)/没到表尾没到表尾 p=L-head-next;/p/p指向头结点后的第一个结点指向头结点后的第一个结点L-head-next=p-next；/删除删除P P结点结点free(p);/释放释放p p
46、结点占据的存储空间结点占据的存储空间 *按序号查找按序号查找按值查找按值查找查找查找 *思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构按序号查找按序号查找 *heada2pa3a1j=1i=3j=2j=3e=p-dataWhile(p!=Null&jnext;j+;查找第查找第i i个元素个元素判断的条件判断的条件执行语句执行语句指
47、针指针p后移，计数器后移，计数器j加加1 *从第从第1 1个结点（个结点（L L.head-next-next）顺链扫描，用指针）顺链扫描，用指针p p指向当前扫描到的结点，指向当前扫描到的结点，p p初值初值p p=L L.head-next-next。用用j j做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，j j初值为初值为1 1。当当p p指向扫描到的下一结点时，计数器指向扫描到的下一结点时，计数器j j加加1 1。当当j j=i i时，时，p p所指的结点就是要找的第所指的结点就是要找的第i i个结点。个结点。【算法思想算法思想】按序号查找按序号查找 *5.5.获
48、取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容StatusGetElem_L(LinkListL,inti,ElemType&e)p=L.head-next;j=1;/p指向第一个结点，初始化指向第一个结点，初始化while(p&jnext;j+;if(!p|ji)returnERROR;/第第i个元素不存在个元素不存在e=p-data;/取第取第i个元素个元素returnOK;/GetElem_L 按序号查找按序号查找【算法描述算法描述】*headbpeaWhile(p!=Null&p-data!=e)按值按值(e)查找查找判断的条件判断的条件执行语句执行语句p=p-n
49、ext;指针指针p后移后移 *从第一个结点起，数据域依次和从第一个结点起，数据域依次和e e相比较。相比较。如如果果找找到到一一个个其其值值与与e e相相等等的的数数据据元元素素，则则返返回回其其在链表中的在链表中的“位置位置”；如如果果查查遍遍整整个个链链表表都都没没有有找找到到其其值值和和e e相相等等的的元元素素，则返回则返回“NULLNULL”。【算法思想算法思想】按值查找按值查找 *6.6.在线性表在线性表L L中查找值为中查找值为e e的数据元素的数据元素LNode*LocateELem_L(LinkListL，Elemtypee)p=L.head-next;while(p&p-d
50、ata!=e)p=p-next;return(p);/返回返回L中值为中值为e的数据元素的位置，查找失败返回的数据元素的位置，查找失败返回NULL 按值查找按值查找【算法描述算法描述】While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n *插入插入（第（第 i i 个结点之前）个结点之前）ai-1ai-1aixaip插入前插入前插入后插入后将值为将值为x x的新结点插入到表的第的新结点插入到表的第i i个结点的位置上，个结点的位置上，即插入到即插入到a ai-1i-1与与a ai i之间之间插入新插入新结点点S后，后，a ai-1i-1和和a ai i之之间关系关系发生生变化