链表程序设计训练_实习报告

1、链表程序设计训练一 实验目的l 使学生掌握Visual C+ 6.0环境下C+语言程序调试与排错方法；l 使学生掌握单向链表结构并实现插入、删除、建表等基本功能操作；l 使学生掌握应单向循环链表结构并实现插入、删除、建表等基本功能操作；l 使学生掌握双向链表结构并实现插入、删除、建表等基本功能操作；l 使学生熟悉应用链表解决实际问题；二 实验环境l 所需硬件环境为微机；l 所需软件环境为Microsoft Visual C+ 6.0或Code:Blocks ；三 实验内容（二）、设计单向循环链表并实现其构建(包括正序及逆序建表)、插入、删除、销毁等基本操作算法#include<iostr

2、eam.h>#include<stdlib.h>#define OVERFLOW -2#define OK 1#define FAILURE 0#define TRUE 1#define FALSE 0#define ERROR -1typedef int ElemType;typedef int Status;typedef struct Node ElemType e; struct Node *next;ListNode,*list;Status DestroyList_Sl(list L)/销毁 list p; if(!L) return ERROR;/*单向线性链表

3、不存在*/ do/*释放单向线性链表空间*/ p=L->next; L->next=p->next; delete p; while(L); return OK;Status ListDelete_Sl(list L) list p; if(!L)return ERROR;/*单向线性链表结点L不存在*/ p=L->next; L->next=p->next; delete p; return OK;list set(int n)/*建立链表*/ list L,p,q; L=new ListNode; L->e=0; L->next=NULL;

4、p=L; cout<<"正序的数字:" for(int i=0;i<n;i+) if(q=new ListNode) ElemType t; cin>>t; q->e=t; q->next=NULL; p->next=q; p=p->next; else while(p) q=p; p=NULL; delete p; p=q->next; if(i=n-1) p->next=L->next; return L;list set2(int n) list L2,p,q; if(L2=new ListNod

5、e) L2->next=NULL; L2->e=0; cout<<"逆序数字:" for(int i=0;i<n;i+) int t; cin>>t; if(q=new ListNode) q->e=t;q->next=NULL;q->next=L2->next;L2->next=q; else p=L2; while(p) L2=p;delete L2; p=p->next; p=L2->next; while(p->next) p=p->next; p->next=L2

6、; return L2;int main() list L,p,q,L2; int n,ListDelete_number; cout<<"个数："<<endl; cin>>n; L=set(n); p=L->next; int i=0; while(p) cout<<p->e<<'t' p=p->next; i+; if(i=n) break; /单链正序测试 cout<<endl; L2=set2(n); p=L2->next; while(p!=L2) co

7、ut<<p->e<<'t' p=p->next; cout<<endl; ListDelete_number=ListDelete_Sl(L); cout<<"ListDelete_number="<<ListDelete_number<<endl; p=L->next; i=0; cout<<"剩下的：" while(p) cout<<p->e<<'t' p=p->next; i+;

8、if(i=n-1) break; /删除结点及测试 DestroyList_Sl(L);return 0;（三）、设计双向链表并实现其构建(包括正序及逆序建表)、插入、删除、销毁等基本操作算法#include<iostream.h>#include<stdlib.h>#define OVERFLOW -2#define OK 1#define FAILURE 0#define TRUE 1#define FALSE 0#define ERROR -1typedef int ElemType;typedef int Status;typedef struct Node E

9、lemType e; struct Node *next; struct Node *last;ListNode,*list;Status DestroyList_Sl(list L)/销毁 list p; if(!L) return ERROR;/*单向线性链表不存在*/ do/*释放单向线性链表空间*/ p=L->next; L->next=p->next; delete p; while(L); return OK;Status ListDelete_Sl(list L) list p; if(!L)return ERROR;/*单向线性链表结点L不存在*/ p=L-&

10、gt;next; L->next=p->next; delete p; return OK;list set(int n)/*建立链表*/ list L,p,q; L=new ListNode; L->e=0; L->next=NULL; p=L; cout<<"正序的数字:" for(int i=0;i<n;i+) if(q=new ListNode) ElemType t; cin>>t; q->e=t; q->next=NULL; p->next=q; q->last=p; p=p->

11、next; else while(p) q=p; p=NULL; delete p; p=q->next; if(i=n-1) q=L->next; p->next=q; q->last=p; return L;list set2(int n) list L2,p,q; if(L2=new ListNode) L2->next=NULL; L2->e=0; cout<<"逆序数字:" for(int i=0;i<n;i+) int t; cin>>t; if(q=new ListNode) q->e=t

12、;q->next=NULL;q->next=L2->next;L2->next=q; else p=L2; while(p) L2=p;delete L2; p=p->next; p=L2->next; while(p->next) p=p->next; p->next=L2; return L2;int main() list L,p,q,L2; int n,ListDelete_number; cout<<"个数："<<endl; cin>>n; L=set(n); p=L->

13、;next; int i=0; while(p) cout<<p->e<<'t' p=p->next; i+; if(i=n) break; /单链正序测试 cout<<endl; cout<<"反向:" i=0; p=L->next; while(p) p=p->last; cout<<p->e<<'t' i+; if(i=n) break; cout<<endl; L2=set2(n); p=L2->next; whil

14、e(p!=L2) cout<<p->e<<'t' p=p->next; cout<<endl; ListDelete_number=ListDelete_Sl(L); cout<<"ListDelete_number="<<ListDelete_number<<endl; p=L->next; i=0; cout<<"剩下的：" while(p) cout<<p->e<<'t' p=p->

15、;next; i+; if(i=n-1) break; /删除结点及测试 DestroyList_Sl(L);return 0;（四）、分析并使用循环链表解决“猴子选大王”问题#include<iostream.h>typedef struct Node int e; struct Node *next; struct Node *last;ListNode,*list;list set(int n)/*建立链表*/ list L,p,q; L=new ListNode; L->e=0; L->next=NULL; p=L; for(int i=0;i<n;i+)

16、 if(q=new ListNode) q->e=i+1; q->next=NULL; p->next=q; q->last=p; p=p->next; else while(p) q=p; p=NULL; delete p; p=q->next; if(i=n-1) q=L->next; p->next=q; p->next=L; L->last=p; return L;int main() list L,p,q,t; int n,m,i=0; cout<<"总个数："<<endl; ci

17、n>>n; cout<<"跳下报的数字:"<<endl; cin>>m; L=set(n); p=L; /*while(p) p=p->next; cout<<p->e<<'t' i+; if(i=n+1) break; */ while(!(L=p->next)&&(p=L->next) p=p->next; if(p->e>0) i+; if(i%m=0) q=p->next; t=p->last; t->next=q; q->last=t; cout<<"delete "<<p->e<<endl; delete p; p=t; cout<<"猴王："<<p->e;return 0;四 实验分析及问题思考1、分析双向循环链表与单向链表、循环链表、双向链表间的差异；循环链表是在单向链表的基础