数据结构教程课后答案

实验题 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;

if(q==NULL) {

return ERROR; } e=q->data;

p->next=q->next; free(q); return OK; //q 为要删除的元素节点//e 为删除节点的数据区域

}

}//

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"); // 初始化单链表 h

printf("(2)依次采用尾插法插入 a,b,c,d,e 元素\n");

printf("(9) 输出单链表 h ："); DispList_h(h); //输出单链表 h

printf("\n"); ListDelete_h(h,3,e);

printf("(10) 删除 h 的第 3 个元素 \n"); printf("(11) 输出单链表 h:"); DispList_h(h); printf("\n");

printf("(12) 释放单链表 h\n"); DestroyList_h(h); return 0;

InitList_h(h);

CreateList_h(h,&a[0],5); //依次采用尾插入法插入 printf("(3) 输出单链表 h ： "); DispList_h(h); printf("\n");

printf("(4) 单链表 h 的长度为： "); printf("%d",ListLength_h(h)); printf("\n"); if(ListEmpty_h(h))

{

printf("(5) 该单链表为空 \n");

}

else

{

printf("(5) 该单链表不为空 \n");

}

GetElem_h(h,3,e);

printf("(6) 单链表 h 的第三个元素

为： printf("%c",e); printf("\n");

printf("(7) 单链表 h 中 a 的位置

为：

printf("%d",LocateElem_h(h,'a')); printf("\n");

ListInsert_h(h,4,'f');

printf("(8) 在第 4 个元素位置上插入 a ，b ，c ，d ，e 元素

// 输出单链表 h

//输出单链表 h 的长度

// 判断单链表 h 是否为空

");

〃输出单链表h 的第3个元素

");

//输出元素’a'的位置

//在第4个元素位置插入’f 元素

f 元素\n");

//删除 h 的第 3 个元

素

//释放单链表 h

实验 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)

return 0;

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;

p->next=s;

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;

ElemType e; 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);

}