1.1数据结构基本概念2

1、第 1章 数据结构 1.1 数据结构的基本概念与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 内部排序ABCDEFG姓名 学号 成绩 班级 李红 9761059 95 机97.6 1065865计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和存储又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。什么

2、是数据结构 下面文字的含义： 漆黑的头发没有麻子脚不大周正 演绎 漆黑的头发，没有麻子，脚不大，周正。结论：描述一个古代美人！ 演绎 漆黑的头发没有，麻子，脚不大周正。结论：描述了一个古代丑女人，还是个瘸子。结论 两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只是文字的不同组合造成！也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：数据及其之间的关系（结构）。1.1 数据结构的基本概念与算法1.数据结构的定义1). 数据： 信息载体，能够被计算机识别、存储和加工处理。可以是数值数据(整数、实数)，也可以是非数值数据(声音、

3、图像等) 。2). 数据项: 是数据的具有独立含义的不可分割的最小标识单位,如成绩表中学号,姓名等.3). 数据元素： 一个数据元素由若干数据项组成,是数据的基本单位，通常作为一个整体进行考虑和处理(又称结点、记录)。 1.1.1数据结构的基本概念学号姓名系别住址电话981111李洪机械六舍5371111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎53722214个数据元素5个数据项1个数据项1个数据元素4). 数据对象: 具有相同性质的数据元素的集合。是数据的一个子集。 例: 成绩表 学号姓名系别住址电话981111李洪机械六舍537

4、1111982111王刚电子四舍5372111983211王将计算机五舍5373211983212张强机械六舎53722211.数据结构的定义1). 数据：2). 数据项: 3). 数据元素： 关键码：值唯一能区别不同的数据元素的数据项数据对象-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成.1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念1.数据结构的定义1). 数据：2). 数据项: 3). 数据元素： 4). 数据对象: 5).数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 研究 内容数据的逻辑结构： 各数据元素之间的逻辑关系数据的存储结构： 各数据

5、元素在计算机中的存储关系对各种数据结构进行的运算： 添加，删除，排序等。1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念1.数据结构的定义1). 数据：2). 数据项: 3). 数据元素： 4). 数据对象: 5).数据结构: 相互之间存在着一种或多种关系的数据元素的集合。 研究 目的一是提高数据处理的速度.二是尽量节省在数据处理过程中所占用的计算机存储空间.1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念1.数据结构的定义2.数据的逻辑结构集合元素间为松散的关系 (属于关系)线性结构元素间为一对一关系树形结构元素间为一对多关系图状结构元素间为多对多关系1.1 数据结构

6、的基本概念与算法1.1.1数据结构的基本概念集合、树型、图形结构属于非线性结构学号姓名语文数学C语言1001张三8554921002李四9284641003王五877473.通迅录、成绩单、花名册线性结构电子字典、家谱、目录树型结构HBCDEFGAHGFECDBA计算机中的目录结构问题树交通线路、通信网络图状结构图形结构特点结点间的连结是任意的AEBCD树型结构特点结点间具有分层次的连接关系3.数据结构的存储结构 数据的存储结构是指数据元素及其关系在计算机存储器内的表示（又称映象）。 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。 一种数据结构可以根据需要采用多种不同的存储结构，

7、常用的存储结构有顺序、链接与索引等存储方式。 数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的。 1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念3.数据结构的存储结构(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念顺序存储结构的线性表线性表(a0, a1, a2, a3)存储单元的地址即物理地址如，C语言的数组a2a3a1a0a1a03.数据结构的存储结构(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。

8、通常借助于数组来实现。(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。 1.1 数据结构的基本概念与算法1.1.1数据结构的基本概念链式存储结构的线性表存储单元的地址即物理地址指针域：存放下一个结点的地址a0,a1在逻辑上相邻,而在机内存储时,存储单元的地址(100,108)并不相邻.链式存储方式特点：每个结点由两部分组成：一部分存放数据，另一部分 存储指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。数据运算(插入和删除等)灵活。a2a3a1a01.1 数据结构的基本概念与算法1.1.1数据结构的基本概念6

9、.数据类型及其分类 数据类型（Data Type）是程序设计语言中所允许使用的变量类型。 一个变量类型不仅定义了相应变量可以设定的值的的集合，还规定了对变量允许进行的一组运算及其规则。 例：C语言中的整型变量，其值为某个区间上整数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。 分类：（1）非结构的原子类型 （2）结构类型（2）结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。（1）非结构的原子类型：原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。结构类型举例： struct

10、stuchar nm8; / 学号char name18; / 姓名char sex; / 性别;struct stu s1; / 学生类型1.算法的定义： 算法(A1gorithm)是对特定问题求解步骤的精确描述，它是指令或语句的有限序列 。1.1 数据结构的基本概念与算法1.1.2 算法及算法分析 有穷性： 一个算法应包含有限个操作步骤，而且每一步都应在有限时间内完成。 确定性：算法中每一条指令必须有确切的含义，确保不会产生二义性。 可行性：算法中指定的操作都是可以通过基本运算执行有限次后实现。 输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象集合。 输出：一个算法有一个或多

11、个的输出，这些输出是同输入有着某些特定关系的量。1.算法概念 算法(A1gorithm)是对特定问题求解步骤的精确描述，它是指令或语句的有限序列 。1.1 数据结构的基本概念与算法1.1.2 算法及算法分析 首先要从具体问题抽象出一个适当的数学模型；然后设计一个解此数学模型的算法；最后采用一种计算机语言编出程序，调试、修改直至得到最终答案。用计算机解决一个具体问题时，大致需要经过下列几个步骤：1.1 数据结构的基本概念与算法1.1.2 算法及算法分析 算法设计的要求 （1）正确性 （2） 可读性 （3）健壮性 （4）效率与低存储量 执行结果应满足预先的功能和性能要求思路清晰、层次分明、简单明了

12、、易读易懂输入数据非法时，算法能作适当处理，不致于引起严重后果有效使用存储空间和较高的时间效率1.1 数据结构的基本概念与算法评价算法标准 算法所占用计算机资源，即时间代价(算法所需要的时间）和空间代价（算法所需要的存储空间）。 算法所需要的时间包括：程序运行时所需要的数据总量；源程序进行编译所需要的时间；计算机执行每条指令所需要的时间；程序中指令重复执行的次数，而本条正是讨论算法中的重点内容 （常考） 1.1.2 算法及算法分析 1.1 数据结构的基本概念与算法1.1.3 算法分析技术初步 1.时间复杂度： 算法中基本操作重复执行的次数依据算法中最大语句频度来估算，它是问题规模n的某个函数f

13、(n)，算法的时间量度记作T(n)O(f（n) 表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。 时间复杂度： T (n)=O( f (n) ) T (n)：算法中所有语句频度之和n：问题规模。 T (n) 是n的某个函数。O：数量级。当问题规模趋向无穷时， T (n)的数量级称为时间复杂度。 x+=5; 单个语句的频度为1，则 程序段的时间复杂度为 for(i=0;in; i+) for(j=0 ;jn;j+) x+=5; 最优算法：随n的增大， T (n)增长较慢的算法。T(n)=O(1)则：T(n)= O(n2)for(i=1

14、;i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; 由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3时间复杂度为T(n)=O(n3)for(i=1;i=n;+i) +x; y+; 语句频度为：2n其时间复杂度为：O(n) for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x;语句频度为： 1+2+3+n-2 =(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 时间复杂度为O(n2)时间复杂度：平均时间复杂度：所有可能的输入实例均以等概率出现的情况

15、下，算法的期望运行时间。最坏时间复杂度：最坏情况下算法的时间复杂度。 算法的时间复杂度不仅与问题规模有关,而且与输入数据有关,即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3)1.1 数据结构的基本概念与算法2.空间复杂度： 定义：算法运行从开始到结束所需的存储空间量,包括 固定部分和可变部分。固定部分：此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序代码、常量、变量等。 可变部分：此部分空间与处理的数据的大小和规模有关，即执行算法时所需额外空间。

16、 1.1.2 算法及算法分析 思考题研究数据结构的目的是什么？数据结构研究哪三方面的问题?关系如何?在数据结构中数据项、数据元素及数据对象的关系？数据的逻辑结构分为哪两大类？各有何特点？数据的存储结构中的顺序存储与链式存储各有什么特点？什么是算法？有何特点？算法设计的基本要求？算法设计的方法？如何评价算法？什么是时间复杂度？时间复杂度与哪些因素有关？什么是空间复杂度？包括哪两部分？习题讲解 1. 数据处理的最小单位是_。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构2. 数据结构中，与所使用的计算机无关的是数据的_。 A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储

17、结构3. 下面叙述正确的是_。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对4. 算法的时间复杂度是指_。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 5. 算法的空间复杂度是指_。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间CCCCD习题讲解 6. 算法一般都可以用哪几种控制结构组合而成_。 A. 循环、

18、分支、递归 B. 顺序、循环、嵌套C. 循环、递归、选择 D. 顺序、选择、循环7.数据的存储结构是指_。 A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示8. 在下列选项中，哪个不是一个算法应该具有的基本特征_。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报9. 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法10. 算法分析的目的是_。 A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进DDCCD习题讲解 11.算法具有五个特性，以下选项中不属于算法特性的是_。 A）有穷性 B）简洁性 C）