1、第第1章绪章绪 论论1.1 数据结构的概念数据结构的概念1.2 数据的逻辑结构和存储结构数据的逻辑结构和存储结构1.3 算法算法本章小结本章小结习题一习题一实训实训1-1 算法性能分析算法性能分析【教学目标】通过对本章的学习，熟悉各名词和术语的含义，理解数据结构及其有关的概念，了解算法的基本特征和算法的评价标准，掌握估算算法的时间复杂度的方法。运用计算机对一批数据进行处理时，必须解决好三个方面的问题：第一，根据数据之间的逻辑关系如何组织这批数据？第二，如何将这批数据存储在计算机的存储器中？第三，对于存储在计算机中的这批数据可以进行哪些操作？如何实现这些操作？对同一问题的不同操作方法如何进行评价
2、？这些问题就是数据结构这门课程所要研究的主要问题。1.1 数据结构的概念数据结构的概念1.1.1 基本概念和术语基本概念和术语在阐述数据结构的概念之前，先对数据结构中常用的几个基本概念和术语给出确切的定义。1.数据数据(Data)数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号的集合。换句话说，数据是对客观事物采用计算机能够识别、存储和处理的形式所进行的描述。简而言之，数据就是计算机化的信息。数据一般可分为数值型数据和非数值型数据，如数学中的整数、实数等都是数值型数据，字符、表格、图形、图像和声音等都是非数值型数据。又如对于C源程序，数据概念不仅是源程序所处理的数据，源程序本身
3、也是被C编译程序处理的数据。编译程序相对于源程序是一个处理程序，它加工的数据是字符流的源程序(.c)，输出的结果是目标程序(.obj)；对于链接程序来说，它加工的数据是目标程序(.obj)，输出的结果是可执行程序(.exe)，如图 1.1 所示。图1.1 编译程序示意图2.数据元素数据元素(Data Element)数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小单位。数据元素有时也叫做结点、元素、顶点、记录等。例如：在数据库管理系统中，数据库中的一条记录就是一个数据元素，这条记录中的每一个字段就是构成这
4、个数据元素的数据项，如表1-1所示。表表1-1 学学 籍籍 表表学 号出 生 年 月姓 名性 别籍 贯住 址1011983.11赵 红 玲女河 北北 京记 录数 据 项3.数据对象数据对象(Data Object)数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合=0，1，2，字母字符数据对象是集合C=A，B，Z。表1-1所示的学籍表也可看做一个数据对象。由此可看出，不论数据元素集合是无限集(如整数集)、有限集(如字符集)，还是由多个数据项组成的复合数据元素(如学籍表)，只要性质相同，都是同一个数据对象。4.数据类型数据类型数据类型是一组性质相同的值集合以及定义在这
5、个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构的实例。从这个意义上讲，数据类型是高级语言中允许的变量种类，是程序语言中已经实现的数据结构(即程序中允许出现的数据形式)。在高级语言中，整型类型可能的取值范围是-32 768+32 767，可用的运算符集合为加、减、乘、除、乘方、取模(如C语言中的+、-、*、/、%)。1.1.2 数据结构的定义数据结构的定义对于什么是数据结构，目前还没有一个公认的定义，对数据结构的概念，可以从以下两个角度来理解：一是把数据结构作为一门独立开设的课程，看“数据
6、结构”在计算机专业中的地位、性质、任务以及它研究的内容等；二是把数据结构作为计算机所处理的数据的组织方式来理解。1.“数据结构数据结构”课程课程“数据结构”作为一门独立的课程在国外是从1968年开始设立的，我国从1978年开始，各高等院校才先后开设了这门课程，现在“数据结构”已是计算机专业的一门综合性的专业基础课。它是“操作系统”、“编译原理”、“数据库系统”、“计算机图形学”、“人工智能”等课程的先修课。“数据结构”的研究不仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系，可以说，“数据结构”是介于数学、计算机硬件和计算机软件三者之间的一门综合性课程，可以用一个定义描述如下
7、：“数据结构”是研究非数值计算的程序设计问题中计算机操作对象以及它们的关系和操作的一门学科。2.数据结构的概念数据结构的概念如果从数据元素之间的组织形式来看，可以认为数据结构指的是计算机所处理的数据元素之间的组织形式和相互关系。在任何问题中，数据元素都不是孤立存在的，它们之间必定存在着某种内在的或者是根据需要人为定义的关系，这种关系就是这些数据元素的数据结构。数据结构一般包括以下三个方面的内容：(1)数据元素之间的逻辑关系，即数据的逻辑结构，是用户根据需要而建立起来的。(2)数据元素及其关系在计算机存储器内的表示，即数据的存储结构，又称数据的物理结构。(3)数据的运算，即对数据元素所进行的操作
8、。可以把数据结构定义为：对计算机处理的一批数据，首先按某种逻辑关系把它们组织起来，再按一定的存储表示方式把它们存储在计算机的存储器中，然后给这批数据规定一组操作。1.2 数据的逻辑结构和存储结构数据的逻辑结构和存储结构1.2.1 逻辑结构逻辑结构根据数据元素之间的不同特性，可以把数据的逻辑结构分为四种基本类型：集合、线性结构、树形结构和图形结构。其逻辑结构关系如图1.2所示。1.集合集合集合中的数据元素之间除了“同属于一个集合”的关系外，没有其它任何关系。大街上熙熙攘攘的人群可以看成是一个集合。集合是数据结构的一种特例，本书不予讨论。2.线性结构线性结构线性结构中的数据元素之间存在一对一的线性
9、关系。即除了第一个元素外，其它的每个元素都有且仅有一个直接前驱，除了最后一个元素外，每个元素都有且仅有一个直接后继。火车站长长的购票队列就是线性结构。3.树形结构树形结构树形结构中的数据元素之间存在一对多的层次关系。即每个结点最多只有一个直接前驱，但每个结点都可以有多个直接后继。其中根结点没有前驱结点，叶子结点没有后继结点。军队中师、团、营、连、排的层次结构就是一种典型的树形结构，三军总司令是根，而士兵就是叶子。4.图形结构图形结构图形结构中的数据元素之间存在多对多的任意关系。即各个结点可以有多个直接前驱，也可以有多个直接后继。城市之间四通八达的公路网就是图形结构。有时也可以把数据逻辑结构简单
10、地分为两种类型，即线性结构和非线性结构。非线性结构包括树形结构和图形结构。图1.2 四种基本逻辑结构关系图1.2.2 存储结构存储结构存储结构(又称物理结构)是逻辑结构在计算机中的存储映像，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。逻辑结构与存储结构的关系为：存储结构是逻辑关系的映像与元素本身的映像。逻辑结构是数据结构的抽象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。存储结构可以分为顺序存储结构和非顺序存储结构两大类。顺序存储的特点是将数据元素按其逻辑顺序依次存储在内存中一组地址连续的存储单元中，即逻辑上相邻的结点物理上也必须相邻。非顺序存储则比较
11、灵活，可以将数据分散存储在内存中，即逻辑上相邻的结点物理上不一定相邻。常用的非顺序存储有链式存储、Hash存储和索引存储。1.3 算算 法法1.3.1 算法的概念及描述算法的概念及描述1.算法算法(Algorithm)简单地说，算法就是解决特定问题的方法。严格地说，算法是由若干条指令组成的有穷序列，其中每条指令表示计算机的一个或多个操作。例如：将一组给定的数据由小到大进行排序，解决的方法有若干种，而每一种排序方法就是一种算法。一个算法必须具有以下五个特性：(1)有穷性。一个算法在执行有限条指令后必须要终止，且每条指令都要在有限时间内完成。不能形成无穷循环。(2)确定性。算法中每条指令必须有确切
12、的含义，不会产生二义性(3)可行性。算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。(4)输入。一个算法有零个或多个的输入，这些输入取决于某个特定的对象的集合。(5)输出。一个算法有一个或多个结果输出。算法和程序有所不同，程序可以不满足上述的有穷性。例如，Windows操作系统在用户未操作之前一直处于“等待”的循环中，直到出现新的用户操作为止。2.算法、语言和程序的关系算法、语言和程序的关系(1)算法。算法描述了数据对象的元素之间的关系(包括数据逻辑关系和存储关系)。(2)语言。算法可用自然语言、框图或高级程序设计语言进行描述。自然语言简单但易于产生二义性，框图直观但不擅长表
13、达数据的组织结构，而高级程序语言则较为准确且比较严谨。(3)程序。程序是算法在计算机中的实现(与所用计算机及所用语言有关)。1.3.2 算法的评价标准算法的评价标准对于一个特定的问题，采用不同的存储结构，其算法描述一般是不相同的，即使在同一种存储结构下，也可以采用不同的求解策略，从而有许多不同的算法。那么，对于解决同一问题的不同算法，选择哪一种算法较为合适，以及如何对现有的算法进行改进，从而设计出更好的算法，这就是算法评价问题。评价一个算法的优劣主要有以下几个标准：1.正确性正确性一个算法能否正确地执行预先的功能，这是评价一个算法的最重要也是最基本的标准。其要求是：(1)所设计的程序没有语法错
14、误。(2)所设计的程序对于几组输入数据能够得出满足要求的结果。(3)所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。(4)程序对于一切合法的输入数据都能产生满足要求的结果。例如，求5个数的最大值问题，给出示意算法如下：max=0;for(i=1;imax)max=x;printf(%f,max);表面上看来该算法是正确的，输入10.1、2.5、-3.4、-6.5、8.4验证，结果也正确，可是当输入数据全部是负数的时候，输出结果却是0，所以该算法并不正确。2.可读性可读性算法主要是为了人的阅读与交流，其次才是机器执行。即使算法已转变成机器可执行的程序，也需考
15、虑人能较好地阅读理解。可读性好有助于人对算法的理解，这既有助于对算法中隐藏错误的排除，也有助于算法的交流和移植。3.健壮性健壮性算法应具有很强的容错能力，即算法能对非法数据的输入进行检查和处理，不会因非法数据的输入而导致异常中断或死机等现象。4.运行时间运行时间运行时间是指算法在计算机上运行所花费的时间，它等于算法中每条语句执行时间的总和。对于同一个问题如果有多个算法可供选择，应尽可能选择执行时间短的算法，一般来说，执行时间越短则算法的效率越高、性能越好。5.占用空间占用空间占用空间是指算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间
16、和算法运行过程中临时占用的存储空间。算法占用的存储空间是指算法执行过程中所需要的最大存储空间。对于一个问题如果有多个算法可供选择，应尽可能选择存储量需求低的算法。实际上，算法的时间效率和空间效率经常是一对矛盾体，相互抵触，有时增加辅助的存储空间可以加快算法的运行速度，即用空间换取时间；有时因为内存空间不够，必须压缩辅助的存储空间，从而降低了算法的运行速度，即用时间换取空间。通常把算法在运行过程中临时占用的存储空间的大小叫做算法的空间复杂度。算法的空间复杂度比较容易计算，它主要包括局部变量所占用的存储空间和系统为实现递归所使用的堆栈占用的存储空间。1.3.3 算法的时间复杂度算法的时间复杂度一个
17、算法的运行时间是该算法中每条语句执行时间的总和，而每条语句的执行时间是该语句的执行次数(也叫语句频度)与执行一次该语句所需时间的乘积。由于同一条语句在不同的机器上执行所需的时间是不相同的，也就是说执行一条语句所需的时间与具体的机器有关，因此要想精确地计算各种语句执行一次所需的时间是比较困难的。实际上，为了评价一个算法的性能，我们只需计算算法中所有语句执行的总次数即可。任何一个算法最终都要被分解成一系列基本操作(如赋值、转向、比较、输入、输出等)来具体执行，每一条语句也要分解成具体的基本操作来执行，所以算法的运行时间也可以用算法中所进行的基本操作的总次数来估算。在一个算法中，进行简单操作的次数越
18、少，其运行时间也相对越少。为了便于比较同一问题的不同算法，也可以用算法中的基本操作重复执行的频度作为算法运行时间的度量标准。通常把算法中的基本操作重复执行的频度称为算法的时间复杂度。算法中的基本操作一般是指算法中最深层循环内的语句，因此，算法中基本操作重复执行的频度T(n)是问题规模n的某个函数f(n)，记作：T(n)=O(f(n)。其中“O”表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，或者说，用“O”表示数量级(Order of Magnitude)的概念。例如，若T(n)=2n2+3n+1,则2n2+3n+1的数量级与n2的数量级相同，所以T(n)=O(n2)。如果
19、一个算法没有循环语句，则算法的基本操作的执行频度与问题规模n无关，记作O(1)，也称常数阶。如果一个算法只有一重循环，则算法的基本操作的执行频度随问题规模n的增大而呈线性增大关系，记作O(n)，也称做线性阶。按数量级递增排列，常见的时间复杂度有：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2)，平方阶O(n2)，立方阶O(n3)，k次方阶O(nk)，指数阶O(2n)。随着问题规模n的不断增大，上述时间复杂度也不断增大，算法执行效率依次降低。下面举例说明计算算法时间复杂度的方法。例例1.1 分析以下程序段的时间复杂度。for(i=1;in;i+)y=y+1;fo
20、r(j=0;j=(2*n);j+)x+;解：该程序段中语句的频度是n-1，语句的频度是(n-1)(2n+1)=2n2-n-1，则程序段的时间复杂度T(n)=(n-1)+(2n2-n-1)=2n2-2=O(n2)。例例1.2 分析以下程序段的时间复杂度。i=1;while(i=n)i=i*2;解解：该程序段中语句的频度是1，设语句的频度为f(n)，则有2f(n)n，即f(n)log2n,取最大值f(n)=log2n，所以该程序段的时间复杂度T(n)=1+f(n)=1+log2n=O(log2n)。例例1.3 分析以下程序段的时间复杂度。a=0,b=1;for(i=2;i=n;i+)s=a+b;b
21、=1;a=s;解解：该程序段中语句的频度是2，语句、的频度都是n-1，则该程序段的时间复杂度T(n)=2+3*(n-1)=3n-1=O(n)。例例1.4 分析下列算法的时间复杂度。prime(int n)int i=2;while(n%i)!=0&i*1.0sqrt(n)printf(%d是一个素数n,n);else printf(%d不是一个素数n,n);解解：从上面的四个例题可以看出，算法的时间复杂度是由嵌套最深层语句的频度决定的。prime函数嵌套最深层语句是，显然它的频度由条件(n%i)!=0&i*1.0sqrt(n)中的i*1.0sqrt(n)决定，即执行频度小于sqrt(n)，所以
22、其时间复杂度是T(n)=()。n例例1.5 下面是求两个nn阶矩阵乘法C=AB的算法，分析该算法的时间复杂度。#define MAX 100void maxtrixmult(int n,float aMAXMAX,bMAXMAX,float cMAXMAX)int i,j,k;float x;for(i=1;i=n;i+)for(j=1;j=n;j+)x=0;for(k=1;k=n;k+)x+=aik*bkj;cij=x;解解：该算法中嵌套最深层语句是，其频度是n3，则该算法的时间复杂度T(n)=O(n3)。本本 章章 小小 结结本章主要介绍了数据结构及其有关的概念，包括数据、数据元素、数据对
23、象、数据类型、数据结构、逻辑结构、存储结构和算法等基本概念。数据结构一般包括三个方面的内容：数据的逻辑结构、数据的存储结构以及对数据元素所进行的操作。根据不同的抽象层次，数据结构可分为逻辑结构和存储结构。数据的逻辑结构是指数据结构中数据元素之间的逻辑关系，是用户根据需要而建立起来的。根据数据元素之间的不同特性，我们可以把数据逻辑结构分为集合、线性结构、树形结构和图形结构四种基本类型。集合中的数据元素之间除了“同属于一个集合”的关系外，没有其它任何关系，它是数据结构的一种特例；线性结构中的数据元素之间存在一对一的线性关系；树形结构中的数据元素之间存在一对多的层次关系；图形结构中的数据元素之间存在
24、多对多的任意关系。有时我们也可以把数据逻辑结构分为两种类型：线性结构和非线性结构。非线性结构包括树形结构和图形结构。数据的存储结构是指数据元素在计算机的存储器中的存储方式。一般来说，存储结构有顺序存储和非顺序存储两种基本类型，其中非顺序存储中常用的有链式存储、Hash存储和索引存储。算法是解决特定问题的方法，是由若干条指令组成的有穷序列。一个算法应具有五个基本特征：有穷性、确定性、可行性、输入和输出。评价一个算法的标准主要有五个方面：正确性、可读性、健壮性、运行时间和占用的存储空间。习习 题题 一一一、单选题一、单选题1.下列四种基本逻辑结构中，数据元素之间关系最弱的是 ，队列属于 。A.集合
25、 B.线性结构 C.树形结构D.图形结构2.线性结构各数据元素之间存在着 的关系，图形结构数据元素之间存在 的关系。A.无关 B.一对一 C.一对多 D.多对多3.在数据结构中，从逻辑上可以把数据结构分成 。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构4.算法中的基本操作重复执行的频度称为算法的 ；除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称为算法的 。A.时间复杂度B.空间复杂度 C.硬件复杂度D.软件复杂度5.算法分析的目的是 ，算法分析的两个主要方面是 。A.找出数据结构的合理性 B.研究算法中的输入和输出的关系
26、C.分析算法的效率以求改进 D.分析算法的易懂性和文档性A.空间复杂度和时间复杂度 B.正确性C.可读性和文档性 D.数据复杂性和程序复杂性6.计算机算法指的是 ，它必具备输入、输出和 等五个特性。A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法 。A正确 B.不正确8.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 。A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续都可以
27、二、填空题二、填空题(将正确的答案填在相应的空中将正确的答案填在相应的空中)1.数据逻辑结构包括集合、和 四种类型，树形结构和图形结构统称为 。2.线性结构中，第一个结点 前驱结点，其余每个结点有且仅有 个直接前驱结点；最后一个结点 后继结点，其余每个结点有且仅有 个直接后继结点。3.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后继结点可以 。4.在图形结构中，每个结点的前驱结点数和后继结点数可以 。5.线性结构中元素之间存在 关系，树形结构中元素之间存在关系，图形结构中元素之间存在 关系。6.算法的五个重要特性是 、。7.下面程序段的
28、时间复杂度是 。for(i=0;in;i+)for(j=0;jm;j+)aij=0;8.下面程序段的时间复杂度是 。i=s=0;while(sn)i+;s+=i;9.下面程序段的时间复杂度是 。s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=bij;sum=s;10.下面程序段的时间复杂度是 。i=1;while(i=n)i=i*3;实训实训1-1 算法性能分析算法性能分析【实训目的实训目的】1.加深对算法评价标准的理解。2.掌握时间复杂度的分析方法。【实训要求实训要求】1.有一个数组，编程实现：(1)从键盘输入元素值。(2)找出数组元素的最大值和最小值。(3)求数组元素
29、的平均值。(4)求出所有小于平均值的元素的个数，并输出其下标和值。2.分别编写两个程序，要求：(1)编程1：分步实现上述功能。(2)编程2：以最高效率实现上述功能。3.从可读性和时间复杂度上分别对两个算法进行性能分析。【算法分析算法分析】1.分步实现四个功能需要四个循环；2.为提高效率，可在一个循环中实现输入、求最大值、求和的功能，第四个功能必须建立在求出平均值的基础上，要另外使用一个循环来完成。【程序清单程序清单】算法一：#include#define M 10/*如要修改数组大小，不用修改程序其它部分*/main()int aM,i,max,min,sum,count=0;float av
30、g;if(M=0)return(0);/*防止出现求平均值时除数为0的情况，保证算法健壮*/for(i=0;iM;i+)/*输入元素值*/scanf(%d,&ai);max=min=a0;for(i=1;iM;i+)/*找出数组元素的最大值和最小值*/if(maxai)min=ai;sum=0;for(i=0;iM;i+)/*求和*/sum+=ai;avg=(float)sum/M;/*求平均*/printf(max=%d,min=%d,average=%fn,max,min,avg);printf(dataaverage:n);for(i=0;iM;i+)/*找出所有小于平均值的元素并计数*
31、/if(aiavg)count+;printf(No.%d=%dn,i,ai);printf(%d dataaveragen,count);算法二：#include#define M 10main()int aM,i,max,min,sum,count=0;float avg;if(M=0)return(0);/*防止出现求平均值时除数为0的情况*/scanf(%d,&a0);max=min=sum=a0;for(i=1;iM;i+)/*边输入边求和，并进行比较，求最大值和最小值*/scanf(%d,&ai);sum+=ai;if(maxai)min=ai;avg=(float)sum/M;p
32、rintf(max=%d,min=%d,average=%fn,max,min,avg);printf(dataaverage:n);for(i=0;iM;i+)if(aiavg)count+;printf(No.%d=%dn,i,ai);printf(%d dataaveragen,count);第第2章线章线 性性 表表2.1 线性表的概念及运算线性表的概念及运算2.2 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表2.3 线性表的链式存储结构线性表的链式存储结构链表链表本章小结本章小结习题二习题二实训实训2-1 顺序表的操作顺序表的操作实训实训2-2 链表的操作链表的操作【教学目标
33、】通过本章的学习，了解线性表的逻辑结构特征；熟练掌握顺序表和链表的描述方法、特点及有关概念；重点掌握顺序表上的插入和删除算法以及链表的建立、查找、插入和删除算法；掌握从时间和空间的角度综合比较顺序表和链表的不同特点及其适用场合。2.1 线性表的概念及运算线性表的概念及运算2.1.1 线性表的定义线性表的定义线性表(Linear List)是由n(n0)个类型相同的数据元素a1,a2,，an组成的有限序列，记作(a1,a2,，ai-1，ai，ai+1，an)。其中a1为第一个元素，又称做表头元素，an为最后一个元素，又称做表尾元素。线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。这里
34、的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。一个线性表也可以用一个标识符来命名，如：L=(a1,a2,ai-1,ai,ai+1,an)线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表(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。例
35、如，大写的英文字母表(A，B，C，Z)就是一个线性表，表中的每一个字母就是一个数据元素；又如，一个单位所有职工的电话号码表也是一个线性表，表中的每一行就是一个数据元素；再如，一个班上所有学生的成绩表也是一个线性表，表中的每一行是一个数据元素，每个数据元素又是由学号、姓名、成绩等数据项组成的。线性表的特点可概括如下：(1)同一性。线性表由同类数据元素组成，每一个ai必须属于同一数据对象。(2)有穷性。线性表由有限个数据元素组成，表长度就是表中数据元素的个数。(3)有序性。线性表中相邻数据元素之间存在着序偶关系。由此可看出，线性表是一种最简单的数据结构，数据元素之间由一前驱一后继的直观有序的关系确
36、定；线性表又是一种最常见的数据结构，矩阵、数组、字符串、堆栈、队列等都符合线性条件。2.1.2 线性表的基本运算线性表的基本运算线性表是一种最简单的数据结构，可以根据需要改变线性表的长度，也可以对线性表中的任何元素进行访问，可以在线性表中的任何位置插入和删除元素，还可以将两个表连接成一个线性表或者把一个线性表拆分成两个或多个线性表。一般地，可以对线性表进行下列运算：(1)初始化：InitList(L)。操作前提：L为未初始化线性表。操作结果：将L初始化为空表。(2)销毁表：DestroyList(L)。操作前提：线性表L已存在。操作结果：释放L空间，将L销毁。(3)清空表：ClearList(
37、L)。操作前提：线性表L已存在。操作结果：将表L置为空表。(4)判断表是否为空：EmptyList(L)。操作前提：线性表L已存在。操作结果：如果L为空表则返回真，否则返回假。(5)求长度：ListLength(L)。操作前提：线性表L已存在。操作结果：如果L为空表则返回0，否则返回表中的元素个数。(6)查找元素：Locate(L,e)。操作前提：表L已存在，e为合法元素值。操作结果：如果L中存在元素e，则将“当前指针”指向首次找到的其值为e的元素所在位置并返回真，否则返回假。(7)取元素：GetData(L,i,*e)。操作前提：表L存在，且i值合法，即1iListLength(L)。操作结
38、果：用e返回线性表L中第i个元素的值。(8)插入元素：InsertList(L,i,e)。操作前提：表L已存在，e为合法元素值，且1iListLength(L)+1。操作结果：在L中第i个位置插入新的数据元素e，L的长度加1。(9)删除元素：DeleteList(L,i,*e)。操作前提：表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。(10)显示线性表：Display(L)。操作前提：线性表L已存在且不为空。操作结果：依次显示表中所有元素的值。线性表在计算机内有两种基本的存储结构，即顺序存储结构和链式存储结构。对于不同的存储结
39、构，实现上述基本操作的算法也不相同。下面将分别讨论线性表的两种基本存储结构以及在不同的存储结构下实现上述基本操作的算法。2.2 线性表的顺序存储结构线性表的顺序存储结构顺序表顺序表2.2.1 顺序存储结构的特点顺序存储结构的特点线性表的顺序存储结构简称顺序表(Sequential List)，它是线性表中最简单、最常用的存储结构，如图2.1所示。线性表的顺序存储方式是将线性表中的数据元素按其逻辑顺序依次存储在内存中一组地址连续的存储单元中。在顺序存储方式中，线性表中数据元素的逻辑顺序与在存储器中的物理顺序是完全一致的，即线性表中的第i个元素(2in)的存储位置紧接在第i-1个元素的后面。假设线
40、性表中的每个数据元素需占用k个存储单元，且第一个数据元素a1在存储器中的起始地址为Loc(a1)，则线性表中的第i个数据元素ai在存储器中的起始地址为：Loc(ai)=Loc(a1)+(i-1)k图2.1 线性表的顺序存储结构示意图由此可见，由于逻辑上相邻的元素其存储的物理位置也是相邻的，因此无需为表示结点间的逻辑关系而增加额外的存储空间，并且只要知道了线性表在存储器中的起始地址，就可以计算出线性表中任何一个数据元素的存储地址，也就是说，线性表的顺序存储结构是一种随机存取的存储结构。但是，顺序存储结构也有一些不方便之处，主要表现在：(1)数据元素最大个数需预先确定，使得高级程序设计语言编译系统
41、需预先分配相应的存储空间。(2)插入与删除运算的效率很低。在插入和删除操作时需移动大量数据，这对于插入和删除操作频繁的线性表来说，系统的运行速度难以提高。(3)顺序存储结构的线性表的存储空间不便于扩充。当一个线性表分配顺序存储空间后，如果线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。在C语言中，定义了一个数组就意味着定义了一块可供用户使用的地址连续的存储空间，该存储空间的起始地址就是用这个数组名表示的地址常量。所以，线性表的顺序存储结构可以用数组来实现，数组的基本类型就是线性表中数据元素的类型，数组的元素个数要大于线性表的长度。线性表的第一个元素存储在数组的起始位置上，线性
42、表的第二个元素紧接着存储在第一个元素的后面，其余类推。顺序表可以用C语言描述如下：#define Elemtype int/*此处假定数据元素为int型*/#define MAXSIZE 50/*顺序表的最大元素个数*/typedef struct ListElemtype listMAXSIZE;/*顺序表元素类型为Elemtype，用数组list存储*/int size;/*线性表的长度*/SeqList;2.2.2 顺序表的基本操作顺序表的基本操作 在2.1节对线性表的一些基本操作做了简要的介绍，下面进一步讨论：当一个线性表按顺序存储方式存储时，如何用C语言实现这些基本操作。(1)初始化
43、表：InitList(L)。将顺序表初始化为一张空表，只要将size成员设置为0即可。要清空顺序表L，只要将size成员设置为0即可。void initList(SeqList*p)p-size=0;(2)求长度：ListLength(L)。顺序表L的长度实际上就是size成员的值。int listLength(SeqList*p)return(p-size);(3)取元素：GetData(L,i)。getData(SeqList*p,int i,Elemtype*e)if(ip-size)/*判断i是否超出顺序表的范围*/printf(位置不正确n);else *e=p-listi-1;(4
44、)查找：Locate(L,e)。int locate(SeqList*p,Elemtype e)int i=0;/*数组下标从0开始，但数据元素在表中的序号从1开始*/while(isize&p-listi!=e)i+;if(i=p-size)return(0);/*返回值为e在表中的序号，为0时查找失败*/elsereturn(i+1);(5)插入元素：InsertList(L,x,i)。用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将原表中位置n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点e。当
45、i=n+1时，是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾即可。void insertList(SeqList*p,int i,Elemtype e)int j;if(ip-size+1)/*检查i的合法性*/printf(插入位置不正确n);else p-size+;for(j=p-size-1;j=i;j-)/*元素向后移，腾出第i个位置*/p-listj=p-listj-1;p-listj=e;/*将元素x插入第i个位置*/(6)删除元素：DeleteList(L,i)。一般情况下，删除第i(1in)个元素时，需将第i+1至第n(共n-i)个元素依次向前移动一个位置
46、。void deleteList(SeqList*p,int i)int j;if(ip-size|i1)/*检查i的合法性*/printf(删除位置不正确n);elsefor(j=i-1;jsize-1;j+)/*结点向前移动，覆盖被删除的结点*/p-listj=p-listj+1;p-size-;(7)显示线性表：Display(L)。当线性表不为空时，顺序显示线性表的元素值。display(SeqList*p)int j;if(p-size=0)printf(该表为空表/n);elseif(p-size=1)/*只有一个结点的情况*/printf(%d,p-list0);else /*有
47、一个以上的结点*/for(j=0;jsize;j+)printf(%d,p-listj);printf(n);2.2.3 顺序表的应用举例顺序表的应用举例例例2.1 求集合A和集合B的并集C。如A=(2,4,6,7,9)和B=(1,5,7,8)的并集为C=(2,4,6,7,9,1,5,8)。算法分析：用两个顺序表La 和Lb分别表示集合A和B。求集合A和集合B的并集就是将La和Lb合并成一个表，合并后仍用La表示。这就要对La和Lb进行如下操作：将存在于线性表Lb中而不存在于线性表La中的数据元素插入到线性表La中。这只要从线性表Lb中依次取得每个数据元素，并根据取得的数据元素值在线性表La中
48、进行查找，若不存在，则插入到La的最后，否则不插入。基于前述的结点定义和顺序表操作函数，设计的合并算法用C语言描述如下：void setUnion(SeqList *La,SeqList *Lb)/*将所有在Lb中但不在La中的元素插入到La中 */int i,n,m;Elemtype e;n=listLength(La);m=listLength(Lb);/*求La和Lb的长度*/for(i=1;i=m;i+)getData(Lb,i,&e);/*取Lb中第i个元素赋给e*/if(!locate(La,e)insertList(La,+n,e);/*如果元素e不在La中，则将e插入La的最后
49、*/例2.2 已知线性表La和Lb中的数据元素按非递减有序排列，将La和Lb表中的数据元素合并为一个新的线性表Lc，Lc中的数据元素仍按非递减有序排列，并要求不破坏La表和Lb表。如La=(2,4,6,7,9)，Lb=(1,5,7,8)，合并后为Lc=(1,2,4,5,6,7,7,8,9)。算法分析：Lc中的数据元素或者是La中的数据元素，或者是Lb中的数据元素，则只要先将Lc置为空表，然后将La或Lb中的元素逐个插入到Lc中即可。设两个指针i和j分别指向La中的某个元素a和Lb中的某个元素b，当ab时，则将元素a插入到Lc的最后，否则将元素b插入到Lc的最后。指针i和j的初值均为1，在所指元
50、素插入Lc后，如果插入的是La中的元素，则i的值加1，否则j的值加1。如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表Lc中。算法用C语言描述如下：void mergel(SeqList*La,SeqList*Lb,SeqList*Lc)int i,j,k;Elemtype a,b;int La_length,Lb_length;i=j=1;k=0;La_length=listLength(La);Lb_length=listLength(Lb);/*取表La,Lb的长度*/initList(Lc);/*初始化表Lc*/while(i=La_length&j=
