《计算机应用基础课件1.1数据结构基本概念》由会员分享，可在线阅读，更多相关《计算机应用基础课件1.1数据结构基本概念（35页珍藏版）》请在金锄头文库上搜索。
1、,第 1章 数据结构,1.1 数据结构的基本概念与算法 1.2 线性表 1.3 栈和队列 1.4 树和二叉树 1.5 查找 1.6 内部排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 而信息的表示和存储又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,什
2、么是数据结构,下面文字的含义： 漆黑的头发没有麻子脚不大周正,演绎 漆黑的头发，没有麻子，脚不大，周正。 结论：描述一个古代美人！,演绎 漆黑的头发没有，麻子，脚不大周正。 结论：描述了一个古代丑女人，还是个瘸子。,结论 两个不同的演绎表现为不同的结果，一个是古代美人，一个确实古代丑女人，原因只是文字的不同组合造成！ 也就是说：相同的文字（数据）经过不同的组合（结构）会得到不同的结果，这就是我们要介绍的数据结构：数据及其之间的关系（结构）。,1.1 数据结构的基本概念与算法,1.数据结构的定义 1). 数据： 信息载体，能够被计算机识别、存储和加工处理。可以是数值数据(整数、实数)，也可以是非
3、数值数据(声音、图像等) 。 2). 数据项: 是数据的具有独立含义的不可分割的最小标识单位,如成绩表中学号,姓名等. 3). 数据元素： 一个数据元素由若干数据项组成,是数据的基本单位，通常作为一个整体进行考虑和处理(又称结点、记录)。,1.1.1数据结构的基本概念,4个数据元素,5个数据项,1个数据项,1个数据元素,4). 数据对象: 具有相同性质的数据元素的集合。是数据的一个子集。 例: 成绩表,1.数据结构的定义 1). 数据： 2). 数据项: 3). 数据元素：,关键码：值唯一能区别不同的 数据元素的数据项,数据对象-由4个记录组成,表中每行是一个记录,每个记录由5个数据项组成.,
4、1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,1.数据结构的定义 1). 数据： 2). 数据项: 3). 数据元素： 4). 数据对象:,5).数据结构: 相互之间存在着一种或多种关系的数据元素的集合。,研究 内容,数据的逻辑结构： 各数据元素之间的逻辑关系 数据的存储结构： 各数据元素在计算机中的存储关系 对各种数据结构进行的运算： 添加，删除，排序等。,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,1.数据结构的定义 1). 数据： 2). 数据项: 3). 数据元素： 4). 数据对象:,5).数据结构: 相互之间存在着一种或多种关系的数据元素的集合
5、。,研究 目的,一是提高数据处理的速度. 二是尽量节省在数据处理过程中所占用的计算机存储空间.,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,1.数据结构的定义,2.数据的逻辑结构,集合元素间为松散的关系 (属于关系) 线性结构元素间为一对一关系 树形结构元素间为一对多关系 图状结构元素间为多对多关系,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,集合、树型、图形结构属于非线性结构,通迅录、成绩单、花名册,线性结构,电子字典、家谱、目录,树型结构,计算机中的目录结构问题,交通线路、通信网络,图状结构,树型结构特点结点间具有分层次的连接关系,3.数据结构的存储
6、结构,数据的存储结构是指数据元素及其关系在计算机存储器内的表示（又称映象）。 存储结构研究的是逻辑结构用计算机语言实现，依赖于计算机语言。,一种数据结构可以根据需要采用多种不同的存储结构，常用的存储结构有顺序、链接与索引等存储方式。 数据的存储结构不同，解决问题的方法就有所不同，数据处理的效率也是不同的。,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,3.数据结构的存储结构,(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,顺序存储结构的线性表,线性表(
7、a1, a2, a3, a4),存储单元的地址即物理地址,如，C语言的数组,3.数据结构的存储结构,(1)顺序存储方式：逻辑上相邻的元素存储在物理位置相邻的存储单元中。主要用于线性结构。通常借助于数组来实现。,(2)链式存储方式：对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常借助于指针类型实现。,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,链式存储结构的线性表,存储单元的地址即物理地址,指针域：存放下一个结点的地址,a1,a2在逻辑上相邻,而在机内存储时,存储单元的地址(100,105)并不相邻.,链式存储方式特点： 每个结点由两部分组
8、成：一部分存放数据，另一部分 存储指向前件或后件结点的指针域。 逻辑上相邻的结点物理上不必相连。 数据运算(插入和删除等)灵活。,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,5.数据类型及其分类,数据类型（Data Type）是程序设计语言中所允许使用的变量类型。 一个变量类型不仅定义了相应变量可以设定的值的的集合，还规定了对变量允许进行的一组运算及其规则。 例：C语言中的整型变量，其值为某个区间上整数，定义在其上的操作为：加，减、乘、除和求余数等算术运算。,分类：（1）非结构的原子类型 （2）结构类型,（2）结构类型：结构类型的值是由若干成分按某种结构组成的，因此是可分解
9、的，并且它的成分可以是非结构的，也可以是结构的。,（1）非结构的原子类型：原子类型的值是不可分解的。如：程序设计语言中的基本类型（整型，实型，字符型，指针类型和空类型）。,结构类型举例： struct stu char nm8; / 学号 char name18; / 姓名 char sex; / 性别 ; struct stu s1; / 学生类型,1.1 数据结构的基本概念与算法,1.1.1数据结构的基本概念,6.抽象数据类型（Abstract Data Type,ADT),抽象数据类型（Abstract Data Type，简称ADT）是指基于一切逻辑关系的数据类型以及定义在这个类型之上
10、的一组操作。在某种意义上讲，抽象数据类型和数据类型实质上是一个概念。抽象数据类型由元素、结构和操作三部分组成。,一个线性表的抽象数据类型可定义如下： ADT Linear_List 数据元素：所有ai属于同一数据对象，i=1,2,n（n0） 逻辑结构：所有数据元素ai存在次序关系（ai，ai+1）， a1无前驱，an无后继 基本操作：设L为List类型的线性表 InitList( 单个语句的频度为1，则 程序段的时间复杂度为, for(i=0;in; i+) for(j=0 ;jn;j+) cij=i*j;,最优算法：随n的增大， T (n)增长较慢的算法。,T(n)=O(1),则：T(n)=
11、 O(n2),for(i=1;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; s+=x; 语句频度为：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),时间复杂度：,平均时
12、间复杂度：所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。 最坏时间复杂度：最坏情况下算法的时间复杂度。,算法的时间复杂度不仅与问题规模有关,而且与输入数据有关,即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3),1.1 数据结构的基本概念与算法,1.1.3 算法分析技术初步,2.空间复杂度：,定义：算法运行从开始到结束所需的存储空间量,包括 固定部分和可变部分。,固定部分：此部分空间与所处理数据的大小和规模无关。通常用来保存本身所用的程序代码、常量
13、、变量等。 可变部分：此部分空间与处理的数据的大小和规模有关，即执行算法时所需额外空间。,思考题,研究数据结构的目的是什么？ 数据结构研究哪三方面的问题?关系如何? 在数据结构中数据项、数据元素及数据对象的关系？ 数据的逻辑结构分为哪两大类？各有何特点？ 数据的存储结构中的顺序存储与链式存储各有什么特点？ 什么是算法？有何特点？ 算法设计的基本要求？ 算法设计的方法？ 如何评价算法？ 什么是时间复杂度？时间复杂度与哪些因素有关？ 什么是空间复杂度？包括哪两部分？,习题讲解,1. 数据处理的最小单位是_。 A. 数据 B. 数据元素 C. 数据项 D. 数据结构 2. 数据结构中，与所使用的计算
14、机无关的是数据的_。 A. 存储结构 B. 物理结构 C. 逻辑结构 D. 物理和存储结构 3. 下面叙述正确的是_。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 4. 算法的时间复杂度是指_。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 5. 算法的空间复杂度是指_。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的
15、存储空间,CCCCD,习题讲解,6. 算法一般都可以用哪几种控制结构组合而成_。 A. 循环、分支、递归 B. 顺序、循环、嵌套C. 循环、递归、选择 D. 顺序、选择、循环 7.数据的存储结构是指_。 (05.4月）A）存储在外存中的数据 B）数据所占的存储空间量 C）数据在计算机中的顺序存储方式 D）数据的逻辑结构在计算机中的表示 8. 在下列选项中，哪个不是一个算法应该具有的基本特征_。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报 9. 在计算机中，算法是指_。 A. 查询方法 B. 加工方法 C. 解题方案的准确而完整的描述 D. 排序方法 10. 算法分析的目的是_。 A. 找出数据结构的合理性 B. 找出算法中输入和输出之间的关系 C. 分析算法的易懂性和可靠性 D. 分析算法的效率以求改进,DDCCD,习题讲解,11.算法具有五个特性，以下选项中不属于算法特性的是_。(05.4月） A）有穷性 B）简洁性 C）可行性 D）确定性 12. 下列叙述中正确的是 A）一个逻辑数据结构只能有一种存储结构 B）数据的逻辑结构属于线性结构，存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D）一
