数据结构学习指导定稿

数据结构学习指导主编孙凌李丹副主编王桂芝周琳高大利

前言本书是与教材《数据结构》配套的教学辅导书，共分8章，顺序与《数据结构》教材前8章的顺序一致。内容包括各章的讲课提要、学习指导、习题及参考答案。编者根据多年的教学积累，对各章的知识要点进行归纳和总结，精心编写了近一百道例题和近四百道练习题，覆盖了本课程的全部教学内容。本书不仅可供学生进行学习辅导，也可供教师教学参考。通过阅读本书，将有助于学生加深对根底理论知识的理解，更可以通过大量的练习培养学生实际应用的能力。特别要提醒的是，本书每章练习均配有参考答案，希望读者合理使用参考答案，尽量不要在解题之前先看答案，以免干扰自己的思考过程。对于每个算法设计题来说，解题方法往往有许多种，参考答案中给出的不一定是最好的。本书第1章、第3章和第4章由周琳编写；第2章由王桂芝编写；第5章由李丹编写；第6章由高大利编写；第7章和第8章由孙凌编写。李丹负责统编全稿。本书在编写过程中力求概念清晰，表述正确，通俗易懂，便于自学。由于时间仓促，且作者水平有限，书中可能会有一些错误，恳请读者批评指正。作者2005年7月

目录TOC\o"1-2"\u第1章概述 5讲课提要 5学习指导 5习题1 8习题1参考答案 11第2章线性表 12讲课提要 12学习指导 13习题2 17习题2参考答案 21第3章串 28讲课提要 28学习指导 28习题3 30习题3参考答案 32第4章数组和广义表 34讲课提要 34学习指导 34习题4 38习题4参考答案 41第5章树 42讲课提要 42学习指导 43习题5 52习题5参考答案 56第6章图 62讲课提要 62学习指导 63习题6 71习题6参考答案 76第7章查找 82讲课提要 82学习指导 82习题7 90习题7参考答案 92第8章内部排序 95讲课提要 95学习指导 96习题8 104习题8参考答案 107

第1章概述讲课提要【主要内容】1．数据结构的研究目的和研究内容2．数据结构中的几个重要概念和术语3．算法设计的根本要求以及算法复杂度的分析和计算方法【教学目标】1．了解数据结构的研究目的和研究内容2．掌握数据结构中的重要概念和术语3．掌握算法设计的根本要求以及算法复杂度的分析和计算方法【所需课时】2次课。[第一次课]1．数据结构的研究目的和研究内容2．数据结构中的重要概念和术语[第二次课]3．算法设计的根本要求以及算法复杂度的分析和计算方法学习指导1．概念和术语数据：是能输入到计算机中并能被计算机程序处理的符号的总称。数据元素：是数据的根本单位，它在计算机处理和程序设计中通常作为一个整体进行考虑和处理。一个数据元素可由假设干数据项组成。数据对象：是具有相同特征的数据元素的集合，是数据的一个子集。数据结构：是数据元素的组织形式，或数据元素相互之间存在一种或多种特定关系的集合。数据的逻辑结构：是指数据结构中数据元素之间的逻辑关系。数据的存储结构：是数据的逻辑结构在计算机内存中的存储方式，又称物理结构。数据类型：是一组具有相同性质的操作对象以及该组操作对象上的运算方法的集合。抽象数据类型：是指一个数学模型以及在该模型上定义的一套运算规那么的集合。算法：建立在数据结构根底上的，为解决问题而采取的步骤和方法。2．逻辑结构的四种根本形态根据数据元素之间关系的不同特征，通常有以下四类根本结构：〔1〕集合：结构中的数据元素间除了“同属于一个集合”的关系外，别无其它关系。〔2〕线性结构：结构中的数据元素之间存在一个对一个的关系。〔3〕树型结构：结构中的数据元素之间存在一个对多个的关系。〔4〕图型结构或网状结构：结构中的数据元素之间存在多个对多个的关系。3．数据存储结构的根本组织方式 数据存储结构有顺序和链式两种方式。〔1〕顺序存储结构的特点：要借助数据元素在存储器中的相应位置来表达数据元素相互间的逻辑关系，常用高级编程语言中的“一维数组”来描述或实现。〔2〕链式存储结构的特点：通过表示数据元素存储地址的指针来表示数据元素之间的逻辑关系，通常用链表来实现。在顺序存储结构的根底上，又可延伸变化出另外两种存储结构，即索引存储和散列存储。〔1〕索引存储就是在数据文件的根底上增加了一个索引表文件。通过索引表建立索引，可以把一个顺序表分成几个顺序子表，其目的是在查询时提高查找效率，防止盲目查找。〔2〕散列存储就是通过数据元素与存储地址之间建立起某种映射关系，使每个数据元素与每一个存储地址之间尽量到达一一对应的目的。这样，查找时同样可大大提高效率。4．数据结构的研究内容数据结构的核心研究内容包括三个方面：数据的逻辑结构、存储结构以及相应的根本操作运算的定义和实现。5．算法的五个重要特征〔1〕有穷性：一个算法必须保证在执行有限步骤之后结束，而不是无限的。〔2〕确定性：算法中每一条指令必须有明确的含义，而不能是模棱两可的。〔3〕可行性：每一个操作步骤都必须在有限的时间内完成。〔4〕输入：一个算法可以有一个或多个输入，也可以没有输入。〔5〕输出：一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。6．算法的评价标准〔1〕正确性。〔2〕易读性。〔3〕高效性。〔4〕可维护性。7．算法分析的目的算法分析主要是指分析算法的效率。算法效率的度量主要从两个方面：算法的运行时间和算法所需的存储空间。分析的目的是通过考察算法的时间和空间效率，以求改良算法或对不同的算法进行比拟。一般情况下，鉴于运算空间〔内存〕较为充足，所以把算法的时间复杂度分析作为重点。8．算法的时间复杂度分析〔1〕算法运算时间的度量的两种方法：事后统计的方法和事前分析估算的方法。〔2〕算法运行时间的分析规那么通常把一个程序的运行时间定义为一个T〔n〕，其中n是该程序输入数据的规模，而不是某一个具体的输入。T(n)的单位是不确定的，一般把它看成在一个特定计算机上执行的指令条数。通常记作：T(n)=O(f(n))，其中f(n)表示数据输入规模。常见的算法时间复杂度的形式按性能降序的排列如下：O(1)<O()<O(n)<O(n*)<O()<O()<O()【例1-1】分析以下程序段的时间复杂度。for(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;解：该程序段的时间复杂度为O(m*n)。【例1-2】分析以下程序段的时间复杂度。i=s=0;①while(s<n){i++;②s+=i;③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O(1)。语句②和语句③构成while循环语句的循环体，它们的执行次数由循环控制条件中s与n的值确定。假定循环重复执行x次后结束，那么语句②和语句③各重复执行了x次。其时间复杂度按线性累加规那么为O(x)。此时s与n满足关系式：s≥n，而s=1+2+3+…+x。所以有：1+2+3+…+x≥n，可以推出：x=x与n之间满足x=f(〕，所以循环体的时间复杂度为O()，语句①与循环体由线性累加规那么得到该程序段的时间复杂度为O(〕。【例1-3】分析以下程序段的时间复杂度。i=1;①while(i<=n)i=2*i;②解：其中语句①的执行次数是1，设语句②的执行次数为f(n)，那么有：。得：T〔n〕=O()【例1-4】有如下递归函数fact(n)，分析其时间复杂度。fact(intn){if(n<=1)return(1);①elsereturn(n*fact(n-1));②}解：设fact〔n〕的运行时间函数是T(n)。该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+O(1)，其中O(1)为常量运行时间。由此可得fact〔n〕的时间复杂度为O(n)。9．算法空间复杂度的含义空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。算法在计算机存储器内占用的存储空间主要分为三局部：算法源代码本身占用的存储空间；算法输入输出数据所占用的存储空间；算法运行过程中临时占用的存储空间。考虑一个算法的空间复杂度时，要综合分析这三个方面的因素。通常记作：S(n)=O(f(n))，其中n为问题的规模〔或大小〕。习题1一、单项选择题1.数据结构是指〔〕。2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为〔〕。A.存储结构 B.逻辑结构3.树形结构是数据元素之间存在一种〔〕。A.一对一关系 B.多对多关系4.设语句x++的时间是单位时间，那么以下语句的时间复杂度为〔〕。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1) B.O() C.O(n) D.O()5.算法分析的目的是〔1〕，算法分析的两个主要方面是〔2〕。〔1〕〔2〕6.计算机算法指的是〔1〕，它具备输入，输出和〔2〕等五个特性。〔1〕〔2〕A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和平安性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要〔〕。8.数据结构作为一门独立的课程出现是在〔〕年。A.1946 B.1953 C.19649.数据结构只是研究数据的逻辑结构和物理结构，这种观点〔〕。C.前半句对，后半句错 D.前半句错，后半句对10.计算机内部数据处理的根本单位是〔〕。二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。2.数据的逻辑结构有四种根本形态，分别是________________、__________________、__________________和__________________。3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。4.一个算法的效率可分为__________________效率和__________________效率。5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。8.下面程序段的时间复杂度是__________________。for(i=0;i<n;i++)for(j=0;j<n;j++)A[i][j]=0;9.下面程序段的时间复杂度是__________________。i=s=0;while(s<n){i++;s+=i;}10.下面程序段的时间复杂度是__________________。s=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;11.下面程序段的时间复杂度是__________________。i=1;while(i<=n)i=i*3;12.衡量算法正确性的标准通常是____________________________________。13.算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。三、求以下程序段的时间复杂度。1.x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;2.x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;3.inti,j,k;for(i=0;i<n;i++)for(j=0;j<=n;j++){c[i][j]=0;for(k=0;k<n;k++) c[i][j]=a[i][k]*b[k][j]}4.i=n-1;while((i>=0)&&A[i]!=k))j--;return(i);5.fact(n){if(n<=1)return(1);elsereturn(n*fact(n-1));}习题1参考答案一、单项选择题1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4.时间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.O()9.O()10.O()11.O(logn)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题 1.O()2.O()3.O(n)4.O(n)5.O(n)

第2章线性表讲课提要【主要内容】1．线性表的概念和根本运算2．顺序表〔线性表的顺序存储结构〕3．链表〔线性表的链式存储结构〕〔1〕单链表和循环单链表〔2〕双向链表和循环双链表4．线性表应用〔1〕栈〔2〕队列【教学目标】1．了解线性表的概念及其常用运算2．熟悉顺序表的结构及根本算法描述3．掌握单链表的结构及根本算法描述，了解双向链表及循环链表4．掌握栈和队列的结构特点及其插入和删除算法5．了解栈在程序设计中的实际应用【所需课时】7次课。[第一次课]1．线性表的定义及其运算2．顺序表的存储结构[第二次课]3．顺序表的根本运算4．顺序表的算法描述及算法分析[第三次课]5．单链表的结构及其算法实现6．循环单链表的结构及其算法实现[第四次课]7．双向链表的结构及其算法实现8．循环双链表的结构及其算法实现[第五次课]9．栈的定义及其结构特点10．顺序栈的结构及其算法实现[第六次课]11．链栈的结构及其算法实现12．栈的应用[第七次课]13．队列的定义及顺序存储14．队列的链式存储学习指导1．线性表的定义线性表是n个数据元素的有限序列，其中n〔n≥0〕为线性表的长度。线性表中各个元素的类型相同。对于线性表〔a1，a2，…，ai，…，an〕而言，数据元素a1没有直接前趋，an没有直接后继，表中的其它元素ai〔2≤i≤n-1〕有且仅一个直接前趋ai-1和直接后继ai+1。2．顺序表顺序表是指线性表的顺序存储结构，即用一组连续的存储单元依次存放线性表的数据元素。在C语言中可用一维数组来表示。在顺序表中，以数据元素在计算机内“物理位置相邻”来表示表中数据元素间的逻辑关系。顺序表是一种随机存储结构，只要确定了存储顺序表的起始位置，那么表中任一元素都可以随机存取。所以在顺序表中可以方便的进行数据元素的查找及存取。但是在进行插入和删除操作时，将会引起元素的大量移动，因而效率比拟低，并且易产生空间浪费或“上溢”现象。顺序表的操作还应注意元素的存储位置，即数组下标〔C语言中下标从0开始〕。【例2-1】试编写出将两个顺序存储的有序表A和B合成一个有序表C的算法。解：假设A、B和C的类型为下述SqList类型：#definemaxlen1000typedefintelemtypetypedefstruct{elemtypeelem[maxlen];intlen;}SqList;设A和B的数据元素均为整数且为升序排列，设A的长度为m，B的长度为n，那么合并后C的长度为m+n。合并时进行A、B元素的比拟，将较小的链入C中，算法描述如下：intmerge(SqList*A,SqList*B,SqList*C)//将两个有序表A和B合成一个有序表C{intm,n,i,j,k;m=(*A).len;n=(*B).len;if(m+n>maxlen-1){printf("overflow");exit(0);}i=0;j=0;//i和j分别作为扫描顺序表A和B的指针k=0;//k指示顺序表C中当前位置while((i<=m)&&(j<=n))if((*A).elem[i]<＝(*B).elem[j]){(*C).elem[k]＝(*A)elem[i];i++;k++;}else{(*C).elem[k]＝(*B)elem[j];j++;k++;}while(i<=m)//表B已结束，表A没有结束，链入表A的剩余局部{(*C).elem[k]＝(*A).elem[i];i++;k++;}while(j<=m)//表A已结束，表B没有结束，链入表B的剩余局部{(*C).elem[k]＝(*B).elem[j];i++;k++;}return(1);}3．链表链表是线性表的链式存储结构。链表是用一组任意的存储单元〔可以是连续的，也可以是不连续的〕存放线性表的数据元素。在链表中，通过指针来表示元素之间的逻辑关系的，不再有逻辑顺序与物理存储顺序一致的特点，是非顺序存储结构。在单链表中，每个结点由数据域和指针域组成。数据域保存数据元素的信息，指针域存放其直接后继的存储位置。其类型可描述为：typedefstructNode{elemtypedata;structNode*next;}LinkList;单链表由头指针唯一确定。为了便于操作，可在链表的第一个结点之前添加一个表头结点。在链表中进行插入和删除操作只需要修改有关的指针内容，不需要移动元素。因此，链表较顺序表的插入和删除操作更加方便、高效。为了便于实现各种运算，假设无特殊说明，均采用带头结点的链表。【例2-2】写一算法实现单链表的逆置。解：假设单链表的表头指针用head表示，其类型为上面定义的LinkList，并且单链表不带头结点。逆置后原来的最后一个结点成为第一个结点，于是从第一个结点开始逐个修改每个结点的指针域进行逆置，且刚被逆置的结点总是新链表的第一个结点，故令head指向它〔如图2-1所示〕。具体算法描述如下：图2-1单链表逆置示意图图2-1单链表逆置示意图示示图head∧…head∧qphead…q(a)单链表初始状态示示图(b)第三个结点逆置示示图voidcontray(LinkList*head){//将head单链表中所有结点按相反次序链接LinkList*p,*q;p=head;//p指向未被逆序的第一个结点,初始时指向原表头结点head=NULL;while(p!=NULL){q=p;//q指向将被逆序链接的结点p=p->next;q->next=head;head=q;}}【例2-3】假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，p为指向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下：voiddelete(LinkList*p){//在链表中删除p所指结点的前趋结点LinkList*q,*t;q=p;while(q->next->next!=p)//q->next不是p的前趋结点q=q->next;t=q->next;//t指向要删除结点q->next=p;//删除t结点free(t);｝【例2-4】试设计实现删除单链表中值相同的多余结点的算法。解：该例可以这样考虑，先取开始结点的值，将它与其后的所有结点值一一比拟，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。设单链表〔其类型为LinkList〕的头指针head指向头结点，那么可按以下步骤执行：首先，用一个指针p指向单链表中第一个表结点，然后用另一个指针q查找链表中其余结点元素，由于是单链表，故结束条件为p==NULL，同时让指针s指向q所指结点的前趋结点，当查找到结点具有q->data==p->data时删除q所指的结点，然后再修改q，直到q为空；然后使p指针后移〔即p=p->next〕，重复进行，直到p为空时为止。算法描述如下：del(LinkList*head){//删除单链表中值相同的多余结点LinkList*p,*s,*q;p=head->next;while(p!=NULL&&p->next!=NULL){s=p;//s指向要删除结点的前趋q=p->next;while(q!=NULL){if(q->data==p->data)}//查找值相同的结点并删除{s->next=q->next;free(q);q=s->next;}else{s=q;q=q->next;}}p=p->next;}}4．栈栈〔Stack〕是限定仅在表的一端进行插入或删除操作的线性表。通常把允许插入和删除操作的一端称为栈顶〔Top〕，而另一端称为栈底〔Bottom〕。表为空时称为空栈。在栈上的主要运算是入栈和出栈。栈中元素如果按a1，a2，…，an的顺序进栈，那么出栈顺序为an，an-1，…，a1。因此，栈又称为“后进先出”〔LastInFirstOut〕的线性表，简称LIFO表。同线性表相似，栈也有顺序栈和链栈两种存储结构。顺序栈易产生“上溢”现象，而链栈不容易产生。另外，注意对栈的操作只能在栈顶进行。5．队列队列〔Queue〕是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。通常把允许插入的一端称为队尾〔rear〕，允许删除的一端称为队头〔front〕。队列中元素如果按a1，a2，…，an的顺序进队，那么出队的顺序仍为a1，a2，…，an。因此，队列又称为“先进先出”〔FirstInFirstOut〕的线性表，简称FIFO表。队列也有顺序队列和链队列两种存储结构。在顺序队列中，为防止“假满”现象，一般采用循环队列〔即首尾相接〕。链队列会因为队满而产生“上溢”现象。习题2一、单项选择题1.线性表是________。A．一个有限序列，可以为空 B．一个有限序列，不可以为空C．一个无限序列，可以为空 D．一个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。A．n-i B．n-i+l C．n-i-1 D．i3.线性表采用链式存储时，其地址________。A．必须是连续的 B．一定是不连续的C．局部地址必须是连续的 D．连续与否均可以4.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比拟________个元素结点。A．n/2 B．n C．〔n+1〕/2 D．〔n-1〕/25.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.设单链表中指针p指向结点m，假设要删除m之后的结点〔假设存在〕，那么需修改指针的操作为________。A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7.在一个长度为n的顺序表中向第i个元素(0<i<n+l)之前插入一个新元素时，需向后移动______个元素。A．n-i B．n-i+l C．n-i-1 D．i8.在一个单链表中，q结点是p结点的前趋结点，假设在q和p之间插入s结点，那么须执行A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下关于线性表的说法不正确的选项是______。

A．线性表中的数据元素可以是数字、字符、记录等不同类型。B．线性表中包含的数据元素个数不是任意的。C．线性表中的每个结点都有且只有一个直接前趋和直接后继。D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。10.线性表的顺序存储结构是一种_______的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取11.在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。A．基地址 B．结点大小C．向量大小 D．基地址和结点大小12.在等概率情况下，顺序表的插入操作要移动______结点。

A．全部 B．一半

C．三分之一

D．四分之一13.在______运算中，使用顺序表比链表好。

A．插入

B．删除

C．根据序号查找

D．根据元素值查找14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。

A．O(1)

B．O(n)

C．O(n2) D．O(log2n)15.设有一个栈，元素的进栈次序为A,B,C,D,E,以下是不可能的出栈序列__________。A．A,B,C,D,E B．B,C,D,E,AC．E,A,B,C,D D．E,D,C,B,A16.在一个具有n个单元的顺序栈中，假定以地址低端〔即0单元〕作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。A．top不变 B．top=0 C．top-- D．top++17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，那么判断队满的条件为________。A．rear％n==front B．〔front+l〕％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，那么判断队空的条件为________。A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front20.在一个链队列中，假定front和rear分别为队首和队尾指针，那么删除一个结点的操作为________。A．front=front->nextB．rear=rear->nextC．rear=front->nextD．front=rear->next二、填空题1.线性表是一种典型的_________结构。2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。3.顺序表中逻辑上相邻的元素的物理位置________。4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。7.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，那么采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，那么采用_______存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。11.在单链表中设置头结点的作用是________。12.对于一个具有n个结点的单链表，在的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，那么说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。14.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。三、简答题1.描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，假设线性表的总数根本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么?6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功能是什么?LinkList*Demo(LinkList*L){//L是无头结点的单链表LinkList*q,*p;if(L&&L->next){q=L;L=L->next;p=L;while(p->next)p=p->next;p->next=q;q->next=NULL;}return(L);}四、算法设计题1.设计在无头结点的单链表中删除第i个结点的算法。2.在单链表上实现线性表的求表长ListLength(L)运算。3.设计将带表头的链表逆置算法。4.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data,next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域〔此域初值为NULL〕把所有结点按照其值从小到大的顺序链接起来。5.线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素〔假设表中存在这样的元素〕的算法。6.线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。7.假定用一个单循环链表来表示队列〔也称为循环队列〕，该队列只设一个队尾指针，不设队首指针，试编写以下各种运算的算法：〔1〕向循环链队列插入一个元素值为x的结点；〔2〕从循环链队列中删除一个结点。8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案一、单项选择题1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C 20．A二、填空题1．线性2．n-i+13．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇14．2、315．O(1)三、简答题1．头指针是指向链表中第一个结点〔即表头结点〕的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。假设链表中附设头结点，那么不管线性表是否为空表，头指针均不为空，否那么表示空表的链表的头指针为空。2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表那么是一种顺序存取的存储结构。5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，那么开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。假设用头指针来表示该链表，那么查找终端结点的时间为O(n)。6．共有14种可能的出栈序列，即为：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量〔即存储的空间大小〕为maxnum。当有元素要参加队列〔即入队〕时，假设rear=maxnum，那么会发生队列的上溢现象，此时就不能将该元素参加队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：〔1〕可建立一个足够大的存储空间以防止溢出，但这样做往往会造成空间使用率低，浪费存储空间。〔2〕要防止出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，那么可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原那么。8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题1．算法思想为：〔1〕应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作；〔2〕当i=0时，删除第一个结点：〔3〕当０<i<n时，允许进行删除操作，但在查找被删除结点时，须用指针记住该结点的前趋结点。算法描述如下：delete(LinkList*q,inti){//在无头结点的单链表中删除第i个结点LinkList*p,*s;intj;if(i<0)printf("Can'tdelete");elseif(i==0){s=q;q=q->next;free(s);}else{j=0;s=q;while((j<i)&&(s!=NULL)){p=s;s=s->next;j++;}if(s==NULL)printf("Cant'tdelete");else{p->next=s->next;free(s);}}}2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：intListLength(LinkList*L){//求带头结点的单链表的表长intlen=0;ListList*p;p=L;while(p->next!=NULL){p=p->next;len++;}return(len);}3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，那么只需进行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//当表不为空时，逐个结点逆置{s=q;q=p;p=p->next;q->next=s;}p->next=q;}4．定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到适宜位置将p结点链入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的结点，初始时指向第一个结点while(p!=NULL){s=head;//s指向q结点的前趋结点q=head->prior;//q指向由prior域构成的链表中待比拟的结点while((q!=NULL)&&(p->data>q->data))//查找插入结点p的适宜的插入位置{s=q;q=q->prior;}s->prior=p;p->prior=q;//结点p插入到结点s和结点q之间p=p->next;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head->next;while((p!=NULL)&&(p->data<=min)){q=p;p=p->next;}while((p!=NULL)&&(p->data<max))p=p->next;q->next=p;}}6．算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*p,*q;q=head;p=head->next;while(p!=NULL)if((p->data<=min)||(p->data>=max)){q=p;p=p->next;}else{q->next=p->next;free(p);p=q->next;}}7．此题是对一个循环链队列做插入和删除运算，假设不需要保存被删结点的值和不需要回收结点，算法描述如下：〔1〕插入〔即入队〕算法：insert(LinkList*rear,elemtypex){//设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如为空队，建立循环链队列的第一个结点{rear=p;rear->next=p;//链接成循环链表}else//否那么在队尾插入p结点{p->next=rear->next;rear->next=p;rear=p;}}〔2〕删除〔即出队〕算法：delete(LinkList*rear){//设循环链队列的队尾指针为rearif(rear==NULL)//空队printf("underflow\n");if(rear->next==rear)//队中只有一个结点rear=NULL;elserear->next=rear->next->next;//rear->next指向的结点为循环链队列的队头结点}8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：intInsertDecreaseList(SqList*L,elemtypex){inti;if((*L).len>=maxlen){printf(“overflow");return(0);}for(i=(*L).len;i>0&&(*L).elem[i-1]<x;i--)(*L).elem[i]=(*L).elem[i-1];//比拟并移动元素(*L).elem[i]=x;(*L).len++;return(1);}

第3章串讲课提要【主要内容】1．串的有关概念及根本操作2．串的存储结构3．串操作应用举例【教学目标】1．掌握串的有关概念及根本运算2．熟悉串的存储结构3．熟悉串操作应用举例【所需课时】一次课。1．串的有关概念及根本运算2．串的存储结构3．串操作应用举例学习指导1．概念和术语串〔String〕〔或字符串〕：是由零个或多个字符组成的有限序列。一般记为s=“aa…a”(n≥0)其中，s是串的名，用双引号括起来的字符序列是串的值。串的长度：串中字符的个数n。子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串：不包含任何字符的串，表示为“Ф”。空格串：由一个或多个空格字符组成的串。例如：“”。2．串的根本操作〔1〕用串变量赋值assign(s,t)和用串常量赋值create(s,ss)〔2〕判等函数 equal(s,t〕〔3〕求长函数 length(s)〔4〕连接函数 concat(s,t)〔5〕求子串函数 substring(s,pos,len)〔6〕定位函数 index(s,t)〔7〕置换函数 replace(s,t,v)〔8〕插入子串 insert(s,pos,t)〔9〕删除子串 delete(s,pos,k)〔10〕串的复制 copy(s,t)【例3-1】字符串：a=“anapple”，b=“otherhero”，c=“her”，求：〔1〕concat(substr(a,1,2),b)。〔2〕replace(a,substr(a,5,1),c)。〔3〕index(a,c)和index(b,c)。解：〔1〕返回值为“anotherhero”，其中substr(a,1,2)的返回值为“an”。〔2〕返回值为“anaherherle”，其中sub(a,5,1)的返回值为“p”。〔3〕返回值分别为0和3。3．串的顺序存储结构〔顺序串〕串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用C语言描述为：typedefstructstrnode{chardata[maxlen];intlen;}SeqString;//定义顺序串类型【例3-2】设定串采用顺序存储结构，写出对串s1和串s2比拟大小的算法。串值大小按字典排序〔升序〕方式，返回值等于-1，0和1分别表示s1<s2，s1=s2和s1>s2。解：算法思想：〔1〕比拟s1和s2共同长度范围内的对应字符：假设s1的字符>s2的字符，返回；假设s1的字符<s2的字符，返回；假设s1的字符=s2的字符，按上述规那么继续比拟；〔2〕当〔1〕中对应字符均相同时，比拟和的长度：两者相等时，返回0；前者>后者时，返回1；前者<后者时，返回-1；算法描述如下：#defineMAXLEN256structstrnode{chardata[MAXLEN];intlen;}SeqString;//定义顺序串类型intstrcmp(SeqStrings1,SeqStrings2)//比拟串s1和串s2的大小{intcomlen;if(s1.len<s2.len)comlen=s1.len;//求出串s1和串s2的共同长度elsecomlen=s2.len;for(i=0;i<comlen;i++)//在共同长度内逐个字符比拟if(s1.ch[i]<s2.ch[i])return(-1);//s1<s2elseif(s1.ch[i]>s2.ch[i])return(1);//s1>s2if(s1.ch[i]==s2.ch[i])return(0);//s1=s2elseif(s1.ch[i]<s2.ch[i])return(-1);//s1<s2elsereturn(1);//s1>s2}4．串的链式存储结构〔即链串或块链结构〕使用链式存储结构的字符串，只要存储空间足够大，其长度没有任何限制，但逻辑上的连续性不表达为物理上的邻接性。每个字符和一个指针域形成一个结点，结点间的关系由链指针实现，即字符逻辑上的连续性由链指针描述。其存储结构用C语言描述为：typedefstructstrnode{//定义字符串的结点类型chardata;structstrnode*next;}LinkString;习题3一、单项选择题1.空串与空格字符组成的串的区别在于〔〕。2.一个子串在包含它的主串中的位置是指〔〕。3.下面的说法中，只有〔〕是正确的。C.假设T包含在S中，那么T一定是S的一个子串4.两个字符串相等的条件是〔〕。A.两串的长度相等C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同5.假设SUBSTR〔S，i，k〕表示求S中从第i个字符开始的连续k个字符组成的子串的操作，那么对于S=“Beijing＆Nanjing”，SUBSTR〔S，4，5〕=〔〕。A.“ijing” B.“jing＆”C.“ingNa” D.“ing＆N”6.假设INDEX〔S，T〕表示求T在S中的位置的操作，那么对于S=“Beijing＆Nanjing”，T=“jing”，INDEX〔S，T〕=〔〕。A.2B.3C7.假设REPLACE〔S，S1，S2〕表示用字符串S2替换字符串S中的子串S1的操作，那么对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE〔S，S1，S2〕=〔〕。A.“Nanjing＆Shanghai” B.“Nanjing＆Nanjing”C.“ShanghaiNanjing” D.“Shanghai＆Nanjing”8.在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是〔〕。A.i＞0B.i≤n≤i≤≤i≤n+19.字符串采用结点大小为1的链表作为其存储结构，是指〔〕。 二、填空题1.计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。2.两个字符串相等的充要条件是_____________________和___________________。3.设字符串S1=“ABCDEF”，S2=“PQRS”，那么运算S=CONCAT〔SUB〔S1，2，LEN〔S2〕〕，SUB〔S1，LEN〔S2〕，2〕〕后的串值为___________________。4.串是指___________________。5.空串是指___________________，空格串是指___________________。三、算法设计题1.设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中〔每个单元存放一个字符〕。现要求从此串的第m个字符以后删除长度为t的子串，m<s，t<(s-m)，并将删除后的结果复制在该数组的第s单元以后的单元中，试设计此删除算法。2.设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符〔假定每个结点只存放1个字符〕的算法。习题3参考答案一、单项选择题1．B 2．D 3．C 4．D 5．B 6．C 7．D 8．C 9．D二、填空题1.固定长度，设置长度指针2.两个串的长度相等，对应位置的字符相等3.“BCDEDE”4.含n个字符的有限序列〔n≥0〕5.不含任何字符的串，仅含空格字符的字符串三、算法设计题1．算法描述为：intdelete(r,s,t,m)//从串的第m个字符以后删除长度为t的子串charr[];ints,t,m;{inti,j;for(i=1;i<=m;i++)r[s+i]=r[i];for(j=m+t-i;j<=s;j++)r[s-t+j]=r[j];return(1);}//delete2．算法思想为：〔1〕链表s中取出一个字符；将该字符与单链表t中的字符依次比拟；〔2〕当t中有与从s中取出的这个字符相等的字符，那么从t中取下一个字符重复以上比拟；〔3〕当t中没有与从s中取出的这个字符相等的字符，那么算法结束。设单链表类型为LinkList；注意，此时类型LinkList中的data成分为字符类型。LinkStringfind(s,t)LinkString*s,*t;{LinkString*ps,*pt;ps=s;while(ps!=NULL){pt=t;while((pt!=NULL)&&(ps->data!=pt->data))pt=pt->next;if(pt==NULL)ps=NULL;else{ps=ps->next;s=ps;}}returns;}//find

第4章数组和广义表讲课提要【主要内容】1．多维数组的顺序存储结构2．特殊矩阵的压缩存储3．广义表的定义及其与线性表的关系4．广义表的存储结构5．广义表运算实现中递归的应用【教学目标】1．掌握多维数组的顺序存储结构2．掌握特殊矩阵的压缩存储方法3．掌握广义表的定义及其与线性表的关系4．掌握广义表的存储结构5．了解广义表运算实现中递归的应用【所需课时】二次课。[第一次课]1．多维数组的顺序存储结构2．特殊矩阵的压缩存储方法3．广义表的定义及其与线性表的关系[第二次课]4．广义表的存储结构5．广义表运算实现中递归的应用学习指导1．多维数组的顺序存储结构对于多维数组，有两种存储方式：一是以行为主序〔或先行后列〕的顺序存放，如BASIC、PASCAL、C等程序设计语言中用的是以行为主的顺序分配，即一行分配完了接着分配下一行。另一种是以列为主序〔先列后行〕的顺序存放，如FORTRAN语言中，用的是以列为主序的分配顺序，即一列一列地分配。以行为主序的分配规律是：最右边的下标先变化，即最右下标从小到大，循环一遍后，右边第二个下标再变，…，从右向左，最后是左下标。以列为主序分配的规律是：最左边的下标先变化，即最左下标从小到大，循环一遍后，左边第二个下标再变，…，从左向右，最后是右下标。不管按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有m×n二维数组Amn，以“以行为主序”的分配为例，按照元素的下标确定其地址的计算方法如下。设数组的基址为LOC(a11)，每个数组元素占据L个地址单元，计算aij的物理地址的函数为：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*L同理，对于三维数组Amnp，即m×n×p数组，对于数组元素aijk其物理地址为：LOC(aijk)=LOC(a111)+((i-1)*n*p+(j-1)*p+k-1))*L注意：在C语言中，数组中每一维的下界定义为0，那么：LOC(aij)=LOC(a00)+(i*n+j)*L【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。假设A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素〔〕的物理地址相同。设每个字符占一个字节。A．A[8][5]B．A[3][10]C．A[5][8]D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。按行存储时，A[8][5]是第85个元素存储的元素。而按列存储时，第85个存储的元素是A[3][10]。即正确答案为B。2．特殊矩阵压缩存储的意义在很多科学计算与工程应用中，经常要使用矩阵的概念。矩阵具有与数组相似的性质，如元素数目固定、元素按下标关系有序地排列，所以在编程时可以利用二维数组来存储矩阵，也可以利用程序设计语言中的各种矩阵运算。在某些情况下，特别是在数值分析中，经常会出现一些阶数很高的矩阵，其中含有许多值相同的元素或零元素，如三角矩阵、对称矩阵、稀疏矩阵等，从节约存储空间的角度考虑，此时假设用二维数组存储会造成空间的极大浪费。为了节省存储空间，可以对这类矩阵进行压缩存储。即为对多个相同值的元素只分配一个存储空间，而对零元素可以不分配空间。3．对称矩阵压缩存储的方法对称矩阵的特点是：在一个n阶方阵中，有aij=aji，其中1≤i,j≤n。对称矩阵关于主对角线对称，因此只需存储上三角或下三角局部即可。对于对称矩阵中的任意元素aij，假设令I=max(i,j)，J=min(i,j)，那么将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。给出对称矩阵A中任意元素aij，依据它的下标i和j就可由上述对应关系式确定其在数组M中的位置K，因此aij的地址可由下式计算。Loc(aij)=Loc(M[K])=Loc(M[0])+K*L=Loc(M[0])+[I*(I+1)/2+J]*L其中：L为每个数据元素所占的存储单元长度。I=max(i,j)。J=min(i,j)。K=I*(I+1)/2+J。【例4-2】假设对n阶对称矩阵A以行序为主序方式将其下三角形的元素〔包括主对角线上所有元素〕依次存放于一维数组B[n〔n+1〕/2]中，那么在B中确定的位置k的关系为〔〕。A．B．C．D．解：如果a按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+〔i-1〕=i〔i-1〕/2。同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：。因此答案为A。4．三角矩阵压缩存储的方法形如图的矩阵称为三角矩阵，其中c为某个常数。其中下面图(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。图4-1三角矩阵图4-1三角矩阵3cc62c481c746082957(a)下三角矩阵3 4810c2946cc157ccc08cccc7(b)上三角矩阵三角矩阵中的重复元素c可以共享一个存储空间，其余的元素有n(n+1)/2个，因此可压缩存储到向量sa[0..n(n+1)/2]中，c存放在向量的最后一个分量中，排列时以行序为主。a和sa[k]的对应关系是：k=i*(k=i*(i-1)/2+j-1当i≥jn*(n+1)/2-1当i<jk=(i-1)*(2n-i+2)/2+j-ik=(i-1)*(2n-i+2)/2+j-i当i≤jn*(n+1)/2当i>j【例4-3】n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素〔包括主对角线上元素〕依次存放于一维数组B中。请写出从第一列开始以列序为主序分配方式时在B中确定元素a的存放位置的公式。解：如果a按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+…+[n-(j-2)]=(j-1)*n-而它又是所在列的第i行，因此在它前的元素个数还得加上i。因此它在一维数组B中的存储顺序为：(j-1)*n-+i5．稀疏矩阵及其压缩存储的特点设m*n矩阵中有t个非零元素且t<<m*n，这样的矩阵称为稀疏矩阵。稀疏矩阵的压缩存储采取如下方法：将非零元素所在的行、列以及它的值构成一个三元组〔i,j,v〕，然后再按某种规律存储这些三元组，这种方法可以节约存储空间。6．稀疏矩阵压缩存储的顺序存储方式以顺序方式组织存储时常用的方法是三元组顺序表，方法是：将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，采用顺序存储方法存储该表。7．稀疏矩阵压缩存储的链式存储方式稀疏矩阵压缩存储的链式存储方式，即十字链表。当矩阵中非零元素的个数和位置在使用中经常发生变化时，不宜采用顺序存储结构，可采用十字链表进行存储。其结点结构如下图。rowcolvdownright图4-2十字链表的结点结构图4-2十字链表的结点结构8．广义表〔列表〕的定义、术语及它与线性表的关系广义表〔GeneralizedLists〕是n〔n≥0〕个数据元素a1,a2,…ai,…,an的有序序列，一般记作：Ls＝〔a1,a2,…ai,…,an〕。其中：Ls是广义表的名称，n是它的长度，每个ai〔1≤i≤n〕是Ls的成员，它可以是单个元素，也可以是一个广义表，分别称为广义表Ls的单元素和子表。当广义表Ls非空时，称第一个元素a1为Ls的表头〔head〕，称其余元素组成的表〔a2，…，ai，…，an〕为Ls的表尾〔tail〕。表的深度：表中元素的最深嵌套层数。广义表与线性表的关系：当广义表Ls中的元素全部是原子时，广义表即为线性表。因此，可认为线性表是广义表的特例，广义表是线性表的推广。9．广义表的三个重要性质〔1〕广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。〔2〕广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。〔3〕广义表可以为其他表所共享。例如，表A、表B、表C是表D的共享子表。在D中可以不必列出子表的值，而用子表的名称来引用。10．广义表的存储结构按结点形式的不同，广义表的链式存储结构可分为两种不同的存储方式。一种称为头尾表示法，另一种称为孩子兄弟表示法。11．广义表的根本运算广义表有两个重要的根本操作，即取头操作〔Head〕和取尾操作〔Tail〕。此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。【例4-4】广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是〔〕。A．head(tail(tail(L)))B．tail(head(head(tail(L))))C．head(tail(tail(head(L))))D．head(tail(tail(tail(L))))解：选项A的结果是字符串“u”；选项B的结果是空表，无字符；选项C的结果是字符“z”；选项D的结果是字符“t”。从所有选项的结果可以看出，ASCII码最大的是字符“z”。因此正确答案是C。习题4一、单项选择题1.