数据结构上机报告--链表的应用.pdf
算法与数据结构算法与数据结构上机报告上机报告姓名：姓名：班级：班级：学号：学号：实验一实验一 链表的操作链表的操作一 实验名称实验名称：链表的基本操作二 实验目的实验目的：通过该实验，了解线性表的链式存储结构,熟悉链式存储结构的存储特点，掌握利用链式存储的线性表进行插入和删除基本算法。三 实验原理实验原理：线性表有各种存储方式，链表是用链式存储方式存放的线性表，它是用一组地址不一定连续的单元存放一组连续的数据， 数据之间的相邻关系是通过数据节点中指针域的值加以体现的。对于线性表 SLSL=(a1,a2,ai-1,ai,an);在第 i 个位置插入一个数据元素 x 后，线性表 SL 就变为SL=(a1,a2,ai-1, x,ai,an);要使得链表中的数据和线性表中的数据保持一致， 就要修改数据节点中指针域的值，在 p 指针所指节点后插入一个新数据节点 S 的操作为: s=(LinkList *)malloc(sizeof(LinkList); s=(LinkList *)malloc(sizeof(LinkList); s-data=x; s-data=x; s-next=p-next; s-next=p-next; p-next=s; p-next=s;同样，对于线性表 SL，在第 i 个位置删除一个数据元素后，线性表 SL 就变为SL=(a1,a2,ai-1,ai+1,an);要使得链表中的数据和线性表中的数据保持一致， 删除 p 指针所指节点后面的数据节点的操作为： s=p-next; s=p-next; p-next=p-next-next; p-next=p-next-next; free(s); free(s);四 实验内容实验内容：实验题实验题 2.22.2编写一个程序 algo2-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为 char） ，并在此基础上设计一个程序exp2-2 .cpp ，完成如下功能：(1) 初始化单链表 h(7) 输出元素 a 的位置(2) 采用尾插法依次插入 a,b,c,d,e(8) 在第 4 个元素位置上插入 f 元素元素(9) 输出单链表 h(3) 输出单链表 h(10) 删除 L 的第 3 个元素(4) 输出单链表 h 长度(11) 输出单链表 h(5) 判断单链表 h 是否为空(12) 释放单链表 h(6) 输出单链表 h 的第 3 个元素五算法步骤算法步骤：实验题实验题 2.32.3 编写一个程序 algo2-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为 char） ，并在此基础上设计一个程序 exp2-3.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)删除 L 的第 3 个元素(11)输出双链表 h(12)释放双链表 h六程序源代码：实验题 2.2/文件名:algo2-2.cpp#include #include typedef char ElemType;typedef struct LNode ElemType data; struct LNode *next;LinkList;void InitList(LinkList *&L) /初始化线性表L=(LinkList *)malloc(sizeof(LinkList);L-next=NULL;void DestroyList(LinkList *&L)LinkList *p=L,*q=p-next;while(q!=NULL)free(p);p=q;q=p-next;free(p);bool ListEmpty(LinkList *L) /判断线性表是否为空return(L-next=NULL);int ListLength(LinkList *L)int n=0;LinkList *p=L;while(p-next!=NULL)n+;p=p-next;return(n);void DispList(LinkList *L) /输出线性表LinkList *p=L-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);bool GetElem(LinkList *L,int i,ElemType &e) /求线性表中某个数据元素值int j=0;LinkList *p=L;while(jnext;if(p=NULL) return false;elsee=p-data;return true;int LocateElem(LinkList *L,ElemType e) /按元素值查找int i=1;LinkList *p=L-next;while(p!=NULL&p-data!=e)p=p-next;i+;if (p=NULL) return (0);else return (i);bool ListInsert(LinkList *&L,int i,ElemType e) /插入数据元素int j=0;LinkList *p=L,*s;while(jnext;if(p=NULL) return false;elses=(LinkList *)malloc(sizeof(LinkList);s-data=e;s-next=p-next;p-next=s;return true;bool ListDelete(LinkList *&L,int i,ElemType &e) /删除数据元素int j=0;LinkList *p=L,*q;while(jnext;if(p=NULL) return false;elseq=p-next;if(q=NULL) return false;e=q-data;p-next=q-next;free(q);return true; /文件名:exp2-2.cpp#include #include typedef char ElemType;typedef struct LNode /定义单链表结点类型ElemType data; struct LNode *next; LinkList;extern void InitList(LinkList *&L);extern void DestroyList(LinkList *&L);extern bool ListEmpty(LinkList *L);extern int ListLength(LinkList *L);extern void DispList(LinkList *L);extern bool GetElem(LinkList *L,int i,ElemType &e);extern int LocateElem(LinkList *L,ElemType e);extern bool ListInsert(LinkList *&L,int i,ElemType e);extern bool ListDelete(LinkList *&L,int i,ElemType &e);void main()LinkList *h;ElemType e;printf(单链表的基本运算如下所示:n);printf(1)初始化单链表 hn);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)单链表 h 的第 3 个元素=%cn,e);printf(7)元素 a 的位置=%dn,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(12)释放单链表 hn);DestroyList(h);实验题 2.3/文件名:algo2-3.cpp#include #include typedef char ElemType;typedef struct DNode/定义双链表结点类型ElemType data;struct DNode *prior;struct DNode *next; DLinkList;void InitList(DLinkList *&L)/初始化L=(DLinkList *)malloc(sizeof(DLinkList);L-prior=L-next=NULL;void DestroyList(DLinkList *&L)DLinkList *p=L,*q=p-next;while (q!=NULL)free(p);p=q;q=p-next;free(p);bool ListEmpty(DLinkList *L)/判线性表是否为空表return(L-next=NULL);int ListLength(DLinkList *L)/求线性表的长度DLinkList *p=L;int i=0;while (p-next!=NULL)i+;p=p-next;return(i);void DispList(DLinkList *L) /输出线性表DLinkList *p=L-next;while (p!=NULL)printf(%c ,p-data);p=p-next;printf(n);bool GetElem(DLinkList *L,int i,ElemType &e) /求线性表中某个数据元素值int j=0;DLinkList *p=L;while (jnext;if (p=NULL)return false;elsee=p-data;return true;int LocateElem(DLinkList *L,ElemType e)/按元素值查找int n=1;DLinkList *p=L-next;while (p!=NULL & p-data!=e)n+;p=p-next;if (p=NULL)return(0);elsereturn(n);bool ListInsert(DLinkList *&L,int i,ElemType e)/插入数据元素int j=0;DLinkList *p=L,*s;while (jnext;if (p=NULL)return false;elses=(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 true;bool ListDelete(DLinkList *&L,int i,ElemType &e) /删除数据元素int j=0;DLinkList *p=L,*q;while (jnext;if (p=NULL)return false;elseq=p-next;if (q=NULL) return false;e=q-data;p-next=q-next;if (p-next!=NULL) p-next-prior=p;free(q);return true;void Sort(DLinkList *&head) /双链表元素排序DLinkList *p=head-next,*q,*r;if (p!=NULL)r=p-next;p-next=NULL;p=r;while (p!=NULL)r=p-next;q=head;while (q-next!=NULL & q-next-datadata)q=q-next;p-next=q-next;if (q-next!=NULL) q-next-prior=p;q-next=p;p-prior=q;p=r;/文件名:exp2-3.cpp#include #include typedef char ElemType;typedef struct DNode /定义双链表结点类型ElemType data;struct DNode *prior;struct DNode *next; DLinkList;extern void InitList(DLinkList *&L);extern void DestroyList(DLinkList *&L);extern bool ListEmpty(DLinkList *L);extern int ListLength(DLinkList *L);extern void DispList(DLinkList *L);extern bool GetElem(DLinkList *L,int i,ElemType &e);extern int LocateElem(DLinkList *L,ElemType e);extern bool ListInsert(DLinkList *&L,int i,ElemType e);extern bool ListDelete(DLinkList *&L,int i,ElemType &e);void main()DLinkList *h;ElemType e;printf(双链表的基本运算如下所示:n);printf(1)初始化双链表 hn);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)双链表 h 的第 3 个元素=%cn,e);printf(7)元素 a 的位置=%dn,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(12)释放双链表 hn);DestroyList(h); 六运行结果及分析运行结果及分析：实验 2.2实验 2.3
