软件技术基础数据结构基本概念

1、,第一章 数据结构,1.1 数据结构的基本概念 1.2 线性结构 1.3 非线性结构 1.4 查找和排序,1.1数据结构的基本概念,1.1.1 什么是数据结构,早期计算机,仅仅用于简单的计算 决定计算机的效率运算速度 输入输出的数据量小 数据元素之间的关系简单 不需数据结构,计算机应用 扩展后,大量的非数值运算 决定计算机的效率- CPU速度 及数据之间的关系结构 输入输出的数据量大 数据元素之间的关系复杂 需要数据结构描述数据之间的关系,2,计算机解一个有关数值计算的具体问题的步骤：,建立数学模型的实质是：分析实际问题，寻找包含在问题中的操作对象，以及这些对象之间的关系，并用数学的语言对这些

2、操作对象和其间的关系加以描述，这就是该问题的数学模型。,建立数学模型设计解模算法编程调试输出结果,数值计算问题中的数学模型通常可用数学方程来描述，但是更多的非数值计算的问题却无法用数学方程来描述其数学模型。,3,例1 学生成绩查询,这三张查询表就是学生成绩查询的数学模型，各元素间存在线性关系，因此这种数学模型称为线性数据结构。,4,d,例2 人机对奕问题（五子棋）,对奕的过程是在一定的对奕规则和取胜策略下进行的，因此为使计算机能够灵活对奕必须事先将对奕的规则、以及对奕过程中可能出现的情况和相应的策略都存入计算机。在人机对奕过程中，计算机操作的对象是对奕过程中可能出现的棋局状态（称为格局）。,c

3、,b,a,5,联想一下，若将一局棋从开始到结束可能出现的格局都画出来，可以得到下面一张图：,因此，对奕问题中的数学模型就是以各种格局为元素的一种“树”结构。可以看出这种树结构中元素的关系不是简单的线性关系，它是另一种典型的数据结构，称为“树结构”。,6,由此，至少要四种颜色的交通灯才能满足保证交通秩序的要求。,例3 利用交通灯进行多叉路口的交通管理问题,本题中可以用一个圆圈表示一条通路，两个通路之间的矛盾关系用对应两个圆圈的连线表示（圆圈称为顶点、连线称为边），则设置交通灯的问题可以等价为对圆圈的染色问题。要求： 每个顶点染一种颜色。 相连的顶点不能染相同的颜色。 总色类最少。,用计算机来解决

4、这类问题时，要处理的问题是诸如顶点和边这样的元素，数据结构中称这种为图结构，于是这类问题的数学模型就是“图”这种数据结构。,7,由此我们可以这样来定义数据结构：,它是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。,8,数据(data)：对客观事物的符号表示，在计算机中是指所有能输入到计算机中被计算机程序处理的符号的总称。 整数，实数，字符串；图象声音编码数据,数据元素(data element)： 数据的基本单位（也称数据结点）通常作为一个整体考虑，代表一定的特征。一个数据元素可由若干个数据项组成。,数据项(data Item)：一个数据元素可以由若干个数

5、据项组成，它是数据的不可分割的最小单位。,一、几个概念,基本概念和述语,9,例、学生花名册,数据元素,数据,学生名字的集合,每个学生的名字,例、学生成绩表,数据,数据元素,数据项,学生成绩的集合,每个学生的成绩,名字,成绩,10,数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。,数据对象(data object)：性质相同的数据元素的集合，是数据的一个子集。 如整数数据对象是集合N=0,1,2,3. 字母数据对象是集合C= a,b,c,d.,任何问题中，数据元素都不是孤立存在的，而是在它们之间存在某种关系，这种数据元素相互之间的关系称为结构 (structure),11,例：家庭成

6、员数据结构可以表示成： F=(C,R) C=父亲，儿子，女儿 R=(父亲，儿子)，(父亲，女儿) ， (儿子，女儿),用形式化描述：数据结构是一二元组： Data_Structure=(K,R) 其中：K是数据元素的有限集合， R是K上关系的有限集。,12,例：用数据结构描述整数I*,1、组成整数数据的全部元素的集合I I 0，1，2，3,2、I中元素的关系集合RE,3、I*的运算集合P，比如算术四则运算,4、P中诸运算的运算规则RU， 如乘、除法优先于加、减法等,I* I，RE，P，RU,RE -10,01,12,13,元素集合,元素间的关系,运算,计 算 机 系 统,元素在计算机系统里的表

7、示 字符？字串？整数？ 元素间的逻辑关系逻辑结构 元素在计算机系统中的存储方式，物理空间关系存储结构 操作指令的集合算法,14,数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合 把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度,小结,15,直接前驱、直接后继： 在数据结构中的任意一个元素与之相邻且在它之前的元素称为该元素的直接前驱，同理与之相邻且在它之后的元素称为该元素的直接后继。,名称解释,16,二、数据的逻辑结构,逻辑结构：数据元素之间在形式上所呈现的关系。,线性结构：定义。 典型的线性结构有

8、线性表， 如：学生成绩表。,线性结构,17,非线性结构：定义。 典型的非线性结构为图结构， 而树是一种特殊的非线性结构。,树结构,图结构,18,三、数据的存储结构（物理结构）,物理结构：数据结构在计算机中的表示（或映象）。 它包括数据元素的表示和关系的表示。 数据元素之间的关系在计算机中不同的表示方法得 到不同的存储结构：,1、顺序存储结构：定义。 多用于线性结构的存储。 各元素之间的逻辑关系是通过存储单元(物理位置)的相邻的关系来反映的。,地址 100 130 160 190,存储单元,19,2、链式存储结构： 定义。 元素间的逻辑关系是由指针来反映的。,地址 P4 300 P1 P2,存储

9、单元,20,3、索引存储： 在存储(即可是顺序存储，也可是链接存储)元素的同时，还建立附加的索引表，索引表中每一项称为索引项， 索引项的一般形式是：（关键字，地址） 关键字是能唯一标识一个元素的数据项。,21,元素可以离散存放,通过查索引表找到需要的元素,索引表,1,2,3,4,索引号,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,22,4、散列存储：没有附加的索引表，从数据元素中直接计算出存储地址，根据元素的关键字直接计算出该元素的存储地址，即在数据元素的字段中有一个或几个字段的值，通过某一散列函数唯一地确定该元素

10、的存储地址。,例：以用户姓名为关键值,算式字母的序号相加,DJS,ZXM,041019 33,262413 63,所以，DJS放在33号地址单元 ZXM放在63号地址单元,23,四、数据操作,数据结构中常见的操作：,遍历：查看数据结构中的所有数据元素。,插入：添加新的元素到一个数据结构中。,删除：将指定元素从数据结构中去掉。,更新：修改数据结构中的某个数据元素。,查找：在数据结构中寻找满足条件的数据元素。,排序：将数据结构中的数据元素按指定的顺序排列。,加工型操作：插入、删除、更新、排序,访问型操作：遍历、查找,24,注意,数据的逻辑结构，数据的存储结构和数据的操作 是一个整体，共同构成数据结

11、构。,数据操作（指某种算法）的设计取决于选定的数据 逻辑结构; 数据操作的实现,取决于选定的存储结构。,同一逻辑结构不同的存储结构是不同的数据结构。,同一逻辑结构、存储结构中,不同的操作也是 不同数据结构。,25,1.1.3 C语言的数据类型,见 “C语言复习”。,26,定义： 算法是对特定问题求解步骤的一种描述。它是指令的有限序列其中每一条指令表示一个或多个操作。,1.1.4 算 法,27,算法的五个特性： 有穷性：一个算法必须总是（对于合法的输入值）在执行有穷 步之后结束，且每一步都可在有穷时间内完成。 确定性：算法中的每一条指令，必须有确切含义，读者不会 产生二义性，且在任何条件下，算法

12、只有唯一的一条 执行路径，即对于相同的输入只能得出相同的输出。 可行性：一个算法是可行的，即算法中描述的操作可以通过已 经实现的基本运算执行有限次来实现。 输 入：一个算法有零个或多个输入，这些输入取自特定的 对象的集合。 输 出：一个算法有一个或多个输出。这些输出与输入有特 定关系。,28,算法与程序,相似：都是解决问题的方法和步骤，是指令的集合,区别：,有穷性,描述方法,程序使用程序设计语言,算法可以使用框图及其他语言,联系：,程序是用某种程序设计语言来实现算法,29,算法语言,算法有严格的描述语言（确定性）,使用类C 或 类PASCAL语言,要求描述一个算法时必须满足：,1、输入和输出的

13、描述,2、描述语句准确、无二义,3、保证算法的有穷性和有效性,在数据结构中常见的问题,检索、插入、删除、更新、排序,每个问题都有一种和多种算法,30,如何衡量一个正确算法的好坏？ 三个尺度 运行所花费的时间（算法的时间特性）； 所占用存储空间的大小（算法的空间特性）； 其它（正确性、可读性、健壮性等）。 时间和空间特性的巨大改进源于更好的数据结构或算法。,算法分析,31,语句频度（Frequency Count）： 语句可能重复执行的最大次数。 时间复杂度（Time Complexity）： 设算法中所有语句的语句频度为t(n)，f(n)是当n趋向无穷大时与t(n)为同阶无穷大，则算法的(渐进

14、)时间复杂度 T(n)=O(f(n) 其中：n为算法计算量或称为规模（size）； f(n)是运算时间随n增大时的增长率； O(f(n)是算法时间特性的量度。,时间复杂度,32,常见复杂度,复杂度高,复杂度低,33,例：程序段 语句频度 时间复杂度 1. x=x+1; 1 O(1) 常数阶 2. for( i=1;i=n;i+) n +1 O(n) 线性阶 x=x+1; 3. for ( i=1;i=n;i+) n+1 for ( i=1;i=n;j+); n(n+1) O(n2) 平方阶 x=x+1;,算法分析示例,34,空间复杂度,空间复杂度： 算法所需的内存空间 S(n)=O(f(n),35,*编写算法的一般步骤：,1、分析问题描述,2、分析算法实现的