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

第2章 线性表及其应用

第2章 线性表及其应用

本章学习要点

◆掌握线性表的逻辑结构及相关概念。

◆掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。体会线性表在各种存储方式之间的差异及其各自的优缺点。 ◆熟练掌握顺序表和链表上各种基本操作的实现过程。 ◆灵活运用顺序表和链表的特点解决实际应用问题。

线性表（Linear List）是一种最基本、最常用的数据结构。线性表有两种基本存储表示方法，即顺序存储表示和链表表示。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本操作及其算法实现，最后给出线性表的应用实例。

2.1线性表的定义和基本运算

2.1.1线性表的定义

线性表是n(n≥0)个同类型数据元素（记录或结点）的有限序列：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的所有元素为A[0],A[1],…,A[n-1]。在线性表的定义中，第i个元素的下标为i-1,即元素的位置等于其下标加1。

日常生活中，线性表的例子很多：

【例2.1】L10=（1，3，5，7，9，2，4，6，8，10）是一个线性表。其中的数据元素是整数，该线性表的长度为10。按表中的排列顺序，元素1是第一个元素没有前驱，元素10是最后一

-.13.-

《数据结构与算法》

个元素没有后继。

【例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。

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）遍历TraverseList(L)：依次输出L中每个元素的值。

在线性表的其它操作中，有些操作可以通过调用基本操作来实现，有些操作比如线性表的排序和归并等操作的实现将在以后的章节中进行。

2.2线性表的顺序存储表示与实现

2.2.1线性表的顺序存储

1．顺序表概念

一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。

设顺序表Ln??a0,a1,?,an?1?中元素a0的首地址为LOC(a0)，每个元素需要占用的字节数为l，则表中任一元素ai的存储位置LOC(ai)可用下面的公式算出：

LOC(ai)?LOC(a0)?i?l(i?0,1,2,?,n?1)顺序表中各元素在内存中所占的位置如

-.14.-

第2章 线性表及其应用

图2.2所示。

2．顺序表的结构定义

顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插入和删除等操作，也就是说一个线性表的长度是可变的，为适应这种情况在C++语言中用以下结构类型来表示顺序表。

typedef int ElemType; //为了方便上机调试程序，本章假定数据元素的类型为整型 const int MAXLEN=100; //定义顺序表存储空间大小的初始分配常量 const int INCSIZE=50; //定义顺序表存储空间的扩充常量值 struct SqList //定义顺序表的结构类型为SqList {

ElemType *elem; //存储空间的基址 int length; //线性表的长度 int listsize; //当前表的存储容量 int incsize; //一次增补的容量值 };

在以上结构表示下，许多关于线性表的运算（如存、取、求线性表的长度和置表空等操作）极易实现。以下主要讨论关于顺序表的插入、删除、查找和遍历等操作。

2.2.2顺序表中基本操作的实现

1．初始化操作InitList_Sq(&L)

该操作的功能是构造一个空线性顺序表L。 算法思想

（1）在堆空间中为线性表动态分配一块连续的存储单元，返回首地址到elem; （2）置线性表的长度值length为0;

（3）置表的当前容量listsize为动态分配时的大小； （4）置容量扩充值incsize的大小为INCSIZE。

线性表L的初始化存储结构如图2.3所示。

-.15.-

《数据结构与算法》

算法实现

void InitList_Sq(SqList &L,int maxlength=MAXLEN,int incsize=INCSIZE) { L.elem=new ElemType[maxlength];

//动态分配一个长度为maxlength的连续存储空间，类型为ElemType，返回首地址到L.elem

}

L.length=0;

L.listsize=maxlength; L.incsize=incsize;

2．提取操作GetElem_Sq(L,i,&e)

该操作将顺序表L中第i个元素的值赋值到e中，如果提取成功返回1否则返回0。 算法实现

int GetElem_Sq(SqList L,int i,ElemType &e) { if(i<1||i>L.length) return 0; //如果位置i不合理时返回0值 else { e=L.elem[i-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(i<1||i>L.length)return 0; else { L.elem[i-1]=e; return 1; } }

4．查找操作LocateElem_Sq(L,e)

查找操作的功能是查找顺序表L中第一个值与e相同的元素的位置，如果查找成功返回1

-.16.-

第2章 线性表及其应用

查找失败返回0。 算法实现

int LocateElem_Sq(SqList L,ElemType e) { int i=0; while(i

查找运算的基本操作为表中元素与数据e的比较。假定表的长度为n,每个位置找到的机会都是相同的，即第i个位置找到的概率为pi?1n，那么查找操作的平均比较次数为：

?ni?1pi?i?n?12。查找的时间复杂度是按最坏的情况来考虑，即查找的是最后一个元素或找

不到该元素，其比较次数为n次,所以查找的时间复杂度为：T(n)??(n)。

5．插入操作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；

(7) 返回值1表示插入成功。 算法实现

void IncSize(SqList &L)

{//该函数的功能是另分配一个存储区并将L的最大存储量增加L.incsize个记录的空间 ElemType *a=new ElemType[L.listsize+L.incsize]; for(int i=0;i

-.17.-

第2章 线性表及其应用

表的头结点的指针。并将其cur域的值置0值。如果操作成功返回1，否则返回0。

算法设计代码如下：

int InitList_S(SLinkList &Space,int &p) { if(p=NewSNode(Space)) { Space[p].cur=0; return 1; } return 0; } （2）静态链表p的插入操作InsertList_S(&Space,&p,i,e)

该操作从Space中摘取一个结点将data域的值置为e并将其插入到p中第i个位置。如果操作成功返回1，否则返回0。算法设计代码如下：

int InsertList_S(SLinkList &Space,int &p,int i,ElemType e) { int h=p,q,k=1; while(Space[h].cur&&k

该操作删除p中第i个结点将data值赋值给e,并将资源归还给Space。如果操作成功返回1，否则返回0。算法设计代码如下：

int DeleteList_S(SLinkList &Space,int &p,int i,ElemType &e) { int h=p,q,k=1; while(Space[h].cur&&k

-.33.-

《数据结构与算法》

}

（4）静态链表p的遍历操作TraverseList_S(Space,p)

该操作按序显示链表p中每一个结点的值。算法设计代码如下： void TraverseList_S(SLinkList Space,int p) { int i=Space[p].cur; while(i) { cout<

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; } cout<<\建立一个静态链表，输入长度:\ cin>>n; cout<<\输入\个结点的值:\ for(i=0;i>e; if(!InsertList_S(SS,p,i+1,e)) { cout<<\空间已满!\\n\break; } } cout<<\链表的初始内容为:\\n\ TraverseList_S(SS,p);

cout<<\在第i个结点前插入一个结点,2-删除第i个结点\\n\ cout<<\显示当前链表的内容,4-显示可用空间长度\\n\ cout<<\退出演示程序. \ while(1) { cout<<“输入选择:”; cin>>num; switch(num) { case 1: cout<<\输入插入位置i和值e:\cin>>i>>e;

-.34.-

第2章 线性表及其应用

if(!InsertList_S(SS,p,i,e)) cout<<\插入的位置不合理,或空间已满。\\n\ break; case 2: cout<<\输入删除位置i:\cin>>i; if(!DeleteList_S(SS,p,i,e)) cout<<\删除位置不合理,或链表已空\\n\ else cout<<\第\个结点被删除，其值为：\ break; case 3: TraverseList_S(SS,p); break; case 4: for(i=0,k=0;;) { if(!(i=SS[i].cur))break; k++; } cout<<\当前的可用空间长度为: \ 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 700 800 900 1000 1100 1200 1-在第i个结点前插入一个结点,2-删除第i个结点 3-显示当前链表的内容,4-显示可用空间长度 5-退出演示程序. 输入选择: 1 输入插入位置i和值e:3 333 输入选择: 4 输入选择: 1 当前的可用空间长度为: 984 输入插入位置i和值e:5 555 输入选择: 2 输入选择: 1 输入删除位置i:11 输入插入位置i和值e:7 777 第11个结点被删除，其值为：900 输入选择: 3 输入选择: 4 100 200 333 300 555 400 777 500 600 700 800 900 当前的可用空间长度为: 985 1000 1100 1200 输入选择: 3 输入选择: 4 100 200 333 300 555 400 500 600 700 800 1000 1100 当前的可用空间长度为: 983 1200 输入选择: 2 输入选择: 5 输入删除位置i:7 欢迎使用顺序表演示程序 第7个结点被删除，其值为：777

说明：

-.35.-

《数据结构与算法》

（1）可用空间中应该去掉链表的头结点和空闲链表的头结点。 （2）可由多个静态链表共享同一个空闲链表。

（3）由于假定系统不能使用指针类型变量，即不能动态分配内存，因此当空间Space中的空闲链表为空时，将使静态链表的插入操作失败。

2.6线性链表的应用举例

【例2.6】有n个人围成一圈，顺序排号：1、2、3、?、n。从第一个人开始报数（从1到m报数），凡报到m的人退出圈子并记下此人的排号，当最后一个人退出圈子时，按出圈次序依次输出所有人原来的排号序列（用单链表编程实现）。 算法思想

（1）建立一个长度为n的单链表L，其结点值依次为1、2、?、n；

（2）指针p（开始时指向头结点）每次向后移动m-1次使其指向出圈结点的直接前区结点； （3）如果p的后继结点为NULL则p=L；

（4）从链表L中删除p的后继结点q并输出q中的编号值； （5）重复执行（2）、（3）、（4）n次。 算法实现

void main() { int m,n,i,k; LinkList L=new Node,p,q; //定义头指针L指向头结点以及结点指针变量p、q cout<<\ cin>>n>>m; p=L; for(i=1;i<=n;i++) //建立有n个结点的单链表并且依次赋于相应的编号值 { p->next=new Node; p=p->next; p->data=i; } p->next=NULL; //最后一个结点的指针域为NULL p=L; cout<<\所求编号序列为:\\n\ for(i=0;inext)p=L; p=p->next; } if(!p->next)p=L; q=p->next; //以下语句实现：删除结点q并输出其编号的值 p->next=q->next; cout<data<<\

-.36.-

第2章 线性表及其应用

delete q; } cout<

程序运行演示结果为：

input n m:10 3↙ 所求编号序列为: 3 6 9 2 7 1 8 5 10 4

算法分析

由算法设计过程可知该算法的时间复杂度为O(n×m)，空间复杂度为O(1)。 【方法二】类似[例2.4]，通过直接调用单链表的基本操作来求解。 void main() { int m,n,i,k; //定义人数n、间隔数m、循环变量i和出圈人前驱结点的位置k ElemType e; //定义出圈人编号e LinkList L; //定义线性链表L cout<<\ //输入n、m的值 InitList_L(L); //初始化L为空链表 for(i=1;i<=n;i++)InsertList_L(L,i,i); //置第i个人的编号为i cout<<\所求编号序列为:\\n\ for(k=0,i=n;i>0;i--) //i为当前的链表长度 { k=(k+m-1)%i; //计算出圈人结点在链表L中的前驱结点位置k DeleteList_L(L,k+1,e); //删除第k+1个结点并提取其编号到e中 cout<

【例2.7】逆置一个具有头结点的单向链表。

链表L逆置前的结构如图2.12(a)所示，L逆置后的结构如图2.12(b)所示。

算法思想

（1）如果长度≤1程序结束；

（2）指针p指向第一个结点，q指向第二个结点； （3）置p的next域为NULL，r为q的直接后继； （4）如果r为NULL转入（7）否则执行（5）；

（5）置q的直接后继为p，置p的值为q，置q的值为r，置r为q的直接后继；

-.37.-

《数据结构与算法》

（6）转入语句（4）；

（7）置q的直接后继为p，置L的直接后继为q。 算法实现

void Contray_L(LinkList &L) { if(!L->next||!L->next->next) return; LinkList p=L->next,q=p->next,r; p->next=NULL; while(r=q->next) { q->next=p;p=q;q=r;} q->next=p; L->next=q; } 算法分析

设链表的长度为n，由算法设计过程可知该算法的时间复杂度为O(n)，空间复杂度为O(1)。 【例2.8】现有两个递增有序的带有头结点的单链表L1、L2，要求将L2中的结点归并到L1中并保持L1仍然有序，并且在归并过程中不另设结点。 算法思想

总的想法是，从前往后将L2中的结点逐个插入到L1中，如果在此过程中有一个结点插入到L1的末尾，则将L2中剩余的部分链接到L1的尾部即可。 算法实现

void Merger_L(LinkList& L1,LinkList& L2) { LinkList p=L1,q=L2->next,r; L2->next=NULL; while(p->next&&q) { if(p->next->datadata) p=p->next; else { r=q;q=q->next; r->next=p->next; p->next=r; p=r; } } if(q)p->next=q; } 算法分析

设L1的长度为m，L2的长度为n。算法的时间复杂度为O(m+n)，空间复杂度为O(1)。 【例2.9】用线性表表示一元多项式并实现多项式的加法、减法和乘法运算。

-.38.-

第2章 线性表及其应用

1．多项式的线性表示法

在数学上，一个n次多项式Pn(x)可按升幂写成：Pn(x)?p0?p1x?p2x2???pnxn，可见，Pn(x)由其n+1个系数组成的系数向量P?(p0,p1,p2,?,pn)唯一确定。因此，在计算机中一个n次多项式可用一个长度为n+1的线性表P来表示，其中pi表示多项式中x的系数。

设多项式Qm(x)的系数向量为Q?(q0,q1,q2,?,qm)且

m

iRn(x)?Pn(x)?Qm(x)的系数向量为:

R?(p0?q0,p1?q1,p2?q2,?,pm?qm,pm?1,?,pn)。

显然，对线性表P、Q、R，若均采用顺序存储结构，那么作多项式的加法运算十分简便。但是，在实际应用中多项式的次数可能很高，且其中有大量的系数为零。

例如，多项式：S(x)??8?6.5x50?3.7x2500，要用顺序存储时必须占用2501个元素的存储单元（期中有大量的0系数），这显然是不合理的。

为此，我们考虑只储存多项式的非零系数，此时必须连同它所表示的项的指数一起存放才行。这样，用（系数，指数）的序列就可以唯一地确定一个多项式了。此时，S(x)可表示为：S=((-8,0),(6.5,50),(3.7,2500))。这显然也是一个线性表，表中元素是一个数对（实数，整数），并且关于元素中的第二个数据项（整数项）是递增有序的。

既然S是线性表，同样存在其存储结构的选择问题。由于多项式相加的运算结果可能增加若干非零项，也可能减少若干个非零项，因此线性表会执行大量的插入和删除操作，在这种情况下不宜采用顺序存储结构，采用带有指针域的单链表表示一个多项式为宜。上述多项式S(x)的单链表表示结构如图2.13所示。其中，头结点的指数域为-1，以示区别。

在C++语言中多项式的链表结构类型定义如下：

#include\

struct PData //定义多项式中每一项的系数和指数结构类型:PData{系数，指数} { double coef; int expn; };

typedef struct PNode //定义多项式链表的结点结构类型:PNode{data,next} { PData data; PNode* next;

-.39.-

《数据结构与算法》

}*Poly; //定义指向该结点PNode的指针类型Poly. 2．初始化一个零多项式的操作 void InitPoly(Poly &p) { p=new PNode; p->next=NULL; p->data.expn=-1; }

3．多项式加单项式的操作（poly<=poly+data）

算法思想

计算Poly+data的方法是：从前往后将poly->data.expn项逐个取出并与data.expn项进行比较，将其插入到poly中的适当位置（按指数expn由小到大）。如果在poly中存在相同的指数域（expn），则求相应的系数域（coef）的和，如果和为零，则删除掉poly中相应的结点。 算法实现

void InsertAddPData(Poly &poly,PData data) { Poly p=poly,q; while(p->next&&p->next->data.expnnext; if(!p->next||p->next->data.expn>data.expn) //插入一项到结点p的后面 { q=new PNode; q->data=data; q->next=p->next; p->next=q; } else //与对应项的系数相加 { p->next->data.coef+=data.coef; if(fabs(p->next->data.coef)<1e-8) //删除系数为零的项 { q=p->next; p->next=q->next; delete q; } } }

4．按序创建一个多项式

void CreatePoly(Poly &poly) { PData data; InitPoly(poly); cout<<\输入多项式的系数和相应的指数(expn =-1结束):\\n\

-.40.-

第2章 线性表及其应用

}

while(1)

{ cin>>data.coef>>data.expn; if(data.coef==0||data.expn<0)break; InsertAddPData(poly,data); }

5．按指数形式显示一个多项式

void DispPoly(Poly poly) { Poly p=poly; if(!p->next) cout<<\当前为一个0多项式:P=0\\n\ else { cout<<\ while(p->next) { p=p->next; if(p->data.coef>0)cout<<'+'; cout<data.coef<<\ } cout<

6．多项式加多项式操作（p<=p+p1） void AddPoly(Poly &p,Poly p1) { Poly pp=p1->next; while(pp) { InsertAddPData(p,pp->data); pp=pp->next; } }

7．多项式减多项式操作（p<=p-p1） void SubPoly(Poly &p,Poly p1) { Poly pp=p1->next; PData data; while(pp) { data=pp->data; data.coef*=-1; InsertAddPData(p,data); pp=pp->next;

-.41.-

《数据结构与算法》

}

}

8．多项式乘以多项式操作（p<=p1×p2） （1）操作：p<=p+p1×d

void MulData(Poly &p,Poly p1,PData d) { PData dd; Poly h=p1->next; while(h) { dd=h->data; dd.coef*=d.coef; dd.expn+=d.expn; InsertAddPData(p,dd); h=h->next; } }

（2）操作：返回p×p1的值

Poly MulPoly(Poly p,Poly p1) { Poly pm,pp=p1->next; InitPoly(pm); while(pp) { MulData(pm,p,pp->data); pp=pp->next; } return pm; }

9．多项式操作的综合演示主程序 void main() { Poly p,p1,p2,p3,p4; cout<<\ CreatePoly(p); DispPoly(p); cout<<\ CreatePoly(p1); DispPoly(p1);

/////p2<=p+p1////////// InitPoly(p2); AddPoly(p2,p); AddPoly(p2,p1); cout<<\DispPoly(p2);

/////p3<=p-p1////////// InitPoly(p3); AddPoly(p3,p);

-.42.-

第2章 线性表及其应用

SubPoly(p3,p1); cout<<\ DispPoly(p3); /////p4<=p*p1///////// p4=MulPoly(p,p1); cout<<\ DispPoly(p4); }

程序运行结果为：

create p:

输入多项式的系数和相应的指数(expn=-1结束):

2 1 5 8 -3.1 11 0 0

P=+2X^1+5X^8-3.1X^11 create p1:

输入多项式的系数和相应的指数(expn =-1结束): 7 0 -5 8 11 9 0 0

P=+7X^0-5X^8+11X^9 p2=p+p1:

P=+7X^0+2X^1+11X^9-3.1X^11 p3=p-p1:

P=-7X^0+2X^1+10X^8-11X^9-3.1X^11 p4=p*p1:

P=+14X^1+35X^8-10X^9+22X^10-21.7X^11-25X^16+55X^17+15.5X^19-34.1X^20

2.7 习 题

一、简答题

1．分别从线性表的存储密度、访问操作、修改和删除操作，这三个方面讨论其顺序存储和链式存储各有哪些优缺点？

2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。 3．简述在单链表中设置头结点的作用（至少说出两条好处）。

4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？ 5．画出执行下列各语句后各指针及链表的示意图。

L=new LNode; P=L; for(i=1;i<=4;i++)

{P->next=new LNode;P=P->next;P->data=i*2-1;} P->next=NULL;

for(i=4;i>=1;i--)Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++)Del_LinkList(L,i); 6．间述以下算法的功能。

int Func(LinkList &L)

{ //L是无表头结点的单链表 if(L&&L->next){

Q=L; L=L->next;P=L; while(P->next)P=P->next;

P->next=Q; Q->next=NULL;return(1); }

else return(0); } 二、填空题

1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（ ）存储

-.43.-

《数据结构与算法》

结构。

2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（ ）个元素，执行以上操作时，移动元素的具体个数与（ ）有关。

3．顺序表中逻辑上相邻的数据元素的物理位置（ ）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（ ）紧相邻。

4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（ ）存储结构。 5．已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。

a.删除P结点的直接后继结点的语句序列是（ ）。 b.删除P结点的直接前驱结点的语句序列是（ ）。 c.删除P结点的语句序列是（ ）。 d.删除首元结点的语句序列是（ ）。 e.删除尾元结点的语句序列是（ ）。 ⑴ P=P->next; ⑵ P->next=P;

⑶ P->next=P->nexe->next; ⑷ P=P->next->next;

⑸ while(P!=NULL)P=P->next;

⑹ while(Q->next!=NULL){P=Q;Q=Q->next;} ⑺ while(P->next!=Q)P=P->next;

⑻ while(P->next->next!=Q)P=P->next; ⑼ while(P->next->next!=NULL)P=P->next; ⑽ Q=P;

⑾ Q=P->next; ⑿ P=L;

⒀ L=L->next; ⒁ delete Q; 三、解答题

1．编写一函数，在线性顺序表L中求出最大元素以及该元素在表中的位置（假设L中的元素不重复）。

2．编程实现，逆置顺序表L中的所有元素（假设L中的元素为整数），并求出所用算法中基本操作的频度。

3．编程实现，将一个顺序表A（假设A中的元素为整数）分拆成两个顺序表B、C，使A中大于等于0的元素存放到B中，小于0的元素存放到C中。

4．编写一函数，将两个递增有序的顺序表A和B归并成一个顺序表C，要求C是按元素值不减有序排列的（允许C中有相同值的元素）。

5．编程实现，求单链表L中的最大元素，并且删除该元素所在的结点。要求算法中基本操作的次数越少越好。

6．试编写一程序，将带有头结点的单循环链表逆置。

7．已知线性表A中的数据元素按照值非递减有序。编写一个算法，将元素e插入到线性表

-.44.-

第2章 线性表及其应用

A中适当位置并仍然保持A有序。试分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。

8．在线性表L中可能有相同的元素。试设计一个算法删除表中所有多余的元素（相同元素仅保留第一个），使删除后表中的元素各不相同。分别在顺序存储和链式存储两种方式下编写出实现该算法的程序。

9．所谓约瑟夫（Josephu）问题是：设有n个人围成一圈并依次进行编号1，2，3，……，n。从某个位置i上的人开始报数，数到m的人出列。下一个人（第m+1个）又从1开始报数，再数到m的人又出列，依次重复下去，直到最后一个人出列为止。按照出列的先后可得一新的序列。试用循环链表作为存储结构，编出求解这一问题的程序。

10．在本章[例2.9]（1）的基础上，编出实现两个多项式Am(x)和Bn(x)相乘的程序。其中，每个多项式都用单链表表示。

2.8 上机实验

本章上机实验的主要目的在于帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用为重点内容。

实验题目 约瑟夫(Joseph)环

【问题描述】

约瑟夫(Joseph)问题的一种描述是：编号为1,2,3,?,n的n个人按顺时针方向围坐一圈，每人有一个密码（正整数）。首先输入一个整数m，从第一个人开始报数1,2,3,?，报到m时停止报数。让报m的人出圈，显示输出该人的密码，并将该密码作为新的m值，从该位置顺时针方向上的下一个人开始重新从1开始报数，如此下去，直到所有人全部出圈为止。设计一个程序模拟该过程。 【基本要求】

（1）用顺序存储结构模拟约瑟夫问题，按照出圈的顺序依次输出每人的编号和密码； （2）利用单向循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人的编号和密码； （3）用静态循环链表存储结构模拟约瑟夫问题，依次输出每个出圈人原来的编号和密码。 【测试数据】

m的初值为20，n=7，7个人的密码依次为：3,1,7,2,4,8,4，首先m的值为6，正确测试结果的编号序列为：6,1,4,7,2,3,5。 【实现提示】

程序运行后，首先要求用户输入人数n和报数上限的初始值m，然后依次读入n个人的密码。此题对于单向循环链表存储结构不需要“头结点”，并注意空表和非空表的判定。

第2章、部分习题参考答案

一、简答题

1．分别从线性表的存储密度、访问操作、插入（修改）和删除操作，这三个方面讨论其顺

-.45.-

《数据结构与算法》

序存储和链式存储各有哪些优缺点？

（1）存储密度：相对于顺序存储而言，链表中的一个结点比顺序表中的一个记录要多一个指针存储空间，所以通常情况下，链表的存储密度比顺序表的存储密度低。但是，如果顺序表的最大长度远大于实际的记录数时其存储密度将会大大降低。另一方面，顺序表要求较大的连续存储空间，这种分配方法会使系统空间中产生许多不可利用的空闲碎块，降低了空间资源的利用率。而链表中的结点在内存中不要求连续存放。

（2）访问操作：顺序表中的元素存储在一个连续的地址空间中，可以对表中的元素进行随机访问。由于链式存储结构的特点，不能随机访问链表中的每一个结点，只能从链表的头指针开始逐个向后访问。

（3）插入和删除操作：对顺序表进行插入或删除操作时，往往需要向后或向前移动大量元素，所以该操作的时间开销很大；而对于链表在进行插入或删除操作时，仅仅是简单的指针赋值运算即可完成。

2．描述链表中，头结点、头指针、首元结点（第一个元素结点）三个概念的区别。 （1）首元结点：是指链表中存储线性表中第一个数据元素的结点。

（2）头结点：在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素。

（3）头指针：头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 3．简述在单链表中设置头结点的作用（至少说出两条好处）。 在单链表中设置头结点的作用是：（1）可以统一表示空链表和非空链表；（2）对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。

4．在单链表、单循环链表、双链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除掉？若可以，其时间复杂度各是多少？

（1）在单链表中若仅知道指针p指向某结点，不知道头指针，则不能将结点p从相应的链表中删除掉。

（2）在有n个结点的单循环链表中，删除结点p的时间复杂度为O(n)。 （3）在有n个结点的双链表中，删除结点p的时间复杂度为O(1)。 5．画出执行下列各语句后各指针及链表的示意图。 （1）LinkList L=new LNode,p=L;

for(i=1;i<5;i++){ p->next=new LNode;p=p->next;p->data=i*2-1;} p->next=NULL; 运行结果为：

（2）在程序段(1)的基础上画出以下程序段运行结果的示意图。 for(i=4;i>0;i--)Ins_LinkList(L,i+1,i*2); 运行结果为：

（3）在程序段(2)的基础上画出以下程序段运行结果的示意图。 for(i=1;i<4;i++)Del_LinkList(L,i); 运行结果为：

-.46.-

第2章 线性表及其应用

6．间述以下算法的功能。

int Func(LinkList &L)

{ //L是无表头结点的单链表 if(L&&L->next){

Q=L; L=L->next;P=L; while(P->next)P=P->next;

P->next=Q; Q->next=NULL;return(1); }

else return(0); } 二、填空题

1．对于线性表的两种基本存储结构，如果表中元素的总数基本稳定，并且很少进行插入和删除操作，但是要求以最快的速度提取或修改线性表中的元素，应该选用（顺序）存储结构。 2．在长度为n的顺序表中插入或删除一个元素，分别需要平均移动（插入操作平均移动元素的次数为：n/2，删除操作平均移动元素的次数为：(n-1)/2）个元素，执行以上操作时，移动元素的具体个数与（具体位置）有关。

3．顺序表中逻辑上相邻的数据元素的物理位置（一定）紧相邻。单链表中逻辑上相邻的数据元素的物理位置（不一定）紧相邻。

4．如果系统语言不支持指针类型的变量，并且在元素总数变化不大的情况下，要求以最快的速度对线性表执行插入和删除操作，那么线性表应该选用（静态链表）存储结构。

5．已知L是带头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试从下面提供的答案中选择合适的语句序列。

a.删除P结点的直接后继结点的语句序列是（ ）。 b.删除P结点的直接前驱结点的语句序列是（ ）。 c.删除P结点的语句序列是（ ）。 d.删除首元结点的语句序列是（ ）。 e.删除尾元结点的语句序列是（ ）。 ⑴ P=P->next; ⑵ P->next=P;

⑶ P->next=P->nexe->next; ⑷ P=P->next->next;

⑸ while(P!=NULL)P=P->next;

⑹ while(Q->next!=NULL){P=Q;Q=Q->next;} ⑺ while(P->next!=Q)P=P->next;

⑻ while(P->next->next!=Q)P=P->next; ⑼ while(P->next->next!=NULL)P=P->next; ⑽ Q=P;

⑾ Q=P->next; ⑿ P=L;

-.47.-

本文来源：https://www.bwwdw.com/article/h287.html