教学课件：《数据结构》陈越

第1章概论【定义】“数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。”1/25§1引子[例1.1]该如何摆放书，才能让读者很方便地找到你手里这本《数据结构》？第1章概论【分析】2/25§1引子[方法1]随便放——任何时候有新书进来，哪里有空就把书插到哪里。[方法2]按照书名的拼音字母顺序排放。[方法3]把书架划分成几块区域，每块区域指定摆放某种类别的图书；在每种类别内，按照书名的拼音字母顺序排放。

查找效率极低！

有时插入新书很困难！

可能造成空间的浪费！第1章概论§1引子[例1.2]写程序实现一个函数PrintN，使得传入一个正整数为N的参数后，能顺序打印从1到N的全部正整数。

voidPrintN(intN){inti;

for(i=1;i<=N;i++)printf(“%d\n”,i);

return;}voidPrintN(intN){if(!N)return;PrintN(N–1);printf(“%d\n”,N);

return;}3/25第1章概论§1引子[例1.3]多项式的标准表达式可以写为：

f(x)=a0+a1x+a2x2+…+anxn现给定一个多项式的阶数

n，并将全体系数存放在数组a[]里。请写程序计算这个多项式在给定点x

处的值。[方法1]计算多项式函数值的直接法

doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/

inti;

doublep=a[0];

for(i=1;i<=n;i++) p+=a[i]*pow(x,i);

returnp;}[方法2]秦九韶法

f(x)=a0+x(a1+x(a2+…+x(an)…)doublef(intn,doublea[],doublex){/*计算阶数为n，系数为a[0]...a[n]的多项式在x点的值*/

inti;

doublep=a[n];

for(i=n;i>0;i--) p=a[i-1]+x*p;

returnp;}4/25秦九韶算法的计算速度明显比直接法快了一个数量级！为什么会这样？第1章概论§1引子5/25#include<stdio.h>#include<time.h>clock_tstart,stop;/*clock_t是clock()函数返回的变量类型*/doubleduration;/*记录被测函数运行时间，以秒为单位*/intmain(){/*不在测试范围内的准备工作写在clock()调用之前*/start=clock();/*开始计时*/function();/*把被测函数加在这里*/stop=clock(); /*停止计时*/duration=((double)(stop-start))/CLK_TCK;/*计算运行时间*/

/*其他不在测试范围的处理写在后面，例如输出duration的值*/

return0;}代码1.6测试函数function()的运行时间即使解决一个非常简单的问题，往往也有多种方法，且不同方法之间的效率可能相差甚远解决问题方法的效率跟数据的组织方式有关（如例1.1）跟空间的利用效率有关（如例1.2）跟算法的巧妙程度有关（如例1.3）第1章概论§1引子6/25第1章概论

数据对象：

计算机要处理的事物，如例1.1中“图书”

。§2.1术语定义

操作：处理事物的动作集合，如例1.1中的“查找”和“插入”，例1.2的函数“求值”等。

算法：

操作的实现方法，如例1.1的按字母序排放的“查找”和“插入”、例1.2的“直接法”和例1.3的“秦九韶法”等。

通常一个算法用一个函数来实现。

逻辑结构：数据对象的逻辑组织关系。分为“线性”、“树”和“图”。例1.1中按方法1来处理，就是把图书集看成是线性的结构；按方法3来处理，就是把图书集看成是树形的结构。

物理结构：数据对象信息在计算机内存中的存储组织关系。一般分为“顺序存储”和“链式存储”。7/25第1章概论

数据类型：

数据对象的类型确定了其“操作集”和“数据定义域”。§2.2抽象数据类型

抽象数据类型：

“抽象”的意思，是指我们描述数据类型的方法是不依赖于具体实现的，即数据对象集和操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。简而言之，抽象数据类型只描述数据对象集和相关操作集“是什么”，并不涉及“如何做到”的问题。8/25第1章概论[例1.4]“矩阵”的抽象数据类型定义§2.2抽象数据类型类型名称：Matrix数据对象集：一个M

N的矩阵A。操作集：对于任意矩阵A、B、C

Matrix，以及正整数i、j、M、N，以下仅列出几项有代表性的操作。1）MatrixCreate(intM,intN)：返回一个M

N的空矩阵；2）

intGetMaxRow(MatrixA)：返回矩阵A的总行数；3）intGetMaxCol(MatrixA)：返回矩阵A的总列数；4）ElementTypeGetEntry(MatrixA,inti,intj)：返回矩阵A的第i行、第j列的元素；5）MatrixAdd(MatrixA,MatrixB)：如果A和B的行、列数一致，则返回矩阵C=A+B，否则返回错误标志；6）MatrixMultiply(MatrixA,MatrixB)：如果A的列数等于B的行数，则返回矩阵C=AB，否则返回错误标志；7）……9/25【定义】一个算法是解决某一类问题的步骤的描述。一般而言，算法应该符合以下五项要求：(1)输入：它接受一些输入（有些情况下不需要输入）；(2)输出：至少产生一个输出；(3)确定性：算法的每一步必须有充分明确的含义，不可以有歧义；(4)有限性：算法是一个有限指令集，并一定在有限步骤之后终止；(5)

可行性：算法的每一步必须在计算机能处理的范围之内。第1章概论§3.1算法定义

另外，算法的描述可以不依赖于任何一种计算机语言以及具体的实现手段。可以用自然语言、流程图等方法来描述。

但是，用某一种计算机语言进行伪码描述往往使算法容易被理解，本书即采用C语言的部分语法作为描述算法的工具。10/25〖例〗选择法排序：把n个整数从小到大排序。思想：从余下的未排序的部分整数中，挑选最小整数放在前面已排序部分的后面.如何进行排序?

哪里?voidSelectionSort(intList[],intN){/*将N个整数List[0]...List[N-1]进行非递减排序*/

for(i=0;i<N;i++){MinPosition=ScanForMin(List,i,N–1);

/*从List[i]到List[N–1]中找最小元，并将其位置赋给MinPosition*/Swap(List[i],List[MinPosition]);

/*将未排序部分的最小元换到有序部分的最后位置*/}}选择排序=找最小整数+交换至合适位置.第1章概论§3.1算法例子11/25

具体衡量、比较算法优劣的指标主要有两个：

空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。第1章概论§3.2算法复杂度

时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。

什么是“好”的算法？○例1.2的实现函数PrintN的递归算法S(n)太大。○例1.3的秦九韶算法的T(n)比较小。12/25第1章概论§3.2算法复杂度

例1.2的实现函数PrintN的递归算法的S(n)太大：

S(n)=c·n其中：n是需要打印的整数的个数，是变量；c是1个单位的内存空间占用存储单元的长度，为固定常数。

例1.3的秦九韶算法的T(n)比较小：T1(n)=c

·n其中：n是多项式的阶数，是变量；c是执行1次加法和乘法需要的时间，为固定常数。

而简单直接算法的T(n)比较大：T2(n)=c1n2+c2n，其中：n是多项式的阶数，是变量；c1是执行1/2次乘法需要的时间；c2是执行1次加法和1/2次乘法需要的时间，都是固定常数。13/25第1章概论§3.2算法复杂度

我们经常关注下面两种复杂度：

最坏情况复杂度：

Tworst(n)

平均复杂度：

Tavg(n)

显然:Tavg(n)≤Tworst(n)。对Tworst(n)

的分析往往比对

Tavg(n)的分析容易。14/25

如果:程序A执行了(3n+4)步，程序B执行了(2n+2)步，A一定比B慢吗？

No！

Why?第1章概论§3.3复杂度的渐进表示法

如何来“度量”一个算法的时间复杂度呢？

首先，它应该与运行该算法的机器和编译器无关；

其次，它应该与要解决的问题的规模n有关；（有时，描述一个问题的规模需要多个参数）

再次，它应该与算法的“1步”执行需要的工作量无关！

所以，在描述算法的时间性能时，人们只考虑宏观渐近性质，即当输入问题规模n“充分大”时，观察算法复杂度随着n的“增长趋势”：当变量n不断增加时，解决问题所需要的时间的增长关系。

比如：线性增长T(n)=c·n即问题规模n增长到2倍、3倍……时，解决问题所需要的时间T(n)也是增长到2倍、3倍……（

与c无关

）

平方增长：T(n)=c·n2即问题规模n增长到2倍、3倍……时，解决问题所需要的时间T(n)增长到4倍、9倍……（

与c无关

）15/25第1章概论

引入下面几种数学符号：[定义1.1]T(n)=O(f(n))表示存在常数c>0,n0>0，使得当n≥n0

时有

T(n)≤cf(n)

例1.3中秦九韶算法的时间复杂度是O(n)

，

而简单直接法的时间复杂度是O(n2)

。[定义1.2]T(n)=Ω(g(n))表示存在常数c>0,n0>0，使得当n≥n0

时有

T(n)≥cg(n)§3.3复杂度的渐进表示法[定义1.3]T(n)=Θ(h(n))表示T(n)=O(h(n))

同时T(n)=Ω(h(n))16/25第1章概论

常用函数增长表§3.3复杂度的渐进表示法输入规模n函数124816321111111log2

n012345n12481632nlog2

n0282464160n21416642561024n318645124096327682n2416256655364294967296n!122440326209227898800026313

103317/252nn2nlognnlognfn第1章概论§3.3复杂度的渐进表示法18/25s=微秒=10-6

秒ms=毫秒=10-3

秒sec=秒min=分yr=年hr=小时d=天n第1章概论§3.3复杂度的渐进表示法19/25第1章概论

对给定的算法做渐进分析时，有几个小窍门：(1)若两段算法分别有复杂度T1(n)=O(f1(n))

和

T2(n)=O(f2(n))，▲那么两段算法串联在一起的复杂度:

T1(n)+T2(n)=max(O(f1(n)),O(f2(n)))

▲那么两段算法嵌套在一起的复杂度:

T1(n)×T2(n)=O(f1(n)×f2(n))§3.3复杂度的渐进表示法(2)若

T(n)是关于n的k阶多项式，那么T(n)=Θ(nk)

(3)一个循环的时间复杂度等于循环次数乘以循环体代码的复杂度。例如下面循环的复杂度是O(N)：for(i=0;i<N;i++){x=y*x+z;k++;}(1)若干层嵌套循环的时间复杂度等于各层循环次数的乘积再乘以循环体代码的复杂度。例如下列2层嵌套循环的复杂度是O(N2)：for(i=0;i<N;i++)

for(j=0;j<N;j++){x=y*x+z;k++;}(2)if-else

结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大。即对结构：if(P1)/*P1的复杂度为

O(f1)*/P2;/*P2的复杂度为

O(f2)*/

elseP3;/*P3的复杂度为

O(f3)*/总复杂度为max(O(f1),O(f2),O(f3))。20/25〖问题〗给定n个整数(可以是负数)的序列{a1,a2,…,an},求函数f(i,j)=max(0,)的最大值。

若全部整数都是负数，则最大子列和为0.算法1intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j,k;/*1*/ MaxSum=0;/*初始化最大子列和*//*2*/

for(i=0;i<N;i++)/*i是子列左端位置*//*3*/

for(j=i;j<N;j++){/*j是子列右端位置*//*4*/ ThisSum=0;/*ThisSum是从A[i]到A[j]的子列和*//*5*/

for(k=i;k<=j;k++)/*6*/ ThisSum+=A[k];/*7*/

if(ThisSum>MaxSum)/*如果刚得到的这个子列和更大*//*8*/ MaxSum=ThisSum;/*则更新结果*/ }/*i，j循环结束*//*9*/

returnMaxSum;}T(N)=O(N3)教材p.15有分析.第1章概论§4应用实例：最大子列和问题21/25算法2intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,i,j;/*1*/ MaxSum=0;/*初始化最大子列和*//*2*/

for(i=0;i<N;i++){/*i是子列左端位置

*//*3*/ ThisSum=0;/*ThisSum是从A[i]到A[j]的子列和

*//*4*/

for(j=i;j<N;j++){/*j是子列右端位置*//*5*/ ThisSum+=A[j];/*对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可*//*6*/

if(ThisSum>MaxSum)/*如果刚得到的这个子列和更大*//*7*/ MaxSum=ThisSum;/*则更新结果*/

}/*j循环结束*/ }/*i循环结束*//*8*/

returnMaxSum;}T(N)=O(N2)第1章概论§4应用实例：最大子列和问题22/25算法3分治法4

35

2

126

2治分45626811T(N/2)T(N/2)O(N)T(N)=2T(N/2)+cN,T(1)=O(1)=2[2T(N/22)+cN/2]+cN=2kO(1)+ckN此处

N/2k=1=O(NlogN)结论对N

2k同样正确程序在教材p.16-17第1章概论§4应用实例：最大子列和问题23/25该算法的核心思想是基于下面的事实：如果整数序列

{a1,a2,…,an}的最大和子列是

{ai,ai+1,…,aj}，那么必定有

对任意i≤l≤j

都成立。因此，一旦发现当前子列和为负，则可以重新开始考察一个新的子列。算法4“在线”算法intMaxSubsequenceSum(constintA[],intN){ intThisSum,MaxSum,j;/*1*/ ThisSum=MaxSum=0;/*2*/

for(j=0;j<N;j++){/*3*/ ThisSum+=A[j];/*4*/

if(ThisSum>MaxSum)/*5*/ MaxSum=ThisSum;/*6*/

else

if(ThisSum<0)/*7*/ ThisSum=0; }/*endfor-j*//*8*/

returnMaxSum;}T(N)=O(N

)序列A[]仅需扫描一遍！

13

24

616

1

1324

6任何时刻,“在线”算法都可以对已经读入的数据序列给出正确的最大子列和答案第1章概论§4应用实例：最大子列和问题24/25-241-63-150.000340.000630.003330.030420.298320.000660.004860.058430.686318.01130.000450.011121.1233111.13NA0.001030.47015448.77NANAO(N)O(N

logN)O(N2)O(N3)时间复杂性4321算法N=10N=100N=1,000N=10,000N=100,000子列大小

上述4种算法用于求最大子列和所需的运行时间的比较(单位：秒)注:不包括输入子列的时间.NA–NotAcceptable,不可接受的时间第1章概论§4应用实例：最大子列和问题25/25第2章实现基础§2.1引子

还是为每个具体应用都编一个程序?

类型名称：数据集合的基本统计

数据对象集：集合S={，

，…，}

操作集：ElementTypeAverage(S)：求S中元素的平均值；ElementTypeMax(S)：求S中元素的最大值；ElementTypeMin(S)：求S中元素的最小值；ElementTypeMedian(S)：求S中元素的中位数。

从不同的应用中抽象出共性的数据组织与操作方法？[例2.1]在日常数据处理中经常碰到的问题是需要对一组数据进行基本的统计分析。比如，分析一个课程班学生的平均成绩、最高成绩、最低成绩、中位数、标准差等。同样的统计要求也可能发生在其他领域。1/25

如何利用程序设计语言实现上述抽象类型？第2章实现基础§2.1引子1.数据存储

C语言（包括其他高级语言）提供了数组、结构、链表等。

数据结构的存储实现跟所需要的操作密切相关。

在数据结构里，是利用数组和链表方式来实现的，包括很复杂的数据结构，如图、树等。2.操作实现流程控制语句，即分支控制语句（如if-else、switch语句）、循环控制语句（如for、while、do-while语句）。

此外，还有模块化的程序设计方法——函数ElementTypeAverage(ElementTypeS[],intN){/*求集合元素的平均值。集合元素存放在数组S中，数组大小为N*/

int

i;ElementTypeSum=0;

for(i=0;i<N;i++)Sum+=S[i];/*将数组元素累加到Sum中*/

returnSum/N;}2/25[方法2]基于问题分解

相近的另一个问题是：求集合中的第K大整数。

当K=

N/2

时，集合的第K大整数就是中位数。

第2章实现基础§2.1引子

求中位数Median(S)[方法1]

基于排序。首先将集合S从大到小排序，第

N/2

（大于等于N/2的最小整数）个元素就是中位数。

求解集合第K大整数问题的一种递归思路是：SN个元素S1N1个元素S2N2个元素元素>=e元素<e

当K=N1时，

第K大整数就是e。

当K<N1时，第K大整数是在S1中的第K大整数。

当K>N1时，第K大整数是在S2中的第(K-N1)大整数。

比较慢！3/25ElementTypeKthLargest(ElementTypeS[],intK){选取S中的第一个元素e;根据e将集合S分解为大于等于e的元素集合S1和小于e的元素集合S2;while(|S2|==0)另选一个

e;if(|S1|>K)returnKthLargest(S1，K);elseif(|S1|<K)returnKthLargest(S2，K-|S1|);else

returne;}[例2.2]求集合{659821734}的中位数。【分析】由于该集合有9个元素，所以中位数应该是集合从大到小排序后的第

9/2

=5个元素。

首先，选取集合的第一个元素6，根据这个元素从集合中分解出S1={6，9，8，7}，S2={5，2，1，3，4}。由于|S1|=4<5，所以该中位数应该在集合S2中，且是S2中第(5–4=1)大整数。

继续选取S2中的第一个整数5，将S2分解出两个集合S1’={5}，S2’={2,1,3,4}。由于|S1’|=1，所以5就是S2集合的第1大整数，也就是集合{659821734}的中位数。第2章实现基础§1引子4/25第2章实现基础§2数据存储基础

变量是数据存储的基本单位。变量的类型决定了存储和操作。

几种基本的数据类型：整型、实型（浮点型）、字符型等。

提供了构造数据类型：数组、结构、指针等。数组数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，用数组名和下标可以唯一地确定数组元素。[例2.3]求集合元素的最大值。集合元素存放在数组A中，数组大小为N。floatMax(floatA[],intN){/*求N个元素数组中的最大值*/

floatCurMax=A[0];

inti;

for(i=1;i<N;i++)

if(A[i]>CurMax)CurMax=A[i];

returnCurMax;}5/25指针第2章实现基础§2数据存储基础

指针是C语言中一个非常重要的概念。使用指针可以对复杂数据进行处理，能对计算机的内存进行分配控制，在函数调用中使用指针还可以返回多个值。⑴指针与数组

数组名是数组中第1个元素（下标为0）的地址，可以看作是常量指针，不能改变指针常量（数组名）的值。⑵用指针实现内存动态分配①分配函数void*malloc(unsignedsize)。②释放函数voidfree(void*ptr)。6/25结构结构类型定义的一般形式为：struct

结构名{

类型名结构成员名1;

类型名结构成员名2;

……

类型名结构成员名n;};第2章实现基础§2数据存储基础【定义】结构类型把一些可以是不同类型的数据分量聚合成一个整体。同时，结构又是一个变量的集合，可以单独使用其变量成员。结构变量的使用使用结构变量就是对其成员进行操作。格式为：结构变量名.结构成员名。此外，结构变量不仅可以作为函数参数，也可以作为函数的返回值。结构数组：结构与数组的结合结构指针：指向结构的指针（1）用*方式访问，形式：（*结构指针变量名）.结构成员名（2）用指向运算符“->”访问指针指向的结构成员，形式：结构指针变量名->结构成员名对结构数组元素成员的引用是通过使用数组下标与结构成员操作符“.”相结合的方式来完成的，其一般格式为：结构数组名[下标].结构成员名7/25共用体【定义】共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。第2章实现基础§2数据存储基础共用体类型定义的一般形式为：union共用体名{

类型名成员名1;

类型名成员名2;

……

类型名成员名n;};

各个成员变量在内存中都使用同一段存储空间，因此共用体变量的长度等于最长的成员的长度。

共用体的访问方式同结构体类似。intmain(){

unionkey{

intk;

charch[2];}u;u.k=258；printf(“%d%d\n”,u.ch[0],u.ch[1]);return0;}0000001000000001

u.k=258的二进制表示：u.ch[0]=2u.ch[1]=18/25链表

链表是一种重要的基础数据结构，也是实现复杂数据结构的重要手段。它不按照线性的顺序存储数据，而是由若干个同一结构类型的“结点”依次串接而成的，即每一个结点里保存着下一个结点的地址（指针）。

链表又分单向链表，双向链表以及循环链表等。单向链表的结构使用结构的嵌套来定义单向链表结点的数据类型。如：structNode{ElementTypeData;

structNode*Next;};第2章实现基础§2数据存储基础structNode*p;p=(structNode*)malloc(sizeof(structNode));9/25head……（1） 插入结点(p之后插入新结点t)单向链表的常见操作（2） 删除结点第2章实现基础§2数据存储基础ptt->Next=p->Next;p->Next=t;

head……pt=p->Next;p->Next=t->next;

10/25（3）单向链表的遍历p=head;while(p!=NULL){……处理p所指的结点信息；

……p=p->Next;}（4） 链表的建立

有两种常见的插入结点方式：（1）在链表的头上不断插入新结点；（2）在链表的尾部不断插入新结点。如果是后者，一般需要有一个临时的结点指针一直指向当前链表的最后一个结点，以方便新结点的插入。第2章实现基础§2数据存储基础11/25双向链表如果将双向链表最后一个单元的Next指针指向链表的第一个单元，而第一个单元的Previous指针指向链表的最后一个单元，这样构成的链表称为双向循环链表。第2章实现基础§2数据存储基础structNode{ElementTypeData;

structNode*Next;

structNode*

Previous;};12/25

双向链表的插入、删除和遍历基本思路与单向链表相同，但需要同时考虑前后两个指针。A1A2A3AN…headpt第2章实现基础§2数据存储基础structDNode{ ElementTypeData;

structDNode*Next;

structDNode*Previous;}*p,*t;指针操作顺序：①t->Previous=p;②t->Next=p->Next;③p->Next->Previous=t;④p->Next=t;①②③④13/25[例2.4]给定一个单链表L，请设计函数Reverse将链表L就地逆转，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素……【分析】基本思路是：

利用循环，从链表头开始逐个处理。

如何把握住循环不变式。（循环不变式表示一种在循环过程进行时不变的性质，不依赖于前面所执行过程的重复次数的断言。）

在每轮循环开始前我们都面临两个序列，其中p是一个待逆转的序列，而q是一个已经逆转好的序列，如下图。

每轮循环的目的是把p中的第一个元素插入到q的头上，使这轮循环执行好后，p和q还是分别指向新的待逆转序列和已经逆转好的序列。第2章实现基础§2数据存储基础p->Next=q;q=p;t……qpt=p->Next;p->Next=q;q=p;p=t;

structNode*Reverse(structNode*L){structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){

t=p->Next;p->Next=q;q=p;

p=t;

}

returnq;}14/25类型定义typedef第2章实现基础§2数据存储基础除了使用C语言提供的标准类型和自己定义的一些结构体、枚举等类型外，还可以用typedef语句来建立已经定义好的数据类型的别名。typedef

原有类型名

新类型名typedef

structNode*NodePtr;这样，Reverse函数头就可以写成：NodePtrReverse(NodePtrL)NodePtrReverse(NodePtrL)/*structNode*Reverse(structNode*L)*/{structNode*p,*q,*t;

p=L，q=NULL;

while(p!=NULL){

t=p->Next;p->Next=q;q=p;

p=t;

}returnq;}15/25第2章实现基础§3流程控制基础顺序结构是一种自然的控制结构，通过安排语句或模块的顺序就能实现。C语言为分支控制提供了if-else和switch两类语句，为循环控制提供了for、while和do-while三类语句。

三种基本的控制结构是顺序、分支和循环。函数定义函数调用函数递归语句级控制单位级控制16/25[例2.5]求100到200之间的所有素数。[分析]可以设定两重循环：大循环（外层循环）控制整数i在100到200之间变化（用for语句），而小循环（内层循环）则用来判别i是否是素数（用while语句）。第2章实现基础§3流程控制基础intmain(){

inti,j;

for(i=100;i<=200;i++){/*外层循环*/

j=2;

while

(j<i&&i%j!=0)j++;

/*内层循环,判别i是否是素数*/

if(j==i)printf(“%d”,i);

/*j==i说明在上面的while循环中i都不能被j整除，因此i是素数*/}return

0;}17/25函数与递归比如：C语言提供了实数和整数的加法运算符号“+”来完成运算；但是“+”不能对复数做加法运算；可以写一个函数来实现这个功能。第2章实现基础§3流程控制基础【定义】函数是一个完成特定工作的独立程序模块。

只需定义一次，就可以多次调用。

函数包括库函数和自定义函数两种。例如，scanf、printf等库函数由C语言系统提供定义，编程时只要直接调用即可。

在程序设计中，往往根据模块化程序设计的需要，用户可以自己定义函数，属于自定义函数。先定义复数类型ImgType，以约定何为复数：structImage{doubler;doublei;};typedefstructImageImgType;再定义复数的加法函数：ImgTypeImgAdd(ImgTypea,ImgTypeb){ImgTypec;c.r=a.r+b.r;c.i=a.i+b.i;/*实部和虚部分别相加*/

returnc;}有了这个函数，以后可以在任何需要计算复数加法的地方调用它！18/25

在设计函数时，注意掌握以下原则：第2章实现基础§3流程控制基础（1）函数功能的设计原则：结合模块的独立性原则，函数的功能要单一，不要设计多用途的函数，否则会降低模块的聚合度；（2）函数规模的设计原则：函数的规模要小，尽量控制在50行代码以内，这样可以使得函数更易于维护；（3）函数接口的设计原则：结合模块的独立性原则，函数的接口包括函数的参数（入口）和返回值（出口），不要设计过于复杂的接口，合理选择、设置并控制参数的数量，尽量不要使用全局变量，否则会增加模块的耦合度。19/25

递归函数【定义】一个函数除了可以调用其他函数外，C语言还支持函数直接或间接调用自己。这种函数自己调用自己的形式称为函数的递归调用，带有递归调用的函数也称为递归函数。

两个关键点：（1） 递归出口：即递归的结束条件，到何时不再递归调用下去;第2章实现基础§2.3流程控制基础（2） 递归式子：当前函数结果与准备调用的函数结果之间的关系，如求阶乘函数的递归式子

Factorial(n)=n*Factorial(n-1)longint

Factorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}注意：程序代码不能写成上述式子！！递归调用20/25[例2.8]设计函数求n!图2.7递归求解4!的过程第2章实现基础§2.3流程控制基础longint

Factorial(intn){if(n==0)return1;else

returnn*Factorial(n-1);}递归出口递归式子Factorial(4)4

Factorial(3)3

Factorial(2)2

Factorial(1)1

Factorial(0)11262421/25[例2.9]汉诺塔（TowerofHanoi）问题132132（a）初始状态（b）中间状态§3流程控制基础第2章实现基础【分析】可以用递归方法来求解汉诺塔问题，也就是将n个金片的移动问题转换为2个n-1个金片的移动问题。当n=1时，就不需要再递归了。voidMove(intn,intstart,intgoal,inttemp){

if(n==0)return;Move(n-1,start,temp,goal);printf(“Movedisk%dfrom%dto%d.\n”,n,start,goal);Move(n-1,temp,goal,start);}递归调用22/25§3流程控制基础第2章实现基础①Move(3,1,3,2)Move(2,1,2,3)Move(1,1,3,2)Move(0,1,2,3)Move(0,2,3,1)Movedisk2from1to2Move(1,3,2,1)Move(0,3,1,2)Movedisk3from1to3Move(1,2,1,3)Move(0,1,2,3)Movedisk1from3to2Move(0,3,1,2)Move(1,1,3,2)Move(0,1,2,3)Move(0,2,3,1)Move(0,2,3,1)Move(2,2,3,1)Movedisk1from2to1Movedisk1from1to3Movedisk1from1to3②③④⑤⑥⑦Movedisk2from2to323/25[例2.10]用递归方法求集合的中位数。第2章实现基础§2.3流程控制基础

根据前面求解集合第K大整数问题的递归算法思路，还需要解决以下两个关键问题：（1）如何根据元素e将集合S分解为S1和S2两个集合？可以采用临时申请空间的方法建立一个临时数组。（2）如何设计递归函数的参数？

将临时数组作为参数传递。#include<malloc.h>ElementTypeMedian(ElementTypeS[],intN){ElementType*p,m;/*申请临时数组大小所需要的空间*/p=(ElementType*)malloc(sizeof(ElementType)*N);m=FindKthLargest(S,(N+1)/2,0,N-1,p);free(p);/*释放临时数组空间*/returnm;}24/25ElementTypeFindKthLargest(ElementTypeS[],intK，intleft,intright,ElementTypet[]){/*在S[left]..S[right]中找第K大整数，t是临时数组*/inti,Large=left,Small=right;/*Large和Small分别指向S1和S2在临时数组中的下一个存放位置*/ElementTypee;/*分解集合的基准e*/e=S[left];/*将第一个元素作为基准*/for(i=left;i<=right;i++)if(S[i]>=e)/*将比e大的元素放临时数组t左边，小的元素放右边*/t[Large++]=S[i];

elset[Small--]=S[i];for(i=left;i<=right;i++)/*将临时数组中的元素拷贝回原数组*/S[i]=t[i];if(K<Large-left)/*Large-left代表了集合S1的大小*//*在集合S1中继续找*/returnFindKthLargest(S,K,left,Large-1,t);if(k==Large-left)/*找到，返回*/returne;else/*在集合S2中找*/returnFindKthLargest(S,K-Large+left,Large,right,t);}25/25若Small==right，即没有比e小的元素，要另选一个基准第3章线性结构1/25§3.1引子【分析】多项式的关键数据是：多项式项数n、每一项的系数ai

（及相应指数i）。有3种不同的方法。一元多项式：

主要运算：多项式相加、相减、相乘等方法1：采用顺序存储结构直接表示[例3.1]一元多项式及其运算。例如：下标i012345……a[i]10–3004……表示成：方法2：采用顺序存储结构表示多项式的非零项。第3章线性结构§3.1引子每个非零项涉及两个信息：指数和系数，可以将一个多项式看成是一个(，)二元组的集合。例如：和表示成：数组下标i012……数组下标i0123……系数9153–系数26–4–1382–指数1282–指数19860–P1(x)(b)P2(x)

相加过程：

比较（9,12）和（26，19），将（26,19）移到结果多项式；

继续比较（9,12）和（–4，8），将（9,12）移到结果多项式；

比较（15,8）和（–4，8），15+（–4）=11，不为0，将新的一项（11,8）增加到结果多项式；

比较（3,2）和（–13,6）,将（–13,6）移到结果多项式；

比较（3,2）和（82,0）,将（3,2）移到结果多项式；

将（82,0）直接移到结果多项式。最后得到的结果多项式是：((26,19),(9,12),(11,8),(–13,6),(3,2),(82,0))

2/25方法3：采用链表结构来存储多项式的非零项。每个链表结点存储多项式中的一个非零项，包括系数和指数两个数据域以及一个指针域，表示为：coefexponlinktypedef

structPolyNode*Polynomial;typedef

structPolyNode{

intcoef;

intexpon; Polynomiallink;}例如:链表存储形式为：第3章线性结构§3.1引子912P1P215832NULL2619–48–136820NULL3/25[例3.2]二元多项式又该如何表示？比如，给定二元多项式：

【分析】可以将上述二元多项式看成关于x的一元多项式

所以，上述二元多项式可以用“复杂”链表表示为：第3章线性结构§3.1引子图3.4二元多项式非零项的链表表示12P832NULL9240NULL153–11NULL4/25第3章线性结构5/25§3.2线性表的定义与实现【定义】“线性表(LinearList)”是由同一类型的数据元素构成的有序序列的线性结构。

线性表中元素的个数称为线性表的长度；

当一个线性表中没有元素（长度为0）时，称为空表；

表的起始位置称表头，表的结束位置称表尾。,类型名称：线性表（List）数据对象集：线性表是

n(≥0)个元素构成的有序序列(a1,a2,

,an)；

ai+1称为

ai的直接后继，

ai-1为

ai的直接前驱；直接前驱和直接后继反映了元素之间一对一的邻接逻辑关系。操作集：对于一个具体的线性表L

List，一个表示位置的整数i，一个元素X

ElementType，线性表的基本操作主要有：1、ListMakeEmpty()：初始化一个新的空线性表L；2、ElementType

FindKth(intK,ListL)：根据指定的位序K，返回相应元素

；3、intFind(ElementTypeX,ListL)：已知X，返回线性表L中与X相同的第一个元素的相应位序i；若不存在则返回空；4、voidInsert(ElementTypeX,inti,ListL)：指定位序i前插入一个新元素X；5、voidDelete(inti,ListL)：删除指定位序i的元素；6、intLength(ListL)：返回线性表L的长度n。

线性表的顺序存储实现第3章线性结构§3.2.1线性表的顺序存储实现在内存中用地址连续的一块存储空间顺序存放线性表的各元素。一维数组在内存中占用的存储空间就是一组连续的存储区域。typedef

struct{ ElementTypeData[MAXSIZE];

intLast;}List;ListL,*PtrL;下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last访问下标为i的元素：L.Data[i]或PtrL->Data[i]线性表的长度：L.Last+1或PtrL->Last+16/251.初始化（建立空的顺序表）第3章线性结构

主要操作的实现List*MakeEmpty(){List*PtrL;PtrL=(List*)malloc(sizeof(List));PtrL->Last=-1;

returnPtrL;}2.查找intFind(ElementTypeX,List*PtrL){int

i=0;

while(i<=PtrL->Last&&PtrL->Data[i]!=X)

i++;

if(i>PtrL->Last)return-1;/*如果没找到，返回-1*/

else

returni;/*找到后返回的是存储位置*/}查找成功的平均比较次数为(n+1)/2，平均时间性能为

O(n)。§3.2.1线性表的顺序存储实现7/25第3章线性结构下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下标i01…i-1ii+1…n…SIZE-1Dataa1a2…aiai+1…an…-Last3.插入（第

i(1≤i≤n+1)个位置上插入一个值为X的新元素)先移动，再插入X§3.2.1线性表的顺序存储实现8/25

插入算法第3章线性结构voidInsert(ElementTypeX,inti,List*PtrL){intj;

if(PtrL->Last==MAXSIZE-1){/*表空间已满，不能插入*/printf(＂表满＂);return;}

if(i<1||i>PtrL->Last+2){/*检查插入位置的合法性*/printf(＂位置不合法＂);return;}

for(j=PtrL->Last;j>=i-1;j--)PtrL->Data[j+1]=PtrL->Data[j];/*将

ai～

an倒序向后移动*/PtrL->Data[i-1]=X;/*新元素插入*/PtrL->Last++;/*Last仍指向最后元素*/

return;}平均移动次数为n/2，平均时间性能为

O(n)。§3.2.1线性表的顺序存储实现9/25第3章线性结构下标i01…i-1i…n-1…MAXSIZE-1Dataa1a2…aiai+1…an…-Last下标i01…i-1…n-2n-1…MAXSIZE-1Dataa1a2…ai+1…anan…-Last4.

删除（删除表的第

i(1≤i≤n)个位置上的元素)后面的元素依次前移§3.2.1线性表的顺序存储实现10/25

删除算法第3章线性结构voidDelete(inti,List*PtrL){intj;

if(i<1||i>PtrL->Last+1){/*检查空表及删除位置的合法性*/printf(“不存在第%d个元素”,i);

return;}

for(j=i;j<=PtrL->Last;j++)PtrL->Data[j-1]=PtrL->Data[j];/*将

ai+1～

an顺序向前移动*/PtrL->Last--;/*Last仍指向最后元素*/

return;}平均移动次数为(n-1)/2，平均时间性能为

O(n)。§3.2.1线性表的顺序存储实现11/25

线性表的链式存储实现第3章线性结构不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系。因此对线性表的插入、删除不需要移动数据元素，只需要修改“链”。typedef

structNode{ElementTypeData;

structNode*Next;}List;ListL,*PtrL;访问序号为i的元素？求线性表的长度？§3.2.3线性表的链式存储实现12/251.求表长第3章线性结构

主要操作的实现intLength(List*PtrL){List*p=PtrL;/*p指向表的第一个结点*/intj=0;while(p){p=p->Next;j++;/*当前p指向的是第

j个结点*/}returnj;}时间性能为

O(n)。§3.2.3线性表的链式存储实现13/25第3章线性结构2.查找List*FindKth(intK,List*PtrL){List*p=PtrL;

inti=1;

while(p!=NULL&&i<K){p=p->Next;i++;}

if(i==K)returnp;/*找到第K个，返回指针*/

else

returnNULL;

/*否则返回空*/}List*Find(ElementTypeX,List*PtrL){List*p=PtrL;

while(p!=NULL&&p->Data!=X)p=p->Next;

returnp;}（1）按序号查找:

FindKth;（2）按值查找:Find平均时间性能为

O(n)。§3.2.3线性表的链式存储实现14/25第3章线性结构3.插入（在链表的第

i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)（1）先构造一个新结点，用s指向；（2）再找到链表的第

i-1个结点，用p指向；（3）然后修改指针，插入结点(p之后插入新结点是s)head……pss->Next=p->Next;p->Next=s;

§3.2.3线性表的链式存储实现思考:修改指针的两个步骤如果交换一下，将会发生什么?15/25

插入算法第3章线性结构List*Insert(ElementTypeX,inti,List*PtrL){List*p,*s;

if(i==1){/*新结点插入在表头