计算机科学是一门研究数据表示和数据处理的科学数据是

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

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

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

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

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

6、与计算科学98级990301刘 丽女数学与应用数学99级990302张会友男信息与计算科学99级990303石宝国男计算机科学与技术99级000801何文颖女计算机科学与技术2000级000802赵胜利男数学与应用数学2000级000803崔文靖男信息与计算科学2000级010601刘 丽女计算机科学与技术2001级010602魏永鸣男数学与应用数学2001级崔文靖8何文颖6李淑芳2刘 丽3，9石宝国5魏永鸣10吴承志1赵胜利7张会有4计算机科学与技术1，5，6，9信息与计算科学2，4，8数学与应用数学3，7，102000级6，7，82001级9，1098级1，2，399级4，5（a）学生信息

7、表（b）姓名索引表（c）专业索引表（d）年级索引表图 1.1 学生信息查询系统中的数据结构例2 八皇后问题。在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。 例3 计划编排问题。一个教学计划包含许多课程，在教学计划包含的许多

8、课程之间，有些必须按规定的先后次序进行，有些则没有次序要求。即有些课程之间有先修和后续的关系，有些课程可以任意安排次序。这种各个课程之间的次序关系可用一个称作图的数据结构来表示，如图1.3所示。有向图中的每个顶点表示一门课程，如果从顶点vi到vj之间存在有向边<vi，vj>，则表示课程i必须先于课程j进行。 由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，可以说数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。图1.2 四皇后问题中隐含的状态树课程编号课程名称先修课程C1

9、计算机导论无C2数据结构C1，C4C3汇编语言C1C4C程序设计语言C1C5计算机图形学C2，C3，C4C6接口技术C3C7数据库原理C2，C9C8编译原理C4C9操作系统C2C1C2C3C6C4C5C9C7C8 12数据结构课程的内容数据结构与数学、计算机硬件和软件有十分密切的关系。数据结构是介于数学、计算机硬件和计算机软件之间的一门计算机科学与技术专业的核心课程，是高级程序设计语言、编译原理、操作系统、数据库、人工智能等课程的基础。同时，数据结构技术也广泛应用于信息科学、系统工程、应用数学以及各种工程技术领域。 方面 层次数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价不同数据结构

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

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

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

13、对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。3 数据对象（data object）是性质相同的数据元素组成的集合，是数据的一个子集。例如，整数数据对象的集合可表示为N0，±1，±2.，字母字符数据对象的集合可表示为C=A,B,Z。4数据结构（data structures） 数据结构定义1：是相互之间存在一种或多种特定关系的数据元素的集合。 形式化定义：数据结构是一个二元组 Data_Structure = (D,R)其中，D是数据元素的有限集合，R是D上关系的集合 数据结构定义2： 按某种逻辑关系组织起来的一批数据（或称带结构的

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

15、构 结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。 存储结构（Storge Structure):数据结构在计算机中的表示(或称映象）称为数据的存储结构，又称为物理结构。四种基本的存储方法： （1）顺序存储方法（顺序存储结构） （2）链接存储方法（链式存储结构） （3）索引存储方法 （4）散列存储方法 同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示

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

17、 C+提供的基本数据类型有：整型、实型、字符型、 逻辑型 例如，高级语言中用到的整数数据类型，是指由32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称。 注：数据类型与数据结构的区别，数据结构强调数据元素之间的逻辑关系。6抽象数据类型（Abstract data type）抽象数据类型（Abstruct Data Type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。抽象数据类型和数据类型实质上是一个概念

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

19、定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。格式：ADT <抽象数据类型名> is Data:<数据描述> Operation:<操作声明> END 例如:给出自然数的抽象数据类型定义. ADT Natural Number is Data: 一个整数的有序子集合，它开始于0，终止于机器能表示的最大整数（MAXINT）。 Operation

20、: 对于所有x,y Natural Number,定义如下操作： add(x,y) 求x+y sub(x,y) 求x-y mul(x,y) 求x*ydiv(x,y) 求x/yend1.2 算法的描述1.2.1算法的概念1算法（algorithm） 通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3有穷性：每条指令的执行次数必须是有限的。（4)确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条

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

22、引起严重后果。高效。有效使用存储空间和有较高的时间效率。1.2.2算法描述 算法可以使用各种不同的方法来描述。最简单的方法是使用自然语言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读。缺点是不够严谨。可以使用程序流程图、N-S图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序还有一个编程的问题。可以直接使用某种程序设计语言来描述算法，不过直接使用程序设计语言并不容易，而且不太直观，常常需要借助于注释才能使人看明白。 用C+描述算法在本教材中，我们将采用C或类C+来描述算法。并且用C描述算法遵循如下规则：（1）所有

23、算法的描述都用C中的函数形式函数类型 函数名（形参及类型说明） 函数语句部分 return(表达式值)； （2）函数中的形式参数有两种传值方式若为一般变量名，则为单向传值，若在变量前面增加“&“符号，则为双向传地址。例如有一个函数为 Void swap(&i, &j,k)则i，j为双向传地址参数，k为单向传值参数。（3）函数的说明部分与函数的实现部分分离在C中，用函数来描述算法时，为使之与面象对象的程序设计相匹配，一般将函数的说明部分与函数的实现部分分离开来。 （4）输入函数C中的输入函数调用为: cin>>变量名。 （5）输出函数C中的输出函数调用为:co

24、ut<<变量名。(6) C+中的类C+对于面向对象程序设计的支持,核心部分就是类的定义。类的定义体现了抽象数据类型的思想，可以支持说明与实现的分离，将抽象数据类型的实现封装在类的内部，使之达到信息隐蔽的目的。1.3 算法分析与度量我们可以从一个算法的时间复杂度与空间复杂度来评价算法的优劣。当我们将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：硬件的速度。例如使用486机还是使用586机。书写程序的语言。实现语言的级别越高，其执行效率就越低。编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。问题的规模。例如，求100以内的素数与

25、求1000以内的素数其执行时间必然是不同的。显然，在各种因素都不能确定的情况下，很难比较出算法的执行时间。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模的函数。时间复杂度一个程序的时间复杂度（Time complexity）是指程序运行从开始到结束所需要的时间。一个算法是由控制结构和原操作构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同的算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本运算的原操作

26、，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行的次数是规模n的某个函数T(n)。许多时候要精确地计算T(n)是困难的，我们引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。定义（大记号）：如果存在两个正常数c和n0，使得对所有的n，nn0，有：f(n) cg(n)则有：f(n) (g(n)例如，一个程序的实际执行时间为T(n)2.7n3+3.8n2+5.3。则T(n)(n3)。使用大记号表示的算法的时间复杂度，称为算法的渐进时间复杂度（Asymptotic Complexity）。通常用(1)表示常数计算时间。常见的渐进时间复杂度有：(

27、1)(log2n)(n)(nlog2n)(n2)(n3)(2n)在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。例分析以下程序段的时间复杂度for (i=1;i<n;i+) y=y+1; for (j=0; j<=(2*n); j+)x+; 常见函数的时间复杂度按数量递增排列及增长率。 常数阶O(1) 对数阶O(log2n) 线性阶O(n) 线性对数阶O(nlog2n) 平方阶O(n2) 立方阶O(n3)

28、k次方阶O(nk) 指数阶O(2n)空间复杂度与时间复杂度类似，空间复杂度是指一程序运行从开始到结束所需的存储量。即算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。本章小结 数据、数据结构等基本概念 数据结构的三个方面的内容 抽象数据类型的概念 线性和非线性结构的逻辑特征 数据存储的四种基本方法 算法、算法的时间复杂度第一章 概论 自测题 一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间的 和运算等的学科。2. 数据结构被形式地定义为（D, R

29、），其中D是 的有限集合，R是D上的 有限集合。3. 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。4. 数据结构按逻辑结构可分为两大类，它们分别是 和 。5. 线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。6 在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 后续结点，其余每个结点有且只有1个后续结点。7. 在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以 。8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 。9数据的存储结构

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

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

32、. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0; 3. x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+; 4. i=1; while(i<=n) i=i*3; 五、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 1. D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 2。D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6

33、,d8),(d4,d5), (d6,d7),(d8,d9) 3。D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)第2章 线性表 线性表是我们要介绍的数据结构中的第一种数据结构，也是比较简单的数据结构，对于线性表的操作是动态的还是静态的在后续的章节里要用到，是学习数据结构的基础。首先看一下什么是线性表。21 线性表的定义及其运算2.1.1 线性表的定义1 线性表的定义线性表（linear_list）是具有相同属性的数据元素的一个有限序列。用

34、二元组表示为： linear_list=(A,R)其中 A=ai 1in,n0,aielemtype R=<ai,ai+1> 1in-1A表示属性相同的数据元素，R代表关系，ai,ai+1>表示有序，也叫有序偶。有了这种关系就表示线性表的数据元素之间是一个有限序列。Elemtype表示一种具体的已知数据类型。为线性表中的数据元素所有可能的数据类型的一个抽象名称。例如：L1=（A，R） =5，38，12，49，63，200，470=某校1971至1977年拥有的计算机的数量L1=(5，38，12，49，63，200，470) L2=（A，R）=“王一”，“王兰”，“王心”，“王

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

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

37、SETNULL（&L）将线性表L置成空表2 求长度 LENGTH（L） 求给定线性表L的长度3 取元素 GET（L，i） 若1ilength(L),则取第i个位置上的元素，否则取得的 元素为NULL。 4求直接前趋 PRI0R（L，X）求线性表L中元素值为X的直接前趋，若X为第一个元素，前驱为NULL5求直接后继 NEXT（L，X） 求线性表L中元素值为X直接后继，若X为最后一个元素，后继为NULL。6定位函数 LOCATE（L，X） 在线性表L中查找值为X的元素位置，若有多个值为X，则以第一个为准，若没有，位置为0。7插入 INSERT（&L，X，i） 在线性表L中第i个位置

38、上插入值为X的元素。8删除 DELETE（&L，i） 删除线性表L中第i个位置上的元素。注意：初始条件、返回值、操作功能是编写一个函数的依据。 引用类型&：给变量起别名。x=y 程序对x进行的任何操作，同时对y也进行操作，反之亦然。因为x,y指向同一存储单元即两个变量使用同一个存储单元。可以用其中的任何一个名字对存储单元进行操作。形参中用&将的值带回到主要函数。例：假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,则对L的一组操作及结果如下：Length(L); /所得结果为5Get(L,i) /所得结果为89Prior(L,x) /所得结果为

39、23Next(L,x) /所得结果为89Locate(L,x) /所得结果为2Insert(&L,y,i) /所得结果为(23,56,88,89,76,18)Delete(&L,i+1) /所得结果为(23,56,88,76,18)以上了解了线性表、线性表的关系以及基本操作。这些基本操作的实现是要有存储作为前提的，线性表在里存储为什么样子，是动态的还是静态的，只有确定了这些才能实现操作，也就是说存储是实现操作的依据。下面介绍两种存储方法。2.2线性表的顺序存储结构一、顺序表结构顺序存储的特点：逻辑关系相邻（ai和ai+1是相邻的）物理位置也相邻存完ai一定要存ai+1线性表的顺

40、序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。这种存储结构的线性表也称为顺序表。它的特点为表中相邻的元素赋以相邻的存储位置。换句话说，以元素在计算机内“物理位置相邻”来表示线性表数据元素之间的逻辑关系。假设线性表中元素为（a1，a2，.,an），设第一个元素a1的内存地址为LOC(a1)（基地址），而每个元素在计算机内占d个存贮单元,则第i个元素ai的地址为 LOC(ai)=LOC(a1)+(i-1)×d (其中1in)由于高级语言中的数组类型具有如下的特点：数组中的元素间的地址是连续的，数组中所有元素的数据类型是相同的。而这与线性表的存储空间结构是类似的。因此，通常

41、都用数组来描述数据结构中的顺序存储结构。 存储的时候即要存储数据元素又要存储数据关系，那么数组把数据元素存储在list,也就存储了关系。用数组存放以后，线性表的长度是数组空间中变化的，用len来表示线性表的长度，并事先预计分配一个足够大的空间maxsize，用一个宏来定义.const int maxsize=maxlen； /maxlen表示线性表允许的最大长度struct sequenlist elemtype amaxsize; /表示线性表（a1，a2，.,an） int len; /len表示当前线性表的实际长度 （可以变化） ；如何来使用？使用方法：首先定义sequenlist L;

42、 int n=7;结构体有两个域：L.a1=a1; L.a2=a2; . L.len;注：结构体类型定义的是一种样子，没有实际的内容。结构体变量是系统实际分配一个空间。变量定义之后，才用实际的空间可以使用。才可以对其两个域进行访问、进行操作。二、顺序表操作的实现1求顺序表的长度length(L)int length(sequenlist L) return L.len;2置空表setnull(&L) void setnull(sequenlist &L) L.len=0;3.遍历线性表：traverlist(&L) 依次访问（输出）表中的元素，且只访问一次。void t

43、raverllist(&L)for(i=1; i<=L.len;i+) cout<<L.ai ;cout<<endl;4删除运算Delete(&L,i)void Delete(sequenlist &L,int i) int j; if(i<1)|(i>L.len) cout<<” position is not correct!”<<endl; else for(j=i+1;j<=L.len;j+) L.aj-1=L.aj; /元素前移 L.len-; /表长度减1 5插入运算Insert( &a

44、mp;L,x,i) void Insert(sequenlist &L,elemtype x,int i) int j;if(L.len>=maxsize-1) cout<<”overflow”<<endl;else if (i<1)|(i>L.len+1) cout<<”position is not correct!”<<endl;else for(j=L.len;j>=i;j-)L.aj+1=L.aj; /元素后移L.ai=x; /插入元素L.len+; /表长度增加1注意逻辑关系的变化 5 定位算法（查找）

45、Locate(L,x)int Locate(sequenlist L, elemtype x) int j=1; while(j<=L.len)&&(L.aj!=x) j+; if(j<=L.len) return j; else return 0; 6 取元素Get(L,i) elemtype Get(sequenlist L,int i) if(i<1)|(i>L.len) return NULL; else return L.ai; . 线性表的链式存贮结构静态存储的特点是用数组的方法来处理，事先定义一个足够大的空间，插入和删除的操作需要不断地移动

46、。效率比较低。线性表的链式存储结构的特点是用一组地址任意的存储单元（可以是连续的，也可以是不连续的）存储线性表的数据元素。因此，为了表示每个数据元素与其直接后继之间的逻辑关系的有序性，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即存储位置）。这两部分信息组成数据元素的存储映象，称为结点。数据元素 + 指针（指示后继元素存储位置） =结点 以“结点的序列”表示线性表-链表。 就是将数据元素存放在结点中，按照前驱和后继的关系用链子将其串起来。在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。线性链表中的结点结构可描述为:其中data 域用来存放

47、结点本身信息，next域用来存放下一个元素地址。单链表可用+描述为:struct link elemtype data; /数据域 link *next; /指针域单链表运算 头插法建立单链表(从左边插入结点)link *hcreat( ) link *s,*p; int i; cin>>i; /输入结点数值，为0时算法结束 p=NULL; while(i) s=new link; s->data=i; s->next=p; p=s; cin>>i; return p;2 尾插法建立单链表(从右边插入结点)link *rcreat( ) link *s,*r

48、,*p; int i; p=r=new link; p->next=NULL; cin>>i; while(i) s=new link; s->data=i;r->next=s; r=s;cin>>i; r->next=NULL; return p; 3 单链表上的查找运算(1) 按值查找Locate(head,x)在单链表head中，查找值为x的结点，若找到，返回它的地址，否则返回NULL。Link *Locate(link *head,elemtype x) link *p; p=head->next; while(p!=NULL)&a

49、mp;&(p->data!=x) p=p->next; return p; (2) 按序号查找get(head,i)在单链表head中查找第i个位置上的元素，若找到，则返回它的地址，否则返回NULL。Link *get(link *head,int i) int j; link *p; j=1; p=head->next; while(j<i)&&(p!=NULL) j+; p=p->next; return p; 4 单链表上的插入运算 void insert(link *head,elemtype x,elemtype y)/在头指针head所指单链表中,在值为y的结点之后插入值为x的结点 link *p,*s; s=new link; s->data=x; if(head->next=NULL) /链表为空 head->next=s; s->next=NULL; p=Locate(head,y) /调用查找算法 if(p=NULL) cout<<”插入位置非法”; else s->next=p->next;p->next=s; 单链表上的删除运算void delete(link *head,elemtype x)