第1章 数据结构介绍.ppt

1、1,数 据 结 构(Data Structure),任课教师： 赵少卡 E-MAIL: ,数计系2012级计算机科学与技术、网络工程专业,2,课程性质：专业核心基础课 教材: 严蔚敏、吴伟民. 数据结构 (C语言版).北京:清华大学出版社,2011. 1981年初稿，使用面最广 周学时：4（理论授课）+ 2（上机实践） 考核：平时成绩（作业、考勤）20% +期中成绩20% +期末成绩60%,3,保持课堂安静，头脑清醒，思维活跃 课后及时复习巩固 认真、独立、按时完成并提交作业 多思考多动手，重视上机实践,课程要求,4,数据结构,基础数据结构,应用数据结构,非线性结构,线性结构,线 性 表,栈,

2、队 列,串,数 组,广 义 表,树,二 叉 树,图,查 找,内 部 排 序,外 部 排 序,文 件,动 态 存 储 管 理,本课程的内容框架,5,讲授篇章,第1章 绪论,第7章 图,第2章 线性表,第9章 查找,第3章 栈和队列,第6章 树和二叉树,第10章 内部排序,6,第 1 章 绪 论,问题求解(Problem Solving)：,7,计算机求解问题的分类,数值计算(科学运算):解方程(组)、 函数求值、 概率统计等。 应用：天气预报(环流模式方程)、结构静力分析（线性代数方程组）、水库大坝的应力计算、预报人口增长等。 非数值计算：字符、表格、图像、声音等。,8,基本概念和术语,数据：计

3、算机程序处理的符号的总称，包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。 数据元素：数据的基本单位（数据中的一个“个体”），通常作为一个整体进行处理。 数据项：数据的具有意义的不可分割的最小单位。一个数据元素可以由若干个数据项构成。,9,数据对象：性质相同的数据元素的集合。 如：整数数据对象 N = 0, 1, 2, （无限集） 字母字符数据对象C= A, B, C, Z （有限集） 因此： 数据元素是数据的一个个体； 数据对象是数据的一个子集。,10,例：a1,a2,a3,a4,a5,a6存在次序为： （1）| i=1，2，3，4，5 （2）Row=, , Co

4、l =, , 所谓结构就是数据元素之间的关系，即描述数据元素之间的运算与运算规则。 数据结构：相互间存在一种或多种特定关系的数据元素的集合。,11,数据的逻辑结构,数据的存储结构 （物理结构、映像）,数据的运算：查找、排序、插入、删除、修改等,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,集合结构,串,索引存储,散列存储,12,主要逻辑结构举例 集合：其中的数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。 线性结构：其中的数据元素之间存在一对一的关系。 树型结构：其中的数据元素之间存在一对多的关系。 图状结构（网状结构）：其中

5、的数据元素之间存在多对多的关系。,13,例1 书目自动检索系统,书目文件,14,例2 人机对弈问题,15,例3 多叉路口交通灯管理问题,有连线的节点用不同的颜色标记, 表示不能同时通行。 要求使用的颜色数尽可能少, 以使减少等待时间。,16,逻辑结构与存储结构,逻辑结构: 数据元素间的逻辑关系，与数据元素的相对位置无关。 存储结构: 逻辑结构在计算机存储器中的表示，如：,顺序存储结构借助元素在存储器中的相对位置来表示 数据元素间的逻辑关系 链式存储结构借助指示元素存储地址的指针表示数据 元素间的逻辑关系,17,18,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链

6、式存储结构,h,19,数据类型与抽象数据类型,数据类型（Data Type）：值的集合以及定义在这个集合上的一组操作。 数据类型分类： （1）原子类型：每个数据都无法再分割。（整型、实型、字符型等） （2）结构类型：结构类型中的数据可以分解为若干原子类型或结构类型数据。（数组、记录、结构体、联合体、串、文件等）,20,抽象数据类型(Abstract Data Type ，ADT):数学模型以及定义在该模型上的一组操作，与其在计算机中的表示和实现无关。 例如：矩阵 + 求转置、加、乘、求逆、求特征值等操作构成一个矩阵的抽象数据类型。 ADT 可用三元组表示：（D,R,P） D 数据对象 R D上

7、的关系的有限集 P 对D的基本操作集,21,抽象数据类型的定义,ADT抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作： 基本操作名（参数表） 初始条件：初始条件描述 操作结果：操作结果描述ADT抽象数据类型名 在定义抽象数据类型中的数据部分和操作部分时，要求只定义数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现。,22,基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以 printf(在函数fa中：a=%dn,a); void fb(int *a) /* a为指针类型，在函数中改变*a，改变后的值将带回主调函数 */ (*a)+; print

8、f(在函数fb中：*a=%dn,*a); void main( ) int n=1; printf(调用函数fa之前：n=%dn,n); fa(n); printf(调用函数fa之后,调用函数fb之前：n=%dn,n); fb( ,30,抽象数据类型（ADT）明确地把数据模型与该模型上的运算紧密地联系起来。 从使用的角度看，ADT隐藏了所有使用者不关心的实现细节，对用户透明（提供接口），使程序模块的实现与使用分离，从而能够独立地考虑模块的外部界面、内部算法和数据结构的实现，做到了信息隐蔽与数据封装。,Abstract Data Type (ADT),user1,user2,usern,.,实现

9、1,实现2,实现3,31,算法与程序,算法（Algorithm）是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法的描述工具有： （1） 自然语言 （2） 程序设计语言 （3） 流程图（框图） （4） 伪码语言：是一种包括高级程序设计语言的三种基本结构（顺序、选择、循环）和自然语言成分的“面向读者”的语言。 程序是用某种程序设计语言对算法的具体实现。如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。,32,算法的5个特征,(1)有穷性：在有限步(或有限时间)之后算法终止。 例：void suanfa1( ) int i,s=0； for (i=0

10、；i=0；i+) s+； (2)确定性：无二义性。 例： x=5；y=10； z=x+y； printf(%d,%d,%d ,x,y,z)； x+y 解释为：x + (+y)？还是 (x+)+ y？,33,(3)可行性(正确性)：可以在计算机上实现。 for( i=1,s=0；i1000000000000；+i) s+；？ (4)输入：有0个（算法本身确定了初始条件） 或多个输入量。 (5)输出：至少有一个输出量。,34,算法设计要求如何设计一个“好”的算法,(1)正确性（4个层次） a.无语法错误； b.对n组输入产生正确结果； c.对特殊输入产生正确结果； d.对所有输入产生正确结果。 (

11、2)可读性：“算法主要是为了人的阅读与交流”。 (3)健壮性（鲁棒性） scanf(%d,in;i+) if(ai=key) return i； return -1； 最好情况：O(1) 最坏情况：O(n) 平均时间复杂度为:O(n),46,例 6 ： fact(int n) if(n1）,T(n)=O(1)+T(n-1) =2*O(1)+T(n-2) =(n-1)*O(1)+T(1) =n*O(1) =O(n),T(n)=,利用递归跟踪或递推方程,47,例 7：设存在递归关系: 0 （n=1） T(n-1)+n-1 （n1） 分析其时间复杂度。 T(n)= T(n-1)+(n-1) =T(n

12、-2)+(n-2)+(n-1) =T(n-3)+(n-3)+(n-2) +(n-1) =(T(1)+1)+2+(n-1) =0+1+2+(n-1) = n(n-1)/2 =O(n2),T(n)=,48,例 8： i=1; while(i=n) i*=3; 设while语句执行f(n)次 则3f(n) n，即f(n) log3n 那么利用定义，T(n) Mf(n)Mlog3n=O(logn),49,增长率（阶）（从大到小）,nn n! cn(c1)：2n , 3n nc(c1)：n3, n2 nlog2 n nr(0r1.0) log2 n c,O(1)O(logn)O(n)O(nloglogn)O(nlogn)O(n2)O(n3) O(2n)O(n!)O(nn),50,常用的时间复杂度频率计数,51,算法效率的度量空间复杂度,一般情况下，算法的复