1、第 2 章 线性表及其应用-.13.-第 2 章 线性表及其应用本章学习要点掌握线性表的逻辑结构及相关概念。掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。熟练掌握顺序表和链表上各种基本操作的实现过程。灵活运用顺序表和链表的特点解决实际应用问题。线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。2.1 线性表的定义
2、和基本运算2.1.1 线性表的定义线性表是 n(n0)个同类型数据元素（记录或结点）的有限序列： a0,a1,a2,an-1。记为：L n=(a0,a1,a2,an-1)。其中：a 0 是开始结点，a n-1 是终端结点，a k 是 ak+1 的直接前驱结点，而 ak+1 是 ak 的直接后继结点(k=0,1,2,n-2) ；终端结点 an-1 没有后继结点，开始结点 a0 没有前驱结点；元素ai(i=0,1,2,n-1)在表中的位置为 i+1；元素的个数 n 称为线性表 L 的长度，长度为零的线性表叫空表。需要说明的是：在 C/C+语言中，数组元素的下标是从 0 开始的，具有 n 个数据元素
3、的数组 A 的所有元素为 A0,A1,An-1。在线性表的定义中，第 i 个元素的下标为 i-1,即元素的位置等于其下标加 1。日常生活中，线性表的例子很多：【例 2.1】L 10=（1，3，5，7，9，2，4，6，8，10）是一个线性表。其中的数据元素是整数，该线性表的长度为 10。按表中的排列顺序，元素 1 是第一个元素没有前驱，元素 10 是最后一个元素没有后继。【例 2.2】L 36=（0,1,2,3,4,5,6,7,8,9,A,B,C,D,X,Y,Z）是一个线性表。其中的数据元素是所有数字字符和所有大写字母字符，线性表的长度为 36。按表中的排列顺序，元素0是第一个元素没有前驱，元素
4、Z是最后一个元素没有后继。【例 2.3】由图 2.1 所示的学生基本情况表 L7 也是一个线性表。线性表中的元素是由 5 个数据项组成的纪录，表的长度为 7。数据结构与算法-.14.-2.1.2 线性表的基本操作线性表的基本运算主要有以下几种：（1）初始化 InitList（ /为了方便上机调试程序，本章假定数据元素的类型为整型const int MAXLEN=100; /定义顺序表存储空间大小的初始分配常量const int INCSIZE=50; /定义顺序表存储空间的扩充常量值struct SqList /定义顺序表的结构类型为 SqListElemType *elem; /存储空间的基
5、址int length; /线性表的长度int listsize; /当前表的存储容量int incsize; /一次增补的容量值;在以上结构表示下，许多关于线性表的运算（如存、取、求线性表的长度和置表空等操作）极易实现。以下主要讨论关于顺序表的插入、删除、查找和遍历等操作。2.2.2 顺序表中基本操作的实现1初始化操作 InitList_Sq(（2）置线性表的长度值 length 为 0;（3）置表的当前容量 listsize 为动态分配时的大小；（4）置容量扩充值 incsize 的大小为 INCSIZE。线性表 L 的初始化存储结构如图 2.3 所示。算法实现void InitList_
6、Sq(SqList /动态分配一个长度为 maxlength 的连续存储空间，类型为 ElemType，返回首地址到 L.elemL.length=0;L.listsize=maxlength;L.incsize=incsize;数据结构与算法-.16.-2提取操作 GetElem_Sq(L,i, /如果位置 i 不合理时返回 0 值else e=L.elemi-1; /通过参数 e 得到第 i 个元素的值return 1;3修改操作 SetElem_Sq(else L.elemi-1=e;return 1;4查找操作 LocateElem_Sq(L,e)查找操作的功能是查找顺序表 L 中第一
7、个值与 e 相同的元素的位置，如果查找成功返回1 查找失败返回 0。算法实现int LocateElem_Sq(SqList L,ElemType e)int i=0;while(iL.length+1)return 0; /插入位置不合理时返回 0 值if(L.length=L.listsize)IncSize(L);for(k=L.length,i-;ki;k-)L.elemk=L.elemk-1; /为第 i 个元素的插入留出一个空位L.elemi=e;L.length+; /修改长度return 1;算法分析从以上算法可见，在不考虑扩容的情况下，插入运算的时间主要花费在元素的向后移动数
8、据结构与算法-.18.-上。假定表的长度为 n,每个位置插入的机会都是相同的，即第 i 个位置插入的概率为，那么插入操作平均移动元素的次数为： 。插入操作的时间1nip 21)(nnip复杂度是按最坏的情况考虑，即插入到表中开始的位置，所以元素的移动次数为 n 次,时间复杂度为 。)(T6删除操作 DeleteList_Sq( /如果删除的位置 i 不合理返回 0e=L.elemi-1; /置 e 的值为 L 中第 i 个元素的值while(in;coute;InsertList_Sq(L,i,e);2综合演示主程序void main_Sq() SqList L; ElemType e;int
9、 i,num;Create_Sq(L);coutnum;switch(num)case 1:couti;if(GetElem_Sq(L,i,e) coutie;if(!SetElem_Sq(L,i,e) coutie;if(!InsertList_Sq(L,i,e) couti;if(!DeleteList_Sq(L,i,e) coute;if(!(i=LocateElem_Sq(L,e) coutnm; /输入 n、m 的值InitList_Sq(L); /初始化 Lfor(i=1;i=n;i+) /置第 i 个人的编号为 iInsertList_Sq(L,i,i);cout“所求编号序列为
10、:n“;k=0;for(i=0;in;i+)k=(k+m-1)%L.length; /计算出圈人在数组 L.elem 中的下标 k数据结构与算法-.22.-DeleteList_Sq(L,k+1,e); /删除第 k+1 个人并提取其编号到 e 中coute“ “;coutendl;运行演示结果为：input n m:10 4所求编号序列为:4 8 2 7 3 10 9 1 6 5程序运行演示过程为，10 个人围成一圈，顺序排号：1、2、3、10。从第一个人开始报数（从 1 到 4 报数） ，凡报到 4 的人退出圈子并依次输出其排号，直到最后一个人退出圈子为止。【例 2.5】试编写一算法，实现
11、对线性顺序表 L 的逆置操作。即利用原表的存储空间将线性表 L=(a0,a1,a2,an-1)逆置为 L=(an-1,an-2,an-3,a0)。void Inverst(SqList /定义指向第一个元素和指向最后一个元素的下标 i、jElemType t; /定义临时变量 twhile(ij) /逐个交换t=L.elemi;L.elemi=L.elemj;L.elemj=t;i+,j-; /交换以后修改下标的相应值void main()SqList L;cout“建立一个线性顺序表:n“;Create_Sq(L);Inverst_Sq(L);cout“交换后的结果为:n“;TraverseList_Sq(L);程序运行演示结果为：建立一个线性顺序表:输入表的长度 n:10输入 10 个元素的值:1 3 5 7 9 11 13 15 17 19交换后的结果为:19 17 15 13 11 9 7 5 3 1
