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

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

2、1线性表的定义和基本运算2. 1.1线性表的定义线性表是n(n20)个同类型数据元素(记录或结点)的有限序列:aO, al, a2,an-lo 记为:Ln=(aO, al, a2, ,» an-l) o其中：aO是开始结点，an-l是终端结点，ak是ak+1的直接前驱结点，而ak+1是ak 的直接后继结点(k=0,l,2,?,n-2)：终端结点an-l没有后继结点，开始结点aO没有前驱 结点；元素ai(i=0,l,2?,n-l)在表中的位置为i+1；元素的个数n称为线性表L的长度， 长度为零的线性表叫空表。需要说明的是：在C/C+语言中，数组元素的下标是从0开始的，具有n个数据元素

3、的数组A的所有元素为,An-1。在线性表的定义中，第i个元素的下标为 i-1,即元素的位置等于其下标加日常生活中，线性表的例子很多：【例2.1】 L10= (1, 3, 5, 7, 9, 2, 4, 6, 8, 10)是一个线性表。其中的数据元素 是整数，该线性表的长度为10。按表中的排列顺序，元素1是第一个元素没有前驱，元素 10是最后一13.-数据结构与算法个元素没有后继。【例 2.2L36二(0,1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, X, Y, Z)是一个线性表。其中的 数据元素是所有数字字符和所有大写字母字符，线性表的长度为36。按表中的排列顺序

4、， 元素?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(&U i, e)：修改表L中第i个元素的值为e的运算。(4)查找LocateElem(L, e)：查找表L中第一个值与e相同的元素的位置。(5)插 入In

5、sertList (&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.顺序表概念一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方 式是将线性

6、表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始 的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。设顺序表Ln?a0, al, ?, an?l?中元素aO的首地址为LOC (a0),每个元素需要占用的字 节数为1,则表中任一元素ai的存储位置LOC(ai)可用下面的公式算出：LOC(ai)?LOC(aO)?i?l(i?O, 1,2, ?, n?l)顺序表中各元素在内存中所占的位置如14.-第2章线性表及其应用图2. 2所示。2.顺序表的结构定义顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插 入和删除等操作，也就是说一个

7、线性表的长度是可变的，为适应这种情况在C+语言中用 以下结构类型来表示顺序表。typedef int ElemType;为了方便上机调试程序，本章假定数据元素的类型为整型const int N!AXLEN=100;定义顺序表存储空间大小的初始分配常量const int INCSIZE=50;定义顺序表存储空间的扩充常量值struct SqList定义顺序表的结构类型为SqList ElemType *elem;存储空间的基址int length;线性表的长度int listsize;当前表的存储容量int incsize;一次增补的容量值;在以上结构表示下，许多关于线性表的运算(如存、取、求线

8、性表的长度和置表空等 操作)极易实现。以下主要讨论关于顺序表的插入、删除、查找和遍历等操作。2. 2. 2顺序表中基本操作的实现1.初始化操作 InitList_Sq(&L)该操作的功能是构造一个空线性顺序表Lo算法思想(1)在堆空间中为线性表动态分配一块连续的存储单元，返回首地址到elem; (2) 置线性表的长度值length为0;(3)置表的当前容量listsize为动态分配时的大小；(4)置容量扩充值incsize 的大小为INCSIZEo线性表L的初始化存储结构如图2. 3所示。二 15. 一数据结构与算法算法实现void InitList_Sq(SqList &L,

9、int maxlength=MAXLEN, int incsize=INCSIZE) L. elem=new ElemTypeLmaxlength;动态分配一个长度为maxlength的连续存储空间，类型为ElemTypet返回首地址到 L. elem)L. length=O;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<l i>L. length) return 0; 如果位置i不合理时返回。值else e=L.;通过参数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<l i>L.