《第2章线性表及其应用》习题解答

《《第2章线性表及其应用》习题解答》由会员分享，可在线阅读，更多相关《《第2章线性表及其应用》习题解答（39页珍藏版）》请在装配图网上搜索。

1、第2章 线性表及其应用本章学习要点掌握线性表的逻辑结构及相关概念。掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。熟练掌握顺序表和链表上各种基本操作的实现过程。灵活运用顺序表和链表的特点解决实际应用问题。线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。2.1线性表的定义和基本运算2.1.1线性表的定义线性表是n(

2、n0)个同类型数据元素（记录或结点）的有限序列：a0,a1,a2,an-1。记为：Ln=(a0,a1,a2,an-1)。其中：a0是开始结点，an-1是终端结点，ak是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个数据元素的数组A的所有元素为A0,A1,An-1。在线性表的定义中，第i个元素的下标为i-1,即元素的位置等于其下

3、标加1。日常生活中，线性表的例子很多：【例2.1】L10=（1，3，5，7，9，2，4，6，8，10）是一个线性表。其中的数据元素是整数，该线性表的长度为10。按表中的排列顺序，元素1是第一个元素没有前驱，元素10是最后一个元素没有后继。【例2.2】L36=（0,1,2,3,4,5,6,7,8,9,A,B,C,D,X,Y,Z）是一个线性表。其中的数据元素是所有数字字符和所有大写字母字符，线性表的长度为36。按表中的排列顺序，元素0是第一个元素没有前驱，元素Z是最后一个元素没有后继。【例2.3】由图2.1所示的学生基本情况表L7也是一个线性表。线性表中的元素是由5个数据项组成的纪录，表的长度为7

4、。2.1.2线性表的基本操作线性表的基本运算主要有以下几种：（1）初始化InitList（&L）：构造一个空线性表L的运算。（2）提取GetElem(L,i,&e)：提取表L中第i个元素的值到e的运算。（3）修改SetElem(&L,i,e)：修改表L中第i个元素的值为e的运算。（4）查找LocateElem(L,e)：查找表L中第一个值与e相同的元素的位置。（5）插入InsertList(&L,i,e)：将e插入到表L中的第i个位置。（6）删除DeleteList(&L,i,&e)：删除表L中的第i元素，并用e返回该元素的值。（7）求表长Length(L):返回线性表L的长度。（8）遍历Tr

5、averseList(L)：依次输出L中每个元素的值。在线性表的其它操作中，有些操作可以通过调用基本操作来实现，有些操作比如线性表的排序和归并等操作的实现将在以后的章节中进行。2.2线性表的顺序存储表示与实现2.2.1线性表的顺序存储1顺序表概念一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。设顺序表中元素的首地址为，每个元素需要占用的字节数为，则表中任一元素的存储位置可用下面的公式算出：顺序表中各元素在内存中所占的

6、位置如图2.2所示。2顺序表的结构定义顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插入和删除等操作，也就是说一个线性表的长度是可变的，为适应这种情况在C+语言中用以下结构类型来表示顺序表。typedef int ElemType; /为了方便上机调试程序，本章假定数据元素的类型为整型const int MAXLEN=100; /定义顺序表存储空间大小的初始分配常量const int INCSIZE=50; /定义顺序表存储空间的扩充常量值struct SqList /定义顺序表的结构类型为SqList ElemType *elem; /存储空间的基址 int len

7、gth; /线性表的长度 int listsize; /当前表的存储容量 int incsize; /一次增补的容量值 ;在以上结构表示下，许多关于线性表的运算（如存、取、求线性表的长度和置表空等操作）极易实现。以下主要讨论关于顺序表的插入、删除、查找和遍历等操作。2.2.2顺序表中基本操作的实现1初始化操作InitList_Sq(&L)该操作的功能是构造一个空线性顺序表L。算法思想（1）在堆空间中为线性表动态分配一块连续的存储单元，返回首地址到elem;（2）置线性表的长度值length为0;（3）置表的当前容量listsize为动态分配时的大小；（4）置容量扩充值incsize的大小为IN

8、CSIZE。线性表L的初始化存储结构如图2.3所示。算法实现void InitList_Sq(SqList &L,int maxlength=MAXLEN,int incsize=INCSIZE)L.elem=new ElemTypemaxlength;/动态分配一个长度为maxlength的连续存储空间，类型为ElemType，返回首地址到L.elemL.length=0;L.listsize=maxlength;L.incsize=incsize;2提取操作GetElem_Sq(L,i,&e)该操作将顺序表L中第i个元素的值赋值到e中，如果提取成功返回1否则返回0。算法实现int GetE

9、lem_Sq(SqList L,int i,ElemType &e)if(iL.length)return 0; /如果位置i不合理时返回0值elsee=L.elemi-1; /通过参数e得到第i个元素的值return 1;3修改操作SetElem_Sq(&L,i,e)修改操作将线性表L中第i个元素的值修改为e，如果修改成功返回1否则返回0。算法实现int SetElem_Sq(SqList &L,int i,ElemType e) if(iL.length)return 0; else L.elemi-1=e;return 1; 4查找操作LocateElem_Sq(L,e)查找操作的功能是

10、查找顺序表L中第一个值与e相同的元素的位置，如果查找成功返回1查找失败返回0。算法实现int LocateElem_Sq(SqList L,ElemType e)int i=0;while(iL.length&L.elemi!=e)i+;if(iL.length)return i+1;else return 0;算法分析查找运算的基本操作为表中元素与数据e的比较。假定表的长度为n,每个位置找到的机会都是相同的，即第i个位置找到的概率为，那么查找操作的平均比较次数为：。查找的时间复杂度是按最坏的情况来考虑，即查找的是最后一个元素或找不到该元素，其比较次数为n次,所以查找的时间复杂度为：。5插入操

11、作InsertList_Sq(&L,i,e)插入操作的功能是将元素e插入到顺序表L中L.elem的第i个位置，同时修改L的长度。如果插入成功返回1，不成功返回0。算法思想(1) 先编写函数IncSize(&L),其功能是将顺序表L的最大存储量增加L.incsize个元素的空间；(2) 如果插入的位置i不合理返回0，表示插入不成功；(3) 如果当前线性表的长度已经达到最大容量值L.listsize，则调用函数IncSize(&L)扩充容量；(4) 将L.elem中第i个以后的所有元素都依次向后移动一个位置，为第i个元素的插入留出一个空位；(5) 置L中第i个元素的值为e；(6) 将表的长度加1；

12、(7) 返回值1表示插入成功。算法实现void IncSize(SqList &L)/该函数的功能是另分配一个存储区并将L的最大存储量增加L.incsize个记录的空间ElemType *a=new ElemTypeL.listsize+L.incsize;for(int i=0;iL.length;i+)ai=L.elemi; /将L.elem中的元素复制到数组a中deleteL.elem; /收回L.elem所占空间L.elem=a; /让L.elem指向aL.listsize+=L.incsize; /修改最大存储空间int InsertList_Sq(SqList &L,int i,E

13、lemType e)int k;if(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;算法分析从以上算法可见，在不考虑扩容的情况下，插入运算的时间主要花费在元素的向后移动上。假定表的长度为n,每个位置插入的机会都是相同的，即第i个位置插入的概率为，那么插入操作平均移动元素的次数为：。插入操作的时间复杂度是按最坏的情况考虑

14、，即插入到表中开始的位置，所以元素的移动次数为n次,时间复杂度为。6删除操作DeleteList_Sq(&L,i,&e)删除操作的功能是删除顺序表L中的第i元素，并返回该元素的值到e中。如果操作成功返回1，否则返回0。算法思想（1）如果删除的位置i不合理返回0，表示删除操作不成功；（2）置e的值为L中第i个元素的值； （3）将L中第i个以后的所有元素都依次向前移动一个位置；（4）将表的长度减1；（5）返回值1表示删除成功。算法实现int DeleteList_Sq(SqList &L,int i,ElemType &e)if(iL.length)return 0; /如果删除的位置i不合理返回

15、0e=L.elemi-1; /置e的值为L中第i个元素的值while(iL.length) /将L中第i个以后的所有元素都依次向前移动一个位置 L.elemi-1=L.elemi;i+; L.length-; /将表的长度减1 return 1;算法分析删除运算的时间主要花费在元素的向前移动上。假定表的长度为n,每个位置删除的机会都是相同的，即第i个位置删除的概率为，那么删除操作平均移动元素的次数为：。删除操作的时间复杂度是按最坏的情况考虑，即删除表中第一个元素，此时的元素移动次数为n-1次, 时间复杂度为：。7求表长的操作Length_Sq(L)该操作的功能是返回顺序表L的长度，如果当前L是

16、空表则返回0。算法实现int Length_Sq(SqList L) return L.length;8遍历操作TraverseList_Sq(L)该操作的功能是顺序显示输出顺序表L中每个元素的值。算法实现#include “iostream.h” /将C+的输入输出流库头文件包含进来void TraverseList_Sq(SqList L)if(!L.length)cout当前线性表为空表.n; /将提示串输出到标准输出设备elsefor(int i=0;iL.length;i+)coutL.elemi ; /输出元素的值和一个空格coutendl;2.2.3顺序表的综合演示程序在前面顺序

17、表的结构定义及其基本操作算法的基础上，本节给出顺序表的各个基本操作的综合演示程序代码以及运行结果。1建立一个有n个元素的顺序表void Create_Sq(SqList &L) ElemType e;int i,n;InitList_Sq(L);coutn;cout输入n个元素的值:n;for(i=1;ie;InsertList_Sq(L,i,e);2综合演示主程序void main_Sq()SqList L; ElemType e;int i,num;Create_Sq(L);cout顺序表的初始数据为:n;TraverseList_Sq(L); while(1) cout1-提取第i个元素

18、， 2-修改第i个元素的值，3-插入第i个元素n; cout4-删除第i个元素的值，5-查找元素e的位置，6-显示当前表的内容n;cout7-退出演示程序：;coutnum;switch(num)case 1:couti;if(GetElem_Sq(L,i,e)cout第i个元素的值为eendl;elsecout输入的位置不合理n;break;case 2:coutie;if(!SetElem_Sq(L,i,e)cout输入的位置不合理,修改不成功n;break; case 3:coutie;if(!InsertList_Sq(L,i,e)cout插入的位置不合理,操作不成功n;break;c

19、ase 4:couti;if(!DeleteList_Sq(L,i,e)cout删除位置不合理,删除操作失败n;elsecout位置: i 的值：e 被删除n;break;case 5:coute;if(!(i=LocateElem_Sq(L,e)cout查找不成功n;elsecout表中位置: i 处的值为：en;break;case 6:cout顺序表的当前值为:n; TraverseList_Sq(L); break;case 7:cout欢迎使用顺序表演示程序n;return;default:cout选择不合理重新选择n;/end_switch/end_while/end_main_S

20、q()（运行结果略）2.2.4 顺序存储结构小结在顺序表的存储结构中，由于表中数据元素的存储顺序与元素之间的逻辑顺序完全一致，因此确定表中元素的存储位置非常容易，访问表中任一元素也就非常方便。这是顺序存储方式的特点，也是顺序表的主要优点。但是，这种存储方式也同时存在以下缺点：（1）对顺序表进行插入或删除操作时，往往需要向后或向前移动大量元素，这一操作的时间开销很大，特别当每个元素中所含的信息量很大时，这个问题显得尤为突出；（2）对顺序表的最大长度listsize以及一次增扩的长度incsize事先不易确定一个比较合适的大小。如果选取的值较小而在实际运行时出现大量的插入操作，这将导致多次调用扩容

21、函数IncSize(&L)来批量移动记录，从而浪费大量的时间；如果选取的值较大，但是在实际运行时很少进行插入操作，这将导致存储空间的大量浪费；（3）顺序存储要求一次分配足够大的连续的内存空间，如果当前系统中没有连续的足够大的空闲空间可用，这将导致内存分配失败。另一方面，这种分配方法会使系统空间中产生许多不可利用的空闲碎块，降低了空间资源的利用率。鉴于以上顺序表存在的问题，后面将给出线性表的另一种存储结构链式存储结构。2.3线性顺序表的应用举例【例2.4】有n个人围成一圈，顺序排号：1、2、3、n。从第一个人开始报数（从1到m报数），凡报到m的人退出圈子并记下此人的排号，当最后一个人退出圈子时，

22、按出圈次序依次输出所有人原来的排号序列（用线性顺序表编程实现）。void main()int m,n,i,k; /定义人数n、间隔数m、循环变量i和出圈人下标kElemType e; /定义出圈人编号eSqList L; /定义线性顺序表Lcoutnm; /输入n、m的值InitList_Sq(L); /初始化Lfor(i=1;i=n;i+) /置第i个人的编号为iInsertList_Sq(L,i,i);cout所求编号序列为:n;k=0;for(i=0;in;i+)k=(k+m-1)%L.length; /计算出圈人在数组L.elem中的下标kDeleteList_Sq(L,k+1,e);

23、 /删除第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】试编写一算法，实现对线性顺序表L的逆置操作。即利用原表的存储空间将线性表L=(a0,a1,a2,an-1)逆置为L=(an-1,an-2,an-3,a0)。void Inverst(SqList &L) /逆置顺序表中的元素int i=0,j=L.l

24、ength-1; /定义指向第一个元素和指向最后一个元素的下标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);coutnext=NULL; /置头结点的指针域为空2提取操作GetElem_L(L,i,&e)提取操作的功能为提取链表L中第i个结点的数据域（data）的值到e中。如果提取成功（即位置i合理）返回1否则返回0。算法实现in

25、t GetElem_L(LinkList L,int i,ElemType &e)int k;LinkList p=L-next;for(k=1;knext;if(idata;return 1;3修改操作SetElem_L(&L,i,e)修改操作修改单链表L中第i结点数据域data的值为e的值。如果修改成功（即位置i合理）返回1否则返回0。算法实现int SetElem_L(LinkList &L,int i,ElemType e)int k;LinkList p=L-next;for(k=1;knext; /取第i个结点的指针pif(idata=e;return 1;4查找操作LocateE

26、lem_L(L,e)该操作查找单链表L中第一个数据域的值与e相同的结点的位置。如果查找成功返回该结点的指针（地址），否则返回空指针（NULL）。算法实现LinkList LocateElem_L(LinkList L,ElemType e)LinkList p=L-next;while(p&p-data!=e) p=p-next; /查找第一个值相同的结点return p;5插入操作InsertList_L(&L,i,e)插入操作的功能是，在单链表L的第i个结点前面插入一个数据域的值为e的结点。如果插入成功返回1，否则返回0。算法思想（1）在单链表L中找到第i-1个结点的指针p；（2）如果查找

27、不成功（即位置i不合理）返回0；（3）在堆空间中分配新的结点q；（4）置q的数据域的值为e；（5）将q插入到L中p-next之前、p之后。用语句q-next=p-next;和p-next=q;实现。（6）返回1表示插入成功。操作结果如图2.6所示。算法实现int InsertList_L(LinkList &L,int i,ElemType e)LinkList p=L,q;int k;for(k=1;knext;k+) p=p-next; /查找L中第i个结点的直接前驱结点的指针pif(i1|kdata=e; /置q中数据域的值为eq-next=p-next; /将q插入L中第i个结点之前p

28、-next=q;return 1;6删除操作DeleteList_L(&L,i,&e)操作的功能是将单链表L中第i个结点的值赋值给e，并将该结点从链表中删除。如果操作成功返回1，否则返回0。算法思想（1）在单链表L中找到第i-1个结点的指针p；（2）如果查找不成功（即位置i不合理）返回0；（3）置q的值为p-next（4）置e的值为q中数据域的值；（5）将结点q从链表中摘除。用语句p-next=q-next;实现。（6）释放结点q所占的堆空间并返回1表示删除成功。操作结果如图2.7(a)、2.7(b)、2.7(c)所示。算法实现int DeleteList_L(LinkList &L,int

29、i,ElemType &e) LinkList p=L,q;int k;for(k=1;knext;k+)p=p-next;if(inext)return 0;q=p-next;e=q-data;p-next=q-next;delete q;return 1;7求表长操作Length_L(L)该操作返回链表L的长度，如果L为空链表则返回0。算法实现int Length_L(LinkList L)int i=0;LinkList p=L-next;while(p)i+;p=p-next;return i;8遍历操作TraverseList_L(L)该操作依次显示输出L中每个结点中数据域的值。算法

30、实现void TraverseList_L(LinkList L)LinkList p=L-next;if(!p)cout链表为空表.n;elsecout链表中的数据有:n;while(p)coutdatanext;coutendl;2.4.3 线性链表中基本操作的综合演示程序在前面链表的结构定义及其基本操作算法的基础上，本节给出关于链表中基本操作的综合演示程序代码。1建立一个有n个结点的单链表void Create_L(LinkList& L) ElemType e;int i,n;InitList_L(L);cout建立链表L:n;coutn;cout输入n个元素的值:n;for(i=1;

31、ie;InsertList_L(L,i,e);2单链表的综合演示主程序void main_L()LinkList L;ElemType e;int i,num;Create_L(L);TraverseList_L(L);while(1)cout1-提取第i个结点的值，2-修改第i个结点的值，3-插入第i个结点n;cout4-删除第i个结点，5-查找第一个数据为e的结点，6-显示当前链表的内容n;coutnum;switch(num)case 1:couti;if(GetElem_L(L,i,e)cout第i个元素的值为eendl;elsecout输入的位置不合理n;break;case 2:c

32、outie;if(!SetElem_L(L,i,e)cout输入的位置不合理,修改不成功n;break; case 3:coutie;if(!InsertList_L(L,i,e)cout插入的位置不合理,操作不成功n;break;case 4:couti;if(!DeleteList_L(L,i,e)cout删除位置不合理,操作失败n;elsecout第i个结点被删除，其值为：en;break;case 5:coute;if(!LocateElem_L(L,e)cout查找不成功n;elsecout数据为e的结点在链表中n;break;case 6:TraverseList_L(L); br

33、eak;case 7:cout欢迎使用顺序表演示程序n;return;default:coutnext=NULL，而在循环链表中空表的条件为h-next=h。（2）指向链尾结点的指针p在单链表中满足的条件是p-next=NULL,而在循环链表中满足的条件是p-next=h.2.5.2双向链表在有n个结点的单链表或单向循环链表中，求一个结点的直接后继结点的时间复杂度为O(1)，而求它的直接前驱结点的时间复杂度均为O(n)。其原因是在结点中只有一个指向直接后继结点的指针，而不含指向直接前驱结点的指针信息。为此给出以下双向链表的概念。1双向链表双向链表中，结点的结构在单链表结点结构(data,nex

34、t)的基础上再增加一个指向直接前驱结点的指针域prior。带有头结点的双向链表的结构如图2.9所示。在C+语言中用以下结构类型来表示双向链表中一个结点的结构类型：typedef struct DNodeElemType data;DNode *next,*prior;*DLinkList;其中，DNode为双向链表的结点结构类型，DLinkList为指向该结点的指针类型。2双向循环链表与单向循环链表类似，在双向链表中，使头结点的prior指针指向尾结点且使尾结点的next指针指向头结点，这样就构成一个双向循环链表。带有头结点的双向循环链表的结构如图2.10所示。双向链表的特点是可以直接求得链表

35、中任意一个结点的直接前驱结点和直接后继结点。但是由于增加了一个指针域，相对于单向链表而言，其存储密度有所降低。2.5.3静态链表1静态链表的概念在有些计算机高级语言中没有设置指针类型，所以不能直接使用线性表的链式存储结构。在这样的语言环境中可借用一维数组来描述线性链表的存储结构，即静态链表存储方式。在C+语言中静态链表的结构类型定义如下：const int MAXSIZE=1000; /链表的最大长度typedef struct SNode ElemType data;int cur;SLinkListMAXSIZE;其中，SNode为静态链表的结点类型（相当于链表的结点类型），数据域data

36、中存放元素的数据，下标（游标）域cur中存放下一个元素（直接后继）的下标；SLinkList为静态链表存储空间Space的定义类型（相当于链表中堆空间的类型）。2静态链表的存储域（1）静态存储空间Space的初始化InitSpace_S(&Space) 该操作将静态链表的存储域Space设置成一个带头结点的空闲“单循环链表”。其中以第一个元素a0作为头结点，该结点的cur=1,a1的cur=2,an-1 的cur=0(n为最大存储长度）。其存储结构如图2.10（a）所示。存储空间初始化算法如下：void InitSpace_S(SLinkList &Space)int n=MAXSIZE,i;

37、for(i=0;in-1;i+)Spacei.cur=i+1;Spacen-1.cur=0;（2）从Space中取一个结点的操作NewSNode(&Space)该操作相当于堆分配命令语句new,其作用是将Space中的空闲链表上第一个结点摘取下来并返回该结点的下标。操作不成功时返回0。在图2.10 （a）的前提下连续执行两次该操作后Space的结构如图2.10（b）所示。算法设计代码如下：int NewSNode(SLinkList &Space)int p;if(p=Space0.cur)Space0.cur=Spacep.cur;return p; （3）归还Space一个结点的操作Del

38、eteSNode(&Space,p) 该操作相当于释放堆空间的语句delete,其作用是将一个结点p插入到Space中空闲链表上第一个结点的位置。在图2.11(a)、图2.11(b)的前提下，归还一个结点（设下标为2）后Space的结构如图2.11(c)所示。算法设计代码如下：void DeleteSNode(SLinkList &Space,int p)Spacep.cur=Space0.cur;Space0.cur=p;3静态链表基本操作在此给出有关静态链表的初始化、插入、删除、显示等基本操作的实现过程。（1）静态链表p的初始化InitList_S(&Space,&p)初始化操作是从其存储

39、空间Space的空闲链表中摘取一个结点，其下标保存到p作为该链表的头结点的指针。并将其cur域的值置0值。如果操作成功返回1，否则返回0。算法设计代码如下：int InitList_S(SLinkList &Space,int &p)if(p=NewSNode(Space)Spacep.cur=0;return 1;return 0; （2）静态链表p的插入操作InsertList_S(&Space,&p,i,e)该操作从Space中摘取一个结点将data域的值置为e并将其插入到p中第i个位置。如果操作成功返回1，否则返回0。算法设计代码如下：int InsertList_S(SLinkLis

40、t &Space,int &p,int i,ElemType e)int h=p,q,k=1;while(Spaceh.cur&ki)/求第i个结点的直接前驱结点h=Spaceh.cur;k+;if(i1|ki)return 0;if(!(q=NewSNode(Space)/获取一个结点return 0;Spaceq.data=e;Spaceq.cur=Spaceh.cur;Spaceh.cur=q;return 1;（3）静态链表p的删除操作DeleteList_S(&Space,&p,i,&e)该操作删除p中第i个结点将data值赋值给e,并将资源归还给Space。如果操作成功返回1，否则

41、返回0。算法设计代码如下：int DeleteList_S(SLinkList &Space,int &p,int i,ElemType &e)int h=p,q,k=1;while(Spaceh.cur&ki)h=Spaceh.cur;k+;if(i1|!Spaceh.cur)return 0; q=Spaceh.cur;Spaceh.cur=Spaceq.cur;e=Spaceq.data;DeleteSNode(Space,q);return 1;（4）静态链表p的遍历操作TraverseList_S(Space,p)该操作按序显示链表p中每一个结点的值。算法设计代码如下：void Tr

42、averseList_S(SLinkList Space,int p)int i=Spacep.cur;while(i)coutSpacei.data ;i=Spacei.cur;coutendl;4静态链表的综合演示程序void main_S()SLinkList SS;int p,i,num,n,k;ElemType e;InitSpace_S(SS);if(!InitList_S(SS,p)cout初始化不成功！n;return;coutn;cout输入n个结点的值:;for(i=0;ie;if(!InsertList_S(SS,p,i+1,e)cout空间已满!n;break;cout

43、链表的初始内容为:n;TraverseList_S(SS,p); cout1-在第i个结点前插入一个结点,2-删除第i个结点n;cout3-显示当前链表的内容,4-显示可用空间长度n;cout5-退出演示程序. ;while(1)coutnum;switch(num)case 1:coutie;if(!InsertList_S(SS,p,i,e)cout插入的位置不合理,或空间已满。n;break;case 2:couti;if(!DeleteList_S(SS,p,i,e)cout删除位置不合理,或链表已空n;elsecout第i个结点被删除，其值为：en;break; case 3:Tra

44、verseList_S(SS,p); break;case 4:for(i=0,k=0;)if(!(i=SSi.cur)break;k+;cout当前的可用空间长度为: kendl; break;case 5:cout欢迎使用顺序表演示程序n;return;default:cout选择不合理重新选择n;/end_switch/end_while/end_main_S()运行结果为：建立一个静态链表，输入长度:12输入12个结点的值:100 200 300 400 500 600 700 800 900 1000 1100 1200链表的初始内容为:100 200 300 400 500 600

45、 700 800 900 1000 1100 12001-在第i个结点前插入一个结点,2-删除第i个结点3-显示当前链表的内容,4-显示可用空间长度5-退出演示程序. 输入选择: 151 / 39输入插入位置i和值e:3 333输入选择: 1输入插入位置i和值e:5 555输入选择: 1输入插入位置i和值e:7 777输入选择: 3100 200 333 300 555 400 777 500 600 700 800 900 1000 1100 1200输入选择: 4当前的可用空间长度为: 983输入选择: 2输入删除位置i:7第7个结点被删除，其值为：777输入选择: 4当前的可用空间长度为: 984输入选择: 2输入删除位置i:11第11个结点被删除，其值为：900输入选择: 4当前的可用空间长度为: 985输入选择: 3100 200 333 300 555 400 500 600 700 800 1000 1100 1200输入选择: 5欢迎使用顺序表演示程序说明：（1）可用空间中应该去掉链表的头结点和空闲链表的头结点。（2）可由多个静态链表共享同一个空闲链表。（3）由于假定系统不能使用指针类型变量，即不能动态分配内存，因此当空间Space中的空闲链表为空时，将使静态链表的插入操作失败。2.6线性链表的应