数据结构动态查找表实验报告
成都信息工程学院计算机系
课程实验报告
一【上机实验目的】
1、 深入理解数据结构的算法思想，将算法理论与实际应用相结合，培养学生的编程能力与编程兴趣，让学生清楚从项目分析、编码 、调试、程序维护的整个程序开发流程。
2、 使学生清楚解决一个编程问题的基本流程，即首先确定逻辑结构，然后在逻辑结构的基础上确定相应的存储结构，最后在设计一套合理而简便实用的算法，整个过程都是在用到数据结构的事项解决问题，是学生能够对线性表、二叉树、图的基本操作较为熟悉，并轻松控制。
3、 让学生明白在编程调试的过程中学习程序设计的思想、分析方法，培养并提高编程能力。
二【实验环境】
PC机每人1台
三【上机实验内容】
.实现所有的动态查找表。
该部分算法有一定的难度，尤其二叉排序树与平衡二叉树，涉及树的插入与删除等复杂操作。实现不易，尽管书中给出的代码较为详细，主要是能较好的掌握二叉树的插入、删除、与遍历，并能很好说明平衡二叉树的动态查找效率明显高于二叉排序树。
四【上机调试程序流程图】
五【上机调试中出现的错误信息、错误原因及解决办法】
1、 传参数时出现的问题、传递过去数值的话不能改变数据值，必须传递地址才行；
2、 空指针异常，老问题了，指针在使用之前必须要初始化分配空间才能够使用；
3、 调试过程中输入数据时出现的低级错误，忘加地址符，导致异常；
4、 对文件的操作出现了问题，写入的数据，读出来不正确或是读不出来，解决方法是以相同的格式和方法读写文件，中途加些printf语句检查读出来是否正确，并多次采用单步调试法，一步一步的调试即可。
六【上机调试后的源程序及还存在的问题】
//文件dtczb.h
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
#define LH +1
#define EH 0
#define RH -1
typedef int Status;
typedef int KeyType;
typedef char Name;
typedef char Sex;
typedef int Age;
//结点数据域的定义
typedef struct
{
KeyType key;
Name name[20];
Sex sex[20];
Age age;
}ElemType;
//动态表的数据结构
typedef struct DSTable
{
ElemType data;
Status bf;
struct DSTable *lchild,*rchild;
}*BiTree,BiTNode;
//构造一个只含根节点的动态表
Status InitDSTable(BiTree *DT);
//动态表中数据元素序列的输入
void InputData(ElemType array[],int n);
//销毁一个动态表
Status DestroyDSTable(BiTree *DT);
//查找表中是否有关键字等于key的记录
Status SearchDSTable(BiTree DT,KeyType key,BiTree f,BiTree *p);
//动态表的插入函数
Status InsertDSTable(BiTree *DT,ElemType e);
//动态表的删除函数
Status DeleteDSTable(BiTree *DT,KeyType key);
Status Delete(BiTree *p);
//动态表中节点的右旋
void R_Rotate(BiTree *p);
//动态表中节点的左旋
void L_Rotate(BiTree *p);
//二叉平衡树的插入
Status InsertAVL(BiTree *DT,ElemType e,Status *taller);
//左平衡函数
void LeftBalance(BiTree *DT);
//右平衡函数
void RightBalance(BiTree *DT);
void Print(BiTree DT);
//小界面的函数
void menu();
//dtczb.c文件
#include "dtczb.h"
//构造一个只含根节点的动态表
Status InitDSTable(BiTree *DT)
{
*DT=NULL;
return(TRUE);
}
//动态表中数据元素序列的输入
void InputData(ElemType array[],int n)
{
int i;
for(i=0;i<n;i++)
{
printf("******请输入第 %d 学生的信息******:\n",i+1);
printf("请输入该学生的学号、姓名、性别、年龄:\n");
scanf("%d %s %s %d",&array[i].key,array[i].name,array[i].sex,&array[i].age);
}
}
//查找表中是否有关键字等于key的记录
Status SearchDSTable(BiTree DT,KeyType key,BiTree f,BiTree *p)
{
if(!DT)
{
*p=f;
return(FALSE);
}
else if EQ(key,DT->data.key)
{
*p=DT;
return(TRUE);
}
else if LT(key,DT->data.key)
{
return(SearchDSTable(DT->lchild,key,DT,p));
}
else
{
return(SearchDSTable(DT->rchild,key,DT,p));
}
}
//动态表的插入函数
Status InsertDSTable(BiTree *DT,ElemType e)
{
BiTree s;
BiTree p;
p=(BiTree)malloc(sizeof(BiTNode));
if(!SearchDSTable(*DT,e.key,NULL,&p))
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
if(!p)
{
*DT=s;
}
else if LT(e.key,p->data.key)
{
p->lchild=s;
}
else
{
p->rchild=s;
}
return(TRUE);
}
else
{
return(FALSE);
}
}
//动态表的删除函数
Status DeleteDSTable(BiTree *DT,KeyType key)
{
if(!(*DT))
{
printf("你要删除的学生不存在!\n");
return(FALSE);
}
else
{
if(EQ(key,(*DT)->data.key))
{
return(Delete(DT));
}
else if (LT(key,(*DT)->data.key))
{
return(DeleteDSTable(&((*DT)->lchild),key));
}
else
{
return(DeleteDSTable(&((*DT)->rchild),key));
}
}
}
Status Delete(BiTree *p)
{
BiTree q,s;
if(!(*p)->rchild)
{
q=*p;
*p=(*p)->lchild;
free(q);
}
else if(!(*p)->lchild)
{
q=*p;
*p=(*p)->rchild;
free(q);
}
else
{
q=*p;
s=(*p)->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
(*p)->data=s->data;
if(q!=*p)
{
q->rchild=s->lchild;
}
else
{
q->lchild=s->rchild;
free(s);
}
}
return(TRUE);
}
//动态表结点的右旋函数
void R_Rotate(BiTree *p)
{
BiTree lc;
lc=(*p)->lchild;
(*p)->lchild=lc->rchild;
lc->rchild=*p;
*p=lc;
}
//动态表中节点的左旋
void L_Rotate(BiTree *p)
{
BiTree rc;
rc=(*p)->rchild;
(*p)->rchild=rc->lchild;
rc->lchild=*p;
*p=rc;
}
//二叉平衡树的插入
Status InsertAVL(BiTree *DT,ElemType e,Status *taller)
{
if(!(*DT))
{
*DT=(BiTree)malloc(sizeof(BiTNode));
(*DT)->data=e;
(*DT)->lchild=(*DT)->rchild=NULL;
(*DT)->bf=EH;
*taller=TRUE;
}
else
{
if(EQ(e.key,(*DT)->data.key))
{
*taller=FALSE;
return(0);
}
if(LT(e.key,(*DT)->data.key))
{
if(!InsertAVL(&((*DT)->lchild),e,taller))
return(0);
if(*taller)
{
switch((*DT)->bf)
{
case LH:
LeftBalance(DT);
*taller=FALSE;
break;
case EH:
(*DT)->bf=LH;
*taller=FALSE;
break;
case RH:
(*DT)->bf=EH;
*taller=FALSE;
break;
}
}
}
else
{
if(!InsertAVL(&((*DT)->rchild),e,taller))
return(0);
if(*taller)
{
switch((*DT)->bf)
{
case LH:
(*DT)->bf=EH;
*taller=FALSE;
break;
case EH:
(*DT)->bf=RH;
*taller=FALSE;
break;
case RH:
RightBalance(DT);
*taller=FALSE;
break;
}
}
}
}
return(1);
}
//左平衡函数
void LeftBalance(BiTree *DT)
{
BiTree lc,rd;
lc=(*DT)->lchild;
switch(lc->bf)
{
case LH:
(*DT)->bf=lc->bf=EH;
R_Rotate(DT);
break;
case RH:
rd=lc->rchild;
switch(rd->bf)
{
case LH:
(*DT)->bf=RH;
lc->bf=EH;
break;
case EH:
(*DT)->bf=lc->bf=EH;
break;
case RH:
(*DT)->bf=EH;
lc->bf=LH;
break;
}
rd->bf=EH;
L_Rotate(&((*DT)->lchild));
R_Rotate(DT);
}
}
//右平衡函数
void RightBalance(BiTree *DT)
{
BiTree rc,ld;
rc=(*DT)->rchild;
switch(rc->bf)
{
case RH:
rc->bf=EH;
(*DT)->bf=EH;
L_Rotate(DT);
case LH:
ld=rc->lchild;
switch(ld->bf)
{
case LH:
(*DT)->bf=EH;
ld->bf=RH;
break;
case EH:
(*DT)->bf=EH;
ld->bf=EH;
break;
case RH:
(*DT)->bf=RH;
ld->bf=EH;
break;
}
}
}
//中序遍历，打印出二叉树中的结点数据值
void Print(BiTree DT)
{
if(DT)
{
Print(DT->lchild);
printf("%d %s %s %d\n",DT->data.key,DT->data.name,DT->data.sex,DT->data.age);
Print(DT->rchild);
}
}
//小界面的函数
void menu()
{
printf("**********欢迎进入二叉排序树系统**********\n");
printf("##########0、文件信息的读取************\n");
printf("&&&&&&&&&&1、文件A的动态查找表<A、平衡,B、排序,C、删除>&&&&&&&&&&&&\n");
printf("**********2、文件B的动态查找表<A、平衡,B、排序,C、删除>************\n");
printf("##########3、文件C的动态查找表<A、平衡,B、排序,C、删除>############\n");
printf("^^^^^^^^^^4、文件的生成%%%%%%%%%%%%\n");
printf("@@@@@@@@@@5、退出系统 @@@@@@@@@@@@@\n");
}
//zhuhanshu.c文件
//主函数的实现
#include "dtczb.h"
#include<windows.h>
LARGE_INTEGER start;
LARGE_INTEGER end ;
LARGE_INTEGER frequency;
int main(void)
{
ElemType block[120],group[120];
int n,i,j,k,m;
int tall;
BiTree T[3];
int number;
char filename[3][20],gilename[3][20];
char decided[20],c;
FILE *fp,*fq,*fr;
menu();
while(1)
{
printf("\n请输入数字选择你要进行的操作:");
scanf("%d",&k); getchar();
switch(k)
{
case 0:
{
fr=fopen("fname","rb");
if(fr==NULL)
{
puts("文件尚未写入，请写入文件!");
exit(0);
}
for(i=0;i<3;i++)
{
fread(gilename[i],sizeof(gilename[i]),1,fr);
}
fclose(fr);
printf("文件读取成功!\n");
break;
}
case 1:
{
InitDSTable(&T[0]);
printf("\n欢迎进入文件A的动态查找表\n");
fq=fopen(gilename[0],"rb");
if(fq==NULL)
{
printf("\n打开文件失败,程序自动退出! \n");
exit(0);
}
fread(&m,sizeof(int),1,fq);
for(i=0;i<m;i++)
{
fread(&group[i],sizeof(ElemType),1,fq);
}
fclose(fq);
printf("请输入A or B or C选择:");
scanf("%c",&c); getchar();
switch(c)
{
case 'A':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertDSTable(&T[0],group[i]);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时: %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[0]);
}
break;
case 'B':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertAVL(&T[0],group[i],&tall);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时: %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[0]);
}
break;
case 'C':
{
for(i=0;i<m;i++)
{
InsertDSTable(&T[0],group[i]);
}
printf("\n请输入你要删除的学生学号:");
scanf("%d",&number);
if(DeleteDSTable(&T[0],number))
{
Print(T[0]);
printf("\n删除成功\n");
}
}
break;
}
}
break;
case 2:
{
InitDSTable(&T[1]);
printf("\n欢迎进入文件B的动态查找表\n");
fq=fopen(gilename[1],"rb");
if(!fq)
{
printf("\n打开文件失败,程序自动退出!\n ");
exit(0);
}
fread(&m,sizeof(int),1,fq);
for(i=0;i<m;i++)
{
fread(&group[i],sizeof(group[i]),1,fq);
}
fclose(fq);
printf("请输入A or B or C选择:");
scanf("%c",&c); getchar();
switch(c)
{
case 'A':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertDSTable(&T[1],group[i]);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时: %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[1]);
}
break;
case 'B':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertAVL(&T[1],group[i],&tall);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时: %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[1]);
}
break;
case 'C':
{
for(i=0;i<m;i++)
{
InsertDSTable(&T[0],group[i]);
}
printf("请输入你要删除的学生学号:");
scanf("%d",&number);
if(DeleteDSTable(&T[1],number))
Print(T[1]);
}
break;
}
}
break;
case 3:
{
InitDSTable(&T[2]);
printf("%s",gilename[2]);
printf("\n欢迎进入文件C的动态查找表\n");
fq=fopen(gilename[2],"rb");
if(!fq)
{
printf("\n打开文件失败,程序自动退出! \n");
exit(0);
}
fread(&m,sizeof(int),1,fq);
for(i=0;i<m;i++)
{
fread(&group[i],sizeof(group[i]),1,fq);
}
fclose(fq);
printf("请输入A or B or C选择:");
scanf("%c",&c); getchar();
switch(c)
{
case 'A':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertDSTable(&T[2],group[i]);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时 : %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[2]);
}
break;
case 'B':
{
if (!QueryPerformanceFrequency(&frequency))
{
return -1;
}
QueryPerformanceCounter(&start); //开始计时
for(i=0;i<m;i++)
{
InsertAVL(&T[2],group[i],&tall);
}
QueryPerformanceCounter(&end); //结束计时
printf("\n此次查找耗时: %lf (us)微秒",(double)(end.QuadPart - start.QuadPart) / (double)frequency.QuadPart);
printf("\n学生的学号 姓名 性别 年龄为: \n");
Print(T[2]);
}
break;
case 'C':
{
for(i=0;i<m;i++)
{
InsertDSTable(&T[0],group[i]);
}
printf("请输入你要删除的学生学号:");
scanf("%d",&number);
if(DeleteDSTable(&T[2],number))
Print(T[2]);
}
break;
}
}
break;
case 4:
{
fr=fopen("fname","wb");
for(j=0;j<3;j++)
{
printf("请输入第 %d 个动态查找表的表长:",j+1);
scanf("%d",&n);
InputData(block,n);
printf("请输入文件%c的文件名:",'A'+j);
scanf("%s",filename[j]);
fwrite(filename[j],sizeof(filename[j]),1,fr);
fp=fopen(filename[j],"wb");
if(fp==NULL)
{
printf("打开文件失败,程序自动退出! ");
exit(0);
}
fwrite(&n,sizeof(int),1,fp);
for(i=0;i<n;i++)
{
fwrite(&block[i],sizeof(block[i]),1,fp);
}
fclose(fp);
}
fclose(fr);
break;
}
case 5:
{
printf("欢迎使用,再见!");
exit(0);
}
}
printf("\n是否继续<Y,N>:");
scanf("%s",decided);
if(strcmp(decided,"N")==0)
{
printf("欢迎使用,再见!\n");
exit(0);
}
else
{
continue;
}
}
return(0);
}
有些隐形的漏洞还需好好维护修改。
七【上机实验中的其他它问题及心得】
这是本学期学完数据结构后的一次相对长一些的程序，我之所以选择这道题目是因为我感觉我二叉树这部分掌握得不太好，想以此来练习并好好学习一下二叉树部分的知识，弥补在学习上的不足。通过此次的上机练习我的感触颇多，数据结构真的是一门很有用的课程，它能教会我们如何编程，如何去解决一个问题，及解决问题的基本思想，在拿到一个问题时该如何的去分析，如何去思考，最后并编写代码解决它。
首先一点通过此次试验，使我清楚了解决一个问题的基本流程，从拿到问题时的需求分析，然后确定处理问题的逻辑结构，从而确定相应的存储结构，最后在逻辑结构、存储结构的基础上确定一套算法，最后编码、调试并实现它，还有一点就是系统的维护，程序的健壮性也很重要。
然后一点是我认识到了学习数据结构不能只靠看书，只停留在听和看的基础上，学程序是一个实践性的过程，必须注重练习和实践，一步一个脚印，必须得靠多调试、多练习、多去思考和总结才能一步一步的是自己成熟起来，在编程中找到信心和兴趣，进而积极主动的去编程，在练中学，去总结思考，才能学有所获。要多做项目、多做应用、多去实践，总之就是要注重实践和调试程序。
在学习过程中基础上一定要理解好算法的思想，理解过程中要多去画画图，通过给变量赋值一步一步的去看程序，不要放过每一个语句。书中的代码写得很经典，需要靠自己一步一步的去分析，才能看懂。看懂并理解思想后该做的就是背着书在电脑上去编写代码，编写过程中很难一蹴而就，要别着急看看出错的原因，多使用单步调试，一步一步的运行并看看相关变量可能出现的值，是否与预期相符合，若不符合是什么原因造成的，就找到了分析的方法了，在一步一步的走下去。有时候编程出现思路不清晰时可以在回到起点去理清思路后再去编写程序，不要盲目的编程一头雾水的编下去，只会使自己错的更离谱。就是一定要有信心要坚持不懈的编下去。有问题是可以向同学请教或上网查询资料，大学中需要一个很重要的能力便是自主学习的能力，老师始终只能是一个引导作用必须得靠自己内因的驱动才能学有所成，才能做学习的主人。
就像数学可以奠定我们理性的思考方法，数据结构与算法这门课在培养我们“像计算机一样”思考问题中有着重要的作用。数据结构的知识让我们知道如何把需要处理的内容、对象用不同的组织方式表述成计算机可以理解的范畴，从而能够进行后期处理；而算法，尤其是好的算法，为我们提供了高效解决这些问题的方法。正如学习数学时需要有所积累才能有所创新一样，而这门课就给我们打下了坚实的基础，所以学好数据结构特别重要。
好好编程吧，学计算机的编程能力提不高就是寸步难行，我以后一定会好好编程的，相信一定会在编程过程中找到快乐，找到兴趣，不再感到那么的枯燥无趣，学的不再那么被动消极。
-
数据结构查找实验报告
实验题91设计一个程序exp91cpp输出在顺序表36210185749中采用顺序方法找关键字5的过程程序如下文件名exp91cp…
-
数据结构实验报告 实验五 查找算法
昆明理工大学信息工程与自动化学院学生实验报告201201学年第一学期课程名称数据结构开课实验室年月日一实验内容查找算法其中线性表的…
-
数据结构查找实验报告
实验报告课程名称实验项目数据结构查找姓名xx专业班级学号网络工程网络132130402xxxx计算机科学与技术学院实验教学中心20…
-
数据结构查找算法实验报告
100410528孙晨添数据结构实验报告实验第四章实验简单查找算法一需求和规格说明查找算法这里主要使用了顺序查找折半查找二叉排序树…
-
《数据结构》实验报告查找
实验四查找一实验目的1掌握顺序表的查找方法尤其是折半查找方法2掌握二叉排序树的查找算法二实验内容1234建立一个顺序表用顺序查找的…
-
数据结构实验报告-静态查找表中的查找
数据结构实验实验一静态查找表中的查找一、实验目的：1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查…
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构-实验8查找的算法
81实现顺序查找的算法一实验目的1熟悉掌握各种查找方法深刻理解各种查找算法及其执行的过程2学会分析各种查找算法的性能二实验内容81…
- 数据结构图实验报告
-
焦作数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
-
信息检索实验报告
信息检索课程结业报告姓学信息检索与web搜索应用背景及概念信息检索InformationRetrieval是指信息按一定的方式组织…