数据结构教程

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

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

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

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

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

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

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

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

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

9、.4.2 算法设计的要求l评价一个好的算法有以下几个标准:l(1) 正确性(Correctness )算法应满足具体问题 的需求。l(2)可读性(Readability)算法应该好读。以有利 于阅读者对程序的理解。l(3)健状性(Robustness)算法应具有容错处理。 当输入非法数据时，算法应对其作出反应， 而不是产年莫名其妙的输出结果。l(4)效率与存储量需求 效率指的是算法执行 的时间；存储量需求指算法执行过程中所需 要的最大存储空间。一般，这两者与问题的 规模有关。 1.4.3 算法效率的度量l对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事先分析和事后测试l事先分析 求出

10、该算法的一个时间界限函数l事后测试 收集此算法的执行时间和实际占 用空间的统计资料。l定义：如果存在两个正常数c和n0，对于所有 的nn0，有f(n) cg(n) 则记作 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最坏情况：1+2+3+n-1=n(n-1)/2l平均时间复杂度为:O(n2)l1.4.4算

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

12、象的符 号，其具体含义在不同的情况下可以不同。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）从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有 直接前趋，而仅有一个直接后继a2；

13、有且仅有一个终端结点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.length+1)printf(“Position error”);return ERRORif(l.

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

15、次 ，需移动表中所有结点，这是最坏情况 ，l其时间复杂度为O（n）。l由于插入可能在表中任何位置上进行，因此 需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一 个结点，令Eis(n)表示移动结点的期望值（即 移动的平均次数），则在第i个位置上插入一 个结点的移动次数为n-I+1。故Eis(n)= pi(n-I+1)不失一般性，假设在表中任何位置 (1in+1)上插入结点的机会是均等的，则p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，Eis(n)= (n-I+1)/(n+1)=n/2也就是说，在顺序表上做插入运算，平均要 移动表上一半结点。当表长 n较大时，算法 的效率相当低。虽然Eis(n)中n的的系数较小 ，但就数量级而言，它仍然是线性阶的。因 此算法的平均时间复杂度为O(n)。2、删除线性表的删除运算是指将表的第 i(1in)结点删除，使长度为n的线性 表： (a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表(a1，