第章线性表及其应用习题解答.doc

第2章 线性表及其应用 本章学习要点 ◆掌握线性表的逻辑结构及相关概念。 ◆掌握线性表的两种基本存储结构线性顺序表（顺序表）和线性链表（链表）的存储结构。体会各种存储方式之间的差异及其各自的优缺点。◆熟练掌握顺序表和链表上各种基本操作的实现过程。 ◆灵活运用顺序表和链表的特点解决实际应用问题。 线性表（Linear List）是一种最基本、最常用的数据结构。有两种基本存储表示方法顺序和链表。线性表的基本操作主要有插入、删除和查找。本章将具体给出线性表的定义、存储结构、基本及其算法实现，最后给出线性表的应用实例。 2.1线性表的定义和基本运算 2.1.1线性表的定义 是n(n≥0)个同类型数据元素（记录或结点）的有限序列：…,an-1。 记为：…,an-1)。 其中：是是终端结点是的直接前驱结点，而是的直接后继结点；终端结点没有后继结点，开始结点没有前驱结点；元素在表中的位置为i+1；元素的个数n称为线性表L的长度，长度为零的线性表叫空表。 需要说明的是：在C/C++语言中，数组元素的下标是从0开始，n个元素的数组A的所有元素为A[0],A[1],…,A[n-1]。定义中第i个元素的下标为i-1,即元素的位置等于其下标加1。 日常生活中，线性表的例子很多 【例2.1】（1，3，5，7，9，2，4，6，8，10）是一个线性表。其中的数据元素是整数，线性表的长度为10。按表中的排列顺序，元素1是第一个元素没有前驱，元素10是最后一个元素没有后继。【例2.2】（0,1,2,3,4,5,6,7,8,9,A,B,C,D,…,X,Y,Z）是一个线性表。其中的数据元素是所有数字字符和所有大写字母字符，线性表的长度为36。按表中的排列顺序，元素‘0’是第一个元素没有前驱，元素‘Z’是最后一个元素没有后继。 【例2.3】由图2.1所示的学生基本情况表也是一个线性表。线性表中的元素是由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）插入InsertListL,i,e)：将e插入到表L中的第i个位置。 （6）删除DeleteListL,i,e)：删除表L中的第i元素，并用e返回该元素的值。 （7）求表长Length(L):返回线性表L的长度。 （8）遍历TraverseListL)：依次输出L中每个元素的值。 在线性表的其它操作中，有些操作可以通过调用基本操作来实现，有些操作比如线性表的排序和归并等操作的实现将在以后的章节中进行。 2.2线性表的顺序存储表示与实现 2.2.1线性表的顺序存储1．顺序表概念 一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。设顺序表中元素的首地址为，每个元素需要占用的字节数为，则表中任一元素的存储位置可用下面的公式算出： 顺序表中各元素在内存中所占的位置如图2.2所示。 2．顺序表的结构定义 顺序表的存储结构和一维数组的存储结构极为相近；但是由于在线性表中允许执行插入和删除等操作，也就是说一个线性表的长度是可变的，为适应这种情况在C++语言中用以下结构类型来表示顺序表。 typedef int ElemType; //为了方便上机调试程序，本章假定数据元素的类型为整型 const int MLEN=100; //定义顺序表存储空间大小的初始分配常量 const int INCSIZE=50; //定义顺序表存储空间的扩充常量值 struct SqList //定义顺序表的结构类型为SqList{ ElemType *elem; //存储空间的基址 int length; //线性表的长度 int listsize; //当前表的存储容量 int incsize; //一次增补的容量值 }; 在结构表示下，许多关于线性表的运算（如存、取、求表长和置表空）极易实现。主要讨论关于顺序表的插入、删除、查找和遍历等操作。 2.2.2顺序表中基本操作的实现 1初始化操作InitListL) 该操作的功能是构造一个空线性顺序表L。