《中南大学数据结构实验报告》由会员分享，可在线阅读，更多相关《中南大学数据结构实验报告（33页珍藏版）》请在金锄头文库上搜索。
1、-中南大学数据构造实验报告实验题目：1单链表的实现2栈和队列3二叉树的遍历4查找与排序学生：代巍学生*： 0909121615 指导教师：余腊生所在学院：信息科学与工程学院专业班级：信息平安1201班指导教师评定：签名：实验一单链表的实现一、实验目的了解线性表的逻辑构造和各种存储表示方法，以及定义在逻辑构造上的各种根本运算及其在*种存储构造上如何实现这些根本运算。在熟悉上述容的根底上，能够针对具体应用问题的要求和性质，选择适宜的存储构造设计出相应的有效算法，解决与线性表相关的实际问题二、实验容用C/C+语言编写程序，完成以下功能：1运行时输入数据，创立一个单链表2可在单链表的任意位置插入新结点
2、3可删除单链表的任意一个结点4在单链表中查找结点5输出单链表三、程序设计的根本思想，原理和算法描述：包括程序的构造，数据构造，输入/输出设计，符号名说明等用一组地址任意的存储单元存放线性表中的数据元素。以元素(数据元素的映象)+指针(指示后继元素存储位置)=结点(表示数据元素或数据元素的映象)以“结点的序列表示线性表称作线性链表单链表单链表是指数据接点是单向排列的。一个单链表结点，其构造类型分为两局部：1、数据域：用来存储本身数据。2、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。1、单链表的查找对单链表进展查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要
3、查好的值，假设是返回该结点的指针，否则返回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-ne*t指向i的直接后继结点释放结点i的空间，将
4、其归还给存储池。四、源程序及注释#include #include #include #include #include #define ElemType int/ 链表类型typedef struct LNodeElemType data;struct LNode *ne*t; LNode, *LinkList;int EmptyList(LinkList &L)if(L-ne*t=NULL)return 0;elsereturn 1;/ 手动建立一个带头结点的线性链表Lvoid SCreateList_L(LinkList &L) LinkList l,p;int i;ElemType d
5、;l=(LinkList) malloc(sizeof(LNode);L=(LinkList) malloc(sizeof(LNode); /生成头结点l=L; L-ne*t=NULL;cout请依次输入结点值，以0为完毕：d; if(d!=0)p=(LinkList) malloc(sizeof(LNode); /生成新结点p-data=d;p-ne*t=l-ne*t;l-ne*t=p;l=l-ne*t; else break;if(EmptyList(L) cout生成链表成功！;else coutne*t=NULL;srand(unsigned)time(NULL);for(int i=
6、n;i0;-i)p=(LinkList) malloc(sizeof(LNode); /生成新结点p-data=(rand()%100+1);p-ne*t=l-ne*t;l-ne*t=p;l=l-ne*t; cout生成链表成功！;cin.get();cin.get(); /ZCreate_L/建立一个带头结点的线性链表LinkList CreateList_L()char c;int n;LinkList L;cout*建立线性链表*endl;cout1.手动建立endl;cout2.自动建立endl;cout*c;if(c=1) SCreateList_L(L);else if(c=2)
7、coutn;ZCreateList_L(L,n);else cout输入错误，请重新输入:ne*t;int i=0;while (p)+i;p=p-ne*t;return i;cin.get();cin.get(); /LengthList/ 在线性链表L中第i个结点之前插入新的数据元素evoid ListInsert_L(LinkList &L)int i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,s; p=L;int j=0;while(p & jne*t;+j;if(!p | ji-1) cout输入错误！;cin.get
8、();cin.get();else coute;s=(LinkList) malloc(sizeof(LNode);s-data=e;s-ne*t=p-ne*t;p-ne*t=s;cout插入成功！;cin.get();cin.get(); /ListInsert_L/ 删除线性链表L中的第i个结点void ListDelete_L(LinkList &L)int i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,q; p=L; int j=0;q=(LinkList) malloc(sizeof(LNode);while (p-n
9、e*t & jne*t;+j; /寻找第i个结点if(!(p-ne*t) | ji-1) coutne*t;p-ne*t=q-ne*t;e=q-data;cout删除成功！endl删除的结点值为：ne*t;cout所有数据如下所示：endl;while (p)coutdatane*t;cin.get();cin.get(); /PrintListvoid SearchList(LinkList &L)/查找*一结点，显示其位置int i=0;ElemType n;coutn;if(L=NULL) coutne*t;while (p-data!=n & p-ne*t!=NULL) p=p-ne*
10、t; i=i+1;if(p-data=n) cout找到了对应的结点，在链表的第i+1位上！;else coutne*t;free(p);L=NULL;cout线性链表L已销毁!endl;/DestroyListint menu_select() /选择函数char *m7= 1.建立线性链表,2.*一结点前插入一个结点,3.删除一个结点,4.计算结点个数并输出,5.查找并显示*一结点位置,6.输出所有节点,0.退出系统;int i;char c1;dosystem(cls);/*清屏*/coutnn=链表的根本操作=nn;for(i=0;i7;i+)coutmiendl;coutn=n;coutc1;while(c16);return(c1-0);void main()LinkList L=NULL;for( ; ; )switch(menu_select()case 1:L=Create
