中南大学数据结构实验报告代巍.doc

中南大学数据结构实验报告实验题目：（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 #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; / 手动建立一个带头结点的线性链表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为结束：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 coutnext=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()char 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 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(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-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(); /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.某一结点前插入一个结点,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;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);五、实验结果实验二 栈和队列一、实验目的了解栈和队列的特性。 掌握栈的顺序表示和实现。 掌握栈的链式表示和实现。 掌握队列的顺序表示和实现。 掌握队列的链式表示和实现。 掌握栈和队列在实际问题中的应用。二、实验内容编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能：初始化顺序栈，插入元素，删除栈顶元素，取栈顶元素，遍历顺序栈，置空顺序栈。三、程序设计的基本思想，原理和算法描述栈的修改时按照先进后出的原则进行的，试验中用到构造空栈，及入栈出栈操作。队列是一种先进先出的线性表，只允许在表的一端插入，而在另一端删除元素，试验中构造队并且入队出队。立顺序栈SeqStack，存放测试数据；建立队列SeqQueue存放出栈数据；建立InitStack、StackEmpty、StackFull、Pop、Push、GetTop函数用作顺序栈的基本操作；建立InitQueue、QEmpty、Qfull、InQueue、OutQueue、ReadFront函数用作队列的基本操作；建立主函数依次按序对子函数进行操作：InitStack初始化栈Push压入数据InitQueue初始化队列Pop弹出数据InQueue存入队列OutQueue出队列Push压入栈Pop弹出数据free清空栈与队列。在数据的输入与数据的输出时提供必要的提示信息。四、源程序及其注释#include #include stack.h#include #define MAXSIZE 100/作用 ：对栈进行初始化/参数：无/返回值：SeqStackSeqStack SeqStackInit() SeqStack S ;S.top = -1 ;return S ;/作用 ：对栈进行判断是否为空/参数：传入要判断的栈/返回值：返回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(SeqStackEmpty(*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%dn,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() ;/这里调用入栈函数，把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 :printf(n请输入要入栈的数：ttn) ;scanf(%d, &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;五、实验结果实验三 二叉树的建立和遍历一、实验目的1、学会实现二叉树结点结构和对二叉树的基本操作。2、掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验内容编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。三、程序设计的基本思想，原理和算法描述1、数据结构的定义二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。二叉树的存储结构分为顺序存储和链式存储结构，本次我们主要应用二叉树的二叉链表的方式存储方式，实验中首先必须对二叉树的数据结构进行定义，即定义一个二叉链表，其中其数据成员包括节点的数据、左子树的指针、右子树的指针。2、二叉树的建立在实验开始前我们要建立一个以先序形式的二叉树，先序的二叉树就是先访问根结点，然后访问左子树，最后访问右子树的遍历。3、二叉树的遍历二叉树的遍历分为先序、中序、后序，需先取遍历的节点的数据存入队列中，然后输出。4、程序中要的函数的介绍（1）二叉树的类型定义（2）定义链式队列类型（3）初始化链式队列的函数（4）主函数四、源程序及注释#include#includetypedef struct BiTNodechar data; struct BiTNode *lchild,*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);void 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);printf(n);/*/printf(The Midtravel is:n);MidTravel(T);printf(n);/*/printf(The PostTravel is:n);PostTravel(T);printf(n);五、实验结果实验四 查找和排序一、实验目的(1)掌握查找的不同方法，并能用c语言实现查找算法。 (2)掌握常用的排序方法，并掌握用c语言实现排序算法的方法。(3)熟练掌握顺序表的选择排序、冒泡排序、直接插入排序等算法的实现；(4)了解各种方法的排序过程及其时间复杂度的分析方法。二、实验内容(1)完整理解有关排序和查找的相关算法和基本思想以及种种算法使用的数据存储结构；(2)通过线性表对一组数据中的某个数据进行查找；对该组数据进行从小到大的顺序进行排序；三、程序设计的基本思想，原理和算法描述：开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。四、源程序及其注释#include #define LENGTH 100#include #include #define INFMT %d#define OUTFMT %d /* #define NULL 0L */#define BOOL int#define TRUE 1#define FALSE 0#define LEN 10000typedef int ElemType;typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree;typedef BSTree BiTree;/* 插入新节点 */void Insert(BSTree *tree, ElemType item) BSTree node = (BSTree)malloc(sizeof(BSTNode); node-data = item; node-lchild = node-rchild = NULL; if (!*tree) *tree = node; else BSTree cursor = *tree; while (1) if (item data) if (NULL = cursor-lchild) cursor-lchild = node; break; cursor = cursor-lchild; else if (NULL = cursor-rchild) cursor-rchild = node; break; cursor = cursor-rchild; return;void showbitree(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 (cursor) if (item = cursor-data) return cursor; else if ( item data) cursor = cursor-lchild; else cursor = 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) BSTree 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; /* 二叉排序树的查找测试 */ do printf(n请输入查找数据：); scanf(%d, &item); getchar(); printf(Searching.n); ret = Search(root, item); if (NULL = ret) printf(查找失败！); else printf(查找成功！); printf(n继续测试按y，退出按其它键。n); 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=(c+1)%7;j+;ac+;goto A;printf(n%d在哈希表的第%d位,第%d次放入哈希表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=data) 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); printf(由于二分查找法要求数据是有序的，现在开始为数组排序.n); Sort(fp,length); printf(数组现在已经是从小到大排列,下面将开始查找.n); int bottom,top,middle; bottom=0; top=length; int i=0; while (bottom=top) middle=(bottom+top)/2; i+; if(fpmiddledata) top=middle-1; else printf(经过%d次查找，查找到数据%d.n,i,data); return; printf(经过%d次查找，未能查找到数据%d.n,i,data);void Sort(int *fp,int length) printf(现在开始为数组排序，排列结果将是从小到大.n); int temp; for(int i=0;ilength;i+) for(int j=0;jfpj+1) temp=fpj; fpj=fpj+1; fpj+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) hlistad