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

数据结构实验报告专业班级：指导老师：余腊生姓 名：学 号：实验一 单链表的基本操作的实现一、实验目的掌握单链表的基本操作：建立、插入、删除、查找等运算。二、实验仪器安装VC+的PC机。三、实验原理 利用线性表的特性以及其链式存储结构特点对线性表进行相关操作。四、 实验内容程序中演示了单链表的创建、插入、删除和查找。程序如下：#include#include#include#includetypedef struct node int data; struct node *next; NODE;/*/NODE *Create()NODE *p,*head;int x;head=(NODE *)malloc(sizeof(NODE);head-next=NULL;printf(Input data,-1 to End!n);scanf(%d,&x);while(x!=-1) p=(NODE *)malloc(sizeof(NODE); p-data=x; p-next=head-next; head-next=p; scanf(%d,&x); return(head);/*/void Output(NODE *head) NODE *p; p=head; printf(Begin to dump the LinkList.n); while(p-next!=NULL) printf(-%d,p-next-data); p=p-next; printf(nThe LinkList ended!n);/*/int Listlen(NODE *head) int i=0; NODE *p=head; while(p-next!=NULL) i+; p=p-next; return(i);/*/int Get(NODE *head,int i)int j=0;NODE *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void Del(NODE *head,int i)NODE *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void Ins(NODE *head,int i,int e)NODE *p=head,*q;int j=0;while(p-next&jnext;if(!p-next&ji-1) printf(Wrong positionn );else q=(NODE *)malloc(sizeof(NODE); q-data=e; q-next=p-next; p-next=q;/*/main() NODE *head; int length; int i,element; system(CLS); head=Create(); Output(head); length=Listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d,&i); element=Get(head,i); printf(the element of the order is %dn,element); printf(input the del position n); scanf(%d,&i); Del(head,i); Output(head); printf(Input the insert posion and element:n); scanf(%d%d,&i,&element); Ins(head,i,element); Output(head); getch();五、数据记录及处理1、运行程序,输入下面一组数据: 93 94 12 13 20 14 链表顺序：14 20 13 12 94 932、删除第二个数据结点，在第一个位置插入数据20。 运行结果如下:插入结果：14 13 12 94 93删除结果：20 14 13 12 94 93运行结果截图：实验二 栈和队列的实现一、目的和要求1.理解队列和栈的顺序存储结构和链式存储结构。通过本实验，熟悉队列、栈的结构特点；2.熟悉队列、栈结构上的操作与算法的实现。二、实验内容1.队列的基本操作和应用。2.栈的基本操作和应用。三、仪器、设备和材料1.适合实验要求的计算机系统。2.V+编程平台。四、实验原理队列与栈是一种操作受限制的线性表，在了解线性表的基本原理的基础上，理解与完成此项实验。五、实验步骤1.采用队列的顺序存储结构，。2.用菜单的形式完成队列的建立，出队，入队等基本操作。3.采用栈的链式存储结构。4.用菜单的形式完成栈的出栈、入栈等基本操作。六、程序算法#include #include #define OVERFLOW -2#define ERROR 0#define OK 1#define MAX 100/栈的最大值typedef int SElemType;typedef int QElemType;typedef structSElemType *base; SElemType *top;SqStack;SqStack InitStacka( )/顺序存储实现栈的初始化SqStack S; S.base=(SElemType *)malloc(MAX*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.top=S.base; return(S);void Pusha(SqStack &S,int x)/顺序存储实现栈的入栈操作if(S.top-S.base=MAX) exit(OVERFLOW); *S.top+=x;void Popa(SqStack &S)/顺序存储实现栈的出栈操作SElemType *p; int x; if(S.top=S.base) return ; else p=S.top; x=*-S.top; printf(t删除的栈顶元素是%dnt出栈操作完成后的栈为:n,x); void printa(SqStack S)/输出SElemType *p; p=S.base; printf(t); while(p!=S.top) printf(%d ,*(p+);printf(n);typedef struct SqNodeSElemType data; SqNode *Link;*Sqptr,NODE;typedef structSqptr top;Stack;Stack InitStackb()/链式存储实现栈的初始化Stack S; S.top=(Sqptr)malloc(sizeof(NODE); if(!S.top) exit (OVERFLOW); S.top-Link=NULL; return(S);void Pushb(Stack &S,int x)/链式存储实现栈的入栈操作Sqptr p; p=(Sqptr)malloc(sizeof(NODE); if(!p) return; p-data=x; p-Link=S.top-Link; S.top-Link=p;void Popb(Stack &S)/链式存储实现栈的出栈操作int x; Sqptr p; if(S.top-Link=NULL) return; else p=S.top-Link; x=p-data; S.top-Link=p-Link; printf(t删除的栈顶元素是%dn,x); free(p);typedef struct QNodeQElemType data; struct QNode *next;*QueuePtr,QNode;typedef structQueuePtr front; QueuePtr rear;LinkQueue;LinkQueue InitQueue()/链式存储实现队列的初始化LinkQueue Q; Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if(!Q.front) exit(OVERFLOW); Q.front-next=NULL; return(Q);void EnQueue(LinkQueue &Q,QElemType x)/链式存储实现队列的入队QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode); if(!p) exit(OVERFLOW); p-data=x; p-next=NULL; Q.rear-next=p; Q.rear=p;void DeQueue(LinkQueue &Q)/链式存储实现队列的出队int x; if(Q.front=Q.rear) return; QueuePtr p; p=Q.front-next; x=p-data; printf(t删除的队头元素是：%dn,x); Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return;typedef structSElemType *base; int front,rear;SqQueue;SqQueue InitQueueb()/顺序存储实现队列的初始化SqQueue S; S.base=(SElemType *)malloc(MAX*sizeof(SElemType); if(!S.base) exit(OVERFLOW); S.front=S.rear=0; return(S);void EnQueueb(SqQueue &S,int x)/顺序存储实现队列的入队if(S.rear+1)%MAX=S.front) return; S.baseS.rear=x; S.rear=(S.rear+1)%MAX;void DeQueueb(SqQueue &S)/顺序存储实现队列的出队int x; if(S.front=S.rear) return; x=S.baseS.front; S.front=(S.front+1)%MAX; printf(t删除的队头元素是:%dn,x);void main()int choice; int n,x; printf(nn); printf(t1.采用链式存储实现栈的初始化、入栈、出栈操作n); printf(t2.采用顺序存储实现栈的初始化、入栈、出栈操作n); printf(t3.采用链式存储实现队列的初始化、入队、出队操作n); printf(t4.采用顺序存储实现队列的初始化、入队、出队操作n); printf(t请选择:); scanf(%d,&choice); switch(choice) case 1:Stack Sa; printf(t1.链式存储实现栈的初始化n); printf(t2.链式存储实现栈的入栈操作n); printf(t3.链式存储实现栈的出栈操作n); while(1) printf(t请选择：); scanf(%d,&n); switch(n) case 1:Sa=InitStackb(); printf(t链式存储栈的初始化完成!n);break; case 2:printf(t以0结束n);printf(t); scanf(%d,&x); while(x) Pushb(Sa,x);scanf(%d,&x); printf(t链式存储栈的入栈操作完成!n);break; case 3:Popb(Sa);break;break; case 2:SqStack S; printf(t1.顺序存储实现栈的初始化n); printf(t2.顺序存储实现栈的入栈操作n); printf(t3.顺序存储实现栈的出栈操作n); while(1) printf(t请选择:); scanf(%d,&n); switch(n) case 1:S=InitStacka(); printf(t顺序存储栈的初始化完成!n);break; case 2:printf(t以0结束n); printf(t); scanf(%d,&x); while(x) Pusha(S,x); scanf(%d,&x); printf(t顺序存储栈的入栈操作完成!n); printa(S);break; case 3:Popa(S); printa(S);break;break; case 3:LinkQueue Q; printf(t1.链式存储实现队的初始化n); printf(t2.链式存储实现队的入栈操作n); printf(t3.链式存储实现队的出栈操作n); while(1) printf(t请选择：); scanf(%d,&n); switch(n) case 1:Q=InitQueue(); printf(t链式存储队的初始化完成!n);break; case 2:printf(t以0结束n);printf(t);scanf(%d,&x); while(x) EnQueue(Q,x);scanf(%d,&x); printf(t链式存储队的入栈操作完成!n);break; case 3:DeQueue(Q);break;break; case 4:SqQueue Sv; printf(t1.顺序存储实现队的初始化n); printf(t2.顺序存储实现队的入栈操作n); printf(t3.顺序存储实现队的出栈操作n); while(1) printf(t请选择：); scanf(%d,&n); switch(n) case 1:Sv=InitQueueb(); printf(t链式存储栈的初始化完成!n);break; case 2:printf(t以0结束n);printf(t);scanf(%d,&x); while(x) EnQueueb(Sv,x);scanf(%d,&x); printf(t链式存储栈的入栈操作完成!n);break; case 3: DeQueueb(Sv);break;break;程序调试截图：1. 采用链式存储实现栈的初始化、入栈、出栈操作2.采用顺序存储实现栈的初始化、入栈、出栈操作3. 采用链式存储实现队列的初始化、入队、出队操作4.采用顺序存储实现队列的初始化、入队、出队操作七、心得体会 实践才能出真知，在通过了上机操作后，才发现了许多在平时上理论课的时候没有想到的方方面面，编写程序时发现很多语法的错误，以及很多英语单词的记不熟，记错，程序函数错用等等，我想需要在以后多多练习，才能逐步解决这些问题。实验三 二叉树的建立和遍历一、目的和要求1、了解二叉树的建立的方法及其遍历的顺序，熟悉二叉树的三种遍历2、检验输入的数据是否可以构成一颗二叉树二、实验内容1.二叉树的建立和遍历三、仪器、设备和材料1.适合实验要求的计算机系统。2.V+编程平台。4、 实验的描述和算法1、实验描述 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。2、 算法#include#includeusing namespace std;templatestruct BinTreeNode /二叉树结点类定义T data; /数据域BinTreeNode *leftChild,*rightChild; /左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL ) :data(x),leftChild(l),rightChild(r) /可选择参数的默认构造函数;/-templatevoid PreOrder_2(BinTreeNode *p) /非递归前序遍历stackBinTreeNode * S;while(p!=NULL | !S.empty()while(p!=NULL) coutdata; /访问根结点S.push(p);p=p-leftChild; /遍历指针进到左子女结点if(!S.empty() /栈不空时退栈p=S.top(); S.pop(); p = p-rightChild; /遍历指针进到右子女结点/-templatevoid InOrder_2(BinTreeNode *p) /非递归中序遍历stackBinTreeNode* S;dowhile(p!=NULL) /遍历指针未到最左下的结点，不空S.push(p); p=p-leftChild; if(!S.empty() /栈不空时退栈p=S.top();S.pop(); coutdata; p=p-rightChild; while(p !=NULL | !S.empty(); /-templatevoid PostOrder_2(BinTreeNode *p) /非递归后序遍历stackBinTreeNode * S;stack tag;/定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过while(p != NULL | !S.empty() /左子树经过结点加L进栈while(p!=NULL)S.push(p); /首先将t和tag为入栈，遍历左子树 tag.push(0);/遍历左子树前的现场保护p=p-leftChild;while( !S.empty() & tag.top()=1)p=S.top();S.pop();tag.pop();coutdata;/最后访问根结点。if( !S.empty()tag.pop();tag.push(1);/遍历右子树前的现场保护,修改栈顶tag为，遍历右子树p=S.top(); / 取栈顶保存的指针p=p-rightChild;elsebreak;templatevoid InOrder_1(BinTreeNode * subTree)/递归函数：中序次序遍历以subTree为根的子树。if(subTree !=NULL) /NULL是递归终止条件InOrder_1(subTree-leftChild); /中序遍历根的左子树coutdata; /访问根结点InOrder_1(subTree-rightChild); /中序遍历根的右子树templatevoid PreOrder_1(BinTreeNode * subTree)/递归函数：前序遍历以subTree为根的二叉树。if(subTree !=NULL) /递归结束条件 coutdata;/访问根结点PreOrder_1(subTree-leftChild); /前序遍历根的左子树PreOrder_1(subTree-rightChild); /前序遍历根的右子树templatevoid PostOrder_1(BinTreeNode * subTree)/递归函数：后序次序遍历以subTree为根的子树。if(subTree !=NULL) /NULL是递归终止条件PostOrder_1(subTree-leftChild); /后序遍历根的左子树PostOrder_1(subTree-rightChild); /后序遍历根的右子树 coutdata; /访问根结点/-templatevoid CreateBinTree(BinTreeNode * & subTree)/递归方式建立二叉树T item; cinitem;if(item !=-1)subTree = new BinTreeNode();if(subTree = NULL)cerr存储分配错！data = item;CreateBinTree(subTree-leftChild); /递归建立左子树CreateBinTree(subTree-rightChild); /递归建立右子树else subTree = NULL; /封闭指向空子树的指针int main() BinTreeNode * Tree = NULL;cout请输入每个结点，回车确认，并以-1结束：;CreateBinTree(Tree); cout先序遍历二叉树结果：; PreOrder_1(Tree); coutendl;cout中序遍历二叉树结果：;InOrder_1(Tree);coutendl; cout后序遍历二叉树结果：; PostOrder_1(Tree);coutendl;cout非递归前序遍历二叉树结果：;PreOrder_2(Tree);coutendl; cout非递归中序遍历二叉树结果：;InOrder_2(Tree);coutendl;cout非递归后序遍历二叉树结果：;PostOrder_2(Tree);coutendl;system(pause); 3、实验程序运行截图实验四 散列法查找和排序一、目的和要求1.用散列法实现顺序查找，折半查找。二、仪器、设备和材料1.适合实验要求的计算机系统。2.V+编程平台。3、 实验步骤和程序1、 顺序查找#include #include #include #define m 100#define NULLKEY 0typedef int KeyType; /* 假设关键字为整型 */typedef structKeyType key;RecordType;typedef RecordType HashTablem;int hash(KeyType k)/*除留余数法构造哈希函数*/int h;h = k%m;return h;int HashSearch( HashTable ht, KeyType K)/*哈希查找*/int h0;int i;int hi;h0=hash(K);if (hth0.key=NULLKEY) return (-1);else if (hth0.key=K) return (h0);else /* 用线性探测再散列解决冲突 */ for (i=1; i=m-1; i+)hi=(h