关于数据结构的基本介绍和基础内容

《关于数据结构的基本介绍和基础内容》由会员分享，可在线阅读，更多相关《关于数据结构的基本介绍和基础内容（34页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构信息与计算科学专业一、任课教师简介姓名：郭荣伟联系电话：13173006561二、课程要求1、本课程总评成绩的计算算法：总成绩=平时成绩*30%+期末成绩*70%；平时成绩（100分）=出勤（30）+作业（40） +随堂上机（30）；2、出勤的统计方法是随机抽查和全查，无故缺勤一次扣10分， 累计三次无考试资格；请假必须提前通知任课老师，并具有班 主任或者辅导员签字的假条，视具体情况扣分，原则上不会超 过5分，补假无效。三、本课程简介数据结构是信息与计算专业的一门专业基础课，其目的是要学习和 逐步掌握各种数据结构和算法，培养设计算法和开发程序的能力， 达到能够根据实际问题的需要，

2、选择适当的数据结构及设计出相应 的算法，并通过上机实验，编写出程序。本课程的主要任务是进一 步锻炼学生的动手能力，提高学生分析和解决实际问题的能力。 本课程的主要内容有各种线性表的介绍，如栈和队列，串；树的 介绍和应用，图的介绍和应用，各种查找和排序算法以及相应的 算法设计和分析。本课程达到的要求是掌握各种数据结构的逻辑 机构和物理结构，以及相应的各种算法。达到对给定一个具体的 问题，能设计出合适的数据结构，选择恰当的算法，并且编写出 具体的实现程序，同时还能书写出规范的程序说明书。第1章 绪论本章主题：数据结构的基本概念和术语本章主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念

3、，理解常用术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：熟悉数据结构常用术语，掌握基本概念，了解算教学重点：熟悉数据结构常用术语，掌握基本概念，了解算 法时间复杂度和空间复杂度的分析与评价法时间复杂度和空间复杂度的分析与评价 教学难点：数据元素间的教学难点：数据元素间的 4 4 种结构关系。种结构关系。主要内容：主要内容： 1.1 1.1 什么是数据结构什么是数据结构1.21.2 算法描述算法描述1.3 1.3 算法分析与评价算法分析与评价计算机是一门研究用计算机进行信息表示和 处理的科学。这里面涉及到两个问题：1. 信息的表示,2.信息的处理而信息的表示又直接关系到处理信息的程

4、 序的效率。随着计算机的普及，信息量的 增加，信息范围的拓宽，使许多系统程序 和应用程序的规模很大，结构又相当复杂 。因此，为了编写出一个“好”的程序，必须分 析待处理的对象的特征及各对象之间存在的 关系，这就是数据结构这门课所要研究的问 题。l 1.1什么是数据结构l 众所周知，计算机的程序是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，信息（ 数据）之间往往具有重要的结构关系，这就是数据结 构的内容。那么，什么是数据结构呢？先看以下几个 例子。l 例1、电话号码查询系统l 设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排：l (a1，b1)(

5、a2，b2)(an，bn)l其中ai，bi(i=1，2n) 分别表示某人的名字和对应的电 话号码要求设计一个算法，当给定任何一个人的名字 时，该算法能够打印出此人的电话号码，如果该电话 簿中根本就没有这个人，则该算法也能够报告没有这 个人的标志。l 算法的设计，依赖于计算机如何存储人的 名字和对应的电话号码，或者说依赖于名字和 其电话号码的结构。l 数据的结构，直接影响算法的选择和效率 。l 上述的问题是一种数据结构问题。可将名 字和对应的电话号码设计成：二维数组、表结 构、向量。假定名字和其电话号码逻辑上已安排成N 元向量的形式，它的每个元素是一个数对(ai， bi)， 1in 数据结构还要

6、提供每种结构类型所定义的 各种运算的算法。例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题见课本通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构 以及它们之间相互关系，并对这种结构定义相应 的运算，而且确保经过这些运算后所得到的新结构 仍然是原来的结构类型。l 1.2 基本概念和术语l数据(Data):是对信息的一种符号表示。在计 算机科学中是指所有能输入到计算机中并被 计算机程序处理的符号的总称。l数据元素(Data Element):是数据的基本单位， 在计算机程序中通常作为一个整体进行考虑 和处理。l 一个数据元素可由若

7、干个数据项组成。数 据项是数据的不可分割的最小单位。l数据对象(Data Object)：是性质相同的数据 元素的集合。是数据的一个子集。l数据结构(Data Structure)：是相互之间存在 一种或多种特定关系的数据元素的集合。l数据类型：在一种程序设计语言中，变量所具 有的数据种类。l例、在C语言中l数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举型 、自定义l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构。通常分 为四类基本结构：l一、集合 结构中的数据元素除了同属于一种 类型外，别无其它关系。l二、线性结构 结

8、构中的数据元素之间存在一 对一的关系。l三、树型结构 结构中的数据元素之间存在 一对多的关系。l四、图状结构或网状结构 结构中的数据元素 之间存在多对多的关系。l 四四类数据基本结构的示意图类数据基本结构的示意图：(a)(a)集合结构集合结构 (b)(b)线性结构线性结构 (c)(c)树型结构树型结构 (d)(d)图形结构图形结构数据结构的形式定义为：数据结构是一个二元 组：Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的 有限集。l例 复数的数据结构定义如下：l Complex=(C，R)l其中：C是含两个实数的集合C1，C2，分 别表示复数的实部和虚部。

9、R=P，P是定义在 集合上的一种关系C1，C2。l数据结构在计算机中的表示称为数据的物理结 构，又称为存储结构。l数据结构在计算机中有两种不同的表示方法：l 顺序表示和非顺序表示l由此得出两种不同的存储结构：顺序存储结 构和链式存储结构l顺序存储结构:用数据元素在存储器中的相对 位置来表示数据元素之间的逻辑关系。l链式存储结构：在每一个数据元素中增加一 个存放地址的指针，用此指针来表示数据元素 之间的逻辑关系。注：任何一个算法的设计取决于选定的数据（逻 辑）结构，而算法的实现依赖于采用的存储结构抽象数据类型抽象数据类型（AbstructAbstruct Data Type Data Type，

10、简简称称ADTADT）ADTADT是指一个数学模型以及定义在该模型上是指一个数学模型以及定义在该模型上的一组的操作。可以看作是数据的逻辑结构及的一组的操作。可以看作是数据的逻辑结构及 其在逻辑结构上定义的操作。其在逻辑结构上定义的操作。 抽象数据类型的定义仅取决于它的一组逻辑抽象数据类型的定义仅取决于它的一组逻辑 特性，而与其在计算机内部如何表示和实现无特性，而与其在计算机内部如何表示和实现无 关关。即不论其内部结构如何变化，只要它的数即不论其内部结构如何变化，只要它的数 学特性不变，都不影响其外部的使用。学特性不变，都不影响其外部的使用。l 抽象数据类型和数据类型实质上是一个概念 。例如，各

11、个计算机都有的“整数”类型是一个 抽象数据类型，尽管他们在不同处理器上实现 的方法不同，但由于其定义的数学特性相同， 在用户看来都是相同的，因此“抽象”的意义在 于数据类型的数学抽象性。l用三元组描述如下：l （，）l其中是数据对象，是上的关系集，是 对的基本操作。l详细内容见课本8l算法和算法分析l算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指令 表示一个或多个操作。l 算法具有以下五个特性：l（1）有穷性 一个算法必须总是在执行有穷步 之后结束，且每一步都在有穷时间内完成。l（2）确定性 算法中每一条指令必须有确切的 含义。不存在二义性。且算法只有一个入口和 一

12、个出口。l（3）可行性 一个算法是可行的。即算法描述 的操作都是可以通过已经实现的基本运算执行 有限次来实现的。l4）输入 一个算法有零个或多个输入，这些输 入取自于某个特定的对象集合。l5）输出 一个算法有一个或多个输出，这些输 出是同输入有着某些特定关系的量。l算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性(Correctness ) 算法应满足具体问题 的需求。l(2)可读性(Readability) 算法应该好读。以有 利于阅读者对程序的理解。(3)健状性(Robustness) 算法应具有容错处理。 当输入非法数据时，算法应对其作出反应，而 不是产生莫名其妙的输出结

13、果。l(4)效率与存储量需求 效率指的是算法执行的 时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般，这两者与问题的规模有 关。l1.4.3 算法效率的度量l 对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事前分析和事后统计l事前分析 求出该算法的一个时间界限函数l事后统计 收集此算法的执行时间和实际占用 空间的统计资料。l注：事后统计有两个缺陷，人们常常采用事前 分析估算的方法。 一般情况下，算法中基本操作重复执行的 次数是问题规模n的某个函数，算法的时 间量度记作T(n)=O(f(n)称作算法的渐近时间复杂度。 例、for(i=1，i1 -I)l l change=f

14、alse;l for(j=0;jaj+1) l aj aj+1;l change=TUREl l l l最好情况：0次l最坏情况：1+2+3+n-1l =n(n-1)/2l平均时间复杂度为:O(n2)l注：除特别指明外，均指最坏情况下的 时间复杂度2 2空间复杂度空间复杂度（Space complexitySpace complexity）一个算法的空间复杂度是指算法运行从开始到结束所一个算法的空间复杂度是指算法运行从开始到结束所 需的存储量。需的存储量。算法的存算法的存储储储储量指的是算法量指的是算法执执执执行行过过过过程中所需的最大存程中所需的最大存 储储储储空空间间间间。 算法算法执执行

15、期行期间间所需要的存所需要的存储储量量应该应该 包括以下三部分：包括以下三部分：(1) (1) 输输入数据所占空入数据所占空间间；(2) (2) 程序本身所占空间；程序本身所占空间；(3) (3) 辅辅助助变变量所占空量所占空间间。 类类似于算法的似于算法的时间时间 复复杂杂度，通常以算法的空度，通常以算法的空间间复复杂杂度作度作 为为算法所需存算法所需存储储空空间间的量度。定的量度。定义义：S(n)=O(g(n)S(n)=O(g(n)称称S(n)S(n)为为算法的空算法的空间间复复杂杂度。度。 若输入数据所占空间只取决于问题本身，和算法无关 ，则只需要分析除输入和程序之外的额外空间，否则 应同时考虑输入本身所需空间（和输入数据的表示形 式有关）原地工作：若额外空间相对于输入数据量来说是个常 数，练习题 一、选择