算法与数据结构C语言习题参考答案15章Word文档格式.docx
《算法与数据结构C语言习题参考答案15章Word文档格式.docx》由会员分享,可在线阅读,更多相关《算法与数据结构C语言习题参考答案15章Word文档格式.docx(32页珍藏版)》请在冰点文库上搜索。
}
【答】循环控制变量i从1增加到n,循环体执行n次,第一句i的初始化执行次数为1,第二句执行n次,循环体中第一句printf执行n次,第二句i从1循环到n,共执行n次。
所以该程序段总的时间代价为:
T(n)=1+n+2n=3n+1=O(n)
6.计算下列程序片断的时间代价:
intj=1;
while(j<
intk=1;
while(k<
printf(“i=%d,j=%d,k=n%”d,I,j,k);
k=k+1;
j=j+1;
【答】循环控制变量i从1增加到n,最外层循环体执行n次,循环控制变量j从1增加到n,中间层循环体执行n次,循环控制变量k从1增加到n,最内层循环体执行n次,所以该程序段总的时间代价为:
T(n)=1+n+n{1+n+n[1+n+2n+1]+1+1+1
=3n3+3n2+4n+2
=O(n3)
2.线性表
1.试写一个插入算法intinsertPost_seq(palist,p,x),在palist所指顺序表中,下标为p的元素之后,插入一个值为x的元素,返回插入成功与否的标志。
【答】
数据结构
采用2.1.2节中顺序表定义。
intinsertPost_seq(PseqListpalist,intp,DataTypex){
/*在palist所指顺序表中下标为p的元素之后插入元素x*/
intq;
if(palist->
n>
=palist->
MAXNUM){
printf(“Overflow”);
returnO;
if(p<
0||p>
palist->
n-1){
printf(“Notexis”!
);
return0;
for(q=palist->
n-1;
q>
=p+1;
q--)/*插入位置及之后的元素均后移一个位置*/
element[q+1]=palist->
element[q];
element[p+1]=x;
palist->
n二palist->
n+1;
return1;
}/*插入元素x*/
/*元素个数加1*/
/*不存在下标为p的元素*/
/*溢出*/
2试写一个删除算法deleteV_seq(palist,x,在palist所指顺序表中,删除一个值为x的元素,返回删除成功与否的标志。
采用2.1.2节中顺序表定义。
intdeleteV_seq(PseqListpalist,p,DataTypex){
/*在palist所指顺序表中删除值为x的元素*/
intp,q;
for(p=0;
pvn;
p++)/*查找值为x的元素的下标*/
if(x==palist->
element[p]){
for(q=p;
q<
n-1;
q++)/*被删除元素之后的元素均前移一个位置*/
element[q]=palist->
element[q+1];
return1;
/*元素个数减1*/
3.设有一线性表e=(e
0,e
1,e
2,,,e
n1),其逆线性表定义为e=(e
n1,,,e
2,e
1,e
0)。
请设计一个算法,将用顺序表表示的线性表置逆,要求逆线性表仍占用原线性表的空间。
采用2.1.2节中顺序表的定义。
思路
考虑对数组element[]进行置逆,即把第一个元素和最后一个元素换位置,把第二个元素和倒数第二个元素换位置••…。
这种调换的工作只需对数组的前一半元素进行,所以设置整数变量count
用于存放数组长度的一半的值。
大家可以考虑一下:
为什么不能对整个数组进行如上的对元素换位置”的工作?
(提示:
这样会将本来已经置逆的线性表又置逆回来,即又变成了原来的表。
)顺序表的置逆算法
voidrev_seq(PSeqListpalist){
DataTypex;
intcount,i;
if(palist->
n==0||palist->
n==1)return;
count=palist->
n/2;
for(i=0;
i<
count;
i++){
x=palist->
element[i];
element[i]=palist->
element[palist->
n1i];
n1i]=x;
}/*只需调换半个表的元素*/
/*空表或只有一个元素,直接返回*/代价分析
该算法中包含一个for循环,其循环次数为n/2。
因此,算法的时间代价为0(n)。
4•已知长度为n的线性表A采用顺序存储结构,请写一算法,找出该线性表中值最小的数据元素。
设置变量min,遍历整个表,不断更新当前已经经历过的元素的最小值即可。
为方便起见,事先假设表不为空。
算法
DataTypemin_seq(PSeqListpalist){
DataTypemin;
inti;
/*求非空顺序表中的最小数据元素*/
min=palist->
element[0];
for(i=1;
palist->
n;
i++)
if(min>
palist->
element[i])
returnmin;
}/*初始化min*/
/*min中保存的总是当前的最小数据*/
代价分析
该算法访问顺序表中每个元素各一次,时间代价为0(n)。
讨论
读者可以试图对上面的算法进行修改,使返回的值不是最小元素的值而是它的下标。
5•已知线性表A的长度为n,并且采用顺序存储结构。
写一算法,删除线性表中所有值为x的元素。
为了减少移动次数,可以采用快速检索的思想,用两个变量i,j记录顺序表
中被处理的两端元素的下标,开始时i=0,j=n1,边检索第i个元素边增加i,直到找到一个元素值等于X,再边检索第j个元素边减少j,直到找到一个元素值不等于x,把下标为j的元素移到下标为i的位置后重复上述过程,直到i另用一变量count记录删除了多少个元素。
voiddelx_seq(PSeqListp,DataTypex){
/*删除顺序表中所有值为x的元素,新顺序表可能不保持原有顺序*/
inti=0,j=p->
n1,count=0;
while(i<
j){
if(p->
element[i]==x){/*找到了一个要删除的元素*/
while((p->
element[j]==x)&
&
(i!
=j)){
/*从后往前找不会被删除的元素,当i,j相等时退出循环,count记录从后往前找的过程中遇到了多少个要删的元素*/
count++;
if(i==j){
p->
n二p->
ncount1;
return;
else{
element[i]=p->
element[j];
j;
i++;
}/*i定位于顺序表开始处,j定位于顺序表最后*/p->
n=p->
ncount;
element[i]==x)p>
n;
这个算法使用了一点技巧使得在中间删除元素时,避免了最后一串元素的移动。
但是,它破坏了原来线性表中元素之间的顺序关系。
如果需要保持原来的顺序应该怎样做?
这里提供一种可行的思路:
从前向后遍历表,如果元素不是x,则继续向后;
如果元素是x,则寻找其后第一个不是x的元素,将这两个元素互换。
具体算法请读者自己实现。
6•写一算法,在带头结点的单链表llist中,p所指结点前面插入值为x的新结点,并返回插入成功与否的标志。
采用2.1.3节中单链表定义。
思想:
由于在单链表中,只有指向后继结点的指针,所以只有首先找到p所指结
点的前驱结点,然后才能完成插入。
而找p所指结点的前驱结点,只能从单链
表的第一个结点开始,使用与locate」nk类似的方式进行搜索。
算法:
intinsertPre_link(LinkListllist,PNodep,DataTypex){
/*在llist带头结点的单链表中,p所指结点前面插入值为x的新结点*/
PNodep1;
if(llist==NULL)return0;
p1=llist;
while(p1!
=NULL&
p1->
link!
=p)p1=p1->
link;
/*寻找p所指结点的前驱结点*/
if(p1=NULL)return0;
PNodeq=(PNode)malloc(sizeof(structNode));
/*申请新结点*/
if(q=NULL){printf(“Outofsnp”ac)e;
r!
e!
!
turn0;
q->
info=x;
link=p1->
link=q;
7.写一算法,在带头结点的单链表llist中,删除p所指的结点,并返回删除
成功与否的标志。
采用2.1.3节中单链表定义。
由于在单链表中,只有指向后继结点的指针,所以只有首先找到p所指结点的前驱结点,然后才能完成删除。
而找p所指结点的前驱结点,只能从单链表的第一个结点开始,使用与locate_link类似的方式进行搜索。
intdeleteP_link(LinkListllist,PNodep){
/*在llist带头结点的单链表中,删除p所指的结点*/
if(llist==NULL)returnNull;
/*寻找p所指结点的前驱结点*/if(p1=NULL)return0;
link=p->
free(p);
/*删除结点p*/
8.已知list是指向无头结点的单链表的指针变量,写出删除该链表下标为i
的(第i+1个)结点的算法。
依次遍历表中的每一个结点并计数,到第i+1个结点时实行删除。
由于链表是无头结点的,所以在删除第一个结点时要特别注意。
intdeleteindex_link_nohead(LinkList*pllist,inti){
/*删除单链表中下标为i的结点。
删除成功返回TRUE否则返回FALSE*/intj;
PNodep,q;
if((*pllist)==NULL||i<
0)returnFALSE;
if(i==0){
q=(*pllist);
(*pllist)=(*pllist)->
link;
free(q);
returnTRUE;
p=(*pllist);
j=0;
while(p->
link!
=NULL&
j<
i1){
p=p->
j++;
link==NULL)returnFALSE;
q=p->
link=q->
}/*此元素不存在*/
/*寻找下标为i1的结点的地址*//*如果需要删除第一个结点*/代价分析
该算法访问单链表中前面i个结点,时间代价为O(i),最大不超过O(n)。
如果函数参数不是LinkList*类型而是LinkList类型,在删除i=0的结点时,程序不能正确实现,其原因请读者思考(考虑C语言的参数传递方式)。
如果单链表带表头结点,重写本题的算法。
比较这两个算法,是否能体会到表头结点的作用。
9•已知list是指向无头结点的单链表的指针变量,写出删除该链表中从下标为i的(第i+1个)结点开始的连续k个结点的算法。
采用2.1.3节单链表定义。
这道题与上题相似,只需要增加计数即可。
要注意的是应该判断给出的i和
k是否合理,是不是会超出链表长度。
intdel_link_nohead(LinkList*pllist,inti,intk){
/*删除单链表中从下标i开始的k个结点。
删除成功返回TRUE否则返回
FALSE*/intj;
0||k<
=0)returnFALSE;
if(i==0){/*如果需要删除从第一个结点开始的k个结点*/for(j=0;
k&
(*pllist)!
=NULL;
j++){
j=0;
while(p->
}/*第i个结点不存在*/
for(j=0;
p->
link!
j++){/寻找下标为i1的结点的地址*/
该算法访问单链表中前面i+k个结点,时间代价为O(i+k),最大不超过0(n)。
13.请设计一个算法,求出循环表中结点的个数。
采用不带头结点的循环链表。
structNode;
typedefstructNode*PNode;
structNode{
DataTypeinfo;
PNodelink;
};
typedefstructNode*LinkList;
遍历整个循环链表,同时计数即可。
错误算法
intcount(LinkListclist){
intcount;
p=clist;
if(clist==NULL)return0;
count=1;
while(q!
=p){
returncount;
}q=q->
count++;
/*如果是空表*/
错误:
如果clist是一个空表,那么第5行的语句“q=-p>
是”非法的。
分析:
应把第6行语句(用下划线表示)提前1行或2行。
一定要放在语句“q二->
之前。
缺点:
增加局部变量p。
这样做没有必要,因为p的初值置为clist,在程序中并没有对p做
其他修改,所以程序中不需要引入p而直接使用clist即可。
intcount(LinkListclist){
PNodeq;
if(clist==NULL)return0;
q=clist->
=clist){
q=q->
该算法访问循环链表中每个结点各一次,时间代价为0(n)。
4•栈与队列
1•写一个递归算法来把整数字符串转换为整数。
(例:
“43567”宀43567
先递归调用本算法转换除去末位外剩余的字符串,结果乘以10。
再转换末
位。
将两结果相加即为所求。
intstringToInt1(char*s,intstart,intend){
/*把整数字符串s中从start到end的部分转换为整数*/
intstringToInt(char*s){
}inti=0;
while(s[i]!
='
\0'
)i++;
/*计算字符串的长度*/
returnstringToInt1(s,0,i1);
/*把整数字符串s转换为整数*/if(start>
end)return1;
/*转换失败*/
/*只有一个字符,直接转换*/if(start==end)returns[end]'
0'
;
returnstringToInt1(s,start,end1)*10+s[end]'
/*先转换其他位,再转
换末位*/代价分析
设n为字符串的长度。
该算法访问每个字符各一次,时间代价为0(n),计
算字符串的长度的时间代价也为0(n)。
故总的时间代价为0(n)。
递归算法需要栈的支持,栈的大小与递归调用的深度成正比。
所以实际空间开销为O(n)。
2.编写一个算法,对于输入的十进制非负整数,将它的二进制表示打印出来。
采用4.1.2节中栈的顺序表示。
将输入的十进制数字反复除以2,直到它变为0。
将每次的数字模2的余数入栈。
栈中存放的就是所要求的二进制表示。
再将栈中的元素依次弹出打印即可。
voidprint_bin(intdec_number){
PSeqStackpastack;
inttemp=dec_number;
if(temp<
0){
printf("
Error!
\n"
);
return;
pastack=createEmptyStack_seq();
/建立一个空栈*/
/*将十进制非负整数转化为二进制数打印出来*/if(pastack==NULL)return;
while(temp>
push_seq(pastack,temp%2);
temp/=2;
while(!
isEmptyStack_seq(pastack)){
%d"
top_seq(pastack));
pop_seq(pastack);
free(pastack);
设输入的十进制数字为n,则算法的时间代价为O(log
2n)。
空间代价主要是栈的大小,为O(log
3.写一个算法:
PSeqStackcreateEmptyStack_seq(intm创I建一个空栈。
PSegStackcreateEmptyStack_seq(intm){
/*创建一个空栈*/
PSeqStackpastack=(PSeqStack)malloc(sizeof(structSeqStack));
if(pastack!
=NULL){
if(pastack->
s){
/*栈顶变量赋值为-1*/
pastack->
s=(DataType*)malloc(sizeof(DataType)*m);
MAXNUM=m;
t=-1;
return(pastack);
elsefreepastack;
printf(“Outofspacne”!
returnNULL;
}/*存储分配失败*/
4,写一个算法:
intisEmptyStack_seq(PSeqStackpastac判断pastack所指的栈是否为空栈。
intisEmptyStack_seq(PSeqStackpastack){
/*判断pastack所指的栈是否为空栈*/
if(pastack->
t==-1)return1;
elsereturn0;
8.假设以循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设队头指
针),试编写相应的创建空队列、入队列和出队列的算法。
采用不带头结点的循环链表表示队列。
structNode{
};
structClinkQueue{
PNoder;
typedefstructClinkQueue*PCIinkQueue;
/*指向循环链表表示的队列的指针类型*//*循环链表表示的队列类型*/
/*尾指针*/
与队列的单链表表示相似,但节省了指向队头的指针变量,所以在