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

《数据结构与算法》 第2章 线性表及其应用 第2章 线性表及其应用 本章学习要点 ◆掌握线性表的逻辑结构及相关概念。 ◆掌握线性表的两种基本存储结构，即线性顺序表（顺序表）和线性链表（链表）的存储结构。MATCH_ word word文档格式规范word作业纸小票打印word模板word简历模板免费word简历 _1714108807138_1线性表在各种存储方式之间的差异及其各自的优缺点。 ◆熟练掌握顺序表和链表上各种基本操作的实现过程。 ◆灵活运用顺序表和链表的特点解决实际应用问题。 线性表（Linear List）是一种最基本、最常用的数据结构。它有两种基本存储表示方法：顺序表和链表。线性表的基本操作主要有插入、删除和查找等。本章将具体给出线性表的定义、存储结构、基本运算及其算法实现，最后给出线性表的应用实例。 2.1线性表的定义和基本运算 2.1.1线性表的定义 线性表是n(n≥0)个同类型数据元素（ 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 或结点）的有限序列： 。记为： 。 其中：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是最后一个元素没有后继。 【例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．顺序表概念 一个线性表在计算机中可以用不同的方法来存储，其中最简单和最常用的一种存储方式是将线性表中的所有元素，按照其逻辑顺序依次存储到计算机内存中的从指定位置开始的一块连续的存储单元中。用这种存储方式表示的线性表称为线性顺序表简称顺序表。 设顺序表 中元素 的首地址为 ，每个元素需要占用的字节数为 ，则表中任一元素 的存储位置 可用下面的公式算出： 顺序表中各元素在内存中所占的位置如图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所示。 算法实现 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查找失败返回0。 算法实现 int LocateElem_Sq(SqList L,ElemType e) { int i=0; while(iL.length+1)return 0; //插入位置不合理时返回0值 if(L.length==L.listsize) IncSize(L); for(k=L.length,i--;k>i;k--) L.elem[k]=L.elem[k-1]; //为第i个元素的插入留出一个空位 L.elem[i]=e; L.length++; //修改长度 return 1; } 算法分析 从以上算法可见，在不考虑扩容的情况下，插入运算的时间主要花费在元素的向后移动上。假定表的长度为n,每个位置插入的机会都是相同的，即第i个位置插入的概率为 ，那么插入操作平均移动元素的次数为： 。插入操作的时间复杂度是按最坏的情况考虑，即插入到表中开始的位置，所以元素的移动次数为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(i<1||i>L.length)return 0; //如果删除的位置i不合理返回0 e=L.elem[i-1]; //置e的值为L中第i个元素的值 while(i 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 输出设备 else { for(int i=0;i>n; cout<<"输入"<>e; 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) { cout<<"1--提取第i个元素， 2--修改第i个元素的值，3--插入第i个元素\n"; cout<<"4--删除第i个元素的值，5--查找元素e的位置，6--显示当前表的 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 \n"; cout<<"7--退出演示程序："; cout<<” 输入选择:”;cin>>num; switch(num) { case 1: cout<<"输入位置i:"; cin>>i; if(GetElem_Sq(L,i,e)) cout<<"第"<>i>>e; if(!SetElem_Sq(L,i,e)) cout<<"输入的位置不合理,修改不成功\n"; break; case 3: cout<<"输入插入位置i和值e:"; cin>>i>>e; if(!InsertList_Sq(L,i,e)) cout<<"插入的位置不合理,操作不成功\n"; break; case 4: cout<<"输入删除位置i:"; cin>>i; if(!DeleteList_Sq(L,i,e)) cout<<"删除位置不合理,删除操作失败\n"; else cout<<"位置: "<>e; if(!(i=LocateElem_Sq(L,e))) cout<<"查找不成功\n"; else cout<<"表中位置: "<>n>>m; //输入n、m的值 InitList_Sq(L); //初始化L for(i=1;i<=n;i++) //置第i个人的编号为i InsertList_Sq(L,i,i); cout<<"所求编号序列为:\n"; k=0; for(i=0;inext=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; 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所示。 算法实现 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; 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<>n; cout<<"输入"<>e; InsertList_L(L,i,e); } } 2．单链表的综合演示主程序 void main_L() { LinkList L; ElemType e; int i,num; Create_L(L); TraverseList_L(L); while(1) { cout<<"1-提取第i个结点的值，2-修改第i个结点的值，3-插入第i个结点\n"; cout<<"4-删除第i个结点，5-查找第一个数据为e的结点，6-显示当前链表的内容\n"; cout<<"7-退出演示程序\n"; cin>>num; switch(num) { case 1: cout<<"输入位置i:"; cin>>i; if(GetElem_L(L,i,e)) cout<<"第"<>i>>e; if(!SetElem_L(L,i,e)) cout<<"输入的位置不合理,修改不成功\n"; break; case 3: cout<<"输入插入位置i和值e:"; cin>>i>>e; if(!InsertList_L(L,i,e)) cout<<"插入的位置不合理,操作不成功\n"; break; case 4: cout<<"输入删除位置i:"; cin>>i; if(!DeleteList_L(L,i,e)) cout<<"删除位置不合理,操作失败\n"; else cout<<"第"<>e; if(!LocateElem_L(L,e)) cout<<"查找不成功\n"; else cout<<"数据为"<next==NULL，而在循环链表中空表的条件为h->next==h。 （2）指向链尾结点的指针p在单链表中满足的条件是p->next==NULL,而在循环链表中满足的条件是p->next==h. 2.5.2双向链表 在有n个结点的单链表或单向循环链表中，求一个结点的直接后继结点的时间复杂度为O(1)，而求它的直接前驱结点的时间复杂度均为O(n)。其原因是在结点中只有一个指向直接后继结点的指针，而不含指向直接前驱结点的指针信息。为此给出以下双向链表的概念。 1．双向链表 双向链表中，结点的结构在单链表结点结构(data,next)的基础上再增加一个指向直接前驱结点的指针域prior。带有头结点的双向链表的结构如图2.9所示。 在C++语言中用以下结构类型来表示双向链表中一个结点的结构类型： typedef struct DNode { ElemType data; DNode *next,*prior; }*DLinkList; 其中，DNode为双向链表的结点结构类型，DLinkList为指向该结点的指针类型。 2．双向循环链表 与单向循环链表类似，在双向链表中，使头结点的prior指针指向尾结点且使尾结点的next指针指向头结点，这样就构成一个双向循环链表。带有头结点的双向循环链表的结构如图2.10所示。 双向链表的特点是可以直接求得链表中任意一个结点的直接前驱结点和直接后继结点。但是由于增加了一个指针域，相对于单向链表而言，其存储密度有所降低。 2.5.3静态链表 1．静态链表的概念 在有些计算机高级语言中没有设置指针类型，所以不能直接使用线性表的链式存储结构。在这样的语言环境中可借用一维数组来描述线性链表的存储结构，即静态链表存储方式。 在C++语言中静态链表的结构类型定义如下： const int MAXSIZE=1000; //链表的最大长度 typedef struct SNode{ ElemType data; int cur; }SLinkList[MAXSIZE]; 其中，SNode为静态链表的结点类型（相当于链表的结点类型），数据域data中存放元素的数据，下标（游标）域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; for(i=0;i>n; cout<<"输入"<>e; if(!InsertList_S(SS,p,i+1,e)) { cout<<"空间已满!\n"; break; } } cout<<"链表的初始内容为:\n"; TraverseList_S(SS,p); cout<<"1-在第i个结点前插入一个结点,2-删除第i个结点\n"; cout<<"3-显示当前链表的内容,4-显示可用空间长度\n"; cout<<"5-退出演示程序. "; while(1) { cout<<“输入选择:”; cin>>num; switch(num) { case 1: cout<<"输入插入位置i和值e:"; cin>>i>>e; 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<<"第"<