数据结构试验报告_实验报告数据结构
数据结构试验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“实验报告数据结构”。
实验一：ADT的类C描述向C程序的转换实验(2学时)
实验目的：
(1)复习C语言的基本用法；
(2)学会用类C的语言对算法进行描述的方法，将类C算法转换成C源程序的方法和过程；
(3)抽象数据类型的定义和表示、实现；
(4)加深对数据的逻辑结构和物理结构之间关系的理解；(5)初步建立起时间复杂度和空间复杂度的概念。实验内容：(类C算法的程序实现)(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果； 实验准备：
1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：
1.安装TC并设置好环境，如果已安装好，可以跳过此步； 2.录入程序代码并进行调试和算法分析；
对实验内容(1)的操作步骤：1)用类C语言描述算法过程；2)用C语言环境实现该算法。
对实验内容(2)的操作步骤：1)完成算法的C实现；2)分析其时间复杂度和空间复杂度。
3.编写实验报告。
实验结果：// 动态分配数组空间 #include #include
int size,i;int *pArray;int *p;void malloc_size(){ pArray=(int *)malloc(size*(sizeof(int)));}
int input_size(){ printf(“please input the size:n”);printf(“size= ”);scanf(“%d”,&size);return 0;}
int input_data(){ printf(“please input the value:n”);for(i=0;i
printf(“pArray[%d]= ”,i);
scanf(“%d”,&pArray[i]);} return *pArray;}
int Compare(){ int x,y,i;x=y=p[0];for(i=0;i
if(x>=p[i])x=p[i];
if(y
max=%dn“,x,y);return 0;}
int Output_data(){ p=pArray;printf(”before ofpaixu :n“);for(i=0;i
printf(”%dt“,*pArray);
pArray++;} printf(”n“);return *pArray;}
void paixu(){ int x=0;int i,j;printf(”later of paixu:n“);for(i=0;i
for(j=i+1;j
{
if(p[i]>=p[j])
{
x=p[i];p[i]=p[j];p[j]=x;
}
}
printf(”%dt“,p[i]);} printf(”n“);}
void main(){ clrscr();input_size();malloc_size();input_data();Output_data();Compare();paixu();}
实验结果：
实验二
线性表及其基本操作实验(2学时)实验目的：
(1)熟练掌握线性表ADT和相关算法描述、基本程序实现结构；(2)以线性表的基本操作为基础实现相应的程序；
(3)掌握线性表的顺序存储结构和动态存储结构之区分。
实验内容：(类C算法的程序实现，任选其一。具体要求参见教学实验大纲)(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算； 实验准备：
1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：
1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//线性链表
#include #include #define M 6
typedef struct node { int data;struct node *next;}*Sqlist;
void Initlialize(Sqlist &L){ L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;}
int Getlength(Sqlist L){ int i=0;Sqlist p=L->next;while(p!=NULL){
i++;
p=p->next;}
return i;}
int Getelem(Sqlist L,int i){
int j=1,e;Sqlist p=L->next;while(j
p=p->next;
j++;}
e=p->data;printf(”第 %d 个元素是：%dn“,i,e);return 1;}
int Locatelem(Sqlist L,int x){
int i=0;Sqlist p=L->next;while(p!=NULL&&p->data!=x){
p=p->next;
i++;} if(p==NULL)
return 0;else
{
printf(”%d 是第 %d 个元素n“,x,i);return i;} }
void CreatlistF(Sqlist &L,int a[ ],int n){ Sqlist s;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;for(i=0;i
s=(Sqlist)malloc(sizeof(Sqlist));
} }
void CreatlistR(Sqlist &L,int a[],int n){
Sqlist s,r;int i;L=(Sqlist)malloc(sizeof(Sqlist));L->next =NULL;r=L;for(i=0;i
s=(Sqlist)malloc(sizeof(Sqlist));
s->data =a[i];
s->next=NULL;
r->next =s;r =s;} }
int Inselem(Sqlist &L,int i,int x){ int j=1;Sqlist s,p=L->next;s=(Sqlist)malloc(sizeof(Sqlist));s->data =x;s->next =NULL;if(iGetlength(L))
return 0;while(j
p=p->next;j++;} printf(”在第 %d 个位置插入数据：%dn“,i,x);s->next =p->next;
p->next =s;return 1;}
int Delelem(Sqlist &L,int i){
int j=1;
Sqlist p,q;
p=L;
if(iGetlength(L))
return 0;s->data =a[i];
s->next =L->next;L->next =s;
while(j
{
p=p->next;
j++;
}
q=p->next;
p->next =q->next;
free(q);
return 1;}
void Displist(Sqlist L){ Sqlist p=L->next;
while(p!=NULL)
{
printf(”%dt“,p->data);
p=p->next;
}
printf(“n”);}
void input(int *pArray,int n){
printf(”请输入数组数据(共含 %d 个元):n“,n);
for(int i=0;i
Scanf(“%d”,&pArray[i]);
}
int main(int argc, char* argv[]){ Sqlist L;
int Array[M],Select;initlialize(L);do{
printf(”请输入选择方法（1表示头插法，2表示尾插法,0表示结束）：n“);
scanf(”%d“,&Select);
switch(Select)
{
case 1: printf(”按头插法建立线性表:n“);
input(Array,M);
creatlistF(L,Array,M);
break;case 2: printf(”按尾插法建立线性表:n“);
input(Array,M);
creatlistR(L,Array,M);
break;
}
printf(”原线性表数据为:n“);Displist(L);
Getelem(L,3);
Locatelem(L,2);
Inselem(L,5,5);
printf(”修改后的线性表数据为:n“);
Delelem(L,4);
Displist(L);}while(Select!=0);return 0;} 运行结果:
实验三
栈和队列实验(6学时)实验目的：
(1)熟练掌握栈和队列的抽象数据类型及其结构特点；(2)实现基本的栈和队列的基本操作算法程序。实验内容：(类C算法的程序实现，任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)；
(2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）； 实验准备：
1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。实验步骤：
1.录入程序代码并进行调试和算法分析； 2.编写实验报告。实验结果：//队列存储 #include #define QueueSize 10 typedef int status;
typedef struct sqqueue { char data[QueueSize];int front,rear;}SqQueue;
void InitQueue(SqQueue &qu){ qu.front =qu.rear =0;}
status EnQueue(SqQueue &qu,char x){
if((qu.rear +1)%QueueSize==qu.front)
return 0;qu.rear =(qu.rear+1)%QueueSize;qu.data[qu.rear]=x;return 1;}
status DeQueue(SqQueue &qu,char &x){ if(qu.rear==qu.front)
return 0;qu.front =(qu.front +1)%QueueSize;x=qu.data[qu.front];return 1;}
status GetHead(SqQueue qu,char &x){ if(qu.rear ==qu.front)
return 0;x=qu.data[(qu.front+1)%QueueSize];return 1;}
status QueueEmpty(SqQueue qu){ if(qu.rear==qu.front)
return 1;else
return 0;}
void main(){ SqQueue qu;char e;InitQueue(qu);printf(”Queue %sn“,(QueueEmpty(qu)==1?”Empty“:”Not Empty“));
printf(”inser an“);
EnQueue(qu,'a');
printf(”inser bn“);
EnQueue(qu,'b');
printf(”inser cn“);
EnQueue(qu,'c');
printf(”inser dn“);
EnQueue(qu,'d');
printf(”Queue %sn“,(QueueEmpty(qu)==1?”Empty“:”Not Empty“));
GetHead(qu,e);
printf(”Queue of top elem is: %cn“,e);
printf(”show of Queue:n“);
while(!QueueEmpty(qu)){
DeQueue(qu,e);
printf(”%ct“,e);}
printf(”n“);} 实验结果：
（2）//用栈实现对表达式的求值运算
#include #include #include
#define TRUE 1 #define FALSE 0 #define OK#define ERROR 0 #define INFEASIBLE-1 #define OVERFLOW-2 #define STACK_INIT_SIZE
#define STACKINCREMENT 10
typedef int Status;typedef char ElemType;
typedef ElemType OperandType;
typedef char OperatorType;
typedef struct {
ElemType *base;
ElemType *top;
int stacksize;}SqStack;
Status InitStack(SqStack &S){
S.base =(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
if(!S.base)exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;}
Status GetTop(SqStack S){
ElemType e;
if(S.top == S.base)return ERROR;
e = *(S.top-1);
return e;}
Status Push(SqStack &S,ElemType e)
{
if(S.top1
merge(r, r1, i, i+length-1, i + 2*length1
merge(r, r1, i, i+length-1, n-1);
else
for(j = i;j
void MergeSort(SortObject * pvector){
RecordNode record[MAXNUM];
int length = 1;
while(length n){
mergePa(pvector->record, record, pvector->n, length);
length *= 2;
mergePa(record, pvector->record, pvector->n, length);
length *= 2;
} }
SortObject vector = {8, 49,38,65,97,76,13,27,49};
int main(){
int i;printf(”排序前序列为：“);
for(i = 0;i
printf(”%d “, vector.record[i]);printf(”n“);
MergeSort(&vector);printf(”采用归并排序为：“);
for(i = 0;i
printf(”%d “, vector.record[i]);
getchar();
return 0;}
实验结果：
实验十
查找实验(2学时)* 实验目的：
(1)熟练掌握各种静态查找表方法(顺序查找、折半查找、索引顺序表等)；(2)熟练掌握二叉排序树的构造方法和查找算法；
(3)了解和掌握其它查找方法。
实验内容：(类C算法的程序实现，除顺序查找算法之外，任选一个)(1)顺序查找算法的实现(必做)；(2)折半查找算法的实现(选做)； 实验结果：//查找实验
1、顺序查找：
#include #define LENGTH 20
void SequenceSearch(int *fp,int Length){
int data;
printf(”开始使用顺序查询.请输入你想要查找的数据: “);
scanf(”%d“,&data);
for(int i=0;i
if(fp[i]==data)
{
printf(”数据%d 是第 %d 个数据n“,data,i+1);
return;
}
printf(”未能查找到数据%d.n“,i,data);}
void main(){
int count;
int arr[LENGTH];
printf(”请输入你的数据的个数:“);
scanf(”%d“,&count);
printf(”请输入 %d 个数据:“,count);
for(int i=0;i
scanf(”%d“,&arr[i]);
SequenceSearch(arr,count);}
实验结果：
2、折半查找：
#include #include #define M 10
typedef struct { char *elem;
int length;
}SStable;
void Create(char **t)
{ int i;static char a[M+1];*t=a;for(i=1;i
printf(”A[%d] is:“,i);
scanf(”%c“,&a[i]);
if(a[i]!= 'n')getchar();} }
int Searth(char *t,char k){ int i;for(i=M;i>=0 && t[i]!=k;i--);
Return i;}
void output(char *t){ int i;for(i=1;i
printf(”n
A[%d] is %c“,i,t[i]);}
void px(char *t)
{ char s;int i,j;for(i=1;i
for(j=i+1;j
{
if(t[i]>t[j]){s=t[i];t[i]=t[j];t[j]=s;}
} }
int Search_bin(char *t,char k){ int low=1,high=M,mid;while(low
mid=(low+high)/2;
if(k==t[mid])return mid;
else if(k
else low=mid+1;} return 0;}
void main(){ char *t,k;int s;Create(&t);output(t);printf(”nplease input you search char:“);k=getchar();s=Searth(t,k);if(s>=0)printf(”1: use search find is A[%d]n“,s);else printf(”1:can not find itn“);px(t);output(t);s=Search_bin(t,k);if(s==0)printf(”n1:can not find it n“);else printf(”n2:use Search_bin find is A[%d]n",s);getchar();}
实验结果：
