编译技术DS02实现基础

《编译技术DS02实现基础》由会员分享，可在线阅读，更多相关《编译技术DS02实现基础（30页珍藏版）》请在金锄头文库上搜索。

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/25 如何利用程序设计语言实现上述抽象类型？如何利用程序设计语言实现上述抽象类型？第第2章章 实现基础实现基础 2.1 引子引子1. 数据存储数据存储 C语言（包括其他

3、高级语言）提供了语言（包括其他高级语言）提供了数组、结构、链表数组、结构、链表等。等。 数据结构的数据结构的存储实现存储实现跟所需要的跟所需要的操作密切相关操作密切相关。 在数据结构里，是在数据结构里，是利用数组和链表方式来实现利用数组和链表方式来实现的，包括很复杂的，包括很复杂的数据结构，如的数据结构，如图、树图、树等。等。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; iN; i+) Sum += Si; /* 将数组元素累加到将数组元素累加到Sum中中 */ return Sum/N;2/25第第2章章 实现基础实现基础 2 数据存储基础数据存储基础 变量变量是数据存储的基本单位。变量的类型决定了是数据存储的基本单位。变量的类型决定了存储和操作存储和操作。 几种基本的数据

5、类型：几种基本的数据类型：整型、实型（浮点型）、字符型整型、实型（浮点型）、字符型等。等。 提供了构造数据类型：提供了构造数据类型：数组、结构、指针数组、结构、指针等。等。1.数组数组数组是最基本的构造类型，它是数组是最基本的构造类型，它是一组相同类型数据一组相同类型数据的有序集合。数的有序集合。数组中的元素在内存中组中的元素在内存中连续存放连续存放，用数组名和下标可以唯一地确定数，用数组名和下标可以唯一地确定数组元素。组元素。5/25（1）一维数组）一维数组（2）二维数组）二维数组（3）数组作为形参和实参）数组作为形参和实参第第2章章 实现基础实现基础 2 数据存储基础数据存储基础例例2.3

6、 求集合元素的最大值。集合元素存放在数组求集合元素的最大值。集合元素存放在数组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语言中一个非常重要的概念。使用指针可语言中一个非常重要的概念。使用指针可以对以对复杂数据复杂数据进行处理，能对计算机的进行处理，能对计算机的

7、内存进行分配内存进行分配控控制，在函数调用中使用指针还可以制，在函数调用中使用指针还可以返回多个值返回多个值。 指针指针的基本运算的基本运算 取地址运算符取地址运算符 & 间接访问运算符间接访问运算符 * 指针的加指针的加 、减操作。、减操作。6/25第第2章章 实现基础实现基础 2 数据存储基础数据存储基础（2） 指针与数组指针与数组 数组名数组名是数组中第是数组中第1个元素（下标为个元素（下标为0）的地址，可以）的地址，可以看作是看作是常量指针常量指针，不能改变指针常量（数组名）的值。，不能改变指针常量（数组名）的值。（3）用指针实现内存动态分配用指针实现内存动态分配分配函数分配函数 vo

8、id *malloc(unsigned size) 。 该函数分配了该函数分配了size个字节，并返回了指向这块内存的指针。个字节，并返回了指向这块内存的指针。 如果分配失败，则返回一个空指针（如果分配失败，则返回一个空指针（NULL）。）。 关于分配失关于分配失败的原因，应该有多种，比如说空间不足就是一种。败的原因，应该有多种，比如说空间不足就是一种。释放函数释放函数void free(void *ptr) 。 该函数是将之前用该函数是将之前用malloc分配的空间还给程序或者是操作系分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。统，也就是释放了这块内存，让它重新

9、得到自由。6/25注意事项：注意事项：A、申请了内存空间后，必须检查是否分配成功。申请了内存空间后，必须检查是否分配成功。B、当不需要再使用申请的内存时，记得释放；、当不需要再使用申请的内存时，记得释放；释放后应该把原本释放后应该把原本指向这块内存的指针变量指向这块内存的指针变量 指向指向NULL，防止程序后面不小心使，防止程序后面不小心使用了该指针用了该指针。（释放的是内存，不是指针变量）。（释放的是内存，不是指针变量）C、这两个函数应该是配对使用。如果申请后不释放就是内存泄露；、这两个函数应该是配对使用。如果申请后不释放就是内存泄露；如果无故释放（还未使用就释放）那就是什么也没有做。释放如

10、果无故释放（还未使用就释放）那就是什么也没有做。释放只能一次，如果释放两次及两次以上会出现错误（释放空指针只能一次，如果释放两次及两次以上会出现错误（释放空指针例外，释放空指针其实也等于啥也没做，所以释放空指针释放例外，释放空指针其实也等于啥也没做，所以释放空指针释放多少次都没有问题）。多少次都没有问题）。D、虽然、虽然malloc()函数的类型是函数的类型是(void *),任何类型的指针都可以转任何类型的指针都可以转换成换成(void *),但是最好还是在前面进行强制类型转换，因为这但是最好还是在前面进行强制类型转换，因为这样可以躲过一些编译器的检查。样可以躲过一些编译器的检查。第第2章章

11、 实现基础实现基础 2 数据存储基础数据存储基础（4） 用指针实现动态顺序存储结构用指针实现动态顺序存储结构 int * p; p=(int *) malloc(10*sizeof(int); if(p=NULL) return; int p10; 第第2章章 实现基础实现基础 2 数据存储基础数据存储基础3. 结构结构结构类型定义的一般形式为：结构类型定义的一般形式为：struct 结构名结构名 类型名类型名 结构成员名结构成员名1; 类型名类型名 结构成员名结构成员名2; 类型名类型名 结构成员名结构成员名n;第第2章章 实现基础实现基础 2 数据存储基础数据存储基础【定义定义】结构类型把

12、一些可以是不同类型的结构类型把一些可以是不同类型的数据分量聚合数据分量聚合成成一个整体。同时，结构又是一个一个整体。同时，结构又是一个变量的集合变量的集合，可以单独使用，可以单独使用其变量成员。其变量成员。7/25struct student /学生信息结构体学生信息结构体 int num; /学号学号 char name20; /姓名姓名 char gender; /性别性别 int age; /年龄年龄stu=97001,Lin Lin,F,19;typedef struct student /学生信息结构学生信息结构体体 int num; /学号学号 int age; /年龄年龄Stud

13、ent；第第2章章 实现基础实现基础 2 数据存储基础数据存储基础结构数组：结构与数组的结合结构数组：结构与数组的结合结构指针结构指针：指向结构的指针：指向结构的指针（1）用）用*方式访问，形式：（方式访问，形式：（*结构指针变量名结构指针变量名 ）.结构成员名结构成员名（2）用指向运算符）用指向运算符“-”访问指针指向的结构成员，形式：访问指针指向的结构成员，形式： 结构指针变量名结构指针变量名-结构成员名结构成员名对结构数组元素成员的引用是通过使用对结构数组元素成员的引用是通过使用数组下标数组下标与与结构成员结构成员操作符操作符“.”相结合的方式来完成的，其一般格式为：相结合的方式来完成的

14、，其一般格式为：结构数组名结构数组名下标下标.结构成员名结构成员名7/25结构变量的使用结构变量的使用使用结构变量就是对其成员进行操作。格式为：使用结构变量就是对其成员进行操作。格式为：结构变量结构变量名名.结构成员名结构成员名。此外，。此外，结构变量不仅可以作为函数参数，结构变量不仅可以作为函数参数，也可以作为函数的返回值。也可以作为函数的返回值。共用体共用体【定义定义】共用体类型是指将共用体类型是指将不同的数据项不同的数据项组织成一个整体，组织成一个整体，它们在它们在内存中占用同一段存储单元。内存中占用同一段存储单元。第第2章章 实现基础实现基础 2 数据存储基础数据存储基础共用体共用体类

15、型定义的一般形式为：类型定义的一般形式为：union共用体共用体名名 类型名类型名 成员名成员名1; 类型名类型名 成员名成员名2; 类型名类型名 成员名成员名n; 各个成员变量在内存中都使用各个成员变量在内存中都使用同一段同一段存储空间存储空间，因此共用体变量的长度等于，因此共用体变量的长度等于最长的成员的长度最长的成员的长度。 共用体的访问方式同结构体类似。共用体的访问方式同结构体类似。int main() union key int k; char ch2; u;u.k = 258；printf(“%d %dn”, u.ch0,u.ch1);return 0;00000010000000

16、01 u.k=258的二进制表示：的二进制表示：u.ch0 = 2u.ch1 = 18/25枚举类型的声明形式如下：枚举类型的声明形式如下：enum 枚举类型名枚举类型名 变量值列表变量值列表;1. 枚举类型枚举类型【定义定义】将需要的变量值一一列举出来，便构成了将需要的变量值一一列举出来，便构成了一个枚举类型一个枚举类型例如：例如：enum weekday sun,mon,tue,wed,thu,fri,sat;枚举类型应用说明：枚举类型应用说明： 对枚举元素按常量处理，不能对它们赋值。对枚举元素按常量处理，不能对它们赋值。如，不能写：如，不能写：sun=0; 枚举元素具有缺省值，它们依次为

17、：枚举元素具有缺省值，它们依次为： 0,1,2,.。 也可以在声明时另行指定枚举元素的值，如：也可以在声明时另行指定枚举元素的值，如：enum weekday sun=7,mon=1,tue,wed,thu,fri,sat;枚举值可以进行关系运算。枚举值可以进行关系运算。如：如： weekday today； if(today=tue) ;整数值不能直接赋给枚举变量，如需要将整数赋值给整数值不能直接赋给枚举变量，如需要将整数赋值给枚举变量，应进行强制类型转换。枚举变量，应进行强制类型转换。如：如：today=(weekday)3;4.链表链表 链表链表是一种重要的基础数据结构，也是实现是一种重

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

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

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

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

22、A3ANheadpt第第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就地逆转就地逆转，即不，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个需要申请新

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

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

25、 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 * NodePtr;这样，这样，Reverse

26、函数头就可以写成：函数头就可以写成：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 流程控制基础流程控制基础顺序结构是一种自然的控制结构，通过安排顺序结构是一种自然的控制结构，通过安排语句或语

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

28、变化（用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 说明在上面的说明在上面的while循环中循环中i都不能被都不能被

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

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

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

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

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

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

35、nt Factorial( int n )if( n = 0 ) return 1;else return 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章章 实现基础实现基础 【分析分析】可以用递归方法来求解汉诺塔问题，也就是可以用递归方法来

36、求解汉诺塔问题，也就是将将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, goal, start);递归调用递归调用22/253 流程控制基础流程控制基础第第2

37、章章 实现基础实现基础 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,1)Move (0,2,3,1)Move (2,2,3,1)Move disk

38、 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两个集合？两个集合？ 可以采用临时申请空间的方法建立一个可以采用临时申请空间

39、的方法建立一个临时数组。临时数组。（2）如何设计递归函数的参数？）如何设计递归函数的参数？将将临时数组作为参数传递临时数组作为参数传递。#include ElementType Median(ElementType S , int N) ElementType *p, m;/* 申请临时数组大小所需要的空间申请临时数组大小所需要的空间*/p = (ElementType *) malloc( sizeof (ElementType)*N);m = FindKthLargest( S, (N+1)/2, 0, N-1, p );free(p); /* 释放临时数组空间释放临时数组空间 */ret

40、urn m;24/25ElementType FindKthLargest( ElementType S , int K， int left, int right, ElementType t ) /* 在在Sleft.Sright中找第中找第K大整数，大整数，t是临时数组是临时数组 */int i, Large = left, Small = right; /* Large和和Small分别指向分别指向S1和和S2在临时数组中的下一个存放位置在临时数组中的下一个存放位置 */ElementType e; /* 分解集合的基准分解集合的基准e */e = Sleft; /* 将第一个元素作为基

41、准将第一个元素作为基准 */for ( i = left; i = e ) /*将比将比e大的元素放临时数组大的元素放临时数组t左边，小的元素放右边左边，小的元素放右边 */ tLarge+ = Si; else tSmall- = Si;for ( i = left; i = right; i+ ) /*将临时数组中的元素拷贝回原数组将临时数组中的元素拷贝回原数组 */ Si=ti; if ( K Large-left ) /* Large-left代表了集合代表了集合S1的大小的大小 */*在集合在集合S1中继续找中继续找 */return FindKthLargest( S, K, left, Large-1, t ); if ( k = Large-left) /* 找到，返回找到，返回 */return e;else/*在集合在集合S2中找中找 */return FindKthLargest( S, K-Large+left, Large, right, t); 25/25若若Small=right，即，即没有比没有比e小的元素，小的元素，要另选一个要另选一个 基准基准