计算机基础 C语言 数据结构

第3章算法与数据结构

3.1计算机的问题求解模型

3.2C语言基础

3.3算法与数据结构的基本概念

3.4线性结构

3.5多维数组和广义表

3.6树

37图

3.8查找

3.9排序

3.10文件

3.1计算机的问题求解模型

本节内容：

•3.1.1计算机求解问题的过程

•3.1.2求解过程的概化一一算法

•3.1.3求解过程的实现一一程序

3JJ计算机求解问题的过程

有人认为计算机是万能的，只要把任务交给计算机，

计算机就会自动完成一切，并且给出正确结果，其实这是

一料误解。

计算机对问题的解决，实际上只是按照人们所指定的

操作步骤工作的°

小久人们拿到一个计算任务，到得到正确的结果，要经

过下述的几个阶段的工作，其中的任何阶段出现问题，都

会影响到结果的正确性。

(1)分析问题

(2)确定处理方案

(3)设计处理步骤和数据结构

(4)编写程序代码

(5)调试程序和结果检验

(6)整理结果

3.1.2求解过程的概化一一算法

当数据处理方案确定以后，算法的选择和设计是问题求解中很重要的一

止

o

所谓算法，就是问题求解的步骤设计。

(1)算法的选择：

一个问题的求解，往往有多种方法。不同的方法之间，从处理的效率、

结果的精度到程序设计人员的工作量、数学模型的难易程序都有很大的差

另I」。这时就要权衡利弊得失，选择一种最为满意的算法。

(2)对算法的描述：

可以选择自然语言、流程图、N—S图等多种方法描述算法。在算法

的描述过程中应该注意以下几点：

(a)按问题的处理前后顺序描述。

(b)描述要简明、准确，不能存在二义性的描述。

(c)在详细的算法描述中，要充分考虑到任何处理细节。

(d)要考虑到问题处理过程中任何可能发生的情况。

(e)算法中的运算和处理应能够在有限的时间内结束。

⑴对于采用模块化设计。模块的划分采用从上向下的顺

序遂步细化。

3.1.2求解过程的概化一一算法

下面看一个求解一元二次方程的根的算法设计过程:

⑴通过自然语言描述算法如下：

(a)输入方程的系数a、b和c；

(b)计算d=b2-4ac；

(c)如果d小于0,转(g)；

(d)计算两个实根

x1=(-b+sqrt(d))/(2a)^nx2=(-b+sqrt(d))/(2a)；

(e)输出两个实成x1和x2；

⑴转⑴；

(g)计算两个复根的实部u=・b/(2a)

和虚部v=sqrt(・d)/(2a)；

(h)输出两个复根x1=u+vi和x2=u-vi；

(i)停止程序执行。

3.1.2求解过程的概化一一算法

(2)通过流程图描述算法如下:

停机

3.1.3求解过程的实现一一程序

算法的实现只是问题解决的一个步骤，将算法用程

序代码描述出来，并且输入到计算机中，让计算机按照

设计好的程序完成指定的工作并且得到我们想要的结果,

才是我们的目的之所在。

程序（Program）是指用某一种计算机语言编写的计

算机可以直接或间接执行的代码序列。

如何才能将算法转换成计算机可能执行的程序呢？

1.计算机语言的分类和执行方式

2.如何用计算机语言描述算法

3.程序的调试与修改

3.1.3求解过程的实现一一程序

1.计算机语言的分类和执行方式

使用某一种语言编程时，这种语言的支持软件、编译程

序或解释程序、内部库函数、用户支持环境、各种设计工具

以及与编程和程序运行有关的软件，就构成了这种语言的程

序设计环境。

程序设计语言可以分为以下三类：

(1)机器语言

机器语言(Machinelanguage)是一种面向计算机的

程序设计语言，用它所设计的程年是一系列的指令。

计算机的CPU可以直接执行机器语言程序，这种程序称

为目标程序(Objectprogram)。

目标程序手工编写非常因难，需要编程者熟悉CPU的指

令系统，熟悉CPU的内部结构。另外，机器语言作为面向机

器的语言，卷不同类型的处理器之间差别很大，即机器语言

程序的可移楂性较差。

机器语言程序直接用二进制代码组成(书写时常采用十

六进制)，目前很少人工编写，而是由高级语言程序通过软

件生成机器语言程序。

3.1.3求解过程的实现一一程序

(2)汇编语言

汇编语言(Assembly工骗g“瑜列.是一种接近机器语言的

符号语言。它将机器语言的指金用便于人们记忆的符号来

表示，通过这种语言系统所带的翻译程序翻译成目标程序

后再执行。汇编程序执行效率很高。目前在实时控制等方

面的编程中仍有不少应用。

汇编语言程序示例：

汇编语言程序机器语言程序

0100MQVDL,010100B201

0102MOVAH,020102B402

0104M210104CD21

0106IW200106CD20

指令地址指令名操作数

3.1.3求解过程的实现一一程序

编汇语言程序的执行方式：

3.1.3求解过程的实现一一程序

(3)高级语言

高级语言(High-levellanguage)是一种完全符

号化的语言，其中采用自然语言(英语)中的词汇

利语法习惯，容易为人们理解和掌握；它完全独立

于具体的计算机，具有很强的可移植性。

用高级语言编写的程序称为源程序(Source

program),源程序不能在计算机直接执行，必须

将它翻译或解释成目标程序后，才能为计算机所理

解和执行。

3.1.3求解过程的实现一一程序

高级语言程序的两种执行方式：

解释方式：编译方式:

编

译

程

序编译、连接

、

连

接执行

程

序

3.1.3求解过程的实现一一程序

2.如何用计算机语言描述算法

在通过算法编写程序代码时，应注意以下问题：

1.熟悉所要使用的计算机语言。

2.熟悉算法中所使用的模型与模型所适用的环境与条

件。

3.根据算法中每一步的要求选择适当的语句和语句参数。

4.选择和设计合适的数据结构。

5.采用模块化设计，算法中的模块和程序中的模块相一

致。

6.为了增加程序的可读性，应增加必要的注释文字。

3.1.3求解过程的实现一一程序

例如，前面求解一元二次方程的算法，可以写出如下的C语

言程序：

#include<stdio.h>

#include<math.h>

main()

(

floata,b,c,d,x1,x2;

scanf(”％f,%f,%f”,&a,&b,&c);

d=b*b-4*a*c;

if(d>=0.0)

{

x1=(-b+sqrt(d))/(2*a);x2=(-b-sqrt(d))/(2*a);

printf("x1=%f\n,,,x1);printf(,'x2=%f\n",x2);

)

else

(

x1=-b/(2*a);x2=sqrt(-d)/(2*a);

printfC^I=%f+i*%f\n,,,x1,x2);printf(,,x2=%f-i*%An,,,x1,x2);

}

)

3.1.3求解过程的实现一一程序

3.程序的调试与修改

在程序的试运行中，可能会出现各种错误，这些错误可以分为以下几种：

(1)编译错误：

在程序的编译阶段发生的错误，一般是保留字的拼写不正确，或者语句不符合本语言的规则

等，发生此类错误时一般会停止编辑工作。比较容易查到出错原因。

⑵连接错误：

在连接各子程序和库函数时发生的错误，一般是程序模块的调用不对一，如形式参数

和实际参数不一致，程序调用库函数时错误(如参数不对、函数不存在等)。这类错

误查错时检查相关的函数，也可以较快地解决。

(3)警告性错误：

编译中发生这类错误时，不影响后面的工作，但是程序运行时可能会发生问题。

(4)运行错误：

编译、连接工作都顺利完成，但是目标程序运行时出现问题如出现数据溢出的错误、

负数开平方的错误、数组使用超界寸寸O这种情况要具体分析出错的原因和出错的位

置，从算法、程序、数据不同的方面着手，必要时输出部分中间结果，逐步分析出出

错的真正原因。

(5)计算结果不正确。程序可以顺利地完成运行，但是输出结果经验证不正确，或者

耳果的精度达不到应有的精度。这类错误最难查找，应从任务的各人阶段分析，如数

学模型中是否存在问题？有无漏洞？数据(包括数据的结构)是否正确是否正确？表

达式的书写有无错误？程序代码有无错误？等等。必要时应在程序中增加大量输出中

间结果的语句，以最终查到错误的原因所在。

程序的调试是一个繁杂的反复过程，需要编程者大量艰苦的工作，程序的通过就

是这样在“运行一一查错一一排错一一再运行一一”的过程中逐步通过。

3.2C语言基础

•本节内容：

•3.2.1C语言程序结构

•3.2・2C语言基本符号

•3.2.3数据和数据类型

•3・2.4运算符、表达式、赋值运算和赋值表达式

•3.2.5赋值语句和输入输出

•3・2.6分支语句

•327循环控制语句

•3.2.8函数

•3.2.9预处理指令

・3210文件操作

3.3算法与数据结构的基本概念

本节内容：

3.3.1概念和术语

3.3.2数据的逻辑结构

3.3.3数据的存储结构

3.3.4算法分析与设计

3.3.1概念和术语

1.数据

2信息

3,数据类型

4.数据结构

5.算法

3.3.1概念和术语

数据

数据是对客观事物的符号表示，他是一

组表示数量、行动和目标的非随机的可鉴

别的符号。它可以是数字、字母等符号。

在计算机中，数据通常是指一切可以输入

到计算机中并能被计算机程序处理的所有

符号的总称。在计算机科学中，通过数据

编码技术，文本、声音、图形、图像都可

以编码成计算机可处理的数据。

3.3.1概念和术语

信息

信息和数据是一个经常容易引起混淆的概念，

从信息论的角度讲，信息是加工后的数据，他对

接收者的行为产生影响，对接收者的决策具有价

值。如某城市的气侯情况（如海口12月份的气温

一般在20度左右），对于要到该城市的人来说就

表现为信息，它可能直接影响是否要到该城市来

以及作何种准备（如：准备什么样的衣服）的决

策。对于当地人来讲，12月份20度的气温更多地

表现为数据。在计算机应用中，信息和数据常是

等同的。

3.3.1概念和术语

数据类型

数据类型是程序设计中的概念，程序中的数

据都属于某个特殊的数据类型。数据类型决定了

数据的性质，如数据的取值范围、操作运算等。

常用的数据类型有整数类型、实数类型、字符类

型、布尔类型（逻辑类型）等。

数据类型还决定了数据在内存中占据的空间

的大小，不同类型的数据在不同的操作系统下占

用的内存大小不同。例如，整数类型数据在

Windows9x中一般占两个字节的空间。

3.3.1概念和术语

数据结构

数据结构是在整个计算机科学与技术领域上

广泛被使用的术语。它用来反映一个数据的内部

构成，即一个数据由那些成分数据构成，以什么

方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数

据结构之分。逻辑上的数据结构反映成分数据之

间的逻辑关系，而物理上的数据结构反映成分数

据在计章机A部的存储安排。

数据结构是数据存在的形式。数据结构是信

息的一种组织方式，其目的是为了提高算法的效

率，它通常与一组算法的集合相对应，通过这组

算法集合可以对数据结构中的数据进行某种操作。

3.3.1概念和术语一一数据结构

数据结构是在整个计算机科学与技术领域上广泛数据结

构作为一门学科主要研究数据的各种逻辑结构和存储结构，

以及对数据的各种操作。

主要有三个方面的内容：数据的逻辑结构；

数据的物理存储结构；

对数据的操作（或算法）。

通常，算法的设计取决于数据的逻辑结构，算法的实现

取决于数据的物理存储结构。

数据结构反映数据内部的构成方式，它常常用一个结构

图来描述:数据中的每一项成分数据被看作一个结点，并用方

框或圆圈表示，成分数据之间的关系用相应的结点之间带箭

号的连线表示。如果成分数据本身又有它自身的结构，则结

构出现嵌套。这里嵌套还允许是递归的嵌套。

3.3.1概念和术语一一数据结构

由于指针数据的引入，使构造各种复杂的数据

结构成为可能。

按数据结构中的成分数据之间的关系，数据结

构有线性与非线性之分。

在非线性数据结构中又有层次与网状之分。

由于数据类型是按照数据结构划分的，因此，

一类数据结构对应着一种数据类型。数据类型按照

该类型中的数据所呈现的结构也有线性与非线性之

分，层次与网状之分。一个数据变量，在高级语言

中的类型说明必须是读变量所具有的数据结构所对

应的数据类型。

3.3.1概念和术语---数据结构

最常用的数据结构是数组结构和记录结构。

数组结构的特点是：

1.成分数据的个数固定，它们之间的逻辑关系由成分

数据的序号（或叫数组的下标）来体现。这些成分数据

按照序号的先后顺序一个挨一个地排列起来。

2•每一个成分数据具有相同的结构（可以是简单结构，

■一

也可以是复杂结构），因而属于同口一个数据类型（相应

地是简单数据类型或构造数据类型）。这种同一招数

据类型称为基类型。

3,所有的成分数据被依序安排在一片连续的存储单元

甲O

°概括起来，数组结构是一人线性的、均匀的、其成分数

据可随机访问的结构。由于这种结构有这些良好的特性，所

以最雀被人们所采用。在高级语言中，与藜组结构相对应的

数据美型是数组尖型，即数组结曷的数据斐量必须说明为V

类型名〉数组名[i],其中i是数组结构的下标类型。

3.3.1概念和术语一一数据结构

记录结构是另一种常用的数据结构。它的特点是：

1.与数组结构一样，成分数据的个数固定。但成分数

据之间没有自然序，它们处于平等地位。每一个成

分数据被称为一个域并赋予域名。不同的域有不同

的域名。

2.不同的域允许有不同的结构，因而允许属于不同的

数据类型。

3,与数组结构一样，它们可以随机访问，但访问的途

径靠的是域名。

3.3.1概念和术语

算法

算法是在有限步骤内求解某一问题所使用的一组定义明

确的规则。通俗点说，就是计算机解题的过程。在这个过程

中，无论是形成解题思路还是编写程序，都是在实施某种算

法。前者是推理实现的算法，后者是操作实现的算法。

一个算法应该具有以下五个重要的特征：

1.有穷性：一个算法必须保证执行有限步之后结束；

2.确切性：算法的每一步骤必须有确切的定义；

3.输入：一个算法有0个或多个输入，以刻画运算对象的初

始情况，所谓。个输入是指算法本身定除了初始条件；

4.输出：一个算法有一个或多个输出，以反映对输入数据加

工后的结果。没有输出的算法是毫无意义的；

5.可行性：算法原则上能够精确地运行，而且人们用笔和纸

做有限次运算后即可完成,

3.3.2数据的逻辑结构

数据结构描述了数据以及数据之间的逻辑关系，数据之间的逻辑关系

称为数据的逻辑结构。

数据的逻辑结构一般分成四种类型：

(1)集合

数褊W素的关系非常松散，他只描述数据元素是否同在一个集合中。例如：

20以内的素数

(2)线性结构

数据元素之间存在线性关系，每个元素都有一个惟一的前导元素和一个惟

的后继元素，第一个元素没有前导，最后一个元素没有后继。例如：

DataDataData

3.3.2数据的逻辑结构

（3）树形结构

数据元素之间呈现层次关系，在树形结构中，每一个元

素通常称为一个节点，每个节点（根节点除外）有一个父节点,

一个节点可以有多个子节点。

4）图状结构

元素呈多对多的关系，在图状结构中每个元素称为一个节点，图状结

构又称网状结构。例如:c3

1—^2)

el%e5

66

34

3.3.3数据的存储结构

研究数据结构的目的是要在计算机中实现对数据的操作，

要实现对数据的操作必须将数据在计算机中表示。对数据不

同的存储，对数据操作的实现将不相同。

我们把对数据结构在计算机中的表示称为数据的存储结

构，又称物理结构。存储结构不但要表示数据，还必须表示

出数据的逻辑结构。

在计算机中，数据都转换为二进制串来进行存储，不同

类型的数据占用的存储空间不同。

数据之间的关系在计算机的表示一般分成顺序存储和链式

存储两种。

在顺序存储中，借助于数据在存储器中的相对位置表示数

据之间的关系，例如:用数组来存储一个线性结构数据对象。

在链式存储中，每个数据元素存储为一个节点，每个节点有

一个或多个指针，指向其他的节点，指针表示了节点（数据

元素）之间的关系

3.3.3数据的存储结构

1,顺序存储结构的特点

在计算机中，所谓顺序存储是指用一组地址连续的存储单

元依次存储数据集合中的元素。

顺序存储结构非常适合存储线性表，例如：设线性表中每个

元素占用I个存储单元，线性表的第一个元素存储位置为

LOC(a0),则第i个元素的存储位置为：

LOC(aj)=LOC(ao)+(i-1)*l

存储位置表示了元素之间的关系，这样可以使得该数据结构

下的许多算法容易实现，并且效率较高。

顺序存储结构虽然可以用元素的存储位置表示元素之间的

关系，但是如果元素集合很大，顺序存储要求一块很大的连续

的内存空间，这在操作系统的存储管理上可能无法满足。

(顺序表)

3.3.3数据的存储结构

2.链式存储结构的特点

链式存储最大的特点是无法用元素的存储位置表示元素之

间的关系，它需要增加指针，通过指针表示元素之间的关系。

利用指针表达元素之间的关系，增加了数据结构的存储空

间要求。另外，对元素的许多操作算法，在实现上也变得较为

麻烦，效率较低。

但是，链式存储大大的增加了数据结构的灵活性，对于有

些数据结构，链式存储比顺序存储更好。

（单链表）

334算法分析与设计

在数据结构中，对数据的操作往往用算法来描述。所谓

算法(Algorithm)，就是指对特定问题求解过程的描述，他由

一系列的籍令组成，每个指令表示一个或多个操作。

算法具有五个重要的特性：

(1)有穷性：一个算法必须在执行有穷步后结束，每一步必

须在有穷的时间内完成。

(2)确定性：算法中的每一条指令必须有确定的含义，不能

产生二叉牲。

(3)可行，应：算法描述的步骤在计算机上是可行的

(4)输入：一个算法可以有零个或多个输入，这个取决于算

法要实现的功能。

(5)输出：一个算法执行过程中或结束后要有输出结果，或

者产生相应的动作指令。

所谓算法分析，就是对设计的算法进行正确性、时间复杂性

和空间复杂性的分析，从而来评价算法的优劣，或估计算法

实现后的运行效果。

3.3.4算法分析与设计

1.算法的正确性

算法设计首先要保证其正确性，只有在保证算法正确性的前提下，才可以讨论算

法的好坏。为了方便对算法正确性的描述，假设设计一个求三角形面积的算法，三

角形的三条边分别为a,b,c,面积表示为area,如果求面积的算法简单的设计为：

•steplread(a,b,c)

•step2s:=(a+b+c)/2

•step3area=s*sqrt(s*(s-a)*(s-b)*(s-c))

•step4write(area)

该算法正确性的描述可以分成下面几个层次：

(1)对于一组数据能够得出正确的结果，该算法没有考虑三角形中两边之和大于第

三边的基本数学原理，因此如果输入的三条边可以构成一个三角形，则该算法是正

确的。

(2)对于精心挑选的、苛刻的测试用例算法可以得到正确的结果。在某些情况下，

上述求三角形面积的算法就不正确了，如当输入的三条边包含负数或者有一条边大

于另外两条边的长度之和时，上述算法将得到错误的结果。

(3)对于一切合法的输入数据，算法得到的结果都是正确的。这是一种理想的情况,

随着算法求解问题复杂度的增加，一个算法在不同的输入数据下会有大量不同的执

行路径，因此要验证算法的完全正确是很困难的。我们只能精心设计测试用例，用

较少的数据去发现更多的错误，然后进行修改，以期达到算法最大程度上的正确性。

3.3.4算法分析与设计

2.时间复杂性分析

一般情况下，一个算法中基本操作重复执行的次数与求解问题的规模

(问题长度)n呈某个函数关系f(n),记作：

T(n)=O(f(n))

我们把T(n)称为算法的时间复杂度。如果算法的执行时间与问题的长度

无关，则该算法的时间复杂度记为0(1),表示常数时间复杂度。

例如:求长度为n的数组a［的n］中，中间一个元素的值a［n⑵,时间消耗与问

题长度n无关。

算法的实现即程序，一般有三种结构：顺序结构、分支结构和重复结构。

三种结构中语句的执行次数构成算法的时间消耗。

23

常用的算法时间复杂度有下述几种。(n)、o(nlog2n)>o(n)>o(n)>

。(2。，假设计算机执行一次基本操作需要的时间为1ms,五种算法时间复杂

度与求解问题的长度关系见表3・7。

3.3.4算法分析与设计

表37算法时间复杂度与求解问题的长度关系

可解问题最大长度（n）

算法时间复杂度1秒1分钟1小时

A1。⑻1000600003.6*106

A2o(nlog2n)14048932.0*105

A3o(n2)312401987

A4o(n3)1033153

A5。⑶91521

在上述表格中，可解问题的最大长度是指在某个时间内n的值。例如对于算法

A2,1秒钟可以解决的问题长度为n,又因为计算机执行一次基本操作需要的时

间为1ms,因止匕有nlog2n=1000,可以计算得到2140。

3.3.4算法分析与设计

可见，时间复杂度越大，在时间消耗的增加带来的求解问题长度的增加会变慢。

卜面我们看计算机速度的提高对不同算法求解问题长度带来的影响，见表3-8。

表3-8计算机速度对求解问题长度的影响

可解问题最大长度（n）

算法时间复杂度计算机速度提高前计算机速度提高10倍

A1o(n)S110s1

A2o(nlog2n)S210s2

A3o(n2)S33.16s3

A4o(n3)S42.15s4

A5o(2n)s5S5+3.3

3.3.4算法分析与设计

3.空间复杂性

算法的空间复杂度是指算法运行中对存储空间的需求，记作：

S(n)=O(f(n))

其中，n表示问题的规模(问题长度)。一个算法对应的程序在执行时

候必须加载到计算机的内存中，程序本身、程序中用到的变量都要占用内

存空间，除了这些内存消耗外，程序在执行过程中还要用到临时变量、还

可能动态的申请额外的内存空间。

分析一个算法的时间复杂度，除了考察数据所占用的空间外，应该分析

可能用到得额外空间。随着计算机存储器容量的增加，人们对算法空间复

杂度的分析的重视程度要小于时间复杂度的分析。

3.4线性结构

在四种数据结构中，线性结构是较为简单、但又是用

非常广泛的结构，线性结构具有如下特点：

(D存在一个惟一的称为“第一个”的数据元素，存在一

个惟一的称为“最后一个”数据元素；

(2)除了“第一个"元素以外，集合中的每一个元素都有

一个惟一的前导元素，第一个元素没有前导；除“最后一

个”数据元素外，每一个元素都有一个惟一的后继元素，

最后一个元素没有后继。

本节内容：

3A1线性表

3.4.2堆栈

3.4.3队列

3.4・4史

3.4.1线性表

线性表(linearlist)是一个具有n(n>0)个数据元素的

有序序列。在不同的应用情况下，数据元素的含义不同，它可

以是一个数、字符或一个对象。

线性表的形式定义如下：

linearjist=(D,R)

其中，D={aj|ai€D0,i=1,2,...,n,n>0}；

R={N},N={vaM问〉|aj.l5ai€D0,i=2,3,...,n,n>0}。

Do为性质相同的数据元素的集合。关系R是有序偶的集合，

它表示元素集中数据元素之间的相邻关系，元素ag,是aj的前导,

a.是凡1的后继。线性表中数据元素的个数n称为线性表的长度。

n=0时，线性表称为空表。

n>0时，线性标记作：(a1，a2,…，an)

3.4.1线性表

1.线性表的基本操作

线性表是一个非常灵活的结构，对线性表的常用操作包括:

1)Length(L)：求线性表的长度函数，返回线性表中数据元素的个数。

2)Get(L,i)：取元素函数，返回线性表L的第i个数据元素的值，OvivLength(L)。

3)Locate(L,x)：定位函数，给定值x,判断线性表中是否有和x值相等的元素。

如果存在，返回第一个和x相等的元素在线性表中的位序，否则，返回0。

4)Prior(L,e):前导函数，返回线性表L中元素e的前导元素。如果e为第一个元素，返回

空。

5)Next(L,e)：后继函数，返回线性表L中元素e的后继元素。如果e为最后一个元素，返

回空。

6)lnsert(L,i,e)：插入操作，在线性表L的第i个元素的前面插入一个元素e。成功插入后,

线性表的长度加一。

例如：插入前的线性表为二L二…af,aj,…a°)。则执行插入操作后线性表L变为:

L=⑸生,…a*,e,a”...an),兀素a2和aj之同的油邻关系被改变。

7)Delete(L,i)：删除操作，将线性表L的第i个元素删除。

例如：删除前的线性表为：L之(叫闰小…aM，a“a唱…a。二。则执行删除操作后线性表L变

为：L=(a1)a2,...aj.1,aj+1,...an),兀素a^,和aj+i成为相邻的兀素，线，隹表的长度减一。

3.4.1线性表

2,线性表的存储结构

在任何逻辑结构上定义的操作算法，必须在特定的存储结构下才能够实

现。存储结构必须将逻辑结构中的数据和数据之间的关系表示出来。

1)线性表的顺序存储结构

顺序结构通过元素之间的物理存储位置表示了线性表中元素之间的关系,

对线性表中的数据元素可以随机存取。这使得线性表的许多操作变得简单和

高效。如：取元素函数Get(L,i)在实现上将只需要一个函数返回语句，而无

需数据结构的遍厉过程。

线性表的顺序存储结构可以用数组来表示，用C语言描述如下：

#defineMAXSIZE100〃设线性表的最大长度为100

typedeffloatElementType;//ElementType为元素类型，为了操作方便，假设为实数

typedefstruct{

ElementTypeelements[MAXSIZE];〃元素数组

intlength;//线性表的实际长度

}SqList

在此结构下可以进行线性表的各种操作运算。

顺序表的实现.

3.4.1线性表

2）线性表的链式存储结构

线性表可以采用单链表结构，定义如下

typedefstructNode{

ElementTypedata;

structNode*next;

}Node；

Node*SqListHead;

3.4.2栈

堆栈(stack)是一种限定只在表尾进行插入和删除操作的线性表，他

在递归算法、面向对象程序设计等许多方面有着重要应用。从数据结构的角

度讲，栈是一种操作受限的线性表，它的插入和删除只能在表的一端进行。

我们把以进行查入和删除操作的一端称为“栈顶”，另一端称为“栈尾”。

堆栈结构如图3・8所示。

图3-8堆栈操作示意图

1.栈的基本操作

栈是一种操作受限的线性表，对栈的操作主要包括：

(1)InitStack(S)：初始化操作，将栈s设为空。

(2)PUSH(S,x)：入栈操作，将元素x压入栈S,成为新的栈顶元素。

(3)POP(S)：出栈函数，S为堆栈，若S不为空，返回S的栈顶元素，

且从栈中删除该栈顶元素(退栈)。如果堆栈为空，则

函数返回值为NULL。

(4)GETTOP(S)：取栈顶元素函数，S为堆栈，若S不为空，返回S的

栈顶元素。如果堆栈为空，则函数返回值为NULL。

2.栈的存储结构

一般地，栈有两种实现方法：顺序实现和链接实现，这和线性表类似。

1）栈的顺序存储结构

栈的顺序存储结构称为顺序栈。

顺序栈通常由一个一维数组和一个记录栈顶位置的变量组成。因为栈的操作仅

在栈顶进行，栈底位置固定不变，所以可将栈底位置设置在数组两端的任意一个端

点上。习惯上将栈底放在数组下标小的那端。另外需使用一个变量top记录当前栈顶

下标值。即表示当前栈顶位置，通常称top为栈顶指针（注意它并非指针类型变量）

顺序栈类型定义如下：

#definesqstack_maxsize6/*顺序栈的容量*/

typedefstruct

{ElementTypedata[sqstack_maxsize];

inttop;

}sqstack;

顺序栈被定义为一个结构类型，它有两个域data和top。

data为一个一维数组，用于存储栈中元素，ElementType为栈元素的数据类型

（有待设定）。

top为int型，它的取值范围为-1,0..sqstackmaxsizeT。top二二一为表示栈空,

top二sqstackmaxsize-l表示栈满。

栈的基本运算在顺序栈上的实现

2）栈的链式存储结构

栈的链接实现是以某种形式的链表作为栈的存储结构，并在这种存储结构上实

现栈的基本运算。

栈的链式存储结构称为链栈，其组织形式与单链表类似。由于只在链栈的头部进

行操作，故链栈没有必要设置头结点。单链表的第一个结点就是链栈栈顶结点。Is称

为栈顶指旬，它相当于单链表的头指针。类似地，链栈由栈顶指针Is唯一确定。栈中

的其它结点通过它们的next域链接起来。栈底结点的next域为null。因链栈本身没有

容量限制，故在用户内存空间的范围内不会出现栈满情况。

链栈类型定义如下：

typedefstructnode

{ElementTypedata;

structnode*next;

}node；

node*LStackTp;

栈的基本运算在链栈上的实现

3.4.3队列

和堆栈不同，队列(queue)是一种先进先出(FirstInFirstOut,

FIFO)的线性表。只能在表的一端进行插入操作，在另一端进行删除操作。

允许插入的一端称为队尾(rear)，允许删除的一端称为队首(front)o

假设队列为q=(a1,a2,...an)，队列中的元素按照a1,a2,…an的顺序依次

进入队列，有按照相同的顺序依次从队列中删除。如图3-9所示。

出队列<----ai32...an<——入队列

队队

头尾

图3.9队列示意图

1.队列的基本操作

队列也是一种操作受限的线性表，对队列的操作主要包括：

(1)InitQueue(Q)：初始化操作，设置一个空的队列Q。

(2)EntQueue(Q,x)：入队操作，将元素x插入到队列Q的尾，成为对

列新的队尾元素。

(3)DelQueue(S)：出队列函数，Q为队列，若Q不为空，返回Q的队

首元素，且将队首元素从队列中删除。如果队列Q

为空，则函数返回值为NULL。

(4)GetHead(S)：取队首元素函数，Q为队列，若Q不为空，返回Q的

队首元素。如果队列为空，则函数返回值NULL。

(5)CurrentSize(Q)：队列大小函数，返回队列Q当前所包含的元素个

数。

2.队列的存储结构

与栈类似，队列通常有两种实现方法，即顺序实现和链接实现。

（1）队列的顺序存储结构

队列的顺序实现称为顺序队，它由一个一维数组（用于存储队列中元素）

及两个分别指示队头和队尾的变量组成，这两个变量分别称为“队头指针”

和“队尾指针”（注意它们并非指针型变量）。通常约定队尾指针指示队尾元

素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位

置的前一个位置，如图所示。

当前空闲区当前队列|当前空闲区1

---.■.一,—---

1ttn

队头队尾

图3-7顺序队列示意图

顺序队列的类型定义如下：

#definemaxsize20

typedefstruct

{ElementTypedata[maxsize];

intfront,rear;

}SqQueue;

顺序队定义为一个结构类型，它有三个域：data、front、rear。其中

data为存储队中元素的一维数组，队头指针front和队尾指针rear定义为整

型类型变量，取值范围是0..maxsize-1。

初看起来,入队操作可用sq.rear=sq.rear+1;data[sq.eear]=x实现.

出队操作可用一条语句实现sq.front=sq.front+1。但实际上这不是一个好

办法。___________________________________________________

(a)⑹(0)(4)⑥

图3-8顺序队的几种状态

在图3-8(e)的状态下，显然按上述方法不能再进行入队运算。但是在数

组的低端仍有空闲位置，亦即顺序队的存储空间并没有被占满。因此，这是

一种“假溢出”。为了充分利用存储空间，克服“假溢出”，可采用循环队

的办法。

把队列设想成一个循环表，

即设想数组的首尾相连：sq.data[O]接在sq.data[maxsize-1]之后。

这种存储结构称为循环队。当sq.「ear=maxsize-1时，只要数组的低下标

端有空闲空间，在循环队上仍可做入队运算。此时只需令sq.rear=O,即把

sq.data⑼作为新的队尾，并将入队元素置入此位置。这样就解决了“假溢

出”问题。循环队的示意图见图3-9。图中阴影部分为当前队列占用空间，

其余为当前空闲空乱

图3-9循环E人示意图

循环队上的入队操作：

sq.rear=(sq.rear+1)%maxsize;sq.data[sq.rear]=x;

出队操作：

sq.front=(sq.front+1)%maxsize;

循环队列的类型定义：

typedefstruct{

{ElementTypedata[maxsize];

intrear,front;

}Cycqueue;

Cycqueuesq;

接下来必须解决的一个问题是，循环队的队满和队空的条件是什么？也就是说,

如何判断一个循环队是满的或空的？

sq.rear==sq.front

解决方法:

1)约定循环队的队头指针指示队头元素在数组中实际位置，队尾指针指示

队尾元素在数组中的实际位置的后一个位置。其次，为简化判断，我们“牺牲

一个存储结点，即约定队头指针才日本的结点不用于存储队列元素，只起标志作

用。这样，当队尾指针“绕一圈”后赶上队头指针时，视为队满。

故队满条件为：

((sq.rear+1)%maxsize)==sq.front

相应地，队空条件为：

sq.rear==sq.front

队列的基本运算的实现

(n)队满示例(Q队空示例

2）增加一个计数器域

循环队列的类型定义：

typedefstruct{

{ElementTypedata[maxsize];

intrear,front;

intcount；

}Cycqueue;

Cycqueuesq;

队满条件为：

sq.count==maxsize

相应地，队空条件为：

sq.count==0

队列的基本运算的实现

(2)队列的链式存储结构

队列的链接存储结构称为链队，它实际上是一个同时带有

头指针和尾指针的单链表。头指针指向队头结点，尾指针指向

队尾结点即单链表的最后一个结点。

lq.front

nil|队尾

链队的类型定义如下：

Typedefstructnode

{ElementTypedata;

Structnode*next;

}Lqueuenode;（链队结点类型）

typedefstruct{

Lqueuenode*front,*rear;

}linkqueue;

链队在一定范围内不会出现队满的情况。

当lq.front==null或lq.rear==null时，队中无元素，此时队空。

队列的基本运算的实现

3.5多维数组与广义表

线性表中的数据元素往往属于相同的数据类

型，且一般是不可分割的原子项。若放宽对元素

性质的上述约束，线性表就扩展为多维数组或广

义表。

本节内容：

3.5.1多维数组及其存储

3.5.2矩阵的压缩存储

3.5.3广义表

3.5.2矩阵的压缩存储

般情况下，对于多维数组采用行优先或列优先的顺序为每一

寺寸殊情况下，这样白的存储会造

方大蕈的空间浪费,用的压缩方式来存稽。

1.特殊矩阵

特殊矩阵是指一些具有特定性质的矩阵，包括:

对称矩阵、下(上)三角矩阵、对角矩阵等。

1)对称矩阵的存储

若一个n阶矩阵A中元素满足性质：aij=aji,1<i,j<n,则称A为n阶对称矩阵。

在传统的存储策略下，每一个元素分配一个存储空间，需要/个存储空间。实际

上，我们可以只存储下三角(包括对角线)中的元素，对于其他的元素可以通过特定

的映射关系来从存储的元素中得到。

要保存下三角中的所有元素需要(M-n)/2+n=n(n+1)/2个存储空间，

假设我们用一个一维数组sa[1..n(n+1)/2]按照行优先的顺序来存储下三角中的每一个

元素，形式如下：

aaaaaa

112122313233■•■^n1■■■^nn

352矩阵的压缩存储

根据上述的存储结构，数组A中的每一个元素aij和一维数

组sa的下标k夕间的关系为：

「当月时

k=<.*

L吗L+i,当可时

对于数组sa中的任意一个元素sa[k],1<k<n(n+1)/2,其在

二维数组A中对应的元素为Aij。首先确定元素的行下标i,i应该

满足：1+2+…+rwk的最大的唯加1。如当k=4时,最大的r=2,

因为此时有1+2<k,则r=2,故行下标i=r+1=3。然后求列下标j,

j=k-i(i+1)/2o因此得出sa[4]中存储的是二维数组A中的第3行

第1列的元素

3.5.2矩阵的压缩存储

2.稀疏矩阵

稀疏矩阵是指含有大量0元素的矩阵。

•个mXn的矩阵A,在正常的情况下需要mxn个存储空间。如果A中含有大量的0元素，即

非零元素的个数k«mxn。此种情况下，我们可以采用压缩存储，即只保存非零元素的值，同

时还需要存储对应的行列坐标。因此需要3k个存储空间，如果kwmXn,则3kv〈mXn。止匕

时可以节省较大的存储空间。

1)三元组表

按照压缩存储的思想，对稀疏矩阵A,只存储每个非。元素的值aij及其行列坐标(i,j),记作三元

组形式(i,j,aij)。将三元组构成一个线性表，线性表采用顺序存储结构。结构定义如下：

#defineMAXSIZE=1000〃最多的可能的非0元素的个数

typedefint曰ementType;〃为了实现方便，设元素类型ElementType为int

typedefstruct{

inti,j;II行列坐标

ElementTypee;〃非。的元素值

}Triple;

typedefstruct{

introw,col,num;〃矩阵的行数和歹!j数及非。个数

Tripledata[MAXSIZE+1];

}SparsemMatrix;

352矩阵的压缩存储

例如，对于一个5行6列的稀疏矩阵A,包含5个非0元素，如图所示。在三元组存

储中，需要15+3共18个存储单元，比压缩存储前需要的30个存储单元要小。

矩阵越大（如800X600）,压缩的比例将越高。

0000160ijv

1516

0850000

2285

15000210

3115

000000

3521

07700005277

J

3.5.2矩阵的压缩存储

2）十字链表

用顺序存储结构存储稀疏矩阵可以有效的节省存储空间。缺点是，在非0元素增加和减少时，

插入和删除不便。为此，用称为“十字链表”的链式存储结构来存储。具体的结构是：

第一，对稀疏矩阵的每一行和每一列都建立一个具有头节点的循环链表，将该行中或该列中的所有

非0元素都连接起来。连接顺序为：在行链表中，按列的次序连接；在列链表中，按行的次序连

接。

第二，对每个非0元素建立一个节点，该节点即处于该元素所在行的行链表中，也处于该元素所在

列的列链表中。结点结构如E______________________

rowcolvalue

downright

其中，row、col和value分别为非零元素所在的行、列坐标和元素值，down和right为两个指针字

段，分别指向该列或该行中下一个非0元素对应的结点。

第三，每个行（列）链表的头结点的结构形式与非0元素结点相同，但节点含义不同。其中，

row=col=0（不用），down和right分别指向该列或该行中第一个非0元素对应的结点。value为

指针字段，指向下一个表头节点，即所有的表头节点构成一个循环链表。编号相同的行列链表公

用一个头节点。因此，表头结点的个数为max{m,n}。

第四，对所有的行（列）表头结点构成的链表建立一个头结点A,结构同上，具体含义是：row记录

矩阵的行数，col纪录矩阵的列数，down=right=0（不用），value为指针字段，指向第一个行

列表头结点。

3.5.2矩阵的压缩存储

H2学4RH6

56*--0I00000000000*

:1

Hl0°1516

2285

31153521

H3

亡

H4

5277

H5

3.6树

在线性表、堆栈、队列等线性结构中，元素之间的关系

是线性的，描述了元素之间的先后次序。但在大量的实际问

题中，对象之间的关系是错综复杂的。例如，人类社会的家

族族谱、各种社会组织机构、一本书的章节目录等等，它们

都无法用线性结构来描述。

在计算机科学中，树型结构是一类重要的非线性数据结

构，它可以很好的表达元素之间的层次关系。

本节内容：

3.6.1树的基本概念及存储结构

3.6.2二叉树

3.6.3常用操作及算法

3.6.1树的基本概念及存储结构

在计算机科学中，树结构是指元素间具有层次关系的非

线性结构，元素之间用分支来连接，非常类似于自然界中的树。

下面是树的严格定义：

树(tree)是n(n>0)个结点的有限集。在一棵非空树中：

(1)有且仅有一个特殊的结点，称为树根(root)；

(2)当n>1时，其余结点可分为m(m>0)个互不相交的有

限集T1,T2,…,Tm,且其中的每一个集合也是一棵树。

T1,T2,…,Tm称为根的子树。

上述树的定义是一个递归定义，递归是树的固有特性。

1A

2B

3E

4K

4L

3G

3H

4M

3I

3J

a）只包含根结点（b）一般的树（a）树的嵌套集合表示（b）树的凹入表示

图3-19一般的树型结构图3-20树型结构的其它表示形式

1.常用术语

树是由一系列的结点构成的，每个结点都包含一个数据元素及若干指向其子树的分支。

结点的度：任一结点V拥有的子树的个数称为结点的度（degree）,记作d（V）。

叶子（叶结点）：度为。的结点称为叶子（leaf）或终端结点。

分支结点：度不为。的结点称为非终端结点或分支结点。除根结点外，分支结点又称为

内部结点。

树的度：树中所有结点度的最大值称为树的度。

结点的层数（level）：树描述了数据的层次结构，从树的根开始，称为树的第一层，根

的孩子结点为第二层，以此类推。

树的深度：树种结点层数的最大值称为树的深度（depth）。

森林（forest）：是m（m>0）棵互不相交的树的集合。。

结点间的关系：

结点的子树的根称为该结点的孩子（child）,该结点称为孩子的双亲（parent）。

同一双亲的孩子结点称兄弟（sibling）。

双亲在同一层的结点互为堂兄弟。

结点的祖先是从根结点到该结点所经分支上的所有分支结点。

以某结点为根的所有的子树结点中的任一结点都成为该结点的子孙。

2.树的存储结构

树最自然的存储结构为链式存储。由于树中每个结点的度数不同，可以用多重链表来

实现，即每个结点有多个指针域，每个结点的指针字段根据结点的度来决定，每个指针指

向一棵子树的根。

在上述的多重链表结构中，结点是异构的，各个结点具有不同的长度，这在程序设计

中难以实现。还可以定义下面的节点结构：

datachildlchild2•••childd

几种常用的链表结构：

1）双亲表示法

用一组连续的空间存储树的结点，每个结点包括两个字段，一个维信息域，另

一个为指针域，指向该结点的父结点。形式说明如下：1

A0

2B1

#defineMAXNODENUM1003C1

typedefcharElementType;4D1

typedefstruct{5E2

ElementTypedata;〃结点类型6F2

intparent;〃父结点指针7G3

}TreeNode;8H4

9I4

TreeNodetree[MAXNODENUM]