数据结构(C语言版)
胡 学 钢 主编
目 录
概 论
第 1 章
线 性 表
第 2 章
栈、队列和数组
第 3 章
树
第 4 章
图
第 5 章
查 找
第 6 章
排 序
第 7 章
文 件
第 8 章
第 1 章 概 论
数据结构的研究内容
1.1
基 本 术 语
1.2
算 法 描 述 及 分 析
1.3
返回
1.1 数据结构的研究内容
1.1.1 用计算机解决实际问题的过程
建立 模型
构造求解算法
选择存储结构型
编写程序
测试
思考：你认为数据结构课程会涉及到上述哪些步骤呢？
数据结构课程在问题求解过程中的作用：
与建立模型的关系\r\r与算法设计的关系\r\r与选择存储结构的关系\r\r与编程之间的关系
1.1.2 学习数据结构的意义
在计算机科学中，数据结构不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。\r 目前在我国，《数据结构》不仅是计算机专业的核心课程之一，而且是一些非计算机专业的主要选修课程之一。 \r 瑞士计算机科学家沃斯（N.Wirth）曾以“算法 数据结构 ＝ 程序”作为他的一本著作的名称。可见，程序设计的实质是对实际问题选择一种好的数据结构，并设计一个好的算法。因此，若仅仅掌握几种计算机语言和程序设计方法，而缺乏数据结构知识，则难以应付众多复杂的课题，且不能有效地利用计算机。
返回
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
数据是指信息的载体，是能够输入到计算机中，并被计算机识别、存储和处理的符号的集合。数据的形式较多，例如我们前面所述的工资报表、学生成绩表，一个家族关系的表示形式，表示一个群体中个体之间关系的图形描述等。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
数据中具有独立意义的个体。例如工资表中的个人工资信息，成绩表中的学生成绩信息，家族关系中的个人等。在有些场合下，也称之为元素、记录、结点、顶点等。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
虽然将具有独立意义的个体用元素来表示，但在许多情况下还需要特定个体的具体信息，因而涉及到了元素的字段信息。字段是对元素的详细描述，通常情况下，元素可能包含多个字段。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
数据结构是指组成数据的元素之间的结构关系。线性结构、树型结构和图结构是《数据结构》中的几类常见的数据结构形式。如果数据中的元素之间没有关系，则构成集合，这也是一种结构。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
我们将线性结构、树型结构和图结构这几类结构称为逻辑结构，因为仅考虑了元素之间的逻辑关系，而没有考虑到其在计算机中的具体实现。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
为所涉及的数据结构选择一种存储形式，并将其存储到计算机中，这样就得到了数据结构在内存中的物理结构（有时也称为存储结构）。一种逻辑结构可能会有多种存储结构。例如，可以采用顺序存储，也可采用连接形式的存储。不同存储结构上所实现的运算的性能可能有一定的差异。
1.2 基本术语
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
在选择了数据结构的存储结构之后，就可以实现所给出的运算了。
1.2 小 结
数 据
数据元素
字段(域)
数据结构
数据结构的逻辑结构
数据结构的物理结构
数据结构运算的实现
所以，由于不同的存储形式对算法的时间性能、空间性能等有较大影响，即使是相同的存储结构也可能会存在不同的算法实现，为此，需要解决这样的问题：究竟何种存储结构更为合适？什么算法更有效？为此，需要对算法进行分析，有关算法分析部分将在本章的后面部分讨论。通过分析，可以知道所实现的算法的性能及所选择的存储结构是否符合要求。
返回
1.3 算法描述及分析
1.3.1 算法描述语言概述
如前所述，对数据结构的运算实现是以算法的形式来描述的。什么是算法？这很难给出一个严格的定义。简单地说，算法就是某类问题的求解方法。或：算法就是一段程序，该程序段对给定的输入可在有限的时间内产生出确定的输出结果。算法可采用多种描述语言来描述，如自然语言、计算机语言或某些伪语言。各种描述语言在对问题的描述能力方面存在一定的差异：自然语言较为灵活，但不够严谨；而计算机语言虽然严格，但由于语法方面的限制，使得灵活性不足。因此，许多教材中采用的是以一种计算机语言为基础，适当添加某些功能或放宽某些限制而得到的一种类语言，如类PASCAL语言、C语言等，这些类语言既具有计算机语言的严格性，又具有某些灵活性，同时也容易上机实现，因而被广泛接受。
1.3 算法描述及分析
1.3.2 算法分析
为了了解算法的有关性能，需要对算法进行分析。通过分析，不仅可以知道算法的有关性能，而且由此还可知道所选择的存储结构是否符合要求。\r 衡量算法的主要性能指标包括时间性能、空间性能等，其中时间性能是指运行算法所需的时间的度量，而空间性能则是指运行算法所需要的辅助空间的规模。在《数据结构》中，大多数算法分析是针对算法的时间性能进行的。算法的时间性能以时间复杂度来衡量。
时间复杂度
为了使算法的时间复杂度便于比较，不宜采用在某个具体机器上所运行的时间的形式来表示，一般是以算法中基本语句的执行次数来衡量的。然而，在实际应用时，基本语句的执行次数的精确计算是困难的，同时也是不必要的，因为许多算法中的语句的执行次数要取决于输入数据，可能会有多种复杂的情况。为便于计算，对这一时间复杂度大多采用一种近似的形式来描述，即采用基本语句执行次数的数量级来表示。此处所谓数量级是这样定义的：\r如果变量n的函数f(n)和g(n)满足：lim =常数k(k≠0)，则称f(n)和g(n)是同一数量级的，并用f(n)=O(g(n))的形式来表示。
返回
第 2 章 线 性 表
线性表的定义和运算
2.1
线性表的顺序存储结构
2.2
链 表
2.3
串
2.4
返回
2.1 线性表的定义和运算
2.1.1 线性表的定义
定义：线性表L是n个元素a1，a2，……，an组成的有限序列，记作L=( a1,a2,…,an)，其中n>=0为表长度；当n=0时为空表，记作L=（）。
对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后面的元素ai 1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。
线性表的特点：
线性结构的例子
由前述可知，线性表是许多实际应用领域中表结构的抽象形式，因此，线性表中元素在不同的场合可以有不同的含义。例如，在字母表（A,B,C,……,Z）中，每个元素是一个字母；在一个学生成绩表中，每个元素是一个学生的成绩信息，其中可能包含学号、姓名、成绩等。但要注意，在同一个表中的各元素的类型是一致的。
为了便于研究，一般不会也不可能讨论所有的运算，取而代之的是只讨论其基本运算。在此基础上，可以较方便地实现更多的运算。
2.1.2 线性表的运算
线性表常用的基本运算有六个：
（1）初始化线性表 initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。
（2）求表长度 List_length(L)——即求表中的元素个数。
（3）按序号取元素 get_element(L,i)——取出表中序号为i的元素 。
（4）按值查询 List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。
2.1.2 线性表的运算
（5）插入元素 List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n 1。
（6）删除元素 List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。
返回
2.2 线性表的顺序存储结构
2.２.1 顺序存储结构
定义：为在计算机上实现数据结构，首先需要将数据结构存储到计算机中。对此可有许多不同的方法，其中最为简单的方法是顺序存储方式：假设有一个足够大的连续的存储空间，则可将表中元素按照其逻辑次序依次存储到这一存储区中，称由此而得到的线性表为顺序表。
在具体实现时，一般用高级语言中的数组来对应连续的存储空间。假设最多可存放maxlen个元素，则可用数组data[maxlen]来存储表中元素。由于线性表有插入和删除元素这类改变表中元素个数的运算，因此，为随时了解线性表当前的元素个数（即表长度），需要另外设置一个变量以记录其元素个数，此处不妨用listlen来记录元素个数。这样，一个线性表的顺序存储结构就有两个分量，将这两个分量合在一起构成了一个整体。如图2－1所示：
顺序存储结构图示：
对所设计的存储形式，需要让计算机知道，这就是数据结构的描述。在用C语言描述这一由两个分量组成的结构时，需要采用其所提供的结构类型（struct），在说明时，要给该类型起个名，在此不妨用seqlist。另外，由于用到的数组事先要规定最大的元素个数，因此，为通用起见而要先给出一个常量形式的最大长度；由于元素的类型也取决于具体应用的问题，故此处的元素类型用elementtype来表示。
顺序表的类型描述：
由上述分析可得顺序表类型的描述如下：\r#define maxlen 100 //不妨假设元素个数最大为100\rtypedef struct \r{elementtype data[maxlen];//定义存储表中元素的数组\r int listlen; //定义表长度分量\r } seqlist;\r由存储方式可知顺序表的特点：逻辑上相邻的元素的存储地址也相邻。\r?在描述算法及上机实现时，需要对这种结构类型的具体变量进行运算，这样就涉及到表结构变量的定义，其格式如下：\rseqlist L，L1；
1．初始化线性表运算的实现 :\r由表结构可知，顺序表L是否为空取决于其元素个数是否为0，因此，只要将表L表中的长度值置为0就实现了建空表的功能。因此算法中的语句部分只要一条语句L->listlen＝0即可。算法如下：\rvoid initial_List（seqlist *L）\r { L->listlen=0; }
2.2.2 线性表运算的实现
在线性表采用顺序表结构存储时，如何实现所给出的六个运算？各算法的性能又如何？下面对此展开讨论。
这一功能的实现也较简单，只需返回表L的分量L.listlen即可求出顺序表L的长度值。算法如下：\rint List_length（seqlist L）\r{ return L.listlen ; }请注意这两个算法中参数L的不同之处，并分析原因。
(2)．求表长度函数的实现 :
按前面的约定，顺序表L中序号为i的元素（即ai）存放在其数组中的下标为i-1的元素中，因此，直接从该数组元素中取值即可。为使该函数有较大的应用范围，可以参数的形式返回所给定的元素的值，因此，算法的实现形式与所给定的问题的运算要求略有差异。另外需要注意的是，作为一个算法，不仅要考虑参数正确的情况下的求解，同时也要考虑参数不正确时的处理。就本题来说，需要判断元素的序号是否在合法的范围。由此得算法如下： \rvoid get_element（seqlist L，int I, elementtype *x）\r{ if（I<1 || I>L.listlen） error(“超出范围”);\r else *x= L.data[I-1]; \r}
(3).按序号求元素运算的实现:
要确定值为x的元素在L表中的位置，需要依次比较各元素。因而需要用循环语句搜索。当搜索到该元素时，就返回其序号，否则返回0。算法如下：\rint List_locate（seqlist L，elementtype x）\r{ int I;\r for (I=0; I (4)．查找运算的实现: 在顺序表L的第i个元素ai前插入一个元素x时，如果能插入，需要依次执行下列操作： \r将ai～an往后移一“格”；\r将x插入到第i个位置上，实现插入; \r修改表的长度：因为表长度是顺序表不可分割的一个分量。 (5)．插入算法的实现: 在执行插入时需要注意： 移动的次序 插入的条件 如何实现批量移动 void List_insert（seqlist *L，elementtype x，int i）\r{ int j;\r if （L->listlen==maxlen）error（“overflow”）; \r else if（i<1||i>L->listlen 1）error(“positionerror”）; \r else {for（j=L->listlen-1;j>=i-1;j--）\r L->data[j 1]=L->data[j];\r L->data[i-1]=x; \r L->listlen ; \r }\r } 插入算法： 试分析该算法的时间性能。 分析：由算法可知，该算法花费时间最多的操作是移动元素，移动元素的次数取决于序号i。对i分别取值为1，2，…和n 1时，移动次数分别为n，n-1,……1，0。为便于讨论，通常是求出插入一个元素时的平均移动次数。虽然在各个位置上插入元素的概率不尽相同，但为了对算法的时间性能有大致的了解，一般都假设各位置的插入概率相同，因此可求出其在插入一个元素时平均移动元素的次数如下： \rEis= （0 1 … n）/( n 1) = n /2 插入算法的性能分析： 讨论：如果能从顺序表L中删除第i个元素的话，则可通过完成如下两个操作来实现： \r将ai 1～an前移，从而将待删除元素ai“挤掉”，因为顺序表要求逻辑上相邻的元素在物理上也相邻。 \r表长度减1。 (6)．删除算法的实现: 在实现删除操作时同样需要注意到：删除的条件、元素移动的次序和如何实现批量元素的移动等问题。 void List_delete(seqlist *L,int i)\r{ int j;\r if (L->listlen<=0) error(“下溢出错”);\r if (i>L->listlen||i<=0) error(“删除位置出错”);\r else { for (j=i;j<=L->listlen-1;j )\r L->data[j-1]=L->data[j];\r L->listlen--;\r }\r} 删除算法： 分析：和插入算法类似的是，删除算法花费时间最多的操作也是移动元素，移动元素的次数同样取决于序号i，为此，同样也要计算出移动一个元素的平均移动次数。由算法可知，在i依次取值为1，2，…和n时，分别要移动n-1，…，1，0次。同样假设各元素的删除概率相同，则删除一个元素时平均移动元素的次数为:\rEis= （0 1 … n）/( n) =( n-1) /2 删除算法的性能分析： 一个问题：算法中循环控制变量j的含义是____\rＡ、要移走的线性元素的序号Ｃ、将要移到的线性表元素的序号\rＢ、要移走的数组元素的下标Ｄ、将要移到的数组元素的下标 例2.1：假设顺序表L中的元素递增有序，设计算法在顺序表中插入元素x，要求插入后仍保持其递增有序特性，并要求时间尽可能少。 2.2.3 顺序表的应用(例2.1) 分析：前面所介绍的基本插入算法是针对指定的插入位置进行的，此处则需要在算法中先搜索出插入的位置，然后将从该位置开始的元素往后移并执行插入。现在的问题是：如何搜索插入位置？如何移动元素？对此有两种基本的方法： \r（1）从表前往表后搜索插入位置，然后批量移动其后面的元素。这种方法比较费时间：假设搜索出的插入序号为i，则搜索所需的比较次数为i，批量移动后面元素的次数为n-i 1。因此，对每次插入操作来说，需要比较或移动表中所有元素。 \r（2）从后往前依次比较各元素，显然，在比较过程中，比x大的元素应该往后移，重复这样的操作，直到搜索到插入位置为止。这种方法相对容易实现，并且比较和移动操作同步，对每个元素来说，比较次数比移动总数多一个（除非是第一个位置）。下面的算法就是采用这种方法。 在插入前还需要做的一件事就是要判断插入的条件，显然，此处能够插入的条件就是原表中还没有满。综上所述得算法如下:\rVoid insert(seqlist *L,elementtype x)\r{ int i=L->listlen-1;\r if (i>=maxlen-1) then error(“overflow”);\r else { while(i>=0