数据结构实用教程（C语言版）（第二版）01第一章 绪论

第一章绪论1．1基本术语1．2数据结构的定义及研究的内容1．2．1数据的逻辑结构1．2．2数据的存储结构1．2．3数据的运算1．3算法1．3．1算法的概念及特性1．3．2算法的描述1．3．3算法的评价1．4学习数据结构的意义和目的1．1基本术语数据（Data）是人们约定的符号，用它来表示客观事物及其活动，是信息的载体。数据是计算机程序加工处理的对象。数据元素（DataElement）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，在不同的情况下，又可以称为元素、结点、顶点或记录。数据是由数据元素构成的。数据项（DataItem）是构成数据元素不可分割的具有独立含义的最小标识单位。若数据元素可再分，则数据元素是由若干个数据项组成；如数据元素不可再分，数据元素和数据项是同一概念，如整型数据就是不可再分的。数据类型（DataType）是一个值的集合和定义在这个值集上一组操作的总称。按值的不同特性，高级程序设计语言中的数据类型可分为原子类型和结构类型两类。1．2数据结构的定义及研究的内容数据结构的定义:按照某种逻辑关系组织起来的一批数据，用一定的存储方式存储在计算机的存储器中，并在这些数据上定义一个运算的集合，就称为一个数据结构。数据结构研究的内容：（1）数据的逻辑结构：按照某种逻辑关系将数据组织好，即逻辑结构。是从具体问题抽象出来的数学模型。（2）数据的存储结构：将数据及数据之间的关系存储到存储区域中，即存储结构。是逻辑结构到存储区域的映射。（3）数据的运算：在这些数据上定义的一个运算集合。数据结构研究内容之间的联系和区别：

数据的逻辑结构是从具体问题抽象出来的数学模型；数据的存储结构是逻辑结构到存储区域的映射；数据的运算是定义在数据的逻辑结构上，实现在存储结构上。

1.2.1数据的逻辑结构定义：是数据元素之间的逻辑关系。是根据实际问题抽象出来的数学模型。表示:(1)二元组表示：

Data_Structure=（D，S）

D={d1，d2，…，dm｝

S=｛r1，r2，…，rn｝

rj=｛<d1，d2>，<d2，d3>，…，<di-1，di>，…，<dn-1，dn>｝D是数据元素的有限集，

S是D上关系的有限集，通常取

S中的一个关系rj来进行讨论，

rj可以表示为数据元素的序偶

<di，dj>的集合。

用二元组表示的数据的逻辑结构，有如下的常用术语：（1）前趋结点、后继结点、相邻结点（2）开始结点、终端结点、内部结点

(2)图形表示：

数据的逻辑结构有两大类：（1）线性结构：经典的线性结构是线性表。

线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，也就是说结构中的数据元素间存在着一对一的相互关系。（2）非线性结构：经典的非线性结构有树形结构和图形结构。

树形结构的逻辑特征是：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，也就是说结构中的数据元素间存在着一对多的层次关系。图形结构的逻辑特征是：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，也就是说结构中的数据元素间存在着多对多的网状关系。表1.1某校围棋社团学生简表学号姓名性别出生日期职务01黄家正男1982-08-05团长02赵芳女1981-08-15组长03王明女1983-04-01组长04王红女1982-06-28组员05张小才男1984-03-17组员06马立伟男1983-10-12组员07孙刚男1982-07-05组员08刘永男1982-12-09组员

例1.1在表1.1中，八名学生按学号从小到大排列，形成一个线性结构。假设表示这种逻辑结构的关系为r1，则r1可以定义为学生按学号顺序递增排列的关系，该线性结构的逻辑结构可用二元组表示为：L=（D，S），r1∈SD=｛01，02，03，04，05，06，07，08｝r1=｛<01，02>，<02，03>，<03，04>，<04，05>，<05，06>，<06，07>，<07，08>｝图1.1线性结构的图示

例1.2

在表1.1中，学生之间还存在着领导与被领导关系，其中01号学生为团长，直接领导02和03号学生，他们分别是组长，02号学生直接领导04和05号学生，03号学生直接领导06、07和08号学生，假设表示这种逻辑结构的关系为r2，则r2可以定义为学生之间的领导与被领导关系，该数据结构的逻辑结构可用二元组表示为：T=（D，S），r2∈SD=｛01，02，03，04，05，06，07，08｝ r2=｛<01，02>，<01，03>，<02，04>，<02，05>，<03，06>，<03，07>，<03，08>｝例1.3在表1.1中，学生之间还有好友关系，如01和02、03、05号是好友，02和04号是好友，03和05号是好友，04和05、06号是好友，06和07之间是好友，08无好友，假设表示这种逻辑结构的关系为r3，则r3可以定义为学生之间的好友关系，该数据结构的逻辑结构可用二元组表示为：G=（D，S），r3∈SD=｛01，02，03，04，05，06，07，08｝ r3=｛<01，02>，<02，01>，<01，03>，<03，01>，<01，05>，<05，01>，<02，04>，<04，02>，<03，05>，<05，03>，<04，05>，<05，04>，<04，06>，<06，04>，<06，07>，<07，06>｝1.2.2数据的存储结构定义：逻辑结构到计算机存储器的映射。在映射中，一方面要将数据集D

中的数据元素存放到存储器中，另一方面还要体现关系集S，常见

的体现关系S的方式有显示和隐含两种。表示：(1)计算机高级语言（C语言）--数据类型及变量的定义。(2)图示法常用的存储方法：

顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元

里。用C语言中的数组来描述。

链接存储：通过附加指针域表示数据元素之间的关系。用C语言中的指

针类型来描述。

索引存储：附加索引表，索引表中的每一项称为索引项(关键字,地址)，

用来标识一个或一组数据元素的存储位置。

散列存储：根据数据元素的关键字直接计算出该结点的存储地址，通

常称为关键字－地址转换法。四种存储方法，可以单独使用，也可以组合起来对数据结构进行存储映象。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。例1.4用顺序和链接两种方法存储有序序列A=（99，123，134），假设每个数据元素占2个字节，即一个存储单元为两个字节。

图1.4关系的映像方法1.2.3数据的运算定义：数据的运算（也称操作）是指对数据元素进行加工和处理。

基本操作一般包括查找、插入、删除、排序等。表示：用算法来描述基本运算。1．3算法1.3.1概念和特性

概念：解决特定问题的方法和步骤，是由若干条指令组成的有限序列。特性：（1）有穷性：对于任意一组合法输入值，一个算法必须总是在执行有穷步骤后结束，有限时间内完成。（2）确定性：算法中每条指令都确切地规定了所应执行的操作，不致产生二义性或多义性；在同一条件下，一个算法只能有一条执行路径。（3）可行性：算法中的每一步都是可行的，都可以通过手工或机器可以接受的有限次操作在有限时间内完成。

（4）输入：一个算法有0个或多个输入，这些输入是算法所需的初始量或待处理的对象，来自某个特定的对象集合。（5）输出：一个算法有1个或多个输出，这些输出与输入有着某种特定的关系。1.3.2表示:自然语言、程序流程图、伪语言、高级语言（C函数）。1.3.3算法的评价

定性:（1）正确性：是指算法应当满足具体问题的需求，即对合理的输入，算法都会得出正确的结果。（2）可读性：是指算法被理解的难易程度。（3）健壮性：是指算法对输入的非法数据恰当地作出反映或进行相应处理的能力。（4）简单性：是指一个算法所采用的逻辑结构、存储结构以及处理过程的简单程度。定量:①时间复杂度：是一个算法运行时所耗费的系统时间，即算法的时间效率●每条语句重复执行的次数称为语句的频度。●当不考虑算法运行的软硬件环境时，算法所耗费的时间就是该算法中所有简单语句的频度之和。●一般情况，在讨论算法的时间效率时，主要考虑当问题规模n趋向无穷大时，时间复杂度T(n)的数量级，亦称为算法的渐近时间复杂度，则T(n)=O(f(n))。记号“O”是一个数学符号，其数学定义是：

设T(n)和f(n)均为正整数n的函数，若存在两个正整数M和n0，使得当n≥n0时，都有|T(n)|≤M|f(n)|存在，则T(n)=O(f(n))。

●在多数情况下，当一个算法中有若干个循环语句时，算法的时间复杂度是由嵌套循环中最内层循环语句的频度决定的。需要注意的是，如果算法中包括对其他函数或算法的调用，计算算法的时间复杂度时还要分析被调用算法或函数的时间复杂度。例1.5

求一维数组元素中的最大值

int

sum(int

a[],intn){ int

i,s;（1）s=a[0]; /*1次*/（2）for(i=1;i<n;i++;) /*n次*/（3）if(s<a[i])s=a[i];/*n-1次*/（4）returns;/*1次*/}T1(n)=1+n+n-1+1=2n+1，f(n)=n，T1(n)=O(n)例1.6两个n阶方阵相加voidMatrixadd(inta[][],intb[][],intc[][],intn){int

i,j;（1）for(i=0;i<n;i++) /*n+1次*/（2） for(j=0;j<n;j++) /*n×(n+1)次*/（3）c[i][j]=a[i][j]+b[i][j];/*n2次*/}T2(n)=n+1+n×(n+1)+n2=2n2+2n+1f(n)=n2

，T2(n)=O(n2)例1.7求两个n阶方阵的乘积voidMatrixmlt(inta[][],intb[][],intc[][],intn){int

i,j,k;（1）for(i=0;i<n;i++) /*n+1次*/（2）for(j=0;j<n;j++) /*n×(n+1)次*/（3）{c[i][j]=0; /*n2次*/（4）for(k=0;k<n;k++) /*n2×(n+1)次*/（5）c[i][j]=c[i][j]+a[i][k]*b[k][j];/*n3次*/}}T3(n)=n+1+n×(n+1)+n2+n2×(n+1)+n3=2n3+3n2+2n+1，f(n)=n3

，T3(n)=O(n3)最好时间复杂度、最坏时间复杂度和平均时间复杂度

例1.8

在一维数组中查找指定的元素

int

search(int

a[],int

x,intn){ inti;（1）for(i=0;i<n;i++;)（2）