数据结构CHAP1.ppt

1、1、什么是数据结构?,数据:生活当中的各种元素 是从我们需要用计算机解决的问题中提取出来的东西 数据结构:这些元素之间的关系 书中介绍的结构与生活息息相关，并不陌生，（线性、树、图，）难重点在于对这些结构进行的操作，（插入，删除，查询，等，不同的结构有各自的操作）。,2、数据结构的作用,帮助你将生活元素转化为可以被计算机理解、处理的数学模式。 （课本就是介绍这些结构及其在这些结构之上进行的操作） 是问题与编程的中间桥梁,数据结构是一种思想,一种意识。这种思想是在你编程地过程中体现出来的, 表现为具体形式就是你对你在整个程序中用到的所有数据做一个良好的排列方式（结构）, 可以是表、树,等等 也可

2、以是书上没有的,自己也可以定义,比如说:星形,球形.等等. 也就是说,你想要你的数据以一种确定的方式组合起来, 以便在编程过程中正确的方便的调用和处理。,数据结构这门课,并不教给你一种具体的语言,也不会教会你具体语法,(那是教你语言的老师的事情), 具体的体现形式可以是各种语言,C也好,VB也好,JAVA也好,你可以在各种语言的编程中定义数据的组织形式, 主要用到C/C+中的结构体，类，都可以。,书中使用的是类C，易于转化为程序，用类C来描述算法，算法要转化为程序来实现。 如果你编程不太熟,而且学过C的话，你最好多找几本C的书来看.常练习,然后渐渐的在自己的编程中体现出你对数据的组织形式,体现

3、出你的数据结构思想.,现在你觉得数据结构没有什么用处，最大的一个原因就是因为你做应用的话，底层的很多东西人家已经帮你封装了很多基本的概念，给你提供了最大的方便。 例如：你在C里面用strstr来查找字符串时，底层用到了数据结构上面的查找算法，而你作为应用开发者，无须关心。,你不学的话，你也能够做应用。但是，没有数据结构的概念： 1、你看东西就不会透彻； 2、进一步的学习很困难。 学了就是专业人士，不学就是票友,参考资料,C+参考大全，Herbert Schildt著，电子工业出版社 数据结构及应用算法教程，严蔚敏，陈文博著，清华大学出版社 数据结构课程设计，苏仕华等，机械工业出版社,系统实例,

4、排队问题的系统仿真理发馆仿真 队列结构可以模拟现实生活中的很多排队现象，例如车站候车，医院候诊，银行排队等，通过程序仿真可预测客流等多种经营指标，提供有价值的量化指标。 不作要求，体会生活事件与数据结构之间的转化。,假设理发馆内设有N把理发椅，可同时为N位顾客进行理发。对于在营业时间(假设为T小时)内进门的顾客，若有空闲理发椅，则该顾客可立即入座理发；否则需要排队候理。一旦有顾客理完发离去时，排在对头的顾客便开始理发。顾客的到达时间和理发所需时间均可随机生成，并约定，过了营业时间顾客不再进门，但仍需继续为已进入店内的顾客理发，直至最后一名顾客离开为止。 通过算法预测一天内顾客在理发馆内的平均逗

5、留时间，和排队人数的平均值。,需要统计一天内每个顾客自进门到出门在理发馆逗留的时间，和每个需排队等候的顾客进门排队时的队伍长度。 只要在顾客进门和出门这两个时刻进行模拟处理即可,设置两个数据类型： 一是事件表，记录顾客进门或出门的事件，表中每一项包括事件类型（0为进门，1为出门),和事件发生的时刻。 二是队列，记录排队顾客情况。队列中的每个元素包括顾客进门的时刻和理发需要的时间。,顾客进门时刻和理发时间在程序中可由随机数来代替。 假设第一个顾客进门时刻为0，它是事件表的第一项，之后每个顾客进门时产生2个随机数durtime(进门顾客理发所需时间），和intertime（下个顾客将到达的时间间隔

6、）。每产生一个进门事件则插入事件表。,另外，进门时如果有空理发椅，则顾客在durtime之后可离开，则产生一个发生时刻为occurtime+durtime的出门事件插入事件表。 若没有空椅子，则顾客情况插入队尾。 当出门事件发生时，表明有椅子空出，则删去对头元素，即排在对头的顾客开始理发，此时也产生一个出门事件插入事件表。,第一章 绪 论,1.1 数据结构讨论的范畴,1.2 基本概念,1.3 算法和算法的量度,1.1 数据结构讨论的范畴,Niklaus Wirth Algorithm + Data Structures = Programs,程序设计: 算法: 数据结构:,为计算机处理问题编制

7、 一组指令集,处理问题的策略,问题的数学模型,结构静力分析计算,例如: 数值计算的程序设计问题, 线性代数方程组, 环流模式方程 (球面坐标系),全球天气预报,非数值计算的程序设计问题,例一: 求一组(n个)整数中的最大值,算法: ? 模型：？,基本操作是“比较两个数的大小”,取决于整数值的范围,例二：计算机对弈,算法：? 模型：?,对弈的规则和策略,棋盘及棋盘的格局,例三：足协的数据库管理,算法：? 模型：?,需要管理的项目？ 如何管理？ 用户界面？,各种表格,概括地说，,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,1.2 基本

8、概念,一、数据与数据结构,二、数据类型,三、抽象数据类型,一、数据与数据结构,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,是数据（集合）中的一个“个体”,数据元素:,数据结构中讨论的基本单位,数据项：,数据结构中讨论的最小单位,数据元素可以是数据项的集合,例如：,描述一个运动员的数据元素可以是,称之为组合项,数据对象,是性质相同的数据元素的集合，是数据的一个子集。整数集合，字符集合。,数据结构：,带结构的数据元素的集合,假设用三个 4 位的十进制数表示一个含 12 位数的十进制数。,3214,6587

9、,9345 a1(3214),a2(6587),a3(9345),则在数据元素 a1、a2 和 a3 之间存在着“次序”关系 a1,a2、a2,a3,3214，6587，9345 a1 a2 a3,6587，3214，9345 a2 a1 a3,例如:,又例，在2行3列的二维数组a1, a2, a3, a4, a5, a6 中六个元素之间 存在两个关系:,行的次序关系: 列的次序关系:,row = ,col = ,a1 a3 a5 a2 a4 a6,a1 a2 a3 a4 a5 a6,再例，在一维数组 a1, a2, a3, a4, a5, a6 的数据元素之间存在如下的次序关系:,| i=1

10、, 2, 3, 4, 5,或者说，数据结构是相互之间存在着某种逻辑关系的数据元素的集合。,可见，不同的“关系”构成不同的“结构”,数据的逻辑结构可归结为以下四类:,线性结构,树形结构,图状结构,集合结构,数据结构的形式定义为:,数据结构是一个二元组,Data_Structures = (D, S),其中:D是数据元素的有限集， S是D上关系的有限集。,数据的存储结构（物理结构）, 逻辑结构在存储器中的映象 数据如何存储在计算机中。,“数据元素”的映象 ？,“关系”的映象 ？,数据元素的映象方法：,用二进制位(bit)的位串表示数据元素,(321)10 = (501)8 = (101000001

11、)2,A = (101)8 = (001000001)2,关系的映象方法：,（表示x, y的方法）,顺序映象,以相对的存储位置表示后继关系,例如:令 y 的存储位置和 x 的存储位置之间差一个常量 C,而 C 是一个隐含值，整个存储结构中只含数据元素本身的信息,x y,链式映象,以附加信息(指针)表示后继关系,需要用一个和 x 在一起的附加信息指示 y 的存储位置,y x,在不同的编程环境中，,存储结构可有不同的描述方法，,当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。例如用“一维数组”描述顺序存储结构，“指针”描述链式存储结构。,二、数据类型,在用高级程序语言编

12、写的程序中， 必须对程序中出现的每个变量、 常量或表达式，明确说明它们所 属的数据类型。,数据类型是一个值的集合和定义 在此集合上的一组操作的总称。,例如，C语言中提供的基本数据类型有:,整型 int,浮点型 float,字符型 char,逻辑型 bool （ C+语言）,双精度型 double,实型（ C+语言）,三、抽象数据类型 (Abstract Data Type 简称ADT),是指一个数学模型以及定义在此数学模型上的一组操作,抽象数据类型包括： 固有数据类型（整型，字符型等） 用户自定义数据类型,例如，抽象数据类型复数的定义：,数据对象： De1,e2e1,e2RealSet 数据关

13、系： R1 | e1是复数的实数部分, | e2 是复数的虚数部分 ,ADT Complex ,基本操作：,AssignComplex( i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +k) ci,j += ai,k*bk,j; ,基本操作: 乘法操作,时间复杂度: O(n3),例 二,for ( i = 2; i =n; +i ) for ( j = 2; j =i-1; +j ) +x; aij=x; ,基本操作: +x,时间复杂度: O(n2),例 三,void bubble_sort(int a, int n) / 将a中整数序列重新排列成自小至大有序的整数序列。 for (i=n-1, change=TRUE; i=1 change = TRUE / bubble_sort,基本操作: 赋值操作,时间复杂度: O(n2),四、算法的存储空间需求,算法的空间复杂度,表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 g(n) 的增长率相同。,S(n) = O(g(n),算法的存储量包括:,1输入数据所占