《编译技术DS02实现基础.ppt》由会员分享，可在线阅读，更多相关《编译技术DS02实现基础.ppt（30页珍藏版）》请在三一办公上搜索。
1、第2章 实现基础,2.1 引子,还是为每个具体应用都编一个程序?,类型名称：数据集合的基本统计数据对象集：集合S=，操作集：ElementType Average(S)：求S中元素的平均值；ElementType Max(S)：求S中元素的最大值；ElementType Min(S)：求S中元素的最小值；ElementType Median(S)：求S中元素的中位数。,从不同的应用中抽象出共性的数据组织与操作方法？,例2.1 在日常数据处理中经常碰到的问题是需要对一组数据进行基本的统计分析。比如，分析一个课程班学生的平均成绩、最高成绩、最低成绩、中位数、标准差等。同样的统计要求也可能发生在其他
2、领域。,1/25,如何利用程序设计语言实现上述抽象类型？,第2章 实现基础,2.1 引子,1.数据存储,C语言（包括其他高级语言）提供了数组、结构、链表等。数据结构的存储实现跟所需要的操作密切相关。在数据结构里，是利用数组和链表方式来实现的，包括很复杂的数据结构，如图、树等。,2.操作实现,流程控制语句，即分支控制语句（如if-else、switch语句）、循环控制语句（如for、while、do-while语句）。此外，还有模块化的程序设计方法函数,2/25,第2章 实现基础,2 数据存储基础,变量是数据存储的基本单位。变量的类型决定了存储和操作。几种基本的数据类型：整型、实型（浮点型）、字
3、符型等。提供了构造数据类型：数组、结构、指针等。,数组数组是最基本的构造类型，它是一组相同类型数据的有序集合。数组中的元素在内存中连续存放，用数组名和下标可以唯一地确定数组元素。,5/25,（1）一维数组,（2）二维数组,（3）数组作为形参和实参,第2章 实现基础,2 数据存储基础,例2.3 求集合元素的最大值。集合元素存放在数组A中，数组大小为N。,5/25,指针,第2章 实现基础,2 数据存储基础,指针是C语言中一个非常重要的概念。使用指针可以对复杂数据进行处理，能对计算机的内存进行分配控制，在函数调用中使用指针还可以返回多个值。,指针的基本运算,取地址运算符&间接访问运算符*指针的加、减
4、操作。,6/25,第2章 实现基础,2 数据存储基础,（2）指针与数组,数组名是数组中第1个元素（下标为0）的地址，可以看作是常量指针，不能改变指针常量（数组名）的值。,（3）用指针实现内存动态分配,分配函数 void*malloc(unsigned size)。该函数分配了size个字节，并返回了指向这块内存的指针。如果分配失败，则返回一个空指针（NULL）。关于分配失败的原因，应该有多种，比如说空间不足就是一种。释放函数void free(void*ptr)。该函数是将之前用malloc分配的空间还给程序或者是操作系统，也就是释放了这块内存，让它重新得到自由。,6/25,注意事项：A、申请
5、了内存空间后，必须检查是否分配成功。B、当不需要再使用申请的内存时，记得释放；释放后应该把原本指向这块内存的指针变量 指向NULL，防止程序后面不小心使用了该指针。（释放的是内存，不是指针变量）C、这两个函数应该是配对使用。如果申请后不释放就是内存泄露；如果无故释放（还未使用就释放）那就是什么也没有做。释放只能一次，如果释放两次及两次以上会出现错误（释放空指针例外，释放空指针其实也等于啥也没做，所以释放空指针释放多少次都没有问题）。D、虽然malloc()函数的类型是(void*),任何类型的指针都可以转换成(void*),但是最好还是在前面进行强制类型转换，因为这样可以躲过一些编译器的检查。
6、,第2章 实现基础,2 数据存储基础,（4）用指针实现动态顺序存储结构 int*p;p=(int*)malloc(10*sizeof(int);if(p=NULL)return;int p10;,第2章 实现基础,2 数据存储基础,结构,结构类型定义的一般形式为：struct 结构名 类型名 结构成员名1;类型名 结构成员名2;类型名 结构成员名n;,第2章 实现基础,2 数据存储基础,【定义】结构类型把一些可以是不同类型的数据分量聚合成一个整体。同时，结构又是一个变量的集合，可以单独使用其变量成员。,7/25,struct student/学生信息结构体 int num;/学号 char n
7、ame20;/姓名 char gender;/性别 int age;/年龄stu=97001,Lin Lin,F,19;,typedef struct student/学生信息结构体 int num;/学号 int age;/年龄Student；,第2章 实现基础,2 数据存储基础,结构数组：结构与数组的结合,结构指针：指向结构的指针,（1）用*方式访问，形式：（*结构指针变量名）.结构成员名（2）用指向运算符“-”访问指针指向的结构成员，形式：结构指针变量名-结构成员名,对结构数组元素成员的引用是通过使用数组下标与结构成员操作符“.”相结合的方式来完成的，其一般格式为：结构数组名下标.结构成
8、员名,7/25,结构变量的使用,使用结构变量就是对其成员进行操作。格式为：结构变量名.结构成员名。此外，结构变量不仅可以作为函数参数，也可以作为函数的返回值。,共用体【定义】共用体类型是指将不同的数据项组织成一个整体，它们在内存中占用同一段存储单元。,第2章 实现基础,2 数据存储基础,共用体类型定义的一般形式为：union共用体名 类型名 成员名1;类型名 成员名2;类型名 成员名n;,各个成员变量在内存中都使用同一段存储空间，因此共用体变量的长度等于最长的成员的长度。共用体的访问方式同结构体类似。,u.k=258的二进制表示：,u.ch0=2,u.ch1=1,8/25,枚举类型的声明形式如
9、下：enum 枚举类型名 变量值列表;,枚举类型【定义】将需要的变量值一一列举出来，便构成了一个枚举类型,例如：enum weekday sun,mon,tue,wed,thu,fri,sat;,枚举类型应用说明：对枚举元素按常量处理，不能对它们赋值。如，不能写：sun=0;枚举元素具有缺省值，它们依次为：0,1,2,.。也可以在声明时另行指定枚举元素的值，如：enum weekday sun=7,mon=1,tue,wed,thu,fri,sat;枚举值可以进行关系运算。如：weekday today；if(today=tue);整数值不能直接赋给枚举变量，如需要将整数赋值给枚举变量，应进行
10、强制类型转换。如：today=(weekday)3;,链表,链表是一种重要的基础数据结构，也是实现复杂数据结构的重要手段。它不是顺序存储数据，而是由若干个同一结构类型的“结点”依次串接而成的，即每一个结点里保存着下一个结点的地址（指针）。链表又分单向链表，双向链表以及循环链表等,单向链表的结构,使用结构的嵌套来定义单向链表结点的数据类型。如：struct Node ElementType Data;struct Node*Next;,第2章 实现基础,2 数据存储基础,struct Node*p;p=(struct Node*)malloc(sizeof(struct Node);,9/25,
11、（1）插入结点(p之后插入新结点t),单向链表的常见操作,（2）删除结点,第2章 实现基础,2 数据存储基础,p-Next=t;,p-Next=t-next;,10/25,（3）单向链表的遍历,p=head;while(p!=NULL)处理p所指的结点信息；p=p-Next;,（4）链表的建立,有两种常见的插入结点方式：（1）在链表的头上不断插入新结点；（2）在链表的尾部不断插入新结点。如果是后者，一般需要有一个临时的结点指针一直指向当前链表的最后一个结点，以方便新结点的插入。,第2章 实现基础,2 数据存储基础,11/25,双向链表,如果将双向链表最后一个单元的Next指针指向链表的第一个单
12、元，而第一个单元的Previous指针指向链表的最后一个单元，这样构成的链表称为双向循环链表。,第2章 实现基础,2 数据存储基础,struct Node ElementType Data;struct Node*Next;struct Node*Previous;,12/25,双向链表的插入、删除和遍历基本思路与单向链表相同，但需要同时考虑前后两个指针。,第2章 实现基础,2 数据存储基础,struct DNode ElementType Data;struct DNode*Next;struct DNode*Previous;*p,*t;指针操作顺序：t-Previous=p;t-Next
13、=p-Next;p-Next-Previous=t;p-Next=t;,13/25,例2.4 给定一个单链表L，请设计函数Reverse将链表L就地逆转，即不需要申请新的结点，将链表的第一个元素转为最后一个元素，第二个元素转为倒数第二个元素，。,【分析】基本思路是：利用循环，从链表头开始逐个处理。如何把握住循环不变式。（循环不变式表示一种在循环过程进行时不变的性质，不依赖于前面所执行过程的重复次数的断言。）在每轮循环开始前我们都面临两个序列，其中p是一个待逆转的序列，而q是一个已经逆转好的序列，如下图。每轮循环的目的是把p中的第一个元素插入到q的头上，使这轮循环执行好后，p和 q还是分别指向新
14、的待逆转序列和已经逆转好的序列。,第2章 实现基础,2 数据存储基础,p-Next=q;q=p;,t=p-Next;p-Next=q;q=p;p=t;,14/25,类型定义typedef,第2章 实现基础,2 数据存储基础,除了使用C语言提供的标准类型和自己定义的一些结构体、枚举等类型外，还可以用typedef语句来建立已经定义好的数据类型的别名。,typedef 原有类型名 新类型名,typedef struct Node*NodePtr;,这样，Reverse函数头就可以写成：NodePtr Reverse(NodePtr L),15/25,第2章 实现基础,3 流程控制基础,顺序结构是一
15、种自然的控制结构，通过安排语句或模块的顺序就能实现。C语言为分支控制提供了if-else和switch两类语句，为循环控制提供了for、while和do-while三类语句。,三种基本的控制结构是顺序、分支和循环。,函数定义函数调用函数递归,语句级控制,单位级控制,16/25,例2.5 求100到200之间的所有素数。,分析 可以设定两重循环：大循环（外层循环）控制整数i在100到200之间变化（用for语句），而小循环（内层循环）则用来判别i是否是素数（用while语句）。,第2章 实现基础,3 流程控制基础,17/25,函数与递归,比如：C语言提供了实数和整数的加法运算符号“+”来完成运算
16、；但是“+”不能对复数做加法运算；可以写一个函数来实现这个功能。,第2章 实现基础,3 流程控制基础,【定义】函数是一个完成特定工作的独立程序模块。只需定义一次，就可以多次调用。函数包括库函数和自定义函数两种。例如，scanf、printf等库函数由C语言系统提供定义，编程时只要直接调用即可。在程序设计中，往往根据模块化程序设计的需要，用户可以自己定义函数，属于自定义函数。,先定义复数类型 ImgType，以约定何为复数：struct Image double r;double i;typedef struct Image ImgType;,再定义复数的加法函数：ImgType ImgAdd(
17、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）函数功能的设计原则：结合模块的独立性原则，函数的功能要单一，不要设计多用途的函数，否则会降低模块的聚合度；,（2）函数规模的设计原则：函数的规模要小，尽量控制在50行代码以内，这样可以使得函数更易于维护；,（3）函数接口的设计原则：结合模块的独立性原则，函数的接口包括函数的参数（入口）和返回值（出
18、口），不要设计过于复杂的接口，合理选择、设置并控制参数的数量，尽量不要使用全局变量，否则会增加模块的耦合度。,19/25,递归函数,【定义】一个函数除了可以调用其他函数外，C语言还支持函数直接或间接调用自己。这种函数自己调用自己的形式称为函数的递归调用，带有递归调用的函数也称为递归函数。,两个关键点：（1）递归出口：即递归的结束条件，到何时不再递归调用下去;,第2章 实现基础,2.3 流程控制基础,（2）递归式子：当前函数结果与准备调用的函数结果之间的关系，如求阶乘函数的递归式子：Factorial(n)=n*Factorial(n-1)。,注意：程序代码不能写成上述式子！,递归调用,20/2
19、5,例2.8 设计函数求n!,图2.7 递归求解4!的过程,第2章 实现基础,2.3 流程控制基础,递归出口,递归式子,21/25,例2.9 汉诺塔（Tower of Hanoi）问题,（a）初始状态,（b）中间状态,3 流程控制基础,第2章 实现基础,【分析】可以用递归方法来求解汉诺塔问题，也就是将n个金片的移动问题转换为2个n-1个金片的移动问题。当n=1时，就不需要再递归了。,递归调用,22/25,3 流程控制基础,第2章 实现基础,23/25,例2.10 用递归方法求集合的中位数。,第2章 实现基础,2.3 流程控制基础,根据前面求解集合第K大整数问题的递归算法思路，还需要解决以下两个关键问题：,（1）如何根据元素e将集合S分解为S1和S2两个集合？可以采用临时申请空间的方法建立一个临时数组。,（2）如何设计递归函数的参数？将临时数组作为参数传递。,24/25,25/25,若Small=right，即没有比e小的元素，要另选一个 基准,
