《数据结构》讲义.doc

此文档收集于网络，仅供学习与交流，如有侵权请联系网站删除第一章：绪论课程：数据结构课题：第一章 1.11.4小节（共4个课时）1.1 什么是数据结构1.2 基本概念和术语1.3 抽象数据类型的表现与实现1.4 算法和算法分析目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学会分析算法的时间复杂性和空间复杂性。新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性教学方法：课堂讲解、例题演示，课件演示教学内容及过程：第1-2课时 计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处理的对象的特性及各对象之间存在的关系产生背景。1.1 什么是数据结构 计算机解题步骤：建立数学模型设计解此数学模型的算法编制程序进行测试调整解答。其中建立数学模型的实质：找出操作对象之间的关系。例1. 图书馆书目检索 对应线性关系例2. 博奕树 对应树型关系例3. 交叉路口交通灯管理 对应图状结构。 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。（地位） 1.2 数据结构的基本概念和术语 1. 数据（Data） 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。包括数值、字符、声音、图象等。 2. 数据元素（Data Element） 数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。一个数据元素可由若干个数据项组成（Data Item）。 3. 数据对象（Data Object） 数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N=0， 1， 2， ，字母字符数据对象是集合C=A，B，Z，表1-1所示的学籍表也可看作一个数据对象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复合数据元素（如学籍表），只要性质相同， 都是同一个数据对象。 综上13所述，再分析数据概念： 4. 结构（Data Structure） 数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。 (1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。 (2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。 (3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。 (4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。 线性结构线性表、栈、队、字符串、数组、广义表非线性结构树、 图 数据结构的形式定义： 数据结构是一个二元组 Data_structure=(D,S) 。其中：D为数据结构的有限集，S是D上关系的有限集。例：复数结构Complex=(C,R)其中：C为含两个实数的集合c1,c2； R=P， P是集合C上的一种关系， P=，为有序偶，c1表示复数的实部，c2表示复数的虚部。存储结构 存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。 形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，DM， 即对于每一个d，dD, 都有唯一的mM，使S（D）=m, 同时这个映象必须明显或隐含地体现关系R。 逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。 顺序映象 （顺序存储结构）顺序结构用元素在存储器中的相对位置表示数据元素之间的逻辑关系。 非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针表示元素之间的逻辑关系。 一维数组来描述顺序存储结构，用指针来描述链式存储结构。 运算的集合 数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做数据结构。 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已经实现的数据结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32 768+32 767， 可用的运算符集合为加、 减、 乘、 除、 取模（如C语言中+， -， *， /， %）。 抽象数据类型 ） 数据的抽象 计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、 9.6E3等, 它们是二进制数据的抽象; 使用者在编程时可以直接使用, 不必考虑实现细节。在高级语言中，则给出更高一级的数据抽象，出现了数据类型， 如整型、 实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。可以这样看，高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、树、图等复杂的抽象数据类型。 ） 抽象数据类型 (Abstract Data Type) 抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个ADT定义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT 通常是指由用户定义且用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。 抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：分解、抽象和信息隐藏。 一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现过程隐藏起来。 数学模型抽象数据类型数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据结构是基础，抽象数据类型是中枢。 一个线性表的抽象数据类型的描述如下： ADT Linear-list 数据元素 所有ai属于同一数据对象，i=1，2，n, n0； 逻辑结构 所有数据元素ai（i=1，2，n-1）存在次序关系，ai无前趋，an无后继； 操作设L为Linear-list: Initial(L): 初始化空线性表; Length(L): 求线性表的表长; Get(L, i): 取线性表的第i个元素； Insert(L, i, b): 在线性表的第i个位置插入元素b； Delete(L, i): 删除线性表的第i个元素。） 抽象数据类型实现 第一种情况： 传统的面向过程的程序设计。第二种情况： “包”、 “模型”的设计方法。第三种情况： 面向对象的程序设计（Object Oriented Programming，简称OOP）。 ） ADT的定义 ADT的定义格式不唯一, 我们采用下述格式定义一个ADT: ADT 抽象数据类型名 数据对象: 数据关系: 基本操作: ADT 抽象数据类型名 其中数据对象和结构关系的定义采用数学符号和自然语言描述, 而基本操作的定义格式为: 操作名称 (参数表) 初始条件: 操作结果: 关于参数传递 参数表中的参数有两种：第一种参数只为操作提供待处理数据, 又称值参；第二种参数既能为操作提供待处理数据, 又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件, 操作结果描述操作执行之后, 数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型, 即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”， PASCAL语言用“变参” 实现, C+语言通过“引用型参数”实现, 而C语言用“指针参数”实现。 用标准C语言表示和实现ADT描述时，主要包括以下两个方面: (1) 通过结构体将int、 float等固有类型组合到一起, 构成一个结构类型, 再用typedef为该类型或该类型指针重新起一个名字。 (2) 用C语言函数实现各操作。 基本操作主要有以下几种： (1) 插入： 在数据结构中的指定位置上增添新的数据元素； (2) 删除： 删去数据结构中某个指定数据元素； (3) 更新：改变数据结构中某个元素的值， 在概念上等价于删除和插入操作的组合； (4) 查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)； (5) 排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小的次序排列。 结构化的开发方法与面向对象的开发方法的不同点，结构化的开发方法是面向过程的开发方法， 首先着眼于系统要实现的功能。从系统的输入和输出出发， 分析系统要实现的功能，用自顶向下、逐步细化的方式建立系统的功能结构和相应的程序模块结构。一旦程序功能需要修改， 就会涉及多个模块，修改量大，易于出错，并会引起程序的退化。 作业1：1：理解和掌握几个重要的基本概念：数据结构；抽象数据类型等；2：理解和运用四种逻辑结构；并进行合理的划分。第3-4课时13 抽象数据类型的表示和实现 (1) 预定义常量和类型。 本书中用到以下常量符号，如True、 False、MAXSIZE等，约定用如下宏定义预先定义： define TRUE 1 define FALSE 0 define MAXSIZE 100 define OK 1 define ERROR 0 (2) 本书中所有的算法都以如下的函数形式加以表示， 其中的结构类型使用前面已有的定义。 数据类型 函数名（形式参数及说明） 内部数据说明； 执行语句组； /*函数名*/ 函数的定义主要由函数名和函数体组成，函数体用花括号“”和“”括起来。 函数中用方括号括起来的部分如“形式参数”为可选项， 函数名之后的圆括号不可省略。 (3) 赋值语句。 1、简单赋值; （1）变量名=表达式，它表示将表达式的值赋给左边的变量； （2）变量+， 它表示变量加1后赋值给变量； （3）变量-， 它表示变量减1后赋值给变量。 2、串联赋值#; 变量1=变量2=变量3=变量k=表达式； 3、成组赋值#; （变量1，变量2，变量3， , 变量k)=（表达式1，表达式2， 表达式3， , 表达式k）； 数组名1下标1下标2=数组名2下标1下标2； 4、条件赋值; 变量名=条件表达式？表达式1: 表达式2； (4) 条件选择语句。 if （表达式） 语句； if （表达式） 语句1； else 语句2； (5) 循环语句。 1、for 语句 for (； ； ） 循环体语句； 首先计算表达式1的值， 然后求表达式2的值，若结果非零（即为真）则执行循环体语句，最后对表达式3运算，如此循环， 直到表达式2的值为零（即不成立为假）时为止。 2、while 语句 while (） 循环体语句； while循环首先计算条件表达式的值，若条件表达式的值非零（即条件成立），则执行循环体语句，然后再次计算条件表达式的值， 重复执行，直到条件表达式的值为零（即为假）时退出循环， 执行该循环之后的语句。 3、do-while 语句 do 循环体语句 while (） 该循环语句首先执行循环体语句, 然后计算条件表达式的值， 若条件表达式成立，则再次执行循环体，再计算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。 (6) 输入、 输出语句。 输入语句： 用函数scanf实现； 特别当数据为单个字符时， 用getchar函数实现；当数据为字符串时，用gets函数实现。 输出语句： 用printf函数实现；当要输出单个字符时，用putchar函数实现；当数据为字符串时，用puts函数实现。 其中输入输出函数中的类型部分不做严格要求， 淡化表述。 (7) 其它一些语句。 return 或return： 用于函数结束。 break语句： 可用在循环语句或case语句中结束循环过程或跳出情况语句。 continue语句： 可用在循环语句中结束本次循环过程， 进入下一次循环过程。 exit语句： 表示出现异常情况时， 控制退出函数。 (8) 注释形式。 /*字符串*/、/ 注释句的作用是增强算法的可阅读性，在算法描述中要求在函数首部加上对算法功能的必要注释描述。加注释说明时如果没有涉及到的参量一定是多余的，而涉及到的内容应当作为参量，这实际上是程序设计中的一个素质要求， 希望多加注意。 (9) 一些基本的函数， 例如：max函数： 用于求一个或几个表达式中的最大值；min函数： 用于求一个或几个表达式中的最小值；abs函数： 用于求表达式的绝对值；eof函数： 用于判定文件是否结束； eoln函数： 用于判断文本行是否结束。 ADT举例：对于一个复数 z=x+yi ADT complex 数据对象 D=c1,c2|c1,c2R 数据关系 R1 基本操作: add(z1,z2,sum)； subTracf(z1,z2,difference)； Get_re (z) ； Get_im(z)；ADT complex；1.4 算 法 1. 算法（Algorithm）的定义 Algorithm is a finite set of rules which gives a sequence of operation for solving a specific type of problem. (算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。) 是指令的有限序列，其中每一条指令表示一个或多个操作。 2. 算法的特性 (1) 有穷性：有限步骤之内正常结束， 不能形成无穷循环。 (2) 确定性：算法中的每一个步骤必须有确定含义， 无二义性。 (3)可行性：原则上能精确进行， 操作可通过已实现的基本运算执行有限次而完成。 (4)输入：有多个或0个输入。 (5)输出： 至少有一个或多个输出。 在算法的五大特性中， 最基本的是有限性、 确定性和可行性。 3. 算法设计的要求） 算法的正确性 (1) 所设计的程序没有语法错误； (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。 (4) 程序对于一切合法的输入数据都能产生满足要求的结果。 例如： 要求n个数的最大值问题， 给出示意算法如下： max=0; for（i=1； imax) max=x; 2） 可读性 3） 健壮性 4） 高效率和低存储量 算法、 语言和程序的关系 (1) 算法： 描述了数据对象的元素之间的关系（包括数据逻辑关系、 存储关系描述）。 (2) 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。 自然语言简单但易于产生二义，框图直观但不擅长表达数据的组织结构， 而高级程序语言则较为准确但又比较严谨。 (3) 程序是算法在计算机中的实现（与所用计算机及所用语言有关）。 设计实现算法过程的步骤 找出与求解有关的数据元素之间的关系（建立结构关系）。 确定在某一数据对象上所施加的运算。 考虑数据元素的存储表示。 选择描述算法的语言。 设计实现求解的算法， 并用程序语言加以描述。 对算法作性能评价1. 性能评价 对问题规模和该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。问题规模N对不同的问题其含义不同，对矩阵是阶数， 对多项式运算是多项式项数，对图是顶点个数，对集合运算是集合中的元素个数。 2. 有关数量关系的计算 数量关系评价体现在时间算法编程后在机器中所耗费的时间。 数量关系评价体现在空间算法编程后在机器中所占的存储量。 1） 关于算法执行时间 一个算法的执行时间大致上等于其所有语句执行时间的总和， 对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。 2） 语句频度语句频度是指该语句在一个算法中重复执行的次数。 例1-1 两个nn阶矩阵相乘。 3） 算法的时间复杂度 原操作是指从算法中选取一种对所研究问题是基本运算的操作， 用随着问题规模增加的函数来表征, 以此作为时间量度。 而对于算法分析，我们关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（Order of Magnitude）。在这里， 我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。 所谓算法的时间复杂度， 即是算法的时间量度，记作： T(n)=O(f(n)它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。 一般情况下， 随n的增大，T(n)的增长较慢的算法为最优的算法。 例如： 在下列三段程序段中，给出原操作x=x+1的时间复杂度分析。 （1） x=x+1 ； 其时间复杂度为O(1)， 我们称之为常量阶； （2） for (i=1; i= n; i+) x=x+1; 其时间复杂度为O(n)， 我们称之为线性阶； （3） for (i=1; i= n; i+) for (j=1; j= n; j+) x=x+1; 其时间复杂度为O(n2), 我们称之为平方阶。此外算法还能呈现的时间复杂度有对数阶O(log2n), 指数阶O(2n)等。 4） 数据结构中常用的时间复杂度频率计数 数据结构中常用的时间复杂度频率计数有7个： O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型 O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型 按时间复杂度由小到大递增排列成表1-3（当n充分大时）。 不同数量级的时间复杂度的形状如图1.6所示， 表1-3与图1.6是同一问题的不同表示形式。一般情况下，随n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法， 而避免使用指数阶的算法。 例如： 下列程序段： for (i=1; i n; i+) for (j=i; j= n; j+) x+;有一个二重循环， 语句x+的执行频度为： n+(n-1)+(n-2)+3+2+1 =n(n+1)/2而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。 5） 最坏时间复杂度 算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。 6） 算法的空间复杂度（略）作业2：1:图1.5、P13：算法的5个特征；2:P15：两段程序的语句的频度的分析本章教学总结：学习资料第二章：线性表课程：数据结构课题：第二章 2.12.4小节（共6个课时）2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加目的要求：理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运算的实现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法； 以达到利用基本算法进行较复杂算法设计的目的。新课重点、难点：线性表、 顺序表、链表教学方法：课堂讲解、例题演示，课件演示教学内容及过程：第1-2课时线性结构的特点：在数据元素的非空有限集中， 存在唯一的一个被称为“第一个”的数据元素； 存在唯一的一个被称为“最后一个”的数据元素； 除第一个元素之外，集合中的每个元素均只有一个前驱； 除最后一个元素之外，集合中的每个元素均只有一个后继。 2.1 线性表的类型定义2.1.1 线性表的逻辑结构例如： 英文字母表(A, B, , Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， 每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。 在较为复杂的线性表中，数据元素(data elements) 可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item) 组成， 常被称为一个记录(record) ，含有大量记录的线性表称为文件(file)。数据对象（data object）是性质相同的数据元素集合。 表2-1 车辆登记表线性表(Linear List)是由n (n0)个类型相同的数据元素a1, a2, ， an组成的有限序列，记作（a1, a2, ，ai-1，ai，ai+1， ，an）。这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同情况下可以不同， 它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1, a2, ，ai-1, ai, ai+1, , an）， 表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-1的直接后继。除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。 线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。 线性表的特点可概括如下： 同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。 有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。 有序性：线性表中表中相邻数据元素之间存在着序偶关系。 由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。 2.1.2 线性表的抽象数据类型定义ADT List数据元素： D=ai| aiElemSet, i=1, 2, ，n, n0 ， ElemSet为某一数据对象 关系： | ai, ai+1D，i=1, 2, , n-1 基本操作：（1） InitList（&L） 初始条件： L为未初始化线性表。 操作结果： 将L初始化为空表。 （2） DestroyList(&L)初始条件： 线性表L已存在。 操作结果： 将L销毁。 （3） ClearList(&L)初始条件： 线性表L已存在 。 操作结果： 将表L置为空表。 （4） ListEmpty（L）初始条件： 线性表L已存在。 操作结果： 如果L为空表则返回真， 否则返回假。 （5） ListLength（L） 初始条件： 线性表L已存在。 操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。 （6） LocateElem(L, e,compare() 初始条件： 表L已存在， compare()是数据元素判定函数。 操作结果： 返回L中第1个与e满足关系compare() 的数据元素的位序，如果不存在，返回值为0。 （7） GetElem(L, i,&e) 初始条件： 表L存在， 且1iListLength（L）。 操作结果： 用e返回线性表L中第i个元素的值。 （8） ListInsert (&L, i, e) 初始条件：表L已存在，1iListLength(L)+1。 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 （9） ListDelete (&L, i, &e) 初始条件： 表L已存在且非空， 1iListLength(L)。 操作结果： 删除L的第i个数据元素， 并用e返回其值， L的长度减1。 ADT List 例21Void union (List &La, List Lb) La_len= ListLength (La); Lb_len= ListLength (Lb); For (i=1;i= Lb_len;i+)GetElem (Lb,i,e); If(!LocateElem(La,e,equal) ListInsert(La,+ La_len,e); O(Listlength(LA)* Listlength(LB)例22Void MergeList(List La,List Lb,List &Lc) InitList(Lc); i=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength (Lb); While(i=La_Len)&(j=Lb_len) GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai= bj) ListInsert(Lc,+k, ai); +i; else ListInsert(Lc,+k, bj); +j while (i=La_len) GetElem(La, i+, ai); ListInsert(Lc, +k, ai); while (j=Lb_len) GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); 2.2 线性表的顺序表示和实现 2.2.1 线性表的顺序存储结构 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。 采用顺序存储结构的线性表通常称为顺序表。假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)： loc(ai) =loc(a1)+(i-1)k其中loc(a1)称为基地址。 它是一种随机存取的数据结构。 顺序存储结构可以借助于高级程序设计语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序号相对应(C语言中下标等于序号减1）。线性表的顺序存储结构可用C语言定义如下： #define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct ElemType *elem; /* 线性表占用的数组空间 */ int length； int listsize; SeqList； 2.2.2 线性表顺序存储结构上的基本运算 1. 初始化操作 Status IniList_Sq(SqList &L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem) exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;Return OK; 2. 插入操作 在这种结构中容易实现随机存取第i个数据元素，C语言中数组的下标从0开始，所以ai应在L.elem i-1中存取。 线性表的插入运算是指在表的第i (1in+1)个位置之前插入一个新元素e，使长度为n的线性表 (e1，ei-1，ei，en) 变成长度为n+1的线性表（e1，, ei-1，e，ei，en）。 用顺序表作为线性表的存储结构时， 由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将原表中位置n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点e。当i=n+1时， 是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾即可。 例如：已知线性表 (4, 9, 15, 28, 30, 30, 42, 51, 62)， 需在第4个元素之前插入一个元素“21”，则需要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请注意区分元素的序号和数组的下标。 图2.3 顺序表中插入元素Status ListInsert_sq(sqList &L, int i, ElemType e)If(iL.length+1) return ERROR;If(L.length=L.listsize)newbase=(ElemType*)realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType);If(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK； 插入元素时，时间主要耗费在移动元素上。移动个数取决于插入位置。3. 删除操作 线性表的删除运算是指将表的第i(1in)个元素删去， 使长度为n的线性表(e1，, ei-1，ei，ei+1，en)变成长度为n-1的线性表(e1，, ei-1， ei+1，en)。删除第i个元素（1in时需将从第i+1至第n（共n-i）个元素依次向前移动一个位置。 例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5个元素， 则需将第6个元素到第10个元素依次向前移动一个位置，如图2.4所示。 图2.4 顺序表中删除元素算法描述： Status ListDelete_Sq(sqList &L,int i,ElemType &e)If( (iL.length) ) return ERROR;P=&(L.elemi-1);e=*p; q=L.elem+L.length-1;For(+p; p=q; +p) *(p-1)=*p;-L.Length;return OK;在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1), i=1, 2, ，n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数， 则同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等， 即Q i=1/n, i=1, 2, ，n。删除一个元素所需移动元素的平均次数Edel为 4.在顺序表中查找元素的算法：int LocatElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType)i=1;p=L.elem;While (i=L.length & !(*compare)(*p+,e) +i;If (iLB.elemj， 则当前先将LB.elemj插入到表LC中; 若LA.elemiLB.elemj，则当前先将LA.elemi插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc )Pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe);If (!Lc.elem) exit (OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;While (pa=pa_last & pb=pb_last) If (*pa=*pb) *pc+=*pa+; Else *pc+=*pb+;while(pa=pa_last) *pc+=*pa+;while(pbnext=NULL），则表示单链表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。对于带头结点的单链表L，p=L-next指向表中的第一个结点a1，即p-data=a1，而p-next-data=a2。 其余依此类推。2.3.2 单链表上的基本运算 1. 建立单链表图2.8 头插法建立单链表图示voidCreateList_L(Linklist&L,intn)L=(Linklist) mallo