数据结构教程(第二版)课后答案
- 格式：doc
- 大小：61.00 KB
- 文档页数：10
- 1 - 实验题 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); - 2 -
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); - 3 -
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; - 4 -
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); - 5 -
} }// 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; } - 6 -
实验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); }
