中南大学数据结构实验报告.docx

《中南大学数据结构实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、中南大学数据结构实验报告实验题目：（1）单链表的实现（2）栈和队列（3）二叉树的遍历（4）查找与排序学生姓名：代巍学生学号：指导老师：余腊生所在学院：信息科学与工程学院专业班级：信息安全1201班指导教师评定：签名：实验一单链表的实现一、实验目的了解线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在某种存储结构上如何实现这些基本运算。在熟悉上述内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题二、实验内容用C/C++语言编写程序，完成以下功能： 

2、    （1）运行时输入数据，创建一个单链表    （2）可在单链表的任意位置插入新结点    （3）可删除单链表的任意一个结点 （4）在单链表中查找结点     （5）输出单链表三、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 用一组地址任意的存储单元存放线性表中的数据元素。  以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点(表示数据元素 或 数据元素的映象)  以“结点的序列”表示线性表称作线性链表（单链表）单链表是指数据接点是单向排列的。一个单链表结点，其

3、结构类型分为两部分：  （1）、数据域：用来存储本身数据。  （2）、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。 1、单链表的查找 对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。 2、单链表的插入 因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。  假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点

4、s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。(p-＞link=s;s-＞link=q)，这样就完成了插入操作。 3、单链表的删除 删除运算思想方法删除运算是将表的第i个结点删去。具体步骤：找到 i-1 的存储位置p令p-next指向 i 的直接后继结点释放结点 i 的空间，将其归还给"存储池"。四、源程序及注释#include#include#include#include#include#

5、defineElemTypeint//链表类型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intEmptyList(LinkList&L){if(L->next==NULL){return0;}else{return1;}}//手动建立一个带头结点的线性链表LvoidSCreateList_L(LinkList&L){LinkListl,p;inti;ElemTyped;l=(LinkList)malloc(sizeof(LNode));L=(Li

6、nkList)malloc(sizeof(LNode));//生成头结点l=L;L->next=NULL;cout<<"请依次输入结点值，以0为结束："<>d;if(d!=0){p=(LinkList)malloc(sizeof(LNode));//生成新结点p->data=d;p->next=l->next;l->next=p;l=l->next;}elsebreak;}if(EmptyList(L))cout<<"生成链表成功！！";elsecout<<"链表为空，未生成！！";ci

7、n.get();cin.get();}//SCreate_L//自动建立一个带头结点的线性链表LvoidZCreateList_L(LinkList&L,intn){LinkListl,p;l=(LinkList)malloc(sizeof(LNode));L=(LinkList)malloc(sizeof(LNode));//生成头结点l=L;L->next=NULL;srand((unsigned)time(NULL));for(inti=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));/

8、/生成新结点p->data=(rand()%100+1);p->next=l->next;l->next=p;l=l->next;}cout<<"生成链表成功！！";cin.get();cin.get();}//ZCre