算法与数据结构习题答案

第一章数据结构基础1.1简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。●数据：指能够被计算机识别、存储和加工处理的信息载体。

●数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

●逻辑结构：指数据元素之间的逻辑关系。

●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.

●线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢?即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题。在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。1.3常用的存储表示方法有哪几种?答：常用的存储表示方法有四种:

●顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

●链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。

●索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（DenseIndex）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

●散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。1.4设三个函数f,g,h分别为f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn请判断下列关系是否成立：(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)分析：数学符号"O"的严格的数学定义：

若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C·f（n）。

通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。

即：O(f(n))=n3

O(g(n))=n3

O(h(n))=n1.5

所以答案为：

答：●（1）成立。●（2）成立。●（3）成立。●（4）不成立。1.5设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?分析：要使前者快于后者，即前者的时间消耗低于后者，即：100n2<2n求解上式，可得

答：n=151.6设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。

(1)i=1;k=0;

while(i<n)

{k=k+10*i;i++;

}

分析：

i=1;//1

k=0;//1

while(i<n)//n

{k=k+10*i;//n-1

i++;//n-1

}

由以上列出的各语句的频度，可得该程序段的时间消耗：

T(n)=1+1+n+(n-1)+(n-1)=3n

可表示为T(n)=O(n)

(2)i=0;k=0;

do{

k=k+10*i;i++;

}

while(i<n);

分析：

i=0;//1

k=0;//1

do{//n

k=k+10*i;//n

i++;//n

}

while(i<n);//n

由以上列出的各语句的频度，可得该程序段的时间消耗：

T(n)=1+1+n+n+n+n=4n+2

可表示为T(n)=O(n)

(3)i=1;j=0;

while(i+j<=n)

{

if(i>j)j++;

elsei++;

}

分析：通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为：

T(n)=O(n)

(4)x=n;//n>1

while(x>=(y+1)*(y+1))

y++;

分析：由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。

由(y+1)*(y+1)<n得：y<n^0.5-1

所以，该程序段的执行时间为：

向下取整(n^0.5-1)

(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

elsex++;

分析：

x=91;//1

y=100;//1

while(y>0)//1101

if(x>100)//1100

{x=x-10;//100

y--;//100

}

else

x++;//1000

以上程序段右侧列出了执行次数。该程序段的执行时间为：T(n)=O(1)1.7算法的时间复杂度仅与问题的规模相关吗?答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。1.8按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn,n0.5,n!，2n，lgn,nlgn,n(3/2)答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。

先将题中的函数分成如下几类：常数阶：2100对数阶：lgnK次方阶：n0.5、n(3/2)

指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn

注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。

根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)n<2100<lgn<n0.5<n(3/2)<nlgn<(3/2)n<2n<n!<nn1.9有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?函数大"O"表示优劣

(1)T1(n)=5n2-3n+60lgn5n2+O(n)较差

(2)T2(n)=3n2+1000n+3lgn3n2+O(n)其次

(3)T3(n)=8n2+3lgn8n2+O(lgn)最差

(4)T4(n)=1.5n2+6000nlgn1.5n2+O(nlgn)最优第二章线性表2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。

链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。

头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜?

答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：

1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。2.4为什么在单循环链表中设置尾指针比设置头指针更好?

答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?

答：下面分别讨论三种链表的情况。

1.单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。

2.双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。

3.单循环链表。根据已知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。2.6下述算法的功能是什么?

LinkListDemo(LinkListL){//L是无头结点单链表

ListNode*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;

}

returnL;

}//Demo

答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。2.7设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList和DeleteList.解：算法如下:#defineListSize100//假定表空间大小为100

typedefintDataType;//假定DataType的类型为int型

typedefstruct{

DataTypedata[ListSize];//向量data用于存放表结点

intlength;//当前的表长度

}Seqlist;

//以上为定义表结构

voidInsertList(Seqlist*L,Datatypex,inti)

{//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length

intj;

if(i<0||i>L->length)

Error("positionerror");//非法位置，退出，该函数定义见教材P7.

if(L->length>=ListSize)

Error(“overflow");

for(j=L->length-1;j>=i;j--)

L->data[j+1]=L->data[j];

L->data[i]=x;

L->length++;

}

voidDeleteList(Seqlist*L,inti)

{//从L所指的顺序表中删除第i个结点ai,合法的删除位置为0<=i<=L->length-1

intj;

if(i<0||i>=L->length)

Error("positionerror");

for(j=i;j<L->length;j++)

L->data[j]=L->data[j+1];//结点前移

L->length--;//表长减小

}2.8试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。

答：1.顺序表：

要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：

//顺序表结构定义同上题

voidReverseList(Seqlist*L)

{

DataTypetemp;//设置临时空间用于存放data

inti;

for(i=0;i<=L->length/2;i++)//L->length/2为整除运算

{temp=L->data[i];//交换数据

L->data[i]=L->data[L->length-1-i];

L->data[L->length-1-i]=temp;

}

}

2.链表：

分析：可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：

(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。

(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：

结点结构定义如下：

typedefcharDataType;//假设结点的数据域类型的字符

typedefstructnode{//结点类型定义

DataTypedata;//结点的数据域

structnode*next;//结点的指针域

}ListNode;

typedefListNode*LinkList;

ListNode*p;

LinkListhead;

LinkListReverseList(LinkListhead)

{//将head所指的单链表(带头结点)逆置

ListNode*p,*q;//设置两个临时指针变量

if(head->next&&head->next->next)

{//当链表不是空表或单结点时

p=head->next;

q=p->next;

p->next=NULL;//将开始结点变成终端结点

while(q)

{//每次循环将后一个结点变成开始结点

p=q;

q=q->next;

p->next=head->next;

head->next=p;

}

returnhead;

}

returnhead;//如是空表或单结点表，直接返回head

2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。

在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。

算法如下：

//顺序表存储结构如题2.7

voidInsertIncreaseList(Seqlist*L,Datatypex)

{

inti;

if(L->length>=ListSize)

Error(“overflow");

for(i=L->length;i>0&&L->data[i-1]>x;i--)

L->data[i]=L->data[i];//比较并移动元素

L->data[i]=x;

L->length++;

}2.10设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。答：与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下：

voidInsertDecreaseList(Seqlist*L,Datatypex)

{

inti;

if(L->length>=ListSize)

Error(“overflow");

for(i=L->length;i>0&&L->data[i-1]<x;i--)

L->data[i]=L->data[i];//比较并移动元素

L->data[i]=x;

L->length++;

}2.11写一算法在单链表上实现线性表的ListLength(L)运算。

解：由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：

intListLength(LinkListL)

{

intlen=0;

ListNode*p;

p=L;//设该表有头结点

while(p->next)

{

p=p->next;

len++;

}

returnlen;

}2.12已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

解：分析：由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。具体算法如下：

LinkListLink(LinkListL1,LinkListL2，intm,intn)

{//将两个单链表连接在一起

ListNode*p,*q,*s;

//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间

if(m<=n)

{s=L1;q=L2->next;free(L2);}

else{s=L2;q=L1->next;free(L1);}

p=s;

while(p->next)p=p->next;//查找短表终端结点

p->next=q;//将长表的开始结点链接在短表终端结点后

returns;

}

本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：O(min(m,n))2.13设A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。

解：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。

算法如下：

LinkListMergeSort(LinkListA,LinkListB)

{//归并两个带头结点的递增有序表为一个带头结点递减有序表

ListNode*pa,*pb,*q,*C;

pa=A->next;//pa指向A表开始结点

C=A;C->next=NULL;//取A表的表头建立空的C表

pb=B->next;//pb指向B表开始结点

free(B);//回收B表的头结点空间

while(pa&&pb)

{

if(pb->data<=pa->data)

{//当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下

q=pa;pa=pa->next;

}

else

{//当B中的元素大于A中当前元素时，将pb表的开始结点摘下

q=pb;pb=pb->next;}

q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表

}

//若pa表非空，则处理pa表

while(pa){

q=pa;pa=pa->next;

q->next=C->next;C->next=q;}

//若pb表非空，则处理pb表

while(pb){

q=pb;pa=pb->next;

q->next=C->next;C->next=q;}

return(C);

}

该算法的时间复杂度分析如下：

算法中有三个while循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)2.14已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。请分析你的算法的时间复杂度。

解：要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。

算法如下：

voidDeleteList(LinkListL,DataTypemin,DataTypemax)

{

ListNode*p,*q,*s;

p=L;

while(p->next&&p->next->data<=min)

//找比min大的前一个元素位置

p=p->next;

q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点

while(q&&q->data<max)

{s=q;q=q->next;

free(s);//删除结点，释放空间

}

p->next=q;//将*p结点的直接后继指针指向*q结点

}2.15写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。

具体算法：

voidDeleteList(LinkListL)

{

ListNode*p,*q,*s;

p=L-next;

while(p->next&&p->next->next)

{

q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋

while(q->next)

if(p->data==q->next->data)

{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点

}

elseq=q->next;

p=p->next;

}

}2.16假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。

解：已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。

算法如下：

voidDeleteNode(ListNode*s)

{//删除单循环链表中指定结点的直接前趋结点

ListNode*p,*q;

p=s;

while(p->next->next!=s)

p=p->next;

//删除结点

q=p->next;

p->next=q->next;

free(p);//释放空间

}

注意：若单循环链表的长度等于1，则只要把表删空即可。2.17已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。

算法如下：

//设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针.

voidDivideList(LinkListL,LinkListA,LinkListB,LinkListC)

{

ListNode*p=L->next,*q;

while(p)

{

if(p->data>='a'&&p->data<='z'||p->data>='A'&&p->data<='Z')

{

q=p->next;

p=p->next;//指向下一结点

q->next=A->next;//将字母结点链到A表中

A->next=q;A=q;

}

elseif(p->data>='0'&&p->data<='9')

{//分出数字结点

q=p->next;

p=p->next;//指向下一结点

q->next=B->next;//将数字结点链到B表中

B->next=q;B=q;

}

else{//分出其他字符结点

q=p->next;

p=p->next;//指向下一结点

q->next=C->next;//将其他结点链到C表中

C->next=q;C=q;

}

}

}//结束

2.18设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。

解：LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。

算法如下：

//双向链表的存储结构

typedefstructdlistnode{

DataTypedata;

structdlistnode*prior,*next;

intfreq;

}DListNode;

typedefDListNode*DLinkList;

voidLocateNode(LinkListL,DataTypex)

{

ListNode*p,*q;

p=L->next;//带有头结点

while(p&&p->data!=x)

p=p->next;

if(!p)ERROR("xisnotinL");//双链表中无值为x的结点

else{p->freq++;//freq加1

q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点

while(q!=L&&q->freq<p->freq)

q=q->prior;

if(q->next!=p)//若*q结点和*p结点不为直接前趋直接后继关系，

//则将*p结点链到*q结点后

{p->prior->next=p->next;//将*p从原来位置摘下

p->next->prior=p->prior;

q->next->prior=p;//将*p插入*q之后。

p->next=q->next;

q->next=p;

p->prior=q;

}

}

}第三章3.1设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：

(1)若入、出栈次序为Push(1),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop(),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop()表示出栈)?

(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析1，2，3，4的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

答：(1)出栈序列为：1324

(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2，3，4的24种排列中，可通过相应入出栈操作得到的序列是：

1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321

不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43123.2链栈中为何不设置头结点?

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。3.3循环队列的优点是什么?如何判别它的空和满?

答：循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。3.4设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何?若只设尾指针呢?

答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.5指出下述程序段的功能是什么?

(1)voidDemo1(SeqStack*S){

inti;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0,i<n;i++)Push(S,arr[i]);

}//Demo1

(2)SeqStackS1,S2,tmp;

DataTypex;

...//假设栈tmp和S2已做过初始化

while(!StackEmpty(&S1))

{

x=Pop(&S1);

Push(&tmp,x);

}

while(!StackEmpty(&tmp))

{

x=Pop(&tmp);

Push(&S1,x);

Push(&S2,x);

}

(3)voidDemo2(SeqStack*S,intm)

{//设DataType为int型

SeqStackT;inti;

InitStack(&T);

while(!StackEmpty(S))

if((i=Pop(S))!=m)Push(&T,i);

while(!StackEmpty(&T))

{

i=Pop(&T);Push(S,i);

}

}

(4)voidDemo3(CirQueue*Q)

{//设DataType为int型

intx;SeqStackS;

InitStack(&S);

while(!QueueEmpty(Q))

{x=DeQueue(Q);Push(&S,x);}

while(!StackEmpty(&s))

{x=Pop(&S);EnQueue(Q,x);}

}//Demo3

(5)CirQueueQ1,Q2;//设DataType为int型

intx,i,n=0;

...//设Q1已有内容，Q2已初始化过

while(!QueueEmpty(&Q1))

{x=DeQueue(&Q1);EnQueue(&Q2,x);n++;}

for(i=0;i<n;i++)

{x=DeQueue(&Q2);

EnQueue(&Q1,x);EnQueue(&Q2,x);}

答：(1)程序段的功能是将一栈中的元素按反序重新排列，也就是原来在栈顶的元素放到栈底，栈底的元素放到栈顶。此栈中元素个数限制在64个以内。

(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。

(3)程序段的功能是利用栈T，将一个非空栈S中值等于m的元素全部删去。

(4)程序段的功能是将一个循环队列Q经过S栈的处理，反向排列，原来的队头变成队尾，原来的队尾变成队头。

(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。3.6回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

解：根据提示，算法可设计为：

//以下为顺序栈的存储结构定义

#defineStackSize100//假定预分配的栈空间最多为100个元素

typedefcharDataType;//假定栈元素的数据类型为字符

typedefstruct{

DataTypedata[StackSize];

inttop;

}SeqStack;intIsHuiwen(char*t)

{//判断t字符向量是否为回文，若是，返回1，否则返回0

SeqStacks;

inti,len;

chartemp;

InitStack(&s);

len=strlen(t);//求向量长度

for(i=0;i<len/2;i++)//将一半字符入栈

Push(&s,t[i]);

while(!EmptyStack(&s))

{//每弹出一个字符与相应字符比较

temp=Pop(&s);

if(temp!=S[i])return0;//不等则返回0

elsei++;

}

return1;//比较完毕均相等则返回1

}3.7利用栈的基本操作，写一个将栈S中所有结点均删去的算法voidClearStack(SeqStack*S)，并说明S为何要作为指针参数?

解：算法如下

voidClearStack(SeqStack*S)

{//删除栈中所有结点

S->Top=-1;//其实只是将栈置空

}

因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。3.8利用栈的基本操作，写一个返回S中结点个数的算法intStackSize(SeqStackS),并说明S为何不作为指针参数?

解：算法如下：

intStackSize(SeqStackS)

{//计算栈中结点个数

intn=0;

if(!EmptyStack(&S))

{

Pop(&S);

n++;

}

returnn;

}

上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。3.9设计算法判断一个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

解：根据提示，可以设计算法如下：

intPairBracket(char*SR)

{//检查表达式ST中括号是否配对

inti;

SeqStackS;//定义一个栈

InitStack(&s);

for(i=0;i<strlen(SR);i++)

{

if(S[i]=='(')Push(&S,SR[i]);//遇'('时进栈

if(S[i]==')')//遇')'

if(!StackEmpty(S))//栈不为空时，将栈顶元素出栈

Pop(&s);

elsereturn0;//不匹配，返回0

}

ifEmptyStack(&s)return1;//匹配，返回1

elsereturn0;//不匹配，返回0

}3.10一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S)、入栈Push(S,i,x)和出栈Pop(S,i)等算法，其中i为0或1，用以表示栈号。

解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：

//双向栈的栈结构类型与以前定义略有不同

#defineStackSize100//假定分配了100个元素的向量空间

#definecharDataType

typedefstruct{

DataTypeData[StackSize]

inttop0;//需设两个指针

inttop1;

}DblStack

voidInitStack(DblStack*S)

{//初始化双向栈

S->top0=-1;

S->top1=StackSize;//这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错

}

intEmptyStack(DblStack*S,inti)

{//判栈空(栈号i)

return(i==0&&S->top0==-1||i==1&&S->top1==StackSize);

}

intFullStack(DblStack*S)

{//判栈满,满时肯定两头相遇

return(S->top0==S-top1-1);

}voidPush(DblStack*S,inti,DataTypex)

{//进栈(栈号i)

if(FullStack(S))

Error("Stackoverflow");//上溢、退出运行

if(i==0)S->Data[++S->top0]=x;//栈0入栈

if(i==1)S->Data[--S->top1]=x;//栈1入栈

}

DataTypePop(DblStack*S,inti)

{//出栈(栈号i)

if(EmptyStack(S,i))

Error("Stackunderflow");//下溢退出

if(i==0)

return(S->Data[S->top0--]);//返回栈顶元素，指针值减1

if(i==1)

return(S->Data[S->top1++]);//因为这个栈是以另一端为底的，所以指针值加1。

}3.11Ackerman函数定义如下：请写出递归算法。┌n+1当m=0时AKM(m,n)=│AKM(m-1,1)当m≠0，n=0时

└AKM(m-1,AKM(m,n-1))当m≠0,n≠0时

解：算法如下

intAKM(intm,intn)

{if(m==0)returnn+1;

if(m<>0&&n==0)returnAKM(m-1,1);

if(m<>0&&n<>0)returnAKM(m-1,AKM(m,n-1));

}3.12用第二种方法，即少用一个元素空间的方法来区别循环队列的队空和队满，试为其设计置空队，判队空，判队满、出队、入队及取队头元素等六个基本操作的算法。

解：算法设计如下:

//循环队列的定义

#defineQueueSize100

typedefcharDatatype;//设元素的类型为char型

typedefstruct{

intfront;

intrear;

DataTypeData[QueueSize];

}CirQueue;

(1)置空队

voidInitQueue(CirQueue*Q)

{//置空队

Q->front=Q->rear=0;

}

(2)判队空

intEmptyQueue(CirQueue*Q)

{//判队空

returnQ->front==Q->rear;

}

(3)判队满

intFullQueue(CirQueue*Q)

{//判队满//如果尾指针加1后等于头指针，则认为满

return(Q->rear+1)%QueueSize==Q->front;

}

4)出队

DataTypeDeQueue(CirQueue*Q)

{//出队

DataTypetemp;

if(EmptyQueue(Q))

Error("队已空，无元素可以出队");

temp=Q->Data[Q->front];//保存元素值

Q->front=(Q->front+1)%QueueSize;//循环意义上的加1

returntemp;//返回元素值

}

(5)入队

voidEnQueue(CirQueue*Q,DataTypex)

{//入队

if(FullQueue(Q))

Error("队已满，不可以入队");

Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//rear指向下一个空元素位置

}

(6)取队头元素

DataTypeFrontQueue(CirQueue*Q)

{//取队头元素

if(EmptyQueue(Q))

Error("队空，无元素可取");

returnQ->Data[Q->front];

}3.13假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写相应的置空队、判队空、入队和出队等算法。

解：算法如下：

//先定义链队结构:

typedefstructqueuenode{

Datatypedata;

structqueuenode*next;

}QueueNode;//以上是结点类型的定义

typedefstruct{

queuenode*rear;

}LinkQueue;//只设一个指向队尾元素的指针

(1)置空队

voidInitQueue(LinkQueue*Q)

{//置空队：就是使头结点成为队尾元素

QueueNode*s;

Q->rear=Q->rear->next;//将队尾指针指向头结点

while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队

{s=Q->rear->next;

Q->rear->next=s->next;

free(s);

}//回收结点空间

}

(2)判队空

intEmptyQueue(LinkQueue*Q)

{//判队空

//当头结点的next指针指向自己时为空队

returnQ->rear->next->next==Q->rear->next;

}

(3)入队

voidEnQueue(LinkQueue*Q,Datatypex)

{//入队

//也就是在尾结点处插入元素

QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点

p->data=x;p->next=Q->rear->next;//初始化新结点并链入

Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点

}

(4)出队

DatatypeDeQueue(LinkQueue*Q)

{//出队,把头结点之后的元素摘下

Datatypet;

QueueNode*p;

if(EmptyQueue(Q))

Error("Queueunderflow");

p=Q->rear->next->next;//p指向将要摘下的结点

x=p->data;//保存结点中数据

if(p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点

Q->rear=Q->rear->next;Q->rear->next=p->next;}

else

Q->rear->next->next=p->next;//摘下结点p

free(p);//释放被删结点

returnx;

}3.14对于循环向量中的循环队列，写出求队列长度的公式。

解：公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSizeQueuelen=(QueueSize+rear-front)%QueueSize3.15假设循环队列中只设rear和quelen来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

解：根据题意，可定义该循环队列的存储结构：

#defineQueueSize100

typedefcharDatatype;//设元素的类型为char型

typedefstruct{

intquelen;

intrear;

DatatypeData[QueueSize];

}CirQueue;

CirQueue*Q;

循环队列的队满条件是：Q->quelen==QueueSize

知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：

(1)判断队满

intFullQueue(CirQueue*Q)

{//判队满,队中元素个数等于空间大小

returnQ->quelen==QueueSize;

}

(2)入队

voidEnQueue(CirQueue*Q,Datatypex)

{//入队

if(FullQueue(Q))

Error("队已满，无法入队");

Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1

Q->quelen++;

}

(3)出队

DatatypeDeQueue(CirQueue*Q)

{//出队

if(Q->quelen==0)

Error("队已空，无元素可出队");

inttmpfront;//设一个临时队头指针

tmpfront=(QueueSize+Q->rear-Q->quelen+1)%QueueSize;//计算头指针位置

Q->quelen--;

returnQ->Data[tmpfront];

}第四章数组和广义表5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000。

解：按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置)

a0000a0001a0002

a0010a0011a0012

a0100a0101a0102

a0110a0111a0112

a0200a0201a0202

a0210a0211a0212

a1000a1001a1002

a1010a1011a1012

a1100a1101a1102

a1110a1111a1112

a1200a1201a1202

a1210a1211a1212

按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)：

a0000a1000

a0100a1100

a0200a1200

a0010a1010

a0110a1110

a0210a1210

a00015.2给出C语言的三维数组地址计算公式。

解：因为C语言的数组下标下界是0，所以Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d其中Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。5.3设有三对角矩阵An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求：

(1)用i,j表示k的下标变换公式。

(2)用k表示i,j的下标变换公式。

(1)解：要求i,j到k的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为：(i*3-1)+j-(i+1)其中(i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数

化简可得：k=2i+j;//c下标是从0开始的。(2)解：因为K和i,j是一一对应的关系，因此这也不难算出：

i=(k+1)/3//k+1表示当前元素前有几个非零元素,被3整除就得到行号

j=(k+1)%3+(k+1)/3-1//k+1除以3的余数就是表示当前行中第几个非零元素，

//加上前面的0元素所点列数就是当前列号5.4设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?

解：(1)因含5*6=30个元素，因此A共占30*4=120个字节。(2)a45的起始地址为：Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116

(3)按行优先顺序排列时，a25=1000+(2*6+5)*4=1068

(4)按列优先顺序排列时：(二维数组可用行列下标互换来计算)a25=1000+(5*5+2)*4=11085.5特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?

答：后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。5.6简述广义表和线性表的区别与联系。

答:广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。5.7画出下列广义表的图形表示：A(a,B(b,d),C(e,B(b,d),L(f,g)))(2)A(a,B(b,A))

解:

(1)这是一个再入表。(2)则是一个递归表。5.8设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?

解：●head(L)=()●tail(L)=(())●L的长度为2●L的深度为25.9求下列广义表运算的结果：(1)head((p,h,w));(2)tail((b,k,p,h));(3)head(((a,b),(c,d)));

(4)tail(((a,b),(c,d)));(5)head(tail(((a,b),(c,d))));(6)tailhead)(((a,b),(c,d)))).

答：(1)head((p,h,w))=p;(2)tail((b,k,p,h))=(k,p,h);(3)head(((a,b),(c,d)))=(a,b);

(4)tail(((a,b),(c,d)))=((c,d))(5)head(tail(((a,b),(c,d))))=(c,d);(6)tail(head(((a,b),(c,d))))=(b).5.10当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。解：转置矩阵就是将矩阵元素的行号与列号互换，根据已知的三对角矩阵的特点，其转置矩阵对角线元素不变，非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系：k=2i+j。我们可以设计出这个矩阵的转置算法：#defineN10//矩阵行、列数

#defineLength(3*N-2)//压缩矩阵的长度

typedefstruct{

intdata[Length];

}DiaMatrix;

voidTransMatrix(DiaMatrix*C)

{//压缩三对角矩阵转置

inti,j;

intt;

for(i=0;i<N;i++)

for(j=i;j<N;j++)

if(i-j<=1&&i-j>=-1)

{//将对应于行列号的压缩矩阵内的元素互换

t=C->data[2*i+j];

C->data[2*i+j]=C->data[2*j+i];

C->data[2*j+i]=t;

}//endif

}//end5.11当稀疏矩阵A和B均以三元组表作为存储结构时试写出矩阵相加的算法其结果存放在三元组表C中。解：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。#defineMaxSize10//用户自定义

typedefintDataType;//用户自定义

typedefstruct

{//定义三元组

inti,j;

DataTypev;

}TriTupleNode;

typedefstruct

{//定义三元组表

TriTupleNodedata[MaxSize];

intm,n,t;//矩阵行，列及三元组表长度

}TriTupleTable;

//以下为矩阵加算法

voidAddTriTuple(TriTupleTable*A,TriTupleTable*B,TriTupleTable*C)

{//三元组表表示的稀疏矩阵A,B相加

intk,l;

DataTypetemp;

C->m=A->m;//矩阵行数

C->n=A->n;//矩阵列数

C->t=0;//三元组表长度

k=0;l=0;

while(k<A->t&&l<B->t)

{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j))

{temp=A->data[k].v+