计算机数据结构教程.pdf

《计算机数据结构教程.pdf》由会员分享，可在线阅读，更多相关《计算机数据结构教程.pdf（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 一 章 绪 论计算机科学是一门研究数据表示和数据处理的科学。数据是计算机化的信息，它是计算机可以直接处理的最基本和最重要的对象。无论是进行科学计算或数据处理、过程控制以及对文件的存储和检索及数据库技术等计算机应用领域中，都是对数据进行加工处理的过程。因此，要设计出一个结构好效率高的程序，必须研究数据的特性及数据间的相互关系及其对应的存储表示，并利用这些特性和关系设计出相应的算法和程序。数据结构是计算机科学与技术专业的专业基础课，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多

2、复杂的课题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识。打 好“数据结构”这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益的。1.1数据结构的定义在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：首先要从该具体问题抽象出一个适当的数学模型，然后设计或选择一个解此数学模型的算法，最后编出程序进行调试、测试,直至得到最终的解答。例如，求解梁架结构中应力的数学模型的线性方程组，该方程组可以使用迭代算法来求解。由于

3、当时所涉及的运算对象是简单的整型、实型或布尔类型数据，所以程序设计者的主要精力是集中于程序设计的技巧上，而无须重视数据结构。随着计算机应用领域的扩大和软、硬件的发展，非数值计算问题越来越显得重要。据统计，当今处理非数值计算性问题占用了 90%以上的机器时间。这类问题涉及到的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程式加以描述。因此，解决这类问题的关键不再是数学分析和计算方法,而是要设计出合适的数据结构，才能有效地解决问题。下面所列举的就是属于这一类的具体问题。例如学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的有关情况的时候，只要我们建

4、立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如 图1.1所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要 求（如给定姓名）对学生信息文件进行查询。诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构。例1 学生信息检索系统。当我们需要查找某个学生的有关情况的时候；或者想查询某个专业或年级的学生的

5、有关情况的时候，只要我们建立了相关的数据结构，按照某种算法编写了相关程序，就可以实现计算机自动检索。由此，可以在学生信息检索系统中建立一张按学号顺序排列的学生信息表和分别按姓名、专业、年级顺序排列的索引表，如 图1.1所示。由这四张表构成的文件便是学生信息检索的数学模型，计算机的主要操作便是按照某个特定要求（如给定姓名）对学生信息文件进行查询。诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中，计算机处理的对象之间通常存在着的是一种简单的线性关系，这类数学模型可称为线性的数据结构(a)学生信息表学号姓名性别专 业年 级9 8 0 0 0 1吴承志男计算

6、机科学与技术9 8 级9 8 0 0 0 2李淑芳女信息与计算科学9 8 级9 9 0 3 0 1刘 丽女数学与应用数学9 9 级9 9 0 3 0 2张会友男信息与计算科学9 9 级9 9 0 3 0 3石宝国男计算机科学与技术9 9 级0 0 0 8 0 1何文颖女计算机科学与技术2 0 0 0 级0 0 0 8 0 2赵胜利男数学与应用数学2 0 0 0 级0 0 0 8 0 3崔文靖男信息与计算科学2 0 0 0 级0 1 0 6 0 1刘 丽女计算机科学与技术2 0 0 1 级0 1 0 6 0 2魏永鸣男数学与应用数学2 0 0 1 级崔文靖8何文颖6李淑芳2刘 丽3,9石宝国5魏

7、永鸣1 0吴承志1赵胜利7张会有4(c)专业索引表计算机科学与技术1,5,6,9信息与计算科学2,4,8数学与应用数学3,7,1 02 0 0 0 级6,7,82 0 0 1 级9,1 09 8 级1,2,39 9 级4,5(b)姓名索引表(d)年级索引表图1 学生信息杳询系统中的数据结构 例2 八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如 图 1.2 所示(为了描述方便，将八皇后问题简

8、化为四皇后问题)。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。例3 计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用个称作图的数据结构来表示，如 图 1.3所示。有向图中的每个顶点表示门课程，如果从顶点垮到为之间存在有向边,则表示课程i 必须先于课程j 进行。由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构

9、。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。图 1.2 四皇后问题中隐含的状态树课程名称计算机导论数据结构汇编语言C 程序设计语言计算机图形学接口技术数据库原理编译原理操作系统先修课程无课程编号C,结构课程的内容数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同时:数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。数据结构课程集中讨论软件开发过程

10、中的设计阶段、同时设计编码和分析阶段的若干基本问题。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”，如 图 1.5所示。图1.5数据结构课程内容体系方面层次数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构的比较及算法分析数据结构的核心技术是分解与抽象。通过分解可以划分出数据的三个层次;再通过抽象,舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能,再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合使我们将问题变换为数据结构。这是一个从具体（即具体问题）到 抽

11、象（即数据结构）的过程。然后，通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务。这是一个从抽象（即数据结构）到具体（即具体实现）的过程。熟练地掌握这两个过程是数据结构课程在专业技能培养方面的基本目标。数据结构作为一门独立的课程在国外是从1968年才开始的，但在此之前其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立有关课程,但当时的课程名称并不叫数据结构。1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所著的 计算机程序设计技巧第一卷 基本算法是第本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从 20世纪60年代末到

12、70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从 70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势,越来越被人们所重视。1.3 数据结构的基本概念1.1.2 基本术语1.数 据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。2.数据元素（data element）数据

13、元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。3.数据对象（data object）是性质相同的数据元素组成的集合，是数据的一个子集。例如，整数数据对象的集合可表示为N=O,1,+2.,字母字符数据对象的集合可表示为 C=4A,B,.,Z,o4.数据结构（data structures）数据结构定义1;是相互.之间存在-种或多种特定关系的数据元素的集合。形式化定义：数据结构是一个二元组D a t a _ S t r u c t u r e =（D,R）其中，D是数据元素的有限集合，R是D上关系的集合数

14、据结构定义2：按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算（操作）。这三个方面的关系为：（1）数据的逻辑结构独立于计算机，是数据本身所固有的。（2）存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。（3）运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必须依赖于存贮结构。逻辑结构一划分方法一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结

15、构 结构中的数据元素之间存在一对一的关系。-.图2/线性表逻辑结构示意图三、树型结构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。图图形结构逻辑示意图存储结构（S t o r g e S t r u c t u r e）:数据结构在计算机中的表示（或称映象）称为数据的存储结构，又称为物理结构。四种基本的存储方法：（1）顺序存储方法（顺序存储结构）（2）链接存储方法（链式存储结构）（3）索引存储方法（4）散列存储方法同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。顺序存储结构:用数据元素在存储

16、器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。索引存储方法：使用该方法存放元素的同时，还建立附加的索引表，索引表的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能惟一标识一个结点的数据项。散列存储方法：通过构造散列函数，用函数的值来确定元素存放的地址。5.数据类型是一组性质相同的值的集合及定义于这个值集合上的一组操作的总称。是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的

17、确定的数据类型。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。CH提供的基本数据类型有：整型、实型、字符型、逻辑型例如，高级语言中用到的整数数据类型，是指由一3 2 7 6 8到3 2 7 6 7中值构成的集合及组 操 作（加、减、乘、除、乘方等）的总称。注：数据类型与数据结构的区别，数据结构强调数据元素之间的逻辑关系。6.抽象数据类型（Abstract data type）抽象数据类型（A b s t r u c t D a t a T y p e,简称A D T）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的

18、组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型和数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。但 在 另 一 方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方法学中，要求在构成软件系统的每个相对独立的模块上，定义 组数据和施

19、于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。抽象数据类型的定义可以由一种数据结构和定义在其上的组操作组成,而数据结构又包括数据元素及元素间的关系，因此抽象数据类型般可以由元素、关系及操作三种要素来定义。抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。格式：A D T 抽象数据类型名i sData:数据描述Operation:操作声明END例如:给出自然数的抽象数据类型定义.ADT Natural Number isDa

20、ta:一个整数的有序子集合，它开始于0,终止于机器能表示的最大整数（MAXINT）。Operation:对于所有x,y Natural Number,定义如下操作：add（x,y）求 x+ysub（x,y）求 x-ymul（x,y）求 x*ydiv（x,y）求 x/yend1.2 算法的描述1.2.1 算法的概念1.算 法（algorithm）通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0 个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3 有穷性

21、：每条指令的执行次数必须是有限的。（4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条指令的执行时间都是有限的。2.算法和程序的关系算法的含义与程序十分相似，但二者是有区别的。一个程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。一个算法若用计算机语言来书写，则它就可以是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，-种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。

22、可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。1.2.2 算法描述算法可以使用各种不同的方法来描述。最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读。缺点是不够严谨。可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序还有一个编程的问题。可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而且不太直观，常常需要借助于注释才能使人看明

23、白。用 C+描述算法在本教材中，我们将采用C+或类C+来描述算法。并且用C+描述算法遵循如下规则：(I)所有算法的描述都用C+中的函数形式函数类型 函数名(形参及类型说明)函数语句部分r et u r n(表达式值)；(2)函数中的形式参数有两种传值方式若为一般变量名，则为单向传值，若在变量前面增加“&”符号，则为双向传地址。例如有一个函数为V o i d s w a p(&i,&j,k)则 i,j 为双向传地址参数，k为单向传值参数。(3)函数的说明部分可函数的实现部分分离在 C+中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离开来。(4)输

24、入函数C +中的输入函数调用为:c i n 变量名。(5)输出函数C +中的输出函数调用为:c o u t n0,有：f(n)W c g(n)则有:f(n)=0(g(n)例如，一个程序的实际执行时间为T(n)=2.7n3+3.8n2+5.3则 T(n)=0(/)。使用大。记号表示的算法的时间复杂度，称为算法的渐进时间复杂度(AsymptoticComp I ex ity)o通常用0(1)表示常数计算时间。常见的渐进时间复杂度有：0(1)0(log2n)o(n)O(nlog2n)0(n2)0(n3)0(2n)在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为0(1),另外，在时间频

25、度不相同时，时间复杂度有可能相同，如 T(n)=n2+3n+4与 T(n)=4n2+2n+l它们的频度不同，但时间复杂度相同，都为0(/)。例分析以下程序段的时间复杂度fbr(i=l;in;i+)y=y+i;for(j=0;j=(2*n);j+)X-H-；常见函数的时间复杂度按数量递增排列及增长率。常数阶0(1)对数阶O(log2n)线性阶0(n)线性对数阶O(nlog2n)平方阶0(n2)立方阶0(n3)k 次方阶O(nk)指数阶O(2n)2.空间复杂度与时间复杂度类似，空间复杂度是指 程序运行从开始到结束所需的存储量。即算法在计算机内执行时所需存储空间的度量。记作：S(n)=O(f(n)我

26、们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。本章小结数据、数据结构等基本概念数据结构的三个方面的内容抽象数据类型的概念线性和非线性结构的逻辑特征数据存储的四种基本方法算法、算法的时间复杂度第一章概论 自测题一、填空题1.数据结构是门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2.数据结构被形式地定义为（D,R）,其中D 是 的有限集合,R 是 D 上的 有限集合。3.数据结构包括数据的、数据的 和数据的 这三个方面的内容。4.数据结构按逻辑结构可分为两大类，它们分别是 和。5.线性结构中元素之间存在_ _ _ _ _

27、_ _ _ _ _ 关系，树形结构中元素之间存在_ _ _ _ _ _ _ _ _ _关系,图形结构中元素之间存在_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _关系。6.在线性结构中，第一个结点 前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。7.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以。8.在图形结构中，每 个 结 点 的 前 驱 结 点 数 和 后 续 结 点 数 可 以。9.数 据 的 存 储 结 构 可 用 四 种 基 本 的 存

28、 储 方 法 表 示，它 们 分 别是O10.数据的运算最常用的有 5 种，它们分别是o11.一个算法的效率可分为 效率和 效率。二、单项选择题（）1.非线性结构是数据元素之间存在一种：A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系（）2.数据结构中，与所使用的计算机无关的是数据的 结构；A）存储 B）物理 C）逻辑 D）物理和存储()3.算法分析的目的是：A）找出数据结构的合理性C）分析算法的效率以求改进B）研究算法中的输入和输出的关系D）分析算法的易懂性和文档性()4.算法分析的两个主要方面是：A）空间复杂性和时间复杂性C）可读性和文档性B）正确性和简明性D）数据复杂性和程

29、序复杂性()5.计算机算法指的是：A)计算方法 B)排 序 方 法 C)解决问题的有限运算序列 D)调度方法()6.计算机算法必须具备输入、输出和A)可行性、可移植性和可扩充性C)确定性、有穷性和稳定性三、简答题一等5 个特性。B)可行性、确定性和有穷性D)易读性、稳定性和安全性1 .数据结构和数据类型两个概念之间有区别吗？2 .简述线性结构与非线性结构的不同点。四、分析下而各程序段的时间复杂度1.for(i=0;in;i+)for(j=0;jm;j+)AiU=0;2.s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=BiU;sum=s;3.x=0;for(i=l;in;i

30、+)for(j=l;j=n-i;j+)x+:4.i=l;while(i=n)i=i*3;五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？1.D=d l,d 2,d 3,d 4 R=(d l,d 2),(d 2,d 3),(d 3,d 4)2 D=d l,d 2,d 9 R=(d l,d 2),(d 1 ,d 3),(d 3,d 4),(d 3,d 6),(d 6,d 8),(d 4,d 5),(d 6,d 7),(d 8,d 9)3。D=d l,d 2,d 9 R=(d l,d 3),(d l,d 8),

31、(d 2,d 3),(d 2,d 4),(d 2,d 5),(d 3,d 9),(d 5,d 6),(d 8,d 9),(d 9,d 7),(d 4,d 7),(d 4,d 6)第2 章 线 性 表线性表是我们要介绍的数据结构中的第一种数据结构，也是比较简单的数据结构，对于线性表的操作是动态的还是静态的在后续的章节里要用到，是学习数据结构的基础。首先看一下什么是线性表。2.1 线性表的定义及其运算2.1.1线性表的定义1.线性表的定义线 性 表(l i n ea r l i s t)是具有相同属性的数据兀素的一 个有限序列。用二元组表示为：l i n ea r _ l i s t=(A,R)其

32、中 A=a i l i n,n 2 0,a i Cel em t yp eR=UWiW n T A 表示属性相同的数据元素，R 代表关系，表示有序，也叫有序偶。有了这种关系就表示线性表的数据元素之间是一个有限序列。E l em t yp e表示一种具体的已知数据类型。为线性表中的数据元素所有可能的数据类型的一个抽象名称。例如：L l=(A,R)A =5,3 8,1 2,49,6 3,2 00,470)R=某校1 9 71 至1 9 77年拥有的计算机的数量L l=(5,3 8,1 2,49,6 3,2 00,470)L 2=(A,R)A =“王一”，“王兰”，“王心”，“王小白”，“王小红”口

33、=父子关系新生报到入学，一个班级有3 0 个学生，这 3 0 个学生只能形成一个集合，如果加上一个关系，把学生按学号来编，这个集合由于有了学号这样的一个关系就成为了一个线性表。所以线性表的关键在于关系。2.线性结构的基本特性：-对一的关系。必有唯一一个元素无前驱，必有唯一一个元素元后继，除此之外任何元素都有唯一的前驱和唯一的后继。有了这种一对一的关系，就称为线性结构或线性表。由以上知道了什么样的关系是线性表，但是我们考虑的不是判断什么样的关系是线性表，什么样的关系不是线性表，而是前提已知一个线性表，那么怎样在计算机里如何存储，如何处理是要研究的问题。下面要介绍几个概念。1。如果已经是一个线性表

34、，用园括可如下来表示。线性表的一般形式：L=(a l.-a i-l.a i.-a n)n 是线性表的元素的个数即线性表的长度,n=0 是空表。这个图表示在逻辑关系上每个元素的前驱和后继的关系。以上是线性表的逻辑结构。2。物理存储线性表的物理存储也就是物理结构的表示，线性表已经存在，对这个线性表进行如下的一些操作，用什么方法，在计算机里如何存储，它的操作怎样来实现。例如，有一种结构整型可以进行四则、求余、求模、运算等。这些运算就是整型可以实现的操作。对于线性表也是一种数据类型，这种结构也可以实现很多操作。线性表作为抽象数据类型可能实现的基本操作：2.1.2线性表的运算常见线性表的运算有：1 .置

35、 空 表 S E T N U L L (&L)将线性表L置成空表2 .求 长 度 L E N G T H (L)求给定线性表L的长度3 .取 元 素 G E T (L,i)若 I W i W l e n g th(L),则 取 第 i个位置上的元素，否则取得的元素为N U L L 4 .求直接前趋P R I O R (L,X)求线性表L中元素值为X的直接前趋，若 X为第 个元素，前驱为N U L L5 .求直接后继N E X T (L,X)求线性表L中元素值为X直接后继，若 X为最后一个元素，后继为N U L L。6 .定位函数 L O C A T E (L,X)在线性表L中查找值为X的元素位

36、置，若有多个值为X,则以第一个为准，若没有，位置为0。7 .插入 I N S E R T (&L,X,i)在线性表L中第i 个位置上插入值为X的元素。8 .删除 D E L E T E (&L,i)删除线性表L中第i 个位置上的元素。注意：初始条件、返回值、操作功能是编写一个函数的依据。引用类型&：给变量起别名。&x=y 程序对x进行的任何操作，同时对y也进行操作，反之亦然。因为x,y指向同一存储单元即两个变量使用同一个存储单元。可以用其中的任何一个名字对存储单元进行操作。形参中用&将L的值带回到主要函数。例：假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的

37、一组操作及结果如下:L e n g t h(L);G e t(L,i)P r i o r (L,x)N e x t (L,x)L o c a t e(L,x)I n s e r t (&L,y,i)D e l e t e(&L,i+1)所得结果为5所得结果为89所得结果为23/所得结果为89所得结果为2所得结果为(23,56,88,89,76,18)所得结果为(23,56,88,76,18)以上了解了线性表、线性表的关系以及基本操作。这些基本操作的实现是要有存储作为前提的，线性表在里存储为什么样子，是动态的还是静态的，只有确定了这些才能实现操作，也就是说存储是实现操作的依据。卜面介绍两种存储方

38、法。2.2线性表的顺序存储结构一、顺序表结构顺序存储的特点：逻辑关系相邻(a i和a i+1是相邻的)物理位置也相邻 存完a i 一定要存a i+1)线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。这种存储结构的线性表也称为顺序表。它的特点为表中相邻的元素赋以相邻的存储位置。换句话说，以元素在计算机内“物理位置相邻”来表示线性表数据元素之间的逻辑关系。假设线性表中元素为(a l,a 2,a n),设第一个元素a l的内存地址为L O C(a l)(基地址),而 每 个 元 素 在 计 算 机 内 占d个 存 贮 单 元，则 第i个 元 素ai的 地 址 为L O C(a

39、 i)=L O C(a l)+(i-l)X d (其中 I W i W n)由于高级语言中的数组类型具有如下的特点：数组中的元素间的地址是连续的，数组中所有元素的数据类型是相同的。而这与线性表的存储空间结构是类似的。因此，通常都用数组来描述数据结构中的顺序存储结构。存储的时候即要存储数据元素又要存储数据关系，那么数组把数据元素存储在l i s t,也就存储了关系。用数组存放以后，线性表的长度是数组空间中变化的，用l e n来表示线性表的长度，并事先预计分配一个足够大的空间m a x s i z e,用一个霭来定义.c o n s t i n i m a x s i z e-m a x l e

40、n：m a x l e n及示线性表允许的最大长度s t r u c t s e qu e n l i s t e l e m t y p e a m a x s i z e ;表示线性表(a l,a 2,a n)i n t l e n;:l e n表示当前线性表的实际长度(可以变化)；如何来使用？使用方法：首先定义s e qu e n l i s t L;i n t n=7;结构体有两个域：L.a l =a l;L.a 2=a 2;L.l e n;注：结构体类型定义的是一种样子，没有实际的内容。结构体变量是系统实际分配一个空间o变量定义之后，才用实际的空间可以使用。才可以对其两个域进行访问、

41、进行操作。二、顺序表操作的实现1.求顺序表的长度l e n g t h (L)i n t l e n g t h(s e qu e n l i s t L)r e t u r n L.l e n;2.置空表s e t n u l l (&L)v o i d s e t n u l 1(s e qu e n l i s t&L)L.l e n=0;3.遍历线性表：t r a v e r l i s t (&L)依次访问(输出)表中的元素，且只访问一次。v o i d t r a v e r l l i s t(&L)(f o r (i=l;i =L.l e n;i+)c o u t L,a i

42、;c o u t e n d l;4 .删除运算D e l e t e (&L,i)v o i d D e l e t e(s e q u e n l i s t&L,i n t i)i n t j;i f(i L l e n)c o u t J,p o s i t i o n i s n o t c o r r e c t!e n d l;e l s e f o r(j=i+l;j=m a x s i z e-l)c o u t o v e r f l o w”e n d l;e l s e i f(i L.l e n+l)c o u t w“p o s i t i o n i s n o

43、t c o r r e c t !5,e n d l;e l s e f o r(j=L.l e n;j=i;j)L.a j+l L.a j ;元素后移L.a i =x;插入元素L.l e n+;表长度增加1 注意逻辑关系的变化5.定 位 算 法(查 找)L o c a t e(L,x)i n t L o c a t e(s e q u e n l i s t L,e l e m t y p e x)i n t j=l;w h i l e(j=L.l e n)&(L.a j !=x)j+；i f(j=L.l e n)r e t u r n j;e l s e r e t u r n 0;)6.

44、取元素G e t(L,i)e l e m t y p e G e t(s e q u e n l i s t L,i n t i)i f(i L.l e n)r e t u r n N U L L;else return L.a i;2.3 线性表的链式存贮结构静态存储的特点是用数组的方法来处理，事先定义一个足够大的空间，插入和删除的操作需要不断地移动。效率比较低。线性表的链式存储结构的特点是用一组地址任意的存储单元（可以是连续的，也可以是不连续的）存储线性表的数据元素。因此，为了表示每个数据元素与其直接后继之间的逻辑关系的有序性，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即

45、存储位置）。这两部分信息组成数据元素的存储映象，称为结点。数据元素+指 针（指示后继元素存储位置）=结点以“结点的序列”表示线性表一链表。就是将数据元素存放在结点中，按照前驱和后继的关系用链子将其串起来。在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。线性链表中的结点结构可描述为：其中d ata域用来存放结点本身信息，next域用来存放下一个元素地址。单 链 变T用C+描述为：struct link elemtype data;/数据域link*next;指针域（a）不带头结点的单链表head_ a,头 I AE t_|a2-|（b）带头结点的单链表图2

46、-7不带头结点和带头结点的单链表单链表运算1.头插法建立单链表(从左边插入结点)link*hcreat()link*s,*p;int i;cini;输入结点数值，为0时算法结束p=NULL;while(i)s=new link;s-data=i;s-next=p;p=s;c in i;return p;2.尾插法建立单链表(从右边插入结点)link*rcreat()link*s,*r,*p;int i;p=r=new link;p-next=NULL;cini;while(i)s=new link;s-data=i;r-n e x t=s;r=s;c i n i;r-n e x t=N U L

47、 L;r e t u r n p;3 .单链表上的查找运算(1)按值查找L o c a t e (h e a d,x)在单链表h e a d 中，查找值为x 的结点，若找到，返回它的地址，否则返回N U L L。L i n k *L o c a t e(l i n k *h e a d,e l e m t y p e x)l i n k *p;p=h e a d-n e x t;w h i l e(p!=N U L L)&(p-d a t a!=x)p=p-n e x t;r e t u r n p;)(2)按序号查找g e t (h e a d,i)在单链表h e a d 中查找第i 个位置

48、上的元素，若找到，则返回它的地址，否则返回N U L L。L i n k *g e t (l i n k *h e a d,i n t i)i n t j;l i n k *p;j=l;p=h e a d-n e x t;w h i l e(j n e x t;r e t u r n p;4 .单链表上的插入运算v o i d i n s e r t (l i n k *h e a d,e l e m t y p e x,e l e m t y p e y)在头指针h e a d 所指单链表中，在值为y 的结点之后插入值为x 的结点 l i n k *p,*s;s=n e w l i n k;

49、s-d a t a=x;i f(h e a d-n e x t=N U L L)链表为空 h e a d-n e x t=s;s-n e x t=N U L L;p=L o c a t e (h e a d,y)调用查找算法i f (p=N U L L)c o u t ,插入位置非法”；e l s e s-n e x t=p-n e x t;p-n e x t=s;5 .单链表上的删除运算v o i d d e l e t e(l i n k *h e a d,e l e m t y p e x)在h e a d 为头指针的单链表中,删除值为x 的结点 l i n k *p,*q;q=h e

50、a d;p=h e a d-n e x t;w h i l e(p!=N U L L)&(p-d a t a!=x)q=P；p=p-n e x t;i f (p=N U L L)c o u t ”要删除的结点不存在”；e l s e q-n e x t=p-n e x t;d e l e t e (p);)6.输出单链表若需将单链表按逻辑顺序输出(见图2-1 0),则必须从头到尾访问单链表中每一个结点，v o i d p r i n t(l i n k *h e a d)l i n k *p;p=h e a d-n e x t;w h i l e(p-n e x t!=N U L L)c o