清华数据结构严蔚敏

《清华数据结构严蔚敏》由会员分享，可在线阅读，更多相关《清华数据结构严蔚敏（240页珍藏版）》请在金锄头文库上搜索。

1、数 据 结 构计算机系第一章 绪 论1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分1.4.1 算法1.4.2 算法设计的要求1.4.3 算法效率的度量1.4.4 算法的存储空间的需求第一章 绪 论l计算机是一门研究用计算机进行信息表示和 处理的科学。这里面涉及到两个问题：l 信息的表示信息的处理而信息的表示和组又直接关系到处理信息 的程序的效率。随着计算机的普及，信息量 的增加，信息范围的拓宽，使许多系统程序 和应用程序的规模很大，结构又相当复杂。 因此，为了编写出一个“好”的程序，必须分 析待处理的对象的特征及各对象之间存在的 关系，这

2、就是数据结构这门课所要研究的问 题。l 1.1什么是数据结构l 众所周知，计算机的程序是对信息进行加工处理 。在大多数情况下，这些信息并不是没有组织，信 息（数据）之间往往具有重要的结构关系，这就是 数据结构的内容。那么，什么是数据结构呢？先看 以下几个例子。l 例1、电话号码查询系统l 设有一个电话号码薄，它记录了N个人的名字和 其相应的电话号码，假定按如下形式安排：l (a1，b1)(a2，b2)(an，bn)l其中ai，bi(i=1，2n) 分别表示某人的名字和对应的 电话号码要求设计一个算法，当给定任何一个人的 名字时，该算法能够打印出此人的电话号码，如果 该电话簿中根本就没有这个人，

3、则该算法也能够报 告没有这个人的标志。l 算法的设计，依赖于计算机如何存储人 的名字和对应的电话号码，或者说依赖于名 字和其电话号码的结构。l 数据的结构，直接影响算法的选择和效 率。l 上述的问题是一种数据结构问题。可将 名字和对应的电话号码设计成：二维数组、 表结构、向量。假定名字和其电话号码逻辑上已安排成N 元向量的形式，它的每个元素是一个数对(ai ，bi)， 1in 数据结构还要提供每种结构类型所定义 的各种运算的算法。例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题P3通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结

4、构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。l 1.2 基本概念和术语l数据(Data):是对信息的一种符号表示。在计 算机科学中是指所有能输入到计算机中并被 计算机程序处理的符号的总称。l数据元素(Data Element):是数据的基本单位 ，在计算机程序中通常作为一个整体进行考 虑和处理。l 一个数据元素可由若干个数据项组成。数 据项是数据的不可分割的最小单位。l数据对象(Data Object)：是性质相同的数据 元素的集合。是数据的一个子集。l数据结构(Data Structure)：是相互之间存在 一种或多种特

5、定关系的数据元素的集合。l数据结构主要指逻辑结构和物理结构l 数据之间的相互关系称为逻辑结构。通常 分为四类基本结构：l一、集合 结构中的数据元素除了同属于一 种类型外，别无其它关系。l二、线性结构 结构中的数据元素之间存在 一对一的关系。l三、树型结构 结构中的数据元素之间存 在一对多的关系。l四、图状结构或网状结构 结构中的数据元 素之间存在多对多的关系。l 数据结构的形式定义为：数据结构是一个二 元组：Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系 的有限集。l例 复数的数据结构定义如下：l Complex=(C，R)l其中：C是含两个实数的集合C1，

6、C2， 分别表示复数的实部和虚部。R=P，P是定 义在集合上的一种关系C1，C2。l数据结构在计算机中的表示称为数据的物理 结构，又称为存储结构。l 数据对象可以是有限的，也可以是无限的 。l 数据结构不同于数据类型，也不同于数据 对象，它不仅要描述数据类型的数据对象， 而且要描述数据对象各元素之间的相互关系 。l抽象数据类型：一个数学模型以及定义在该 模型上的一组操作。l 抽象数据类型实际上就是对该数据结构 的定义。因为它定义了一个数据的逻辑结构 以及在此结构上的一组算法。l 用三元组描述如下：l （，）l数据结构在计算机中有两种不同的表示方法 ：l 顺序表示和非顺序表示l由此得出两种不同的

7、存储结构：顺序存储 结构和链式存储结构l顺序存储结构:用数据元素在存储器中的相 对位置来表示数据元素之间的逻辑关系。l链式存储结构：在每一个数据元素中增加 一个存放地址的指针（ ），用此指针来表示 数据元素之间的逻辑关系。l数据类型：在一种程序设计语言中，变量所 具有的数据种类。l例1、 在FORTRAN语言中，变量的数据类型 有整型、实型、和复数型 l例2、在C语言中l数据类型：基本类型和构造类型l基本类型：整型、浮点型、字符型l构造类型：数组、结构、联合、指针、枚举 型、自定义l数据对象：某种数据类型元素的集合。l例3、整数的数据对象是-3，-2，-1，0，1 ，2，3，l英文字符类型的数

8、据对象是A，B，C，D， E，F，l 1.3 抽象数据类型的表示和实现lP11l 1.4 算法和算法分析l算法：是对特定问题求解步骤的一种描述l 算法是指令的有限序列，其中每一条指 令表示一个或多个操作。l 算法具有以下五个特性：l（1）有穷性 一个算法必须总是在执行有穷 步之后结束，且每一步都在有穷时间内完成 。l（2）确定性 算法中每一条指令必须有确切 的含义。不存在二义性。且算法只有一个入 口和一个出口。l（3）可行性 一个算法是可行的。即算法描 述的操作都是可以通过已经实现的基本运算 执行有限次来实现的。l4）输入 一个算法有零个或多个输入，这些 输入取自于某个特定的对象集合。l5）输

9、出 一个算法有一个或多个输出，这些 输出是同输入有着某些特定关系的量。l1.4.2 算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性(Correctness ) 算法应满足具体问 题的需求。l(2)可读性(Readability) 算法应该好读。以有 利于阅读者对程序的理解。(3)健状性(Robustness) 算法应具有容错处理 。当输入非法数据时，算法应对其作出反应 ，而不是产年莫名其妙的输出结果。l(4)效率与存储量需求 效率指的是算法执行 的时间；存储量需求指算法执行过程中所需 要的最大存储空间。一般，这两者与问题的 规模有关。l1.4.3 算法效率的度量l 对一个算法

10、要作出全面的分析可分成两用 人才个阶段进行，即事先分析和事后测试l事先分析 求出该算法的一个时间界限函数l事后测试 收集此算法的执行时间和实际占 用空间的统计资料。l定义：如果存在两个正常数c和n0，对于所有 的nn0，有f(n) cg(n) l则记作 f(n)=O(g(n) 一般情况下，算法中基本操作重复执行的 次数是问题规模n的某个函数，算法的 时间量度记作T(n)=O(f(n)称作算法的渐近时间复杂度。 例、for(I=1，I1 - I)l l change=false;l for(j=0;jaj+1) l aj aj+1;l change=TUREl l 最好情况：0次l l l最坏情

11、况：1+2+3+n-1l =n(n-1)/2l 平均时间复杂度为:O(n2)l1.4.4算法的存储空间需求l空间复杂度:算法所需存储空间的度量 ，记作:l S(n)=O(f(n) l其中n为问题的规模(或大小)第二章 线性表l2.1 线性表的类型定义l2.2 线性表的顺序表示和实现l2.3 线性表的链式表示和实现l 2.3.1 线性链表2.3.2 循环链表2.3.3 双向链表2.4 一元多项式的表示及相加l2.1 线性表的逻辑结构l线性表(Linear List) ：由n(n)个数据元素(结 点)a1，a2， an组成的有限序列。其中数据 元素的个数n定义为表的长度。当n=0时称为 空表，常常

12、将非空的线性表(n0)记作：l (a1，a2，an) l这里的数据元素ai(1in)只是一个抽象的符 号，其具体含义在不同的情况下可以不同。l例1、26个英文字母组成的字母表l （A，B，C、Z）l例2、某校从1978年到1983年各种型号的计算 机拥有量的变化情况。l （6，17，28，50，92，188）例3、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 . .l例4、一副扑克的点数l （2，3，4，J，Q，K，A）从以上例子可看出线性表的

13、逻辑特征是：在非空的线性表，有且仅有一个开始结点a1 ，它没有直接前趋，而仅有一个直接后继a2 ；有且仅有一个终端结点an，它没有直接后继 ，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个 直接前趋a i-1和一个直接后继a i+1。线性表是一种典型的线性结构。l数据的运算是定义在逻辑结构上的，而运算 的具体实现则是在存储结构上进行的。l抽象数据类型的定义为：P19算法2.1l例2-1 利用两个线性表LA和LB分别表示两个 集合A和B，现要求一个新的集合A=AB。void union(List Lb-len=listlength(Lb);for(I=1;Il.le

14、ngth+1)l printf(“Position error”);l return ERRORl l if(l.length=ListSize)l printf(“overflow”);l exit(overflow);l for(j=l.length-1;j=I-1;j-)l l.dataj+1=l.dataj;l l.dataI-1=x;l l.length+;ll 现在分析算法的复杂度。l 这里的问题规模是表的长度，设它的 值为。该算法的时间主要化费在循环的 结点后移语句上，该语句的执行次数（ 即移动结点的次数）是。由此可看出， 所需移动结点的次数不仅依赖于表的长 度，而且还与插入位置有关。l当时，由于循环变量的终值大于初值， 结点后移语句将不进行；这是最好情况 ，其时间复杂度O（1）；l当=1时，结点后移语句将循环执行n次 ，需移动表中所有结点，这是最坏情况 ，l其时间复杂度为O（n）。l 由于插入可能在表中任何位置上进行， 因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一 个结点，令Eis(n)表