数据结构教程(第二版)课后答案
实验题 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
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define NULL 0
typedef int Status;
typedef int ElemType;
typedef struct LNode {
ElemType data;
struct LNode *next;
}LNode,*LinkList;
Status InitList_h(LinkList &h) { //初始化线性表
h=(LinkList )malloc(sizeof(LNode)); //h指向头节点，头节点数据域为空
h->next=NULL;
return OK;
}// InitList_h
Status DispList_h(LinkList &h) { //输出线性表
LinkList p=h->next;
while(p!=NULL)
{
printf("%c",p->data);
p=p->next;
}
return OK;
} // DispList_h
Status CreateList_h(LinkList &h,ElemType a[],int n) { //尾插法建表
LinkList s,r;int i;
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;
return OK;
}// CreateList_h
Status ListLength_h(LinkList h) { //求线性表的长度
LinkList p=h;int n=0;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return(n);
}// ListLength_h
Status ListEmpty_h(LinkList h) { //判断单链表是否为空
return(h->next==NULL);
}// ListEmpty_h
Status DestroyList_h(LinkList &h) { //销毁线性表
LinkList p=h,q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=p->next;
}
free(p);
return OK;
}// DestroyList_h
Status GetElem_h(LinkList h, int i, ElemType &e) {
// h为带头节点的单链表的头指针。
// 当第i 个元素存在时，其值赋给e 并返回OK ，否则返回ERROR
int j=0;
LinkList p=h;
while(j
{
j++;p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
e=p->data;
return OK;
}
}// GetElem_h
Status ListInsert_h(LinkList &h, int i, ElemType e) { //插入数据元素
int j=0;
LinkList p=h,s;
/*
找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素
*/
while(j
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
s=(LinkList )malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
}// ListInsret_h
Status ListDelete_h(LinkList &h, int i, ElemType &e) { //删除数据元素
int j=0;
LinkList p=h,q;
while(j
{
j++;
p=p->next;
}
if(p==NULL)
{
return ERROR;
}
else
{
q=p->next; //q为要删除的元素节点
if(q==NULL)
{
return ERROR;
}
e=q->data; //e为删除节点的数据区域
p->next=q->next;
free(q);
return OK;
}
}// ListDelete_h
int LocateElem_h(LinkList h, ElemType e) { //按元素值查找元素
LinkList p=h->next;
int i=1;
while(p!=NULL&&p->data!=e)
{
p=p->next;i++;
}
//如果要插入的节点为头节点，则退出
if(p==NULL)
{
return ERROR;
}
else
{
return(i);
}
}// LocateElem_h
int main() {
ElemType e,a[5]={'a','b','c','d','e'};
LinkList h;
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
return 0;
}
实验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
typedef char ElemType;
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
}DLinkList;
void InitList(DLinkList *&h)
{
h=(DLinkList *)malloc(sizeof(DLinkList));
h->prior=h->next=NULL;
}
void DestroyList(DLinkList *&h)
{
DLinkList *p=h,*q=p->next;
while(q!=NULL)
{
free(p);
p=q;
q=q->next;
}
free(p);
}
int ListEmpty(DLinkList *h)
{
return(h->next==NULL);
}
int ListLength(DLinkList *h)
{
DLinkList *p=h;
int i=0;
while(p->next!=NULL)
{
i++;
p=p->next;
}
return(i);
}
void DispList(DLinkList *h)
{
DLinkList *p=h->next;
while(p!=NULL)
{
printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
int GetElem(DLinkList *h,int i,ElemType &e)
{
int j=0;
DLinkList *p=h;
while(j
{
i++;
p=p->next;
}
if(p==NULL)
else
e=p->data;
return 1;
}
int LocateElem(DLinkList *h,ElemType e)
{
int n=1;
DLinkList *p=h->next;
while(p!=NULL &&p->data!=e)
{
n++;
p=p->next;
}
if(p==NULL)
return 0;
else
return n;
}
int ListInsert(DLinkList *&h,int i,ElemType e)
{
int j=0;
DLinkList *p=h,*s;
while(j
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
s=(DLinkList *)malloc(sizeof(DLinkList));
s->data=e;
s->next=p->next;
if(p->next!=NULL)p->next->prior=s;
s->prior=p;
return 1;
}
}
int ListDelete(DLinkList *&h,int i,ElemType &e) {
int j=0;
DLinkList *p=h,*q;
while(j
{
j++;
p=p->next;
}
if(p==NULL)
return 0;
else
{
q=p->next;
if(q==NULL)
return 0;
p->next=q->next;
if(p->next!=NULL)p->next->prior=p;
free(q);
return 1;
}
}
//实现双链表各种基本运算的算法.cpp
void main()
{
DLinkList *h;
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);
}