最新【考研计算机专业课】武汉大学数据结构PPT课件 第2章线性表(共144张PPT课件).pptx

《最新【考研计算机专业课】武汉大学数据结构PPT课件 第2章线性表(共144张PPT课件).pptx》由会员分享，可在线阅读，更多相关《最新【考研计算机专业课】武汉大学数据结构PPT课件 第2章线性表(共144张PPT课件).pptx（144页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 线性表线性表 2.1 线性表的基本概念线性表的基本概念 2.2 线性表的顺序存储线性表的顺序存储2.3 线性表的链式存储线性表的链式存储(cn ch)2.4 线性表的应用线性表的应用(yngyng) 2.5 有序表有序表 第一页，共一百四十四页。2.1.1 线性表的定义线性表的定义 线性表是具有线性表是具有相同特性的数据元素相同特性的数据元素(yun s)的一个的一个有限有限序列序列。 该序列中所含元素的个数叫做线性表的长度，用该序列中所含元素的个数叫做线性表的长度，用n表示，表示，n0。 当当n=0时，表示线性表是一个空表，即表中不包含任何元素。时，表示线性表是一个空表，即表中不

2、包含任何元素。设序列中第设序列中第i（i表示表示逻辑位序逻辑位序）个元素为）个元素为ai（1in）。）。 线性表的一般表示为：线性表的一般表示为： (a1，a2，ai，ai+1，an)逻辑逻辑(lu j)结构结构2.1 线性表的基本概念线性表的基本概念 第二页，共一百四十四页。 其中其中a1为第一个元素，又称做表头元素，为第一个元素，又称做表头元素，a2为第二个元素，为第二个元素，an为最后一个为最后一个(y )元素，又称做表尾元素。元素，又称做表尾元素。 例如，在线性表例如，在线性表 (1，4，3，2，8，10)中，中，1为表头元素，为表头元素，10为表尾元素。为表尾元素。第三页，共一百四十

3、四页。2.1.2 线性表的运算线性表的运算 线性表的基本运算如下：线性表的基本运算如下： （1）初始化线性表）初始化线性表InitList(&L)：构造一个空的线性表：构造一个空的线性表L。 （2）销毁）销毁(xiohu)线性表线性表DestroyList(&L)：释放线性表：释放线性表L占用的内存空间。占用的内存空间。逻辑逻辑(lu j)结构抽象运算结构抽象运算ADT第四页，共一百四十四页。 （3）判线性表是否为空表）判线性表是否为空表ListEmpty(L)：若：若L为空表，则返为空表，则返回真，否则返回假。回真，否则返回假。 （4）求线性表的长度）求线性表的长度ListLength(L)

4、：返回：返回L中元素个数。中元素个数。 （5）输出线性表）输出线性表DispList(L)：当线性表：当线性表L不为空时，顺序显示不为空时，顺序显示L中各结点的值域。中各结点的值域。 （ 6 ） 求 线 性 表） 求 线 性 表 L 中 指 定 位 置 的 某 个中 指 定 位 置 的 某 个( m u )数 据 元 素数 据 元 素GetElem(L,i,&e)：用：用e返回返回L中第中第 i(1iListLength(L)个元素的值。个元素的值。第五页，共一百四十四页。 （7）定位查找）定位查找LocateElem(L,e)：返回：返回(fnhu)L中第中第1个值域与个值域与e相等的位序。

5、若这样的元素不存在，则返回相等的位序。若这样的元素不存在，则返回(fnhu)值为值为0。 （ 8 ） 插 入 数 据 元 素） 插 入 数 据 元 素 L i s t I n s e r t ( & L , i , e ) ： 在： 在 L 的 第的 第i(1iListLength(L)+1)个元素之前插入新的元素个元素之前插入新的元素e，L的长度增的长度增1。 （9）删除数据元素）删除数据元素ListDelete(&L,i,&e)：删除：删除L的第的第i(1iListLength(L)个元素，并用个元素，并用e返回其值，返回其值，L的长度减的长度减1。第六页，共一百四十四页。2.2.1 线性

6、表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是：线性表的顺序存储结构就是：把线性表中的所有元素按照其把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续块连续(linx)的存储空间中。的存储空间中。 这样，线性表中第一个元素的存储位置就是指定的存储位置，这样，线性表中第一个元素的存储位置就是指定的存储位置，第第i+1个元素（个元素（1in-1）的存储）的存储位置紧接在第位置紧接在第i i个元素的存储位个元素的存储位置的后面。置的后面。线性表线性表 逻辑逻辑(lu j)(lu j)结构结构

7、顺序顺序表表 存储结构存储结构区别区别(qbi)2.2 线性表的顺序存储线性表的顺序存储第七页，共一百四十四页。 假定线性表的元素假定线性表的元素(yun s)类型为类型为ElemType，则每个元素，则每个元素(yun s)所占所占用存储空间大小（即字节数）为用存储空间大小（即字节数）为sizeof(ElemType)，整个线性表所占用，整个线性表所占用存储空间的大小为：存储空间的大小为： n*sizeof(ElemType)其中，其中，n表示线性表的长度。表示线性表的长度。第八页，共一百四十四页。 a a1 1 LOC(A) 0 a a2 2 LOC(A)+sizeof(ElemType)

8、 1 线性表存储空间线性表存储空间 存储地址存储地址 下标位置下标位置 a ai i LOC(A)+(i-1)*sizeof(ElemType) i-1 a an n LOC(A)+(n-1)*sizeof(ElemType) n-1 LOC(A)+(MaxSize-1)*sizeof(ElemType) MaxSize-1 顺序顺序(shnx)(shnx)表示表示意图意图第九页，共一百四十四页。 在定义在定义(dngy)一个线性表的顺序存储类型时，需要定义一个线性表的顺序存储类型时，需要定义(dngy)一个数一个数组来存储线线表中的所有元素组来存储线线表中的所有元素和定义和定义一个整型变量来

9、存储线性表一个整型变量来存储线性表的长度的长度。 假定数组用假定数组用dataMaxSize表示，长度整型变量用表示，长度整型变量用length表示，表示，并采用结构体类型表示，则元素类型为通用类型标识符并采用结构体类型表示，则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下的线性表的顺序存储类型可描述如下：第十页，共一百四十四页。 typedef struct ElemType dataMaxSize; int length; SqList; /顺序顺序(shnx)表类型表类型 其中，其中，data成员存放元素，成员存放元素，length成员存放线性表的实际长度。成员

10、存放线性表的实际长度。 说明：由于说明：由于C/C+中数组的下标从中数组的下标从0开始，线性表的第开始，线性表的第i个元个元素素ai存放顺序存放顺序(shnx)表的第表的第i-1位置上。为了清楚，将位置上。为了清楚，将ai在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理物理位序位序。第十一页，共一百四十四页。地址地址城市名城市名区号区号说明说明100Beijing010首都首都130Shanghai021直辖市直辖市160Wuhan027湖北省省会湖北省省会190Xian029陕西省省会陕西省省会210Nanjing025江苏省省会江

11、苏省省会 对于第对于第1章的逻辑结构章的逻辑结构City，假定每个元素占用，假定每个元素占用30个存储单元个存储单元(dnyun)，数据从，数据从100号单元号单元(dnyun)开始由低地址向高地址方向存储，开始由低地址向高地址方向存储，对应的顺序表如下：对应的顺序表如下： 第十二页，共一百四十四页。2.2.2 顺序表基本顺序表基本(jbn)运算的实现运算的实现 一旦采用顺序表存储结构，可以用一旦采用顺序表存储结构，可以用C/C+语言语言(yyn)实现实现线性表的各种基本运算。为了方便，假设线性表的各种基本运算。为了方便，假设ElemType为为char类型，使用如下自定义类型语句：类型，使用

12、如下自定义类型语句： typedef char ElemType;第十三页，共一百四十四页。1. 建立顺序表建立顺序表其方法其方法(fngf)是将给定的含有是将给定的含有n个元素的数组的每个元素依次放入到顺个元素的数组的每个元素依次放入到顺序表中，并将序表中，并将n赋给顺序表的长度成员。算法如下：赋给顺序表的长度成员。算法如下： void CreateList(SqList *&L,ElemType a,int n) /建立顺序表建立顺序表 int i; L=(SqList *)malloc(sizeof(SqList); for (i=0;idatai=ai; L-length=n; 由给定

13、的由给定的CC+数组建立数组建立(jinl)顺序表。顺序表。第十四页，共一百四十四页。2. 顺序表基本运算算法顺序表基本运算算法 （1） 初始化线性表初始化线性表InitList(L) 该运算的结果是构造该运算的结果是构造(guzo)一个空的线性表一个空的线性表L。实际上只需将。实际上只需将length成员设置为成员设置为0即可。即可。 void InitList(SqList *&L) /引用型指针引用型指针 L=(SqList *)malloc(sizeof(SqList); /分配存放线性表的空间分配存放线性表的空间 L-length=0; 本算法的时间复杂度为本算法的时间复杂度为O(1

14、)。顺序顺序(shnx)表表LL指针指向一个指针指向一个(y )顺序表顺序表第十五页，共一百四十四页。引用的作用引用的作用(zuyng)(zuyng)： 当不用引用时当不用引用时main() SqList *sq; InitList(sq); op(sq);void InitList (SqList *L) L=(SqList *)malloc(sizeof(SqList)； L-length=0；？sqL0？sqmain：调用调用(dioyng)InitList返回返回(fnhu)到到main：顺序表顺序表第十六页，共一百四十四页。引用的作用引用的作用(zuyng)：当使用引用时：当使用引用

15、时main() SqList *sq; InitList(sq); op(sq);void InitList (SqList *&L) /用引用用引用 L=(SqList *) malloc (sizeof(SqList)； L-length=0；？sqL0sqmain：调用调用(dioyng)InitList返回返回(fnhu)到到main：顺序表顺序表第十七页，共一百四十四页。 （2） 销毁线性表销毁线性表DestroyList(L) 该运算该运算(yn sun)的结果是释放线性表的结果是释放线性表L占用的内存空间。占用的内存空间。 void DestroyList(SqList *&L)

16、 free(L); 本算法的时间复杂度为本算法的时间复杂度为O(1)。 第十八页，共一百四十四页。 思考题：思考题：这里采用顺序这里采用顺序(shnx)指针，而不是直接给定顺指针，而不是直接给定顺序序(shnx)表。两者有什么区别？表。两者有什么区别？例如例如(lr)，如果直接采用顺序表：，如果直接采用顺序表：void InitList(SqList &L) /引用型引用型 L.length=0;第十九页，共一百四十四页。 （3） 判定是否为空表判定是否为空表ListEmpty(L) 该运算该运算(yn sun)返回一个值表示返回一个值表示L是否为空表。若是否为空表。若L为空表，则返回为空表，

17、则返回1，否则返回否则返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的时间复杂度为本算法的时间复杂度为O(1)。第二十页，共一百四十四页。 （4）求线性表的长度）求线性表的长度ListLength(L) 该运算返回该运算返回(fnhu)顺序表顺序表L的长度。实际上只需返回的长度。实际上只需返回(fnhu)length成员的值即可。成员的值即可。 int ListLength(SqList *L) return(L-length); 本算法的时间复杂度为本算法的时间复杂度为O(1)。第二十一页，共一百四十四页。 （5）输出线性表）输出线

18、性表DispList(L) 该运算当线性表该运算当线性表L不为不为(b wi)空时，顺序显示空时，顺序显示L中各元素的值。中各元素的值。 void DispList(SqList *L) int i;if (ListEmpty(L) return;for (i=0;ilength;i+)printf(%c，L-datai);printf(n); 第二十二页，共一百四十四页。 本算法中基本本算法中基本(jbn)运算为运算为for循环中的循环中的printf语句，故时间语句，故时间复杂度为：复杂度为： O(L- -length)或或O(n)（n表示表示L中的元素个数）中的元素个数）第二十三页，共一

19、百四十四页。 （6）求某个）求某个(mu )数据元素值数据元素值GetElem(L,i,e) 该运算返回该运算返回L中第中第 i(1iListLength(L)个元素的值，存放在个元素的值，存放在e中。中。 int GetElem(SqList *L,int i,ElemType &e) if (iL-length) return 0;e=L-datai-1;return 1; 本算法的时间复杂度为本算法的时间复杂度为O(1)。 第二十四页，共一百四十四页。 （7） 按元素值查找按元素值查找LocateElem(L,e) 该运算顺序查找第该运算顺序查找第1个值域与个值域与e相等的元素的位序。若

20、这样相等的元素的位序。若这样(zhyng)的元素不的元素不存在，则返回值为存在，则返回值为0。 int LocateElem(SqList *L,ElemType e) int i=0;while (ilength & L-datai!=e) i+;if (i=L-length) return 0;else return i+1; 第二十五页，共一百四十四页。 本算法中基本运算为本算法中基本运算为while循环中的循环中的i+语句，故时间语句，故时间(shjin)复杂度为：复杂度为： O(L-length)或或O(n) （n表示表示L中的元素个数）中的元素个数）第二十六页，共一百四十四页。 （

21、8） 插入数据元素插入数据元素ListInsert(L,i,e) 该运算在顺序表该运算在顺序表L的第的第i个位置个位置(1iListLength(L)+1)上上插入新的元素插入新的元素e。 思路：如果思路：如果i值不正确，则显示相应错误信息；否则将顺值不正确，则显示相应错误信息；否则将顺序表原来第序表原来第i个元素及以后个元素及以后(yhu)元素均后移一个位置，腾出一元素均后移一个位置，腾出一个空位置插入新元素，顺序表长度增个空位置插入新元素，顺序表长度增1。第二十七页，共一百四十四页。int ListInsert(SqList *&L,int i,ElemType e) int j; if

22、(iL-length+1) return 0; i-; /将顺序表逻辑位序转化为将顺序表逻辑位序转化为data下标即物理位序下标即物理位序 for (j=L-length;ji;j-) /将将datai及后面元素及后面元素(yun s)后移后移 L-dataj=L-dataj-1; L-datai=e; L-length+; /顺序表长度增顺序表长度增1 return 1;a0ai-1aian-1逻辑逻辑(lu j)位序位序1 i i+1 n MaxSize 第二十八页，共一百四十四页。 对于本算法来说，元素移动的次数不仅与表长对于本算法来说，元素移动的次数不仅与表长L.length=n有关，

23、有关，而且与插入位置而且与插入位置i有关：当有关：当i=n+1时，移动次数为时，移动次数为0； 当当i=1时，移动次数为时，移动次数为n，达到最大值。在线性表，达到最大值。在线性表sq中共有中共有n+1个可以插入元素的地方个可以插入元素的地方(dfng)。假设。假设pi（= ）是在第）是在第i个位个位置上插入一个元素的概率，则在长度为置上插入一个元素的概率，则在长度为n的线性表中插入一个元素时的线性表中插入一个元素时所需移动元素的平均次数为：所需移动元素的平均次数为： 因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。11n)(2)1(11)1(1111nOninninni

24、niip an-1ai-1（共（共n-1-(i-1)+1=n-i+1）个）个元素元素(yun s)移动移动第二十九页，共一百四十四页。 （9）删除数据元素）删除数据元素ListDelete(L,i,e) 删除顺序表删除顺序表L中的第中的第i(1iListLength(L)个元素。个元素。 思路：如果思路：如果i值不正确，则显示相应错误信息；否则将线性表值不正确，则显示相应错误信息；否则将线性表第第i个元素以后元素均向前移动个元素以后元素均向前移动(ydng)一个位置，这样覆盖了原来一个位置，这样覆盖了原来的第的第i个元素，达到删除该元素的目的，最后顺序表长度减个元素，达到删除该元素的目的，最后

25、顺序表长度减1。第三十页，共一百四十四页。int ListDelete(SqList *&L,int i,ElemType &e) int j; if (iL-length) return 0; i-; /将逻辑将逻辑(lu j)位序转化为位序转化为data下标即物理位序下标即物理位序 e=L-datai; for (j=i;jlength-1;j+) /将将datai之后的元素后前移之后的元素后前移 L-dataj=L-dataj+1; L-length-;/顺序表长度减顺序表长度减1 return 1;a0ai-1aian-1逻辑逻辑(lu j)位序位序1 i i+1 n MaxSize

26、第三十一页，共一百四十四页。 对于本算法来说，元素移动的次数也与表长对于本算法来说，元素移动的次数也与表长n和删除元素的位和删除元素的位置置i有关：当有关：当i=n时，移动次数为时，移动次数为0； 当当i=1时，移动次数为时，移动次数为n-1。在线性表。在线性表sq中共有中共有n个元素可以被删除。个元素可以被删除。假设假设pi（pi= ）是删除第）是删除第i个位置上元素的概率个位置上元素的概率(gil)，则在长度，则在长度为为n的线性表中删除一个元素时所需移动元素的平均次数为：的线性表中删除一个元素时所需移动元素的平均次数为： = 因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O

27、(n)。)(21)(1)(11nOninninpninii n1aian-1（共（共n-1-i+1=n-i个元素）个元素）均前移一个均前移一个(y )位置位置第三十二页，共一百四十四页。 例例2.2 设计一个算法，将设计一个算法，将x插入到一个有序插入到一个有序(从小到大排序从小到大排序)的线的线性表（顺序存储结构即顺序表）的适当位置上，并保持线性表的性表（顺序存储结构即顺序表）的适当位置上，并保持线性表的有序性。有序性。 解：解：先通过先通过(tnggu)比较在顺序表比较在顺序表L中找到存放中找到存放x的位置的位置i，然后将，然后将x插入插入到到L-L-datai中，最后将顺序表的长度增中，

28、最后将顺序表的长度增1。第三十三页，共一百四十四页。void Insert(SqList *&L,ElemType x) int i=0，j; while (ilength & L-datailength-1;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-length+;查找查找(ch zho)插插入位置入位置元素元素(yun s)后移一个位置后移一个位置a0ai-1aian-1逻辑逻辑(lu j)位序位序1 i i+1 n MaxSize 第三十四页，共一百四十四页。 例例2.3 设计一个算法，将两个元素有序（从小到大）的顺序表合设计一个算法，将两个元素有序

29、（从小到大）的顺序表合并并(hbng)成一个有序顺序表。成一个有序顺序表。 求解思路：求解思路：将两个顺序表进行将两个顺序表进行二路归并二路归并。 第三十五页，共一百四十四页。 1 3 5 2 4 10 20 ij 1 3 5 2 4 10 20 ij1 k 1 3 5 2 4 10 20 ij1 2 k1 2 3 kpqrpqrpqr第三十六页，共一百四十四页。 1 3 5 2 4 10 20 ij1 2 3 4 k 1 3 5 i 2 4 10 20 1 2 3 4 5 kjj 1 3 5 i 2 4 10 20 1 2 3 4 5 k复制(fzh)pqrpqrpqr第三十七页，共一百四十

30、四页。SqList *merge(SqList *p,SqList *q) SqList *r; int i=0，j=0，k=0; r=(SqList *)malloc(sizeof(SqList); while (ilength & jlength) if (p-dataidataj) r- datak=p-datai; i+;k+; else r- datak=q- dataj; j+;k+; 由由p和和q中的元素中的元素(yun s)建立顺序建立顺序表表q第三十八页，共一百四十四页。while (ilength) r-datak=p-datai; i+;k+; while (jlengt

31、h) r-datak=q-dataj; j+;k+; r-length=k; /或或p-length+q-length return(r); 第三十九页，共一百四十四页。 例例2.4 已知长度为已知长度为n的线性表的线性表A采用顺序存储结构，编写一个采用顺序存储结构，编写一个时间复杂度为时间复杂度为O(n)、空间复杂度为、空间复杂度为O(1)的算法，该算法删除线性的算法，该算法删除线性表中所有值为表中所有值为x的数据元素。的数据元素。 解法一：解法一：用用k记录顺序记录顺序(shnx)表表A中等于中等于x的元素个数，边扫描的元素个数，边扫描A边统计边统计k，并将不为，并将不为x的元素放置在的元

32、素放置在k位置上，最后修改位置上，最后修改A的长度。的长度。12323213x=213313AA1A1 A可以直接可以直接(zhji)利用利用A的空间建立的空间建立A1第四十页，共一百四十四页。void delnode1(SqList &A,ElemType x) int k=0，i; /k记录值不等于记录值不等于(dngy)x的元素个数的元素个数 for (i=0;iA.length;i+) if (A.datai!=x) A.datak=A.datai; k+; /不等于不等于x的元素增的元素增1 A.length=k; /顺序表顺序表A的长度等于的长度等于k算法算法(sun f)(sun

33、 f)1 1：类似于建顺序表类似于建顺序表第四十一页，共一百四十四页。 解法二：解法二：用用k记录顺序表记录顺序表A中等于中等于x的元素的元素(yun s)个数，边扫描个数，边扫描A边边统计统计k，并将不为，并将不为x的元素的元素(yun s)前移前移k个位置，最后修改个位置，最后修改A的长度。的长度。123232x=2i=0,k=0:1前移前移0个位置个位置(wi zhi)123232i=1,k=1123232i=2,k=1:3前移前移1个位置个位置(wi zhi)133232第四十二页，共一百四十四页。133232i=3,k=2133232i=4,k=2:3前移前移2个位置个位置(wi z

34、hi)133232133232i=5,k=3A.length=6-3=3，A变为：变为：133第四十三页，共一百四十四页。void delnode2(SqList &A,ElemType x) int k=0，i=0; /k记录值等于记录值等于x的元素个数的元素个数 while (idata0; /取基准取基准i=0;j=A-length-1;while(i!=j) while(ji& A-datajbase) j-; /从右向左扫描从右向左扫描(somio)，找一个小元素，找一个小元素 A-datai=A-dataj;/将小元素前移将小元素前移 while(idataidataj=A-dat

35、ai; /将大元素后移将大元素后移A-datai=base;第四十七页，共一百四十四页。2.3.1 线性表的链式存储线性表的链式存储链表链表 在链式存储中，每个存储结点不仅包含有所存元素本身的在链式存储中，每个存储结点不仅包含有所存元素本身的信息（称之为信息（称之为数据域数据域），而且），而且(r qi)包含有元素之间逻辑关系的信包含有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息，这称为指针域，这样息，即前驱结点包含有后继结点的地址信息，这称为指针域，这样可以通过前驱结点的指针域方便地找到后继结点的位置，提高数据可以通过前驱结点的指针域方便地找到后继结点的位置，提高数据查找速度。

36、查找速度。 一般地，每个结点有一个或多个这样的指针域。若一个结一般地，每个结点有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点，则仅它的值为空，用常量点中的某个指针域不需要任何结点，则仅它的值为空，用常量NULL表示。表示。2.3 线性表的链式存储线性表的链式存储(cn ch) 第四十八页，共一百四十四页。 由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是：最简单也最常用

37、的方法是： 在每个结点中除包含有数据域外在每个结点中除包含有数据域外(y wi)，只设置，只设置一个指针域一个指针域，用，用以指向其后继结点，这样构成的链接表称为线性单向链接表，简以指向其后继结点，这样构成的链接表称为线性单向链接表，简称称单链表单链表。第四十九页，共一百四十四页。带头结点带头结点(ji din)单链表示单链表示意图意图 在线性表的链式存储中，为了便于插入和删除在线性表的链式存储中，为了便于插入和删除(shnch)算法的实算法的实现，每个链表带有一个头结点，并通过头结点的指针唯一标识该现，每个链表带有一个头结点，并通过头结点的指针唯一标识该链表。链表。 或尾结点或尾结点(ji

38、din)第五十页，共一百四十四页。对于第对于第1章的逻辑结构章的逻辑结构City，采用，采用(ciyng)带头结点的单链表存带头结点的单链表存储时的结构如下所示：储时的结构如下所示：第五十一页，共一百四十四页。 在单链表中，由于每个结点只包含有一个指向后继结点的指针在单链表中，由于每个结点只包含有一个指向后继结点的指针(zhzhn)(zhzhn)，所以当访问过一个结点后，只能接着访问它的，所以当访问过一个结点后，只能接着访问它的后继结点后继结点，而无法访问它的而无法访问它的前驱结点前驱结点。 第五十二页，共一百四十四页。 另一种可以采用的方法是：另一种可以采用的方法是： 在每个结点中除包含有数

39、值域外，设置有两个指针域，分别在每个结点中除包含有数值域外，设置有两个指针域，分别(fnbi)用以指向其前驱结点和后继结点，这样构成的链接表称之为用以指向其前驱结点和后继结点，这样构成的链接表称之为线性双向链接表，简称线性双向链接表，简称双链表双链表。第五十三页，共一百四十四页。带头结点的双链表示带头结点的双链表示(biosh)意意图图或尾结点或尾结点(ji din)第五十四页，共一百四十四页。 在双链表中，由于在双链表中，由于(yuy)(yuy)每个结点既包含有一个指向后继结点的每个结点既包含有一个指向后继结点的指针，又包含有一个指向前驱结点的指针，所以当访问过一个结点指针，又包含有一个指向

40、前驱结点的指针，所以当访问过一个结点后，既可以后，既可以依次向后访问每一个结点依次向后访问每一个结点，也可以，也可以依次向前访问每一依次向前访问每一个结点。个结点。双链表的特点双链表的特点(tdin)(tdin)与单链表相比，双链表中从某结点与单链表相比，双链表中从某结点(ji din)访问前后结点访问前后结点(ji din)更方便。更方便。第五十五页，共一百四十四页。 在单链表中，假定每个结点类型用在单链表中，假定每个结点类型用LinkList表示，它应包括存表示，它应包括存储元素的数据储元素的数据(shj)域，这里用域，这里用data表示，其类型用通用类型标识符表示，其类型用通用类型标识符

41、ElemType表示，还包括存储后继元素位置的指针域，这里用表示，还包括存储后继元素位置的指针域，这里用next表示。表示。 LinkList类型的定义如下：类型的定义如下： typedef struct LNode /定义单链表结点类型定义单链表结点类型 ElemType data; struct LNode *next; /指向后继结点指向后继结点 LinkList;第五十六页，共一百四十四页。2.3.2 2.3.2 单链表基本运算单链表基本运算(yn sun)(yn sun)的实现的实现 1. 建立单链表建立单链表 先考虑如何建立单链表。假设我们通过一个含有先考虑如何建立单链表。假设我们

42、通过一个含有n个数据的数组个数据的数组来建立单链表。建立单链表的常用方法有如下两种：来建立单链表。建立单链表的常用方法有如下两种： （1） 头插法建表头插法建表 该方法从一个空表开始，读取字符数组该方法从一个空表开始，读取字符数组a中的字符，生成新结中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后点，将读取的数据存放到新结点的数据域中，然后将新结点插入将新结点插入到当前链表的表头到当前链表的表头上，直到结束为止上，直到结束为止(wizh)。采用头插法建表的算。采用头插法建表的算法如下：法如下：第五十七页，共一百四十四页。void CreateListF(LinkList*&L,E

43、lemType a,int n) LinkList *s;int i; L=(LinkList *)malloc(sizeof(LinkList); /创建头结点创建头结点(ji din) L-next=NULL; for (i=0;idata=ai; s-next=L-next; L-next=s; /将将* *s s插在开始结点之前，头结点之后插在开始结点之前，头结点之后 第五十八页，共一百四十四页。adcbi=0i=1i=2i=3L采用头插法建立采用头插法建立(jinl)单链表的过单链表的过程程LaLdaLcdaLbcda第第1 1步：建头结点步：建头结点(ji din)(ji din)

44、第第2 2步：步：i i0 0，新建，新建a a结点，插入结点，插入(ch r)(ch r)到头结点之到头结点之后后第第3 3步：步：i i1 1，新建，新建d d结点，插入到头结点之后结点，插入到头结点之后第第4 4步：步：i i2 2，新建，新建c c结点，插入到头结点之后结点，插入到头结点之后第第5 5步：步：i i3 3，新建，新建b b结点，插入到头结点之后结点，插入到头结点之后第五十九页，共一百四十四页。 （2）尾插法建表）尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组元素的顺序相反。若希望两者次序一致序和

45、原数组元素的顺序相反。若希望两者次序一致(yzh)(yzh)，可，可采用尾插法建立。采用尾插法建立。 该方法是将新结点插到当前链表的表尾上，为此必须增加一个该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针尾指针r r，使其，使其始终指向当前链表的尾结点始终指向当前链表的尾结点。采用尾插法建表的。采用尾插法建表的算法如下：算法如下：第六十页，共一百四十四页。void CreateListR(LinkList *&L,ElemType a,int n) LinkList *s，*r;int i; L=(LinkList *)malloc(sizeof(LinkList); /创建头结点

46、创建头结点 r=L; /r始终指向终端结点，开始始终指向终端结点，开始(kish)时指向头结点时指向头结点 for (i=0;idata=ai; r-next=s; r=s; /将将*s插入插入*r之后之后 r-next=NULL;/终端结点终端结点next域置为域置为NULL第六十一页，共一百四十四页。bcdai=0 i=1 i=2 i=3head头结点头结点b采用采用(ciyng)尾插法建立单链表的过程尾插法建立单链表的过程adc第六十二页，共一百四十四页。2. 插入结点运算插入结点运算 插入运算是将值为插入运算是将值为x的新结点插入到单链表的第的新结点插入到单链表的第i个结点的位置个结点

47、的位置(wi zhi)上。先在单链表中找到第上。先在单链表中找到第i-1个结点，再在其后插入新结点。个结点，再在其后插入新结点。 单链表插入结点的过程如下图所示。单链表插入结点的过程如下图所示。第六十三页，共一百四十四页。插入插入(ch r)结点示意图结点示意图第六十四页，共一百四十四页。 3. 删除结点运算删除结点运算 删除运算是将单链表的第删除运算是将单链表的第i个结点删去。先在单链表中找到第个结点删去。先在单链表中找到第i-1个结点，再删除其后的结点。个结点，再删除其后的结点。 删除单链表结点的过程删除单链表结点的过程(guchng)如下图所示。如下图所示。第六十五页，共一百四十四页。删

48、除删除(shnch)结点示意结点示意图图第六十六页，共一百四十四页。 4. 线性表基本运算实现线性表基本运算实现 （1） 初始化线性表初始化线性表InitList(L) 该运算建立一个该运算建立一个(y )空的单链表，即创建一个空的单链表，即创建一个(y )头结点。头结点。 void InitList(LinkList *&L) L=(LinkList *)malloc(sizeof(LinkList); /创建头结点创建头结点L-next=NULL; L第六十七页，共一百四十四页。 （2）销毁线性表）销毁线性表DestroyList(L) 释放单链表释放单链表L占用的内存空间。即逐一占用的内

49、存空间。即逐一(zhy)释放全部结点的空间。释放全部结点的空间。 void DestroyList(LinkList *&L) LinkList *p=L,*q=p-next;while (q!=NULL) free(p); p=q;q=p-next;free(p); 初始初始(ch sh)时时循环循环(xnhun)结结束时束时LpqLpq=NULL第六十八页，共一百四十四页。 （3）判线性表是否为空表）判线性表是否为空表ListEmpty(L) 若单链表若单链表L没有没有(mi yu)数据结点，则返回真，否则返回假。数据结点，则返回真，否则返回假。 int ListEmpty(LinkLis

50、t *L) return(L-next=NULL); 第六十九页，共一百四十四页。 （4）求线性表的长度）求线性表的长度(chngd)ListLength(L) 返回单链表返回单链表L中数据结点的个数。中数据结点的个数。 int ListLength(LinkList *L) LinkList *p=L;int i=0;while (p-next!=NULL) i+; p=p-next;return(i); 初始初始(ch sh)时时循环循环(xnhun)结结束时束时Lp，i=0Lp p，i i为结点个数为结点个数第七十页，共一百四十四页。 （5）输出线性表）输出线性表DispList(L)