《第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章 线性表及其应用

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

2.4线性表的链式存储表示与实现

2.4.1线性表的链式存储

1．线性链表的概念

线性链表的存储结构是可以用任意一组存储单元来存放线性表中的数据元素，即这些存储单元在内存中可以是连续的也可以是不连续的。为了能正确表示线性表中的每个数据元素以及它们之间存在的逻辑关系（前驱与后继关系），对于一个数据元素ai来说，除了要存储它本身的信息之外，还需要存储指示其直接后继元素ai?1的指针（地址）信息。由以上两部分信息结合起来构成线性链表中的一个数据元素，称之为结点（node）。结点中存储数据信息的区域称为数据域（data）,而存储其直接后继元素存储位置的区域称为指针域（next）。结点的结构如图2.4(a)所示。

含有n个数据元素的线性表 Ln??a0,a1,?,an?1?，按图2.4(b)所示的方法构成一个具有n个结点的链表，称为线性表的链式存储结构。由于此种存储结构的链表中，每个结点只包含一个指针域，所以称之为线性链表或单链表。在图2.4(b)中，h称为单链表的表头指针，它指向链表中第一个结点的存储位置。由于最后一个结点没有直接后继，它的指针域为空，通常用NULL（或^）来表示。

-.23.-

《数据结构与算法》

为了对单链表的各种操作进行统一处理和方便表示，在链表的开头增设一个结点称为头结点，它的结构与链表中其他结点的结构一样，但在data域中不存放数据。如图2.5(a)表示空表，而图2.5(b)表示非空表，它们在形式上是一致的。

2．单链表结点结构的定义

根据单链表中结点结构的特点，在C++语言中用以下结构类型来表示一个结点的结构类型：

typedef struct Node //定义单链表的结点结构类型Node {

ElemType data; Node *next;

}*LinkList; //定义指向结点Node的指针类型LinkList 以上语句同时定义了结点的结构类型Node和指向该类型结点的指针类型LinkList。在这种结构的表示下，关于线性表的插入和删除操作相对于顺序表而言简单了许多。

2.4.2带头结点的单链表中基本操作的实现

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

该操作是构造一个只含有头结点的空链表L。其中L为指向头结点的指针。 算法实现

void InitList_L(LinkList &L)

{ L=new Node; //L指向头结点 L->next=NULL; //置头结点的指针域为空 }

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

提取操作的功能为提取链表L中第i个结点的数据域（data）的值到e中。如果提取成功（即位置i合理）返回1否则返回0。 算法实现

int GetElem_L(LinkList L,int i,ElemType &e) { int k; LinkList p=L->next;

-.24.-

第2章 线性表及其应用

}

for(k=1;knext;

if(i<1||!p)return 0; //位置i不合理返回0 e=p->data; 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个结点的指针p if(i<1||!p)return 0; //位置i不合理返回0 p->data=e; return 1; }

4．查找操作LocateElem_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）如果查找不成功（即位置i不合理）返回0； （3）在堆空间中分配新的结点q； （4）置q的数据域的值为e；

（5）将q插入到L中p->next之前、p之后。用语句q->next=p->next;和p->next=q;实现。 （6）返回1表示插入成功。操作结果如图2.6所示。

-.25.-

《数据结构与算法》

算法实现

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个结点的直接前驱结点的指针p if(i<1||kdata=e; //置q中数据域的值为e q->next=p->next; //将q插入L中第i个结点之前 p->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 i,ElemType &e) { LinkList p=L,q;

-.26.-

第2章 线性表及其应用

}

int k;

for(k=1;knext;k++) p=p->next;

if(i<1||!p->next)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中每个结点中数据域的值。 算法实现

void TraverseList_L(LinkList L) { LinkList p=L->next; if(!p) cout<<\链表为空表.\\n\ else { cout<<\链表中的数据有:\\n\ while(p) { cout<data<<\ p=p->next; } cout<

2.4.3 线性链表中基本操作的综合演示程序

在前面链表的结构定义及其基本操作算法的基础上，本节给出关于链表中基本操作的综

-.27.-

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