2014/5/9
1
西北师范大学经济管理学院\r ----信息管理系
\r本演示文稿可能包含观众讨论和即席反应。使用 PowerPoint 可以跟踪演示时的即席反应，\r\r在幻灯片放映中，右键单击鼠标\r请选择“会议记录”\r选择“即席反应”选项卡\r必要时输入即席反应\r单击“确定”撤消此框\r\r此动作将自动在演示文稿末尾创建一张即席反应幻灯片，包括您的观点。\r
数据结构课件
用C语言描述
2014/5/9
2
第1章 绪 论
●1.7 ?关于学习数据结构
1.1? 数据结构的基本概念(定义)
1.2 数据结构的内容（研究范围）
1.3? 算法设计
1.4? 算法描述工具
1.5? 对算法作性能评价
1.6? 数据结构与C语言表示
2014/5/9
3
1.1 数据结构的基本概念（定义）
数据结构的相关名词：\r数据（Data）\r数据元素（Data Element） \r数据对象（Data Object） \r数据结构（Data Structure） \r数据类型(Data Type) \r数据抽象与抽象数据类型
2014/5/9
4
数据（Data）
定义：\r 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。\r 数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。
例如对C源程序
2014/5/9
5
数据元素（Data Element）
定义：\r 数据元素是组成数据的基本单位 ，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：
2014/5/9
6
数据对象（Data Object）
定义：\r 数据对象是性质相同的数据元素的集合，是数据的一个子集。
整数集合：N={0，±1，±2，…} 无限集\r字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ} 有限集
例如：
2014/5/9
7
数据结构（Data Structure）
定义：\r 数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。 例如表结构：
2014/5/9
8
数据结构（Data Structure）
树型结构
图结构
2014/5/9
9
数据类型(Data Type)
定义：\r 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
如在高级语言中，整型类型的取值范围为：\r-32768~ 32767，运算符集合为加、减、乘、除、取模，即 、-、*、/、%。
2014/5/9
10
数据类型(Data Type)
高级语言中的数据类型分为两大类：
1.原子类型，其值不可分解。如C语言中的标准类型（整型、实型、字符型、）。
2.结构类型，其值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。
指针类型属于哪种类型？
2014/5/9
11
数据抽象与抽象数据类型
数据的抽象\r抽象数据类型(Abstract Data Type) \r抽象数据类型实现 \rADT的表示与实现\r面向对象的概念\r结构化的开发方法与面向对象开发方法不同点
2014/5/9
12
1.2 数据结构的内容
逻辑结构 \r存储结构 \r运算集合
2014/5/9
13
逻辑结构
定义：\r 数据的逻辑结构是指数据元素之间逻辑关系描述。
形式化描述：\r Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。
四类基本的结构\r 集合结构、线性结构、树型结构、图状结构。
2014/5/9
14
集合结构
定义：\r 结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
例如：
2014/5/9
15
线性结构
定义：\r 结构中的数据元素之间存在着一对一的线性关系。
例如：
2014/5/9
16
树型结构
定义：\r 结构中的数据元素之间存在着一对多的层次关系。
例如：
2014/5/9
17
图状结构或网状结构
定义：\r 结构中的数据元素之间存在着多对多的任意关系。
例如：
2014/5/9
18
综上所述，数据的逻辑结构可概括为：
逻辑结构
2014/5/9
19
存储结构
定义：\r 存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。
形式化描述：\r D要存入机器中，建立一从D的数据元素到存储空间M单元映象S ，D→M，即对于每一个d， d∈D,都有唯一的z∈M使S（D）=Z, 同时这个映象必须明显或隐含地体现关系R。
2014/5/9
20
逻辑结构与存储结构的关系为：
存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。
数据元素之间关系在计算机中的表示方法：\r顺序映象 （顺序存储结构） \r非顺序映象（非顺序存储结构）
存储结构
2014/5/9
21
运算集合
例如工资表：
2014/5/9
22
数据结构的内容
综上所述，数据结构的内容可归纳为三个部分，\r逻辑结构、存储结构和运算集合：\r按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据上定义了一个运算的集合，就叫做数据结构。\r
2014/5/9
23
1.3 算法
算法（Algorithm）定义 \r算法的特性 \r算法设计的要求
2014/5/9
24
算法（Algorithm）定义
定义：\r Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem.\r 算法是规则的有限集合，是为解决特定问题而规定的一系列操作。 \r
2014/5/9
25
算法的特性
1. 有限性：有限步骤之内正常结束，不能形成无穷循环
2. 确定性：算法中的每一个步骤必须有确定含义，无二\r 义性得以实现。
3. 输 入： 有多个或0个输入
4. 输 出： 至少有一个或多个输出。
5. 可行性：原则上能精确进行，操作可通过已实现基本\r 运算执行有限次而完成。
2014/5/9
26
算法设计的要求
算法的正确性
算法特征：
可读性
健壮性
高效率和低存储量
例如要求n个数的最大值问题\r给出算法如下：\r max:=0;\r for（i=1 ；i<= n ;i ） \r { scanf("%f", x);\r if (x>max) max=x;\r }
2014/5/9
27
1.4 算法描述的工具
概述：\r 算法 数据结构=程序 \r算法、语言、程序的关系 \r设计实现算法过程步骤\r类描述算法的语言选择\r\r
2014/5/9
28
算法、语言、程序的关系
1. 算法：描述了数据对象的元素之间的关系（包括数据逻辑关系、存贮关系描述）。
2. 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。
3.程序是算法在计算机中的实现。
2014/5/9
29
设计实现算法过程步骤
1. 找出与求解有关的数据元素之间的关系
2. 确定在某一数据对象上所施加运算
3. 考虑数据元素的存储表示
4. 选择描述算法的语言
5.设计实现求解的算法，并用程序语言加以描述。
2014/5/9
30
类描述算法的语言选择
类语言：
类语言是接近于高级语言而又不是严格的高级语言，具有高级语言的一般语句设施，撇掉语言中的细节，以便把注意力主要集中在算法处理步骤本身的描述上。
2014/5/9
31
3.赋值语句
对C语言作以下描述：
（1）简单赋值
1）〈变量名〉=〈表达式〉 \r 2） 〈变量〉 ， \r 3） 〈变量〉- -，
（2）串联赋值
〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉
2014/5/9
32
对C语言作以下描述：
（4）条件赋值
〈变量名〉=〈条件表达式〉？〈表达式1〉:〈表达式2〉
（3）成组赋值
(<变量>,<变量2>,<变量3>,…<变量k〉=(<表达式1>,<表达式2 >\r ,<表达式3>,…<表达式k>)\r〈数组名1〉[下标1][下标2]=〈数组名2〉[下标1][下标2]
2014/5/9
33
4.条件选择语句
对C语言作以下描述：
if (<表达式>) 语句;
if (<表达式>) 语句1;\r else 语句2;\r
2014/5/9
34
情况语句
switch (<表达式>）\r {case 判断值1:\r 语句组 1；\r break;\r case 判断值2:\r 语句组 2；\r break; \r……
case 判断值n:\r 语句组n;\r break;\r [default: \r 语句组；\r break;]\r }
对C语言作以下描述：
2014/5/9
35
对C语言作以下描述：
5.循环语句
for 语句
for (<表达式1>；<表达式2>；<表达式3>）\r{循环体语句；}
2014/5/9
36
while 语句
while (<条件表达式>）\r {循环体语句；\r }
对C语言作以下描述：
do –while 语句
do { 循环体语句\r }while (<条件表达式>）
2014/5/9
37
1.5 对算法作性能评价
评价算法的标准：\r 评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。 \r性能评价 \r有关数量关系计算
2014/5/9
38
性能评价
定义：\r 对问题规模与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。
问题规模N—对不同的问题其含义不同：\r 对矩阵是阶数；\r 对多项式运算是多项式项数；\r 对图是顶点个数；\r 对集合运算是集合中元素个数。
2014/5/9
39
有关数量关系计算
数量关系评价体现在时间——算法在机器中所耗费时间。\r数量关系评价体现在空间——算法在机器中所占存储量。\r关于算法执行时间\r语句频度 \r算法的时间复杂度\r数据结构中常用的时间复杂度频率计数 \r最坏时间复杂度 \r算法的空间复杂度
2014/5/9
40
关于算法执行时间
定义：\r 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。
分析：\r 不是针对实际执行时间的精确地算出算法执行具体时间，而是针对算法中语句的执行次数做出估计，从中得到算法执行时间的信息。
2014/5/9
41
语句频度
定义：\r 语句频度是指该语句在一个算法中重复执行的次数。
例如：\r两个矩阵相乘
算法语句 对应的语句频度 \r 1 for（i=0；i< n;i ） n\r 2 for （j=0；j 2014/5/9 42 算法的时间复杂度 算法的时间复杂度，即是算法的时间量度记做： T(n)=O(f(n)) 例如给出X=X 1 （1）x=x 1 ；时间复杂度为O(1)，称为常量阶； （2）for (i=1; i<= n; i ) x=x 1; 时间复杂度为O(n)，称为线性阶； （3）for (i=1; i<= n; i )\r for (j=1;j<= n; j ) x=x 1; 时间复杂度为O(n2), 称为平方阶。 2014/5/9 43 常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个: O(1) 常数型 O(n)线性型 O(n2)平方型 \rO(n3)立方型 O(2n)指数型 O(log2n)对数型\rO(nlog2n)二维型 按时间复杂度由小到大排列的频率表： 2014/5/9 44 常用的时间复杂度频率计数 常用的时间复杂度频率表： 2014/5/9 45 最坏时间复杂度 定义：\r 讨论算法在最坏情况下的时间复杂度，即分析最坏情况下以估计出算法执行时间的上界。 例如冒泡排序算法 2014/5/9 46 void bubble(int a[], int length)\r{将a中整数数组重新排序，达到递增有序}\r int i=0, j, temp;\r int change ;\r do{\r change=false ;\r for(j=1;j {\rtemp= a[j];\ra[j]=a[j 1];\ra[j 1]=temp;\rchange=true;\r }\r i=i 1 ;\r }\r while(i 最坏时间复杂度 2014/5/9 47 算法的空间复杂度 定义： 用空间复杂度作为算法所需存储空间的量度，\r 记做： S(n)=O(f (n)) 。\r 2014/5/9 48 1.6 数据结构与C语言表示 1.6.1 数据结构与程序设计的关联性 问题描述：欲求1名学生10次C语言程序设计的测试成绩总分与平均分。其中10次测验的成绩分别为：80，85，77，56，68，83，90，92，80，98。 2014/5/9 49 程序示例1-1： main()\r { int sum，verage； /*总分，平均分*/\r int t1,t2,t3,t4,t5,t6,t7,t8,t9,t10； /*10个变量存10次成绩*/\r t1=80；t2=85；t3=77；t4=56； t5=68； /*分别赋值*/\r t6=83；t7=90；t8=92；t9=80；t10=98;\r sum= t1 t2 t3 t4 t5 t6 t7 t8 t9 t10; /*计算总分*/\r average=sum/10; /*计算平均分*/\r printf(“总分=%d\n”,sum); printf(“平均分=%d\n”, average);\r } 2014/5/9 50 根据测试次数与测试成绩的关系，采用数组结构存储测验成绩，提高了程序的适用范围。\rmain()\r { int sum，erage；int i;\r int t[10] =80，85，77，56，68，83，90，92，80，98} /*分别赋值*/\r sum=0; /*总分置初值*/\r for (i=0; i<10; i )\r sum=sum t[i];\r average=sum/10; /*计算平均分*/\r printf(“总分=%d\n”,sum); printf(“平均分=%d\n”, average);\r } 程序示例1-2： 2014/5/9 51 1.6.2 结构化程序设计与函数的模块化 结构化程序设计 ：是为使程序具有合理的结构，以保证程序正确性而规定的一套程序设计的方法 。 程序设计的实质：算法 数据结构=程序 \r即“程序是在数据的特定表示方式的基础上，对抽象算法的具体描述”。\r程序结构=控制结构 数据结构 2014/5/9 52 ①?????? 结构化程序设计目的 通过设计结构良好的程序，以程序的静态良好结构保证程序动态执行的正确性，使程序易理解、易调试、易维护，以提高软件开发的效率，减少出错率。 ②结构化程序设计的构成单元 任何程序都可由顺序、选择、重复三种基本控制结构来组成。 ③结构化程序设计方法 其一：“自顶向下，逐步求精”的设计思想 ；其二：“独立功能，一个入口，一个出口“的模块化结构； 其三：“仅用三种基本控制结构”的设计原则 2014/5/9 53 1.6.3 面向对象与抽象数据类型 1.面向对象的概念： 面向对象=对象 类 继承 通信 对象：指在应用问题中出现的各种实体、事件、规格说明等 。 类：具有相同属性和服务的对象 继承：是面向对象方法的最有特色的方面。 2014/5/9 54 面向对象程序设计的特点是封装性、继承性和多态性 与数据结构密切相关的是定义在数据结构上的一组操作。 基本操作主要有：\r⑴插入：在数据结构中的指定位置上增添新的数据元素 ；\r⑵删除：删去数据结构中某个指定数据元素 ；\r⑶更新：改变数据结构中某个元素的值，在概念上等价于删除和插入操作的组合 ；\r⑷查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值）；\r ⑸排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。 2014/5/9 55 结构化与面向对象开发方法的不同点 结构化的开发方法：是面向过程的开发方法，首先着眼于系统要实现的功能。 面向对象的开发方法：\r首先着眼于应用问题所涉及的对象，包括对象、对象属性和要求的操作，从而建立对象结构和为解决问题需要执行的时间序列。 2014/5/9 56 用抽象数据类型的概念来指导问题的求解过程： 2．抽象数据类型与问题求解方法 定义：\r 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。 一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。 2014/5/9 57 数据的抽象 汇编语言中十进制表示的数据98.65、9.6E3等, 它们是二进制数据的抽象; 高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等，\r还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。\r 2014/5/9 58 抽象数据类型 线性表的抽象数据类型的描述： ADT Linear_list\r数据元素 所有ai属于同一数据对象，i=1，2，……，n n≥0；\r逻辑结构 所有数据元素ai（i=1，2，…，n-1）存在次序关系\r 2014/5/9 59 抽象数据类型实现 传统的面向过程的程序设计 实现的三种方法： “包”、“模型”的设计方法 面向对象的程序设计（Object Oriented Programming，简称OOP）\r 2014/5/9 60 ADT的表示与实现 ADT的定义： ADT 基本操作的定义格式为： <操作名称> (参数表) 操作前提:<操作前提描述> 操作结果:<操作结果描述> 2014/5/9 61 关于参数传递： 参数表中的参数有值参和变参两种。 用标准C语言表示和实现ADT描述时，主要有两个方面： 二、用C语言函数实现各操作。 一、通过结构体将int、float等固有类型组合到一起,构成一个结构类型,再用typedef为该类型或该类型指针重新起一个名字。 ADT的表示与实现 2014/5/9 62 1.6.4 算法描述规范与设计风格 1. 算法表示格式与函数模块化 [函数返回值类型] 函数名（[形式参数及说明]）\r{ 内部数据说明；\r 执行语句组；\r } /*函数名*/ 算法表示格式 2014/5/9 63 1.6.4 算法描述规范与设计风格 函数的模块化 1. 算法表示格式与函数模块化 [包含文件语句]\r[宏定义语句]\r[自定义类型语句]\r[所有子函数的原型说明]\r[子函数1定义]\r.\r.\r.\r[子函数n定义]\r [主函数定义] 2014/5/9 64 2. 算法描述要点 1.6.4 算法描述规范与设计风格 加上必要的注释 注释形式可以用/*字符串*/ 避免函数返回值隐含说明 预定义常量和类型 # define TRUE 1\r # define FALSE 0\r # define MAXSIZE 100\r # define OK 1\r # define ERROR 0 2014/5/9 65 避免可能出现的二义性表达 注意不同的退出语句区别 return <表达式>或return：用于函数结束。\rbreak语句：可用在循环语句或switch语句中结束循环过程或跳出情况语句。\rcontinue语句：可用在循环语句中结束本次循环过程，进入下一次循环过程。\r exit语句：表示出现异常情况时，控制退出函数。 使用有意义的函数名与变量名 2. 算法描述要点 1.6.4 算法描述规范与设计风格 简化输入、输出表述 规范多分支转向 2014/5/9 66 3. 与参数传递的相关技术 1.6.4 算法描述规范与设计风格 变量的作用域 全局变量：程序中所有函数都可以访问的量 局部变量：只能在该函数中访问的量。 参数传递方式 ?????参数传递是函数之间进行信息通讯的重要渠道。其参数传递的主要方式有传值和传地址两类。函数参数表中的参数有两种：第一种参数只为操作提供待处理数据,又称值参；第二种参数既能为操作提供待处理数据，又能返回操作结果，也称变量参数。 2014/5/9 67 #include 关于参数传递示例源程序： 2014/5/9 68 void main()\r { int x=100,y=800;\r swap1(x,y); /*调用函数swap1()*/\rprintf(“\n调用swap1后x= %d,y=%d”,x,y); /*输出调用swap1后的数据*/\rx=100;y=800;\rswap2(