一、 设计人员相关信息
1. 设计者姓名、学号和班号:12地信李晓婧 12012242983
2. 设计日期:2014.
3. 上机环境:VC++6.0
二、 程序设计相关信息
1. 实验题目:编写一个程序,实现单链表的各种基本运算(假设单链表的元素类型为char),并在此基础上设计一个程序,完成如下功能:
(1) 初始化单链表;
(2) 采用尾插法依次插入元素a,b,c,d,e;
(3) 输出单链表
(4) 输出单链表长度
(5) 判断单链表是否为空
(6) 输出单链表第3个元素
(7) 输出元素a的位置
(8) 在第4个元素位置上插入元素f
(9) 输出单链表
(10)删除第三个元素
(11)输出单链表
(12)释放单链表
2. 实验项目组成:
(1) 插入和删除节点操作
(2) 建立单链表
尾插法建表
(3) 线性表基本运算在单链表中的实现
初始化线性表
销毁线性表
判断线性表是否为空表
求线性表的长度
3. 实验项目的程序结构(程序中的函数调用关系图):
4. 实验项目包含的各个文件中的函数的功能描述:
l 尾插法建表CreateListR:将新节点插到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾节点。
l 初始化线性表InitList:该运算建立一个空的单链表,即创建一个头节点;
l 销毁线性表DestroyList:释放单链表占用的内存空间,即逐一释放全部节点的空间;
l 判断线性表是否为空表ListEmpty:若单链表没有数据节点,则返回真,否则返回假;
l 求线性表的长度ListLength:返回单链表中数据节点的个数;
l 输出线性表DispList:逐一扫描单链表的每个数据节点,并显示各节点的data域值;
l 求线性表中某个数据元素值GetElem:在单链表中从头开始找到第i个节点,若存在第i个数据节点,则将其data域值赋给变量e;
l 按元素值查找LocateElem:在单链表中从头开始找第一个值域与e相等的节点,若存在这样的节点,则返回逻辑序号,否则返回0;
l 插入数据元素ListInsert:先在单链表中找到第i-1个节点*p,若存在这样的节点,将值为e的节点*s插入到*p节点的后面;
l 删除数据元素ListDelete:先在单链表中找到第i-1个节点*p,若存在这样的节点,且也存在后继节点*q;删除*q节点,返回TRUE;否则返回FALSE表示参数i错误。
5. 算法描述或流程图:
6. 实验数据和实验结果:
7. 出现的问题及解决方法:
问题1:
解决方法:
问题2:
解决方法:
void DispList(LinkList*L)/*输出表*/
{
LinkList*p=L->next; //p指向开始节点
while(p!=NULL) //p不为NULL,输出*p节点的data域
{printf("%c",p->data); 将%d改为%c
p=p->next; //p移向下一个节点
}
printf("\n");
}
三、 程序盘
提交的程序盘应包含全部的源程序清单和可执行文件。
第二篇:数据结构动态查找表实验报告
成都信息工程学院计算机系
课程实验报告
一【上机实验目的】
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);
}
有些隐形的漏洞还需好好维护修改。
七【上机实验中的其他它问题及心得】
这是本学期学完数据结构后的一次相对长一些的程序,我之所以选择这道题目是因为我感觉我二叉树这部分掌握得不太好,想以此来练习并好好学习一下二叉树部分的知识,弥补在学习上的不足。通过此次的上机练习我的感触颇多,数据结构真的是一门很有用的课程,它能教会我们如何编程,如何去解决一个问题,及解决问题的基本思想,在拿到一个问题时该如何的去分析,如何去思考,最后并编写代码解决它。
首先一点通过此次试验,使我清楚了解决一个问题的基本流程,从拿到问题时的需求分析,然后确定处理问题的逻辑结构,从而确定相应的存储结构,最后在逻辑结构、存储结构的基础上确定一套算法,最后编码、调试并实现它,还有一点就是系统的维护,程序的健壮性也很重要。
然后一点是我认识到了学习数据结构不能只靠看书,只停留在听和看的基础上,学程序是一个实践性的过程,必须注重练习和实践,一步一个脚印,必须得靠多调试、多练习、多去思考和总结才能一步一步的是自己成熟起来,在编程中找到信心和兴趣,进而积极主动的去编程,在练中学,去总结思考,才能学有所获。要多做项目、多做应用、多去实践,总之就是要注重实践和调试程序。
在学习过程中基础上一定要理解好算法的思想,理解过程中要多去画画图,通过给变量赋值一步一步的去看程序,不要放过每一个语句。书中的代码写得很经典,需要靠自己一步一步的去分析,才能看懂。看懂并理解思想后该做的就是背着书在电脑上去编写代码,编写过程中很难一蹴而就,要别着急看看出错的原因,多使用单步调试,一步一步的运行并看看相关变量可能出现的值,是否与预期相符合,若不符合是什么原因造成的,就找到了分析的方法了,在一步一步的走下去。有时候编程出现思路不清晰时可以在回到起点去理清思路后再去编写程序,不要盲目的编程一头雾水的编下去,只会使自己错的更离谱。就是一定要有信心要坚持不懈的编下去。有问题是可以向同学请教或上网查询资料,大学中需要一个很重要的能力便是自主学习的能力,老师始终只能是一个引导作用必须得靠自己内因的驱动才能学有所成,才能做学习的主人。
就像数学可以奠定我们理性的思考方法,数据结构与算法这门课在培养我们“像计算机一样”思考问题中有着重要的作用。数据结构的知识让我们知道如何把需要处理的内容、对象用不同的组织方式表述成计算机可以理解的范畴,从而能够进行后期处理;而算法,尤其是好的算法,为我们提供了高效解决这些问题的方法。正如学习数学时需要有所积累才能有所创新一样,而这门课就给我们打下了坚实的基础,所以学好数据结构特别重要。
好好编程吧,学计算机的编程能力提不高就是寸步难行,我以后一定会好好编程的,相信一定会在编程过程中找到快乐,找到兴趣,不再感到那么的枯燥无趣,学的不再那么被动消极。