中南大学数据结构实验报告实验题目：（1）单链表的实现（2）栈和队列（3）二叉树的遍历（4）查找与排序学生姓名：代巍学生学号：0909121615指导老师：余腊生所在学院：信息科学与工程学院专业班级：信息安全1201班指导教师评定：签名：实验一单链表的实现一、实验目的了解线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在某种存储结构上如何实现这些基本运算。

在熟悉上述内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题二、实验内容用C/C++语言编写程序，完成以下功能：（1）运行时输入数据，创建一个单链表（2）可在单链表的任意位置插入新结点（3）可删除单链表的任意一个结点（4）在单链表中查找结点（5）输出单链表三、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）用一组地址任意的存储单元存放线性表中的数据元素。

以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点(表示数据元素或数据元素的映象)以“结点的序列”表示线性表称作线性链表（单链表）单链表是指数据接点是单向排列的。

一个单链表结点，其结构类型分为两部分：（1）、数据域：用来存储本身数据。

（2）、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。

1、单链表的查找对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。

2、单链表的插入因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。

假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。

(p-＞link=s;s-＞link=q)，这样就完成了插入操作。

3、单链表的删除删除运算思想方法删除运算是将表的第i个结点删去。

具体步骤：找到i-1 的存储位置p令p-next指向i 的直接后继结点释放结点i 的空间，将其归还给"存储池"。

四、源程序及注释#include <iostream.h>#include <stdlib.h>#include <malloc.h>#include <conio.h>#include <time.h>#define ElemType int// 链表类型typedef struct LNode{ElemType data;struct LNode *next;} LNode, *LinkList;int EmptyList(LinkList &L){if(L->next==NULL){return 0;}else{return 1;}}// 手动建立一个带头结点的线性链表Lvoid SCreateList_L(LinkList &L){ LinkList l,p;int i;ElemType d;l=(LinkList) malloc(sizeof(LNode));L=(LinkList) malloc(sizeof(LNode)); //生成头结点l=L;L->next=NULL;cout<<"请依次输入结点值，以0为结束："<<endl; for(i=1;i=1;){cin>>d;if(d!=0){p=(LinkList) malloc(sizeof(LNode)); //生成新结点p->data=d;p->next=l->next;l->next=p;l=l->next;}else break;}if(EmptyList(L)) cout<<"生成链表成功！！";else cout<<"链表为空，未生成！！";cin.get();cin.get();} //SCreate_L// 自动建立一个带头结点的线性链表Lvoid ZCreateList_L(LinkList &L,int n){ LinkList l,p;l=(LinkList) malloc(sizeof(LNode));L=(LinkList) malloc(sizeof(LNode)); //生成头结点l=L;L->next=NULL;srand((unsigned)time(NULL));for(int i=n;i>0;--i){p=(LinkList) malloc(sizeof(LNode)); //生成新结点p->data=(rand()%100+1);p->next=l->next;l->next=p;l=l->next;}cout<<"生成链表成功！！";cin.get();cin.get();} //ZCreate_L//建立一个带头结点的线性链表LinkList CreateList_L(){ char c;int n;LinkList L;cout<<"*********建立线性链表*********"<<endl;cout<<"1.手动建立"<<endl;cout<<"2.自动建立"<<endl;cout<<"******************************"<<endl;cin>>c;if(c=='1') {SCreateList_L(L);}else if(c=='2') {cout<<"请输入链表结点的个数:";cin>>n;ZCreateList_L(L,n);} else {cout<<"输入错误，请重新输入:"<<endl;}return L;cin.get();cin.get();}// 计算线性链表L中结点的个数int LengthList(LinkList &L){LinkList p=L->next;int i=0;while (p){++i;p=p->next;}return i;cin.get();cin.get();} //LengthList// 在线性链表L中第i个结点之前插入新的数据元素e void ListInsert_L(LinkList &L){int i;ElemType e;cout<<"第i个结点之前插入新的结点,请输入i:"; cin>>i;while(i<=0 || i>LengthList(L)){cout<<"位置错误，重新输入插入位置：" ;cin>>i;}LinkList p,s;p=L;int j=0;while(p && j<i-1) {p=p->next;++j;}if(!p || j>i-1) {cout<<"输入错误！！"; cin.get();cin.get();}else {cout<<"新结点的数据为：";cin>>e;s=(LinkList) malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;cout<<"插入成功！！";}cin.get();cin.get();} //ListInsert_L// 删除线性链表L中的第i个结点void ListDelete_L(LinkList &L){int i;ElemType e;cout<<"请输入要删除第i个结点的i值："; cin>>i;while(i<=0 || i>LengthList(L)){cout<<"位置错误，重新输入删除位置:";cin>>i;}LinkList p,q;p=L; int j=0;q=(LinkList) malloc(sizeof(LNode));while (p->next && j<i-1){p=p->next;++j;} //寻找第i个结点if(!(p->next) || j>i-1) {cout<<"删除位置不合理"; cin.get();cin.get();}else{q=p->next;p->next=q->next;e=q->data;cout<<"删除成功！！"<<endl<<"删除的结点值为："<<e; free(q); //删除并释放结点}cin.get();cin.get();} //ListDelete_L// 输出线性链表L中的所有数据元素void PrintList(LinkList &L){LinkList p=L->next;cout<<"所有数据如下所示："<<endl;while (p){cout<<p->data<<" ";p=p->next;}cin.get();cin.get();} //PrintListvoid SearchList(LinkList &L)//查找某一结点，显示其位置{int i=0;ElemType n;cout<<"请输入要找的数据：";cin>>n;if(L==NULL) {cout<<"链表为空！！";}LinkList p=L->next;while (p->data!=n && p->next!=NULL) {p=p->next; i=i+1;}if(p->data==n) {cout<<"找到了对应的结点，在链表的第"<<i+1<<"位上！";} else cout<<"链表上找不到相应的的结点!!";cin.get();cin.get();}void DestroyList(LinkList &L)//退出系统前，内部做结尾工作{while(L){LinkList p;p=L;L=L->next;free(p);}L=NULL;cout<<"线性链表L已销毁!!"<<endl;}//DestroyListint menu_select() //选择函数{char *m[7]={ "1.建立线性链表","2.某一结点前插入一个结点","3.删除一个结点","4.计算结点个数并输出","5.查找并显示某一结点位置","6.输出所有节点","0.退出系统"};int i;char c1;do{system("cls");/*清屏*/cout<<"\n\n=========链表的基本操作=========\n\n"; for(i=0;i<7;i++)cout<<m[i]<<endl;cout<<"\n==================================\n"; cout<<"请选择(1-6,0):";cin>>c1;}while(c1<'0'||c1>'6');return(c1-'0');}void main(){LinkList L=NULL;for( ; ; ){switch(menu_select()){case 1:L=CreateList_L();system("pause");break;case 2:if(L!=NULL) ListInsert_L(L); else {cout<<"链表为空，请先建链表！！"; cin.get();cin.get();break;}system("pause");break;case 3:if(L!=NULL) ListDelete_L(L); else {cout<<"链表为空，请先建链表！！"; cin.get();cin.get();break;}system("pause");break;case 4:if(L!=NULL) {int i=LengthList(L);cout<<"结点的个数为："<<i; cin.get();cin.get();}else {cout<<"链表为空，请先建链表！！";cin.get();cin.get();break;}system("pause");break;case 5:if(L!=NULL) SearchList(L);else {cout<<"链表为空，请先建链表！！";cin.get();cin.get();break;}system("pause");break;case 6:if(L!=NULL) PrintList(L);else {cout<<"链表为空，请先建链表！！";cin.get();cin.get();break;}system("pause");break;case 0:if(L!=NULL) DestroyList(L); exit(0);}}}五、实验结果实验二栈和队列一、实验目的了解栈和队列的特性。