数据结构-为什么学习数据结构资料

1、前 言为什么学习数据结构课程内容学习目的(md)与考核形式参考文献共五十六页为什么学习(xux)数据结构计算机解决具体问题的步骤：从具体问题中抽象出数学模型数据表示（数据是计算机化的信息，是计算机的处理对象）设计或选择一个解此数学模型的算法数据处理编程、运行计算机问题分为两类：数值计算： （计算量大、数据量少）数学(shxu)模型可以用数学(shxu)方程式描述，主要进行算法设计的研究；非数值计算： （数据量大、处理简单）数学模型无法用数学方程式描述，需研究数据结构。共五十六页为什么学习(xux)数据结构数据结构是数据间的相互关系；数据结构是计算机科学中的一门综合性的专业基础课程，也是计算机系

2、统程序设计的基础；计算机科学研究的基本课题：数据结构、算法二者的关系：密不可分，Wirth提出：算法数据结构程序 算法与数据结构选择的重要性计算机内存的增大与速度(sd)的提高并不能降低选择合适算法与数据结构的重要性。共五十六页为什么学习(xux)数据结构例：问题提出：百元钱买百支笔问题(钢笔3元一支，圆珠笔2元一支，铅笔0.5元一支)。问：有哪些购买方案？解法(ji f)1：用三层循环，内循环100万余次101*101*101=1030301）for (x=0；x=100；x+) for (y=0；y=100；y+) for (z=0；z=100；z+) if (x+y+z=100) & (

3、3*x+2*y+0.5*z=100) printf(“%d,%d,%d”,x,y,z)；结果：在某机器上运行用了50分钟。共五十六页为什么学习(xux)数据结构解法2：而经过(jnggu)分析，钢笔最多买20支，圆珠笔最多买34支.for (x=0 ;x=20;x+) for (y=0;y=34-x;y+) if (3*x+2*y+0.5*(100-x-y)=100) printf(“%d,%d,%d”,i,j,k);结果：优化后内循环了525次，只运行了2秒，相差1500倍。思考：是否可以再进行优化？共五十六页为什么学习(xux)数据结构解法3：设钢笔买了x只；圆珠笔买了y只；铅笔(qinb

4、)买了z只；(0 x20)，满足方程组：共五十六页课程内容课程内容：讲课:系统地介绍软件设计中常用的几种数据结构(sh j ji u)和相应的存储结构和算法，以及常用的几种查找和排序算法。该课程为后续课程的学习以及软件设计水平的提高打下良好基础。上机实践共五十六页学习(xux)目的与考核形式课程学习目的掌握各种主要数据结构的特点、机内表示、处理数据的算法设计，以及算法分析； 组织、处理数据的理论和方法，建立良好的编程风格(fngg)；培养数据的抽象能力。课程考核形式平时成绩 20%30%期末成绩70%80%共五十六页参考文献参考文献数据结构与算法设计,王晓东,电子工业出版社,2002.3数据结

5、构（C语言(yyn)篇）习题与解析,李春葆, 清华大学出版社数据结构题集（C语言版）, 严蔚敏 吴伟民, 清华大学出版社 数据结构 殷人昆 编著, 清华大学出版社 数据结构 张选平 雷永梅, 机械工业出版社，2002.1共五十六页第1章 绪论(xln)1.1 什么是数据结构1.2 抽象数据类型1.3 抽象数据类型的表示和实现(shxin)1.4 算法和算法分析共五十六页1.1 什么(shn me)是数据结构登录号书名作者分类号001高等数学樊应川S01002理论力学罗远祥L01003高等数学华罗庚S01004线性代数栾汝书S02a1a2a3aiai+1ana1a2aiai+1an存储(cn c

6、h)方法线性结构数据的操作：建立、插入、删除、查找等应用实例1：书目检索自动化问题共五十六页1.1 什么(shn me)是数据结构.树型结构应用实例(shl)2： 人机对弈问题共五十六页CEDABABACADBABCBDDADBDCEAEBECED图结构1.1 什么(shn me)是数据结构应用实例(shl)3：多叉路口交通灯管理问题共五十六页1.1 什么(shn me)是数据结构小小的总结以上例子的解决，都不是数值计算问题。描述这类非数值问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此简单说来，数据结构是一门研究非数值计算的程序设计中计算机的操作(cozu)对象以及它们之

7、间的关系和操作等的学科。数据结构课程的地位（P3P4） 共五十六页1.2 基本概念与术语(shy)1.2.1 数据(shj)、数据(shj)元素、数据(shj)项、数据(shj)对象1.2.2 数据结构1.2.3 抽象数据类型共五十六页1. 2.1数据、数据元素(yun s)、数据项、数据对象数据（data)：所有能输入到计算机中进行加工处理的对象；数据元素（data element）：数据的基本(jbn)单位，也称结点（node）或记录（record）；数据项（data item）：有独立含义的数据最小单位，也称项或字段(field)；数据对象(data object)：性质相同的数据元素的

8、集合，是数据的一个子集。共五十六页1.2.2 数据结构(sh j ji u)数据结构（Data Structure）是相互之间存在一种或多种特定(tdng)关系的数据元素的集合。例如：数据结构包含如下三个方面的内容：1：数据的逻辑结构 （logic structure）独立于计算机，是数据本身所固有的。2：数据的存储物理结构（storagephysical structure)是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。3：数据的操作运算（operation） 指所施加的一组操作总称。操作的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。共五十六页1.2.2 数据结构(sh j

9、ji u)例1：设有一个(y )表(a1,a2,a3,a4,a5)，它的抽象描述可表示为：Line（D，S） 其中：Da1,a2,a3,a4,a5，S,，则：它的逻辑关系图示如下：a1a2a3a4a5共五十六页例2 设一个数据结构的抽象描述(mio sh)为:Tree（D，S）其中：D r,a,b,c,d,e,f,g,h, S , ,则：它的逻辑关系图示如下：rabcdefgh共五十六页一般来说，根据数据元素之间的关系的不同特性(txng)，通常有如下4类基本结构：共五十六页数据结构可用二元组Data Structure（D，S）的形式(xngsh)来描述。其中：D a1,a2,an为元素集合

10、；S r1,r2,rm为关系的集合。共五十六页1.2.2 数据结构(sh j ji u)数据的逻辑(lu j)结构集 合线性结构数据的逻辑结构非线性结构一般线性表线性表推广特殊线性表树型结构网状结构线性表栈和队列串数组广义表树二叉树有向图无向图共五十六页1.2.2 数据结构(sh j ji u)数据的存储结构顺序存贮(cn zh)结构链式存贮结构索引存贮结构散列存贮结构共五十六页1.2.3 抽象数据类型数据类型（Data Type）一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。例如，在C语言中提供的数据类型： int, char, float, double等原子类型以int为

11、例：32768到32767中的整数(zhngsh)值构成的集合一组操作（加、减、乘、除、乘方等）共五十六页1.2.3 抽象数据类型数组、结构体、共用体、枚举等结构类型，还有指针(zhzhn)、空(void)类型等，用户也可用typedef 自己定义数据类型。typedef int integer; typedef struct int num; char name20; float score; STUDENT;STUDENT stu1,stu2, *p;共五十六页1.2.3 抽象数据类型抽象数据类型 （Abstract Data Type） 指一个数学模型(mxng)以及定义在该模型(mxn

12、g)上的一组操作表示方法格式1：三元组的形式（D，S，P）格式2： ADT 抽象数据类型名数据对象：数据关系：基本操作： ADT 抽象数据类型名共五十六页1.3 应用(yngyng)举例-ADT Triplet（P9）ADT Triplet 数据对象(duxing)：De1,e2,e3| e1,e2,e3ElemSet 数据关系：R, 基本操作： InitTriplet(&T,v1,v2,v3) DestroyTriplet(&T) Put(&T, i ,e) Get(T, i ,&e) IsAscending(T) IsDescending(T) Max(T,&e) Min(T,&e) AD

13、T Triplet共五十六页1.4 算法(sun f)与算法(sun f)分析1.4.1 算法(sun f)的基本概念1.4.2 算法描述1.4.3 算法分析共五十六页1.4.1 算法(sun f)的基本概念算法（algorithm）解决某一特定问题的具体步骤的描述，是指令的有穷序列(xli)。算法特性有穷性确定性可行性输入输出共五十六页1.4.1 算法(sun f)的基本概念例：判断下述描述是否是一个(y )算法？ void main( ) int i=2,y=0,x; while !(i%2) i+=2; x=2/y; 共五十六页1.4.1 算法(sun f)的基本概念算法和程序的关系算法

14、的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环）；程序中的指令必须是机器可执行的，而算法中的指令则无此限制(xinzh)。一个算法若用计算机语言来书写，则它就可以是一个程序。共五十六页1.4.2 算法(sun f)描述1.用流程图描述算法一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。2.用自然语言描述算法用我们日常生活中的自然语言（可以是中文形式，也可以是英形式）也可以描述算法。 3.用其它(qt)方式描述算法我们还可以用数学语言或约定的符号语言来描述

15、算法。共五十六页1.4.2 算法(sun f)描述4.用C描述算法（1）所有算法的描述都用C中的函数形式 函数类型 函数名（形参及类型说明） 函数语句部分 return(表达式值)； （2）函数中的形式参数有两种传值方式若为一般(ybn)变量名，则为单向传值；若在变量前面增加“&“符号，则为双向传地址（借用C+的引用参数）。共五十六页例2 void swap(int *p1,int *p2) int temp; temp=*p1;*p1=*p2;*p2=temp; main ()int i=3， j=5;swap(&i,&j); printf(“%d %d”,i,j); 赋值参数特点(tdin

16、)：传值方式例1 void swap(int a, int b) int temp; temp=a;a=b;b=temp; main () int i=3，j=5; swap(i,j); printf(“%d %d”,i,j); 共五十六页引用(ynyng)参数1. 形式： x& ,表示“x类型的引用” int i=5; int &j=i; j=10; printf(“%d,%d”,i,j)共五十六页2. 作为函数参数（传送变量的地址(dzh)/别名） void swap( int &a,int &b) int temp; temp=a;a=b;b=temp; main() int i=3,j

17、=5; swap(i,j); printf(“%d %d”,i,j); 共五十六页类C语言描述(mio sh)算法的符号约定（1）预定义的常量和类型/函数结果状态码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE 1#define OVERFLOW 2/Status 函数的类型typedef int Status;共五十六页（2）存储结构(jigu)的表示 用类型定义typedef描述；（3）数据元素类型为ElemType（4）赋值语句（5）选择语句（6）循环语句（7）结束语句（8）基本函数 m

18、ax( ) min( ) abs( ) floor( ) ceil( ) eof( ) eoln( )（9）逻辑运算 & |共五十六页例如(lr)：抽象数据类型Triplet的表示和实现（P12P13）。共五十六页1.4.3 算法(sun f)的评价本课程的目的就是要对特定的问题，按照具体要求，设计出较好的算法。算法的评价衡量(hng ling)算法优劣的标准正确性(correctness)可读性(readability)健壮性(robustness)高效率与低存储量时间复杂度（计算复杂度）算法运行时间的相对量度。空间复杂度算法运行中临时占用空间大小的量度。共五十六页1.4.3 算法(sun

19、f)的评价一、时间复杂度1 语句频度(pn d)一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。算法运行时间大致等于计算机执行一个简单操作的时间与算法所包含简单操作次数之积。即：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的基本语句的执行次数称为语句频度或时间频度。共五十六页例1：计算如下(rxi)程序段中+x；的语句频度。程序+x；for(i=0;i=n;i+) +x；for(i=2;i=n;i+) for(j=1;j=n;j+) +x；for(i=2;i=n;i+) for(j=2;j=i-1;j+) +

20、x；语句频度1n1n(n1)共五十六页1.4.3 算法(sun f)的评价渐近时间复杂度实际上算法的时间复杂度只需大致算出相应数量级（Order）就可以(ky),称为渐近时间复杂度，一般地我们简称为时间复杂度。 记作： T(n)O(f (n) )算法时间复杂度的评价情况1： （P15）共五十六页1.4.3 算法(sun f)的评价例：设n为正整数，利用大“O”记号(j ho)，根据基本操作的语句频度计算下列程序段的时间复杂度。(1) i=1; k=0 while(in) k=k+10*i; i+; (2) i=1; k=0;do k=k+10*i; i*=2; while(in); 共五十六页

21、1.4.3 算法(sun f)的评价(3) （P15）for (i=1;i=n ;i+) for (j=1;j=n;j+)cij=0;for (k=1;k=1 & change;-i) change=FALSE; for(j=1;jaj+1) aj aj+1; change=TRUE; / bubble_sort 共五十六页1.4.3 算法(sun f)的评价语句频度最好情况0最坏情况平均情况时间复杂度O(1)O(n2)O(n2)共五十六页1.4.3 算法(sun f)的评价按数量级递增(dzng)排列依次为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3) O(nk)

22、O(2n)nn2n32n2124844281664161024101024022023021024常见的时间复杂度共五十六页共五十六页共五十六页1.4.3 算法(sun f)的评价二、空间复杂度1 空间频度一个算法在执行时所占有的内存开销，称为空间频度，但我们一般是讨论算法占用的辅助(fzh)存储空间。讨论方法与时间频度类似，不再赘述。 空间复杂度S(n)O(f(n)与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。共五十六页课后复习题1. 填空题数据的逻辑结构可形式地用一个二元组B(D，S)来表示，其中D是_，S是_。存储结构可根据数据元素在机