数据结构课后答案高等教育出版社 唐策善版文档格式.docx
《数据结构课后答案高等教育出版社 唐策善版文档格式.docx》由会员分享，可在线阅读，更多相关《数据结构课后答案高等教育出版社 唐策善版文档格式.docx（96页珍藏版）》请在冰点文库上搜索。
2.1头指针：
指向链表的指针。
因为对链表的所有操均需从头指针开始，即头指针具有标识链表的作用，所以链表的名字往往用头指针来标识。
如：
链表的头指针是la，往往简称为“链表la”。
头结点：
为了链表操作统一，在链表第一元素结点（称为首元结点，或首结点）之前增加的一个结点，该结点称为头结点，其数据域不无实际意义（当然，也可以存储链表长度，这只是副产品），其指针域指向头结点。
这样在插入和删除中头结点不变。
开始结点：
即上面所讲第一个元素的结点。
2.2只设尾指针的单循环链表，从尾指针出发能访问链表上的任何结点。
2·
3
voidinsert（ElemTypeA[],intelenum,ElemTypex）
//向量A目前有elenum个元素，且递增有序，本算法将x插入到向量A中，并保持向量的递增有序。
{inti=0,j;
while（i<
elenum&
&
A[i]<
=x）i++;
//查找插入位置
for（j=elenum-1;
j>
=i;
j--）A[j+1]=A[j];
//向后移动元素
A[i]=x;
//插入元素
}//算法结束
4
voidrightrotate（ElemTypeA[],intn,k）
//以向量作存储结构，本算法将向量中的n个元素循环右移k位，且只用一个辅助空间。
{intnum=0;
//计数，最终应等于n
intstart=0;
//记录开始位置（下标）
while（num<
n）
{temp=A[start];
//暂存起点元素值，temp与向量中元素类型相同
empty=start;
//保存空位置下标
next=（start-K+n）%n;
//计算下一右移元素的下标
while（next!
=start）
{A[empty]=A[next];
//右移
num++;
//右移元素数加1
empty=next;
next=（next-K+n）%n;
//计算新右移元素的下标
}
A[empty]=temp;
//把一轮右移中最后一个元素放到合适位置
start++;
//起点增1，若num<
n则开始下一轮右移。
}//算法结束
算法二
算法思想：
先将左面n-k个元素逆置，接着将右面k个元素逆置，最后再将这n个元素逆置。
{ElemTypetemp;
for（i=0;
i<
（n-k）/2;
i++）//左面n-k个元素逆置
{temp=A[i];
A[i]=A[n-k-1-i];
A[n-k-1-i]=temp;
for（i=1;
=k;
i++）//右面k个元素逆置
{temp=A[n-k-i];
A[n-k-i]=A[n-i];
A[n-i]=temp;
for（i=0;
n/2;
i++）//全部n个元素逆置
A[i]=A[n-1-i];
A[n-1-i]=temp;
5
voidinsert（linklist*L,ElemTypex）
//带头结点的单链表L递增有序，本算法将x插入到链表中，并保持链表的递增有序。
{linklist*p=L->
next,*pre=L，*s;
//p为工作指针，指向当前元素，pre为前驱指针，指向当前元素的前驱
s=（linklist*）malloc（sizeof（linklist））;
//申请空间，不判断溢出
s->
data=x;
while（p&
p->
data<
=x）{pre=p;
p=p->
next;
}//查找插入位置
pre->
next=s;
s->
next=p;
6
voidinvert（linklist*L）
//本算法将带头结点的单链表L逆置。
//算法思想是先将头结点从表上摘下，然后从第一个元素结点开始，依次前插入以L为头结点的链表中。
next,*s;
//p为工作指针，指向当前元素，s为p的后继指针
L->
next=null;
//头结点摘下，指针域置空。
算法中头指针L始终不变
while（p）
{s=p->
//保留后继结点的指针
next=L->
//逆置
p=s;
//将p指向下个待逆置结点
}
7
（1）intlength1（linklist*L）
//本算法计算带头结点的单链表L的长度
inti=0;
//p为工作指针，指向当前元素，i表示链表的长度
{i++;
}
return（i）;
（2）intlength1（nodesa[MAXSIZE]）
//本算法计算静态链表s中元素的个数。
{intp=sa[0].next,i=0;
//p为工作指针，指向当前元素，i表示元素的个数，静态链指针等于-1时链表结束
while（p！
=-1）
p=sa[p].next;
8
voidunion_invert（linklist*A,*B,*C）
//A和B是两个带头结点的递增有序的单链表，本算法将两表合并成
//一个带头结点的递减有序单链表C，利用原表空间。
{linklist*pa=A->
next,*pb=B->
next,*C=A,*r;
//pa,pb为工作指针，分别指向A表和B表的当前元素，r为当前逆置
//元素的后继指针,使逆置元素的表避免断开。
//算法思想是边合并边逆置，使递增有序的单链表合并为递减有序的单链表。
C->
算法中头指针C始终不变
while（pa&
pb）//两表均不空时作
if（pa->
=pb->
data）//将A表中元素合并且逆置
{r=pa->
pa->
next=C->
next=pa;
pa=r;
//恢复待逆置结点的指针
else//将B表中元素合并且逆置
{r=pb->
pb->
next=pb;
pb=r;
//以下while（pa）和while（pb）语句，只执行一个
while（pa）//将A表中剩余元素逆置
while（pb）//将B表中剩余元素逆置
free（B）;
//释放B表头结点
9
voiddeleteprior（linklist*L）
//长度大于1的单循环链表，既无头结点，也无头指针，本算法删除*s的前驱结点
{linklist*p=s->
next,*pre=s;
//p为工作指针，指向当前元素，
//pre为前驱指针，指向当前元素*p的前驱
while（p->
next!
=s）{pre=p;
}//查找*s的前驱
free（p）;
//删除元素
10
voidone_to_three（linklist*A,*B,*C）
//A是带头结点的的单链表，其数据元素是字符字母、字符、数字字符、其他字符。
本算法//将A表分成
//三个带头结点的循环单链表A、B和C，分别含有字母、数字和其它符号的同一类字符，利用原表空间。
{linklist*p=A->
next,r;
//p为工作指针，指向A表的当前元素，r为当前元素的后继指针,使表避免断开。
//算法思想是取出当前元素，根据是字母、数字或其它符号，分别插入相应表中。
B=（linklist*）malloc（sizeof（linklist））;
B->
//准备循环链表的头结点
C=（linklist*）malloc（sizeof（linklist））;
C->
while（p）
{r=p->
//用以记住后继结点
if（p->
data>
=’a’&
p->
=’z’||p->
=’A’&
=’Z’）
{p->
next=A->
A->
}//将字母字符插入A表
elseif（p->
=’0’&
=’9’）
next=B->
}//将数字字符插入B表
else{p->
}//将其它符号插入C表
p=r;
//恢复后继结点的指针
}//while
11
voidlocate（dlinklist*L）
//L是带头结点的按访问频度递减的双向链表，本算法先查找数据x,
//查找成功时结点的访问频度域增1，最后将该结点按频度递减插入链表中适当位置。
next,*q;
//p为工作指针，指向L表的当前元素，q为p的前驱，用于查找插入位置。
data!
=x）p=p->
//查找值为x的结点。
if（!
p）return（“不存在值为x的结点”）;
else{p->
freq++;
//令元素值为x的结点的freq域加1。
next->
prir=p->
prior;
//将p结点从链表上摘下。
prior->
next=p->
q=p->
//以下查找p结点的插入位置
while（q!
=L&
q->
freq<
p-freq）q=q->
next=q->
prior=p;
//将p结点插入
prior=q;
next=p；
第三章栈和队列（参考答案）
//从数据结构角度看，栈和队列是操作受限的线性结构，其顺序存储结构
//和链式存储结构的定义与线性表相同，请参考教材，这里不再重复。
3.11234213432144321
124321433241
132423143421
13422341
14322431
设入栈序列元素数为n，则可能的出栈序列数为C2nn=（1/n+1）*（2n!
/（n!
）2）
3.2证明：
由j<
k和pj<
pk说明pj在pk之前出栈，即在k未进栈之前pj已出栈，之后k进栈，然后pk出栈；
k和pj>
pk说明pj在pk之后出栈，即pj被pk压在下面，后进先出。
由以上两条，不可能存在i<
j<
k使pj<
pk<
pi。
也就是说，若有1，2，3顺序入栈，不可能有3，1，2的出栈序列。
3.3voidsympthy（linklist*head,stack*s）
//判断长为n的字符串是否中心对称
{inti=1;
linklist*p=head->
while（i<
=n/2）//前一半字符进栈
{push（s,p->
data）;
if（n%2!
==0）p=p->
//奇数个结点时跳过中心结点
while（p&
data==pop（s））p=p->
if（p==null）printf（“链表中心对称”）；
elseprintf（“链表不是中心对称”）；
}//算法结束
3.4
intmatch（）
//从键盘读入算术表达式，本算法判断圆括号是否正确配对
（inits;
//初始化栈s
scanf（“%c”,&
ch）;
while（ch!
=’#’）//’#’是表达式输入结束符号
switch（ch）
{case’（’:
push（s,ch）;
break;
case’）’:
if（empty（s））{printf（“括号不配对”）;
exit（0）;
pop（s）;
if（!
empty（s））printf（“括号不配对”）;
elseprintf（“括号配对”）;
3.5
typedefstruct//两栈共享一向量空间
{ElemTypev[m];
//栈可用空间0—m-1
inttop[2]//栈顶指针
}twostack;
intpush（twostack*s,inti,ElemTypex）
//两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，
//本算法是入栈操作
{if（abs（s->
top[0]-s->
top[1]）==1）return（0）;
//栈满
else{switch（i）
{case0:
v[++（s->
top）]=x;
case1:
v[--（s->
default:
printf（“栈编号输入错误”）;
return（0）;
return
（1）;
//入栈成功
ElemTypepop（twostack*s,inti）
//两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作
{ElemTypex;
if（i!
=0&
i!
=1）return（0）;
//栈编号错误
if（s->
top[0]==-1）return（0）;
//栈空
elsex=s->
v[s->
top--];
break;
top[1]==m）return（0）;
top++];
return（0）;
return（x）;
//退栈成功
ElemTypetop（twostack*s,inti）
//两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作
switch（i）
top];
//取栈顶元素成功
3．6
voidAckerman（intm,intn）
//Ackerman函数的递归算法
{if（m==0）return（n+1）;
elseif（m!
n==0）return（Ackerman（m-1,1）;
elsereturn（Ackerman（m-1,Ackerman（m,n-1））
3．7
（1）linklist*init（linklist*q）
//q是以带头结点的循环链表表示的队列的尾指针，本算法将队列置空
{q=（linklist*）malloc（sizeof（linklist））;
//申请空间，不判断空间溢出
q->
next=q;
return（q）;
（2）linklist*enqueue（linklist*q，ElemTypex）
//q是以带头结点的循环链表表示的队列的尾指针，本算法将元素x入队
{s=（linklist*）malloc（sizeof（linklist））;
//将元素结点s入队列
q=s;
//修改队尾指针
（3）linklist*delqueue（linklist*q）
//q是以带头结点的循环链表表示的队列的尾指针，这是出队算法
{if（q==q->
next）return（null）;
//判断队列是否为空
else{linklist*s=q->
//s指向出队元素
if（s==q）q=q->
//若队列中只一个元素，置空队列
elseq->
next=s->
//修改队头元素指针
free（s）;
//释放出队结点
}//算法结束。
算法并未返回出队元素
3.8
{ElemTypedata[m];
//循环队列占m个存储单元
intfront,rear;
//front和rear为队头元素和队尾元素的指针
//约定front指向队头元素的前一位置，rear指向队尾元素
}sequeue;
intqueuelength（sequeue*cq）
//cq为循环队列，本算法计算其长度
{return（cq->
rear-cq->
front+m）%m;
3.9
{ElemTypesequ[m];
intrear,quelen;
//rear指向队尾元素,quelen为元素个数
（1）intempty（sequeue*cq）
//cq为循环队列，本算法判断队列是否为空
quelen==0?
1:
0）;
（2）sequeue*enqueue（sequeue*cq，ElemTypex）
//cq是如上定义的循环队列，本算法将元素x入队
{if（cq->
quelen==m）return（0）;
//队满
else{cq->
rear=（cq->
rear+1）%m;
//计算插入元素位置
cq->
sequ[cq->
rear]=x;
//将元素x入队列
cq->
quelen++;
//修改队列长度
return（cq）;
ElemTypedelqueue（sequeue*cq）
//cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素
quelen==0）return（0）;
//队空
else{intfront=（cq->
quelen+1+m）%m;
//出队元素位置
quelen--;
return（cq->
sequ[front]）;
//返回队头元素
第四章串（参考答案）
{chardata[MAXSIZE];
intcurlen;
//curlen表示终端结点在向量中的位置
}seqstring;
升级会员 