数据结构与算法_实现基础

1、第第2章章 实现基础实现基础 2.1 引子引子 还是还是为每个具体应用都编一个程序为每个具体应用都编一个程序? 类型名称：类型名称：数据集合的基本统计数据集合的基本统计 数据对象集：数据对象集：集合集合S= ， ， 操作集操作集：1. ElementType Average(S)：求：求S中元素的平均值；中元素的平均值；2. ElementType Max(S)：求：求S中元素的最大值；中元素的最大值；3. ElementType Min(S)：求：求S中元素的最小值；中元素的最小值；4. ElementType Median(S)：求：求S中元素的中位数。中元素的中位数。 从不同的从不同的应

2、用中应用中抽象出共性的数据组织与操作方法？抽象出共性的数据组织与操作方法？例例2.1 在日常数据处理中经常碰到的问题是需要对在日常数据处理中经常碰到的问题是需要对一组数据一组数据进进行基本的统计分析。比如，分析一个课程班学生的平均成绩、行基本的统计分析。比如，分析一个课程班学生的平均成绩、最最高成绩、最低成绩、中位数、标准差高成绩、最低成绩、中位数、标准差等。同样的统计要求也可能等。同样的统计要求也可能发生在其他领域发生在其他领域。1/251x2xNx 如何利用程序设计语言实现上述抽象类型？如何利用程序设计语言实现上述抽象类型？第第2章章 实现基础实现基础 2.1 引子引子1. 数据存储数据存

3、储 C语言（包括其他高级语言）提供了语言（包括其他高级语言）提供了数组、结构、链表数组、结构、链表等。等。 数据结构的数据结构的存储实现存储实现跟所需要的跟所需要的操作密切相关操作密切相关。 在数据结构里，是在数据结构里，是利用数组和链表方式来实现利用数组和链表方式来实现的，包括很复杂的，包括很复杂的数据结构，如的数据结构，如图、树图、树等。等。2. 操作实现操作实现流程控制语句，即流程控制语句，即分支控制语句分支控制语句（如（如if-else、switch语句）、语句）、循环控制语句循环控制语句（如（如for、while、do-while语句）。语句）。 此外，还有模块化的程序设计方法此外，

4、还有模块化的程序设计方法函数函数ElementType Average(ElementType S, int N)/* 求集合元素的平均值求集合元素的平均值。集合。集合元素存放在数组元素存放在数组S中，数组大小为中，数组大小为N */ int i; ElementType Sum=0; for(i = 0; i= e元素元素 e 当当K = N1时，时， 第第K大整数就是大整数就是e。 当当K N1 时，时，第第K大整数大整数是是在在S2中中的第的第(K-N1)大整数大整数。 比较慢！比较慢！3/25ElementType KthLargest( ElementType S, int K) 选

5、取选取S中的第一个元素中的第一个元素e;根据根据e将集合将集合S分解为大于等于分解为大于等于e 的元素集合的元素集合S1和小于和小于e的元素集合的元素集合S2; while (|S2| =0 ) 另选一个另选一个 e;if (|S1|K) return KthLargest(S1，K);else if (|S1|K) return KthLargest(S2，K-|S1|);else return e; 例例2.2 求集合求集合 6 5 9 8 2 1 7 3 4 的中位数的中位数。【分析分析】由于该集合有由于该集合有9个元素，所以中位数应该是集合从大到个元素，所以中位数应该是集合从大到小排序

6、后的第小排序后的第 9/2 = 5个元素。个元素。 首先，选取集合的第一个元素首先，选取集合的第一个元素6，根据这个元素从集合中分解出，根据这个元素从集合中分解出S1=6，9，8，7，S2=5，2，1，3，4。 由于由于|S1|=45，所以该中位数应该在集合，所以该中位数应该在集合S2中，且是中，且是S2中第中第(5 4 =1)大整数。大整数。 继续选取继续选取S2中的第一个整数中的第一个整数5，将，将S2分解出两个集合分解出两个集合S1=5，S2=2,1,3,4。由于由于|S1|=1，所以，所以5就是就是S2集合的第集合的第1大整数，也就是集合大整数，也就是集合6 5 9 8 2 1 7 3

7、 4的中位数。的中位数。第第2章章 实现基础实现基础 1 引子引子4/25第第2章章 实现基础实现基础 2 数据存储基础数据存储基础 变量变量是数据存储的基本单位。变量的类型决定了是数据存储的基本单位。变量的类型决定了存储和操作存储和操作。 几种基本的数据类型：几种基本的数据类型：整型、实型（浮点型）、字符型整型、实型（浮点型）、字符型等。等。 提供了构造数据类型：提供了构造数据类型：数组、结构、指针数组、结构、指针等。等。1.数组数组数组是最基本的构造类型，它是数组是最基本的构造类型，它是一组相同类型数据一组相同类型数据的有序集合。的有序集合。数组中的元素在内存中数组中的元素在内存中连续存放

8、连续存放，用数组名和下标可以唯一地确，用数组名和下标可以唯一地确定数组元素。定数组元素。例例2.3 求集合元素的最大值。集合元素存放在数组求集合元素的最大值。集合元素存放在数组A中，数组大小中，数组大小为为N。float Max(float A, int N) /* 求求N个元素数组中的最大值个元素数组中的最大值 */ float CurMax = A0; int i; for(i=1; i CurMax) CurMax =Ai; return CurMax;5/252. 指针指针第第2章章 实现基础实现基础 2 数据存储基础数据存储基础 指针指针是是C语言中一个非常重要的概念。使用指针可以对

9、语言中一个非常重要的概念。使用指针可以对复杂数复杂数据据进行处理，能对计算机的进行处理，能对计算机的内存进行分配内存进行分配控制，在函数调用中使用控制，在函数调用中使用指针还可以指针还可以返回多个值返回多个值。 指针与数组指针与数组 数组名数组名是数组中第是数组中第1个元素（下标为个元素（下标为0）的地址，可以看作是）的地址，可以看作是常量常量指针指针，不能改变指针常量（数组名）的值。，不能改变指针常量（数组名）的值。 用指针实现内存动态分配用指针实现内存动态分配 分配函数分配函数 void *malloc(unsigned size) 。 释放函数释放函数void free(void *pt

10、r) 。6/253. 结构结构结构类型定义的一般形式为：结构类型定义的一般形式为：struct 结构名结构名 类型名类型名 结构成员名结构成员名1; 类型名类型名 结构成员名结构成员名2; 类型名类型名 结构成员名结构成员名n;第第2章章 实现基础实现基础 2 数据存储基础数据存储基础【定义定义】结构类型把一些可以是不同类型的结构类型把一些可以是不同类型的数据分量聚合数据分量聚合成一个整体。成一个整体。同时，结构又是一个同时，结构又是一个变量的集合变量的集合，可以单独使用其变量成员。，可以单独使用其变量成员。 结构变量的使用结构变量的使用使用结构变量就是对其成员进行操作。使用结构变量就是对其成

11、员进行操作。格式为：格式为：结构变量名结构变量名.结构成员名结构成员名。此。此外，外，结构变量不仅可以作为函数参数，结构变量不仅可以作为函数参数，也可以作为函数的返回值。也可以作为函数的返回值。 结构数组：结构与数组的结合结构数组：结构与数组的结合 结构指针结构指针：指向结构的指针：指向结构的指针（1）用）用*方式访问，形式：（方式访问，形式：（*结构指针变量名结构指针变量名 ）.结构成员名结构成员名（2）用指向运算符）用指向运算符“-”访问指针指向的结构成员，形式：访问指针指向的结构成员，形式： 结构指针变量名结构指针变量名-结构成员名结构成员名对结构数组元素成员的引用是通过使用数组下标与结

12、构成员操作符对结构数组元素成员的引用是通过使用数组下标与结构成员操作符“.”相结合的方式来完成的，其一般格式为：相结合的方式来完成的，其一般格式为：结构数组名结构数组名下标下标.结构成员名结构成员名7/25 共用体共用体【定义定义】共用体类型是指将共用体类型是指将不同的数据项不同的数据项组织成一个整体，组织成一个整体，它们在它们在内存中占用同一段存储单元。内存中占用同一段存储单元。第第2章章 实现基础实现基础 2 数据存储基础数据存储基础共用体共用体类型定义的一般形式为：类型定义的一般形式为：union共用体共用体名名 类型名类型名 成员名成员名1; 类型名类型名 成员名成员名2; 类型名类型

13、名 成员名成员名n; 各个成员变量在内存中都使用各个成员变量在内存中都使用同一段同一段存储空间存储空间，因此共用体变量的长度等于，因此共用体变量的长度等于最长的成员的长度最长的成员的长度。 共用体的访问方式同结构体类似。共用体的访问方式同结构体类似。int main() union key int k; char ch2; u;u.k = 258；printf(“%d %dn”, u.ch0,u.ch1);return 0;0000001000000001 u.k=258的二进制表示：的二进制表示：u.ch0 = 2u.ch1 = 18/254. 链表链表 链表链表是一种重要的基础数据结构，也

14、是实现是一种重要的基础数据结构，也是实现复杂数据结构复杂数据结构的重的重要手段。它不按照线性的顺序存储数据，而是由若干个同一结构类要手段。它不按照线性的顺序存储数据，而是由若干个同一结构类型的型的“结点结点”依次串接而成的，即每一个结点里保存着依次串接而成的，即每一个结点里保存着下一个结点下一个结点的地址的地址（指针指针）。 链表链表又分又分单向链表单向链表，双向链表双向链表以及以及循环链表循环链表等。等。 单向链表的结构单向链表的结构headABCDNULL使用结构的使用结构的嵌套嵌套来定义来定义单向链表结点单向链表结点的数据类型。如：的数据类型。如：struct Node ElementT

15、ype Data; struct Node *Next;第第2章章 实现基础实现基础 2 数据存储基础数据存储基础struct Node *p;p = (struct Node *) malloc(sizeof(struct Node);9/25h e ad（1）插入结点插入结点 ( p之后插入新结点之后插入新结点t ) 单向链表的常见操作单向链表的常见操作（2）删除结点删除结点 第第2章章 实现基础实现基础 2 数据存储基础数据存储基础ptt-Next = p-Next;p-Next = t; headpt = p-Next;p-Next = t-next; 10/25（3） 单向链表的遍历

16、单向链表的遍历 p = head;while (p!=NULL) 处理处理p所指的结点信息；所指的结点信息； p = p-Next;（4）链表的建立链表的建立 有两种常见的插入结点方式：有两种常见的插入结点方式：（1）在链表的）在链表的头上头上不断插入新结点；不断插入新结点；（2）在链表的）在链表的尾部尾部不断插入新结点。不断插入新结点。如果是后者，一般需要有一个如果是后者，一般需要有一个临时的结点指针临时的结点指针一直指一直指向当前链表的最后一个结点，以方便新结点的插入。向当前链表的最后一个结点，以方便新结点的插入。第第2章章 实现基础实现基础 2 数据存储基础数据存储基础11/25 双向链

17、表双向链表 如果将如果将双向链表双向链表最后一个单元的最后一个单元的Next指针指向链表的第一个单指针指向链表的第一个单元，而第一个单元的元，而第一个单元的Previous指针指向链表的最后一个单元，这指针指向链表的最后一个单元，这样构成的链表称为样构成的链表称为双向循环链表。双向循环链表。第第2章章 实现基础实现基础 2 数据存储基础数据存储基础struct Node ElementType Data; struct Node *Next; struct Node * Previous;12/25 双向链表的插入、删除和遍历基本思路与单向链表相同，但双向链表的插入、删除和遍历基本思路与单向链

18、表相同，但需要同时考虑需要同时考虑前后两个指针前后两个指针。A1A2A3ANheadpt第第2章章 实现基础实现基础 2 数据存储基础数据存储基础struct DNode ElementType Data;struct DNode *Next;struct DNode *Previous; *p,*t;指针操作顺序：指针操作顺序： t-Previous = p; t-Next = p-Next; p-Next-Previous = t; p-Next = t; 13/25例例2.4 给定一个单链表给定一个单链表L，请设计函数，请设计函数Reverse将链表将链表L就地逆转就地逆转，即，即不需要

19、申请新的结点，将链表的第一个元素转为最后一个元素，第二不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素个元素转为倒数第二个元素【分析分析】 基本思路是：基本思路是： 利用利用循环循环，从链表头开始逐个处理。，从链表头开始逐个处理。 如何把握住如何把握住循环不变式循环不变式。（循环不变式表示一种在循环过程进行时。（循环不变式表示一种在循环过程进行时不变的性质，不变的性质，不依赖于前面所执行过程的重复次数的断言不依赖于前面所执行过程的重复次数的断言。）。） 在每轮循环开始前我们都面临两个序列，其中在每轮循环开始前我们都面临两个序列，其中p是一个待逆转的序是一个待

20、逆转的序列列，而，而q是一个已经逆转好的序列是一个已经逆转好的序列，如下图。，如下图。 每轮循环的目的是把每轮循环的目的是把p中的第一个元素插入到中的第一个元素插入到q的头的头上，使这轮循环上，使这轮循环执行好后，执行好后，p和和 q还是分别指向新的待逆转序列和已经逆转好的序列。还是分别指向新的待逆转序列和已经逆转好的序列。第第2章章 实现基础实现基础 2 数据存储基础数据存储基础tqpt = p-Next;p-Next = q;q = p;p = t; struct Node *Reverse(struct Node *L) struct Node *p, *q, *t; p = L，q =

21、 NULL; while ( p != NULL ) t = p-Next; p-Next = q; q = p; p = t; return q;14/255. 类型定义类型定义typedef第第2章章 实现基础实现基础 2 数据存储基础数据存储基础 除了使用除了使用C语言提供的标准类型和自己定义的一些结构体、枚举等类语言提供的标准类型和自己定义的一些结构体、枚举等类型外，还可以型外，还可以用用typedef语句来建立已经定义好的数据类型的别名。语句来建立已经定义好的数据类型的别名。typedef 原有类型名原有类型名 新类型名新类型名typedef struct Node * NodePt

22、r;这样，这样，Reverse函数头就可以写成：函数头就可以写成：NodePtr Reverse( NodePtr L )NodePtr Reverse( NodePtr L )/* struct Node *Reverse(struct Node *L) */ struct Node *p, *q, *t; p = L，q = NULL; while ( p != NULL ) t = p-Next; p-Next = q; q = p; p = t; return q;15/25第第2章章 实现基础实现基础 3 流程控制基础流程控制基础 顺序结构是一种自然的控制结构，通过安排顺序结构是一种

23、自然的控制结构，通过安排语句语句或模块的顺序或模块的顺序就能实现。就能实现。 C语言为分支控制提供了语言为分支控制提供了if-else和和switch两类语句，两类语句， 为循环控制提供了为循环控制提供了for、while和和do-while三类语句。三类语句。 三种基本的控制结构是三种基本的控制结构是顺序、分支和循环顺序、分支和循环。 函数定义函数定义 函数调用函数调用 函数递归函数递归语句级控制语句级控制单位级控制单位级控制16/25例例2.5 求求100到到200之间的所有素数。之间的所有素数。分析分析 可以设定两重循环：大循环（外层循环）控制整数可以设定两重循环：大循环（外层循环）控制

24、整数i在在100到到200之间变化（用之间变化（用for语句），而小循环（内层循环）则用语句），而小循环（内层循环）则用来判别来判别i是否是素数（用是否是素数（用while语句）。语句）。第第2章章 实现基础实现基础 3 流程控制基础流程控制基础int main() int i, 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 说明说明在上面

25、的在上面的while循环中循环中i都不能被都不能被j整除，因此整除，因此i是素数是素数 */ return 0;17/253. 函数与递归函数与递归比如：比如：C语言提供了实数和整数的加语言提供了实数和整数的加法运算符号法运算符号“+”来完成运算；来完成运算；但是但是“+”不能对复数做加法运算；不能对复数做加法运算；可以写可以写一个函数一个函数来实现这个功能。来实现这个功能。第第2章章 实现基础实现基础 3 流程控制基础流程控制基础 【定义定义】函数函数是一个完成特定工作的是一个完成特定工作的独立程序模块独立程序模块。 只需只需定义一次定义一次，就可以，就可以多次调用多次调用。 函数包括函数包

26、括库函数库函数和和自定义函数自定义函数两种。例如，两种。例如，scanf、printf等库函数由等库函数由C语言系统提供定义，编程时只要直接调用即可。语言系统提供定义，编程时只要直接调用即可。 在程序设计中，往往根据模块化程序设计的需要，用户可以自己定义在程序设计中，往往根据模块化程序设计的需要，用户可以自己定义函数，属于自定义函数。函数，属于自定义函数。先定义复数类型先定义复数类型 ImgType，以约定，以约定何为复数：何为复数：struct Image double r; double i; ;typedef struct Image ImgType; 再定义复数的加法函数：再定义复数的

27、加法函数：ImgType ImgAdd(ImgType a, ImgType b) ImgType c; c.r = a.r + b.r; c.i = a.i + b.i; /* 实部和虚部分别相加实部和虚部分别相加 */ return c;有了这个函数，以有了这个函数，以后可以在任何需要后可以在任何需要计算复数加法的地计算复数加法的地方调用它！方调用它！18/25 在设计函数时，注意掌握以下原则：在设计函数时，注意掌握以下原则：第第2章章 实现基础实现基础 3 流程控制基础流程控制基础（1）函数）函数功能的设计原则功能的设计原则：结合模块的独立性原则，函数的：结合模块的独立性原则，函数的功功

28、能要单一能要单一，不要设计多用途的函数，否则会降低模块的聚合度；，不要设计多用途的函数，否则会降低模块的聚合度； （2）函数）函数规模的设计规模的设计原则：函数的原则：函数的规模要小规模要小，尽量控制在，尽量控制在50行行代码以内，这样可以使得函数更易于维护；代码以内，这样可以使得函数更易于维护；（3）函数）函数接口的设计接口的设计原则：结合模块的独立性原则，函数的接原则：结合模块的独立性原则，函数的接口包括函数的参数（入口）和返回值（出口），口包括函数的参数（入口）和返回值（出口），不要设计过于不要设计过于复杂的接口复杂的接口，合理选择、设置并控制参数的数量，尽量不要使，合理选择、设置并控制

29、参数的数量，尽量不要使用全局变量，否则会增加模块的耦合度。用全局变量，否则会增加模块的耦合度。19/25 递归函数递归函数【定义定义】一个函数除了可以调用其他函数外，一个函数除了可以调用其他函数外，C语言还支持语言还支持函数函数直接或间接调用自己直接或间接调用自己。这种函数自己调用自己的形式称为。这种函数自己调用自己的形式称为函数的函数的递归调用递归调用，带有递归调用的函数也称为，带有递归调用的函数也称为递归函数递归函数。 两个关键点：两个关键点：（1）递归出口递归出口：即递归的结束条件，到何时不再递归调用下去：即递归的结束条件，到何时不再递归调用下去;第第2章章 实现基础实现基础 2.3 流

30、程控制基础流程控制基础（2）递归式子递归式子：当前函数结果与准备调用的函数结果之间的关：当前函数结果与准备调用的函数结果之间的关系，如求阶乘函数的递归式子系，如求阶乘函数的递归式子 Factorial(n) = n* Factorial(n-1)long int Factorial( int n )if( n = 0 ) return 1;e l s e r e t u r n n * Factorial(n-1);注意：程序代码不能写成上述式子！注意：程序代码不能写成上述式子！递归调用递归调用20/25例例2.8 设计函数求设计函数求n!图图2.7 递归求解递归求解4!的过程的过程第第2章章

31、 实现基础实现基础 2.3 流程控制基础流程控制基础long int Factorial( int n )if( n = 0 ) return 1;e l s e r e t u r n n * Factorial(n-1);递归出口递归出口递归式子递归式子Factorial(4)4 Factorial (3)3 Factorial (2)2 Factorial (1)1 Factorial (0)11262421/25例例2.9 汉诺塔（汉诺塔（Tower of Hanoi）问题）问题132132 （a）初始状态）初始状态 （b）中间状态）中间状态3 流程控制基础流程控制基础第第2章章 实现

32、基础实现基础 【分析分析】可以用递归方法来求解汉诺塔问题，也就是可以用递归方法来求解汉诺塔问题，也就是将将n个金片的移动个金片的移动问题转换为问题转换为2个个n-1个金片的移动问题个金片的移动问题。当。当n=1时，就不需要再递归了。时，就不需要再递归了。void Move(int n, int start, int goal, int temp) if( n = 0 ) return; Move(n-1, start, temp, goal); printf(“Move disk %d from %d to %d.n”, n, start, goal); Move(n-1, temp, goa

33、l, start);递归调用递归调用22/253 流程控制基础流程控制基础第第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)Move disk 2 from 1 to 2Move (1,3,2,1)Move (0,3,1,2)Move disk 3 from 1 to 3Move (1,2,1,3)Move (0,1,2,3)Move disk 1 from 3 to 2Move (0,3,1,2)Move (1,1,3,2)Move (0,1,2,3)Move (0,2,3

34、,1)Move (0,2,3,1)Move (2,2,3,1)Move disk 1 from 2 to 1Move disk 1 from 1 to 3Move disk 1 from 1 to 3Move disk 2 from 2 to 323/25例例2.10 用递归方法求集合的中位数。用递归方法求集合的中位数。第第2章章 实现基础实现基础 2.3 流程控制基础流程控制基础 根据前面根据前面求解集合第求解集合第K大整数问题的大整数问题的递归算法递归算法思路思路，还需要解决，还需要解决以下两个关键问题：以下两个关键问题：（1）如何根据元素）如何根据元素e将集合将集合S分解为分解为S1和和S2两个集