数据结构实验报告(C语言)(强力推荐)

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

数据结构实验

实验内容和目的：

掌握几种基本的数据结构：集合、线性结构、树形结构等在求解实际问题中的应用，以及培养书写规范文档的技巧。学习基本的查找和排序技术。让我们在实际上机中具有编制相当规模的程序的能力。养成一种良好的程序设计风格。

实验教材：

数据结构题集（C语言版） 清华大学出版社 2007年

实验项目：

实验一、栈和循环队列

㈠、实验内容：

① 栈

掌握栈的特点(先进后出FILO)及基本操作,如入栈、出栈等，栈的顺序存储结构和链式存储结构，以便在实际问题背景下灵活应用。本程序采用的是链栈结构，具有初始化一个栈、PUSH、POP、显示所有栈里的元素四个功能。

② 循环队列

掌握队列的特点(先进先出FIFO)及基本操作,如入队、出队等，学会循环队列的实现，以便在实际问题背景下灵活运用。本程序具有初始化一个队列、入队、出队、显示队列的所有元素、队列长度五个功能。

㈡、实验代码

① 栈

程序代码：

#include <stdio.h>

#include <malloc.h>

#define Stack_Size 6

#define ERROR 0

#define OK 1

typedef int SElemType;

typedef struct SNode

{

SElemType data;

struct SNode *next;

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

}SNode,*LinkStack;

int CreatTwo(LinkStack &head,int n)

{

int i;

SNode *p;

head=(LinkStack)malloc(sizeof(SNode));

head->next=NULL;

printf("请输入数据(数字):\n");

for(i=n;i>0;--i)

{

p=(SNode *)malloc(sizeof(SNode));

scanf("%d",&p->data);

p->next=head->next;

head->next=p;

}

return 1;

}

int menu_select()

{

int sn;

for(;;)

{

scanf("%d",&sn);

if(sn<1||sn>6)

printf("\n\t输入错误，请重新输入\n");

else

break;

}

return sn;

}

int Push(LinkStack &top,SElemType e)

{

SNode *q;

q=(LinkStack)malloc(sizeof(SNode));

if(!q)

{

printf("溢出!\n");

return(ERROR);

}

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

q->data=e;

q->next=top->next;

top->next=q;

return(OK);

}

int Pop(LinkStack &top,SElemType &e)

{

SNode *q;

if(!top->next)

{printf("error!\n");

return(ERROR);}

e=top->next->data;

q=top->next;

top->next=q->next;

free(q);

return(OK);

}

void main()

{ int e;

LinkStack top;

printf("1.初始化一个栈;\n2.PUSH;\n3.POP;\n4.显示所有栈里的元素;\n5.结束;\n");

while(1)

{

switch(menu_select())

{

case 1:

if(CreatTwo(top,Stack_Size))printf("Success!\n");break; case 2:

printf("Push:\n");

scanf("%d",&e);

if(Push(top,e))printf("Success!\n");

break;

case 3:

if(Pop(top,e))printf("Success!\n");

printf("%d\n",e);

break;

case 4:

LinkStack p;

printf("所有栈里的元素:\n");

p=top;

while(p->next)

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

{p=p->next;

printf("%7d",p->data);

}

printf("\n");

break;

case 5:

return;

}

}

}

运行结果：

② 循环队列

程序代码：

#include<stdlib.h>

#include<stdio.h>

#define OVERFLOW -1

#define OK 1

#define ERROR 0

#define MAXSIZE 100

typedef struct

{

int *elem;//队列存储空间

int front;

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

int rear;

}SqQueue;

//判断选择是否正确

int menu_select()

{

int sn;

for(;;)

{

scanf("%d",&sn);

if(sn<1||sn>6)

printf("\n\t输入错误，请重新输入\n");

else

break;

}

return sn;

}

//参数(传出)SqQueue &Q,循环队列(空)

int InitQueue(SqQueue &Q)

{

Q.elem=(int *)malloc(MAXSIZE*sizeof(int));

if(!Q.elem)exit(OVERFLOW);

Q.front=Q.rear=-1;

for(int i=0;i<MAXSIZE;i++)

Q.elem[i]=-1;

return OK;

}

//返回Q的元素个数

int QueueLength(SqQueue Q)

{

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

}

//显示队列的元素

void Display(SqQueue Q)

{

for(int i=0;i<=QueueLength(Q);i++)

if(Q.elem[i]!=-1)printf("%d ",Q.elem[i]);

printf("\n");

}

//入队

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

int EnQueue(SqQueue &Q,int e)

{

Q.rear=(Q.rear+1)%MAXSIZE;

if(Q.rear==Q.front)return ERROR;

Q.elem[Q.rear]=e;

return OK;

}

//出队

int DeQueue(SqQueue &Q,int &e)

{

if(Q.front==Q.rear)return ERROR;

e=Q.elem[Q.front+1];

Q.elem[Q.front+1]=-1;

Q.front=(Q.front+1)%MAXSIZE;

return OK;

}

void main()

{

SqQueue Q;

InitQueue(Q);

int elem,e;

printf("请输入队列元素(以0结束):\n");

scanf("%d",&elem);

while(elem!=0)

{

EnQueue(Q,elem);

scanf("%d",&elem);

}

printf("队列为：\n");

Display(Q);

printf("1.初始化一个队列;\n2.入队;\n3.出队;\n4.显示队列的所有元素;\n5.队列长度:\n6.结束;\n");

while(1)

{

switch(menu_select())

{

case 1:

printf("请输入队列元素(以0结束):\n");

scanf("%d",&elem);

while(elem!=0)

{EnQueue(Q,elem);

scanf("%d",&elem);}

printf("队列为：\n");

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

Display(Q);

fflush(stdin);

break;

case 2:

scanf("%d",&elem);

EnQueue(Q,elem);

printf("队列为：\n");

Display(Q);

fflush(stdin);

break;

case 3:

DeQueue(Q,elem);

printf("队列为：\n");

Display(Q);

break;

case 4:

printf("\n队列的所有元素:\n");

Display(Q);

break;

case 5:

printf("%d\n",QueueLength(Q));

break;

case 6:

return;

}

}

}

运行结果：

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

实验二、数组

㈠、实验内容：

数组一般不做插入或删除操作，也就是说，一旦建立了数组，则结构中的数据元素个数和元素之间的关系就不再发生变动。本程序数组的大小定义为3*3，可以通过修改“#define M”来变动。本程序具有矩阵相加、矩阵A转置、矩阵B转置、矩阵相乘四个功能。 ㈡、实验代码：

#include <stdio.h>

#define M 3

void MatrixAdd(int m1[M][M],int m2[M][M],int result[M][M])//两个矩阵m1和m2相加,结果放到result

{

int i,j;

for (i=0;i<M;i++)

{

for(j=0;j<M;j++)

result[i][j]=m1[i][j]+m2[i][j];

}

}

void MatrixTrams(int m1[M][M],int result[M][M])//矩阵转置 {

int i,j;

for (i=0;i<M;i++)

{

for (j=0;j<M;j++)

result[i][j]=m1[j][i];

}

}

void MatrixMultiply(int m1[M][M],int m2[M][M],int result[M][M]) {

int i,j;

for (i=0;i<M;i++)

{

for (j=0;j<M;j++)

{

result[i][j]=0;

for (int k=0;k<M;k++)

result[i][j]+=m1[i][k]*m2[k][j];

}

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

}

}

void Display(int result[M][M])//显示矩阵

{

int i,j;

for (i=0;i<M;i++)

{

for(j=0;j<M;j++)

printf("%-5d",result[i][j]);

printf("\n");

}

}

void main()

{

int A[M][M],B[M][M];

int i,j;

printf("请输入第一个矩阵：\n");

for(i=0;i<M;i++)

for(j=0;j<M;j++)

scanf("%d",&A[i][j]);

printf("请输入第二个矩阵：\n");

for(i=0;i<M;i++)

for(j=0;j<M;j++)

scanf("%d",&B[i][j]);

int result[M][M];

/*printf("\n 矩阵A:\n");

Display(A);

printf("\n 矩阵B:\n");

Display(B);*/

printf("请选择：\n1.矩阵相加：\n2.矩阵A转置：\n3.矩阵B转置：\n4.矩阵相乘：\n5.退出。\n\n");

while (1)

{int l;

scanf("%d",&l);

switch(l)

{

case 1:

printf("矩阵相加的运算结果：\n");

MatrixAdd(A,B,result);

Display(result);

printf("\n");

break;

case 2:

printf("矩阵A转置的运算结果：\n");

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

}

MatrixTrams(A,result); Display(result); printf("\n"); break; case 3: printf("矩阵B转置的运算结果：\n"); MatrixTrams(B,result); Display(result); printf("\n"); break; case 4: printf("矩阵相乘的运算结果：\n"); MatrixMultiply(A,B,result); Display(result); printf("\n"); break; case 5: printf("退出。\n"); return; default: printf("输入错误！"); printf("\n"); } }

实验结果：

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

实验三、查找

㈠ 、实验内容

掌握各种查找（顺序、二分法、查找树、哈希）方法及适用场合，并能在解决实际问题时灵活应用。本实验采用二分查找。二分查找又称折半查找，它是一种效率较高的查找方法。折半查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。本程序具有找出数据位置和显示查找次数两个功能。

㈡、实验代码：

#include <stdio.h>

#define MAX 100

void main()

{

int r[MAX],i,k,low,high,mid,m,n;

printf("\n\n 建立递增有序的查找顺序表（以-1结束）：\n"); for(i=0;i<MAX;i++)

{

scanf("%d",&r[i]);

if(r[i]==-1)

{

n=i;

break;

}

}

printf("\n 请输入要查找的数据：\n");

scanf("%d",&k);

low=0;high=n-1;m=0;

while(low<=high)

{

mid=(low+high)/2;

m++;

if(r[mid]>k)

high=mid-1;

else

if(r[mid]<k)

low=mid+1;

else

break;

}

if(low>high)

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

{

printf("没有找到\n");

printf("共进行%d次比较。\n",m);

if(r[mid]<k)

mid++;

printf("可将这个数插入到第%d个数的后面。\n",mid); }

else

{

printf("\n 要找的数据=%d在第%d个数的位置上。\n",k,mid+1);

printf("\n\n 共进行了%d次比较。\n",m); }

}

实验结果：

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

实验四、树

㈠ 、实验内容：

进一步掌握树的结构及非线性特点，递归特点和动态性；进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法及用广义表进行输入输出。本程序将第一个元素作为树根，其余元素若小于树根则为左子树，若大于树根则为右子树。本程序具有求左子树、求右子树、求深度、先序遍历、中序遍历（递归算法）、中序遍历（非递归算法）、后序遍历六个功能。

㈡、实验代码

//描述：两个指针指向左右孩子，算法见教材

#include <stdio.h>

#include <stdlib.h>

#define MAX 50

typedef struct btnode

{

int Data;

struct btnode *Llink;

struct btnode *Rlink;

}btnode,*btreetype;

btreetype CreatTree(int n)//传入数据数量，返回根结点指针 {

int i;

btreetype root=NULL;

for (i=0;i<n;i++)

{

btreetype newNode,currentNode,parentNode; newNode=(btreetype)malloc(sizeof(btnode)); scanf("%d",&newNode->Data);

newNode->Llink=NULL;

newNode->Rlink=NULL;

currentNode=root;

if(currentNode==NULL)root=newNode;

else{

while (currentNode!=NULL)

{

parentNode=currentNode;

if(newNode->Data<currentNode->Data) currentNode=currentNode->Llink; else

currentNode=currentNode->Rlink;

我自己编的C语言实验报告,每个程序都在VC6.0环境下编译通过~~~非常好用

}

if(newNode->Data<parentNode->Data)

parentNode->Llink=newNode;

else

parentNode->Rlink=newNode;

}

}

return root;

}

void OutputTree(btreetype &root)

{

btreetype p;

p=root->Llink;

printf("建立的二叉树的左子树为：\n");

while (p!=NULL)

{

printf("%-8d",p->Data);

p=p->Llink;

}

p=root->Rlink;

printf("\n建立的二叉树的右子树为：\n");

while (p!=NULL)

{

printf("%-8d",p->Data);

p=p->Rlink;

}

}

int depth(btreetype root)

{

btreetype p;

p=root;

int dep1;

int dep2;

if(root==NULL)return 0;

else