第1章数据结构和算法优秀课件.ppt

《第1章数据结构和算法优秀课件.ppt》由会员分享，可在线阅读，更多相关《第1章数据结构和算法优秀课件.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 数据结构和算法第1页，本讲稿共93页2课程教学要求：1 1 1 1、上课做好笔记；、上课做好笔记；、上课做好笔记；、上课做好笔记；2 2、按时、独立、认真完成作业按时、独立、认真完成作业按时、独立、认真完成作业按时、独立、认真完成作业；3 3 3 3、实验课：实验报告（电子档）两份；、实验课：实验报告（电子档）两份；、实验课：实验报告（电子档）两份；、实验课：实验报告（电子档）两份；一份是按要求完成该实验内容的实验报告，一份是按要求完成该实验内容的实验报告，一份是按要求完成该实验内容的实验报告，一份是按要求完成该实验内容的实验报告，另一份则是算法优化后的实验报告；另一份则是算法优化后的

2、实验报告；另一份则是算法优化后的实验报告；另一份则是算法优化后的实验报告；实验成绩综合给出。实验成绩综合给出。实验成绩综合给出。实验成绩综合给出。4 4 4 4、勤奋学习，积极思考，提出问题，解决问题。、勤奋学习，积极思考，提出问题，解决问题。、勤奋学习，积极思考，提出问题，解决问题。、勤奋学习，积极思考，提出问题，解决问题。5 5 5 5、上课不迟到、不早退，班级考勤。、上课不迟到、不早退，班级考勤。、上课不迟到、不早退，班级考勤。、上课不迟到、不早退，班级考勤。第2页，本讲稿共93页3课程考核方法：课程考核方法：1 1、期末考试：、期末考试：50%50%；4 4、实验：、实验：30%30%

3、；2 2、学习笔记：、学习笔记：10%10%；3 3、作业、随堂测验、课程总结：、作业、随堂测验、课程总结：10%10%；第3页，本讲稿共93页4第1章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析第4页，本讲稿共93页51.1 数据与数据类型 1.1.1 数据和数据元素 1.1.2 数据类型 1.1.3 数据对象第5页，本讲稿共93页6数据数据 在计算机科学中，数据数据是指描述客观事物的数值、字符、描述客观事物的数值、字符、描述客观事物的数值、字符、描述客观事物的数值、字符、相关符号等所有能够输入到计算机

4、中并能被计算机程序处相关符号等所有能够输入到计算机中并能被计算机程序处相关符号等所有能够输入到计算机中并能被计算机程序处相关符号等所有能够输入到计算机中并能被计算机程序处理的符号的总称理的符号的总称理的符号的总称理的符号的总称。例如：例如：数值数据、字符、声音、图像、图形等第6页，本讲稿共93页7 数据元素数据元素 我们将数据中具有独立意义的个体称为数据元素数据元素。数据元素是数据的基本单位数据元素是数据的基本单位数据元素是数据的基本单位数据元素是数据的基本单位，在程序设计时通常作为一个，在程序设计时通常作为一个整体进行考虑和处理整体进行考虑和处理。有时，一个数据元素可由若干个有时，一个数据元

5、素可由若干个数据项数据项数据项数据项组成。数据项是数组成。数据项是数据的不可分割的最小单位据的不可分割的最小单位。第7页，本讲稿共93页8 为实现图书馆书目的自动检索，将与图书相关的数据做成如图所示的表，试分析表中的数据元素、数据项。10002数据结构陈英18.00书号书名作者价格10001计算机原理张明15.00 答：答：答：答：表中某一本书的相关数据表中某一本书的相关数据(表中每一行表中每一行)都是一个数据元素，每一个都是一个数据元素，每一个数据元素其具有独立意义。每一个数据元素由数据元素其具有独立意义。每一个数据元素由4 4个简单数据项个简单数据项(书号、书书号、书名、作者、价格名、作者

6、、价格)组成。组成。数据元素也被称为：记录、节点。例例例例1.11.1：第8页，本讲稿共93页91.1 数据与数据结构 1.1.1 数据和数据元素 1.1.2 数据类型 1.1.3 数据对象第9页，本讲稿共93页10 数据类型概念和定义数据类型概念和定义 是一个同类值的集合和定义在这个值集上的一组操作的总称。当我们在高级程序语言中定义每一种数据类型，在程序当我们在高级程序语言中定义每一种数据类型，在程序编译时计算机语言编译系统就知道了以下信息：编译时计算机语言编译系统就知道了以下信息：(1)(1)一组性质相同的值集合，一组性质相同的值集合，(2)(2)一个预定的存储体系，一个预定的存储体系，(

7、3)(3)定义在这个值集合上的一组操作。定义在这个值集合上的一组操作。数据类型数据类型可分为两类：数据类型数据类型数据类型数据类型简单数据类型简单数据类型简单数据类型简单数据类型、结构数据类型结构数据类型结构数据类型结构数据类型第10页，本讲稿共93页11 简单数据类型简单数据类型 简单类型的数据是不可分解的整体，如整数、实数、字符、指针、枚举量等。请解释整型数据类型。答：答：答：答：整型数据类型通常有整型数据类型通常有short(2short(2字节字节)、int(2int(2字节字节)、long(4long(4字节字节)等形式，其值集为某等形式，其值集为某个区间上的整数。个区间上的整数。如

8、果整型是两个字节表示的，其值集范围是：如果整型是两个字节表示的，其值集范围是：-32768-327683276732767，定义在整型数据上，定义在整型数据上的操作为：单目正的操作为：单目正(+)(+)操作、负操作、负(-)(-)操作，双目加操作，双目加(+)(+)操作、减操作、减(-)(-)操作、乘操作、乘(*)(*)操作、除操作、除(/)(/)操作和取模操作和取模(MOD)(MOD)操作等算术运算，双目关系操作等算术运算，双目关系(，=，=，等等)操作运算以及赋操作运算以及赋值值(=)(=)操作等。操作等。例例例例1.21.2第11页，本讲稿共93页12 结构数据类型结构数据类型 结构类型

9、结构类型由简单数据类型按照一定的规则构造而成。结构数据类型中还可包含结构数据类型，所以结构数据类型的数据可以分解成若干个简单数据类型的数据或子结构数据类型。也称作复合数据类型。第12页，本讲稿共93页13 数组数据类型分析。答：答：数组是结构数据类型，例如：数组是结构数据类型，例如：char name20,一维数组由若干个同种简单数据类型顺序排列而成，一维数组由若干个同种简单数据类型顺序排列而成，数组的每个值的数据类型相同；数组的每个值的数据类型相同；int a1010，二维数组看成是一个以，二维数组看成是一个以“一行一行”为一个元素的一维数组；为一个元素的一维数组；而而“一行一行”中简单元素

10、有序。中简单元素有序。float b51015等。三维数组看成是一个以等。三维数组看成是一个以“一个面一个面(行行*列列)”为一个元为一个元素的一维数组；素的一维数组；“面面”为二维数组。为二维数组。例例例例1.31.3第13页，本讲稿共93页14 定义表1.1表示的数据类型。解：解：解：解：表表1.1中每一个数据元素的数据项是由长整型的书号、字符型的书名、中每一个数据元素的数据项是由长整型的书号、字符型的书名、作者名以及实型的价格，我们可以采用如下的作者名以及实型的价格，我们可以采用如下的C语言语句来定义一个称为语言语句来定义一个称为EmployeeType的、新的的、新的(用户自定义用户自

11、定义)数据类型：数据类型：typedef struct long mun；char name10，book100；float price；EmployeeType；例例例例1.41.4第14页，本讲稿共93页15 然后，将这个名为然后，将这个名为EmployeeType的新数据类型当作一个基本数据类型来的新数据类型当作一个基本数据类型来使用。我们可以使用该数据类型定义一个变量使用。我们可以使用该数据类型定义一个变量x：EmployeeType x；它表达的是它表达的是“变量变量x将在后面的程序中用到，它指称一个大约将在后面的程序中用到，它指称一个大约118个字节个字节的主存储器区域，用于以二进

12、制依次存放四个值：一个整数、两个字符串的主存储器区域，用于以二进制依次存放四个值：一个整数、两个字符串和一个实数和一个实数”。第15页，本讲稿共93页161.1 数据与数据结构 1.1.1 数据和数据元素 1.1.2 数据类型 1.1.3 数据对象第16页，本讲稿共93页17 数据对象数据对象 数据对象是数据类型的实例，简称对象。数据对象举例。答：答：答：答：例如：例如：25，是整型数据对象。，是整型数据对象。A，是字符数据对象。，是字符数据对象。char*p，定义，定义p为一个字符指针对象。为一个字符指针对象。int a10，定义，定义a为一个含有为一个含有10个整型数的整型数组对象。个整型

13、数的整型数组对象。Rectangle r，定义，定义 r 为一个为一个Rectangle类型的对象。类型的对象。RECtangle rec，定义，定义 rec 为一个为一个RECtangle 抽象数据类型的对象。抽象数据类型的对象。例例例例1.51.5第17页，本讲稿共93页18第1章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析第18页，本讲稿共93页19 在计算机科学中，是指数据元素之间的关系，它包括三个方面的内容：(1)数据元素间的逻辑关系，即数据的(2)数据元素以一定的存储方式存放在计算机的存储器中

14、，形成数据元素的(3)在这些数据元素上定义的一组 数据结构数据结构数据结构数据结构逻辑结构逻辑结构逻辑结构逻辑结构存储结构存储结构存储结构存储结构运算集合运算集合运算集合运算集合第19页，本讲稿共93页20 数据的逻辑结构数据的逻辑结构定义：定义：数据元素之间的相互联系称为数据的逻辑结构。数据元素的逻辑结构的形式定义为一个二元组：B(K，R)B是一种数据结构，K是数据元素的有限集合，K=ki|1 i n，n 0 R是K上二元关系的有限集合，R=rj|1 j m，m 0。二元关系可以表示为序偶，(x，yK)，二元关系也可以表示为无序对，(x，y)(x，yK)。第20页，本讲稿共93页21 数据的

15、逻辑结构可以用图形形象地表示。用图形中的每一个节点(或叫顶点)对应着一个数据元素，用两节点间的连线(称有向边或弧)对应着关系中的一个序偶，其中第一个元素为起始点，第二个元素为终止点，箭头指向终止点。第21页，本讲稿共93页22例：序偶和无序对的图形表示如图所示。(a)无序对无序对(A，B)，(无向边无向边)；(b)序偶序偶，(也可以用也可以用2个单向箭头边个单向箭头边)；(c)序偶序偶，(有向边有向边)；(d)序偶序偶，(有向边有向边)第22页，本讲稿共93页23 根据数据元素之间关系的不同特性，通常有下列四类基本结构。线性逻辑结构线性逻辑结构 树型逻辑结构树型逻辑结构 图型逻辑结构图型逻辑结

16、构 集合逻辑结构集合逻辑结构第23页，本讲稿共93页24 线性逻辑结构线性逻辑结构 例：数据的逻辑结构 Linearity=(K，R)。其中K=01，02，03，04，05，06，07，08；R=r ，r=，。节点之间是一个对一个的关系，呈线性关系，是线性逻辑结构。节点之间是一个对一个的关系，呈线性关系，是线性逻辑结构。它的特征是：若结构为非空集，则该结构有且只有一个开始节点和它的特征是：若结构为非空集，则该结构有且只有一个开始节点和一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接一个终端节点，并且所有节点都最多只有一个直接前趋和一个直接后继。后继。第24页，本讲稿共93页25 树形

17、逻辑结构树形逻辑结构 例：数据的逻辑结构 Tree=(K，R)。其中K=A，B，C，D，E，F，G，H，I，J，R=r，r=，。它的特征是：节点之间是一个对多个的关系，一个节点可能有一个直它的特征是：节点之间是一个对多个的关系，一个节点可能有一个直接前趋和多个直接后继。呈树形关系，是树形数据结构接前趋和多个直接后继。呈树形关系，是树形数据结构(非线性结构非线性结构)。第25页，本讲稿共93页26 图形逻辑结构图形逻辑结构 例：数据的逻辑结构 Graph=(K，R)。其中K=0.1，0.2，0.3，0.4，0.5，0.6，0.7，R=r，r=(0.1，0.2)，(0.1，0.4)，(0.2，0.

18、3)，(0.2，0.6)，(0.2，0.7)，(0.3，0.7)，(0.4，0.6)，(0.5，0.7)，或者r=，它的特征是：节点之间是多个对多个的关系，它的特征是：节点之间是多个对多个的关系，一个节点可能有多个直接前趋和多个直接后继。一个节点可能有多个直接前趋和多个直接后继。呈图形关系呈图形关系 (非线性结构非线性结构)。第26页，本讲稿共93页27 集合逻辑结构集合逻辑结构例：数据的逻辑结构 set=(K，R)。其中K=1，2，3，4，5，6，7，8，9，10；R=，二元关系集为空，表示元素之间不存在关系，元素彼此是独立的。是集合。集合中数据元素之间的关系是松散的，实际运算时可以用其它结

19、构来表示它。第27页，本讲稿共93页28 数据的存储结构数据的存储结构 数据的存储结构是 用计算机处理具体问题时，必须考虑由这个具体问题抽象出的数据在计算机中的存储方式，以便于运算。通常情况下，数据在计算机中存储方式有以下四种：顺序存储顺序存储 链接存储链接存储 索引存储索引存储 散列存储散列存储指数据在计算机中的存储方式指数据在计算机中的存储方式指数据在计算机中的存储方式指数据在计算机中的存储方式第28页，本讲稿共93页29 顺序存储顺序存储 将逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系来体现 （3，5，6，8，23，12，54）=float an

20、例例例例1.61.6 第29页，本讲稿共93页30例例例例1.71.7第30页，本讲稿共93页31 链接存储链接存储 逻辑上相邻的结点不一定存储在物理位置相邻的存储单元中，结点间的逻辑关系由附加的指针字段来体现。一组数据元素的集合（3，5，6）365 例例例例1.81.8 第31页，本讲稿共93页32例例例例1.9 1.9 设有一组线性排列的数据元素(zhao，qian，sun，li，zhou，wu，zheng，wang)，其链接存储形式如图所示。第32页，本讲稿共93页33 索引存储索引存储 该方法在存储结点信息的同时，建立附加的索引表。索引表中的每一个索引项由唯一标识某结点的关键字以及该结

21、点的地址组成。例例例例1.101.10 赵1钱23孙56李891、赵文 36754232、赵五 675432823、钱四 896543224、钱进 365423756、孙军 245639889、李百 5674382第33页，本讲稿共93页34 散列存储散列存储 应用一个函数，将每一个结点的关键字作为该函数的自变量，得到相应的函数值作为该结点的存储地址。有函数 y=2x,集合（3，5，6）的存储：1 2 3 4 5 6 7 8 9 10 11 12 13 356例例例例1.111.11第34页，本讲稿共93页35 数据的运算数据的运算 正如整数和实数分别对应不同的运算一样，不同逻辑结构的数据有不

22、同的运算。数据运算不仅仅是加、减、乘、除、矩阵、微分、积分、方程等等这些数值计算问题，还包括像在一张表格中，进行查找记录，增加记录，修改记录，删除记录等等操作运算，而怎样才能进行这样的运算呢?在数据结构中，这些运算常常涉及算法问题。例如：例如：线性结构的数据数据可以非常方便地进行插入、删除数据元素，而对于树和图这样的线性结构的数据数据可以非常方便地进行插入、删除数据元素，而对于树和图这样的非线性结构的数据可以有查询数据元素之间的关系、遍历数据元素等运算非线性结构的数据可以有查询数据元素之间的关系、遍历数据元素等运算。通常情况下，逻辑关系不同的数据分别对应一组运算的集合；而数据的存储结构反映数通

23、常情况下，逻辑关系不同的数据分别对应一组运算的集合；而数据的存储结构反映数通常情况下，逻辑关系不同的数据分别对应一组运算的集合；而数据的存储结构反映数通常情况下，逻辑关系不同的数据分别对应一组运算的集合；而数据的存储结构反映数据在计算机内部的存储安排，对具有相同逻辑关系的数据考虑其不同的物理存储，目的是为据在计算机内部的存储安排，对具有相同逻辑关系的数据考虑其不同的物理存储，目的是为据在计算机内部的存储安排，对具有相同逻辑关系的数据考虑其不同的物理存储，目的是为据在计算机内部的存储安排，对具有相同逻辑关系的数据考虑其不同的物理存储，目的是为了提高算法的效率。了提高算法的效率。了提高算法的效率。

24、了提高算法的效率。第35页，本讲稿共93页36 数据的运算数据的运算栈的基本运算集合：(1)初始化栈：Inistack(S)，将栈S置为一个空栈(不含任何元素)。(2)进栈：Push(S，X)，将元素X插入到栈S中，也称为“入栈”、“压入”。(3)出栈：pop(S)，删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。(4)取栈顶元素：gettop(S)，取栈S中栈顶元素。(5)判栈空：StackEmpty(S)，判断栈S是否为空，若为空，返回值为true，否则返回值为false。第36页，本讲稿共93页37 根据以上分析，我们可以看到数据结构的概念主要包括根据以上分析，我们可以看到数据

25、结构的概念主要包括如图所示的三个方面的主要内容：如图所示的三个方面的主要内容：第37页，本讲稿共93页38 我们讨论两数据结构是否相同，主要看它们的逻辑结我们讨论两数据结构是否相同，主要看它们的逻辑结构、存储结构和运算集合是否相同，这三者中只要有一构、存储结构和运算集合是否相同，这三者中只要有一个不同，都不能称这两个数据结构相同。个不同，都不能称这两个数据结构相同。第38页，本讲稿共93页39 设有两个呈线性排列的数据分别是设有两个呈线性排列的数据分别是1,3,5,7,9和和0.1,0.2,0.4,0.6,0.8（其中的每个数是数据元素），现将它（其中的每个数是数据元素），现将它们分别存放在整

26、型一维数组们分别存放在整型一维数组A5和实型一维数组和实型一维数组B5中。现中。现在，我们来分析这两个数据的数据结构是否相同。在，我们来分析这两个数据的数据结构是否相同。例例例例1.121.12第39页，本讲稿共93页40 首先，这两个数据都是呈线性排列，则它们的逻辑结构均首先，这两个数据都是呈线性排列，则它们的逻辑结构均为线性逻辑结构；为线性逻辑结构；其次，它们分别存储在一维数组中，这使得逻辑位置相邻其次，它们分别存储在一维数组中，这使得逻辑位置相邻的数据元素在物理存储位置上也相邻，这样它们都属于顺序存的数据元素在物理存储位置上也相邻，这样它们都属于顺序存储结构；储结构；另外，根据另外，根据

27、C C语言语法规定，一维数组语言语法规定，一维数组A5A5中的数据元中的数据元素间可以进行加、减、乘、除和模运算，而一维数组素间可以进行加、减、乘、除和模运算，而一维数组B5B5中中的数据元素间只能进行加、减、乘、除运算；这样，数据的数据元素间只能进行加、减、乘、除运算；这样，数据1,3,5,7,91,3,5,7,9和数据和数据0.1,0.2,0.4,0.6,0.80.1,0.2,0.4,0.6,0.8的运的运算集合不同。可以断定，这两个数据有着完全不同的数据结构。算集合不同。可以断定，这两个数据有着完全不同的数据结构。第40页，本讲稿共93页41第1章 数据结构和算法 1.1 数据与数据类型

28、 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析第41页，本讲稿共93页42 数据类型数据类型数据类型数据类型 简单类型简单类型简单类型简单类型 int float double char 构造类型构造类型构造类型构造类型 数组数组 int5 char25 结构体结构体 struct 结构型名结构型名 数据类型名数据类型名 成员成员;第42页，本讲稿共93页43例例例例1.131.13 struct student long number;char name20;char sex;float score3;struct student A50;第4

29、3页，本讲稿共93页44 指针型指针型指针型指针型 int a,b,*p=&a,*q;q=&b；ap110110第44页，本讲稿共93页45定义1.12 指针就是变量的地址，一个变量的地址称为该变量的指针。指针变量(内存单元)是存储指针(地址)的变量。在语言中，允许用一个变量来存放指针，这种变量称为指针变量。在C语言中指针变量的定义和指针变量的引用格式如下：指针变量的定义格式为：类型标识符 *指针变量名指针变量的引用格式为：*指针变量名对指针变量的类型说明包括三个内容：(1)指针类型说明，即定义变量为一个指针变量；(2)指针变量名；(3)变量值(指针)所指向的变量的数据类型。变量的地址是由编译

30、系统分配的，对用户完全透明，用户一般可以不知道变量的具体地址。严格地说，一个指针是一个地址，是一个常量。而一个指针变量却可以被赋予不同的指针值，是变量。但有时也把指针变量简称为指针。为了避免混淆，我们约定：“指针”是指地址，是常量，“指针变量”是指取值为地址的变量。定义指针的目的是为了通过指针去访问内存单元。第45页，本讲稿共93页46【例1.29】试解释在语言中，变量说明语句：int*p 的意义是什么？答：因为在变量说明语句中，*是类型说明符，表示其后的变量是指针类型变量，即：p是一个指针变量，指针变量名为p，p所指向的变量的数据类型为int类型。所以该语句定义了一个整型指针变量p。注意：在

31、变量说明语句中，*是类型说明符；在变量引用时，*是运算符，注意区别。【例1.30】有如下指针说明语句：float*p1；/p1是指向浮点变量的指针变量 char*p2；/p2是指向字符变量的指针变量 在使用时p1和p2可以互相混合使用吗？答：在使用时不可以互相混合使用。一个指针变量只能存储同类型的变量的地址，例如p1只能指向浮点变量，p2只能指向字符变量，p1和p2不能时而指向一个浮点变量，时而又指向一个字符变量。第46页，本讲稿共93页47【例1.31】指针说明和使用中要注意什么问题？答：例如有变量说明语句：int a，*p，*q，下面一些问题是要注意的。(1)p=&a；/&是地址运算符，&

32、a表示变示变量a的地址，p=&a表示把整型变量a 的地址赋予整型指针变量p。(2)q=p；/由于p，q均为指向整型变量的指针变量，因此可以相互赋值。(3)*p=&a；/该赋值是错误的，作为一条赋值语句，被赋值的指针变量p前不能再加“*”说明符。因为在变量引用时，*是取内容运算符。(4)p=1000；/该赋值是错误的，指针变量的赋值只能赋予地址，决不能赋予任何其它数据，否则将引起错误。(5)int i=3，*p=&i；/定义了一个整型变量i 且初值为3；定义了一个整型指针变量p，同时将i的地址存放于指针变量p中。注意：此种方法是在定义变量并且赋初值，*p=&i的用法是可以的，其等价于：int i

33、=3，*p；p=&i；。注意与第(3)小题的区别。第47页，本讲稿共93页48 已知定义：int x，*k=&x；试问：表达式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：答：对于*k，表示变量x。对于&x，&是地址运算符，&x表示变示变量x的地址。对于*&x，表示*k，即变量x。对于&*k，*k表示变量x，&*k即表示变量x的地址(&x)。对于*&k，表示变量k。而&*x则存在语法错误。第48页，本讲稿共93页49 用户自定义类型用户自定义类型用户自定义类型用户自定义类型 typedef 类型名类型名1 类型名类型名2;(1)typedef int AB;(2)typedef s

34、truct long number；stutable;stutable A50;(3)typedef int *POINT;POINT p;例例例例1.151.15第49页，本讲稿共93页50 运算符运算符运算符运算符 指向结构体成员的指针引用 结构体成员的引用 struct student long number;float score;x,*p=&x;p score=95;x.number=1001L;例例例例1.161.16第50页，本讲稿共93页51 函数函数函数函数 系统函数系统函数系统函数系统函数 内存分配函数（申请内存函数）内存分配函数（申请内存函数）void *malloc(i

35、nt size)功能功能：申请大小为size个字节的内存。返回值返回值：若申请成功，则返回所分配 的内存单元首地址。第51页，本讲稿共93页52 内存释放函数内存释放函数 void free(void *blocd)功能功能：释放由malloc等内存分配函数申请到的内存，其首地址放在参数block中。返回值返回值：无注：注：注：注：当程序中使用了上述两个函数时，应在程序的开头使用：当程序中使用了上述两个函数时，应在程序的开头使用：include “alloc.h”第52页，本讲稿共93页53例例例例1.181.18 char *p1;p1=malloc(80);scanf(“%s”,p1);p

36、rintf(“%s”,p1);free(p1);第53页，本讲稿共93页54 用户自定义函数用户自定义函数用户自定义函数用户自定义函数 数据类型符数据类型符 函数名（形参表）函数名（形参表）形参说明；形参说明；函数体；函数体；return语句；语句；函数返回函数返回值的类型值的类型return (值值or变量变量)；无返回值：无返回值：return;第54页，本讲稿共93页55 函数调用函数调用函数调用函数调用 a.函数名（实参表）；函数名（实参表）；b.变量函数名（实参表）；变量函数名（实参表）；求三个整数的和、积、最大值、最小值。求三个整数的和、积、最大值、最小值。main()int a,

37、b,c,x,y,v,w;scanf(“%d%d%d”,&a,&b,&c);x=sum(a,b,c);y=mul(a,b,c);v=max(a,b,c);w=min(a,b,c);printf(“%d%d%d%d”,x,y,v,w);例例例例1.191.19第55页，本讲稿共93页2023/2/956int sum(int a,int b,int c)return(a+b+c);int mul(int a,int b,int c)return(a*b*c);int max(int a,int b,int c)int max(int a,int b,int c)int x;int x;if(ab)

38、x=a;else x=b;if(ab)x=a;else x=b;if(xc)x=c;if(xc)x=c;return x;return x;第56页，本讲稿共93页57 文件操作文件操作文件操作文件操作 从键盘输入两个学生数据，写入一个文件中，再读出这两个学生的数据从键盘输入两个学生数据，写入一个文件中，再读出这两个学生的数据显示在屏幕上。文件操作的显示在屏幕上。文件操作的C语言程序例如下。语言程序例如下。truct stu char name15；int num；int age；char addr20；boya2，boyb2，*pp，*qq；/定义两个结构数组定义两个结构数组boya和和 b

39、oyb以及两个结构指针变量以及两个结构指针变量pp和和qq例例例例1.201.20第57页，本讲稿共93页58void main()FILE*fp；/定义文件指针变量定义文件指针变量fp int i；pp=boya；/pp指向指向boya qq=boyb；/qq指向指向boyb if(fp=fopen(stu_list，w+)=NULL)/以读写方式打开以读写方式打开d盘根目录下的文件盘根目录下的文件“stu_list”，/如果文件打开出错如果文件打开出错(NULL)则输出出错信息并退出程序则输出出错信息并退出程序 printf(Cannot open file strike any key

40、exit!)；exit(1)；第58页，本讲稿共93页59 printf(n input datan)；for(i=0；iname，&pp-num，&pp-age，pp-addr)；/输入二个学生数据输入二个学生数据 pp=boya；fwrite(pp，sizeof(struct stu)，2，fp)；/写入写入fp文件指针所指的该文件中去文件指针所指的该文件中去 rewind(fp)；/把文件内部位置指针移到文件首把文件内部位置指针移到文件首 fread(qq，sizeof(struct stu)，2，fp)；/读出两块学生数据到读出两块学生数据到qq指针所指的结构数组指针所指的结构数组bo

41、yb printf(nnnametnumber age addrn)；第59页，本讲稿共93页60 for(i=0；iname，qq-num，qq-age，qq-addr)；/在屏幕上显示输出在屏幕上显示输出 fclose(fp)；/关闭文件关闭文件fp 该程序执行结果如下：该程序执行结果如下：该程序执行结果如下：该程序执行结果如下：input data John 1001 22 Beijing Tom 1002 21 Shanghai name number age addr John 1001 22 Beijing Tom 1002 21 Shanghai 第60页，本讲稿共93页61 程

42、序测试程序测试程序测试程序测试 是指在计算机上利用输入数据是指在计算机上利用输入数据(测试数据测试数据)来实来实际运行该程序，把程序的实际行为与所期望的行为进行比较。如际运行该程序，把程序的实际行为与所期望的行为进行比较。如果两种行为不同，就可判定程序中有问题存在。果两种行为不同，就可判定程序中有问题存在。但是，对于大多数实际的程序，可能的用于测试数据的数但是，对于大多数实际的程序，可能的用于测试数据的数量太大了，不可能进行穷尽测试。量太大了，不可能进行穷尽测试。实际用来测试的输入数据空间的子集称之为实际用来测试的输入数据空间的子集称之为程序测试程序测试程序测试程序测试测试集测试集测试集测试集

43、第61页，本讲稿共93页62 测试数据的设计测试数据的设计测试数据的设计测试数据的设计 测试的目的是找出程序中的错误。如果用来寻找错误的测试测试的目的是找出程序中的错误。如果用来寻找错误的测试数据找不到错误，那么我们对该程序的正确性就有了自信心。为数据找不到错误，那么我们对该程序的正确性就有了自信心。为此我们必须知道对于该测试数据，程序的正确结果应是什么。此我们必须知道对于该测试数据，程序的正确结果应是什么。设计测试数据的技术分为两类：设计测试数据的技术分为两类：1 1、黑盒法黑盒法黑盒法黑盒法 2 2 2 2、白盒法、白盒法、白盒法、白盒法第62页，本讲稿共93页63黑盒法黑盒法黑盒法黑盒法

44、 黑盒法考虑的是程序的功能，而不是实际的代码编写的黑盒法考虑的是程序的功能，而不是实际的代码编写的如何。如何。最流行的黑盒法是最流行的黑盒法是I/OI/O分类及因果图，本节仅探讨分类及因果图，本节仅探讨I/OI/O分分类。类。在这种方法中，输入数据和在这种方法中，输入数据和(或或)输出数据空间被分成输出数据空间被分成若干类，不同类中的数据会使程序所表现出的行为有质的不若干类，不同类中的数据会使程序所表现出的行为有质的不同，而相同类中的数据则使程序表现出本质上类似的行为。同，而相同类中的数据则使程序表现出本质上类似的行为。第63页，本讲稿共93页64例例例例1.211.211.211.21 一元

45、二次方程求解的例子中有三种本质上不同的行为：一是一元二次方程求解的例子中有三种本质上不同的行为：一是产生复数根，二是产生实数根且不同，产生实数根且相同。产生复数根，二是产生实数根且不同，产生实数根且相同。可以根据这三种行为把输入空间分为三类。可以根据这三种行为把输入空间分为三类。第一类中的数据将产生第一种行为；第一类中的数据将产生第一种行为；第二类中的数据将产生第二种行为；第二类中的数据将产生第二种行为；第三类中的数据将产生第三种行为。第三类中的数据将产生第三种行为。一个测试集应至少从每一类中抽取一个输入数据进行测试。一个测试集应至少从每一类中抽取一个输入数据进行测试。第64页，本讲稿共93页

46、65白盒法白盒法白盒法白盒法 白盒法是通过检查程序代码来设计测试数据，以便使测白盒法是通过检查程序代码来设计测试数据，以便使测试数据的执行结果能很好地覆盖程序的语句以及执行路径。试数据的执行结果能很好地覆盖程序的语句以及执行路径。对一个测试集最起码的要求就是使程序中的每一条语句都至对一个测试集最起码的要求就是使程序中的每一条语句都至对一个测试集最起码的要求就是使程序中的每一条语句都至对一个测试集最起码的要求就是使程序中的每一条语句都至少执行一次。这种要求被称为少执行一次。这种要求被称为少执行一次。这种要求被称为少执行一次。这种要求被称为“语句覆盖语句覆盖语句覆盖语句覆盖”。第65页，本讲稿共9

47、3页66程序调试问题：程序调试问题：定义1.17 调试是确定并纠正程序错误的过程。在许多情况下，调试程序主要依靠程序员的经验，一个有经验的程序员能够很快地确定并纠正程序中的错误。在这里，详细地介绍程序调试问题显然超出了我们课程的范围，但我们可以提出一些建议，供读者参考。调试程序主要采取以下方法：1逻辑推理的方法。当程序出现错误时，一般首先用逻辑推理的方法，分析程序或者算法，来确定错误语句。2程序跟踪的方法。利用调试工具对程序进行跟踪，以确定程序什么时候开始出现错误。3代码分离的方法，当需要跟踪得语句太多时，试着把可疑的代码分离出来，专门跟踪这段代码。4从独立函数开始的方法。在测试和调试一个有错

48、的程序时，从一个与其他函数独立的函数开始，这个函数应该是一个典型的输入或输出函数(请读者考虑为什么？)。调试成功之后，再引入一个还没有测试的函数。依次下去，调试的范围一步一步地扩大。这种方法被称为增量测试与调试。第66页，本讲稿共93页67第1章 数据结构和算法 1.1 数据与数据类型 1.2 数据结构 1.3 算法的描述工具C语言 1.4 算法和算法评价 1.5 算法性能分析第67页，本讲稿共93页68 什么是算法什么是算法什么是算法什么是算法 算法算法是为解决一个特定问题而采取的确定的有限的步骤，是指是为解决一个特定问题而采取的确定的有限的步骤，是指令的有限序列。令的有限序列。算法算法具有

49、输入、输出、有穷性、确定性和可行性特性。具有输入、输出、有穷性、确定性和可行性特性。【例例1.51】在学习数学时，对一道数学题解题过程的描述就是一个在学习数学时，对一道数学题解题过程的描述就是一个解题算法，对一个数学证明题的证明过程同样是证题算法。解题算法，对一个数学证明题的证明过程同样是证题算法。但也并不是只有但也并不是只有“计算计算”的问题才有算法，对一个特定问题的解的问题才有算法，对一个特定问题的解决过程的描述也是算法决过程的描述也是算法【例例1.52】如手工书上对一个纸鹤折法的图示描述就是一个算法。因为如手工书上对一个纸鹤折法的图示描述就是一个算法。因为按照图示的方法和步骤我们能完成一

50、个纸鹤的制作，它解决了一个特定按照图示的方法和步骤我们能完成一个纸鹤的制作，它解决了一个特定问题。对于一首歌曲的乐谱也可以称为该歌曲的算法。因为它指定了演问题。对于一首歌曲的乐谱也可以称为该歌曲的算法。因为它指定了演奏该歌曲的每一个步骤，按照它的描述就能演奏出预定的曲子。奏该歌曲的每一个步骤，按照它的描述就能演奏出预定的曲子。第68页，本讲稿共93页69算法的特性算法的特性算法的特性算法的特性 按照算法的定义，一个算法必须具备下列五个特性：有穷性：必须在执行有穷个操作之后结束，而且“有穷性”也应在合理的范围内。确定性：也称无二义性。算法中，对每一个操作的描述都必须是精确的、有确切的含义，而不是