安徽农业大学计算机科学与技术 2

1、数据结构,范国华,教材： 数据结构（C语言版） 严蔚敏（清华大学出版社） 辅导材料： 数据结构习题与解析（C语言版） 李春葆（清华大学出版社） 数据结构算法设计指导（Pascal版） 胡学刚 （清华大学出版社）,1.1 数据结构讨论的范畴 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法及其量度,第一章 绪言,1.1 数据结构讨论的范畴 Niklaus wirth 程序设计： 为计算机处理问题编制的一组指令集。 算法： 处理问题的策略。 数据结构： 问题的数学模型。,Algorithm + Data Structures=Programs,数值计算的程序设计问题,梁架结构

2、中应力的分析计算： 线性代数方程组 天气预报： 环流模式方程,非数值计算的程序设计问题： 例1 个人电话簿问题 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。,例2 人机对奕问题,例3 多叉路口交通灯管理问题,数据结构定义: 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等等的学科。,数据结构是一门综合性的专业课程，是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系

3、统、数据库系统及其他系统程序和大型应用程序的基础。,1.2 基本概念和术语 数据（data)是对客观事物的符号表示,在计算机科学中则是指所有能被输入到计算机中，并能被计算机处理的符号的总称； 数据元素（data element）数据中的一个“个体”，数据的基本单位； 数据项（data item）数据结构中讨论的最小单位； 数据对象（data object） 性质相同的数据元素的集合。 数据结构（data structure)带结构的数据元素的集合；,例如：,一个含12位数的十进制数可以用3个4位的十进制数来表示。 4217，3558，6119a1(4217),a2(3558),a3(6119)

4、 在a1、a2、a3存在“次序”关系 4217，3558，6119 = 3558，6119，4217 a1 a2 a3 a2 a3 a1,数据元素之间的关系可以分为以下四类： 线性结构 一个对一个，如线性表、栈、队列 树形结构 一个对多个，如树 图状结构 多个对多个，如图 集合 数据元素间除“同属于一个集合”外，无其它关系,线性结构,树形结构,树 二叉树 二叉搜索树,14,13,12,11,2,3,4,5,6,7,8,9,10,3,1,5,8,7,10,11,9,9,8,7,4,5,6,6,2,3,13,1,bin,dev,etc,lib,user,1,1,2,5,6,4,3,1,2,5,4,

5、3,6,11,33,18,14,6,6,5,16,19,21,图结构,网络结构,数据结构的形式定义为：数据结构是一个二元组： Data-Structure = ( D，S ) 其中：D是数据元素的有限集，S是D上关系的有限集,数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储（物理）结构数据的逻辑结构在计算机存储器中的映象（表示）,数据元素的映象方法,计算机中的数据元素是用二进制位（bit）的位串来表示的。 (321)10 = (501)8 = (101000001)2 A = (101)8 = (001000001)2,关系的映象方法,所有的关系都可以用有序对的形式来表示 即 顺序映象：

6、借助数据元素在存储器中的相对位置来表示数据元素间的逻辑关系。 y的存储位置和x的存储位置之间差一个常量C 整个存储结构中只包含数据元素本身的信息 链式映象：借助指示元素存储地址的指针表示数据元素间的逻辑关系。 y的存储位置和x的存储位置之间没有固定的关系 存储结构中不光包含数据元素本身的信息还包含指向后继元素的指针。,1536,y,1400,x,1346,元素3,元素4,1345,h,链式存储,h,数据类型高级语言中指数据的取值范围及其上可进行的操作的总称。,数据类型可分为2种： 简单型和结构型 例如C语言中的： 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义

7、,抽象数据类型(ADT)：一个数学模型以及定义在该模型上的一组操作。 抽象数据类型实际上就是对该数据结构的定义。因为它定 义了一个数据的逻辑结构以及在此结构上的一组算法。,1.3 抽象数据类型的表示与实现,ADT的两个重要特征,数据抽象： 用ADT描述程序处理的实体时，强调的是其本质特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装： 将实体的外部特性和其内部的实现细节分离，并且对外部用户隐藏其内部实现细节。,例：复数的抽象数据类型,ADT Complex 数据对象： =e1,e2 | e1,e2 属于 RealSet 数据关系： R1= |e1是复数的实数部分，

8、|e2是复数的虚数部分 ,基本操作：,InitComplex( i=n; i+ ) for( j=1; j=n; j+ ) cij = 0; for( k=1; k=n; k+ ) cij = cij + aik * bkj; ,基本操作：乘法操作 由于是一个三重循环，每个循环从1到n，则总次数为: nnn,Void bubble-sort(int a，int n) for ( i = n-1, change = TURE; i1 change = TURE ,例2.将a中整数序列重新排成自小到大的有序整数序列,最好情况：0 次 最坏情况：1+2+3+n-1 = n(n-1)/2 平均时间复杂

9、度为: O(n2) 最坏时间复杂度为: O(n2),基本操作：交换序列中相邻的两个整数,以下六种计算算法时间的多项式是最常用的。其关系为： O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) 指数时间的关系为： O(2n) O(n!) O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。,算法的存储空间需求 空间复杂度:算法所需存储空间的度量，记作: S ( n ) = O ( f ( n ) ) 其中n为问题的规模（或大小） 它表示随问题规模n的增大，算法运行所需存储量的增长