线性表-PPT课件.ppt

1、 3:39 第二章第二章 线性表线性表 3:39 第第2 2章章 线性表线性表 第第3 3章章 栈和队列栈和队列 第第4 4章章 串、数组和广串、数组和广义表义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a a1 1 , a, a2 2 , , , a, an n） （逻辑、存储（逻辑、存储和运算）和运算） 3:39 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，

2、其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱和一个直接后继。个直接后继。线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的 3:39 第第2 2章章线性表线性表1. 了解线性结构的特点了解线性结构的特点2.2.掌握顺序表的定义、查找、插入和删除掌握顺序表的定义、查找、插入和删除 3.3.掌握链表的定义、查找、插入和删除掌握链表的定义、查找、插入和删除 4.4.能够从时间

3、和空间复杂度的角度比较两种能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合存储结构的不同特点及其适用场合 教学目标教学目标 3:39 2.1 线性表的类型定义线性表的类型定义2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 线性表的应用线性表的应用教学内容教学内容 3:39 L=（a1, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：由由n（n=0）个类型相同的数）个类型相同的数据元素组成的有限序列据元素组成的有限序列n=0n=0时称为时称为数据元素数据元素线性起点线性起点a ai i的

4、直接前趋的直接前趋a ai i的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点2.1 2.1 线性表的类型定义线性表的类型定义 3:39 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级041810205041810205于春梅于春梅女女 18 180404级计算机级计算机1 1班班041810260041810260何仕鹏何仕鹏男男 20 200404级计算机级计算机2 2班班041810284041810284王王 爽爽女女 19 19040

5、4级计算机级计算机3 3班班041810360041810360王亚武王亚武男男 18 180404级计算机级计算机4 4班班： ：数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性1:11:1 3:39 （6，17，28，50，92，188） 数据元素都是字符数据元素都是字符; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性数据元素都是数字数据元素都是数字; 元素间关系是线性元素间关系是

6、线性（2，3，4，J，Q，K，A）线线性表性表特点特点：在数据元素的非空有限集中：在数据元素的非空有限集中 存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素 存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元素的数据元素 除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一个只有一个直接前驱直接前驱 除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有一只有一个直接后继个直接后继相邻结点间的关系相邻结点间的关系 3:39 线性表的基本操作线性表的基本操作1.1. 初始化线性表初始化线性表L InitLi

7、st(L)L InitList(L)构造一个空的线性表构造一个空的线性表L L，即表的初始化。，即表的初始化。 2.2. 销毁线性表销毁线性表L DestoryList(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

8、 L是否为空是否为空 IsEmpty(L) IsEmpty(L) 判断判断L L是否为空表，是返回是否为空表，是返回true,true,否返回否返回falsefalse6.6. 获取线性表获取线性表L L中的某个数据元素内容中的某个数据元素内容 GetElem(L,i,&e)GetElem(L,i,&e)将将L L中第中第i i个数据元素的值返回到变量个数据元素的值返回到变量e e中中 3:39 7.7. 检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e)LocateELem(L,e)判断线性表判断线性表L L中是否存在值为中是否存在值为e e的结点的结点 8.8. 在

9、线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(&L,i,e)ListInsert(&L,i,e)向线性表向线性表L L的第的第i i个位置之个位置之前前插入一个值为插入一个值为e e的数据元素的数据元素9.9. 删除线性表删除线性表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)Prior

10、Elem(L,cur_e,&pri_e)返回返回L L中当前数据元素中当前数据元素cur_ecur_e的前驱结点的前驱结点11.11.返回后继结点返回后继结点NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)返回返回L L中当前数据元素中当前数据元素cur_ecur_e的的后继结点的的后继结点 3:39 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻顺序存储方法：顺序存储方法：用

11、用一组地址连续一组地址连续的存储单元依次存储的存储单元依次存储线性表的元素，可通过线性表的元素，可通过数组数组VnVn来实现。来实现。顺序存储定义：顺序存储定义：把逻辑上相邻的数据元素存储在物理把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。上相邻的存储单元中的存储结构。 3:39 Loc(元素元素i)=Loc(元素元素1)+（i-1)*m元素元素n n.元素元素i i.元素元素2 2元素元素1 1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储地址存储内容存储内容顺序存储顺序存储假设每个假设每个元素所占元素所占存储单元存储单元个数为个数为mm起始地址起始地址L

12、Lo o顺序表： 定义：用一组地址连续的存储单元存放一个线性表定义：用一组地址连续的存储单元存放一个线性表 元素地址计算方法：元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*m / 任意两个相邻元素间地址相差任意两个相邻元素间地址相差m LOC(ai+1)=LOC(ai)+m 特点：特点： 实现实现逻辑上相邻逻辑上相邻物理地址相邻物理地址相邻 实现实现随机存取随机存取起始地址，基地址起始地址，基地址第第i个元素的地址个元素的地址 每一个数据元素的存储位置都和线性表的起每一个数据元素的存储位置都和线性表的起始位置相差一个始位置相差一个和数据元素在线性表中的位序和数据元素在线性表中的

13、位序成正比的成正比的常数常数，因此只要确定了起始位置，线，因此只要确定了起始位置，线性表中任一数据元素都可性表中任一数据元素都可随机存取随机存取。 顺序表可以随机存取，高级程序设计语言中顺序表可以随机存取，高级程序设计语言中的数组也有随机存取的特性。的数组也有随机存取的特性。实现：实现：可用可用C语言的一维数组实现语言的一维数组实现 3:39 #define MAXSIZE 100 /#define MAXSIZE 100 /预定义最大长度预定义最大长度typedef struct typedef struct ElemType ElemMAXSIZE; / ElemType ElemMAXS

14、IZE; /指向数据元素的基地址指向数据元素的基地址 int length; /int length; /线性表的当前长度线性表的当前长度 SqListSqList；顺序表的类型定义顺序表的类型定义线性表基本运算操作有：线性表基本运算操作有：查找、插入、删除查找、插入、删除由于线性表的长度是可变的，所需的存储空间不同，由于线性表的长度是可变的，所需的存储空间不同，所以在所以在C语言中，可用语言中，可用动态分配的一维数组动态分配的一维数组来描述。来描述。 3:39 a1a2anbb+lb+（n-1）l12n内存存储地址元素序号b+(maxlen-1)l备用空间#define LIST_INIT_

15、SIZE 100#define LISTINCREMENT 10Typedef struct ElemType * elem; int length;SqList;数据元素不是简单类型时,可定义结构体数组动态申请内存L.elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);线性表存储空间初始分配量线性表存储空间初始分配量线性表存储空间分配增量线性表存储空间分配增量存储空间基址存储空间基址预定义 3:39 malloc(malloc(m m) )：开辟：开辟m m字节长度的地址空间，字节长度的地址空间，并返回这段空间的首地址并返回这段空

16、间的首地址sizeof(sizeof(x x) )：计算变量：计算变量x x的长度的长度free(free(p p) )：释放指针：释放指针p p所指变量的存储空间所指变量的存储空间，即彻底删除一个变量，即彻底删除一个变量补充：补充：C C语言的动态分配函数（语言的动态分配函数（ ） 3:39 线性表的基本操作线性表的基本操作1. 1. 初始化线性表初始化线性表L InitList(L) L InitList(L) 2. 2. 销毁线性表销毁线性表L DestoryList(L) L DestoryList(L) 3. 3. 清空线性表清空线性表L ClearList(L) L ClearLi

17、st(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,i,e) 7. 7. 检索值为检索值为e e的数据元素的数据元素 LocateELem(L,e) LocateELem(L,e) 8. 8. 在线性表在线性表L L中插入一个数据元素中插入一个数据元素 ListInsert(L,i,e)ListInsert(

18、L,i,e)9. 9. 删除线性表删除线性表L L中第中第i i个数据元素个数据元素 ListDelete(L,i,e)ListDelete(L,i,e) 3:39 典型操作的算法实现典型操作的算法实现1.1. 初始化线性表初始化线性表L L （参数用引用）（参数用引用）Status InitList_Sq(SqList &L) /构造一个空的顺序表构造一个空的顺序表L L.elem= (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); /为顺序表分配空间为顺序表分配空间 if(!L.elem) exit(OVERFLOW); /存储分配失败存

19、储分配失败 L.length=0; /空表长度为空表长度为0 return OK; 3:39 2. 2. 销毁线性表销毁线性表L Lvoid DestroyList(SqList &L)void DestroyList(SqList &L) if (L.elem) free(L.elem); / if (L.elem) free(L.elem); /释放存储空间释放存储空间 return OK; return OK; 3. 3. 清空线性表清空线性表L Lvoid ClearList(SqList &L) L.length=0; /将线性表的长度置为将线性表的长度置为0 3:39 4.4. 求

20、线性表求线性表L L的长度的长度int GetLength(SqList L) return (L.length); 5.5.判断线性表判断线性表L L是否为空是否为空int IsEmpty(SqList L) if (L.length=0) return 1; else return 0; 3:39 按序号查找（位置）按序号查找（位置） 按值查找按值查找查找查找 3:39 251247893614123456789L.elem0e=L.elem3 /取第取第4个元素赋给变量个元素赋给变量e查找第查找第 i i 个元素（假设个元素（假设i i=4=4）序号若下标从0开始L.elem1L.ele

21、m2L.elem3 3:39 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) return ERROR; / /判断判断i i值是否合理，若不合理，返回值是否合理，若不合理，返回ERRORERROR e=L.elemi-1;e=L

22、.elemi-1; / /第第i-1i-1的单元存储着第的单元存储着第i i个数据个数据 return OK;return OK; 3:39 查找元素查找元素e e（根据指定数据查找，返回其所在的位置）（根据指定数据查找，返回其所在的位置）25 34 57 16 48 09 0 1 2 3 4 5 data查找查找 16 i25 34 57 16 48 09 i25 34 57 16 48 09 i25 34 57 16 48 09 i查找成功查找成功 3:39 25 34 57 16 48 0 1 2 3 4data查找 50i25 34 57 16 48 i25 34 57 16 48 i

23、25 34 57 16 48 i25 34 57 16 48 i查找失败查找失败 3:39 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; 3:39 2512478936141234567892512479989361499插入插入25124789361425124789361425124

24、7893614插第插第 4 4 个结点之前，移动个结点之前，移动 6 64+14+1 次次插在第插在第 i i 个结点之前，移动个结点之前，移动 n-i+1n-i+1 次次插入插入（插在第（插在第 i i 个结点之前）先看个结点之前）先看i i=4=4依次赋值 3:39 （1 1）判断）判断插入位置插入位置i i 是否合法是否合法。（2 2）判断顺序表的）判断顺序表的存储空间是否已满存储空间是否已满。 （3 3）将第）将第n n至第至第i i 位的元素依次位的元素依次向后移动一个位置向后移动一个位置，空，空出第出第i i个位置。个位置。（4 4）将要插入的新元素）将要插入的新元素e e放入第放

25、入第i i个位置个位置。（5 5）表长加表长加1 1，插入成功返回，插入成功返回OKOK。【算法思想算法思想】 3:39 8. 8. 在线性表在线性表L L中第中第i i个数据元素之前插入数据元素个数据元素之前插入数据元素e e Status ListInsert_Sq(SqList &L,int i ,ElemType e) if(iL.length+1) return ERROR; /i值不合法值不合法 if(L.length=MAXSIZE) return ERROR; /当前存储空间已满当前存储空间已满 for( j=L.length-1; j=i-1; j -) L.elemj+1=

26、L.elemj; /插入位置及之后的元素后移插入位置及之后的元素后移 L.elemi-1=e; /将新元素将新元素e放入第放入第i个位置个位置 +L.length; /表长增表长增1 return OK;【算法描述算法描述】 3:39 若插入在尾结点之后，则根本无需移动（特别快）；若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部后移（特别慢）；若插入在首结点之前，则表中元素全部后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1n+1种可能）的平均移动次种可能）的平均移动次数，该如何计算？数，该如何计算？ 算法时间复杂度T(n)设Pi是在第

27、i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为假设在线性表的任何位置上插入、删除元素都是等概率的，则 3:39 251247893614123456789251247361425124736142512473614删除删除删除删除（删除第（删除第 i i 个结点）先看个结点）先看i i=4=4删除第删除第 4 4 个结点，移动个结点，移动 6 64 4 次次删除第删除第 i i 个结点，移动个结点，移动 n-in-i 次次 3:39 （1 1）判断）

28、判断删除位置删除位置i i 是否合法是否合法（合法值为（合法值为1in1in）。）。（2 2）将欲删除的元素保留在）将欲删除的元素保留在e e中。中。 （3 3）将第）将第i+1i+1至第至第n n 位的元素依次位的元素依次向前移动一个位置向前移动一个位置。（4 4）表长减表长减1 1，删除成功返回，删除成功返回OKOK。【算法思想算法思想】 3:39 9. 9. 将线性表将线性表L L中第中第i i个数据元素删除个数据元素删除Status ListDelete_Sq(SqList &L, int i, ElemType &e) if(iL.length) return ERROR; /i值不

29、合法值不合法 e=L.elemi-1; /将欲删除的元素保留在将欲删除的元素保留在e中中 for (j=i;j=L.length-1;j+) L.elemj-1=L.elemj; /被删除元素之后的元素前移被删除元素之后的元素前移 -L.length; /表长减表长减1 return OK;【算法描述算法描述】 3:39 若删除尾结点，则根本无需移动（特别快）；若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中若删除首结点，则表中n-1n-1个元素全部前移（特别慢）；个元素全部前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n n种可能）的平均移动次数，种可能）的

30、平均移动次数，该如何计算？该如何计算？【算法分析算法分析】算法时间主要耗费在移动元素的操作上算法时间主要耗费在移动元素的操作上 算法评价 设设Qi是删除第是删除第i个元素的概率，则在长度为个元素的概率，则在长度为n的线性的线性表中删除一个元素所需移动的元素次数的平均次数表中删除一个元素所需移动的元素次数的平均次数为：为：niideinQE1)( nOnTninnEnQnidei121)(11则若认为 3:39 查找、插入、删除算法的平均查找、插入、删除算法的平均时间时间复杂度为复杂度为O(n)O(n)故在故在顺序表中插入或删除顺序表中插入或删除一个元素时，平一个元素时，平均移动表的一半元素，当

31、均移动表的一半元素，当n n很大时，很大时，效率效率很低很低例：已知顺序表例：已知顺序表La和和Lb的数据元素按值的数据元素按值非递减排列，归并非递减排列，归并La和和Lb得到新的顺序得到新的顺序表表Lc，Lc的元素也按值非递减排列的元素也按值非递减排列Ch2_3.c合并有序顺序表合并有序顺序表算法思想：算法思想： 基本操作是基本操作是“复制复制”，设，设2 2个下标个下标i i和和j j，分别，分别指向指向2 2个表当前处理的元素，比较它们的值，当个表当前处理的元素，比较它们的值，当i i所指向的值不大于所指向的值不大于j j所指向的值时，复制所指向的值时，复制i i所指元所指元素到素到Lc

32、Lc中，否则复制中，否则复制j j所指元素到所指元素到LcLc中。中。 反复进行上述操作，直到反复进行上述操作，直到LALA或或LBLB结束之后，结束之后，再把尚未结束的再把尚未结束的LBLB或或LALA的剩余各元素依次复制到的剩余各元素依次复制到LCLC中中 。 3:39 void Mergelist(SqList La, SqList Lb, SqList &Lc)void Mergelist(SqList La, SqList Lb, SqList &Lc) InitList (Lc); InitList (Lc); n=ListLength(La); m=ListLength(Lb);

33、 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个元素，放到个元素，放到ai ai中中 GetElem(Lb,j,&bj); GetElem(Lb,j,&bj); if (ai=bj) if (ai=bj) ListInsert_Lc(Lc,k+,ai); i

34、+; ListInsert_Lc(Lc,k+,ai); i+; /LA/LA的当前项较小，将它复制到的当前项较小，将它复制到LCLC中中 3:39 3:39 elseelse ListInsert_Lc( Lc,k+,bj ); j+; ListInsert_Lc( Lc,k+,bj ); j+; /LB/LB的当前项较小，将它复制到的当前项较小，将它复制到LCLC中中 while (in)while (in) /LA /LA还有剩余还有剩余GetElem(La,i+, ai); GetElem(La,i+, ai); ListInsert_Lc(Lc,k+,ai); ListInsert_L

35、c(Lc,k+,ai); / /将将LALA的剩余各元素依次复制到的剩余各元素依次复制到LCLC中中 while (jm)while (jnext=NULLhead-next=NULL 3:39 讨论讨论2 2. . 在链表中设置在链表中设置头结点头结点有什么好处？有什么好处？便于便于首元结点首元结点( (第一个结点第一个结点) )的处理的处理首元结点的地址保存在头结点的指针域中首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理一致，无须进行特殊处理;便于便于空表和非空表空表和非空表的统一处理的统一处理无

36、论链表是否为空，头指针都是指向头结无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就点的非空指针，因此空表和非空表的处理也就统一了。统一了。 3:39 讨论讨论3. 3. 头结点的头结点的数据域数据域内装的是什么？内装的是什么？ 头结点的头结点的数据域数据域可以为空，也可存放线性表可以为空，也可存放线性表长度长度等附加信息，但此结点不能计入链表长度值。等附加信息，但此结点不能计入链表长度值。头结点的数据域头结点的数据域H H 3:39 （1 1）结点在存储器中的位置是结点在存储器中的位置是任意任意的，即的，即逻辑上逻辑上相邻的数据元素在物理上不一定相邻相邻的数据元素在

37、物理上不一定相邻链表（链式存储结构）的特点链表（链式存储结构）的特点（2 2）单链表中，任何两个元素的存储位置之间没单链表中，任何两个元素的存储位置之间没有固定的联系，每个元素的存储位置都包含在其有固定的联系，每个元素的存储位置都包含在其直接前驱结点的信息中。直接前驱结点的信息中。（3）访问时只能通过头指针进入链表，并通过每）访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点个结点的指针域向后扫描其余结点(顺藤摸瓜顺藤摸瓜)，所以寻找第一个结点和最后一个结点所花费的时所以寻找第一个结点和最后一个结点所花费的时间不等间不等这种存取元素的方法被称为这种存取元素的方法被称为顺序存取

38、法顺序存取法 3:39 优点优点数据元素的个数可以自由扩充数据元素的个数可以自由扩充 插入、删除等操作不必移动数据，只需插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高修改链接指针，修改效率较高链表的优缺点链表的优缺点 3:39 缺点缺点存储密度小存储密度小存取效率不高，必须采用存取效率不高，必须采用顺序存取顺序存取，即存，即存取数据元素时，只能按链表的顺序进行访问取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）（顺藤摸瓜）链表的优缺点链表的优缺点 3:39 练习练习1.1.链表的每个结点中都恰好包含一个指针。链表的每个结点中都恰好包含一个指针。 2.2.顺序表结构适宜于进行顺序

39、存取，而链表顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。适宜于进行随机存取。3.3.顺序存储方式的优点是存储密度大，且插顺序存储方式的优点是存储密度大，且插入、删除运算效率高。入、删除运算效率高。4.4.线性表若采用链式存储时，结点之间和结线性表若采用链式存储时，结点之间和结点内部的存储空间都是可以不连续的。点内部的存储空间都是可以不连续的。 5.5.线性表的每个结点只能是一个简单类型，线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型而链表的每个结点可以是一个复杂类型 3:39 2.3.1 2.3.1 单链表的定义和实现单链表的定义和实现a1a2an.LL非空

40、表非空表空表空表单链表是由表头唯一确定，因此单链表可单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名以用头指针的名字来命名若头指针名是若头指针名是L，则把链表称为表，则把链表称为表L 3:39 typedef struct LNodetypedef struct LNode ElemType data; ElemType data; /数据域数据域 struct LNode struct LNode * *next; next; /指针域指针域LNode,LNode,* *LinkList; LinkList; / / * *LinkListLinkList为为LnodeLnode类

41、型的指针类型的指针单链表的存储结构定义单链表的存储结构定义LNode *pLinkList p 3:39 LNode *p注意区分指针变量和结点变量两个不同的概念注意区分指针变量和结点变量两个不同的概念指针变量指针变量p p：表示结点地址：表示结点地址结点变量结点变量* *p p：表示一个结点：表示一个结点注意：注意：LinkList和和LNode *是不同名字的同一个指针是不同名字的同一个指针类型，类型，LinkList类型的指针变量类型的指针变量head表示它是单链表示它是单链表的头指针表的头指针,LNode *类型的指针变量类型的指针变量p表示它是指向表示它是指向某一结点的指针。某一结点

42、的指针。typedef 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 3:39 a1a2an.L若若p-dat

43、a=ai, 则则p-next-data=ai+1 pab指针p后移，p=p-nextp-next 3:39 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(

44、 (L,i,eL,i,e) ) 6. 6. 检索值为检索值为e e的数据元素的数据元素 LocateELemLocateELem( (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 单链表基本操作的实现单链表基本操作的实现 3:39 1.1.初始化初始化( (构造一个空表构造一个空表 )【算法思想算法思想】（1）

45、生成新结点作头结点，用头指针）生成新结点作头结点，用头指针head指向头结点。指向头结点。（2）头结点的指针域置空。）头结点的指针域置空。【算法描述算法描述】Status InitList_L(LinkList *L) L-head=(LinkList)malloc(sizeof( LNode); if(L-head) L-head-next=NULL; reurn OK;return ERROE; 3:39 2. 2. 判断表是否为空判断表是否为空Status ListEmpty(LinkList L) / / /若若L L为空表，则返回为空表，则返回TURETURE，否则返回，否则返回FA

46、LSEFALSE Status flag=FALSE; /flag初值状态为初值状态为FALSE if(L-head-next=NULL) / / /空空 flag=TRUE; return flag; 3:39 3.3.求表长求表长int ListLength_L(LinkList L)/返回返回L L中数据元素个数中数据元素个数 int i=0; p=L.head; while(p-next!=NULL) /遍历单链表遍历单链表, ,统计结点数统计结点数 i+; p=p-next; return i; 3:39 4.4.清空清空Void ClearList(LinkList * * L)

47、/ / 将将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结点占据的存储空间结点占据的存储空间 3:39 按序号查找按序号查找 按值查找按值查找查找查找 3:39 思考：顺序表里如何找到第思考：顺序表里如何找到第i i个元素？个元素？ 链表的查找：要从链表的头指针出发，链表的查找：要从链表的头指针出发，顺着链域顺着链域nextnext逐个结点往下搜索，

48、直至逐个结点往下搜索，直至搜索到第搜索到第i i个结点为止。因此，链表不是个结点为止。因此，链表不是随机存取结构随机存取结构按序号查找按序号查找 3:39 heada2pa3a1j=1i=3j=2j=3e=p-dataWhile ( p!=Null & jnext; j+; 查找第查找第i i个元素个元素判断的条件判断的条件执行语句执行语句指针指针p后移，计数器后移，计数器j加加1 3:39 从第从第1 1个结点（个结点（L L.head-next-next）顺链扫描，用指针）顺链扫描，用指针p p指向当前扫描到的结点，指向当前扫描到的结点，p p初值初值p p = = L L.head-ne

49、xt-next。用用j j做计数器，累计当前扫描过的结点数，做计数器，累计当前扫描过的结点数，j j初值为初值为1 1。当当p p指向扫描到的下一结点时，计数器指向扫描到的下一结点时，计数器j j加加1 1。当当j j= = i i时，时，p p所指的结点就是要找的第所指的结点就是要找的第i i个结点。个结点。【算法思想算法思想】按序号查找按序号查找 3:39 5.5.获取线性表获取线性表L L中的某个数据元素的内容中的某个数据元素的内容Status GetElem_L(LinkList L, int i, ElemType &e) p=L.head-next; j=1; /p指向第一个结点，

50、初始化指向第一个结点，初始化 while(p & jnext; j+; if(!p | ji)return ERROR; /第第i个元素不存在个元素不存在 e=p-data; /取第取第i个元素个元素 return OK; /GetElem_L 按序号查找按序号查找【算法描述算法描述】 3:39 headbpeaWhile (p!=Null & p-data!=e)按值按值(e)查找查找判断的条件判断的条件执行语句执行语句p=p-next; 指针指针p后移后移 3:39 从第一个结点起，数据域依次和从第一个结点起，数据域依次和e e相比较。相比较。如果找到一个其值与如果找到一个其值与e e相等