数据结构作业参考答案.docx
《数据结构作业参考答案.docx》由会员分享，可在线阅读，更多相关《数据结构作业参考答案.docx（37页珍藏版）》请在冰点文库上搜索。
数据结构作业参考答案
作业1.线性表
编程作业：
1．将顺序表逆置，要求用最少的附加空间。
参考答案
#include
#include
#include
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
typedefstruct
{ElemType*elem;
intlength;
intlistsize;
}SqList;
//创建空顺序表
StatusInitList_Sq（SqList&L）
{
L.elem=（ElemType*）malloc（LIST_INIT_SIZE*sizeof（ElemType））;
if（!
L.elem）
exit（OVERFLOW）;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
//顺序表在第i个元素之前插入e
Statussxbcr（SqList&L,inti,ElemTypee）
{
ElemType*p,*q;
if（（i<1）||（i>L.length+1））
return（ERROR）;
else
{q=&（L.elem[i-1]）;
for（p=&（L.elem[L.length-1]）;p>=q;--p）
*（p+1）=*p;
*q=e;
++L.length;
return（OK）;
}
}
//顺序表显示
voidxsList（SqListL）
{
inti=L.length,k;
for（k=0;kprintf（"%d",L.elem[k]）;
printf（"\n"）;
}
//顺序表逆置
voidnizhi（SqList&L）
{
inti=0,j=L.length-1;
ElemTypetemp;
for（;i{
temp=L.elem[i];
L.elem[i]=L.elem[j];
L.elem[j]=temp;
}
}
main（）
{
SqListL;
charflag1='y',flag2='n';
inti;
ElemTypek;
if（InitList_Sq（L））
{
printf（"建立空顺序表成功！
\n"）;
do{
printf（"当前线性表长度为：
%d\n",L.length）;
printf（"请输入要插入元素的位置：
"）;
scanf（"%d",&i）;
printf（"请输入要插入的元素值：
"）;
scanf（"%d",&k）;
if（sxbcr（L,i,k））
{
printf（"插入成功，插入后顺序表长度为：
%d\n",L.length）;
printf（"插入后的顺序表为：
"）;
xsList（L）;
}
else
printf（"插入失败"）;
printf（"\n继续插入元素？
（y/n）"）;
fflush（stdin）;
scanf（"%c",&flag1）;
}while（flag1=='y'）;
nizhi（L）;
printf（"顺序表逆置后为：
\n"）;
xsList（L）;
}
}
2．从键盘读入n个整数（升序），请编写算法实现：
（1）CreateList（）：
建立带表头结点的单链表；
（2）PrintList（）：
显示单链表，（形如：
H->10->20->30->40）;
（3）InsertList（）：
在有序单链表中插入元素x；
（4）ReverseList（）：
单链表就地逆置；
（5）DelList（）：
在有序单链表中删除所有值大于mink且小于maxk的元素。
选作：
使用文本菜单完成功能选择及执行。
参考答案：
#include
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
typedefintStatus;
typedefintElemType;
typedefstructnode{
ElemTypedata;
structnode*link;
}Lnode,*LinkList;
//头插法建立单链表
voidCreate_L1（LinkList&L,intn）
{
LinkListp;
inti;
L=（LinkList）malloc（sizeof（Lnode））;
L->link=NULL;
for（i=n;i>0;--i）
{
p=（LinkList）malloc（sizeof（Lnode））;
scanf（"%d",&p->data）;
p->link=L->link;
L->link=p;}
}
//尾插法建立单链表
voidCreate_L2（LinkList&L,intn）
{
LinkLists,p;
inti;
L=（LinkList）malloc（sizeof（Lnode））;
L->data=0;
L->link=NULL;
p=L;
for（i=1;i<=n;i++）
{
s=（LinkList）malloc（sizeof（Lnode））;
scanf（"%d",&s->data）;
s->link=NULL;
p->link=s;
p=s;}
}
//查找是否存在结点e
LinkListdlbcz（LinkListL,ElemTypee）
{
LinkListp=L->link;
while（p!
=NULL&&p->data!
=e）
p=p->link;
return（p）;
}
//在第i个元素之前插入结点e
StatusListInsert_L（LinkListL,inti,ElemTypee）
{
LinkListp=L,s;
intj=0;
while（p&&j{p=p->link;++j;}
if（!
p||j>i-1）
returnERROR;
s=（LinkList）malloc（sizeof（Lnode））;
s->data=e;
s->link=p->link;
p->link=s;
returnOK;
}
//删除第i个结点
StatusListDelete_L（LinkListL,inti,ElemType&e）
{
LinkListp=L,q;
intj=0;
while（p->link&&j{
p=p->link;++j;}
if（!
（p->link）||j>i-1）
returnERROR;
q=p->link;
p->link=q->link;
e=q->data;
free（q）;
returnOK;
}
//求第i个元素值
StatusGetElem_L（LinkListL,inti,ElemType&e）
{
intj=1;
LinkListp=L->link;
while（p&&j{p=p->link;j++;}
if（!
p||j>i）returnERROR;
e=p->data;
returnOK;
}
//显示单链表中元素
voidxsList（LinkListL）
{
LinkListp=L->link;
while（p）
{
printf（"%d",p->data）;
p=p->link;
}
}
//删除大于mink且小于maxk的元素
voidDelList（LinkList&L,ElemTypemink,ElemTypemaxk）
{
LinkListp=L,q;
while（p->link&&p->link->datap=p->link;
q=p;
while（q&&q->dataq=q->link;
p->link=q;
}
//就地升序排序
voidsh_sort（LinkList&L）
{
LinkListp=L->link,pre=L,q=L->link->link,u;
p->link=NULL;
while（q）
{
p=L->link;
pre=L;
while（p&&p->datadata）
{
pre=p;
p=p->link;
}
u=q->link;
pre->link=q;
q->link=p;
q=u;
}
}
//就地逆置
voidnizhi（LinkList&L）
{
LinkListp=L->link,q=L->link->link,u;
p->link=NULL;
while（q）
{
u=q->link;
q->link=L->link;
L->link=q;
q=u;
}
}
//有序表插入
voidyxcharu（LinkList&L,ElemTypee）
{
LinkListpre,p,s;
pre=L;
p=L->link;
while（p&&p->data{
pre=p;
p=p->link;
}
s=（LinkList）malloc（sizeof（Lnode））;
s->data=e;
s->link=p;
pre->link=s;
}
main（）
{
LinkListL;
intn,i,mink,maxk;
ElemTypee;
charchoice='0';
while（choice!
='q'）
{
printf（"\n****************\n"）;
printf（"1.建立单链表"）;
printf（"2.取元素值"）;
printf（"3.查找\n"）;
printf（"4.插入"）;
printf（"5.删除"）;
printf（"6.显示\n"）;
printf（"7.删除大于mink且小于maxk的元素值"）;
printf（"8.就地升序排序\n"）;
printf（"9.就地逆置"）;
printf（"a.有序表插入"）;
printf（"q.退出\n"）;
printf（"\n请选择操作：
"）;
fflush（stdin）;
scanf（"%c",&choice）;
switch（choice）
{
case'1':
printf（"请输入单链表中结点个数：
"）;
scanf（"%d",&n）;
Create_L2（L,n）;
break;
case'2':
printf（"请输入元素位序：
"）;
scanf（"%d",&i）;
GetElem_L（L,i,e）;
printf（"元素值为：
%d\n",e）;
break;
case'3':
printf（"请输入要查找的元素：
"）;
scanf（"%d",&e）;
if（dlbcz（L,e））
printf（"查找成功！
"）;
else
printf（"查找失败。
"）;
break;
case'4':
printf（"请输入插入位置：
"）;
scanf（"%d",&i）;
printf（"请输入要插入的元素：
"）;
scanf（"%d",&e）;
if（ListInsert_L（L,i,e））
printf（"插入成功！
单链表为：
"）;
else
printf（"插入失败。
"）;
break;
case'5':
printf（"请输入删除位置：
"）;
scanf（"%d",&i）;
if（ListDelete_L（L,i,e））
printf（"删除成功！
"）;
else
printf（"删除失败。
\n"）;
break;
case'6':
printf（"\n单链表为：
"）;
xsList（L）;
break;
case'7':
printf（"请输入mink和maxk:
"）;
scanf（"%d,%d",&mink,&maxk）;
DelList（L,mink,maxk）;
break;
case'8':
sh_sort（L）;
break;
case'9':
nizhi（L）;
break;
case'a':
printf（"请输入在有序表中插入的元素值:
"）;
scanf（"%d",&e）;
yxcharu（L,e）;
break;
}
}
}
作业2.栈、队列、数组
非编程作业：
1．若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。
参考答案：
可能的出栈序列：
（14种）
dcbacdbabacdcbdaadcbcbadbdcaacdbbcdaacbdbcadabdcbadcabcd
不可能的出栈序列：
（10种）
dbcadbacdabcdacbdcabcabdcdabbdaccadbadbc
2．简要说明循环队列如何判断队满和队空？
参考答案：
当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环状的下一个位置）上”作为队列“满”状态的标志时，循环队列判断队满的条件为：
（rear+1）%MaxQsize==front；判断队空的条件为：
front==rear。
3．设A为n阶对称矩阵，采用压缩存储存放于一维数组F[n（n+1）/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式和存放下三角阵时任一矩阵元素aij（1≤i,j≤n）的地址计算公式。
参考答案：
存放上三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：
存放下三角阵时，任一矩阵元素aij（1≤i,j≤n）的地址计算公式为：
4．写出下面稀疏矩阵的三元组顺序表和十字链表表示。
参考答案：
编程作业
栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式：
a+b/c-（d*e+f）*g
输出其后缀表达式：
abc/+de*f+g*-
参考答案：
#include
#include
#include
#defineOVERFLOW-2
#defineOK1
#defineERROR0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefintStatus;
typedefcharSElemType;
typedefcharstring[80];
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;
return（OK）;
}
StatusClearStack（SqStack&S）
{S.base=（SElemType*）realloc（S.base,STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return（OK）;
}
voidDestroyStack（SqStack&S）
{S.stacksize=0;
if（S.base）free（S.base）;
S.base=S.top=NULL;
}
StatusStackEmpty（SqStackS）
{if（S.top==S.base）
returntrue;
else
returnfalse;
}
SElemTypeGetTop（SqStackS）
{SElemTypee;
if（S.top>S.base）
e=*（S.top-1）;
returne;
}
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;
returnOK;
}
StatusPop（SqStack&S,SElemType&e）
{if（S.top==S.base）//栈空
returnERROR;
e=*--S.top;
returnOK;
}
StatusInOP（SElemTypec）
{
charOperators[]={'+','-','*','/','（','）','#','\0'};
intlen=strlen（Operators）;
for（inti=0;iif（c==Operators[i]）
returntrue;
returnfalse;
}
SElemTypePrecede（SElemTypecurtop,SElemTypeinput）
{SElemTypeorder;
switch（input）{
case'+':
case'-':
switch（curtop）{
case'+':
case'-':
case'*':
case'/':
case'）':
order='>';break;
case'（':
case'#':
order='<';break;
}
break;
case'*':
case'/':
switch（curtop）{
case'+':
case'-':
case'（':
case'#':
order='<';break;
case'*':
case'/':
case'）':
order='>';break;
}
break;
case'（':
switch（curtop）{
case'+':
order='<';break;
case'-':
order='<';break;
case'*':
order='<';break;
case'/':
order='<';break;
case'（':
order='<';break;
case'#':
order='<';break;
}
break;
case'）':
switch（curtop）{
case'+':
order='>';break;
case'-':
order='>';break;
case'*':
order='>';break;
case'/':
order='>';break;
case'（':
order='=';break;
case'）':
order='>';break;
}
break;
case'#':
switch（curtop）{
case'+':
order='>';break;
case'-':
order='>';break;
case'*':
order='>';break;
case'/':
order='>';break;
case'）':
order='>';break;
case'#':
order='=';break;
}
break;
}
returnorder;
}
voidPass（stringSuffix,SElemTypech）
{*Suffix=ch;
}
voidTransfo
升级会员 