数据结构教程第二版课后答案.docx
《数据结构教程第二版课后答案.docx》由会员分享，可在线阅读，更多相关《数据结构教程第二版课后答案.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构教程第二版课后答案
实验题2.2编写一个程序algo2-2.cpp，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能。
（1）初始化单链表h；
（2）依次采用尾插法插入a,b,c,d,e元素；
（3）输出单链表h；
（4）输出单链表h长度；
（5）判断单链表h是否为空；
（6）输出单链表h的第3个元素；
（7）输出元素a的位置；
（8）在第4个元素位置上插入‘f’元素；
（9）输出单链表h；
（10）删除h的第3个元素；
（11）输出单链表h；
（12）释放单链表h；
程序：
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineNULL0
typedefintStatus;
typedefintElemType;
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
StatusInitList_h（LinkList&h）{//初始化线性表
h=（LinkList）malloc（sizeof（LNode））;//h指向头节点，头节点数据域为空
h->next=NULL;
returnOK;
}//InitList_h
StatusDispList_h（LinkList&h）{//输出线性表
LinkListp=h->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
returnOK;
}//DispList_h
StatusCreateList_h（LinkList&h,ElemTypea[],intn）{//尾插法建表
LinkLists,r;inti;
h=（LinkList）malloc（sizeof（LNode））;
r=h;
for（i=0;i{
s=（LinkList）malloc（sizeof（LNode））;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
returnOK;
}//CreateList_h
StatusListLength_h（LinkListh）{//求线性表的长度
LinkListp=h;intn=0;
while（p->next!
=NULL）
{
n++;
p=p->next;
}
return（n）;
}//ListLength_h
StatusListEmpty_h（LinkListh）{//判断单链表是否为空
return（h->next==NULL）;
}//ListEmpty_h
StatusDestroyList_h（LinkList&h）{//销毁线性表
LinkListp=h,q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
returnOK;
}//DestroyList_h
StatusGetElem_h（LinkListh,inti,ElemType&e）{
//h为带头节点的单链表的头指针。
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
intj=0;
LinkListp=h;
while（j=NULL）
{
j++;p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
e=p->data;
returnOK;
}
}//GetElem_h
StatusListInsert_h（LinkList&h,inti,ElemTypee）{//插入数据元素
intj=0;
LinkListp=h,s;
/*
找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素
*/
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
s=（LinkList）malloc（sizeof（LNode））;
s->data=e;
s->next=p->next;
p->next=s;
returnOK;
}
}//ListInsret_h
StatusListDelete_h（LinkList&h,inti,ElemType&e）{//删除数据元素
intj=0;
LinkListp=h,q;
while（j=NULL）//查找删除元素的前一个节点
{
j++;
p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
q=p->next;//q为要删除的元素节点
if（q==NULL）
{
returnERROR;
}
e=q->data;//e为删除节点的数据区域
p->next=q->next;
free（q）;
returnOK;
}
}//ListDelete_h
intLocateElem_h（LinkListh,ElemTypee）{//按元素值查找元素
LinkListp=h->next;
inti=1;
while（p!
=NULL&&p->data!
=e）
{
p=p->next;i++;
}
//如果要插入的节点为头节点，则退出
if（p==NULL）
{
returnERROR;
}
else
{
return（i）;
}
}//LocateElem_h
intmain（）{
ElemTypee,a[5]={'a','b','c','d','e'};
LinkListh;
printf（"
（1）初始化单链表h\n"）;
InitList_h（h）;//初始化单链表h
printf（"
（2）依次采用尾插法插入a,b,c,d,e元素\n"）;
CreateList_h（h,&a[0],5）;//依次采用尾插入法插入a，b，c，d，e元素
printf（"（3）输出单链表h：
"）;
DispList_h（h）;//输出单链表h
printf（"\n"）;
printf（"（4）单链表h的长度为：
"）;
printf（"%d",ListLength_h（h））;//输出单链表h的长度
printf（"\n"）;
if（ListEmpty_h（h））
{
printf（"（5）该单链表为空\n"）;
}
else
{
printf（"（5）该单链表不为空\n"）;//判断单链表h是否为空
}
GetElem_h（h,3,e）;
printf（"（6）单链表h的第三个元素为：
"）;
printf（"%c",e）;printf（"\n"）;//输出单链表h的第3个元素
printf（"（7）单链表h中a的位置为：
"）;
printf（"%d",LocateElem_h（h,'a'））;//输出元素'a'的位置
printf（"\n"）;
ListInsert_h（h,4,'f'）;//在第4个元素位置插入'f'元素
printf（"（8）在第4个元素位置上插入f元素\n"）;
printf（"（9）输出单链表h：
"）;
DispList_h（h）;//输出单链表h
printf（"\n"）;
ListDelete_h（h,3,e）;//删除h的第3个元素
printf（"（10）删除h的第3个元素\n"）;
printf（"（11）输出单链表h:
"）;//输出单链表h
DispList_h（h）;
printf（"\n"）;
printf（"（12）释放单链表h\n"）;
DestroyList_h（h）;//释放单链表h
return0;
}
实验2.3编编写一个程序,实现双链表的各种基本运算,并在此基础上设计一个主程序完成如下功能.
（1）初始化双链表h；
（2）依次采用尾插法插入a,b,c,d,e元素；
（3）输出双链表h；
（4）输出双链表h的长度；
（5）判断双链表h是否为空；
（6）输出双链表h的第3个元素；
（7）输出元素a的位置；
（8）在第4个元素位置上插入f元素；
（9）输出双链表h；
（10）删除h的第3个元素；
（11）输出双链表h；
（12）释放双链表h；
#include
#include
typedefcharElemType;
typedefstructDNode
{
ElemTypedata;
structDNode*prior;
structDNode*next;
}DLinkList;
voidInitList（DLinkList*&h）
{
h=（DLinkList*）malloc（sizeof（DLinkList））;
h->prior=h->next=NULL;
}
voidDestroyList（DLinkList*&h）
{
DLinkList*p=h,*q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=q->next;
}
free（p）;
}
intListEmpty（DLinkList*h）
{
return（h->next==NULL）;
}
intListLength（DLinkList*h）
{
DLinkList*p=h;
inti=0;
while（p->next!
=NULL）
{
i++;
p=p->next;
}
return（i）;
}
voidDispList（DLinkList*h）
{
DLinkList*p=h->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
printf（"\n"）;
}
intGetElem（DLinkList*h,inti,ElemType&e）
{
intj=0;
DLinkList*p=h;
while（j=NULL）
{
i++;
p=p->next;
}
if（p==NULL）
return0;
else
e=p->data;
return1;
}
intLocateElem（DLinkList*h,ElemTypee）
{
intn=1;
DLinkList*p=h->next;
while（p!
=NULL&&p->data!
=e）
{
n++;
p=p->next;
}
if（p==NULL）
return0;
else
returnn;
}
intListInsert（DLinkList*&h,inti,ElemTypee）
{
intj=0;
DLinkList*p=h,*s;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）
return0;
else
{
s=（DLinkList*）malloc（sizeof（DLinkList））;
s->data=e;
s->next=p->next;
if（p->next!
=NULL）p->next->prior=s;
s->prior=p;
p->next=s;
return1;
}
}
intListDelete（DLinkList*&h,inti,ElemType&e）
{
intj=0;
DLinkList*p=h,*q;
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）
return0;
else
{
q=p->next;
if（q==NULL）
return0;
p->next=q->next;
if（p->next!
=NULL）p->next->prior=p;
free（q）;
return1;
}
}
//实现双链表各种基本运算的算法.cpp
voidmain（）
{
DLinkList*h;
ElemTypee;
printf（"
（1）初始化双链表h:
\n"）;
InitList（h）;
printf（"
（2）依次采用尾插法插入a,b,c,d,e元素\n"）;
ListInsert（h,1,'a'）;
ListInsert（h,2,'b'）;
ListInsert（h,3,'c'）;
ListInsert（h,4,'d'）;
ListInsert（h,5,'e'）;
printf（"（3）输出双链表h:
"）;
DispList（h）;
printf（"（4）双链表h的长度=%d\n",ListLength（h））;
printf（"（5）双链表h为%s\n",（ListEmpty（h）?
"空":
"非空"））;
GetElem（h,3,e）;
printf（"（6）双链表h的第3个元素=%c\n",e）;
printf（"（7）元素a的位置=%d\n",LocateElem（h,'a'））;
printf（"（8）在第4个元素位置上插入f元素\n"）;
ListInsert（h,4,'f'）;
printf（"（9）输出双链表h:
"）;
DispList（h）;
printf（"（10）删除h的第3个元素\n"）;
ListDelete（h,3,e）;
printf（"（11）输出双链表h:
"）;
DispList（h）;
printf（"释放双链表h:
\n"）;
DestroyList（h）;
}
升级会员 