数据结构实验题答案.docx
《数据结构实验题答案.docx》由会员分享,可在线阅读,更多相关《数据结构实验题答案.docx(101页珍藏版)》请在冰点文库上搜索。
数据结构实验题答案
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
intInitList_Sq(SqList&L)
{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)returnERROR;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
//算法2.3,构造一个空的线性表L,该线性表预定义大小为LIST_INIT_SIZE
//请补全代码
}
intLoad_Sq(SqList&L)
{
//输出顺序表中的所有元素
inti;
if(L.length==0)printf("TheListisempty!
");//请填空
else
{
printf("TheListis:
");
for(i=0;i}
printf("\n");
returnOK;
}
intListInsert_Sq(SqList&L,inti,inte)
{int*newbase,*p,*q;
if((i<1)||(i>L.length+1))returnERROR;
if(L.length>=L.listsize)
{newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!
newbase)returnERROR;
L.elem=newbase;
L.listsize+=LISTINCREMENT;}
q=&(L.elem[i-1]);
for(p=&L.elem[L.length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
returnOK;
//算法2.4,在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1≤i≤L.length+1
//请补全代码
}
intListDelete_Sq(SqList&L,inti,int&e)
{int*p,*q;
if((i<1)||(i>L.length))returnERROR;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
returnOK;
//算法2.5,在顺序线性表L中删除第i个位置的元素,并用e返回其值
//i的合法值为1≤i≤L.length
//请补全代码
}
intmain()
{
SqListT;
inta,i;
ElemTypee,x;
if(InitList_Sq(T))//判断顺序表是否创建成功
{
printf("ASequenceListHasCreated.\n");
}
while
(1)
{
printf("1:
Insertelement\n2:
Deleteelement\n3:
Loadallelements\n0:
Exit\nPleasechoose:
\n");
scanf("%d",&a);
switch(a)
{
case1:
scanf("%d%d",&i,&x);
if(!
ListInsert_Sq(T,i,x))printf("InsertError!
\n");//判断i值是否合法,请填空
elseprintf("TheElement%disSuccessfullyInserted!
\n",x);
break;
case2:
scanf("%d",&i);
if(!
ListDelete_Sq(T,i,e))printf("DeleteError!
\n");//判断i值是否合法,请填空
elseprintf("TheElement%disSuccessfullyDeleted!
\n",e);
break;
case3:
Load_Sq(T);
break;
case0:
return1;
}
}
}
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{int*elem;
intlength;
intlistsize;
}List;
intInitList(List&L)
{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)returnERROR;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intLoad(List&L)
{inti;
if(L.length==0)printf("TheListisempty!
");
else{for(i=0;iprintf("%d",L.elem[i]);
}
printf("\n");
returnOK;
}
intMergeList(ListLa,ListLb,List&Lc)
{int*pa,*pb,*pc;
int*pa_last,*pb_last;
pa=La.elem;
pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!
Lc.elem)returnERROR;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while((pa<=pa_last)&&(pb<=pb_last))
{if(*pa<=*pb)*pc++=*pa++;
else*pc++=*pb++;
}
while(pa<=pa_last)*pc++=*pa++;
while(pb<=pb_last)*pc++=*pb++;
returnOK;
}
voidmain()
{ListLa,Lb,Lc;
InitList(La);
InitList(Lb);
inti,j;
scanf("%d",&La.length);
for(i=0;iscanf("%d",&La.elem[i]);
scanf("%d",&Lb.length);
for(j=0;jscanf("%d",&Lb.elem[j]);
MergeList(La,Lb,Lc);
printf("ListA:
");
Load(La);
printf("ListB:
");
Load(Lb);
printf("ListC:
");
Load(Lc);
}
#include
#include
#defineOK1
#defineERROR0
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#defineElemTypeint
typedefstruct
{int*elem;
intlength;
intlistsize;
}List;
intInitList(List&L)
{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!
L.elem)returnERROR;
L.length=0;
L.listsize=LIST_INIT_SIZE;
returnOK;
}
intLoad(List&L)
{inti;
if(L.length==0)printf("TheListisempty!
");
else{for(i=0;iprintf("%d",L.elem[i]);
}
printf("\n");
returnOK;
}
intMergeList(ListLa,List&Lc)
{int*pa,*pc,i,a;
int*pa_last;
pa=La.elem;
Lc.listsize=Lc.length=La.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));
if(!
Lc.elem)returnERROR;
pa_last=La.elem+La.length-1;
for(i=0;i{a=pa[La.length-i-1];
pa[La.length-i-1]=pa[i];
pa[i]=a;
}
while(pa<=pa_last)*pc++=*pa++;
returnOK;
}
voidmain()
{ListLa,Lc;
InitList(La);
inti,j;
scanf("%d",&La.length);
for(i=0;iscanf("%d",&La.elem[i]);
printf("TheListis:
");
Load(La);
MergeList(La,Lc);
printf("TheturnedListis:
");
Load(Lc);
}
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L(LinkList&L,intn){
//创建含有n个元素的单链表
LinkListp,q;
inti;
ElemTypee;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;//先建立一个带头结点的单链表
q=(LinkList)malloc(sizeof(LNode));
q=L;
for(i=0;i{scanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));//生成新结点
p->data=e;//请补全代码
q->next=p;
q=p;
q->next=NULL;
}
returnOK;
}
intLoadLink_L(LinkList&L){
//单链表遍历
LinkListp=L->next;
if(!
p)printf("TheListisempty!
");//请填空
else
{
printf("TheLinkListis:
");
while(p)//请填空
{
printf("%d",p->data);
p=p->next;//请填空
}
}
printf("\n");
returnOK;
}
intLinkInsert_L(LinkList&L,inti,ElemTypee)
{intj;
LNode*p,*s;
p=L;j=0;
while(p&&j{p=p->next;++j;}
if(!
p||j>i-1)returnERROR;
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
returnOK;
//算法2.9
//在带头结点的单链线性表L中第i个位置之前插入元素e
//请补全代码
}
intLinkDelete_L(LinkList&L,inti,ElemType&e)
{LNode*p,*q;
intj;
p=L;j=0;
while(p->next&&j{p=p->next;++j;}
if(!
(p->next)||j>i-1)returnERROR;
q=p->next;
p->next=q->next;
e=q->data;
free(q);
returnOK;
//算法2.10
//在带头结点的单链线性表L中,删除第i个元素,并用e返回其值
//请补全代码
}
intmain()
{
LinkListT;
inta,n,i;
ElemTypex,e;
printf("Pleaseinputtheinitsizeofthelinklist:
\n");
scanf("%d",&n);
printf("Pleaseinputthe%delementofthelinklist:
\n",n);
if(CreateLink_L(T,n))//判断链表是否创建成功,请填空
{
printf("ALinkListHasCreated.\n");
LoadLink_L(T);
}
while
(1)
{
printf("1:
Insertelement\n2:
Deleteelement\n3:
Loadallelements\n0:
Exit\nPleasechoose:
\n");
scanf("%d",&a);
switch(a)
{
case1:
scanf("%d%d",&i,&x);
if(!
LinkInsert_L(T,i,x))printf("InsertError!
\n");//判断i值是否合法,请填空
elseprintf("TheElement%disSuccessfullyInserted!
\n",x);
break;
case2:
scanf("%d",&i);
if(!
LinkDelete_L(T,i,e))printf("DeleteError!
\n");//判断i值是否合法,请填空
elseprintf("TheElement%disSuccessfullyDeleted!
\n",e);
break;
case3:
LoadLink_L(T);
break;
case0:
return1;
}
}
}
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L(LinkList&L,intn){
//创建含有n个元素的单链表
LinkListp,q;
inti;
ElemTypee;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;//先建立一个带头结点的单链表
q=(LinkList)malloc(sizeof(LNode));
q=L;
for(i=0;i{scanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));//生成新结点
p->data=e;//请补全代码
q->next=p;
q=p;
q->next=NULL;
}
returnOK;
}
intLoadLink_L(LinkList&L){
//单链表遍历
LinkListp=L->next;
if(!
p)printf("TheListisempty!
");//请填空
else
{
while(p)//请填空
{
printf("%d",p->data);
p=p->next;//请填空
}
}
printf("\n");
returnOK;
}
intMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)
{LNode*pa,*pb,*pc;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while(pa&&pb)
{if(pa->data<=pb->data)
{pc->next=pa;pc=pa;pa=pa->next;}
else{pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?
pa:
pb;
free(Lb);
returnOK;
}
voidmain()
{
LinkListLa,Lb,Lc;
intn,m;
scanf("%d",&n);
CreateLink_L(La,n);
scanf("%d",&m);
CreateLink_L(Lb,m);
printf("ListA:
");
LoadLink_L(La);
printf("ListB:
");
LoadLink_L(Lb);
MergeList_L(La,Lb,Lc);
printf("ListC:
");
LoadLink_L(Lc);
}
#include
#include
#defineERROR0
#defineOK1
#defineElemTypeint
typedefstructLNode
{
intdata;
structLNode*next;
}LNode,*LinkList;
intCreateLink_L(LinkList&L,intn){
//创建含有n个元素的单链表
LinkListp,q;
inti;
ElemTypee;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;//先建立一个带头结点的单链表
q=(LinkList)malloc(sizeof(LNode));
q=L;
for(i=0;i{scanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));//生成新结点
p->data=e;//请补全代码
q->next=p;
q=p;
q->next=NULL;
}
returnOK;
}
intLoadLink_L(LinkList&L){
//单链表遍历
LinkListp=L->next;
if(!
p)printf("TheListisempty!
");//请填空
else
{
while(p)//请填空
{
printf("%d",p->data);
p=p->next;//请填空
}
}
printf("\n");
returnOK;
}
intChange_L(LinkList&La,LinkList&Lc)
{LNode*p,*q,*b;
p=La->next;
Lc=(LinkList)malloc(sizeof(LNode));Lc=b=La;
b->next=NULL;
while(p)
{q=p;
p=p->next;
q->next=b->next;
b->next=q;
}
returnOK;
}
voidmain()
{
LinkListLa,Lc;
intn;
scanf("%d",&n);
CreateLink_L(La,n);
printf("TheListis:
");
LoadLink_L(La);
Change_L(La,Lc);
printf("TheturnedListis:
");
LoadLink_L(Lc);
}
#include
#include
#defineOK1
#defineERROR0
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
typedefintSElemType;//定义栈元素类型
typedefintStatus;//Status是函数的类型,其值是函数结果状态代码,如OK等
structSqStack
{
SElemType*base;//在栈构造之前和销毁之后,base的值为NULL
SElemType*top;//栈顶