数据结构教程课后答案

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

2、OK 1#define ERROR 0#define NULL 0typedef 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_hStatus DispList_h(LinkList &h) /输出

3、线性表LinkList p=h-next; while(p!=NULL)printf(%c,p-data);p=p-next; return OK; / DispList_hStatus CreateList_h(LinkList &h,ElemType a,int n) LinkList s,r;int i;h=(LinkList )malloc(sizeof(LNode); r=h;for(i=0;idata=ai;r-next=s;/尾插法建表r=s; r-next=NULL; return OK;/ CreateList_hStatus ListLength_h(LinkList h)

4、 LinkList p=h;int n=0; while(p-next!=NULL) /求线性表的长度n+; p=p-next; return(n);/ ListLength_hStatus 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_hStatus

5、GetElem_h(LinkList h, int i, ElemType &e) / h 为带头节点的单链表的头指针。/ 当第 i 个元素存在时，其值赋给 e 并返回 OK ，否则返回 ERRORint j=0;LinkList p=h;while(jnext;if(p=NULL)return ERROR;elsee=p-data;return OK;/ GetElem_hStatus ListInsert_h(LinkList &h, int i, ElemType e) /插入数据元素int j=0;LinkList p=h,s;/*i=2 时，表找到插入节点的上一个元素，如果是头节点则

6、退出，当 i=1 时表示头节点， 示第一个元素*/while(jnext;if(p=NULL)return ERROR;elses=(LinkList )malloc(sizeof(LNode); s-data=e;s-next=p-next;p-next=s;return OK;/ ListInsret_hStatus ListDelete_h(LinkList &h, int i, ElemType &e) / 删除数据元素int j=0;LinkList p=h,q; while(jnext;if(p=NULL)return ERROR;else/查找删除元素的前一个节点q=p-next

7、; if(q=NULL) return ERROR; e=q-data; p-next=q-next; free(q); return OK;/q 为要删除的元素节点/e 为删除节点的数据区域/ ListDelete_hint 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

8、() ElemType e,a5=a,b,c,d,e;LinkList h;printf(1) 初始化单链表 hn);InitList_h(h);/ 初始化单链表 hprintf(2)依次采用尾插法插入 a,b,c,d,e元素n);CreateList_h(h,&a0,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);elseprin

9、tf(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 个元素/输

10、出单链表 h/释放单链表hprintf(9) 输出单链表 h：);DispList_h(h);/输出单链表 hprintf(n);ListDelete_h(h,3,e);printf(10) 删除 h 的第 3 个元素 n); printf(11) 输出单链表 h:); DispList_h(h);printf(n);printf(12) 释放单链表 hn);DestroyList_h(h);return 0;个主程序完成实验 2.3 编编写一个程序 , 实现双链表的各种基本运算 , 并在此基础上设计 如下功能 .(1) 初始化双链表 h；(2) 依次采用尾插法插入 a,b,c,d,e 元素；

11、(3) 输出双链表 h；(4) 输出双链表 h 的长度；(5) 判断双链表 h 是否为空；(6) 输出双链表 h 的第 3 个元素；(7) 输出元素 a 的位置；(8) 在第 4 个元素位置上插入 f 元素；(9) 输出双链表 h；(10) 删除h的第3个元素；(11) 输出双链表 h；(12) 释放双链表 h；#include #includetypedef char ElemType;typedef struct DNodeElemType data;struct DNode *prior;struct DNode *next;DLinkList;void InitList(DLinkLi

12、st *&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;retu

13、rn(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(jnext;if(p=NULL)return 0;else e=p-data;return 1;int LocateElem(DLinkList *h,ElemType e) int n=1;DLinkList *p=h-next; whil

14、e(p!=NULL &p-data!=e) n+;p=p-next; if(p=NULL) return 0;elsereturn n;int ListInsert(DLinkList *&h,int i,ElemType e) int j=0;DLinkList *p=h,*s;while(jnext;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

15、1;int ListDelete(DLinkList *&h,int i,ElemType &e)int j=0;DLinkList *p=h,*q;while(jnext;if(p=NULL)return 0;elseq=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 的长度 =%dn,ListLength(h);printf(5)双链表 h 为sn,(ListEmpty(h)?空:非空);GetElem(h,3,e);printf(6) 双链表