数据结构书本习题答案

1.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请判断下

列关系是否成立：

(l)f(n)=O(g(n))

(2)g(n)=O(f(n))

(3)h(n)=O(nl.5)

(4)h(n)=O(nlgn)

分析：

数学符号”0“的严格的数学定义：

若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=0(f(n))表示存在正的常数C

和nO,使得当n》nO时都满足OWT(n)WC•f(n)。

通俗地说，就是当n-8时，f(n)的函数值增长速度与T(n)的增长速度同阶。一般，一个函数的

增长速度与该函数的最高次阶同阶。

即：

O(f(n))=n3

O(g(n))=n3

O(h(n))=nl.5

所以答案为：

答：•(1)成立。

•(2)成立。

•(3)成立。

•(4)不成立。

1.5设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多

大？

分析：要使前者快于后者，即前者的时间消耗低于后者，即：

100n2<2n

求解上式，可得

答：n=15

1.6设n为正整数，利用大记号，将下列程序段的执行时间表示为n的函数。

(l)i=l;k=0;

while(i<n)

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

)

分析：

i=l;//l

k=0;//l

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;//I

k=0;//l

do{//n

k=k+10*i;//n

i++;〃n

while(i<n);//n

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

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

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

⑶i=l;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>l

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

y++;

分析：

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

n的值时退出循环。

由(y+l)*(y+l)<n得：y<nA0.5-l

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

向下取整(M0.5-1)

(5)x=91;y=100;

while(y>0)

if(x>100)

{x=x-10;y-;)

elsex++;

分析:

x=91;//l

y=100;//l

while(y>0)//1101

if(x>100)//1100

{x=x-10;//100

y—;//100

)

else

x++;//1000

以上程序段右侧列出了执行次数。该程序段的执行时间为：

T(n)=O(l)

1.7算法的时间复杂度仅与问题的规模相关吗？

答：算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情

况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下

的时间复杂度为准的。

1.8按增长率由小至大的顺序排列下列各函数：

2100,(3/2)n>(2/3)n,nn,n0.5,n!,2n,Ign,nlgn,n(3/2)

答：常见的时间复杂度按数量级递增排列，依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对

数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。

先将题中的函数分成如下几类：

常数阶：2100

对数阶：Ign

K次方阶：n0.5、n(3/2)

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

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

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

(2/3)n<2100<Ign<n0.5<n(3/2)<nlgn<(3/2)n<2n<n!<nn

1.9有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。

例如，^4T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.01gn+0(n),这两个式子表示，当n

足够大时Tl(n)优于T2(n),因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大

时，哪•个较优，哪…个较劣？

函数大"0"表示优劣

(1)T1(n)=5n2-3n+601gn5n2+O(n)较差

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

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

(4)T4(n)=1.5n2+6000nlgn1.5n2+O(nlgn)最优

2.1试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。

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

链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单

链表可以用头指针的名字来命名。

头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链

表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操

作一致(都是在某一结点之后)。

2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜？

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

有以下几方面的考虑：

L基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空

间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为

好。2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储

结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，

若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。

2.3在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素？

答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除•个结点需平均移动(n-l)/2

个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置ioi越接近n则所需移动的结点

数越少。

2.4为什么在单循环链表中设置尾指针比设置头指针更好？

答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点

都很方便，设一带头结点的单循环链表，其尾指针为rear,则开始结点和终端结点的位置分别是

rear->next->next和rear,查找时间都是0(1)。

若用头指针来表示该链表，则查找终端结点的时间为O(n)。

2.5在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p

从相应的链表中删去?若可以，其时间复杂度各为多少？

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

1.单链表。若指针p指向某结点时，能够根据该指针找到其直接后继，能够顺后继指针链找到*p

结点后的结点。但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去

该结点。

2.双链表。由于这样的链表提供双向指针，根据*p结点的前趋指针和后继指针可以查找到其直

接前趋和直接后继，从而可以删除该结点。其时间复杂度为0(1)。

3.单循环链表。根据L1知结点位置，可以直接得到其后相邻的结点位置(直接后继)，又因为是循

环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为

O(n)o

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个结点定义为(aO,al,…an-1)，重写顺序表上实现的插入和删除算法：InsertList和

DeleteList.

解:算法如下:

#defineListSize100//假定表空间大小为100

typedefiniDataType;〃假定DataType的类型为int型

typedefstruct(

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

intlength;//当前的表长度

}Seqlist;

〃以上为定义表结构

voidInsertList(Seqlist*L,Datatypex,inti)

(

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

intj;

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

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

if(L->length>=ListSize)

ErrorC4overilowu);

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

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

L->data[i]=x;

L->length+4-;

)

voidDeleteList(Seqlist*L,inti)

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

intj;

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

Error(upositionerror");

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

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

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

)

2.8试分别用顺序表和单链表作为存储结构，实现将线性表(aO,al,...an-l)就地逆置的操作，所谓"就地"

指辅助空间应为O(l)»

答：

1.顺序表：

要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如

此反复，就可将整个表逆置了。算法如下：

〃顺序表结构定义同上题

voidReverseList(Seqlist*L)

(

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

inti;

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

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

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

L->datafL->length-1-i]=temp;

}

}

2.链表：

分析：

可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算

法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：

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

(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的

包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点

依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法

是这样的：

结点结构定义如下：

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

typedefstructnode{〃结点类型定义

DataTypedata;〃结点的数据域

structnode*next;〃结点的指针域

JListNode;

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)

EITOF(aoverflow");

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已知LI和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两

个链表连接在一起，请分析你的算法的时间复杂度。

解：分析：

山于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结

点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单

链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连

接。

具体算法如下：

LinkListLink(LinkListLI,LinkListL2,intm,intn)

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

ListNode*p,*q,*s;

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

if(m<=n)

{s=Ll;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,并要求辅助空间为0(1),请分析算法的时间复杂度。

解：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时

扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到

A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得

到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(l)o

算法如下：

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,则该算法的时间复杂度0(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);〃删除结点，释放空间

I

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'llp->data>="A'&&p->data<=*Zr)

(

q=p->next;

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

q->next二Aonext;〃将字母结点链到A表中

A->next=q;A=q;

)

elseif(p->data>='Or&&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->nex仁C->next;〃将其他结点链到C表中

C->next=q;C=q;

}〃结束

2.18设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq,在链表

被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq

域的值加I,并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表

头。试写一符合上述要求的LocateNode运算的算法。

解：LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。

找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着

前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q

后就可以了。

算法如下：

〃双向链表的存储结构

typedefstructdlistnode{

DataTypedata;

structdlistnode*prior,*next;

intfreq;

JDListNode;

typedefDListNode*DLinkList;

voidLocateNode(LinkListL,DataTypex)

(

ListNode*p,*q;

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

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

p=p->next;

if(!p)ERRORC'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结点链到*4结点后

{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(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),Pop()，则出栈的数字序列为何

(这里Push⑴表示i进栈，Pop()表示出栈)？

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

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

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

(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(l),Pop(),Push(2),Push

(3),Push(4),Pop()。这样,3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。

具体操作为：Push(l),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,4312

3.2链栈中为何不设置头结点？

答：链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之

后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

3.3循环队列的优点是什么？如何判别它的空和满？

答：循环队列的优点是：它可以克服顺序队列的“假上溢"现象，能够使存储队列的向量空间得到充分的利

用。判别循环队列的"空"或"满"不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一

布尔变量来区别队列的空和满。二是少用•个元素的空间，每次入队前测试入队后头尾指针是否会重合，如

果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列

中元素的个数。

3.4设长度为n的链队用单循环链表表示，若设头指针，则入队HI队操作的时间为何？若只设尾指针呢？

答：

当只设头指针时，出队的时间为1,而入队的时间需要n,因为每次入队均需从头指针开始查找，找

到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为lo因为是循环链表，尾指针所

指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

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)SeqStackSI,S2,tmp;

DataTypex;

…〃假设栈tmp和S2已做过初始化

while(!StackEmpty(&S1))

(

x=Pop(&S1);

Push(&tmp,x);

)

while(!StackEmpty(&tmp))

(

x=Pop(&tmp);

Push(&Sl,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)CirQueueQI,Q2;//设DataType为int型

intx,i,n=0;

...//设QI已有内容，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栈将一个非空栈si的所有元素按原样复制到一个栈S2当中去。

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

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

尾变成队头。

(5)这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部

出队，进入队列2,然后再把队列2的元素复制到队列1中。

3.6回文是指正读反读均相同的字符序列，如"abba"和"abdba”均是回文，但"good”不是回文。试写一个算

法判定给定的字符向量是否为回文。(提示：将一半字符入栈)

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

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

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

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

typedefstruct{

DataTypedatafStackSize];

inttop;

}SeqStack;

intIsHuiwen(char*t)

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

SeqStacks;

inti,len;

chartemp;

InilStack(&s);

len=strlen⑴;〃求向量长度

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

Push(&s,t[il);

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设计算法判断•个算术表达式的圆括号是否正确配对。(提示：对表达式进行扫描，凡遇到'('就进栈,

遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。

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

iniPairBracket(char*SR)

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

inti;

SeqStackS;〃定义一个栈

InitStack(&s);

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

(

if(S[i]==，C)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为。或1,用以表

示栈号。

解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空

间可以充分利用。双向栈的算法设计如下：

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

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

#definecharDataType

typedefstruct{

DataTypeData[StackSize]

inttopO;〃需设两个指针

inttopi;

JDblStack

voidInitStack(DblStack*S)

{〃初始化双向栈

S->topO=-1;

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

)

intEmptyStack(DblStack*S,inti)

{〃判栈空(栈号i)

return(i==0&&S->topO==-111i==1&&S->top1==StackSize);

)

intFullStack(DblStack*S)

{〃判栈满，满时肯定两头相遇

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

)

voidPush(DblStack*S,inti,DataTypex)

{〃进栈(栈号i)

if(FullStack(S))

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

if(i==0)S->Data[++S->topOJ=x;〃栈0入栈

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

)

DataTypePop(DblStack*S,inti)

{〃出栈(栈号i)

if(EmptyStack(S,i))

Error(nStackunderflow");〃下溢退出

if(i==0)

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

if(i==l)

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

)

3.11Ackerman函数定义如下：请写出递归算法。

rn+1当m=0时

AKM(m,n)=|AKM(m-1,1)当mWO,n=0时

LAKM(m-l,AKM(m,n-l))当mWO,