中南大学大数据结构实验报告材料

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

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

3、或者说指向其直接后 继的指针。1、单链表的查找对单链表进行查找的思路为： 对单链表的结点依次扫描， 检测其数据域是否 是我们所要查好的值，若是返回该结点的指针，否则返回NULL。2、单链表的插入因为在单链表的链域中包含了后继结点的存储地址， 所以当我们实现的时候， 只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。假设在一个单链表中存在2个连续结点p、q (其中p为q的直接前驱)，若 我们需要在p、q之间插入一个新结点s,那么我们必须先为s分配空间并赋值， 然后使p的链域存储s的地址，s的链域存储q的地址即可。(p- link=s;s- link=q) ，这样就完成了插入操作。3、

4、单链表的删除删除运算思想方法删除运算是将表的第 i 个结点删去。具体步骤：找 到i-1的存储位置p令p-next指向i的直接后继结点释放结点i的空间，将其归还给 存储池 。四、源程序及注释#include #include #include #include #include #define ElemType int/ 链表类型typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int EmptyList(LinkList &L) if(L-next=NULL) return 0;elsereturn 1

5、;/ 手动建立一个带头结点的线性链表 L void 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;coutd;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 生成链表成功！

6、 else cout 链表为空，未生成！ ！ ; cin.get();cin.get(); /SCreate_L生成头结点next=NULL;srand(unsigned)time(NULL);for(int i=n;i0;-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() ch

7、ar c;int n;LinkList L;cout* 建立线性链表*endl;cout1. 手动建立 endl;cout2. 自动建立 endl;cout|*|c;if(c=1) SCreateList_L(L);else if(c=2) coutn;ZCreateList_L(L,n);else cout 输入错误，请重新输入 :next;int i=0;while (p)+i;p=p-next;return i;cin.get();cin.get(); /LengthList/在线性链表L中第i个结点之前插入新的数据元素evoid ListInsert_L(LinkList &L)int

8、 i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,s;p=L;int j=0;while(p & jnext;+j;if(!p | ji-1) cout输入错误！ cin.get();cin.get();else coute;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(Link

9、List &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-next & jnext;+j; / 寻找第 i 个结点if(!(p-next) | ji-1) coutnext;p-next=q-next;e=q-data;cout 删除成功！ endl 删除的结点值为： next; cout 所有数据如下所示： endl;while (p)coutdatanext;cin.get();cin.get();

10、 /PrintListvoid SearchList(LinkList &L)/ 查找某一结点，显示其位置int i=0;ElemType n;coutn;if(L=NULL) coutnext;while (p-data!=n & p-next!=NULL) p=p-next; i=i+1;if(p-data=n) cout 找到了对应的结点，在链表的第 i+1 位上！ ; else coutnext;free(p);L=NULL;cout 线性链表 L 已销毁 !endl;/DestroyListint menu_select() / 选择函数char *m7= 1. 建立线性链表 ,2.

11、 某一结点前插入一个结点 ,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=CreateList_L(); system(pause); break

12、;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:i;if(L!=NULL) int i=LengthList(L);cout 结点的个数为： cin.get();cin.get();else cout 链表为空

13、，请先建链表！ ！ ;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); exi

14、t(0);五、实验结果一槌表的基本操作占S 结 位 个出点 一S 入并- 性点工 线结一结并紫 立一隧岀 僅-1、厂咅一剩一入输2 1 请- 与1=1=:2插新.72也窜重据！继 耘：数！键1 ft?选2置置结入按 请请实验二 栈和队列、实验目的了解栈和队列的特性。 掌握栈的顺序表示和实现。 掌握栈的链式表示和实现。 掌握队列的顺序表示和实现。 掌握队列的链式表示和实现。 掌握栈和队列在实际问题中的应用、实验内容编写一个程序实现顺序栈的各种基本运算， 并在此基础上设计一个主程序完 成如下功能：初始化顺序栈，插入元素，删除栈顶元素，取栈顶元素，遍历顺序 栈，置空顺序栈。三、程序设计的基本思想，原

15、理和算法描述栈的修改时按照先进后出的原则进行的， 试验中用到构造空栈， 及入栈出栈 操作。队列是一种先进先出的线性表， 只允许在表的一端插入， 而在另一端删除 元素，试验中构造队并且入队出队。立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数据；建立 InitStack、StackEmpty、StackFull、Pop Push、GetTop 函数用作顺 序栈的基本操作； 建立 InitQueue 、 QEmpty、 Qfull 、 InQueue、 OutQueue、 ReadFront 函数用作队列的基本操作；建立主函数依次按序对子函数进行操作：Ini tStack

16、 初始化栈Push压入数 据f Ini tQueue初始化队列Pop弹出数据In Queue存入队列OutQueue出队 列一 Push压入栈Pop弹出数据free清空栈与队列。在数据的输入与数据的 输出时提供必要的提示信息。四、源程序及其注释#include #include stack.h#include #define MAXSIZE 100/ 作用 ：对栈进行初始化/ 参数：无/ 返回值： SeqStackSeqStack SeqStackInit()SeqStack S ;S.top = -1 ;return S ;/ 作用 ：对栈进行判断是否为空/ 参数：传入要判断的栈/返回值：返

17、回TRUE为空，返回FLASE为非空int SeqStackEmpty(SeqStack S)if(S.top top - ;printf(n清空！ n) ;/ 作用 ：把元素 x 压入栈，使其成为新的栈顶元素/ 参数：传入栈和要输入的数字/ 返回值：无void SeqStackPush(SeqStack *S,DataType x)S-top+ ;/ 要求是先挖坑，再种萝卜S-dataS-top = x ;/ 作用 ：出栈/ 参数：要从该栈出来/ 返回值：从栈中出来的数DataType SeqStackPop(SeqStack *S)DataType temp ;if(SeqStackEmp

18、ty(*S)printf(sorry ！为空栈！ ) ;/ exit(1) ;elsetemp = S-dataS-top ;/ 出栈是当前出栈，要求先挖萝卜再填坑 S-top - ;printf(n%dn,temp) ;/ 作用 ：取栈顶元素/ 参数：要操作的栈/ 返回值：从栈中出来的数DataType SeqStackGetTop(SeqStack S)DataType temp ;if(SeqStackEmpty(S)printf(sorry ！为空栈！ ) ;/ exit(1) ;elsetemp = S.dataS.top ;/ 出栈是当前出栈，要求先挖萝卜再填坑printf(n%d

19、n,temp)/ 作用 输出顺序栈中的元素/ 参数：要操作的栈/ 返回值：从栈中出来的数void SeqStackPrint(SeqStack S)DataType temp ;SeqStack p ;p = S ;printf( 输出栈中的所有元素 :) ;while(!SeqStackEmpty(p)temp = p.datap.top ;/ 出栈是当前出栈，要求先挖萝卜再填坑p.top - ;printf(n% d n,temp) ;/ 当这里位置数据类型怎么办void main(void)int num ;int input ;SeqStack p ;p = SeqStackInit(

20、) ;/ 这里调用入栈函数，把 10,20,30 进栈SeqStackPush(&p,10) ;SeqStackPush(&p,20) ;SeqStackPush(&p,30) ;while(1)printf(nt实验二 nn) ;printf(n1.入栈) ;printf(n2.栈顶元素弹出 ) ;printf(n3.取栈顶元素 ) ;printf(n4.输出顺序栈中的元素 )printf(n5.清空栈 n) ;printf(t请输入要实现的功能 n)scanf(%d,&num) ;switch(num)case 1 :ttn) ;printf(n 请输入要入栈的数： scanf(%d, &

21、input) ;SeqStackPush(&p,input) ;break;case 2 :SeqStackPop(&p) ;break;case 3 :SeqStackGetTop(p) ;break;case 4 :SeqStackPrint(p) ;break;case 5 :ClearStack(&p) ;break;五、实验结果栈脛元 恚豐出駱中的元素“请输入要实现的功能请输入要实现的功能4输岀栈中的所有元素：4231212枝顶栈岀空 人栈暮诟 12 3 4 5 1元素弹岀请输入要实现的功能请输入要入栈的数;2请瀚人要究现的功能清空!实验三 二叉树的建立和遍历一、实验目的1、学会实现

22、二叉树结点结构和对二叉树的基本操作。2、掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递 归数据结构进行处理的算法。二、实验内容 编写程序任意输入二叉树的结点个数和结点值， 构造一棵二叉树， 采用三种递归 遍历算法 （ 前序、中序、后序 ） 对这棵二叉树进行遍历并计算出二叉树的高度 。三、程序设计的基本思想，原理和算法描述1、数据结构的定义 二叉树是另一种树型结构， 它的特点是每个结点至多只有两棵子树， 并且二叉树 有左右之分， 其次序不能任意颠倒。 二叉树的存储结构分为顺序存储和链式存储 结构，本次我们主要应用二叉树的二叉链表的方式存储方式， 实验中首先必须对 二叉树的数据

23、结构进行定义， 即定义一个二叉链表， 其中其数据成员包括节点的 数据、左子树的指针、右子树的指针。2、二叉树的建立在实验开始前我们要建立一个以先序形式的二叉树， 先序的二叉树就是先访问根 结点，然后访问左子树，最后访问右子树的遍历。3、二叉树的遍历 二叉树的遍历分为先序、中序、后序，需先取遍历的节点的数据存入队列中，然 后输出。4、程序中要的函数的介绍 （ 1）二叉树的类型定义 （2）定义链式队列类型 （ 3）初始化链式队列的函数 （4）主函数四、源程序及注释#include#includetypedef struct BiTNodechar data;struct BiTNode *lchi

24、ld,*rchild;BiTNode,*BiTree;void CreatBiTree(BiTree &T)/ 前序法创建二叉树char ch;if(ch=getchar()=n)T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);void PreTravel(BiTree &T)/ 前序遍历if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);vo

25、id MidTravel(BiTree &T)/ 中序遍历if(T)MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);void PostTravel(BiTree &T)/ 后序遍历if(T)PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);void main()BiTree T;printf(please input the bitree:n );CreatBiTree(T);printf(The Pretravel is:n);PreTravel(T);p

26、rintf(n);/*/printf(The Midtravel is:n);MidTravel(T);printf(n);/*/printf(The PostTravel is:n);PostTravel(T);printf(n);五、实验结果p 1 e.s e inline thu bitree : 13I he Pr-e travel135The Midtrvel is =135The PostTiael is-531Press any key t;o continue实验四 查找和排序一、实验目的(1) 掌握查找的不同方法，并能用 c 语言实现查找算法。(2) 掌握常用的排序方法，并掌

27、握用 c 语言实现排序算法的方法。(3) 熟练掌握顺序表的选择排序、冒泡排序、直接插入排序等算法的实现；(4) 了解各种方法的排序过程及其时间复杂度的分析方法。二、实验内容(1) 完整理解有关排序和查找的相关算法和基本思想以及种种算法使用的数据存 储结构；(2) 通过线性表对一组数据中的某个数据进行查找； 对该组数据进行从小到大的顺序进行排序； 三、程序设计的基本思想，原理和算法描述 ：开始的时候提示输入一组数据。 并存入一维数组中， 接下来调用一系列查找算法 对其进行处理。 顺序查找只是从头到尾进行遍历。 二分查找则是先对数据进行排 序，然后利用三个标志，分别指向最大，中间和最小数据，接下来

28、根据待查找数 据和中间数据的比较不断移动标志， 直至找到。 二叉排序树则是先构造， 构造部 分花费最多的精力， 比根节点数据大的结点放入根节点的右子树， 比根节点数据 小的放入根节点的左子树， 其实完全可以利用递归实现， 这里使用的循环来实现 的，感觉这里可以尝试用递归。 当二叉树建好后， 中序遍历序列即为由小到大的 有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树， 以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。四、源程序及其注释#include #define LENGTH 100#include #include #define INFMT %d#def

29、ine OUTFMT %d /* #define NULL 0L */ #define BOOL int#define TRUE 1 #define FALSE 0#define LEN 10000typedef int ElemType;typedef struct BSTNodeElemType data;struct BSTNode *lchild, *rchild; BSTNode, *BSTree; typedef BSTree BiTree;/* 插入新节点 */void Insert(BSTree *tree, ElemType item)BSTree node = (BSTre

30、e)malloc(sizeof(BSTNode); node-data = item;node-lchild = node-rchild = NULL;if (!*tree)*tree = node;elseBSTree cursor = *tree;while (1)if (item data)if (NULL = cursor-lchild)cursor-lchild = node;break;cursor = cursor-lchild;elseif (NULL = cursor-rchild)cursor-rchild = node;break;cursor = cursor-rchi

31、ld;return;voidshowbitree(BiTree T)/ 递归显示二叉树的广义表形式打印根节点if(!T) printf( 空 );return; printf(%d,T-data); / if(T-lchild |T-rchild)putchar();showbitree(T-lchild);/ 递归显示左子树putchar(,);showbitree(T-rchild);/ 递归显示右子树putchar();/* 查找指定值 */BSTree Search(BSTree tree, ElemType item) BSTree cursor = tree;while (curs

32、or)if (item = cursor-data)return cursor;else if ( item data)cursor = cursor-lchild;elsecursor = cursor-rchild;return NULL;/* 中缀遍历 */void Inorder(BSTree tree)BSTree cursor = tree;if (cursor)Inorder(cursor-lchild);printf(OUTFMT, cursor-data);Inorder(cursor-rchild);/* 回收资源 */void Cleanup(BSTree tree)BS

33、Tree cursor = tree, temp = NULL;if (cursor)Cleanup(cursor-lchild);Cleanup(cursor-rchild);free(cursor);void searchtree(BSTree root)char choice;printf( 中序遍历的结果为 :n);Inorder(root);printf(nn);ElemType item;BSTree ret;/* 二叉排序树的查找测试 */doprintf(n 请输入查找数据： );scanf(%d, &item);getchar();printf(Searching.n);re

34、t = Search(root, item);if (NULL = ret)printf( 查找失败！ );elseprintf( 查找成功！ );n);printf(n 继续测试按 y ，退出按其它键。choice = getchar(); while (choice=y|choice=Y);Cleanup(root);searchhash(int *arr,int n)int a10;int b,i,j,c;j=1;for(i=0;i9;i+)ai=0;printf( 以下为哈希表输出 n);for(i=0;in;i+)c=arri%7;A: if(ac=0)ac=arri;else c=

35、(c+1)%7;j+;ac+;goto A;printf(n%d 在哈希表的第4位，第4次放入哈希表n,arri,c,j);j=1;void SequenceSearch(int *fp,int Length);void Search(int *fp,int length);void Sort(int *fp,int length);void SequenceSearch(int *fp,int Length)int data;printf( 开始使用顺序查询 .n 请输入你想要查找的数据 .n); scanf(%d,&data);for(int i=0;iLength;i+)if(fpi=d

36、ata)printf(经过d次查找，查找到数据 %d.n,i+1,data);return ;printf（ 经过d次查找，未能查找到数据%d.n,i,data）; void Search(int *fp,int length)int data;printf( 开始使用顺序查询 .n 请输入你想要查找的数据 .n); scanf(%d,&data);.n);printf( 由于二分查找法要求数据是有序的，现在开始为数组排序 Sort(fp,length);printf( 数组现在已经是从小到大排列 , 下面将开始查找 .n);int bottom,top,middle;bottom=0;top

37、=length;int i=0;while (bottom=top)middle=(bottom+top)/2;i+;if(fpmiddledata)top=middle-1; elseprintf(”经过d次查找，查找到数据d.n,i,data);return;printf( 经过d次查找，未能查找到数据%d.n,i,data);void Sort(int *fp,int length).n);printf( 现在开始为数组排序，排列结果将是从小到大int temp;for(int i=0;ilength;i+)for(int j=0;jfpj+1)temp=fpj;fpj=fpj+1;fp

38、j+1=temp;printf( 排序完成 !n 下面输出排序后的数组 :n);for(int k=0;klength;k+)printf(%5d,fpk);printf(n);struct hash int key;int si;struct hash hlist11;int i,adr,sum,d;float average;void chash(int *arr,int n) for(i=0;i11;i+) hlisti.key=0;hlisti.si=0;for(i=0;in;i+) sum=0;adr=(3*arri)%11;d=adr;if(hlistadr.key=0) hlistadr.key=arri;hlistadr.si=1;else