数据结构习题答案汇总.docx
《数据结构习题答案汇总.docx》由会员分享，可在线阅读，更多相关《数据结构习题答案汇总.docx（70页珍藏版）》请在冰点文库上搜索。
数据结构习题答案汇总
第一章
1.9解：
因为初始x=2假设循环执行了y次，则有
，
解之得 y>=
故可得，时间复杂度
；count=
1.17
intfib（intk,intm,int&f）
{int*temp;if（k<2||m<0）return0;
if（melseif（m==k-1）f=1;
else
{temp=（int*）malloc（m*sizeof（int））;
for（inti=0;i<=k-2;i++）temp[i]=0;
temp[k-1]=1;//初始化
for（i=k;i<=m;i++）//求出序列第k至第m个元素的值
{intsum=0;
for（intj=i-k;jtemp[i]=sum;}
f=temp[m];
free（temp）;
}return1;
}
intmain（intargc,char*argv[]）
{intk,m,f;
cout<<"pleaseinputthek&m:
"<>k>>m;
if（fib（k,m,f））cout<<"Thevalueis:
"<elsecout<<"inputdataerror!
"<return0;}
1.18
#defineSIZE100
typedefstruct{char*sport;
intgender;//取0,1;分别代表male,female
//enum{male,female}gender;
charschoolname;//校名为'A','B','C','D'或'E'
char*result;intscore;}resulttype;
typedefstruct{intmalescore；
intfemalescore;inttotalscore;}scoretype;
voidsummary（resulttyperesult[],intn）//求各校的男女总分和团体总分,假设结果已经储存在result[]数组中
{scoretypescore[5]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}};//需要同初值
for（inti=0;i{
while（result[i].sport!
=NULL）
{
switch（result[i].schoolname）
{
case'A':
score[0].totalscore+=result[i].score;
if（result[i].gender==0）
score[0].malescore+=result[i].score;
else
score[0].femalescore+=result[i].score;
break;
case'B':
score[1].totalscore+=result[i].score;
if（result[i].gender==0）
score[1].malescore+=result[i].score;
else
score[1].femalescore+=result[i].score;
break;
case'C':
score[2].totalscore+=result[i].score;
if（result[i].gender==0）
score[2].malescore+=result[i].score;
else
score[2].femalescore+=result[i].score;
break;
case'D':
score[3].totalscore+=result[i].score;
if（result[i].gender==0）
score[3].malescore+=result[i].score;
else
score[3].femalescore+=result[i].score;
break;
case'E':
score[4].totalscore+=result[i].score;
if（result[i].gender==0）
score[4].malescore+=result[i].score;
else
score[4].femalescore+=result[i].score;
break;
default:
break;
}
}
}
for（i=0;i<5;i++）
{
cout<<"School"<"<cout<<"Totalscoreofmale:
"<cout<<"Totalscoreoffemale:
"<cout<<"Totalscoreofall:
"<}
}
intmain（intargc,char*argv[]）
{
intn;
resulttyperesult[SIZE];//可以用动态分配内存的方法，根据输入的n分配内存
cout<<"pleaseinputthen:
"<cin>>n;
cout<<"pleaseinputtheresultsport,gender,schoolname,result,score:
"<for（inti=0;i{cin>>result[i].sport
>>result[i].gender
>>result[i].schoolname
>>result[i].result
>>result[i].score;
}
summary（result,n）;
return0;
}
第二章
2.11
StatusInsert_SqList（SqList&va,intx）//把x插入递增有序表va中
{if（va.length+1>va.listsize）return0;
va.length++;
for（inti=va.length-2;va.elem[i]>x&&i>=0;i--）
va.elem[i+1]=va.elem[i];
va.elem[i+1]=x;
return1;
}
2.12
Statuscomp（SqListA,SqListB）{
inti=0,j=0;
while（ii--;j--;
if（i==A.length&&j==B.length）return0;
if（i==A.length&&j!
=B.length）return-1;
if（i!
=A.length&&j==B.length）return1;
if（A.elem[i]>B.elem[j]）
return1;
else
return-1;
}
第二种方法
StatusListComp（SqListA,SqListB）//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A{
for（inti=0;A.elem[i]||B.elem[i];i++）
if（A.elem[i]!
=B.elem[i]）returnA.elem[i]-B.elem[i];
return0;
}//ListComp
2.21
voidinvert（SqList&C）
{intm=C.length/2;
inti,n;
n=C.length;
ElemTypetemp;
for（i=0;i{
temp=C.elem[i];
C.elem[i]=C.elem[n-i-1];
C.elem[n-i-1]=temp;
}
}
作业三
typedefintStatus;
typedefintElemType;
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
voidCreate（LinkList&L,intn）//尾插法创建单链表;
{ElemTypedata;
L=（LinkList）malloc（sizeof（LNode））;
L->next=NULL;
LinkListt,s;
t=L;
cout<<"创建一个带头结点的单链表!
"<for（inti=0;i{cout<<"请输入第"<";
cin>>data;
s=（LinkList）malloc（sizeof（LNode））;
s->data=data;s->next=NULL;
t->next=s;t=s;}
}
voidPrint（LinkListL）//遍历单链表的元素
{LinkListh=L->next;
cout<<"链单表的元素值为:
";
while（h）
{
cout<data<<"";
h=h->next;
}
cout<}
（2.19）
StatusDelet_Between（LinkList&L,intmink,intmaxk）//删除递增链表中mink,maxk之间的元素；
{LinkListp,q,r;
p=L;
while（p->next->data<=mink）
p=p->next;
if（p->next）
{
q=p->next;
while（q->data{
r=q;
q=q->next;
free（r）;
}
p->next=q;
}
return1;
}
（2.22）
StatusInvert（LinkList&L）
{LinkListp,q,r;
q=L;
p=L->next;
while（p）
{r=p->next;
if（q==L）p->next=NULL;//原首元结点指向空（现为尾结点）
elsep->next=q;
q=p;p=r;
}
if（L->next）
L->next=q;//头结点指向原尾结点（现为首元结点）
return1;
}
（2.24）
voidConnect（LinkList&A,LinkList&B,LinkList&L）
{LinkListpa,pb,pc,pre;
pre=（LinkList）malloc（sizeof（LinkList））;
pc=pre;//pc总指向生成的新单链表的最后一个节点；
pa=A->next;pb=B->next;
while（pa&&pb）
{
if（pa->datadata）
{pc->next=pa;pc=pa;pa=pa->next;}
Else
{pc->next=pb;pc=pb;pb=pb->next;}
}
if（pa!
=NULL）pc->next=pa;
if（pb!
=NULL）pc->next=pb;
L=pre;
Invert（L）;
}
intmain（intargc,char*argv[]）
{LinkListL,A,B,C;
intmink,maxk,n;
cout<<"请输入所要创建的单链表元素个数n:
";
cin>>n;
Create（L,n）;
Print（L）;
cout<<"请输入要删除元素的区间[mink,maxk]:
";
cin>>mink>>maxk;
Delet_Between（L,mink,maxk）;
Print（L）;
Invert（L）;
Print（L）;
cout<<"请输入所要创建的单链表A元素个数n:
";
cin>>n;
Create（A,n）;
Print（A）;
cout<<"请输入所要创建的单链表B元素个数n:
";
cin>>n;
Create（B,n）;
Print（B）;
Connect（A,B,C）;
Print（C）;
return0;}
作业四
typedefintStatus;
typedefcharElemType;
typedefstructLNode{
ElemTypedata;
structLNode*next;
structLNode*pre;
}LNode,*LinkList;
//创建单链表
voidCreate（LinkList&L,intn）//尾插法创建单链表;
{
ElemTypedata;
L=（LinkList）malloc（sizeof（LNode））;
L->next=NULL;
L->pre=NULL;
LinkListt,s;t=L;
cout<<"创建一个带头结点的单链表!
"<for（inti=0;i{cout<<"请输入第"<";
cin>>data;
s=（LinkList）malloc（sizeof（LNode））;
s->data=data;s->next=NULL;s->pre=NULL;
t->next=s;t=s;
}
//t->next=L;
}
//输出单链表
voidPrint1（LinkListL）//遍历单链表的元素
{LinkListh=L->next;
cout<<"链单表的元素值为:
";
while（h）
{cout<data<<"";
h=h->next;
}
cout<}
//输出循环单链表
voidPrint2（LinkListL）//遍历单链表的元素
{LinkListh=L->next;
cout<<"链单表的元素值为:
";
while（h!
=L）
{cout<data<<"";h=h->next;}
cout<}
//前向输出循环单链表
voidPrint3（LinkListL）//遍历单链表的元素
{LinkListh=L->pre;
cout<<"链单表的元素值为:
";
while（h!
=L）
{cout<data<<"";h=h->pre;}
cout<}
//（2.31）
StatusDelete_Pre（LinkLists）//删除单循环链表中结点s的直接前驱
{LinkListp;p=s;
while（p->next->next!
=s）
p=p->next;//找到s的前驱的前驱p
p->next=s;return1;
}
//（2.32）
StatusDuLNode_Pre（LinkList&L）//完成双向循环链表结点的pre域
{LinkListp;
for（p=L;p->next->pre!
=NULL;p=p->next）
p->next->pre=p;return1;
}//DuLNode_Pre
//（2.33）
StatusLinkList_Divide（LinkList&L,LinkList&A,LinkList&B,LinkList&C）//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
{LinkLists,p,q,r;s=L->next;
A=（LinkList）malloc（sizeof（LNode））;p=A;
B=（LinkList）malloc（sizeof（LNode））;q=B;
C=（LinkList）malloc（sizeof（LNode））;r=C;//建立头结点
while（s）
{if（s->data>='0'&&s->data<='9'）
{p->next=s;p=s;s=s->next;}
elseif（（s->data>='a'&&s->data<='z'）||（s->data>='A'&&s->data<='Z'））
{q->next=s;q=s;s=s->next;}
else
{r->next=s;r=s;s=s->next;}
}
p->next=A;q->next=B;r->next=C;return1;
}
intmain（intargc,char*argv[]）
{intn;
LinkListL,s,A,B,C;
cout<<"请输入要创建的单向循环链表元素的个数n:
";
cin>>n;
Create（L,n）;Print1（L）;
LinkList_Divide（L,A,B,C）;
Print2（A）;Print2（B）;Print2（C）;
s=A->next->next;
Delete_Pre（s）;
Print2（A）;
/*DuLNode_Pre（L）;
Print2（L）;*/
return0;
}
第三章
作业五
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOVERFLOW-2
#defineERROR0
typedefcharSElemtype;
typedefintstatus;
typedefstruct{
SElemtype*base;
SElemtype*top;
intstacksize;
}Sqstack;
//构造顺序栈
statusInitstack（Sqstack&s）
{s.base=（SElemtype*）malloc（STACK_INIT_SIZE*sizeof（SElemtype））;
if（!
s.base）exit（OVERFLOW）;
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return1;
}
//将元素进栈
statusPush（Sqstack&s,SElemtypee）
{
if（s.top-s.base>=s.stacksize）
{s.base=（SElemtype*）realloc（s.base,（s.stacksize+STACKINCREMENT）*sizeof（SElemtype））;
if（!
s.base）exit（OVERFLOW）;
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;}
*s.top++=e;
return1;
}
//将元素出栈
statusPop（Sqstack&s,SElemtype&e）
{
if（s.base==s.top）returnERROR;
s.top--;
e=*s.top;
return1;
}
chargetpop（Sqstack&s）
{
chare;
if（s.base==s.top）returnERROR;
e=*（s.top-1）;
returne;
}
（3.17）
statusIsReverse（Sqstack&s）//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0
{
Initstack（s）;
chare,c;
printf（"请输入要检测的模式串:
"）;
while（（e=getchar（））!
='&'）
Push（s,e）;
while（（e=getchar（））!
='@'）
{
if（s.base==s.top）return0;
Pop（s,c）;
if（e!
=c）return0;
}
if（s.base!
=s.top）return0;
return1;
}//IsReverse
（3.19）statusmatch（charc[]）//括号匹配！
{inti=0;
chare;
Sqstacks;
Initstack（s）;
while（c[i]!
='#'）
{switch（c[i]）
{
case'{':
case'[':
case'（':
Push（s,c[i]）;break;
case'}':
if（s.base!
=s.top&&getpop（s）=='{'）
{Pop（s,e）;break;}
elsereturn0;
case']':
if（s.base!
=s.top&&getpop（s）=='['）
{Pop（s,e）;break;}
elsereturn0;
case'）':
if（s.base!
=s.top&&getpop（s）=='（'）
{Pop（s,e）;break;}
elsereturn0;
}
i++;
}
if（s.base==s.top）return1;//栈为空匹配;
elsereturn0;
}
voidmain（）
{/*charstr[100];
printf（"请输入要模式序列:
"）;gets（str）;
if（match（str））
cout<<"括号匹配成功！
"<else
cout<<"括号不匹配！
"<Sqstacks;
if（IsReverse（s））
cout<<"两模式串互逆!
"<else
cout<<"两模式串不互逆!
"<}
第四章
typedefintStatus;
typedefcharStringtype;
#defineMAXSTRLEN255
typedefstruct{
char*ch;
intlength;
}HString;
StatusStrAssign（HString&S,char*
升级会员 