数据结构zmz_1绪论.ppt

1、数据结构,主讲：郑梦泽,信息工程学院,大家好,E-Mail: Phone: 88052705 (O) Office: 14 - 2315 短号：674758,数据结构：考试课、 64学时 授课; 48学时 上机训练：16学时 先修课程：离散数学、C语言(或其他语言) 后续课程：面向对象程序设计、操作系统、 数据库系统、人工智能等,是计算机类专业和信息类专业 非常重要的基础课程和核心课程,课程设置与重要性,课程安排 授课：Week 318 星期一（1、2节） 星期四（单周，1、2节） 单元训练上机: 8次 星期四（双周，1，2节）,课程考核 数据结构 课程结束期末考试(闭卷笔试）：60 作业+上

2、机+考勤+课堂：40,上机作业提交： 10.0.0.14 / 10.0.0.15,保持课堂安静，头脑清醒，思维活跃 认真、独立、按时完成并提交作业 重视上机实践,课程要求,课程做什么？,思考 统计总分,表1是5次C语言课程的测验成绩，设计一个小程序计算这5次测验的总分,书目文件,例 书目自动检索系统,电话号码查询系统 学生成绩管理系统 职工信息系统 等文档管理的数学模型,是一门研究程序设计问题中计算机的操作对象之间的关系和操作等等的学科 Pascal之父：尼古拉斯沃斯Niklaus Wirth “算法+数据结构=程序”,一、数据结构研究什么,二、几个重要概念,数据的操作：查询、插入、修改、删除

3、等,数据（data)所有能输入到计算机中去的符号（早期：数值，现在：字符、声音、图像）,数据元素（data element）数据的基本单位，也称结点（node）或记录（record） 数据项（data item）有独立含义的数据最小单位，也称域(field),数据对象（data object)性质相同数据元素的集合,二、几个重要概念,数据结构（data structure)数据元素和数据元素关系的集合 Data_Structure = D, S,数据的逻辑结构只抽象反映数据元素的逻辑关系,从逻辑关系上描述数据 与数据元素的存储位置无关,数据逻辑结构分为： 集合 线性结构 树形结构 图状结构,二

4、、几个重要概念,1、集合 数据元素间除“同属于一个集合”外，无其它关系,三、数据的逻辑结构,2、线性结构 一个对一个，如线性表、栈、队列,三、数据的逻辑结构,2、线性结构 关于栈的故事,三、数据的逻辑结构,2、线性结构 汉诺塔,三、数据的逻辑结构,案例 人机对奕问题,案例 人机对奕问题,案例 人机对奕问题,3、树形结构 一个对多个,三、数据的逻辑结构,计算机某磁盘目录结构示意图,4、图形结构、网状结构 多个对多个,三、数据的逻辑结构,学校校园网交换机之间位置和距离示意图,4、图形结构、网状结构,三、数据的逻辑结构,哥尼斯堡七桥问题 在18世纪的东普鲁士的哥尼斯堡城市，有条横贯全城的普雷格尔河和

5、两个岛屿，在河的两岸与岛屿之间架设了7座桥，把它们连接起来。,数据的存储结构数据的逻辑结构在计算机存储器中的实现,索引存储结构 散列存储结构,四、数据的存储结构,元素n,.,元素i,.,元素2,元素1,Lo,Lo+m,Lo+(i-1)*m,Lo+（n-1)*m,存储地址,存储内容,Loc(元素i)=Lo+（i-1)*m,顺序存储结构,四、数据的存储结构,1536,元素2,1400,元素1,1346,元素3,元素4,1345,链式存储结构,h,四、数据的存储结构,小结,数据类型值的集合+一组操作,例 C语言中，提供int, char, float, double等基本数据类型， 数组、结构体、共

6、用体等构造数据类型， 还有指针、空(void)类型等。 用户也可用typedef 自己定义数据类型,typedef struct long num; char name30; char author20; char publisher30; float price; BOOKCARD; BOOKCARD book1,book2,*p;,五、数据类型,数据结构和数据类型的关系 “数据类型”是数据结构在计算机内部的具体表现 ； “数据结构”是数据类型的抽象,一些常用的数据结构，需要将元素、它们的关系和操作用自定义类型的方法进行描述,抽象数据类型Abstract Data Type,ADT,五、数据

7、类型,定义：ADT是指一个数学模型和定义在该模型上的一组操作的总称 不考虑其在计算机内具体存储结构与运算的具体实现算法,ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,ADT Circle 数据对象：D=r,x,y| r,x,y 均为实数 数据关系：R=| r是半径,是圆心坐标 基本操作： CreateCircle( float image; Complex;,/基本操作的函数原型说明 void CreateComplex(Complex ,/基本操作的实现 void CreateComplex(Complex ,ADT实现举例,算法（Algorithm）解

8、决某一特定问题的具体步骤的描述，是指令的有限序列,六、算法和算法分析,有穷性(Finiteness)算法必须在执行有限步骤后结束 确定性(Definiteness)算法每一步骤必须是确切定义的，不能产生二义性 可行性(Effectiveness)算法是能行的 输入(Input) 算法有零个或多个输入 输出 (Output) 算法有一个或多个输出,六、算法和算法分析,void exam1() int n=2; while(n%2=0) n=n+2; printf(“%dn”,n); ,void exam2() int y=0; int x=3/y; printf(“%d,%dn”,x,y); ,

9、违反了有穷性,违反了可行性,这两段描述均不能满足算法的特征,试问它们违反了哪些特征？,六、算法和算法分析,衡量算法优劣的标准 正确性(Correctness) 可读性(Readability) 健壮性(Robustness) 效率(Efficiency),健壮性: 1、指当输入数据 非法时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。 2、处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理,可读性： 1、算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解； 2、另一方面，晦涩难读的算法易于隐藏

10、较多错误而难以调试。,正确性： 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果,六、算法和算法分析,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,方法1用三重循环： for(i=0; i=100; i+) for(j=0; j=100; j+) for(k=0; k=100;k+) if(k%3 = = 0 ,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案。,循环次数=1

11、01*101*101 即约一百万次,方法2用二重循环：k=100-i-j for(i=0; i=100; i+) for(j=0; j=100; j+) k=100 i j ; if(k%3 = = 0 ,循环次数=101*101 即约一万次,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案。,方法3用二重循环：钱100元，母鸡5元1只，所以i=20， 同样，

12、j=33 for(i=0; i=20; i+) for(j=0; j=33; j+) k=100 i j ; if(k%3 = = 0 ,循环次数=21*34=714,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案。,方法4用一重循环：合并方程得到:14*i+8*j = 200 简化为: 7*i+4*j=100 所以有：i=14 又： j=25-7*i/4

13、，故i必为4的倍数 for(i=0; i=14; i+4) j = (100 7*i)/4; k=100 i j ; if(k%3 = = 0 ,循环次数=4,百钱买百鸡问题,100元钱买100只鸡，母鸡每只5元，公鸡每只3元，小鸡3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？,求解：设母鸡、公鸡、小鸡各为i, j, k只。则有： i + j + k = 100 5i + 3j + k/3 = 100 只需要解出本方程就可以得到答案。,（渐近）时间复杂度：算法耗用时间相对问题规模的增长率 用T(n)表示 空间复杂度：算法占用存储空间的量度 用S(n)表示,七、算法时间效率度量方法,时

14、间复杂度T(n)定义：设n是问题规模, f(n)是程序执行的次数，大O表示法：T(n)=O(f(n) T(n)只取f(n)的最高阶 顺序结构： T(n)=O(n0)=O(1) 单循环结构： T(n)=O(n) 双循环结构： T(n)=O(n2),七、算法时间效率度量方法,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),频度最大语句重复执行次数的阶数,七、算法时间效率度量方法,例：阅读程序，（1）求执行“下划线”语句的次数f(n),（2）T(n)=? for(i=1;i=n;i+) for(j=1;j=2*n;j+) cij=0; for(k=1;k=n+1;k+) cij=cij+aik*bkj; ,七、算法时间效率度量方法,时间复杂度：看重复执行的次数的阶数,常用时间复杂度： O(