数据结构与算法设计（第二版）课件 第2章 线性表

第二章线性表西安科技大学计算机学院张小艳数据结构与算法设计第一章复习1.教学目标

通过线性表的学习，熟悉本书对每种数据结构的描述方法，掌握线性表的定义、特点、典型算法及实际中的实用。2.教学要求①了解线性表的逻辑结构特性。②熟练掌握线性表的两种存储结构的描述方法。③熟练掌握线性表在顺序存储结构上基本操作的实现④熟练掌握线性表在各种链式存储结构上基本操作的实现；⑤能够从时间和空间复杂度的角度比较线性表两种存储结构的特点第二章线性表3．教学重点：①线性表顺序存储结构的特点及基本操作。②线性表链式存储结构的特点及基本操作。4．教学难点：①链表的概念。②链式存储结构上算法的实现。第二章线性表2.1线性表的定义及逻辑结构2.1.1线性表的定义例2-1中华传统文化经典:二十四节气。二十四节气蕴含着中华民族悠久的文化内涵和历史积淀。在漫长的农耕社会中，二十四节气发挥着重要作用，拥有丰富的文化内涵。2.1线性表的定义及逻辑结构2.1.1线性表的定义例2-1中华传统文化经典:二十四节气。二十四节气歌诀：

立春雨水渐，惊蛰虫不眠，春分近清明，采茶谷雨前；

立夏小满足，芒种大开镰，夏至才小暑，大暑三伏天；

立秋处暑去，白露南飞雁，秋分寒露至，霜降红叶染；

立冬小雪飘，大雪兆丰年，冬至数九日，小寒又大寒。

节气歌唱出了节气的顺序。一年中的节气罗列出来如下：【立春

雨水

惊蛰

春分

清明

谷雨

立夏

小满

芒种

夏至

小暑

大暑

立秋

处暑

白露

秋分寒露霜降立冬小雪大雪冬至小寒大寒】2.1线性表的定义及逻辑结构2.1.1线性表的定义线性表——是n个相同类型数据元素组成的有限序列。记作：（a1,a2,…，ai-1，ai，ai+1，…，an）

其中a1称作起始结点，

an称作终端结点。i称为ai在线性表中的位置或序号。

n为表长，n=0时，称为空表。2.1线性表的定义及逻辑结构

例2-2计算机学院学院从2008年到2013年拥有的学生人数的变化情况表：

(800，1000，2000，3600，3800，4500)

（a1,a2,…，ai-1，ai，ai+1，…，an）

从数据可以看到，我们学院在迅速发展。例2-3、

在校学生的健康信息表是一个线性表，表中每个学生的信息由学号、姓名、性别、年龄、班级和健康状况等组成学号姓名性别年龄班级健康状况1204101钱小明男19计科12健康1204108周维男18计科12一般1204111杨丽女20计科12健康1204112赵武男23计科12差………………1204135张丽女17计科12一般2.1线性表的定义及逻辑结构

数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同的情况下可以不同，可以是一个节气，可以是一个数字，可以是一个学生信息。共同的特点就是：一个线性表中的数据元素必须属于同一数据对象。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

线性表是由n(n≥0)个数据类型相同的数据元素a1，a2，…，ai-1，ai，ai+1，…，an组成的有限序列，通常记为：表中相邻元素间存在着顺序关系，对于任一对相邻结点

<ai，ai+1

>ai称为ai+1的前驱，ai+1称为ai的后继对于ai，当i=2,…,n时，有且仅有一个直接前趋ai-1；当i=1,2,…,n-1时，有且仅有一个直接后继ai+1；而a1是表中第一个元素，它没有直接前趋；an是表中最后一个元素，它没有直接后继。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

线性表是由n(n≥0)个数据类型相同的数据元素组成的有限序列，通常记为：<ai，ai+1

>ai称为ai+1的前驱，ai+1称为ai的后继（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

“二十四节气”中节气的时间<ai，ai+1

>ai称为ai+1的前驱，ai+1称为ai的后继（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

“每年学生人数”位置计算机学院学院从2008年到2013年拥有的学生人数的变化情况表：

(800，1000，2000，3600，3800，4500)<ai，ai+1

>ai称为ai+1的前驱，ai+1称为ai的后继（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

“每个学生信息”表中数值顺序很重要，也不能随意变换。这是线性表的基本要求，就如同国家有法律，学校有规章制度，家庭有规则，我们必须遵守规则、遵纪守法。学号姓名性别年龄班级健康状况1204101钱小明男19计科12健康1204108周维男18计科12一般1204111杨丽女20计科12健康1204112赵武男23计科12差………………1204135张丽女17计科12一般线性表的特点：线性表由同一类型的数据元素组成，每个ai必须属于同一数据类型。线性表中的数据元素个数是有限的，表长就是表中数据元素的个数。存在唯一的“第一个”数据元素；存在唯一的“最后一个”数据元素。除第一个数据元素外，每个数据元素均有且只有一个前驱元素。除最后一个数据元素外，每个数据元素均有且只有一个后继元素。（a1,a2,…，ai-1，ai，ai+1，…，an）

2.1线性表的定义及逻辑结构

2.1.2线性表的基本操作

(1)初始化InitList(L)

(2)线性表判空EmptyList(L)

(3)求长度LengthList(L)

(4)取元素函数GetList(L,i)

(5)按值查找LocatList(L,x)

(6)插入操作InsertList(L,i,x)

(7)删除操作DeleteList(L,i)2.1线性表的定义及逻辑结构

（a1,a2,…，ai-1，ai，ai+1，…，an）

2.2线性表的顺序存储结构2.2.1顺序表

线性表的顺序存储结构是指在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，元素之间的逻辑关系通过存储位置来反映，用这种存储形式存储的线性表称其为顺序表。设a1的存储地址为Loc(a1)，每个数据元素占L个存储单元，则第i个数据元素的地址为：Loc(ai)=Loc(a1)+(i-1)×L1≤i≤n

按数据元素的序号随机存取线性表的顺序存储结构可用C语言定义如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

L;线性表中最后一个元素在数组中的位置存放数据元素

顺序存储结构三个重要属性：存储数据元素的空间：数组elem，用于存放数据元素。线性表的最大容量：MAXSIZE。线性表当前长度：由last+1确定，last：最后一个数据元素在数组中的下标。2.2线性表的顺序存储结构细节决定成败！！！线性表的顺序存储结构可用C语言定义如下：#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];

intlast;}

SeqList;

SeqList

L;线性表中最后一个元素在数组中的位置存放数据元素

2.2线性表的顺序存储结构细节决定成败！！！强调两个问题：“数组的长度”和“线性表的长度”两个概念。注意区分数据元素的位序和数组的下标。SeqList*L

；SeqList

L;表长：L.last+1数据元素：L.elem[0]~L.elem[L.last]表长：（*L）.last+1或L->last+1数据元素：L->elem[0]~L->elem[L->last]2.2线性表的顺序存储结构#defineMAXSIZE100typedefstructLinear_list{datatypeelem[MAXSIZE];intlast;}

SeqList;

细节决定成败！！！2.2.2顺序表上插入与删除操作的实现1初始化main(){inti,len;SeqListL;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L.elem[i]);

L.last++;}………}2.2线性表的顺序存储结构#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2顺序表上插入与删除操作的实现1初始化main(){inti,len;SeqList*L;L.last=-1;scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}………}2.2线性表的顺序存储结构#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.2顺序表上插入与删除操作的实现1初始化SeqList*InitList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L->last=-1;returnL;}主函数对初始化函数的调用：main(){inti,len;SeqList*L;L=InitList();scanf(“%d”,&len);for(i=0,i<len,i++){scanf(“%d”,&L->elem[i]);

L->last++;}……………}2.2线性表的顺序存储结构本算法的主要运算是比较。2按值查找intLocatList(SeqList*L,datatypex){inti=0;

while(i<=L->last&&L->elem[i]!=x)i++;

if(i>L->last)return-1;elsereturni;/*返回的是存储位置*/

}平均时间复杂度：

假设查找每个元素的概率相等：1/n;查找第i个的比较次数：i平均比较次数为:

(1+2+3+4+…+n)/n=(n+1)/2，时间复杂度为O(n)。2.2线性表的顺序存储结构最好的比较次数为1次，最差的是比较n次。3插入运算线性表的插入是指在表的第i个位置上插入一个值为x的新元素,i的取值范围为1≤i≤n+1。③修改last指针（相当于修改表长），

使之仍指向最后一个元素。步骤：①将ai～an

顺序向下移动，

为新元素让出位置；②将x置入空出的第i个位置；2.2线性表的顺序存储结构1intInsertList(SeqList*Lp,inti,datatypex)2{intj;3if(Lp->last==MAXSIZE-1)4{printf(″表满″);5return(-1);6}if(i<1||i>Lp->last+2) {printf(″位置错″);9return(0);10}for(j=Lp->last;j>=i-1;j--) Lp->elem[j+1]=Lp->elem[j];13Lp->elem[i-1]=x;/*新元素插入*/14Lp->last++; /*last仍指向最后元素*/15return(1); /*插入成功，返回*/16}算法实现：算法设计时请注意：注意数据的移动方向检验插入位置的有效性：1≤i≤n+1在表满的情况下不能再做插入2.2线性表的顺序存储结构1intInsertList(SeqList*Lp,inti,datatypex)2{intj;3if(Lp->last==MAXSIZE-1)4{printf(″表满″);5return(-1);6}if(i<1||i>Lp->last+2) {printf(″位置错″);9return(0);10}for(j=Lp->last;j>=i-1;j--) Lp->elem[j+1]=Lp->elem[j];13Lp->elem[i-1]=x;/*新元素插入*/14Lp->last++; /*last仍指向最后元素*/15return(1); /*插入成功，返回*/16}算法实现：时间复杂度分析：2.2线性表的顺序存储结构插入位置i，从ai

到an都要向下移动一个位置，共需要移动n-i+1个元素，而i的取值范围为1≤i≤n+1，即有n+1个位置可以插入。设在第i个位置上插入元素的概率为Pi，则平均移动数据元素的次数为假设在每个位置插入元素的概率相等，Pi = 1/(n+1)时间复杂度为：O（n）

时间性能分析：

在顺序表中插入一个数据元素时，其时间主要耗费在移动数据元素上。在第i个位置上插入x，从ai

到an都要向下移动一个位置，共需要移动n-i+1个元素，而i的取值范围为1≤i≤n+1，即有n+1个位置可以插入。设在第i个位置上插入元素的概率为Pi，则平均移动数据元素的次数为说明在顺序表上作插入运算平均需要移动表中一半的数据元素假设在每个位置插入元素的概率相等，即Pi = 1/(n+1)，则2.2线性表的顺序存储结构①将ai+1～an顺序向上移动。4.删除操作指将表中第i个元素从线性表中去掉,i的取值范围为:1≤i≤n步骤：②修改last指针使之仍指向最后一个元素。2.2线性表的顺序存储结构①当表空时不能做删除，否则产生下溢错误。②要检查删除位置的有效性1≤i≤n③删除ai

之后，该数据已不存在，如果需要，先取出ai

，再做删除。④注意数据的移动方向。算法如下：1intDeleteList(SeqList*Lp,inti)2{intj;if(i<1||i>Lp->last+1){printf(″不存在第i个元素″);5return(0);6}7for(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j];Lp->last--;10return(1); /*删除成功*/11}/*检查删除位置的合法性*//*向上移动*//*删除成功*/2.2线性表的顺序存储结构1intDeleteList(SeqList*Lp,inti)2{intj;if(i<1||i>Lp->last+1){printf(″不存在第i个元素″);5return(0);6}7for(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j];Lp->last--;10return(1); /*删除成功*/11}2.2线性表的顺序存储结构算法性能分析：时间主要消耗在移动表中元素上删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数：等概率情况下，Ｐi＝

1/n则平均移动数据元素的次数为时间复杂度为：O（n）2.2线性表的顺序存储结构线性表顺序表示的优缺点对比优点缺点无需为表示结点间的逻辑关系而增加额外的存储空间可方便地随机存取表中的任一元素插入或删除需要移动大量的数据元素当线性表长度变化较大时难以确定存储空间的容量造成存储空间浪费2.2.3顺序表应用举例例2-4利用两个线性表La和Lb分别表示两个集合A和B，现要求一个新的集合A = A∪B。假设集合中的数据元素属于整型数据。

算法思路：扩大线性表La，将存在于线性表Lb中而不在La中的数据元素加入到线性表La中。逐一取出Lb中的元素，判断是否在La中，若不在，则插入。由于La是集合，数据元素之间没有顺序关系，所以插入时，可以插入到La的最后一个元素后面，这样，就不用移动大量数据元素。A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2线性表的顺序存储结构2.2.3顺序表应用举例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2线性表的顺序存储结构#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

2.2.3顺序表应用举例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2线性表的顺序存储结构#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

472.2.3顺序表应用举例A=(23,45,78,91,55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)2.2线性表的顺序存储结构#defineMAXSIZE20typedefstructLinear_list{intelem[MAXSIZE];

intlast;}

SeqList;

847算法如下：1voidunin(SeqList*La,SeqListLb)2{inti,j,La_len,Lb_len;3datatypee;4La_len=La->last;5Lb_len=Lb.last;6for(i=0;i<=Lb_len;i++)7{e=Lb.elem[i];8j=0;9while(j<=La_len&&e!=La->elem[j])j++;

10if(j>La_len) 11if(La_len<MAXSIZE-1)/*存储空间足够*/12La->elem[++(La->last)]=e;/*插入到La的最后*/13}14}语句6循环次数是Lb的表长，语句9循环次数最多是La的表长，此算法的时间复杂度为O(ListLength(La) × ListLength(Lb))。2.2线性表的顺序存储结构例2-5有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。例如A = (2,2,3),B = (1,3,3,4)，则C = (1,2,2,3,3,3,4)。

算法思路：依次扫描A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表。设表C是一个空表，设两个指针i、j分别指向表A和B中的元素，若A.elem[i] > B.elem[j]，则将B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，则当前先将A.elem[i]插入到表C中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表C中。2.2线性表的顺序存储结构例2-5有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。A = (2,2,3),B = (1,3,3,4)，则C = (1,2,2,3,3,3,4)。

初始状态：C为空表；i=0;j=0;k=0;A-lastB-lastijk2.2线性表的顺序存储结构例2-5有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。A = (2,2,3),B = (1,3,3,4)，则C = (1,2,2,3,3,3,4)。初始状态：C为空表；i=0;j=0;k=0;A-lastB-lastijk2.2线性表的顺序存储结构若A.elem[i] > B.elem[j]，则将B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，则将A.elem[i]插入到表C中；C->last++

如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完

的表中剩余的所有元素放到表C中。1例2-5有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。A = (2,2,3),B = (1,3,3,4)，则C = (1,2,2,3,3,3,4)。初始状态：C为空表；i=0;j=0;k=0;A-lastB-lastijk2.2线性表的顺序存储结构1223333344若A.elem[i] > B.elem[j]，则将B.elem[j]插入到表C中；若A.elem[i]≤B.elem[j]，则将A.elem[i]插入到表C中；C->last++

如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完

的表中剩余的所有元素放到表C中。1voidmerge(SeqListA,SeqListB,SeqList*C)

2{inti,j,k;

3i=0;j=0;k=0;

4while(i<=A.last&&j<=B.last) /*A表、B表都不为空*/

5if(A.elem[i]<=B.elem[j])

6C->elem[k++]=A.elem[i++];/*将A表中i指针指向记录插入到C中*/

7else

8C->elem[k++]=B.elem[j++];/*将B表中i指针指向记录插入到C中*/

9while(i<=A.last) /*将A表剩余部分插入到C中*/

10C->elem[k++]=A.elem[i++];

11while(j<=B.last) /*将B表剩余部分插入到C中*/

12C->elem[k++]=B.elem[j++];

13C->last=k-1;

14}语句4～语句8循环次数为表A的长度或者表B的长度语句9～语句12是两个并列的循环，这两个中只有可能做一个，循环次数为表A或表B剩余的部分。因此，该算法的时间复杂度是O(A.last + B.last)。2.2线性表的顺序存储结构习题：将顺序表(a1，a2，...，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值均比a1大（这里假设数据元素的类型具有可比性，不妨设为整型）。这一操作称为划分，a1也称为基准。

划分前23456103576185620划分后201810623453576562.2线性表的顺序存储结构线性表顺序表示的优点：①

无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；

线性表顺序表示的缺点：②由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。

②可方便地随机存取表中的任一元素。

①

插入或删除运算不方便，除表尾位置外，在其它位置上进行插入或删除操作都必须移动大量的数据元素，其效率较低；2.2线性表的顺序存储结构

线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式来表示。然而，对顺序表进行插入、删除操作时需要通过移动数据元素来实现，影响了运行效率。

我们就要寻求更好的存储方式，就像我们平时在解决问题时需要学会变通，不能一条道儿走到黑，如果犯了错误，改正就好，常言道：“知错就改，善莫大焉”。2.3线性表的链式存储结构用一组任意的存储单元来存储线性表中的数据元素。

这组存储单元连续不连续都可以。为了表示数据元素ai和其直接后继ai+1之间的逻辑关系还需要存储一个指示其后继的信息。指针域数据域结点在顺序表中，只需要存储数据元素，其逻辑关系-物理位置相邻就能体现在链式存储结构中，除了存储数据元素。单链表2.3线性表的链式存储结构线性表(a1,a2,a3,a4,a5,a6,a7,a8)对应的链式存储结构。2.3线性表的链式存储结构0500a1a1的地址为：05002.3线性表的链式存储结构a202000510a2的存储地址通过a1的指针域next获得（0200）2.3线性表的链式存储结构051005100900a3的存储地址通过a2的指针域next获得（0510）2.3线性表的链式存储结构090009000910a4的存储地址可以通过a3的指针域next获得（0900）2.3线性表的链式存储结构把链表中第一个元素的地址存放在一个指针变量中，我们称这个指针变量为链表的头指针。头指针H05002.3线性表的链式存储结构为了表示数据元素ai和其直接后继ai+1之间的逻辑关系还需要存储一个指示其后继的信息。指针域数据域在链式存储结构中，除了存储数据元素。含有n个数据元素的线性表通过每个结点的指针域拉成了一个“链子”，称之为单链表。…………单链表2.3线性表的链式存储结构H作为线性表的一种存储结构，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常的单链表可以抽象的表示成这样一种形式：…………H∧2.3线性表的链式存储结构typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

指针域数据域LNode是结构体结点类型；LinkList是结构体结点指针类型。用头指针来标识一个单链表，如单链表L、单链表H。H…………H单链表-存储结构C语言描述2.3线性表的链式存储结构LinkListH；H是一个结构体指针，即单链表的头指针。typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

H==NULL为真。

单链表-存储结构C语言描述2.3线性表的链式存储结构头结点的数据域可以不存放任何数据，也可以存放链表的结点个数的信息头指针H指向头结点的存储位置。这样的单链表我们称之为带头结点的单链表。在线性链表的第一结点之前附设一个结点，称为头结点。…………H头结点头指针2.3线性表的链式存储结构一个带头结点的空链表

H->next==NULL

单链表H不是空表，可以通过头指针访问表中所有结点。假设p=H->nextp->data=a1p->next->data=a2H头结点头指针…………Hpp->next2.3线性表的链式存储结构假设q是指向线性表中第i个结点的指针，……H那么q->next是指向第i+1个数据元素(结点ai+1)的指针。qq->next2.3线性表的链式存储结构typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

单链表是一种动态存储结构在C语言中，可以利用malloc函数向系统申请存储空间，这个函数返回存储区的首地址。p=(LinkList)malloc(sizeof(LNode));free(p)p2.3线性表的链式存储结构typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

5while(!p&&j<i)6{p=p->next；

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}取第i个数据元素操作采用“数”结点的方法，从第一个开始“数”，一直“数”到第i个。……Hpj=02.3线性表的链式存储结构1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

5while(!p&&j<i)6{p=p->next；

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}取第i个数据元素操作采用“数”结点的方法，从第一个开始“数”，一直“数”到第i个。2.3线性表的链式存储结构……Hpj=0--------------------------------------------------------------p=p->nextj++pj=ip……Hpj=i2.3线性表的链式存储结构1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

5while(!p&&j<i)6{p=p->next；

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

2.3线性表的链式存储结构1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

5while(!p&&j<i)6{p=p->next；

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}……Hj=0--------------p=p->nextj++j=1pp1LinkListGetlist(LinkListL,inti)2{intj；3LNode*p；4p=L；j=0；

5while(!p&&j<i)6{p=p->next；

7j++；}8if（i==j）returnp；

9else10returnNULL；

11}……Hj=0------------------------------------------------------------------------------------------------------------p=p->nextj++j=npp2.3线性表的链式存储结构从第一个元素开始“数”，一直“数”到最后一个结点(p->next=NULL)。(1)设一个临时变量p指向头结点，计数器j等于0。(2)当p->next!=NULL时，循环：指针p后移，指向它的直接后继结点，计数器j加1.循环停止时返回J就是链表长度。……Hj=0------------------------------------------------------------------------------------------------------------p=p->nextj++j=np单链表-求单链表长度2.3线性表的链式存储结构单链表的存储结构描述用C语言如下：typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

定义结构体变量：LinkListH；H是一个结构体指针，即单链表的头指针通常在线性链表的第一结点之前附设一个称为头结点的结点。

H->next==NULL（带头结点）对于带头结点的单链表H∧若定义

LinkListp;

且p=H->next那么p->data=a1p->next->data=a2

其余依此类推。通常我们用头指针来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L或H中，头指针为NULL，则表示一个空表，即H==NULL为真。a1a2an∧…H2.3线性表的链式存储结构头指针和头结点的异同头指针头结点指向第一个结点的指针，若链表有头结点，则是指向头结点的指针具有标示作用，常用头指针作为链表的名字放在第一个元素之前，其数据域一般无意义(也可以放链表的长度)有了头结点，在第一个元素结点之前插入和删除第一个结点，其操作与其他结点的操作就统一了造成存储空间浪费

不带头结点的链表和带头结点的链表的区别不带头结点带头结点链表为空：L==NULL为真链表的第一个数据元素由L指向在第一个元素之前插入一个元素和删除第一个元素要单独处理，和在其他位置插入、删除操作不同链表为空：L->next==NULL为真链表的第一个数据元素由L->next指向插入、删除操作统一2.3线性表的链式存储结构2.3.2单链表上的基本运算intInitList(LinkList*h){if(

(*h=(LinkList)malloc(sizeof(LNode)))==NULL

)return(0);(*h)->next=NULL;return(1);}1.初始化初始化操作即建立一个空表。H∧2.3线性表的链式存储结构typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

1建立单链表

建立过程是一个动态生成的过程，即从“空表”起，依次建立结点，并逐个插入链表１头插法２尾插法逆序创建链表顺序创建链表2.3.2单链表上的基本运算typedefstructnode{

datatypedata;structnode*next;

}LNode，*LinkList；

2.3线性表的链式存储结构1）用头插法建立单链表的算法Step0:

Step1:Step2:Step3:在链表的头部插入，读入数据的顺序和线性表的逻辑顺序是相反的申请一块空间，S指向，读入S->data;将L->next的值赋给S->next

将L->next的值改为S建立只有头结点的单链表LS10L∧∧L=(Linklist)malloc(sizeof(LNode));L->next=NULL;s=(Linklist)malloc(sizeof(Lnode))s->data=c;s->next=L->next;L->next=s;输入数据：10,9,8,7,6,5,4,3,2,12.3线性表的链式存储结构1）用头插法建立单链表的算法Step0:

Step1:Step2:Step3:在链表的头部插入，读入数据的顺序和线性表的逻辑顺序是相反的申请一块空间，S指向，读入S->data;将L->next的值赋给S->next

将L->next的值改为S建立只有头结点的单链表L10L∧∧S9s=(Linklist)malloc(sizeof(Lnode))s->data=c;s->next=L->next;L->next=s;2.3线性表的链式存储结构1）用头插法建立单链表的算法Step0:

Step1:Step2:Step3:在链表的头部插入，读入数据的顺序和线性表的逻辑顺序是相反的申请一块空间，S指向，读入S->data;将L->next的值赋给S->next

将L->next的值改为S建立只有头结点的单链表L10L∧∧91210

∧…L2.3线性表的链式存储结构1LinklistCreateFromHead()2{LinkListL;3LNode*s;4charc;5intflag=1;/*设置一个标识变量flag，初值为1，当输入“$”时，将flag置为0，建表结束*/6L=(Linklist)malloc(sizeof(LNode)); /*为头结点分配存储空间*/7L->next=NULL;8while(flag)9{c=getchar();10if(c!='$’)11{s=(Linklist)malloc(sizeof(LNode));/*为读入的字符分配存储空间*/12s->data=c; /*数据域赋值*/13s->next=L->next;/*将s插入到链表中第一个数据元素之前*/14L->next=s;15}16else17flag=0;/*读入符号为“$”，修改结束标识*/

18}19returnL;20}2.3线性表的链式存储结构2）尾插法建表算法中必须维持一个始终指向已建立的链表表尾的指针。L=(Linklist)malloc(sizeof(LNode));L->next=NULL;r->next=s;r=s;s=(Linklist)malloc(sizeof(LNode));s->data=c;2.3线性表的链式存储结构1LinklistCreateFromHead()2{LinkListL;3LNode*s;4charc;5intflag=1;6L=(Linklist)malloc(sizeof(LNode)); /*为头结点分配存储空间*/7L->next=NULL; /*建带头结点的空链表*/8r=L; /*尾指针r指向表尾*/9while(flag)10{c=getchar();11if(c!='$')12{s=(Linklist)malloc(sizeof(LNode));/*为读入的字符分配存储空间*/13s->data=c; /*数据域赋值*/14r->next=s; /*插入到表尾*/15r=s;16}17else18{flag=0;19r->next=NULL;20}21}22returnL;23}2.3线性表的链式存储结构2)按值查找

算法描述：查找过程从单链表的头指针指向的头结点出发，顺着链表逐个将结点的值和给定值e作比较。若找到，返回找到的值为e的结点的存储位置，否则，返回空。要查找结点值等于给定值的结点1210

∧…L2.3线性表的链式存储结构1LinkListLocate(LinkListL,chare)2{LinkListp;3p=L->next;/*从表中第一个结点比较*/4while(p!=NULL&&p->data!=e)

5p=p->next;6returnp;7}算法实现如下：由于线性链表失去了随机存取的特性，所以按序号查找算法、按值查找算法的时间复杂度均为O(n)。1210

∧…L2.3线性表的链式存储结构typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s根本不用惊动其他结点，这两句的顺序可不可以交换？单链表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

press->next=pre->nextpre->next=s一定要注意：这两句的顺序不能反。a1aiai-1…an∧…e单链表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在单链表L中第i个位置之前插入一个数据元素e。这里是在单链表的第i个位置之前插入，单链表中每个结点只有指向后继的指针，所以要找到指向第i-1个结点的指针。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s单链表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

首先：在单链表中找到第i-1个结点并由指针pre指向。然后：申请一个新的结点并由指针s指向，将e赋给s的数据域；最后：修改指针、插入。也就是：s->next=pre->next；pre->next=s。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s单链表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″插入位置不合理!″);12returnERROR;13}14s=(LinkList)malloc(sizeof(LNode));15s->data=e;16s->next=pre->next;17pre->next=s;18returnOK;19}∧……a1ai-1aiai+1anL

k=0

prep-p->nextk=k+1

prek=i-1

preks

e单链表—插入操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″插入位置不合理!″);12returnERROR;13}14s=(LinkList)malloc(sizeof(LNode));15s->data=e;16s->next=pre->next;17pre->next=s;18returnOK;19}单链表—插入操作

pres

ek=i-1∧a1ai-1aiai+1anL……typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在单链表L中第i个位置之前插入一个数据元素e。这里是在单链表的第i个位置之前插入，单链表中每个结点只有指向后继的指针，所以要找到指向第i-1个结点的指针。a1aiai-1…an∧…

Lpreess->next=pre->nextpre->next=s单链表—插入操作（不带头结点）s=(LinkList)malloc(sizeof(LNode));s->data=e;typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入操作是要完成：在单链表L中第i个位置之前插入一个数据元素e。i=1a1aiai-1…an∧…

Less->next=LL=s单链表—插入操作（不带头结点）s=(LinkList)malloc(sizeof(LNode));s->data=e;typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1一个单链表L，pre指向其中一个结点。先记下来待删结点，q=pre->next;修改指针：pre->next=q->next;如果后面还需要用删除结点的数据信息，可以将q->data返回。最后要将q结点释放。

preqpre->next=q->next单链表—删除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1首先：需要在单链表中找到第i-1个结点，并由指针pre指向。然后：用q指针指向待删结点:q=pre->next，如果要用q的数据域，可记录下来：e=q->data。修改指针删除结点q,pre->next=q->next。

preqpre->next=q->next删除操作是要完成：在单链表L中，删除第i个数据元素。最后：释放q结点。e=q->data单链表—删除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

1intDelList(LinkListL,inti,char*e)2{3LinkListpre,q;4intk;5pre=L;k=0;6while(pre->next!=NULL&&k<i-1)7{pre=pre->next;8k=k+1;9}10if(k!=i-1)11{printf(″删除结点的位置i不合理!″);12returnERROR;13}14q=pre->next;15pre->next=q->next; 16*e=q->data;17free(q);18returnOK;19}∧……a1ai-1aiai+1an

L

k=0

prep-p->nextk=k+1

prek=i-1

prekqpre->next=q->nexte=q->data单链表—删除操作typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1首先：需要在单链表中找到第i-1个结点，并由指针pre指向。然后：用q指针指向待删结点:q=pre->next，如果要用q的数据域，可记录下来：e=q->data。修改指针删除结点q,pre->next=q->next。

preqpre->next=q->next删除操作是要完成：在单链表L中，删除第i个数据元素。最后：释放q结点。e=q->data单链表—删除操作(不带头结点）typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

a1aiai-1…an∧…

Lai+1i=1L=L->next删除操作是要完成：在单链表L中，删除第i个数据元素。e=L->data单链表—删除操作(不带头结点）头指针H指向链表附加头结点的存储位置，付出一个头结点的存储空间来简化插入、删除操作。这就如同苏心所说“哪有什么岁月静好，不过是有人替你负重前行”一样啊。typedefstructnode{datatypedata;structnode*next;}LNode，*LinkList；

插入删除算法分析：

删除算法中的循环条件(pre->next! = NULL&&k < i-1)前插算法中的循环条件(pre! = NULL&&k < i-1)因为前插时的插入位置有n+1个(n为当前单链表中数据元素的个数)。i=n+1是指在第n+1个位置前插入，即在单链表的末尾插入。

而删除操作中删除的合法位置只有n个，若使用与前插操作相同的循环条件，则会出现指针指空的情况，使删除操作失败。在线性链表中插入、删除元素虽然不需要移动数据元素，但需要查找插入、删除的位置，所以时间复杂度仍然是Ｏ(n)。1intInsList(LinkListL,inti,chare)2{3LinkListpre,s;4intk;5pre=L;k=0;6while(pre!=NULL&&k<i-1)7{p