数据结构 课件全套 张惠涛 第1-9章 绪论、线性表-排序

1/48review复习#include<bits/stdc++.h>intmain(){ inta[10]={89,23,45,13,67,90,35,68,33,67}; inti,j,temp; for(i=0;i<10;i++) printf("%d",a[i]); printf("\n");

for(i=1;i<10;i++) { temp=a[i]; j=i-1; while(j>=0&&temp<a[j]) { a[j+1]=a[j]; j--;

} a[j+1]=temp; } for(i=0;i<10;i++) printf("%d",a[i]); printf("\n"); return0;}2/48review复习voidswap(int*a,int*b){ inttemp; temp=*a; *a=*b; *b=temp;}intmain(){ inta,b; scanf("%d%d",&a,&b); swap(&a,&b); printf("a=%d,b=%d",a,b); return1;}3/48voidswap(int&a,int&b){ inttemp; temp=a; a=b; b=temp;}intmain(){ inta,b; scanf("%d%d",&a,&b); swap(a,b); printf("a=%d,b=%d",a,b); return1;}review复习1.1什么是数据结构1.2算法及算法分析4/48第1章绪论数据：所有能够输入到计算机中，且能被计算机处理的符号的集合。1.1.1数据结构的定义数据结构中的几个概念5/48数据结构：逻辑结构+存储结构+算法1.1什么是数据结构Word文档图像文档都是数据而数据结构中主要讨论结构化数据。6/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90一个学生成绩表示例7/48typedefstructstudent{ intnumber; charname[8]; intscore;}st;typedefstructstlist{ stdata; intlength;}stl;//结构体定义数据中可包含结构体类型变量数据结构化数据示例数据元素：是数据（集合）中的一个“个体”，它是数据的基本单位。数据项：数据项是用来描述数据元素的，它是数据的最小单位。数据项(用于描述数据元素)数据元素8/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生901班学生数据张三男101班李四计科系北京…数据元素（类型不相同）不是数据对象数据对象：具有相同性质的若干个数据元素的集合，如整数数据对象是所有整数的集合。2班学生数据张三男101班李四男102班…数据元素（类型相同）是数据对象默认情况下，数据结构中讨论的数据都是数据对象。9/48不相邻相邻10/48数据结构中讨论的元素关系主要是指相邻关系或邻接关系。学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90逻辑结构存储结构数据运算数据元素之间的逻辑关系

数据的逻辑结构。数据元素及其关系在计算机中的存储方式

数据的存储结构（或物理结构）。施加在该数据上的操作

数据运算。11/48数据结构的3个方面：数据的逻辑结构是从数据元素的逻辑关系上描述数据的。是指数据元素之间的逻辑关系的整体，通常是从求解问题中提炼出来的。数据逻辑结构与数据的存储无关，是独立于计算机的。12/481.1.1逻辑结构数据的逻辑结构是面向用户的，它有多种表示形式。

学生成绩表的逻辑结构表示1-图表直接来源于现实世界13/481、数据的逻辑结构表示学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生9010011002100310041005100614/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90一个二元组表示为：

B=(D，R)

其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中：

D={di|1≤i≤n，n≥0}：数据元素的集合

R={rj|1≤j≤m，m≥0}：关系的集合

二元组是一种通用的逻辑结构表示方法15/48学生表的逻辑结构表示2-二元组序偶<x，y>（x，y∈D）

x为第一元素，y为第二元素。x为y的前驱元素。y为x的后继元素。若某个元素没有前驱元素，则称该元素为开始元素；若某个元素没有后继元素，则称该元素为终端元素。序偶<x，y>表示x、y是有向的，序偶(x，y)表示x、y是无向的每个关系rj的用若干个序偶来表示：16/48二元组逻辑表示：

<1001,1002>，<1002,1003>，<1003,1004>，<1004,1005>，<1005,1006>每个学生记录用学号标识17/48学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90例如，如下数据为一个矩阵：

对应的二元组表示为B=(D，R)，其中：

D={2，6，3，1，8，12，7，4，5，10，9，11}

R={r1，r2}其中，r1表示行关系，r2表示列关系

r1={<2,6>，<6,3>，<3,1>，<8,12>，<12,7>，<7,4>，

<5,10>,<10,9>，<9,11>}

r2={<2,8>，<8,5>，<8,12>，<12,10>，<2,7>，<7,9>,

<7,4>，

<4,11>}26318127451091118/48元素之间关系：无。特点：数据元素之间除了“属于同一个集合”的关系外，别无其他逻辑关系。是最松散的，不受任何制约的关系。各种各样的数据呈现出不同的逻辑结构，归纳为4种。1）集合19/482、逻辑结构类型元素之间关系：一对一。特点：开始元素和终端元素都是唯一的，除此之外，其余元素都有且仅有一个前驱元素和一个后继元素。…20/482）线性结构元素之间关系：一对多。

特点：开始元素唯一，终端元素不唯一。除终端元素以外，每个元素有一个或多个后续元素；除开始元素外，每个元素有且仅有一个前驱元素。21/483）树形结构【例1-3】有一种数据结构B2=（D，R），其中D={48，25，64，57，82，36，75}R={r1，r2}

r1={<25，36>，<36，48>，<48，57>，<57，64>，

<64，75>，<75，82>}

r2={<48，25>，<48，64>，<64，57>，<64，82>，

<25，36>，<82，75>}画出其逻辑结构表示，指出是什么类型？22/4848253664578275r2关系表示r1关系表示解：B2的逻辑结构图如下。r1为线性结构r2为树形结构23/48元素之间关系：多对多。

特点：所有元素都可能有多个前驱元素和多个后继元素。24/484）图形结构线性结构树形结构图形结构线性表栈队列串数组树二叉树图25/48数据结构课程按逻辑结构类型分类学习一个一个数据结构的!数据逻辑结构在计算机中的存储表示称为数据的存储结构，也称为物理结构。

逻辑结构存储结构映射设计存储结构的这种映射应满足两个要求：存储逻辑结构中的所有元素存储数据元素间的逻辑关系26/481.1.2存储结构顺序存储结构链式存储结构索引存储结构哈希（散列）存储结构在软件开发中，人们设计了各种存储结构。归纳为4种基本的存储结构。27/48struct{intno; //存储学号

charname[8]; //存储姓名

intscore; //存储成绩

}Stud[6]={{1001,“张梦”,87},…,{1006,"王生",90}};存放学生成绩表的结构体数组Stud定义如下：28/48学生成绩表顺序存储结构－结构体数组学号姓名C语言程序设计成绩1001张梦871002李华961003陈烨951004张强891005赵娟781006王生90Stud数组起始地址…存储结构建立完毕学生成绩表的逻辑结构Stud[0]1001张梦8729/48Stud[1]1002李华96Stud[5]1006王生90顺序存储结构的特点：所有元素占用一整块内存空间。逻辑上相邻的元素，物理上也相邻。Stud[i]Stud[i+1]两个逻辑上相邻元素存储空间也相邻30/48直接映射typedefstructscore{intnum;charname[10];intC_score;}StuScore;typedefstructstudentscore{StuScoredata;structstudentscore*next;}LN_score;//链式存储结构定义学生成绩表存放学生表的链表的结点类型StudType声明如下：31/48学生表链式存储结构－链表学生成绩表的逻辑结构32/48链式存储学生成绩表在内存中的表示学生成绩表采用链式存储结构在内存中如图表示，其中内存地址用十进制表示。学生成绩表的逻辑结构33/48链式存储结构的特点：链式存储结构不具有随机存储特性，如果要查找某一个元素，需要通过指针遍历整个节点，直到找到该元素为止。同时，链式存储结构便于数据修改，如在某个元素前插入或删除元素时，不需要移动节点，只需修改相应节点对应的指针域地址即可，如删除一个元素操作示例如图1.13所示。图

链式存储结构删除操作链式存储结构删除操作过程描述：先定义一个指针指向要删除的节点，以免该节点丢失在内存中成为野指针，将所要删除的节点前面的指针域地址修改为要删除节点后面节点的地址，最后释放要删除的节点指针。一个逻辑元素用一个结点存储，每个结点单独分配，所有结点的地址不一定是连续的。用指针来表示逻辑关系。34/48链式存储结构的特点：学号（关键字）地址100101002510032100441005110063主数据表学生表的逻辑结构地址学号姓名成绩01001张梦8711005赵娟7821003陈烨9531006王生9041004张强8951002李华96索引表索引存储结构=主数据表

+索引表。索引表中所有关键字有序排列（如递增）。35/48学生成绩表索引存储结构学号姓名C语言程序设计成绩1001张梦871005赵娟781003陈烨951006王生901004张强891002李华96查找关键字（如学号）为k的元素时：先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字k。然后通过对应地址在主数据表中找到元素。36/48学号（关键字）地址100101002510032100441005110063主数据表地址学号姓名成绩01001张梦8711005赵娟7821003陈烨9531006王生9041004张强8951002李华96索引表通过索引表按关键字查找速度快增加索引表

存储空间较大37/48索引存储结构特点：哈希存储结构=哈希函数+解决冲突方法。哈希函数h(key)将关键字为key的元素存放在该地址。查找关键字为key的元素时，先计算h(key)，由该值和解决冲突方法来确定其存储地址。38/48学生表哈希存储结构学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901学生表的逻辑结构n=7,m=10哈希函数：h(key)=key%10地址学号姓名性别班号020陈华男990211张斌男9901212王奇男99013434李英女990155王萍女9901626董强男9902788刘丽女99029学号(key)h(key)11%10=188%10=83434%10=42020%10=01212%10=22626%10=655%10=539/48学生表哈希存储结构地址学号姓名性别班号020陈华男990211张斌男9901212王奇男99013434李英女990155王萍女9901626董强男9902788刘丽女99029哈希函数：h(key)=key%10查找关键字（如学号）为k的元素时：先计算d=h(k)。在d地址比较关键字k，若相同，表示找到了！40/48学生表哈希存储结构按关键字查找速度快需要解决冲突但不适合任何数据的存储41/48哈希存储结构的特点同一逻辑结构可以对应多种存储结构。结论：42/48数据运算是对数据的操作。数据运算分为两个层次：运算定义（或运算描述）和运算实现。逻辑结构、存储结构和运算三者之间的关系：运算定义逻辑结构存储结构映射运算实现43/481.1.3数据运算对于“学生成绩表”这种数据结构，可以进行一系列的运算：查找学号为1002的学生姓名增加一个学生记录；删除一个学生记录；查找性名为“赵娟”的学生记录；查找成绩大于90的学生记录；……运算描述44/48学号姓名C语言程序设计成绩1001张梦871005赵娟781003陈烨951006王生901004张强891002李华96Stud数组起始地址……直接找到Stud[1]元素，返回李华45/48顺序存储结构中实现“查找序号为2的学生姓名”Stud[0]1001张梦87Stud[1]1002李华96head1001张梦87i=1，pi2i=2，pi=2找到序号为2的记录，返回刘丽46/48思考并讨论：顺序存储结构和链式存储结构的区别（如插入、删除、查找等）链式存储结构中实现“查找序号为2的学生姓名”1002李华961003陈烨951004张强891005赵娟781006王生90∧同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。结论：47/4848/48#include<bits/stdc++.h>typedefstructLinknode{ intdata; structLinknode*next;}Linkstd;intmain(){ Linkstd*L; L=(Linkstd*)malloc(sizeof(Linkstd)); Linkstd*p,*s; inta; p=L; scanf("%d",&a);

while(a!=0) { s=(Linkstd*)malloc(sizeof(Linkstd)); s->data=a; p->next=s; p=p->next; s->next=NULL; scanf("%d",&a); } p=L; while(p->next!=NULL) { printf("%d",p->next->data); p=p->next; } return0;}分析算法占用的资源CPU时间内存空间时间性能分析空间性能分析算法分析目的：分析算法的时空效率以便改进算法性能。

1.3.1算法分析概述49/211.3算法分析算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中输入和输出的关系C.分析算法的效率以求改进D.分析算法的易读性和可行性答：C。示例50/21算法中的基本操作一般是最深层循环内的原操作。算法执行时间大致=基本操作所需的时间×其运算次数。

在算法分析时，计算T(n)时仅仅考虑基本操作的运算次数。转化51/21简化的算法时间复杂度分析算法运行时间=一个简单操作所需的时间×简单操作次数每条语句执行一次所需要的时间，随机器而异。取决于机器的指令性能，速度以及编译代码的质量。是由及其本身软硬件环境决定的，与算法无关。所以，可以假设执行每条语句的时间均为单位时间，在讨论算法运行时间时不予考虑。所以，算法的运行时间取决于简单操作次数，用T（n）表示，执行简单操作次数越多，其执行时间就相对越多。为了便于比较不同算法的时间效率，我们仅比较算法简单操作次数的数量级，数量级越大，算法时间复杂度越高。算法的时间复杂度就是用T（n）的数量级来表示，记作O（f（n））。52/21intmain(){ inti,j,n,m=0; scanf("%d",&n); for(i=0;i<n;i++) for(j=0;j<n;j++) m++; printf("%d",m); return0;}基本操作【例1.2】分析下面算法的时间复杂度53/21这种简化的时间复杂度分析方法得到的结果相同，但分析过程更简单。

解：该算法中的基本操作是两重循环中最深层的语句m++，分析它的频度，即：

54/21

所以，该算法的时间复杂度为

55/21请自行计算如下算法的时间复杂度voidfun(intn){ inti,x=0; for(i=1;i<n;i++) for(j=i+1;j<=n,j++) x++;}下列程序段的时间复杂度是（）。A.O(log2n) B.O(n)C.O(nlog2n) D.O(n2)count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j++)count++;说明：本题为2014年全国考研题基本操作示例56/21解：该算法中的基本操作是两重循环中最深层的语句count++，由于外层循环和内层循环之间没有交叉，符合乘积关系，先分析外层循环的执行次数为：

...满足条件内层循环的执行次数为：所以整个算法的时间复杂度为：57/21voidfun(intn) { inti,x=0; for(i=1;i<n;i++) for(j=i+1;j<=n,j++) x++; }58/21【例1.3】分析下面算法的时间复杂度基本操作解：该算法中的基本操作是两重循环中最深层的语句x++，分析它的执行次数，即：

所以，该算法的时间复杂度为voidfn(intn){ inty=0; while(y*y<=n) y++;}59/21【例1.4】分析下面算法的时间复杂度

所以，该算法的时间复杂度为解：该算法中的基本操作是y++，分析它的执行次数与y值的变化关系，再根据条件约束，计算出执行次数与n的关系，进而分析该算法的时间复杂度。...满足条件y*y<=n

所以，voidfun1(intn){ i=1,k=100; while(i<=n) { k=k+1; i+=2; }}60/21【例1.6】分析下面算法的时间复杂度解：该算法中的基本操作是while循环中最深层的语句i+=2，分析该循环的执行次数为：...满足条件所以整个算法的时间复杂度为：intFind(inta[],ints,intt,intx){intm=(s+t)/2;if(s<=t){if(a[m]==x)returnm;elseif(x<a[m])returnFind(a,s,m-1,x);elsereturnFind(a,m+1,t,x);}return-1;}61/21【例1.7】以折半查找为例分析递归算法的时间复杂度解：分析递归算法的时间复杂度前先要分析该算法的执行次数递归方程。该算法的执行次数递归方程为：T(n)=1

当n=1T(n)=T(n/2)+1

当n>1只有当n=1时，即才能到达出口，使得此时，所以，整个算法的时间复杂度为：于是：62/21

各种不同算法时间复杂度的比较关系如下：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)

算法时间性能比较：假如求同一问题有两个算法：A和B，如果算法A的平均时间复杂度为O(n)，而算法B的平均时间复杂度为O(n2)。一般情况下，认为算法A的时间性能好比算法B。指数阶多项式阶63/21某算法的时间复杂度为O(n2)，表明该算法的（）。A.问题规模是n2 B.执行时间等于n2

C.执行时间与n2成正比 D.问题规模与n2成正比示例答：C。64/21下面几种算法时间复杂度中，时间复杂度最高的是（）。A.O(nlog2n) B.O(n2)C.O(n) D.O(2n)示例答：D。65/21

若一个算法的空间复杂度为O(1)，则称此算法为原地工作或就地工作算法。空间复杂度：用于量度一个算法运行过程中临时占用的存储空间大小。一般也作为问题规模n的函数，采用数量级形式描述，记作：

S(n)=O(g(n))

66/21算法空间复杂度分析算法的空间复杂度是指（）。A.算法中输入数据所占用的存储空间的大小B.算法本身所占用的存储空间的大小C.算法中所占用的所有存储空间的大小D.算法中需要的辅助变量所占用存储空间的大小答：D。67/21某算法的空间复杂度为O(1)，则（）。A.该算法执行不需要任何辅助空间B.该算法执行所需辅助空间大小与问题规模n无关C.该算法执行不需要任何空间D.该算法执行所需空间大小与问题规模n无关答：B。68/21分析如下算法的空间复杂度。解：算法中临时分配的变量个数与问题规模n无关，所以空间复杂度均为O(1)。intfun(intn){inti，j，k，s;

s=0;

for(i=0;i<=n;i++)for(j=0;j<=i;j++)

for(k=0;k<=j;k++)

s++;

return(s);}临时占用的存储空间：函数体内分配的空间示例69/212.1线性表的定义和操作2.2线性表的顺序表示70/472.3线性表的链式表示2.4有序表CONTENTS提纲第2章线性表线性表是一个具有相同特性的数据元素的有限序列。

2.1.1线性表的定义线性表中所含元素的个数叫做线性表的长度，用n表示，n≥0。n=0时，表示线性表是一个空表，即表中不包含任何元素。有穷性：数据元素个数是有限的。一致性：所有元素性质相同，即属于同一数据类型。序列性：数据元素由逻辑序号唯一确定。一个线性表中可以有相同值的元素。逻辑关系：元素之间为1对1的关系。71/472.1线性表的定义和操作(a1，a2，…，ai，ai+1，…，an)ai（1≤i≤n）表示第i（i表示逻辑位序）个元素。表头元素表尾元素(a1，a2，…，ai，ai+1，…，an)72/47线性表的逻辑表示为：

一个汽车线性表

一个小人线性表

不胜枚举73/47线性表是客观事物的抽象

初始化线性表InitList(&L)：构造一个空的线性表L。

销毁线性表DestroyList(&L)：释放线性表L占用的内存空间。

判线性表是否为空表ListEmpty(L)：若L为空表，则返回真，否则返回假。

求线性表的长度ListLength(L)：返回L中元素个数n。

线性表的9个基本运算如下:74/472.1.2线性表的基本操作

输出线性表DispList(L)：线性表L不为空时，顺序显示L中各结点的值域。

求线性表L中指定位置的某个数据元素GetElem(L，i，&e)：用e返回L中第i（1≤i≤n）个元素的值。

定位查找LocateElem(L，e)：返回L中第一个值域与e相等的逻辑位序。若这样的元素不存在，则返回值为0。

插入一个数据元素ListInsert(&L，i，e)：在L的第i（1≤i≤n）个元素之前插入新的元素e，L的长度增1。

删除数据元素ListDelete(&L，i，&e)：删除L的第i（1≤i≤n）个元素，并用e返回其值，L的长度减1。75/47ADTList{

数据对象：D={ai|1≤i≤n，n≥0，ai为ElemType类型}//ElemType是自定义类型标识符

数据关系：R={<ai，ai+1>|ai、ai+1∈D，i=1，…，n-1}

基本运算：9个运算}76/47线性表的抽象数据类型：数据基本运算1基本运算n…应用程序程序员可以直接使用它来存放数据作为存放数据的容器。程序员可以直接使用它的基本运算

完成更复杂的功能。线性表的作用实现了的线性表77/47示例一个整数线性表L=(1,3,1,4,2)ListLength(L)

返回5ListEmpty(L)

返回falseGetElem(L，3，e)

e=1LocateElem(L，1)

1ListInsert(L，4，5)L=(1,3,1,5,4,2)ListDelete(L，3)L=(1,3,5,4,2)78/47线性表的知识结构线性表的概念线性表的存储结构线性表的应用特殊的线性表—有序表顺序存储结构顺序表中基本运算的实现链式存储结构单链表单链表中基本运算的实现双链表双链表中基本运算的实现循环链表循环链表中基本运算的实现线性表ADT=

逻辑结构+运算定义（运算描述）79/47

线性表顺序存储结构：把线性表中的所有元素按照顺序存储方法进行存储。2.2.1顺序表的定义按逻辑顺序依次存储到存储器中一片连续的存储空间中。80/472.2线性表的顺序表示线性表(a1,a2,…,ai,…,an)直接映射a1a2…ai…an…nMaxSize-101i-1n-1datalength顺序表逻辑结构存储结构81/47typedefstruct{ElemTypedata[MaxSize];

intlength;}SqList; //顺序表类型其中data成员存放元素，length成员存放线性表的实际长度。顺序表类型声明：说明：注意逻辑位序和物理位序相差1。这里，假设ElemType为int类型82/47示例一个整数线性表L=(1,3,1,4,2)MaxSize-113142…5012datalength顺序表L34L.data[1]L.length83/47L->data[1]L->lengthMaxSize-113142…5012datalength顺序表指针L3484/47一个整数线性表L=(1,3,1,4,2)voidCreateList(SqList*&L，ElemTypea[]，intn)

//整体建立顺序表{inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}1、建立顺序表a[0..n-1]

顺序表L─整体创建顺序表。传递顺序表指针85/472.2.2顺序表基本运算的实现顺序表？？？L1010

顺序表指针的含义顺序表的空间顺序表LSqList*L;L=(SqList*)malloc(sizeof(SqList));1010通过顺序表指针L操作顺序表86/47算法参数说明

顺序表指针引用voidCreateList(SqList*&L，ElemTypea[]，intn)引用参数：将执行结果回传给实参引用符号“&”放在形参L的前面。输出型参数均为使用“&”，不论参数值是否改变。引用参数SqList*&L

将顺序表地址L回传给对应的实参87/47voidCreateList(SqList*&L，ElemTypea[]，intn){inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}voidmain(){SqList*h;intn=5;ElemTypea[]={1,3,1,4,2};

CreateList(h,a,n);

//对顺序表h进行其他操作}？？？h131425Lh指向有效顺序表，可以操作88/47如果使用引用：voidCreateList(SqList*L，ElemTypea[]，intn){inti=0,k=0;

L=(SqList*)malloc(sizeof(SqList));

while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}

L->length=k;}为什么用顺序表指针引用如果不使用引用：voidmain(){SqList*h;intn=5;ElemTypea[]={1,3,1,4,2};

CreateList(h,a,n);

//对顺序表h进行其他操作}？？？h131425Lh仍然是垃圾值，操作错误89/47（1）初始化线性表InitList(L)

构造一个空的线性表L。实际上只需将length成员设置为0即可。

voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));

//分配存放线性表的顺序表空间

L->length=0;}90/472、顺序表基本运算算法voidDestroyList(SqList*&L){

free(L);}（2）销毁线性表DestroyList(L)

释放线性表L占用的内存空间。Lfree(L)释放L所指向的空间顺序表顺序表采用指针传递，有两个优点：更清楚看到顺序表创建和销毁过程（malloc/free）；在算法的函数之间传递更加节省空间（在函数体内不必创建值形参即整个顺序表的副本）。91/47boolListEmpty(SqList*L){

return(L->length==0);}（3）判定是否为空表ListEmpty(L)

返回一个值表示L是否为空表。若L为空表，则返回true，否则返回false。92/47intListLength(SqList*L){

return(L->length);}（4）求线性表的长度ListLength(L)返回顺序表L的长度。实际上只需返回length成员的值即可。93/47（5）输出线性表DispList(L)

该运算当线性表L不为空时，顺序显示L中各元素的值。

voidDispList(SqList*L){for(inti=0;i<L->length;i++)printf("%d"，L->data[i]);printf("\n");}94/47boolGetElem(SqList*L，inti，ElemType&e){

if(i<1||i>L->length)

returnfalse;

e=L->data[i-1];

returntrue;}（6）求某个数据元素值GetElem(L，i，e)

该运算返回L中第i（1≤i≤ListLength(L)）个元素的值，存放在e中。体现顺序表的随机存取特性本算法的时间复杂度为O(1)。95/47intLocateElem(SqList*L，ElemTypee){inti=0;while(i<L->length&&L->data[i]!=e)

i++;

if(i>=L->length)return0;elsereturni+1;}（7）按元素值查找LocateElem(L，e)

顺序查找第1个值域与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。96/47在顺序表L的第i（1≤i≤ListLength(L)+1）个位置上插入新的元素e。

01i-1n-1nia1a2…aiai+1…anei+1插入完成lengthnn+197/47（8）插入数据元素ListInsert(L，i，e)boolListInsert(SqList*&L，inti，ElemTypee){intj;

if(i<1||i>L->length+1||L->length==MaxSize)returnfalse; //参数错误时返回false

i--; //将顺序表逻辑序号转化为物理序号

for(j=L->length;j>i;j--) //将data[i..n]元素后移一个位置

L->data[j]=L->data[j-1];

L->data[i]=e; //插入元素e

L->length++; //顺序表长度增1

returntrue; //成功插入返回true}a1a2…ai…an…ai+1ian-1anai+1eai98/47

对于本算法来说，元素移动的次数不仅与表长L->length=n有关，而且与插入位置i有关：

算法最好时间复杂度为O(1)算法最坏时间复杂度为O(n)当i=1时，移动次数为n，达到最大值。当i=n+1时，移动次数为0；99/47该运算删除顺序表L的第i（1≤i≤ListLength(L)）个元素。

01i-1n-1ia1a2…ai+1…anaien-2an-1lengthnn-1删除完成100/47（9）删除数据元素ListDelete(L，i，e)boolListDelete(SqList*&L，inti，ElemType&e){intj;

if(i<1||i>L->length||L->length==0)

//参数错误时返回falsereturnfalse;

i--; //将顺序表逻辑序号转化为物理序号

e=L->data[i];

for(j=i;j<L->length-1;j++) //将data[i..n-1]元素前移

L->data[j]=L->data[j+1];

L->length--; //顺序表长度减1

returntrue; //成功删除返回true}a1a2…ai…an…ai+1ianai+1ai+2101/47#include<stdio.h>#include<malloc.h>#defineMaxSize50typedefintElemType;typedefstruct{ElemTypedata[MaxSize]; //存放顺序表元素

intlength; //存放顺序表的长度}SqList; //顺序表的类型//包含前面的9个基本运算函数102/47将顺序表类型声明及其基本运算函数放在sqlist.cpp文件中：#include"sqlist.cpp" //包含顺序表基本运算算法voidmain(){SqList*L;printf("初始化L\n");InitList(L);printf("ListEmpty(L)=%d\n",ListEmpty(L));printf("L的位置1插入元素1\n");ListInsert(L,1,1);printf("L的位置2插入元素3\n");ListInsert(L,2,3);printf("L的位置3插入元素1\n");ListInsert(L,3,1);printf("L的位置4插入元素4\n");ListInsert(L,4,4);printf("L的位置5插入元素2\n");ListInsert(L,5,2);printf("L:");DispList(L);printf("ListLength(L)=%d\n",ListLength(L));printf("ListEmpty(L)=%d\n",ListEmpty(L));inte;GetElem(L,3,e);printf("L的第3个元素:%d\n",e);printf("第1个值为1的元素的逻辑序号:%d\n",LocateElem(L,1));printf("L的位置4插入元素5\n");ListInsert(L,4,5);printf("L:");DispList(L);printf("删除第3个元素\n");ListDelete(L,3,e);printf("L:");DispList(L);printf("销毁L\n");DestroyList(L);}103/47顺序表存储结构特征顺序表元素操作方式顺序表9个基本运算算法设计104/47

顺序表应用算法设计：数据采用顺序表存储，利用顺序表的基本操作来完成求解任务。105/473、顺序表的应用示例

【例2-1】假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于a的元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。106/47解法一：设删除L中所有值等于a元素后的顺序表为L1，显然L1包含在L中，为此L1重用L的空间。扫描顺序表L，重建L中只包含不等于a的元素，算法过程是置k=0（k用来记录新表中的元素个数），用i从左到右扫描L中所有的元素，当i指向的元素为a时跳过它；否则将其放置在k的位置，即L->data[k]=L->data[i],k++。01baaa删除所有x=a的元素（k记录保留的元素个数，初值=0）：2345k=3，L->length=k=3clength63删除完成dk=0k=1k=2k=3以整体建立顺序表算法为基础！107/47删除顺序表中所有值为x的元素（方法1）演示voiddelnode1(SqList*&L，charx){intk=0，i; //k记录值不等于x的元素个数

for(i=0;i<L->length;i++)if(L->data[i]!=x) //若当前元素不为x，将其插入A中

{L->data[k]=L->data[i];k++; //不等于x的元素增1

}

L->length=k;

//顺序表L的长度等于k}108/47对应的算法如下：

解法二：扫描顺序表L，用i从左到右扫描L中的所有元素，用k记录L中当前等于a的元素的个数，一边扫描L一边统计当前k的值，当i指向的元素为a时k增加1；否则将不为a的元素前移k个位置，即L->data[i-k]=L->data[i]。最后修改L的长度。算法如下：109/4701baada删除所有x=a的元素（k记录删除的元素个数，初值=0）2345k=0，前移0个位置ck=1k=1，前移1个位置k=2k=2，前移2个位置k=3顺序表长度=6-k=3length63删除完成110/47删除顺序表中所有值为x的元素（方法2）演示voiddelnode2(SqList*&L，charx){intk=0，i=0; //k记录值等于x的元素个数

while(i<L->length)

{if(L->data[i]==x) //当前元素值为x时k增1 k++;

else

//当前元素不为x时将其前移k个位置

L->data[i-k]=L->data[i];

i++;

}

L->length-=k; /顺序表L的长度递减k}111/47对应的算法如下：

【例2-2】设有一个整数顺序表L。设计一个算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该元素的前面，将所有大于它的元素移到该元素的后面。x无序整数序列≤xx>x112/470812273145536476809pivotijpivot=L->data[0]（基准）j从后向前找≤pivot的元素i从前向后找>pivot的元素3两者交换31

0

2

3

3

5

7

4

6

8113/47解法1voidpartition1(SqList*&L){inti=0，j=L->length-1;intpivot=L->data[0]; //以data[0]为基准while(i<j)

{while(i<j&&L->data[j]>pivot)

j--;

//从后向前扫描，找一个≤pivot的元素

while(i<j&&L->data[i]<=pivot)

i++; //从前向后扫描，找一个>pivot的元素if(i<j)

swap(L->data[i],L->data[j]);}

swap(L-data[0],L->data[i]);}对应的算法如下：114/47310012233345576476889pivot（基准）ij30812273145536476809pivot（基准）ijpivot=L->data[0]（基准）j从后向前找小于等于pivot的元素：前移i从前向后找大于pivot的元素：后移0

3

2

1

3

5

7

4

6

8算法时间复杂度为O(n)。115/47解法2voidpartition2(SqList*&L){inti=0，j=L->length-1;

ElemTypepivot=L->data[0]; //以data[0]为基准

while(i<j)

{while(j>i&&L->data[j]>pivot)

j--; //从右向左扫描，找≤pivot的data[j]

L->data[i]=L->data[j]; //将其放入data[i]处while(i<j&&L->data[i]<=pivot)

i++; //从左向右扫描，找>pivot的记录data[i]

L->data[j]=L->data[i]; //将其放入data[j]处}

L->data[i]=pivot; //放置基准}116/47对应的算法如下：线性表中每个元素有唯一的前驱元素和后继元素。2.3.1

单链表的定义1.链表概述117/552.3线性表的链式表示每个物理结点增加一个指向后继结点的指针域

单链表。每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

双链表。118/55学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901设计链式存储结构时，每个逻辑元素用一个结点单独存储，为了表示逻辑关系，增加指针域。线性表(a0,a1,…,ai,…,an-1

)映射逻辑结构存储结构带头结点单链表示意图a1a2an∧…L119/55typedefstructLNode//声明单链表结点类型{inflistdata;

structLNode*next;//指向后继结点}LinkNode;typedefstructinf{ intnum; charname[8];

charsex[4];

intglassno;}inflist;线性表(a0,a1,…,ai,…,an-1

)映射逻辑结构存储结构带头结点双链表示意图a1an∧…La2120/55顺序表：需要平均移动半个表的元素。链表：只需修改相关结点的指针域即可，这样既方便又省时。插入或删除操作121/55链表和顺序表的比较顺序表：具有随机存取特性。链表：不具有随机存取特性。122/55随机存取特性（查找序号i的元素的时间为O(1)）一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1（100%），而链表的存储密度小于1。存储密度=结点数据本身占用的空间结点占用的空间总量a18个字节4个字节存储密度=8/12=67%例如123/55存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比，即：顺序表：存储密度高。链表：存储密度相对较低。124/55存储密度单链表中结点类型LinkNode的声明如下:

typedefstructLNode

//声明单链表结点类型{intdata;

structLNode*next;//指向后继结点}

LinkNode;a125/552.3.2单链表上基本操作的实现a1a2an∧…第一个结点的操作和表中其他结点的操作相一致，无需进行特殊处理。无论链表是否为空，都有一个头结点，因此空表和非空表的处理也就统一了。单链表增加一个头结点的优点：带头结点单链表头结点首结点尾结点126/55当访问过一个结点后，只能接着访问它的后继结点，而无法访问它的前驱结点。ab…p…p是指针，*p是p指向的结点，为了简单，称p指向的结点为p结点127/55单链表的特点插入操作：将值为x的新结点s插入到p结点之后。特点：只需修改相关结点的指针域，不需要移动结点。（1）插入结点操作128/551、插入结点和删除结点操作abx…p…s

s->next=p->next

p->next=s插入操作语句描述如下：

s->next=p->next;

p->next=s;单链表插入结点演示p结点next的修改尽可能放在后面执行129/55删除操作：删除p结点之后的一个结点。特点：只需修改相关结点的指针域，不需要移动结点。130/55（2）删除结点操作abx…p…p->next=p->next->next删除操作语句描述如下：

p->next=p->next->next;

free(p->next);为了释放被删除结点，操作语句描述如下：

q=p->next;p->next=q->next;free(q);131/55单链表删除结点演示132/55structstudent*createlist(){structstudent*head;structstudent*q;//指向当前链表的最后一个结点structstudent*p;//新建结点intdata;head=(structstudent*)malloc(sizeof(structstudent));head->next=NULL;q=head;scanf("%d",&data);while(data!=9999){p=(structstudent*)malloc(sizeof(structstudent));//新建结点p->data=data;

p->next=q->next;q->next=p;//插入结点q=q->next;//保证q的逻辑完整性，q指向前链表的最后一个结点scanf("%d",&data);}returnhead;}整体建立单链表先考虑如何整体建立单链表。

a[0..n-1]带头结点的单链表L整体创建建立单链表的常用方法有两种。133/552、整体建立单链表从一个空表开始，创建一个头结点。依次读取字符数组a中的元素，生成新结点将新结点插入到当前链表的表头上，直到结束为止。注意：链表的结点顺序与逻辑次序相反。134/55（1）头插法建表voidList_Head(LNode*&L)//头插法{ LNode*s;intx; L=(LNode*)malloc(sizeof(LNode)); L->next=NULL; scanf("%d",&x); while(x!=9999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); }}135/55头插法建表算法如下：注意：链表的结点顺序与逻辑次序相同。从一个空表开始，创建一个头结点。依次读取字符数组a中的元素，生成新结点将新结点插入到当前链表的表尾上，直到结束为止。增加一个尾指针r，使其始终指向当前链表的尾结点136/55（2）尾插法建表voidList_Tail(LNode*&L)//尾插法

{ intx; L=(LNode*)malloc(sizeof(LNode)); LNode*s,*r=L; scanf("%d",&x); while(x!=9999){ s=(LNode*)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; scanf("%d",&x); } r->next=NULL;}137/55尾插法建表算法如下：（1）初始化线性表InitList(&L)

该运算建立一个空的单链表，即创建一个头结点。voidInitList(LinkNode*&L)

{L=(LinkNode*)malloc(sizeof(LinkNode));

//创建头结点

L->next=NULL;}∧L138/553、线性表基本运算在单链表上的实现

（2）销毁线性表DestroyList(&L)

释放单链表L占用的内存空间。即逐一释放全部结点的空间。

voidDestroyList(LinkNode*&L){

LinkNode*pre=L，*p=L->next;

//pre指向p的前驱结点

初始时L∧…prep139/55while(p!=NULL) //扫描单链表L

{free(pre); //释放pre结点

pre=p; //pre、p同步后移一个结点

p=pre->next;

}

free(pre); //循环结束时，p为NULL，pre指向尾结点，释放它}循环结束时L∧prep=NULL…140/55

（3）判断线性表是否为空表ListEmpty(L)

若单链表L没有数据结点，则返回真，否则返回假。

boolListEmpty(LinkNode*L){

return(L->next==NULL);}∧L空表的情况141/55（4）求线性表的长度ListLength(L)

返回单链表L中数据结点的个数。

intListLength(LinkNode*L){

intn=0;

LinkNode*p=L; //p指向头结点，n置为0（即头结点的序号为0）

初始时L∧…pn=0142/55while(p->next!=NULL)

{ n++; p=p->next;

}

return(n); //循环结束，p指向尾结点，其序号n为结点个数}循环结束时L∧pn为结点个数…143/55

（5）输出线性表DispList(L)

逐一扫描单链表L的每个数据结点，并显示各结点的data域值。

voidDispList(LinkNode*L){LinkNode*p=L->next; //p指向开始结点

while(p!=NULL) //p不为NULL，输出p结点的data域

{printf("%d"，p->data);

p=p->next; //p移向下一