HUNAN UNIVERSITY
课程实验报告
题目:BST的构建与查找
学生姓名:
学生学号:
专业班级:
指导老师:李晓鸿老师
完成日期:20##年11月22号
一. 需求分析
输入形式
在该程序中,用户需要输入节点个数和节点数据以及查找的节点,节点数据间使用空格隔开,当用户输入有误时提示用户输入错误并重新输入。具体格式如下:
请输入节点个数:
请依次节点数据:
请输入需查找的节点:
输出形式
若用户需查找的节点查找成功,则输出查找成功以及比较的次数,若查找不成功则输入查找失败,具体格式如下:
查找成功 ,比较次数为__
查找失败, 比较次数为__
程序功能
该程序可以通过使用二叉链表构建一个BST,并实现BST内节点的插入和查找功能
测试数据
1.请输入节点个数:8
请依次节点数据:12,4,35,78,56,34,89,0
请输入需查找的节点:89
查找成功,比较次数为3
2.请输入节点个数:8
请依次节点数据:12,4,35,78,56,34,89,0
请输入需查找的节点:678
查找失败,比较次数为3
3.请输入节点个数:c
输入有误请重新输入
4. 请输入节点个数:8
请依次节点数据:12,4,35,78,56,&,89.3,A
输入有误,请重新输入
二. 概要设计
抽象数据类型
1.在本程序中,需要对插入的节点进行检索,而BST的插入和检索的速率都是很高的,所以我们选用构建BST的方法来解决这项问题;
2.由用户输入的节点个数及节点数据均为正整数,可使用整型数据进行存储,并构建一个BST存储这些节点数据;
3.为了节约空间,使用二叉链表实现BST;
4.为了能查询表中数据,定义一个二叉树节点类,其ADT设计如下:
数据类型:整型数据
数据关系:二叉树所对应的数据关系
基本操作:
int val() ; //返回结点的数值
void setLeft(Node* ) ; //设置左结点
void setRight(Node* ); //设置右结点
Node* left()const; //返回左结点
Node* right()const ;//返回右结点
4.为了存储这些数据,构建一个二叉查找树,其ADT设计如下:
数据类型:整型数据
数据关系:二叉树所对应的数据关系
基本操作:
void clear();//初始化操作
bool insert(const Elem&);//插入元素的操作
bool find(const Elem&)const;//查找元素的操作
算法基本思想
该算法主要包括表的构建和查询两项:
① 在表的构建上,通过用户输入的数据,将第一个输入的节点数据存入根节点中,从第二个节点元素开始,与根节点数据进行比较,如果该元素大于根节点的值,则与根节点的右子节点相比较,若右子节点为空,则将该元素存入这个节点,若不为空,则将该右子节点视为根节点,重复上述步骤。而若该元素小于根节点的值,则与根节点左子节点相比较,若左子节点为空,则将该元素存入这个节点,若不为空,则将该左子节点视为根节点,重复上述步骤。直到所有的输入的元素都存进表中为止;
② 在表的查询上,通过用户输入的查询的数值,将该数据与已建好的表的根节点相比较,比较次数+1,当两个数相等时,输出查找成功,比较次数为1。当该数小于根节点的数时,若左子节点不为空,则视根节点的左子节点为根节点,将该数据与新的根节点相比较,比较次数加1,重复上述步骤,直到左子节点为空。当该数大于根节点的数时,若右子节点不为空,则视根节点的右子节点为根节点,将该数据与新的根节点相比较,比较次数加1,重复上述步骤,直到两个数相等或者直到子节点为空时结束循环。若找到相等的元素,则输出查找成功以及相应的比较次数,若子节点为空时仍然没有查找到该元素,则输出未查找到该元素以及相对应的查找次数;
程序基本流程
本程序主要包括输入、 构建BST 、查询 和输出四个模块,其流程图如下:
c
三. 详细设计
物理数据类型
1. 用户输入的节点个数使用int型数据进行存储,用户输入的节点的数据通过构建一个Node类进行存储,Node类详细ADT设计如下:
class Node
{
private:
int data;//节点数据
Node *p1;//指向左子节点的指针
Node *p2;//指向右子节点的指针
public:
int val() {return data;} ;//返回结点的数值
void setLeft(Node* it){p1=it;} ; //设置左结点
void setRight(Node* it ){p2=it}; //设置右结点
Node* left()const{return p1;}; //返回左结点
Node* right()const{return p2;} ;//返回右结点
}
2. 采用二叉链表实现BST,二叉链表ADT设计如下:
class BST
{
private:
Node* root;//根节点
public:
BST(){root=NULL;}//构造函数
~BST(){delete roop;}//析构函数
void clear()
{ root=NULL;}//初始化操作
bool insert(const int& it)//插入操作
{
Node *subroot1=root;
Node *subroot2=root;
if(root==NULL){root=new Node(it);}//传给根节点值
while(subroot1!=NULL)
{
subroot2=subroot1;
if(it<subroot1.val())
subroot1=subroot1.Left();
else
subroot1=subroot1.Right();
}
if(subroot2.val()>it)
subroot2.setLeft(new Node (it));
//设置左子节点
else
subroot2.setRight(new Node (it));
//设置右子节点
return true;
}
bool find(int& it)//查找操作
{
Node* subroot=root;
int count=0;//
while(subroot!=NULL)
{
if(it==subroot.val())
{count++;return true;}//查找成功
else if(it<subroot.val())
{subroot=subroot.Left();count++;}
//在左子节点进行查找
else if(it>subroot.val())
{subroot=subroot.Right();count++;}
//在右子节点进行查找
}
return false;//查找失败
}
}
算法具体步骤
本算法主要包括以下几个模块:
1. 输入模块:
cin>>n;
for(int i=0;i<n;i++)
cin>>num;
cin>>FindNum;
2. 构建BST模块:
for(int i=0;i<n;i++)
Tree.insert(num);//
3. 查找模块:
使用find函数查询该BST中是否有节点的数据为FindNum
4.输出模块:
if(Tree.find(FindNum)==true)
cout<<”查找成功,比较次数为“<<count<<”次”;
if(Tree.find(FindNum)==false)
cout<<”查找失败,比较次数为“<<count<<”次”;
函数关系调用
建表 for(int i=0;i<n;i++)
Tree.insert(num);
算法
true 输出“查找成功“及比较次数
查找 Tree.find(FindNum)
false 输出“查找失败“及比较次数
算法时空分析
n个元素的BST高度约为log2n,而该算法的插入的最坏情况是在BST最底端进行插入,所以插入的时间复杂度为Θ(log n),当用户输入规模为n个时,插入的算法时间复杂度为Θ(n log n)。查找的时间复杂度最坏情况也是在最底端找到或者查找失败,时间复杂度为Θ(log n),
所以算法总时间复杂度为Θ(n log n)。
输入输出格式
输入:
请输入节点个数:8
请依次节点数据:13 58 42 19 22 44 100 65
请输入需查找的节点:
42
13
12
输出:
查找成功,比较次数为3
查找成功,比较次数为1
查找失败,比较次数为3
源代码:
#include<iostream>
using namespace std;
class Node
{
private:
double data;
Node *p1;
Node *p2;
public:
Node(double it){ data = it; p1 = NULL; p2 = NULL; };
~Node(){ delete[]p1; delete[]p2; };
void setLeft(Node* item){ p1 = item; }; //设置左结点
void setRight(Node* item){ p2 = item; }; //设置右结点
Node* Left()const{ return p1; };//返回左结点
Node* Right()const{ return p2; };//返回右结点
double val()
{
return data;
};//返回结点的数值
};
class BST
{
private:
Node* root;//根节点
public:
int count;
BST(){ root = NULL; count = 0; }//构造函数
//~BST(){ delete[]root; }//析构函数
void clear()
{
root = NULL;
}//初始化操作
void insert(const double& it)//插入操作
{
if (root == NULL){ root = new Node(it); }//传给根节点值
Node *subroot1 = root;
Node *subroot2 = root;
while (subroot1 != NULL)
{
subroot2 = subroot1;
if (it<subroot1->val())
subroot1 = subroot1->Left();
else
subroot1 = subroot1->Right();
}
if (subroot2->val()>it)
subroot2->setLeft(new Node(it));
//设置左子节点
else
subroot2->setRight(new Node(it));
//设置右子节点
}
int find(double& it)//查找操作
{
count = 0;
Node* subroot = root;
while (subroot != NULL)
{
if (it == subroot->val())
{
count++; return 1;
}//查找成功
else if (it<subroot->val())
{
subroot = subroot->Left(); count++;
}
//在左子节点进行查找
else if (it>subroot->val())
{
subroot = subroot->Right(); count++;
}
//在右子节点进行查找
}
return 0;//查找失败
}
};
int judge()
{
//对输入的合法性进行判断并返回有效的输入
int temp;
cin.sync(); //清空输入流缓冲区
cin >> temp;
while (1)
{
if (cin.fail() || cin.bad() || cin.get() != '\n') //验证输入是否合法,其中cin.fail()和cin.bad()解决输入字符串和溢出的问题
cout << "输入有误,请重新输入:\n"; //cin.get()检查输入流中是否还有字符(如果有就表示输入的是形如123r或12.3的错误
else break; //输入合法则跳出循环
cin.clear(); //清空输入流缓冲区标志位,以免影响下次输入
cin.sync();
cin >> temp;
}
return temp;
}
int main()
{
BST Tree;
while (1)
{
Tree.count = 0;
int n; double num; double FindNum;
cout << "请输入节点个数:\n";
n = judge();
if (n == -1)
return 0;
cout << "请输入个节点的数据:\n";
for (int i = 0; i < n; i++)
{
cin >> num;
Tree.insert(num);
}
cout << "请输入要查询的节点:\n";
cin>>FindNum;
if (Tree.find(FindNum) == 1)
cout << "查找成功,比较次数为" << Tree.count << "次\n\n";
else if (Tree.find(FindNum) == 0)
cout << "查找失败, 比较次数为" << Tree.count << "次\n\n";
system("pause>>NUL");
}
}
第二篇:数据结构动态查找表实验报告
成都信息工程学院计算机系
课程实验报告
一【上机实验目的】
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);
}
有些隐形的漏洞还需好好维护修改。
七【上机实验中的其他它问题及心得】
这是本学期学完数据结构后的一次相对长一些的程序,我之所以选择这道题目是因为我感觉我二叉树这部分掌握得不太好,想以此来练习并好好学习一下二叉树部分的知识,弥补在学习上的不足。通过此次的上机练习我的感触颇多,数据结构真的是一门很有用的课程,它能教会我们如何编程,如何去解决一个问题,及解决问题的基本思想,在拿到一个问题时该如何的去分析,如何去思考,最后并编写代码解决它。
首先一点通过此次试验,使我清楚了解决一个问题的基本流程,从拿到问题时的需求分析,然后确定处理问题的逻辑结构,从而确定相应的存储结构,最后在逻辑结构、存储结构的基础上确定一套算法,最后编码、调试并实现它,还有一点就是系统的维护,程序的健壮性也很重要。
然后一点是我认识到了学习数据结构不能只靠看书,只停留在听和看的基础上,学程序是一个实践性的过程,必须注重练习和实践,一步一个脚印,必须得靠多调试、多练习、多去思考和总结才能一步一步的是自己成熟起来,在编程中找到信心和兴趣,进而积极主动的去编程,在练中学,去总结思考,才能学有所获。要多做项目、多做应用、多去实践,总之就是要注重实践和调试程序。
在学习过程中基础上一定要理解好算法的思想,理解过程中要多去画画图,通过给变量赋值一步一步的去看程序,不要放过每一个语句。书中的代码写得很经典,需要靠自己一步一步的去分析,才能看懂。看懂并理解思想后该做的就是背着书在电脑上去编写代码,编写过程中很难一蹴而就,要别着急看看出错的原因,多使用单步调试,一步一步的运行并看看相关变量可能出现的值,是否与预期相符合,若不符合是什么原因造成的,就找到了分析的方法了,在一步一步的走下去。有时候编程出现思路不清晰时可以在回到起点去理清思路后再去编写程序,不要盲目的编程一头雾水的编下去,只会使自己错的更离谱。就是一定要有信心要坚持不懈的编下去。有问题是可以向同学请教或上网查询资料,大学中需要一个很重要的能力便是自主学习的能力,老师始终只能是一个引导作用必须得靠自己内因的驱动才能学有所成,才能做学习的主人。
就像数学可以奠定我们理性的思考方法,数据结构与算法这门课在培养我们“像计算机一样”思考问题中有着重要的作用。数据结构的知识让我们知道如何把需要处理的内容、对象用不同的组织方式表述成计算机可以理解的范畴,从而能够进行后期处理;而算法,尤其是好的算法,为我们提供了高效解决这些问题的方法。正如学习数学时需要有所积累才能有所创新一样,而这门课就给我们打下了坚实的基础,所以学好数据结构特别重要。
好好编程吧,学计算机的编程能力提不高就是寸步难行,我以后一定会好好编程的,相信一定会在编程过程中找到快乐,找到兴趣,不再感到那么的枯燥无趣,学的不再那么被动消极。