第二章 线性表内容概述线性结构是每一个有意义的程序基本都使用的一种数据结构，也是最简单的数据结构。那么，线性结构如何表示与实现？本章从线性表的抽象数据类型定义、线性表的顺序存储及实现算法、线性表的链式存储及算法实现等三个方面阐述该问题。重点与难点重点为顺序表和单链表的描述和插入、删除运算以及算法的效率分析。难点为单链表的插入、删除运算和链表的应用。思考1线性结构与非线性结构的根本区别是什么？2线性表有哪两种存储结构，各有哪些优缺点？3在单链表和双向链表中，能否从当前结点出发访问任一结点？4当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用何种存储结构为宜？当经常进行的是插入和删除操作时，则应采用存储结构为宜？5在单链表中设置头结点有何作用？6有一个单链表L（至少有1个结点），编写一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。7有一个单链表，其结点的元素值以非递减有序排列，其结点的元素值有可能相同，编写一个算法删除单链表中多余的元素值相同的结点。第一节线性表的类型定义线性表示最常用且最简单的一种数据结构。了解线性表的结构特点、掌握线性表抽象类型定义是运用线性结构解决具体应用问题的基础。1.线性表定义、线性表的结构特点所谓线性表（Linear_List），就是n（n0）个数据元素的集合a1,a2,an，这些数据元素之间有逻辑上的线性关系。线性表结构的特点是：当数据元素集合为非空时（即n0），则（1）有且仅有一个元素作为该结构的第一个元素，即a1；（2）有且仅有一个元素作为该结构的最后一个元素，即an；（3）当1KN时，第k个元素ak有且仅有一个直接前驱，即ak-1，有且仅有一个直接后继，即ak+1；另外，a1的后继为a2，a1无前驱，an的前驱为an-1，an无后继。具有n个元素的线性表，n称为线性表的长度。当长度n为0时，线性表称为空表。当n0时，线性表中每个数据元素ai的位置称为ai在线性表中的位序。线性表中每个数据元素在不同的情况下，可以是一个数或一个符号，也可以是一篇文章，甚至是图片等其他更复杂的信息。例如，2到20的所有质数：（2，3，5，7，11，13，17，19）是一个线性表，表中的数据元素是单个的整数。又如，一个班级的学生姓名集合：（李帅，张伟，王明）表中的数据元素是字符串。在第一章所举的例子中，航班信息表为稍复杂的线性表，一个数据元素可以由若干个数据项（Item）组成。该线性表中的元素，常称为数据记录（DataRecord），简称记录，它是数据处理领域组织数据的基本单位。在日常生活中，学生学籍表、职工档案表、图书馆书目表、医院病历表、库存账目表等都可称为线性表。对于线性表，我们可以按照需求来增加或缩减它的长度，即进行插入或删除操作，也可以对表中的元素进行查找或访问等操作。2.线性表抽象类型定义线性表的抽象数据类型定义如下：ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：CreatList(&L)操作结果：生成一个空的线性表L。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。ListInsert(&L,i,e)初始条件：线性表L已存在，1iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。GetElem(L,i,&e)初始条件：线性表L已存在，1iListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ADTList对于以上定义的抽象数据类型线性表，除了对其进行的基本操作外，还可进行一些更复杂的操作。如：对线性表进行排序；在一个有序的线性表中插入元素；将两个或两个以上有序的线性表归并成为一个有序的线性表等。这些复杂的操作可建立在基本操作的基础上完成，即它们可通过调用基本操作来实现。若操作环境或操作要求发生变化（例如，存储结构的变化），只需要修改基本操作的实现算法，而通过调用基本操作实现的其它算法则不必修改或只做很少的修改，这在一定程度上可以达到软件模块复用的目的。第二节线性表的顺序表示和实现顺序存储结构是线性表存储结构的选择之一。当线性表很少涉及插入和删除操作时，优先选择顺序结构表示线性表。1、顺序表数据类型定义顺序表数据类型定义线性表的顺序表示是利用一组地址连续的内存空间依次存储线性表的各个数据元素，即以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。因为顺序存储结构是一种随机存取的存储结构，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序存储结构所需要的存储空间。首先定义一个指针表示存储空间的基地址，为了保存线性表的长度需要定义一个整型变量，此外为了指示顺序表当前分配的存储空间大小还需要定义一个整型变量，即当前线性表的最大容量。所需要的具体数据类型描述如下：#defineMAXLEN100#defineLIST_INCREASE10/线性表存储空间的动态分配增量typedefstructElemType*list;/线性表的存储空间的基地址intlength;/线性表的当前长度intmaxsize;/线性表当前分配的存储容量List_Sq;结构体类型List_Sq用于实现线性表的动态分配顺序存储结构。由于存储空间为动态分配，在对线性表进行插入等操作时，若原有的存储空间已满而不能满足进一步操作，可进行空间再分配，存储空间的增加量用LIST_INCREASE表示。下面我们将给出各种典型的线性表操作的算法。2、顺序表的生成算法生成线性表线性表的生成算法主要是为其准备所需要的存储空间（这可通过malloc函数动态申请空间实现），同时为参数L的成员L.list、L.length、L.maxsize赋以相应的值。StatusCreatList_S(List_Sq&L)/构造一个空的线性表LL.list=(ElemType*)malloc(MAXLEN*sizeof(ElemType);if(!L.list)exit(OVERFLOW);/若存储空间分配失败，则退出程序L.length=0;/初始化表的长度为0L.maxsize=MAXLEN;/初始化表的存储容量returnOK;/初始化成功/CreatList_S算法2-1线性表的生成算法3、返回线性表中第i个元素值的算法返回线性表中第i个元素值的算法在顺序存储线性表的连续单元中，第i个元素位于地址从L.list向后偏移i1的位置上（或处于L.list为基地址的连续单元中，下标为i1的位置上），我们可直接通过下标返回该元素的值。本算法的时间复杂度为O(1)。StatusGetElem_S(List_SqL,inti,ElemType&e)if(iL.length)returnERROR;/若i为无效值，返回错误e=L.listi1;/通过参数e返回第i个元素值returnOK;/GetElem_S算法2-2返回线性表中第i个元素的值4、线性表的插入算法在线性表的第i个位置插入元素该操作是指在线性表的第i个位置之前插入新的数据元素，插入后线性表的长度增加1个单位，插入的元素分别与原线性表的第i1个元素、第i个元素在逻辑上是相邻的关系。由于顺序存储结构是通过元素之间存储位置的关系来反映逻辑关系，为了完成插入操作，满足插入元素与其前驱元素、后继元素之间的相邻关系，我们需要把原线性表第i个到第n个元素依次向后移动一个单位。如图2.2所示，在第4个和第5个元素之间插入元素，需要将第5个到第7个元素依次向后移动一个单位。StatusListInsert_S(List_Sq&L,inti,ElemTypee)if(iL.length+1)returnERROR;/若i为无效值，返回错误if(L.length=L.maxsize)/若存储容量已满，则增加分配空间newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/若增加分配空间失败，退出程序L.list=newbase;/新基址L.maxsize+=LIST_INCREASE;/存储容量增加/ifq=&(L.listi1);/插入位置。q=L.list+i1;也可。for(p=&(L.listL.length1);p=q;p)/p=L.list+L.Length1;也可。*(p+1)=*p;/将插入元素位置之后的元素依次后移一个位置*q=e;/插入元素e+L.length;/线性表长度增加1returnOK;/插入操作成功/ListInsert_S算法2-3线性表的插入算法该算法的主要操作和影响算法效率的步骤为：将插入位置其后的元素依次向后移一个位置。执行此算法时，假定线性表的长度为n，当向第i个位置（1in+1）插入元素时，需要后移ni+1个元素，所以进行每次插入平均需要移动元素的次数的数量级为n，故此算法的时间复杂度为O(n)。5、线性表的删除算法删除线性表中的第i个元素和插入操作的原理相同，当删除第i个元素之后，为了满足原线性表第i+1个和第i1个元素之间的相邻关系，我们需要将原第i+1个到第n个元素依次向前移动一个单位。如图2.3所示，删除第4个元素后，需要将第5个到第7个元素依次向前移动一个单位。StatusListDelete_S(List_Sq&L,inti,ElemType&e)if(iL.length)returnERROR;/