数据结构C语言 .pptx

《数据结构C语言 .pptx》由会员分享，可在线阅读，更多相关《数据结构C语言 .pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学习提要掌握本课程所涉及到的基本名词、术语和概念，特别是数据的逻辑结构和存储结构之间的关系及性质。了解抽象数据类型的定义、表示和实现方法。理解算法设计的五个要素和基本要求；掌握算法效率的度量方法，着重学习算法的时间复杂度分析。第1页/共51页教学重点数据、数据元素、数据项；逻辑结构和存储结构在概念上的联系与区别；数据结构及其三个组成部分；抽象数据类型和数据抽象；评价算法优劣的标准及方法。第2页/共51页1.1什么是数据结构一、为什么要学习数据结构？1、电子计算机的主要用途：早期：主要用于数值计算。后来：处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。第3页/共51页用计

2、算机解决问题的过程建立模型构造求解算法选择存储结构编写程序测试描述问题的共性描述问题的求解方法将问题涉及的数据存储到计算机中分析问题的过程数据结构的作用进行更为复杂的算法设计选择合理的存储结构提高编程技术第4页/共51页引引 例例书目自动检索系统的数学模型书目自动检索系统的数学模型登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表第5页/共51页人机对奕问题的数学模型人机对奕问题的数学模型树树.第6页/共51页CEDABABACADBABCBDDADBDCEAEBECED图十字路口的交通灯管理问题的数学模型第7页/共51页求解非数值计算的

3、问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。第8页/共51页问题：学习数据结构有什么用？答：计算机内的数值运算依靠数学方程，而非数值运算（如表、树、图等）则要依靠数据结构。同样的数据对象，用不同的数据结构来表示，运算效率可能有明显的差异。程序设计的实质是对实际问题选择一个好的数据结构，加之设计一个好的算法。而好的算法在很大程度上取决于描述实际问题的数据结构。算法+数据结构=程序 提高复杂程序设计的能力 培养算法设计能力 为后继课

4、程（如操作系统、编译原理等）打基础。第9页/共51页数据结构课程的形成和发展形成阶段60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，美唐欧克努特教授开创了数据结构的最初体系，计算机程序设计技巧第一卷基本算法，“数据结构”被列入美国一些大学计算机科学系的教学计划。发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，80年代初，我国高校陆续开设该课程。第10页/共51页数据结构课程所处的地位：介于数学、计算介于数学、计算机硬件和计算机机硬件和计算机软件三者之间的软件三者之间的一门核心课程。一门核心课程。第

5、11页/共51页1.2 1.2 基本概念和术语1.2.1基本概念1.数据（data）：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合,是计算机程序加工的”原料”。分类：数值性数据 非数值性数据第12页/共51页2、数据元素（data element）数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。有时一个数据元素可以由若干数据项(Data Item)(Data Item)组成。数据项是数据不可分割的最小标识单位。数据元素又称为元素、结点、记录。学号学号 姓名姓名成成绩绩001LiLy89002Yang98003Zhao78第

6、13页/共51页3、数据对象（data object）l数据对象是具有相同性质的数据元素的集合。u整数数据对象 N=0,1,2,u字母字符数据对象 C=A，B，Zu学生成绩数据对象Cj=（101，jane，80），（102，jack，90），（103，jerry，75）学号学号姓名姓名成绩成绩001LiLy89002Yang98003Zhao78第14页/共51页4、数据结构(data structure)数据结构是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(Structure)。数据

7、结构是一堆数据元素和这些数据元素之间的关系的总和。第15页/共51页 按数据元素之间关系的不同特性，通常有4类基本结构（1）集合 结构中的数据元素除了“同属于一个集合”外，别无其它关系。（2）线性结构 结构中的数据元素之间存在一对一的关系。（3）树型结构 结构中的数据元素之间存在一对多的关系。（4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。线性结构线性结构线性结构线性结构 数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系数据元素之间存在着一个对一个的关系bindevetclibuseretcuser集合集合集合集合 数据元素

8、之间无特殊关系数据元素之间无特殊关系数据元素之间无特殊关系数据元素之间无特殊关系devlibbindevetcuser树形结构树形结构 数据元素之间存在着一个对多个的关系数据元素之间存在着一个对多个的关系树树树树 二叉树二叉树二叉树二叉树 二叉搜索树二叉搜索树二叉搜索树二叉搜索树14131211234567891031587101199874566231311图形（网状）结构图形（网状）结构图形（网状）结构图形（网状）结构 数据元素之间存数据元素之间存数据元素之间存数据元素之间存在着多对多的关系。在着多对多的关系。在着多对多的关系。在着多对多的关系。152436第16页/共51页数据结构的形式

9、定义用一个二元组表示，记为：Data_Structure=（D,S）其中，D 是数据元素的有限集（即一个数据 对象），S 是该对象中所有数据成员之间的关系的有限集合。在计算机科学中，对复数的定义：复数是一种数据结构Complex=(C,R)其中：C是包含两个实数的集合 C1,C2,R=P,P是定义在C上的一种关系 。第17页/共51页例、用数据结构如何描述2行3列矩阵：它是一个含6个数据元素a1,a2,a3,a4,a5,a6 的集合，且集合上存在“行关系”和“列关系”两个次序关系，其中 行关系为 ，列关系为 ，。意为 x 和 y 之间存在 x领先于y 的次序关系。思考：如何描述一个一行六列的矩

10、阵？第18页/共51页例1-5 假设我们需要编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，则首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由一位教师、一至三名研究生及一至六名本科生组成，小组成员之间的关系是：教师指导研究生，而由每位研究生指导一至两名本科生。则可以如下定义数据结构：Group=(P，R)其中:P=T，G1，Gn，S11Snm 1=n=3，1=m=2，R=R1,R2 R1=|1=i=n,1=n=3 R2=|1=i=n,1=j=m,1=n=3,1=m=2 第19页/共51页5、数据的逻辑结构数据的逻辑结构从逻辑关系上描述数据，可以看作是从具体问题抽象出来

11、的数据模型，与数据的存储无关，也与数据元素本身的形式、内容、相对位置无关；数据的逻辑结构分类：线性结构 线性表、栈、队列、串非线性结构 树、图（或网络）第20页/共51页6、数据的存储结构数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。它包括数据元素的表示和关系的表示。（1）数据元素的表示：位、字长、元素、结点、数据域（2）关系的表示两种基本的存储方法：顺序映像（顺序存储结构）非顺序映像（链式存储结构）第21页/共51页u顺序存储结构:借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内仍然相邻

12、。u链式存储结构：在每一个数据元素中增加一个存放地址的指针，借助该指针来表示数据元素之间的逻辑关系。所有元素存放在可以不连续的存贮单元中，但元素之间的关系可以通过地址（指针）确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。第22页/共51页存储结构的描述存储结构的描述方法随编程环境的不同而不同，通常可用高级编程语言中提供的数据类型描述之。例如，用一维数组类型描述顺序存储结构，用指针描述链式存储结构。例如，定义日期为：typedef struct int y;/年号 Yearint m;/月号 Monthint d;/日号 Day DateType;/日期类型同样，此时对数据元素也要借用

13、高级编程语言中的数据类型描述之。第23页/共51页7、数据类型（data type）数据类型是一个值的集合和定义在这个值集上的一组操作的总称。数据类型可分两类：原子类型和结构类型。例如：在C语言中 原子类型：整型、实型、字符型等 结构类型：数组、结构体、联合等第24页/共51页9、抽象抽象数据类型(Abstract Data Type简称ADT)l由用户定义，用以表示应用问题的数据模型l指一个数学模型以及定义在此数学模型上的一组操作。l例如：计算机拥有的整数类型。l它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。第25页/共51页抽象数据类型的描述方

14、法抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名数据对象和数据关系的定义用伪码（不真正执行的符号）描述。基本操作的定义格式为：基本操作名（参数表）初始条件：初始条件描述 操作结果：操作结果描述第26页/共51页基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除了可以提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初

15、始条件为空，则省略之。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。第27页/共51页举例抽象数据类型复数的定义：ADT Complex 数据对象：De1,e2e1,e2RealSet 数据关系：R1变量1变量n;输 出 语 句 printf(格 式 串，表 达 式 1，表 达 式 n);或 cout表达式1表达式n;(9)注释 行注释 /文字序列(10)基本函数有 求最大值 max(表达式l，表达式n)求最小值 min(表达式1，表达式n)求绝对值 abs(表达式)求不足整数值 floor(表达式)向下取整 求进位整数值 ceil(表达式)向上取整 判定文件结束 eo

16、f(文件变量)或eof 判定行结束 eoln(文件变量)或eoln 第35页/共51页抽象数据类型实现示例例如利用C语言实现的“复数”类型如下描述：/存储结构的定义typedef struct float realpart;float imagpart;complex;/基本操作的函数原型说明void Assign(complex&Z,float realval,float imagval);/构造复数 Z，其实部和虚部分别被赋以参数 realval 和 imagval 的值void DestroyComplex(complex&Z)/销毁复数 Zfloat GetReal(cpmplex Z

17、);/返回复数 Z 的实部值float Getimag(cpmplex Z);/返回复数 Z 的虚部值void add(complex z1,complex z2,complex&sum);/以 sum 返回两个复数 z1，z2 的和基本操作的实现void add(complex z1,complex z2,complex&sum)/以 sum 返回两个复数 z1，z2 的和sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;第36页/共51页1.4算法和算法分析算法的定义：是对特定问题求解步骤的一

18、种描述,是一个有穷的指令集，这些指令表示一个或多个操作。算法的特性(要素)：有穷性 算法应在执行有穷步后结束,且每一步都在有穷时间内完成确定性 每步定义都是确切、无歧义的可行性 算法中描述的操作应能通过执行有限次已经实现的基本运算而实现输入 有0个或多个输入输出 有一个或多个输出(处理结果)。第37页/共51页算法设计的要求正确性：不含有语法错误；对于各种合法的输入数据能够得到满足规格说明要求的结果。可读性：要求程序有较好的人机交互性,有助于人们对算法的理解。健壮性：对输入的非法数据能作出适当的响应或处理。效率与低存储需求：主要指算法的执行时间和所需的最大存储空间，这两方面主要和问题的规模有关

19、。第38页/共51页算法效率的度量 算法的后期测试在算法中的某些部位插装时间函数 time()测定算法完成 某一功能所花费时间。算法的事前估计：空间复杂度时间复杂度第39页/共51页程序运行所需要的时间取决于下列因素：依据的算法选用何种策略。问题的规模。书写程序的语言。编译程序所生成目标代码的质量。硬件的速度。可以认为一个特定算法“运行工作量”大小，只依赖于问题的规模（通常用整数n表示），或者说，它是问题规模的函数。第40页/共51页一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。语句的频度指的是该语句

20、重复执行的次数。我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。时间复杂度是问题规模的函数T(n)。第41页/共51页语句频度举例（a）+x;s=0；+x 的频度为1 （b）for(i=1;i=n;+i)+x;s+=x;+x的频度为n（c）for(j=1;j=n;+j)for(k=1;k=n;+k)+x;s+=x;+x的频度为n2第42页/共51页时间复杂度设解决一个问题的规模为n，基本操作被重复执行的次数是n的一个函数 f（n），假如，随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，则可记作：T(n)=O(f(n)其中T（

21、n）叫算法的渐进时间复杂度，简称时间复杂度，O是Order（数量级）的首字母，意思是T（n）与f（n）只差一个常数倍。比较同一问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。基本操作的原操作,数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的频度相同。第43页/共51页渐进时间复杂度的计算加法规则 针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)乘法规则针对嵌套程序段 T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)注：c log2n n nlog

22、2n n2 n3 2n 3n n!第44页/共51页变量计数变量计数x=0;y=0;for(int k=0;k n;k+)x+;for(int i=0;i n;i+)for(int j=0;j n;j+)y+;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2)=O(n2)第45页/共51页例对 n 个整数的序列进行选择排序。其中序列的“长度”n 为问题的规模。void selectSort(int a,int n)/对n个整数a0,a1,an-1按递增顺序排序 for(int i=0;i n-1;i+)int

23、k=i;/从ai查到an-1,找最小整数,在ak for(int j=i+1;j n;j+)if(aj=0&Ai!=k)i-;return i;算法的语句 i-的频度不仅与 n 有关，还与 A i 中各元素的取值，以及 k 的取值有关。第47页/共51页算法的空间复杂度空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，记作：S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。算法的存储量包括：输入数据所占空间;程序本身所占空间；辅助变量所占空间。第48页/共51页说明算法的所有性能之间都存在着或多或少的相互影响，因此，当设计一个算法，特别是大型算法时，要综合考虑算法的各项性能、算法的使用频率、算法处理的数据量的大小、算法描述语言的特性及算法运行的机器系统环境等各方面因素，才能设计出比较好的算法。第49页/共51页本章小结与数据结构相关的几个名词概念数据结构研究的内容：数据的逻辑结构 数据的物理结构（存储结构）在数据结构上的操作抽象数据类型算法分析：时间复杂度、空间复杂度第50页/共51页感谢您的观看。第51页/共51页