数据结构习题答案Word文档格式.docx
- 文档编号:3022119
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:32
- 大小:665.98KB
数据结构习题答案Word文档格式.docx
《数据结构习题答案Word文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构习题答案Word文档格式.docx(32页珍藏版)》请在冰点文库上搜索。
1/6*n*(n+1)*(n+2)
(6)i=1;
j=0;
While(i+j<
=n){
@if(i>
j)j++;
elsei++;
n
(7)x=n;
y=o;
while(x>
=(y+1)*(y+1)){
@y++;
n
(8)x=91;
y=100;
while(y>
0){
@if(x>
100){x-=10;
y--;
}
elsex++;
1100
1.2.3综合题20、
voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数
{
scanf("
%d,%d,%d"
&
x,&
y,&
z);
if(x<
y)x<
->
y;
//<
为表示交换的双目运算符,以下同
if(y<
z)y<
z;
//冒泡排序
printf("
%d%d%d"
x,y,z);
}//print_descending
1.2.3综合题22
试编写算法,计算i!
.2i的值并存入数组a[0…arrsize-1]的第i-1个分量中(I=1,2,….,n)。
假设计算机中允许的整数最大值为maxint,则当n>
arrsize或对某个k(1≤k≤n)使k!
.2k>
maxint时,应按出错处理,注意选择你认为较好的出错处理方法。
解:
Statusalgo119(inta[ARRSIZE])//求i!
*2^i序列的值且不超过maxint
last=1;
for(i=1;
=ARRSIZE;
i++)
a[i-1]=last*2*i;
if((a[i-1]/last)!
=(2*i))reurnOVERFLOW;
last=a[i-1];
returnOK;
}//algo119
分析:
当某一项的结果超过了maxint时,它除以前面一项的商会发生异常.
第二章线性表
作业:
2.2.2综合题3、
编写一个函数将一个向量A(有n个元素且任何元素均不为0)分拆成两个向量,使A中大于0的元素存放在B中,小于0的元素存放在C中。
本题的算法思想是:
依次遍历A的元素,比较当前的元素值,大于0者赋给B(假设有p个元素),小于0者赋给C(假设有q个元素)。
实现本题功能的函数如下:
voidret(vectorA,intn,vectorB,int*p,vectorC,int*q)
{inti;
*p=0;
*q=0;
for(i=0;
=n-1;
i++)
{if(A[i]>
0)
{(*p)++;
B[*p]=A[i];
if(A[i]<
{(*q)++;
C[*q]=A[i];
2.2.2综合题5、
编写一个函数从一给定的向量A中删除元素值在x到y(x≤y)之间的所有元素,要求以较高的效率来实现。
从0开始扫描向量A,以k记录下元素值在x到y之间的元素个数,对于不满足该条件的元素,前移k个位置。
最后返回向量的新长度,这种算法比每删除一个元素后立即移动其后元素效率要高一些。
实现本题功能的过程如下:
intdel(A,n,x,y)
vectorA;
intn;
ElemTypex,y;
{inti=0,k=0;
while(i<
n)
=x&
&
A[i]<
=y)k++;
elseA[i-k]=A[i];
/*前移k个位置*/
i++;
return(n-k);
2.2.2综合题8、
有两个向量A(有m个元素)和B(有n个元素),其元素均以从小到大的升序排列,编写一个函数将它们合并成一个向量C,要求C的元素也是以从小到大的升序排列。
依次扫描通过A和B的元素,比较当前的元素的值,将较小值的元素赋给C,如此直到一个向量扫描完毕,然后将未完的一个向量的余下所有元素赋给C即可。
intlink(vectora,intm,vectorb,intn,vectorc)
{inti=0,j=0,l,k=0;
while(i<
m&
j<
n)/*扫描通过a和b,将当前较小者赋给c*/
{if(a[i]<
b[j])c[k++]=a[i++];
elseif(a[i]>
b[j])c[k++]=b[j++];
else
{/*相等者只保存一个*/
c[k++]=b[j++];
if(i==m)/*b未完时,当余下的元素赋给c*/
for(l=j;
l<
n;
l++)
c[k++]=b[l];
if(j==n)/*a未完时,当余下的元素赋给c*/for(l=i;
m;
l++)
c[k++]=a[l];
returnk;
/*返回c的长度*/
2.2.2综合题9、
有一个单链表(不同结点的数据域值可能相同),其头指针为head,编写一个函数计算数据域为x的结点个数。
本题是遍历通过该链表的每个结点,每遇到一个结点,结点个数加1,结点个数存储在变量n中。
intcount(head,x)
node*head;
ElemTypex;
{
node*p;
intn=0;
p=head;
while(p!
=NULL)
if(p->
data==x)n++;
p=p->
next;
}
return(n);
2.2.2综合题11、
有一个单链表L(至少有1个结点),其头结点指针为head,编写一个函数将L逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点,如此等等。
本题采用的算法是:
从头到尾扫描单链表L,将第一个结点的next域置为NULL,
将第二个结点的next域指向第一个结点,将第三个结点的next域指向第二个结点,如此等等,直到最后一个结点,便用head指向它,这样达到了本题的要求。
voidinvert(head)
node*p,*q,*r;
q=p->
while(q!
=NULL)/*当L没有后续结点时终止*/
{r=q->
q->
next=p;
p=q;
q=r;
}head->
next=NULL;
head=p;
/*p指向L的最后一个结点,现改为头结点*/
2.2.2综合题16、
有一个有序单链表(从小到大排列),表头指针为head,编写一个函数向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。
本题算法的思想是先建立一个待插入的结点,然后依次与链表中的各结点的数据域比较大小,找到插入该结点的位置,最后插入该结点。
node*insertorder(head,x)
node*head;
ElemTypex;
node*s,*p,*q;
s=(node*)malloc(sizeof(node));
/*建立一个待插入的结点*/
s->
data=x;
if(head==NULL||x<
head->
data)/*若单链表为空或x小于第一个结点的date域*/
next=head;
/*则把s结点插入到表头后面*/
head=s;
else
{q=head;
/*为s结点寻找插入位置,p指向待比较的结点,q指向p的前驱结点*/
p=q->
=NULL&
x>
p->
data)/*若x小于p所指结点的data域值*/
if(x>
data)/*则退出while循环*/
q=p;
/*将s结点插入到q和p之间*/
next=s;
return(head);
2.2.2综合题23、
假设在长度大于1的循环单链表中,既无头结点也无头指针,p为指向该链表中某个结点的指针,编写一个函数删除该结点的前驱结点。
本题利用循环单链表的特点,通过p指针可循环找到其前驱结点q及q的前驱结点r,然后将其删除。
node*del(p)
node*q,*r;
/*查找p结点的前驱结点,用q指针指向*/
while(q->
next!
=p)q=q->
r=q;
/*查找q结点的前驱结点,用r指针指向*/
while(r->
=q)r=r->
r->
/*删除q所指的结点*/
free(q);
return(p);
2.2.2综合题41
试写一算法在带头结点的单链表结构上的实现线性表操作LOCATE(L,X)。
LNode*Locate(LinkListL,intx)//链表上的元素查找,返回指针
for(p=l->
p&
data!
=x;
next);
returnp;
}//Locate
第三章栈和队列
3.2.2综合习题13、
如果用一个循环数组qu[0,m0-1]表示队列时,该队列只有一个头指针front,不设队尾指针rear,而改置计数器count用以记录队列中结点的个数。
(1)编写实现队列的五个基本运算;
(2)队列中能容纳元素的最多个数还是m0-1吗?
(1)依题意,有如下条件:
队列为空:
count==0,front==1
队列为满:
count==m0
队列尾的第一个元素位置==(front+count)%m0
队列首的第一个元素位置==(front+1)%m0
队列类型定义如下:
typedefintqu[m0];
由此得到如下对应上述基本运算的5个函数如下:
/*m0定义为全局变量*/
voidmakenull(front,count)/*使队列q为空*/
intfront,count;
{front=1;
count=0;
}
intempty(count)/*判定队列q是否为空*/
intcount;
{if(count==0)return
(1);
elsereturn(0);
voidpop(q,front,count,x)/*取队列头元素给x*/
quq;
ElemType*x;
if(count==0)printf("
队列下溢出\n"
);
{front=(front+1)%m0;
*x=q[front];
voidenqueue(q,x,front,count)/*将元素x入队列*/
{intplace;
if(count==m0)printf("
队列上溢出\n"
{count++;
e=(front+count)%m0;
q[place]=x;
voiddequeue(q,front,count)/*删除队列头元素*/
count--;
(2)队列中可容纳的最多元素个数为m0个。
3.2.2综合习题31
假设称正读和反读都相同的字符序列为“回文”,例如,‘abba’和‘abcba’是回文,‘bcde’和‘ababa’则不是回文,试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。
intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0
InitStack(S);
InitQueue(Q);
while((c=getchar()!
='
@'
)
Push(S,c);
EnQueue(Q,c);
//同时使用栈和队列两种结构
while(!
StackEmpty(S))
Pop(S,a);
DeQueue(Q,b));
if(a!
=b)returnERROR;
returnOK;
}//Palindrome_Test
第三章串
4.2.3综合习题2、
若x和y是两个采用顺序结构存储的串,编写一个比较两个串是否相等的函数。
两个串相等表示对应的字符必须都相同,所以扫描两串,逐一比较相应位置的字符,若相同继续比较直到全部比较完毕,如果都相同则表示两串相等,否则表示两串不相等,由此得到如下函数:
intsame(x,y)
orderstring*x,*y;
inti=0,tag=1;
if(x->
len!
=y->
len)
return(0);
while(i<
x->
len&
tag)
vec[i]!
vec[i])tag=0;
i++;
return(tag);
4.2.3综合习题4、
采用顺序结构存储串s,编写一个函数删除s中第i个字符开始的j个字符。
先判定s串中要删除的内容是否存在,若存在则将第i+j-1之后的字符前移j个位置。
其函数如下:
orderstring*delij(s,i,j)
orderstring*s;
inti,j;
inth;
if(i+j<
for(h=i;
h<
i+j-1;
h++)/*第i+j-1之后的字符都前移j个位置*/
vec[h]=s->
vec[h+j];
len-=j;
return(s);
elseprintf("
无法进行删除操作\n"
);
4.2.3综合习题24、
编写算法,求串s所含不同字符的总数和每种字符的个数。
typedefstruct{
charch;
intnum;
}mytype;
voidStrAnalyze(StringtypeS)//统计串S中字符的种类和个数
mytypeT[MAXSIZE];
//用结构数组T存储统计结果
=S[0];
c=S[i];
while(T[j].ch&
T[j].ch!
=c)j++;
//查找当前字符c是否已记录过
if(T[j].ch)T[j].num++;
elseT[j]={c,1};
}//for
for(j=0;
T[j].ch;
j++)
printf("
%c:
%d\n"
T[j].ch,T[j].num);
}//StrAnalyze
4.2.3综合习题30
试写一算法,在串的堆存储结构上实现基本操作Concat(&
T,s1.s2).
voidHString_Concat(HStrings1,HStrings2,HString&
t)//将堆结构表示的串s1和s2连接为新串t
if(t.ch)free(t.ch);
t.ch=malloc((s1.length+s2.length)*sizeof(char));
=s1.length;
i++)t.ch[i-1]=s1.ch[i-1];
for(j=1;
=s2.length;
j++,i++)t.ch[i-1]=s2.ch[j-1];
t.length=s1.length+s2.length;
}//HString_Concat
第五章数组与广义表
5.2.3综合习题9、
假设稀疏矩阵A和B(具有相同的大小m×
n)都采用三元组表示,编写一个函数计算C=A+B,要求C也采用三元组表示。
本题采用的算法思想是:
依次扫描A和B的行号和列号,若A的当前项的行号等于B的当前项的行号,则比较其列号,将较小列的项存入C中,如果列号也相等,则将对应的元素值相加后存入C中;
若A的当前项的行号小于B的当前项的行号,则将A的项存入C中;
若A的当前项的行号大于B的当前项的行号,则将B的项存入C中。
这样产生了C,因此,实现本题功能的函数如下:
voidmatadd(A,B,C)
smatrikA,B,C;
inti=1,j=1,k=1;
=A[0][2]&
=B[0][2])
/*若A的当前项的行号等于B的当前项的行号,则比较其列号,将较小列的项*/
/*存入C中,如果列号也相等,则将对应的元素值相加后存入C中*/
if(A[i][0]==B[j][0])
if(A[i][1]<
B[j][1])
C[k][0]=A[i][0];
C[k][1]=A[i][1];
C[k][2]=A[i][2];
k++;
elseif(A[i][1]>
C[k][0]=B[j][0];
C[k][1]=B[j][1];
C[k][2]=B[j][2];
j++;
C[k][2]=A[i][2]+B[j][2];
if(C[k][2]!
=0)k++;
elseif(A[i][0]<
B[j][0])
/*若A的当前项的行号小于B的当前项的行号,则将A的项存入C中*/
else/*若A的当前项的行号大于B的当前项的行号,则将B的项存入C中*/
C[0][0]=A[0][0];
/*产生第0行的结果*/
C[0][1]=A[0][1];
C[0][2]=k-1;
5.2.3综合习题26
试设计一个算法,将数组An中的元素A[0]至A[n-1]循环右移k位,并要求只用一个元素大小的附加存储,元素移动或交换次数为O(n)。
voidRSh(intA[n],intk)//把数组A的元素循环右移k位,只用一个辅助存储空间
=k;
if(n%i==0&
k%i==0)p=i;
//求n和k的最大公约数p
for(i=0;
p;
j=i;
l=(i+k)%n;
temp=A[i];
while(l!
=i)
A[j]=temp;
temp=A[l];
A[l]=A[j];
j=l;
l=(j+k)%n;
}//循环右移一步
A[i]=temp;
}//RSh
要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"
循环链"
上面.举例如下:
n=15,k=6,则p=3.
第一条链:
A[0]->
A[6],A[6]->
A[12],A[12]->
A[3],A[3]->
A[9],A[9]->
A[0].
第二条链:
A[1]->
A[7],A[7]->
A[13],A[13]->
A[4],A[4]->
A[10],A[10]->
A[1].
第三条链:
A[2]->
A[8],A[8]->
A[14],A[14]->
A[5],A[5]->
A[11],A[11]->
A[2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 习题 答案