中南大学数据结构实验报告_数据结构实验报告答案

2020-02-28 其他范文下载本文

中南大学数据结构实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构实验报告答案”。

数据结构实验报告

专业班级：指导老师：余腊生姓

名：学

号：实验一单链表的基本操作的实现

一、实验目的掌握单链表的基本操作：建立、插入、删除、查找等运算。

二、实验仪器

安装VC++的PC机。

三、实验原理

利用线性表的特性以及其链式存储结构特点对线性表进行相关操作。

四、实验内容

程序中演示了单链表的创建、插入、删除和查找。程序如下：

#include #include #include #include typedef 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||j>i)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||j>i-1)printf(“the position is wrongn”);else p->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&&j>i-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 struct {SElemType *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 SqNode {SElemType data;SqNode *Link;}*Sqptr,NODE;typedef struct {Sqptr 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 QNode {QElemType data;struct QNode *next;}*QueuePtr,QNode;typedef struct {QueuePtr 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 struct {SElemType *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.base[S.rear]=x;S.rear=(S.rear+1)%MAX;} void DeQueueb(SqQueue &S)//顺序存储实现队列的出队 {int x;if(S.front==S.rear)return;x=S.base[S.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Ｃ++编程平台。

四、实验的描述和算法

1、实验描述

二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。因为耳熟的每一个左右子树又是一颗二叉树，所以可以用递归的方法来建立其左右子树。二叉树的遍历是一种把二叉树的每一个节点访问完并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句实现。

2、算法

#include #include using namespace std;template struct BinTreeNode

//二叉树结点类定义 { T data;

//数据域

BinTreeNode *leftChild,*rightChild;

//左子女、右子女域

BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL)

:data(x),leftChild(l),rightChild(r){}

//可选择参数的默认构造函数 };//-----------template void PreOrder_2(BinTreeNode *p)

//非递归前序遍历 { stack * > 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;

//遍历指针进到右子女结点

} } } //--template void InOrder_2(BinTreeNode *p)

//非递归中序遍历 { stack* > S;do {

while(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());}

//----template void PostOrder_2(BinTreeNode *p)//非递归后序遍历 { stack * > 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;

}

else

break;

} } template void InOrder_1(BinTreeNode * subTree){//递归函数：中序次序遍历以subTree为根的子树。

if(subTree!=NULL)

//NULL是递归终止条件

{

InOrder_1(subTree->leftChild);//中序遍历根的左子树

coutdata;

//访问根结点

InOrder_1(subTree->rightChild);//中序遍历根的右子树

} } template void PreOrder_1(BinTreeNode * subTree){//递归函数：前序遍历以subTree为根的二叉树。if(subTree!=NULL)

//递归结束条件

{

coutdata;//访问根结点

PreOrder_1(subTree->leftChild);

//前序遍历根的左子树

PreOrder_1(subTree->rightChild);

//前序遍历根的右子树

} } template void PostOrder_1(BinTreeNode * subTree){//递归函数：后序次序遍历以subTree为根的子树。

if(subTree!=NULL)

//NULL是递归终止条件

{

PostOrder_1(subTree->leftChild);//后序遍历根的左子树

PostOrder_1(subTree->rightChild);//后序遍历根的右子树

coutdata;

//访问根结点

} } //------------template void CreateBinTree(BinTreeNode * & subTree){//递归方式建立二叉树

T item;

cin>>item;

if(item!=-1)

{

subTree = new BinTreeNode();

if(subTree == NULL)

{

cerr

exit(1);

}

subTree->data = item;

CreateBinTree(subTree->leftChild);//递归建立左子树

CreateBinTree(subTree->rightChild);//递归建立右子树

}

else subTree = NULL;

//封闭指向空子树的指针 } int main(){

BinTreeNode * Tree = NULL;cout

cout

PreOrder_1(Tree);

cout

PostOrder_1(Tree);cout

cout

3、实验程序运行截图

实验四散列法查找和排序

一、目的和要求

1.用散列法实现顺序查找，折半查找。

二、仪器、设备和材料

1.适合实验要求的计算机系统。2.VＣ++编程平台。

三、实验步骤和程序

1、顺序查找 #include #include #include #define m

#define NULLKEY 0 typedef int KeyType;

/* 假设关键字为整型 */ typedef struct { KeyType key;}RecordType;typedef RecordType HashTable[m];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(ht[h0].key==NULLKEY)

return(-1);else

if(ht[h0].key==K)

return(h0);

else

/* 用线性探测再散列解决冲突 */

{

for(i=1;i

{

hi=(h0+i)% m;

if(ht[hi].key==NULLKEY)

return(-1);

else

if(ht[hi].key==K)

return(hi);

}

return(-1);

}

} void main(){ int i,j;int n;int p;int hj;int k;int result;HashTable ht;for(i=0;i

ht[i].key = NULLKEY;printf(“请输入哈希表的元素个数:”);scanf(“%d”,&n);for(i=1;i

printf(“请输入第%d个元素:”,i);

fflush(stdin);

scanf(“%d”,&p);

j = hash(p);

if(ht[j].key == NULLKEY)

ht[j].key = p;

else

{

for(i=1;i

{

hj=(j+i)% m;

if(ht[hj].key==NULLKEY)

{

ht[j].key = p;

}

i = m;

}

} } printf(“请输入要查找的元素:”);fflush(stdin);scanf(“%d”,&k);result = HashSearch(ht,k);if(result ==-1)printf(“未找到!n”);else printf(“元素位置为%dn”,result);system(“pause”);运行结果如下：

2、折半查找

#include #define N 21 void main(void){ int a[N];int i,n,num;int top,bottom,mid;int flag=1;int loc=-1;printf(“你想在多少个数中进行折半查找，请输入(1--20):”);scanf(“%d”,&n);while(n20){

printf(“你输入的数不正确，请重新输入:n”);

printf(“你想在多少个数中进行折半查找，请输入(1--20):”);

scanf(“%d”,&n);} printf(“请你输入一个整数a[1]:”);scanf(“%d”,&a[1]);i=2;while(i

printf(“请你输入一个整数a[%d]:”,i);

scanf(“%d”,&a[i]);

i++;} printf(“n输出表列n”);for(i=1;i

bottom=%d,mid=%d,a[i]=%dn“,top,bottom,mid,mid,a[mid]);if((num>a[top])||(num

loc=-1;

flag=0;} else if(a[mid]==num){

loc=mid;

printf(”找到数

%6d的位置%2dn“,num,loc);