C
CDlee
Unregistered / Unconfirmed
GUEST, unregistred user!
<见笑拉，只是想交几个学c++的朋友;我要读大三拉。另外，暑假我在武汉呢，
准备用delphi做个中学试题数据库，希望能得到高手指点，QQ:103263223 .027-87436014 小李>
数据结构课程设计报告
一 池塘风雨
本程序的实现，采用较为简单的处理方法。
数据结构有：
1． 一个windows窗体类，内有menu菜单和一个时钟；
2． 数组，4组，分别记录雨点的坐标和池塘涟漪的坐标。
池塘中的景物有：
1． 芦苇群 ：静物，坐标是随即散列；
2． 荷叶 ：静物；
3． 雨水 ：动画，坐标随即散列；
4． 池水涟漪：动画，坐标随即散列。
动画的实现方法，主要是察除法。算法可见程序的详细注释。
平台是Boland C++Bilder 6.0 。遗憾的是，看了几天，也未能把程序写成多线程编程，而对于自然形态的刻画，也没有掌握较好的算法，感觉本程序的收获不大。
//---------------------------------------------------------------------------
//rain.h
//该文件定义一个窗体类和该类的一个外部指针变量
//////////////////////////////////////////////////////////////////////////////
#ifndef rainH
#define rainH
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
#include <Menus.hpp>
#include <OleCtnrs.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
TMainMenu *MainMenu1;
TMenuItem *N1;
TMenuItem *N2;
TMenuItem *N3;
TMenuItem *N4;
TMenuItem *N5;
TTimer *Timer1;
void __fastcall N2Click(TObject *Sender);
void __fastcall N5Click(TObject *Sender);
void __fastcall Timer1Timer(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
//////////////////////////
//rain.cpp
//
//该文件具体实现在窗体上绘制池塘风雨的动画
///////////////////////////////////////////////////////////////////////////////
#include <vcl.h>
#pragma hdrstop
#include "rain.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int x[80];//雨点的x坐标
int y[80];//雨点的y坐标
int icount=0;//时钟控制变量
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
//全局函数
//初始化雨点的坐标，且保证不落入保护区域（该区域绘制一荷叶）
//////////////////////////////////////////////////////////////////////////////
void PreDrawRain()
{
for(int i=0;i<80;i++)
{
x=random(1000);
y=random(800);
if(x>100&&x<200&&y>350&&y<400)
y-=100;
}
}
//--------------------------------------------------------------------------
//全局函数
//绘制雨点，同时对时钟控制变量增1操作
//////////////////////////////////////////////////////////////////////////////
void DrawRain()
{
for(int i=0;i<80;i++)
{
Form1->Canvas->MoveTo(x,y);
Form1->Canvas->LineTo(x-5,y+5);
}
icount++;
}
//---------------------------------------------------------------------------
//全局函数
//动画“雨”和“池塘涟漪”的实现
/////////////////////////////////////////////////////////////////////////////
void Draw()
{
int dx,dy;//涟漪扩充增量
int x0[8];//涟漪x坐标
int y0[8];//涟漪y坐标
for(int j=0;j<6;j++)
{
for(int i=0;i<8;i++){
x0=100+random(400);
//涟漪散落范围：
y0=100+random(300);
// x：100~500，y：100~400
if(x0>100&&x0<200&&y0>350&&y0<400)
y0-=100;x0+=200;
}
for(dx=random(2),dy=random(4);dx<10;dx+=1,dy++)
{
for(int i=0;i<8;i++)
{//第i次绘制涟漪
Form1->Canvas->Pen->Color=clMedGray;
Form1->Canvas->Ellipse(x0-2*dx,y0-dx,x0+2*dx,y0+dx);
Form1->Canvas->Ellipse(x0-2*dx-2,y0-dx-1,x0+2*dx+2,y0+dx+1);
}
PreDrawRain();
DrawRain();
Sleep(200);
for(int i=0;i<8;i++)
{//第i次察除涟漪
Form1->Canvas->Pen->Color=clSkyBlue;
Form1->Canvas->Ellipse(x0-2*dx,y0-dx,x0+2*dx,y0+dx);
Form1->Canvas->Ellipse(x0-2*dx-2,y0-dx-1,x0+2*dx+2,y0+dx+1);
}
DrawRain();
}
}
}
//---------------------------------------------------------------------------
//成员函数
//退出执行程序
/////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::N2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
//成员函数
//时钟开始，程序从新执行
/////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::N5Click(TObject *Sender)
{
Timer1->Enabled=true;
//重新开始，时钟可访问
}
//---------------------------------------------------------------------------
//成员函数：时钟函数
//初始化“池塘”环境，调用动画函数
//////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::Timer1Timer(TObject *Sender)
{
int i,x,y;//x，y为芦苇的坐标
Canvas->Pen->Color=clBlack;
Canvas->Brush->Color=clSkyBlue;
//池塘之水
Canvas->FloodFill(100,400,clBlack, fsBorder);
//绘制荷叶
Canvas->Pie(105,355,195,395,195,355,195,390);
Canvas->Brush->Color=clGreen;
Canvas->FloodFill(130,360,clBlack,fsBorder);
//荷叶旁静芦苇（一棵）,突出立体感
Canvas->Pen->Color=clGreen;
x=170;
y=325;
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
//散列芦苇：池塘左方15棵
for(i=0;i<15;i++)
{
x=random(150);
y=random(400);
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
}
//散列芦苇：池塘下方15棵
for(i=0;i<15;i++)
{
x=50+random(400);
y=400+random(100);
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
}
Canvas->Pen->Color=clBlack;
Canvas->Brush->Color=clSkyBlue;
//绘制动画
Draw();
//如果时钟控制变量超值，时钟无效
if(icount>200)
{
icount=0;
Timer1->Enabled=false;
}
}
//---------------------------------------------------------------------------
二 魔王语言
本程序的实现，没有多少扩展。
对于魔王的语言，我是这样理解的。对于一串字符串（魔王语言），遇到成对（）则使用规则2：（θδ1δ2…δn）→θδnθδn-1…θδ1θ，而遇到大写字母A和B，则使用规则1的两个特殊（具体）形式：（1）B→tAdA （2）A→sae ，以此翻译。
由形式规则2知，（……）本质上是一字符串，故多重括号（…（……）…）应是魔王语言，但因时间等因素，本程序的算法不能翻译这类语言，只能胜任一重括号或无括号的情况；但是，本程序对包括多重括号在内的魔王语言输入错误，具有较好的识别性。
本程序的数据结构为：
1． 数组，存储魔王语言和人类语言，且是类Langvage 的保护（protected）成员变量；
2． 堆栈，对于括号，检查魔王语言的错误；
3． 类Langvage ，它的结构为：
该类中，本应有人类语言到魔王语言的翻译函数，这样它才是完整的。时间不够，所以并未添置。
对于算法，就是两个规则的反映。可祥见程序的详细注释。
平台是 Visual C++.NET，收获就是，对于字符串的操作，这样的练习是有益的。
//////////////////////////////////
//langvage.h
//类langvage的声明
/////////////////////////////////////////////////////////////////////////////////////////
#pragma once
//n默认的魔王语言最大长度
const n=100;
class Langvage
{
public:
Langvage(void);
~Langvage(void);
protected:
char lgv[n];
char lgvH[n];
int size;
int sizeH;
public:
void LgvGtoH(void);
void PrintLgvH(void);
void InitLgvG(void);
};//可见于类langvage的结构图
////////////////////////////////////
//langvage.cpp
//类langvage的定义实现
////////////////////////////////////////////////////////////////////////////////////////
#include "langvage.h"
#using <mscorlib.dll>
#include<iostream.h>
Langvage::Langvage(void)
{
size=0;
sizeH=0;
}
Langvage::~Langvage(void)
{
}
///////////////////////////////////////
//public：翻译魔王语言
//基本思路是：
// 1。魔王语言有无错误，若有，打印错误，返回；否则，转2；
// 2。是否有括号？若无，直接从lgv[n]翻译到lgvH[n]，否则，设置中间数组，先翻译去掉括号，再行翻//译。
//原则是魔王语言lgv不被破坏。
////////////////////////////////////////////////////////////////////////////////////////////////
void Langvage::LgvGtoH(void)
{
int i,j,k1=-1,k2=-1;//k1追踪（的位置，k2追踪）的位置
char cha;//记录（后的第一个字符
char array[100],stack[50];//中间字符数组和堆栈
int karray=0,top=-1;//karray记录中间数组的实际长度
int k=0;//k标志是否有括号
for(i=0;i<size;i++)
if(lgv=='('||lgv==')') break;
if(i==size) goto here;//goto语句，说明魔王语言无括号
//否则，判断有无错误
for(i=0;i<size;i++)
{
if(top==-2)
{
cout<<"Langvage Error with '(' or ')' !"<<endl;
return;
}
if(lgv=='(')
{
top++;stack[top]='(';
}
else
if(lgv==')') top--;
}
if(top!=-1) { cout<<"Langvage Error with '(' or ')' !"<<endl;return;}
for(i=0;i<size;i++)
{
if(lgv=='(') k1=i;
if(lgv==')') k2=i;
}
//设置k为1，魔王语言有括号且无错误
k=1;
if(k2==k1+1)//如果括号为空，既是 ：……（）……
{
j=0;
for(i=0;i<size;i++)
{
if(i==k1) i+=2;
array[j]=lgv;
karray++;
j++;
}
goto here;
}
//括号不为空，设置cha，先翻译到array[n]
cha=lgv[k1+1];
for(i=0;i<k1;i++)
{
array=lgv;karray++;
}//i==k1
array=cha;i++;karray++;
for(j=k2-1;j>k1+1;j--)
{
array=lgv[j];
i++;karray++;
array=cha;
i++;karray++;
}
for(j=k2+1;j<size;j++)
{
array=lgv[j];
i++;karray++;
}
//翻译已无括号的魔王语言
here:
if(k)//如果原魔王语言有括号，从array翻译
for(j=0,i=0;j<karray;j++)
{
switch(array[j])
{
case 'B':
{
lgvH='t';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
lgvH='d';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
case 'A':
{
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
default:
{ lgvH=array[j];i++;
sizeH++;}
}
}
else
{//原魔王语言无括号
for(j=0,i=0;j<size;j++)
{
switch(lgv[j])
{
case 'B':
{
lgvH='t';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
lgvH='d';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
case 'A':
{
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
default:
{ lgvH=lgv[j];i++;
sizeH++;}
}
}
}
}
//////////////////////////////////////
//public：打印人类语言
//根据约定，输出空格和换行字符
/////////////////////////////////////////////////////////////////////////////////////
void Langvage:
rintLgvH(void)
{
int i;
cout<<"----------------"<<endl;
for(i=0;i<sizeH;i++)//
{
switch(lgvH)
{
case '/':
cout<<'/0';break;
case '@':
cout<<endl;break;
default:
cout<<lgvH;
}
}
}
/////////////////////////////////////////
//public：魔王语言输入
// ’/’,’@’和’#’，是输入的事先约定，与魔王语言无关，起到输出控制作用
///////////////////////////////////////////////////////////////////////////////
void Langvage::InitLgvG(void)
{
char cha;
int i=0;
cout<<"请输入魔王语言，'/'为输入空格，'@'为输入换行符，'#' 为退出符:"<<endl;
cin>>cha;
while(1)
{
if(cha=='#')
return;
lgv=cha;
i++;
size++;
cin>>cha;
}
}
/////////////////////////////////////////////
//fmain.cpp
//主函数，设置菜单界面，测试类langvage
///////////////////////////////////////////////////////////////////////////////////////
#include<iostream.h>
#include"Langvage.h"
void main()
{
char ch;
while(1)
{
cout<<"---------------------------------------------------------------------"<<endl;
cout<<"If you want to exit,input e ,or input another key to come in:"<<endl;
cin>>ch;
cout<<"---------------------------------------------------------------------"<<endl;
if(ch=='e') return;
Langvage lgv;
lgv.InitLgvG();
lgv.LgvGtoH();
lgv.PrintLgvG();
}
}
三 哈夫曼树编码/译码器
本程序实现了哈夫曼树编码/译码器。
本程序所用的数据结构为：
1． 二叉树 ，由类HfmTree 实现；
2． 数组，元素是类Narray 的对象，辅助建立哈夫曼树。
另外有若干可读写操作的文本文件。
本程序中主要的类的结构和关系为：
class Narray
class Node
class HfmTree
本程序的算法中，哈夫曼树的建立，是通过class Narray 的数组辅助实现的。在开始，数组中成员变量head指针指向已输入的字符接点(Node)，然后根据哈夫曼树的算法，生成一个新接点（Node），指向最小（key值）的两个接点，然后使其一的head指针指向新接点，另一个接点的标志i标志该接点退出数组。循环如此，建立哈夫曼树，我称这个方式为“挂葡萄式”。
对于编码/译码的实现，都是通过遍历哈夫曼树，跟踪实现的；遍历算法，都是中序递归的。可祥见与程序的实现部分。
通过本程序的设计，感觉收获不小。无论是程序设计技巧，还是对面向对象的理解，还是对c++的掌握（尤其文件操作），都感到这个程序写的有价值。
平台是Visual C++.NET 。
/////////////////////////////////////////////////////////////////////////////////
//hfmtree.h
//接点类Node，辅助类Narray，哈夫曼树类HfmTree的定义
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//默认的可哈夫曼编码的字符最大个数
const int charnum=60;
class Node {
float key;//字符的权值
char name;// 叶接点的名称
char *pstr;// 叶接点的编码代码
Node *left,*right;
public:
//初始化部分
Node(float Key=0,char Name='/0');
//virtual ~Node();
void Set(float Key,char Name);
void Set(const char * Pstr);
//获得封装值
float Getkey();
char Getname();
//需使用指针的引用，可做左值或右值
char *&Getpstr();
Node *&Getleft();
Node *&Getright();
};
class Narray {
public:
int i;//标志该head是否有意义
Node *head;
};
class HfmTree {
Node *head;// 哈夫曼树头指针
Node *p;//应用指针
int n;//叶接点个数
protected:
void MedVisit(Node *q, int &num);//中序遍历
void precoding(Node *q);//编码前设置
void nowcoding(Node *q,char ch);//编码，递归函数
void nowDcoding(Node *q,char &
ch);//译码，递归函数
public:
HfmTree();
void InithfmTree(int N);
void coding();//编码，tobetrans->codefile
void Decoding();//译码，->textfile
void print();//打印代码，每行50个代码->codeprint
void Treeprint();//打印哈夫曼树，treeprint
};
/////////////////////////////////////////////////
//hfmtree.cpp
//哈夫曼树编码/译码器所有功能的实现
///////////////////////////////////////////////////////////////////////////
#include"hfm.h"
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
//这儿是c++新标准，很高兴Visual C++.NET支持：）
#include<fstream>
using namespace std;
extern const int charnum;
//所需要的各文本文件
fstream from("tobetrans.txt",ios_base::in|ios_base:ut);
fstream to("codefile.txt",ios_base::in|ios_base:ut);
fstream to1("codefile.txt",ios_base::in|ios_base:ut);
fstream text("textfile.txt",ios_base::in|ios_base:ut);
fstream tree("treeprint.txt",ios_base::in|ios_base:ut);
static int iCount=0;
static char array[charnum];//编码跟踪变量和数组
Node::Node(float Key,char Name):
key(Key),name(Name)
,left(NULL),right(NULL),pstr(NULL)
{ }
void Node::Set(float Key,char Name)
{
key=Key;
name=Name;
}
void Node::Set(const char *Pstr)
{
pstr=new char[charnum];
strcpy(pstr,Pstr);
}
float Node::Getkey() { return key }
char Node::Getname() { return name;
}
char *&Node::Getpstr(){ return pstr;}
Node *&Node::Getleft() { return left;
}
Node *&Node::Getright() { return right;
}
HfmTree::HfmTree():head(NULL),p(NULL),n(0)
{ }
////////////////////////////////////
//public：建立哈夫曼树
// 说明见与开始部分
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::InithfmTree(int N)
{
n=N;
int i,k0,k1;//k0，k1记录最小两个接点的序号
float Key;
char Name;
if(N>charnum) { cerr<<"Error:You need too much Node!";
return;}
Narray array[charnum];//辅助数组的定义和初始化
for( i=0;i<charnum;i++)
{
array.head=NULL;
array.i=-1;
}
cout<<endl<<" 请依次相隔输入"<<N<<" 个数(权重)和他们的单字符名称："<<endl;
for(i=0;i<N;i++)
{
cin>>Key>>Name;
p=new Node(Key,Name);
if(!p) { cerr<<"Error:Cannot create Node!";
return;}
array.head=p;
array.i=1;
}
//跟踪辅助数组的挂接操作次数
int m=0;
while(m<N)
{
for(i=0;i<N;i++)
if(array.i==1)
{
Key=array.head->Getkey();//先取得第一个存在的接点权（和）值
break;
}
for(i=0;i<N;i++)
if((array.i==1)&&(Key>=array.head->Getkey()))
{
Key=array.head->Getkey();
k0=i;//记录最小接点的序号
}
for(i=0;i<N;i++)
if((i!=k0)&&(array.i==1))
{
Key=array.head->Getkey();//取得第二个存在的接点权（和）值
break;
}
for(i=0;i<N;i++)//
if((i!=k0)&&(array.i==1)&&(Key>=array.head->Getkey()))
{
Key=array.head->Getkey();
k1=i;//记录第二小接点的序号
}
if(k0==k1)
{
cout<<"Error with init_hfmtree !"<<endl;
return;
}
//申请新接点，赋值挂接
p=new Node(array[k0].head->Getkey()+array[k1].head->Getkey());
if(!p) { cerr<<"Error:Cannot create Node!";
return;}
if(array[k0].head->Getkey()<=array[k1].head->Getkey())
{
p->Getleft()=array[k0].head;
p->Getright()=array[k1].head;
}
else
{
p->Getleft()=array[k1].head;
p->Getright()=array[k0].head;
}
array[k0].head=p;
array[k1].i=0;
//辅助数组中剩余有意义接点
int ksize=0;
for(i=0;i<N;i++)
if(array.i==1) ksize++;
//如果为1，则建立完成，使head指针指向该有意义的接点
if(ksize==1)
{
int j;
for(i=0;i<N;i++)
if(array.i==1)
{
j=i;
break;
}
head=array[j].head;
return;
}
m++;
}
}
//////////////////////////////////////////////
//protected：中序遍历（递归）
//以凹凸表的形式把树输出，并把有关信息写入文本文件treeprint.txt
//num需使用引用，控制空格的输出
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::MedVisit(Node *q,int &num)
{
if(!q) { return;}
for(int i=0;i<num;i++)
cout<<'/0';
if(q->Getname()!='/0')
{
tree<<q->Getname();
tree<<"-'s key is ";
tree<<q->Getkey()
<<"and its code is "
<<q->Getpstr()<<endl;
}
if(q->Getname()!='/0')
cout<<q->Getname()<<"-'s key is "<<q->Getkey()<<endl;
else
cout<<"-'s key is "<<q->Getkey()<<endl;
num++;
MedVisit(q->Getleft(),num);
num--;
num++;
MedVisit(q->Getright(),num);
num--;
}
///////////////////////////////////////////
//protected：获得各字符的哈夫曼编码（递归）
//array跟踪遍历步骤，向左时加入‘0’，向右时加入‘1’，为叶接点时把编码赋值给pstr
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree:recoding(Node *q)
{
if(q->Getname()!='/0') {
array[iCount]='/0';
q->Getpstr()=new char[charnum];
strcpy(q->Getpstr(),array);
iCount--;
return;
}
array[iCount]='0';
iCount++;
precoding(q->Getleft());
array[iCount]='1';
iCount++;
precoding(q->Getright());
//这一步是必须的，它说明遍历在在中间接点由左转向右
if(q->Getname()=='/0') iCount--;
}
///////////////////////////////
//protected：对文本文件内容编码（递归）
/////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::nowcoding(Node *q,char ch)
{
if(!q) return;
if(q->Getname()==ch)
{
to<<q->Getpstr()<<endl;
return;
}
nowcoding(q->Getleft(),ch);
nowcoding(q->Getright(),ch);
}
void HfmTree::coding()
{
p=head;
if(!p) { cout<<"Error: please init_hfmtree first !"<<endl;return;
}
if(!from) { cerr<<" Error open file 'tobetrans.txt' !"<<endl;
return;}
if(!to) { cerr<<" Error open file 'codefile.txt' !"<<endl;
return;}
precoding(p);
p=head;
char ch;
while(!from.eof())
{
from>>ch;
nowcoding(p,ch);
}
}
///////////////////////////////////
//protected：对文本文件翻译（递归）
//对哈夫曼树搜索，‘0’向左，‘1’向右，到达叶接点写入字符名称
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::nowDcoding(Node *q,char &ch)
{
if(!q) return;
if(q->Getname()!='/0')
{
text<<q->Getname();
return;
}
if(ch=='0')
{
q=q->Getleft();
to1>>ch;
nowDcoding(q,ch);
}
else
if(ch=='1')
{
q=q->Getright();
to1>>ch;
nowDcoding(q,ch);
}
}
void HfmTree:ecoding()
{
char ch;
int i=0;
p=head;
if(!p) { cout<<"Error: please init_hfmtree first !"<<endl;return;
}
if(!to1) { cerr<<" Error open file 'codefile.txt' !"<<endl;
return;}
if(!text){ cerr<<" Error open file 'text.txt' !"<<endl;
return;}
to1>>ch;
while(!to1.eof())
{
nowDcoding(p,ch);
}
}
void HfmTree:rint()
{
fstream file("codefile.txt",ios_base::in|ios_base:ut);
if(!file) { cerr<<"Error:can't open codefile.txt !"<<endl;
return;}
char ch;
int i=0;
while(!file.eof())
{
file>>ch;
cout<<ch;
i++;
if(i==50) { i=0;cout<<endl;}
}
file.close();
}
void HfmTree::Treeprint()
{
p=head;
if(!p) { cerr<<"Error: please init_hfmtree first !"<<endl;
return;
}
if(!tree){ cerr<<"Error :can't open file treeprint.txt !"<<endl;return;}
int num=0;
MedVisit(p,num);//
}
/////////////////////////////////////
//fmain.cpp：测试文件
//主函数，菜单的设置，防止错误输入
////////////////////////////////////////////////////////////////////////////////////////////////
#include"hfm.h"
#include<iostream.h>
void main()
{
HfmTree hfmtree;
char ch;int n=0,m=0;
cout<<endl<<"------------------------------------------------------------------"<<endl
<<" input a char to select the work you want todo
:"<<endl
<<"init_hfmtree: i "<<"treeprint: t "<<endl
<<"coding : c "<<"decoding: d "<<endl
<<"print : p "<<"exit : e "<<endl
<<"------------------------------------------------------------------";
cout<<endl;
cin>>ch;
while(ch!='e')
{
switch(ch)
{
case 'i':
cout<<"input the number of the node of your hfmtree :";
cin>>n;
if(n<=0) { cerr<<endl<<"Error :the number cannot be smaller than 0"<<endl;break;}
hfmtree.InithfmTree;break;
case 't':
if(!n||!m) { cerr<<"Errorlease init_tree and coding first !"<<endl;
break;}
hfmtree.Treeprint();break;
case 'c':
m=1;
hfmtree.coding();break;
case 'd':
hfmtree.Decoding();break;
case 'p':
if((!n)||(!m)) { cerr<<"Errorlease init_tree and coding first !"<<endl;
break;}
hfmtree.print();break;
default :
cerr<<"Error input char!"<<endl;
}
cout<<endl<<"------------------------------------------------------------------"<<endl
<<" input a char to select the work you want:"<<endl
<<"init_hfmtree: i "<<"treeprint: t "<<endl
<<"coding : c "<<"decoding: d "<<endl
<<"print : p "<<"exit : e "<<endl
<<"------------------------------------------------------------------";
cout<<endl;
cin>>ch;
}
}
四 图书馆图书的管理(B_树)
本程序完成了所要求部分内容，图书可插入、查询、借阅、归还，而只有删除算法，可能没有时间实现了，而且，刚测试知道，我的所有可执行程序，包括在Boland C++ Builder 6.0 和Visual C++.NET 调试过的，在没有这两个系统的计算机上因缺少相关.DLL文件而无法运行。不知道老师是否可以把可执行程序带回去检查。有一点可以说明，这四个程序，确实已调试好，且对可能有的错误，都具有较好的处理能力。
简单说一下本程序的设计。本程序如果扩充，事实上既是做一个数据库。而对于本次实习，重点在于掌握B_树这种数据结构，并通过设计过程，提高对复杂数据结构和程序的设计能力。所以，本程序的设计策略是，精简，突出重点，不铺枝漫叶，但作为一个系统，应对各种情况具有良好的反映能力。
本程序所使用的数据结构为：
1． B_树 ，由类（class） Btree 实现。
本程序的主要类及其主要结构与关系为：
class Book class BtreeNode class Btree
算法中，有两个难点，其一是插入的分裂算法，其一是删除的合并算法。其中分裂算法是由类Btree的protected成员函数 void Parting(BtreeNode *&
pp);实现的。这是一个递归函数。可祥见于程序的实现部分。
平台是Visual C++.NET。
/////////////////////////////////////
//btree.h：书类、B_树类（及其接点类）的定义
//B_树的阶定义为全局变量
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#pragma once
//B_树的阶
const int m=3;
const int n=m+1;
const int mhalf=2;
//mhalf 是m/2 的上整数
class Book
{//书类
public:
Book(void);
~Book(void);
int bookID;//本程序中，id作为索引
char name[40];
char writer[20];
int nowNum;
int totalNum;
};
class BtreeNode
{//接点类
public:
BtreeNode(void);
virtual ~BtreeNode(void);
protected:
int ikey;//
BtreeNode *parent;//指向父接点
Book books[n];
BtreeNode *ptr[n];//指向孩子接点
public:
int &
Getikey(void);
BtreeNode *&
Getparent(void);
Book &
Getbook(int i);
BtreeNode *&
Getptr(int i);
};
class BTree
{//B_树
public:
BTree(void);
virtual ~BTree(void);
protected:
BtreeNode *head;
BtreeNode *p;
public:
void InitBtree(int k);
void Insert(const Book &
node);
int Search(const Book &
node);
int Borrow(const Book &
node);
int Return(const Book &
node);
void Delete(const Book &node);
void Print(void);
protected:
void Letbe(Book &
book, const Book &
node);//把node的信息copy给book
void Parting(BtreeNode *&
pp);//分裂函数
};
///////////////////////////////////////////
//btree.cpp：所有类的实现
////////////////////////////////////////////////////////////////////////////////////////////////
#include "btree.h"
#using <mscorlib.dll>
#include<string.h>
#include<iostream>
using namespace std;
BTree::BTree(void)
{
head=p=new BtreeNode();
}
BTree::~BTree(void)
{
}
BtreeNode::BtreeNode(void)
: ikey(0)
, parent(NULL)
{
for(int i=0;i<n;i++)
ptr=NULL;//指针初始化为空
}
BtreeNode::~BtreeNode(void)
{
}
Book::Book(void)
: bookID(0)
, nowNum(0)
, totalNum(0)
{
}
Book::~Book(void)
{
}
int &
BtreeNode::Getikey(void)
{
return ikey;
}
BtreeNode * &
BtreeNode::Getparent(void)
{
return parent;
}
Book &
BtreeNode::Getbook(int i)
{
if((i>0)&&(i<n))
return books;
else
{
cerr<<"Error: book number is wrong..."<<endl;
exit(-1);
}
}
BtreeNode *&
BtreeNode::Getptr(int i)
{
//TODO: return statement
if(i>=0&&i<n)
return ptr;
else
{
cerr<<"Error: pointer number to children is wrong..."<<endl;
exit(-1);
}
}
void BTree::InitBtree(int k)
{
}
/////////////////////////
//public：插入函数
//基本思路：
// 通过bresult值找到该插入的叶接点，插入；
// 判断是否需要分裂，如是，调用递归分裂函数。
///////////////////////////////////////////////////////////////////////////////////////////////
void BTree::Insert(const Book &
node)
{
p=head;
int i,j=0,bresult=0;
//bresult值可判断是否是叶接点
while(1)
{
bresult=0;
if(!p) { cerr<<"Errorointer point to NULL !"<<endl;return;}
for(i=0;i<n;i++)
bresult=bresult||int(p->Getptr(i));
//判断叶接点的算法
for(i=1;i<n;i++)
if(node.bookID<p->Getbook(i).bookID||p->Getbook(i).bookID==0)
{
j=i;//记录该插入的位置
break;
}
if(!bresult) goto here;//到达叶接点，跳出
if(j) p=p->Getptr(j-1);//继续向下搜索，j记录了值
else
p=p->Getptr(p->Getikey());//否则j==0说明该搜索最右边的孩子
}
here:
for(i=n-1;i>j;i--)
Letbe(p->Getbook(i),p->Getbook(i-1));
Letbe(p->Getbook(j),node);//插入
p->Getikey()++;
//如果需要分裂，调用分裂函数
if(p->Getikey()>=m)
Parting(p);
}
////////////////////////////////////
//public：查询函数
//查询关键字是book-id
///////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Search(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book!"<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
cout<<" Search successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
////////////////////////////////////
//public：截阅函数
////////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Borrow(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book!"<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
if(p->Getbook(i).nowNum>0){
p->Getbook(i).nowNum--;
cout<<" Borrow successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
else
{
cout<<"Sorry:the library has no this book this time ,palease wait”
<<” for someone's return."<<endl;
return 0;
}
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
////////////////////////////////
//public：归还函数
////////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Return(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book! maybe you want insert it..."<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
if(p->Getbook(i).nowNum<p->Getbook(i).totalNum){
p->Getbook(i).nowNum++;
cout<<" Return successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
else
{
cout<<"Sorry:this book is full already,are you sure you borrow it?"
<<endl;
return 0;
}
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
//////////////////////////////
//public：删除函数
//尚未写
////////////////////////////////////////////////////////////////////////////////////////////////
void BTree:elete(const Book &node)
{
}
void BTree:rint(void)
{
}
void BTree::Letbe(Book &
book, const Book &
node)
{
book.bookID=node.bookID;
strcpy(book.name,node.name);
book.nowNum=node.nowNum;
book.totalNum=node.totalNum;
strcpy(book.writer,node.writer);
}
///////////////////////////////////////
//protected：分裂函数
//基本思路：
// 生成书对象，保存需上提的book[mhalf]的信息；
// 生成新接点，以mhalf为界，把待分裂接点的信息分为两部分；
// 判断待分裂接点，如有父接点，则按照B_树分裂算法，把新接点插入，递归判断父接点是否需要分裂；//否则，待分裂接点为根接点，再生成一个新接点作为新的根接点，插入。
////////////////////////////////////////////////////////////////////////////////////////////////
void BTree:arting(BtreeNode *&
pp)
{
BtreeNode *pb=new BtreeNode();
Book book;
int i=0,j=0;
for(i=mhalf+1;i<=n-1;i++){
Letbe(pb->Getbook(++j),pp->Getbook(i));
Letbe(pp->Getbook(i),book);
}
j=0;
Letbe(book,pp->Getbook(mhalf));
Letbe(pp->Getbook(mhalf),pb->Getbook(mhalf));
pp->Getikey()=mhalf-1;
pb->Getikey()=m-mhalf;
if(pp->Getparent()==NULL)//如果无父接点
{
BtreeNode *phead=new BtreeNode();//新根接点
Letbe(phead->Getbook(1),book);
phead->Getptr(0)=pp;
phead->Getptr(1)=pb;
pp->Getparent()=phead;
pb->Getparent()=phead;
phead->Getikey()++;
head=phead;
return;
}
else
{//有父接点
BtreeNode *&pparent=pp->Getparent();
for(i=1;i<n;i++)
if(book.bookID<pparent->Getbook(i).bookID||pparent->Getbook(i).bookID==0)
{
j=i;//记录父接点中应存放books[mhalf]的位置
break;
}
for(i=n-1;i>j;i--)
Letbe(pparent->Getbook(i),pparent->Getbook(i-1));
Letbe(pparent->Getbook(j),book);
for(i=n-1;i>j;i--)
pparent->Getptr(i)=pparent->Getptr(i-1);
pparent->Getptr(j)=pb;
pb->Getparent()=pparent;
pparent->Getikey()++;
//如果父接点需要分裂，递归调用
if(pparent->Getikey()>=m)
Parting(pparent);
else
return;//否则返回
}
}
////////////////////////////////////////////
//fmain.cpp：测试文件
//设置菜单，测试图书管理系统，防止各种常规性错误录入
///////////////////////////////////////////////////////////////////////////////////////////////
#include"BTree.h"
#include<iostream>
using namespace std;
void main()
{
BTree library;
Book book;
char ch;int ID;
cout<<endl<<"input char todo
as follows:"<<endl
<<" insert :'i' "<<" "<<" search :'s' "<<endl
<<" borrow :'b' "<<" "<<" return :'r' "<<endl
<<" delete :'d' "<<" "<<" exit :'e' "<<endl;
cin>>ch;
while(1)
{
switch(ch)
{
case 'i':
cout<<"input :"<<endl
<<"book_id"<<" "<<"name"<<" "<<"now_num"<<" "<<"total_num"
<<" "<<"writer"<<endl;
cin>>book.bookID>>book.name>>book.nowNum>>book.totalNum>>book.writer;
if(book.bookID<=0){
cerr<<"Error input for book_id !"<<endl;break;
}
if(book.nowNum<=0||book.totalNum<=0){
cerr<<"Error for either now_num or total_num is not biger than 0 !"<<endl;break;
}
if(book.nowNum!=book.totalNum) {
cerr<<"Error input for now_num not equal to toatl_num !"<<endl;break;
}
library.Insert(book);
break;
case 's':
cout<<endl<<" input the book id you want to search:";
cin>>ID;
book.bookID=ID;
library.Search(book);
break;
case 'b':
cout<<endl<<" input the book id you want to borrow:";
cin>>ID;
book.bookID=ID;
library.Borrow(book);
break;
case 'r':
cout<<endl<<" input the book id you want to return:";
cin>>ID;
book.bookID=ID;
library.Return(book);
break;
case 'd':
cout<<"Sorry ..."<<endl;break;
case 'e':
goto exit;
default:
cout<<"Error input char !"<<endl;
}
cout<<endl<<"input char todo
as follows:"<<endl
<<" insert :'i' "<<" "<<" search :'s' "<<endl
<<" borrow :'b' "<<" "<<" return :'r' "<<endl
<<" delete :'d' "<<" "<<" exit :'e' "<<endl;
cin>>ch;
}
exit:
return;
}
<课程设计报告完>
准备用delphi做个中学试题数据库，希望能得到高手指点，QQ:103263223 .027-87436014 小李>
数据结构课程设计报告
一 池塘风雨
本程序的实现，采用较为简单的处理方法。
数据结构有：
1． 一个windows窗体类，内有menu菜单和一个时钟；
2． 数组，4组，分别记录雨点的坐标和池塘涟漪的坐标。
池塘中的景物有：
1． 芦苇群 ：静物，坐标是随即散列；
2． 荷叶 ：静物；
3． 雨水 ：动画，坐标随即散列；
4． 池水涟漪：动画，坐标随即散列。
动画的实现方法，主要是察除法。算法可见程序的详细注释。
平台是Boland C++Bilder 6.0 。遗憾的是，看了几天，也未能把程序写成多线程编程，而对于自然形态的刻画，也没有掌握较好的算法，感觉本程序的收获不大。
//---------------------------------------------------------------------------
//rain.h
//该文件定义一个窗体类和该类的一个外部指针变量
//////////////////////////////////////////////////////////////////////////////
#ifndef rainH
#define rainH
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
#include <Menus.hpp>
#include <OleCtnrs.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published: // IDE-managed Components
TMainMenu *MainMenu1;
TMenuItem *N1;
TMenuItem *N2;
TMenuItem *N3;
TMenuItem *N4;
TMenuItem *N5;
TTimer *Timer1;
void __fastcall N2Click(TObject *Sender);
void __fastcall N5Click(TObject *Sender);
void __fastcall Timer1Timer(TObject *Sender);
private: // User declarations
public: // User declarations
__fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------
//////////////////////////
//rain.cpp
//
//该文件具体实现在窗体上绘制池塘风雨的动画
///////////////////////////////////////////////////////////////////////////////
#include <vcl.h>
#pragma hdrstop
#include "rain.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int x[80];//雨点的x坐标
int y[80];//雨点的y坐标
int icount=0;//时钟控制变量
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
//全局函数
//初始化雨点的坐标，且保证不落入保护区域（该区域绘制一荷叶）
//////////////////////////////////////////////////////////////////////////////
void PreDrawRain()
{
for(int i=0;i<80;i++)
{
x=random(1000);
y=random(800);
if(x>100&&x<200&&y>350&&y<400)
y-=100;
}
}
//--------------------------------------------------------------------------
//全局函数
//绘制雨点，同时对时钟控制变量增1操作
//////////////////////////////////////////////////////////////////////////////
void DrawRain()
{
for(int i=0;i<80;i++)
{
Form1->Canvas->MoveTo(x,y);
Form1->Canvas->LineTo(x-5,y+5);
}
icount++;
}
//---------------------------------------------------------------------------
//全局函数
//动画“雨”和“池塘涟漪”的实现
/////////////////////////////////////////////////////////////////////////////
void Draw()
{
int dx,dy;//涟漪扩充增量
int x0[8];//涟漪x坐标
int y0[8];//涟漪y坐标
for(int j=0;j<6;j++)
{
for(int i=0;i<8;i++){
x0=100+random(400);
//涟漪散落范围：
y0=100+random(300);
// x：100~500，y：100~400
if(x0>100&&x0<200&&y0>350&&y0<400)
y0-=100;x0+=200;
}
for(dx=random(2),dy=random(4);dx<10;dx+=1,dy++)
{
for(int i=0;i<8;i++)
{//第i次绘制涟漪
Form1->Canvas->Pen->Color=clMedGray;
Form1->Canvas->Ellipse(x0-2*dx,y0-dx,x0+2*dx,y0+dx);
Form1->Canvas->Ellipse(x0-2*dx-2,y0-dx-1,x0+2*dx+2,y0+dx+1);
}
PreDrawRain();
DrawRain();
Sleep(200);
for(int i=0;i<8;i++)
{//第i次察除涟漪
Form1->Canvas->Pen->Color=clSkyBlue;
Form1->Canvas->Ellipse(x0-2*dx,y0-dx,x0+2*dx,y0+dx);
Form1->Canvas->Ellipse(x0-2*dx-2,y0-dx-1,x0+2*dx+2,y0+dx+1);
}
DrawRain();
}
}
}
//---------------------------------------------------------------------------
//成员函数
//退出执行程序
/////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::N2Click(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
//成员函数
//时钟开始，程序从新执行
/////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::N5Click(TObject *Sender)
{
Timer1->Enabled=true;
//重新开始，时钟可访问
}
//---------------------------------------------------------------------------
//成员函数：时钟函数
//初始化“池塘”环境，调用动画函数
//////////////////////////////////////////////////////////////////////////////
void __fastcall TForm1::Timer1Timer(TObject *Sender)
{
int i,x,y;//x，y为芦苇的坐标
Canvas->Pen->Color=clBlack;
Canvas->Brush->Color=clSkyBlue;
//池塘之水
Canvas->FloodFill(100,400,clBlack, fsBorder);
//绘制荷叶
Canvas->Pie(105,355,195,395,195,355,195,390);
Canvas->Brush->Color=clGreen;
Canvas->FloodFill(130,360,clBlack,fsBorder);
//荷叶旁静芦苇（一棵）,突出立体感
Canvas->Pen->Color=clGreen;
x=170;
y=325;
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
//散列芦苇：池塘左方15棵
for(i=0;i<15;i++)
{
x=random(150);
y=random(400);
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
}
//散列芦苇：池塘下方15棵
for(i=0;i<15;i++)
{
x=50+random(400);
y=400+random(100);
Canvas->MoveTo(x,y);
Canvas->LineTo(x+5,y+50);
Canvas->MoveTo(x,y+30);
Canvas->LineTo(x+10,y+10);
Canvas->MoveTo(x,y+20);
Canvas->LineTo(x+10,y+5);
Canvas->MoveTo(x,y+5);
Canvas->LineTo(x+10,y-5);
}
Canvas->Pen->Color=clBlack;
Canvas->Brush->Color=clSkyBlue;
//绘制动画
Draw();
//如果时钟控制变量超值，时钟无效
if(icount>200)
{
icount=0;
Timer1->Enabled=false;
}
}
//---------------------------------------------------------------------------
二 魔王语言
本程序的实现，没有多少扩展。
对于魔王的语言，我是这样理解的。对于一串字符串（魔王语言），遇到成对（）则使用规则2：（θδ1δ2…δn）→θδnθδn-1…θδ1θ，而遇到大写字母A和B，则使用规则1的两个特殊（具体）形式：（1）B→tAdA （2）A→sae ，以此翻译。
由形式规则2知，（……）本质上是一字符串，故多重括号（…（……）…）应是魔王语言，但因时间等因素，本程序的算法不能翻译这类语言，只能胜任一重括号或无括号的情况；但是，本程序对包括多重括号在内的魔王语言输入错误，具有较好的识别性。
本程序的数据结构为：
1． 数组，存储魔王语言和人类语言，且是类Langvage 的保护（protected）成员变量；
2． 堆栈，对于括号，检查魔王语言的错误；
3． 类Langvage ，它的结构为：
该类中，本应有人类语言到魔王语言的翻译函数，这样它才是完整的。时间不够，所以并未添置。
对于算法，就是两个规则的反映。可祥见程序的详细注释。
平台是 Visual C++.NET，收获就是，对于字符串的操作，这样的练习是有益的。
//////////////////////////////////
//langvage.h
//类langvage的声明
/////////////////////////////////////////////////////////////////////////////////////////
#pragma once
//n默认的魔王语言最大长度
const n=100;
class Langvage
{
public:
Langvage(void);
~Langvage(void);
protected:
char lgv[n];
char lgvH[n];
int size;
int sizeH;
public:
void LgvGtoH(void);
void PrintLgvH(void);
void InitLgvG(void);
};//可见于类langvage的结构图
////////////////////////////////////
//langvage.cpp
//类langvage的定义实现
////////////////////////////////////////////////////////////////////////////////////////
#include "langvage.h"
#using <mscorlib.dll>
#include<iostream.h>
Langvage::Langvage(void)
{
size=0;
sizeH=0;
}
Langvage::~Langvage(void)
{
}
///////////////////////////////////////
//public：翻译魔王语言
//基本思路是：
// 1。魔王语言有无错误，若有，打印错误，返回；否则，转2；
// 2。是否有括号？若无，直接从lgv[n]翻译到lgvH[n]，否则，设置中间数组，先翻译去掉括号，再行翻//译。
//原则是魔王语言lgv不被破坏。
////////////////////////////////////////////////////////////////////////////////////////////////
void Langvage::LgvGtoH(void)
{
int i,j,k1=-1,k2=-1;//k1追踪（的位置，k2追踪）的位置
char cha;//记录（后的第一个字符
char array[100],stack[50];//中间字符数组和堆栈
int karray=0,top=-1;//karray记录中间数组的实际长度
int k=0;//k标志是否有括号
for(i=0;i<size;i++)
if(lgv=='('||lgv==')') break;
if(i==size) goto here;//goto语句，说明魔王语言无括号
//否则，判断有无错误
for(i=0;i<size;i++)
{
if(top==-2)
{
cout<<"Langvage Error with '(' or ')' !"<<endl;
return;
}
if(lgv=='(')
{
top++;stack[top]='(';
}
else
if(lgv==')') top--;
}
if(top!=-1) { cout<<"Langvage Error with '(' or ')' !"<<endl;return;}
for(i=0;i<size;i++)
{
if(lgv=='(') k1=i;
if(lgv==')') k2=i;
}
//设置k为1，魔王语言有括号且无错误
k=1;
if(k2==k1+1)//如果括号为空，既是 ：……（）……
{
j=0;
for(i=0;i<size;i++)
{
if(i==k1) i+=2;
array[j]=lgv;
karray++;
j++;
}
goto here;
}
//括号不为空，设置cha，先翻译到array[n]
cha=lgv[k1+1];
for(i=0;i<k1;i++)
{
array=lgv;karray++;
}//i==k1
array=cha;i++;karray++;
for(j=k2-1;j>k1+1;j--)
{
array=lgv[j];
i++;karray++;
array=cha;
i++;karray++;
}
for(j=k2+1;j<size;j++)
{
array=lgv[j];
i++;karray++;
}
//翻译已无括号的魔王语言
here:
if(k)//如果原魔王语言有括号，从array翻译
for(j=0,i=0;j<karray;j++)
{
switch(array[j])
{
case 'B':
{
lgvH='t';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
lgvH='d';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
case 'A':
{
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
default:
{ lgvH=array[j];i++;
sizeH++;}
}
}
else
{//原魔王语言无括号
for(j=0,i=0;j<size;j++)
{
switch(lgv[j])
{
case 'B':
{
lgvH='t';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
lgvH='d';i++;sizeH++;
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
case 'A':
{
lgvH='s';i++;sizeH++;
lgvH='a';i++;sizeH++;
lgvH='e';i++;sizeH++;
break;
}
default:
{ lgvH=lgv[j];i++;
sizeH++;}
}
}
}
}
//////////////////////////////////////
//public：打印人类语言
//根据约定，输出空格和换行字符
/////////////////////////////////////////////////////////////////////////////////////
void Langvage:
rintLgvH(void){
int i;
cout<<"----------------"<<endl;
for(i=0;i<sizeH;i++)//
{
switch(lgvH)
{
case '/':
cout<<'/0';break;
case '@':
cout<<endl;break;
default:
cout<<lgvH;
}
}
}
/////////////////////////////////////////
//public：魔王语言输入
// ’/’,’@’和’#’，是输入的事先约定，与魔王语言无关，起到输出控制作用
///////////////////////////////////////////////////////////////////////////////
void Langvage::InitLgvG(void)
{
char cha;
int i=0;
cout<<"请输入魔王语言，'/'为输入空格，'@'为输入换行符，'#' 为退出符:"<<endl;
cin>>cha;
while(1)
{
if(cha=='#')
return;
lgv=cha;
i++;
size++;
cin>>cha;
}
}
/////////////////////////////////////////////
//fmain.cpp
//主函数，设置菜单界面，测试类langvage
///////////////////////////////////////////////////////////////////////////////////////
#include<iostream.h>
#include"Langvage.h"
void main()
{
char ch;
while(1)
{
cout<<"---------------------------------------------------------------------"<<endl;
cout<<"If you want to exit,input e ,or input another key to come in:"<<endl;
cin>>ch;
cout<<"---------------------------------------------------------------------"<<endl;
if(ch=='e') return;
Langvage lgv;
lgv.InitLgvG();
lgv.LgvGtoH();
lgv.PrintLgvG();
}
}
三 哈夫曼树编码/译码器
本程序实现了哈夫曼树编码/译码器。
本程序所用的数据结构为：
1． 二叉树 ，由类HfmTree 实现；
2． 数组，元素是类Narray 的对象，辅助建立哈夫曼树。
另外有若干可读写操作的文本文件。
本程序中主要的类的结构和关系为：
class Narray
class Node
class HfmTree
本程序的算法中，哈夫曼树的建立，是通过class Narray 的数组辅助实现的。在开始，数组中成员变量head指针指向已输入的字符接点(Node)，然后根据哈夫曼树的算法，生成一个新接点（Node），指向最小（key值）的两个接点，然后使其一的head指针指向新接点，另一个接点的标志i标志该接点退出数组。循环如此，建立哈夫曼树，我称这个方式为“挂葡萄式”。
对于编码/译码的实现，都是通过遍历哈夫曼树，跟踪实现的；遍历算法，都是中序递归的。可祥见与程序的实现部分。
通过本程序的设计，感觉收获不小。无论是程序设计技巧，还是对面向对象的理解，还是对c++的掌握（尤其文件操作），都感到这个程序写的有价值。
平台是Visual C++.NET 。
/////////////////////////////////////////////////////////////////////////////////
//hfmtree.h
//接点类Node，辅助类Narray，哈夫曼树类HfmTree的定义
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//默认的可哈夫曼编码的字符最大个数
const int charnum=60;
class Node {
float key;//字符的权值
char name;// 叶接点的名称
char *pstr;// 叶接点的编码代码
Node *left,*right;
public:
//初始化部分
Node(float Key=0,char Name='/0');
//virtual ~Node();
void Set(float Key,char Name);
void Set(const char * Pstr);
//获得封装值
float Getkey();
char Getname();
//需使用指针的引用，可做左值或右值
char *&Getpstr();
Node *&Getleft();
Node *&Getright();
};
class Narray {
public:
int i;//标志该head是否有意义
Node *head;
};
class HfmTree {
Node *head;// 哈夫曼树头指针
Node *p;//应用指针
int n;//叶接点个数
protected:
void MedVisit(Node *q, int &num);//中序遍历
void precoding(Node *q);//编码前设置
void nowcoding(Node *q,char ch);//编码，递归函数
void nowDcoding(Node *q,char &
ch);//译码，递归函数
public:
HfmTree();
void InithfmTree(int N);
void coding();//编码，tobetrans->codefile
void Decoding();//译码，->textfile
void print();//打印代码，每行50个代码->codeprint
void Treeprint();//打印哈夫曼树，treeprint
};
/////////////////////////////////////////////////
//hfmtree.cpp
//哈夫曼树编码/译码器所有功能的实现
///////////////////////////////////////////////////////////////////////////
#include"hfm.h"
#include<iostream.h>
#include<stdlib.h>
#include<string.h>
//这儿是c++新标准，很高兴Visual C++.NET支持：）
#include<fstream>
using namespace std;
extern const int charnum;
//所需要的各文本文件
fstream from("tobetrans.txt",ios_base::in|ios_base:
ut);fstream to("codefile.txt",ios_base::in|ios_base:
ut);fstream to1("codefile.txt",ios_base::in|ios_base:
ut);fstream text("textfile.txt",ios_base::in|ios_base:
ut);fstream tree("treeprint.txt",ios_base::in|ios_base:
ut);static int iCount=0;
static char array[charnum];//编码跟踪变量和数组
Node::Node(float Key,char Name):
key(Key),name(Name)
,left(NULL),right(NULL),pstr(NULL)
{ }
void Node::Set(float Key,char Name)
{
key=Key;
name=Name;
}
void Node::Set(const char *Pstr)
{
pstr=new char[charnum];
strcpy(pstr,Pstr);
}
float Node::Getkey() { return key }
char Node::Getname() { return name;
}
char *&Node::Getpstr(){ return pstr;}
Node *&Node::Getleft() { return left;
}
Node *&Node::Getright() { return right;
}
HfmTree::HfmTree():head(NULL),p(NULL),n(0)
{ }
////////////////////////////////////
//public：建立哈夫曼树
// 说明见与开始部分
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::InithfmTree(int N)
{
n=N;
int i,k0,k1;//k0，k1记录最小两个接点的序号
float Key;
char Name;
if(N>charnum) { cerr<<"Error:You need too much Node!";
return;}
Narray array[charnum];//辅助数组的定义和初始化
for( i=0;i<charnum;i++)
{
array.head=NULL;
array.i=-1;
}
cout<<endl<<" 请依次相隔输入"<<N<<" 个数(权重)和他们的单字符名称："<<endl;
for(i=0;i<N;i++)
{
cin>>Key>>Name;
p=new Node(Key,Name);
if(!p) { cerr<<"Error:Cannot create Node!";
return;}
array.head=p;
array.i=1;
}
//跟踪辅助数组的挂接操作次数
int m=0;
while(m<N)
{
for(i=0;i<N;i++)
if(array.i==1)
{
Key=array.head->Getkey();//先取得第一个存在的接点权（和）值
break;
}
for(i=0;i<N;i++)
if((array.i==1)&&(Key>=array.head->Getkey()))
{
Key=array.head->Getkey();
k0=i;//记录最小接点的序号
}
for(i=0;i<N;i++)
if((i!=k0)&&(array.i==1))
{
Key=array.head->Getkey();//取得第二个存在的接点权（和）值
break;
}
for(i=0;i<N;i++)//
if((i!=k0)&&(array.i==1)&&(Key>=array.head->Getkey()))
{
Key=array.head->Getkey();
k1=i;//记录第二小接点的序号
}
if(k0==k1)
{
cout<<"Error with init_hfmtree !"<<endl;
return;
}
//申请新接点，赋值挂接
p=new Node(array[k0].head->Getkey()+array[k1].head->Getkey());
if(!p) { cerr<<"Error:Cannot create Node!";
return;}
if(array[k0].head->Getkey()<=array[k1].head->Getkey())
{
p->Getleft()=array[k0].head;
p->Getright()=array[k1].head;
}
else
{
p->Getleft()=array[k1].head;
p->Getright()=array[k0].head;
}
array[k0].head=p;
array[k1].i=0;
//辅助数组中剩余有意义接点
int ksize=0;
for(i=0;i<N;i++)
if(array.i==1) ksize++;
//如果为1，则建立完成，使head指针指向该有意义的接点
if(ksize==1)
{
int j;
for(i=0;i<N;i++)
if(array.i==1)
{
j=i;
break;
}
head=array[j].head;
return;
}
m++;
}
}
//////////////////////////////////////////////
//protected：中序遍历（递归）
//以凹凸表的形式把树输出，并把有关信息写入文本文件treeprint.txt
//num需使用引用，控制空格的输出
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::MedVisit(Node *q,int &num)
{
if(!q) { return;}
for(int i=0;i<num;i++)
cout<<'/0';
if(q->Getname()!='/0')
{
tree<<q->Getname();
tree<<"-'s key is ";
tree<<q->Getkey()
<<"and its code is "
<<q->Getpstr()<<endl;
}
if(q->Getname()!='/0')
cout<<q->Getname()<<"-'s key is "<<q->Getkey()<<endl;
else
cout<<"-'s key is "<<q->Getkey()<<endl;
num++;
MedVisit(q->Getleft(),num);
num--;
num++;
MedVisit(q->Getright(),num);
num--;
}
///////////////////////////////////////////
//protected：获得各字符的哈夫曼编码（递归）
//array跟踪遍历步骤，向左时加入‘0’，向右时加入‘1’，为叶接点时把编码赋值给pstr
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree:
recoding(Node *q){
if(q->Getname()!='/0') {
array[iCount]='/0';
q->Getpstr()=new char[charnum];
strcpy(q->Getpstr(),array);
iCount--;
return;
}
array[iCount]='0';
iCount++;
precoding(q->Getleft());
array[iCount]='1';
iCount++;
precoding(q->Getright());
//这一步是必须的，它说明遍历在在中间接点由左转向右
if(q->Getname()=='/0') iCount--;
}
///////////////////////////////
//protected：对文本文件内容编码（递归）
/////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::nowcoding(Node *q,char ch)
{
if(!q) return;
if(q->Getname()==ch)
{
to<<q->Getpstr()<<endl;
return;
}
nowcoding(q->Getleft(),ch);
nowcoding(q->Getright(),ch);
}
void HfmTree::coding()
{
p=head;
if(!p) { cout<<"Error: please init_hfmtree first !"<<endl;return;
}
if(!from) { cerr<<" Error open file 'tobetrans.txt' !"<<endl;
return;}
if(!to) { cerr<<" Error open file 'codefile.txt' !"<<endl;
return;}
precoding(p);
p=head;
char ch;
while(!from.eof())
{
from>>ch;
nowcoding(p,ch);
}
}
///////////////////////////////////
//protected：对文本文件翻译（递归）
//对哈夫曼树搜索，‘0’向左，‘1’向右，到达叶接点写入字符名称
////////////////////////////////////////////////////////////////////////////////////////////////
void HfmTree::nowDcoding(Node *q,char &ch)
{
if(!q) return;
if(q->Getname()!='/0')
{
text<<q->Getname();
return;
}
if(ch=='0')
{
q=q->Getleft();
to1>>ch;
nowDcoding(q,ch);
}
else
if(ch=='1')
{
q=q->Getright();
to1>>ch;
nowDcoding(q,ch);
}
}
void HfmTree:
ecoding(){
char ch;
int i=0;
p=head;
if(!p) { cout<<"Error: please init_hfmtree first !"<<endl;return;
}
if(!to1) { cerr<<" Error open file 'codefile.txt' !"<<endl;
return;}
if(!text){ cerr<<" Error open file 'text.txt' !"<<endl;
return;}
to1>>ch;
while(!to1.eof())
{
nowDcoding(p,ch);
}
}
void HfmTree:
rint(){
fstream file("codefile.txt",ios_base::in|ios_base:
ut);if(!file) { cerr<<"Error:can't open codefile.txt !"<<endl;
return;}
char ch;
int i=0;
while(!file.eof())
{
file>>ch;
cout<<ch;
i++;
if(i==50) { i=0;cout<<endl;}
}
file.close();
}
void HfmTree::Treeprint()
{
p=head;
if(!p) { cerr<<"Error: please init_hfmtree first !"<<endl;
return;
}
if(!tree){ cerr<<"Error :can't open file treeprint.txt !"<<endl;return;}
int num=0;
MedVisit(p,num);//
}
/////////////////////////////////////
//fmain.cpp：测试文件
//主函数，菜单的设置，防止错误输入
////////////////////////////////////////////////////////////////////////////////////////////////
#include"hfm.h"
#include<iostream.h>
void main()
{
HfmTree hfmtree;
char ch;int n=0,m=0;
cout<<endl<<"------------------------------------------------------------------"<<endl
<<" input a char to select the work you want todo
:"<<endl
<<"init_hfmtree: i "<<"treeprint: t "<<endl
<<"coding : c "<<"decoding: d "<<endl
<<"print : p "<<"exit : e "<<endl
<<"------------------------------------------------------------------";
cout<<endl;
cin>>ch;
while(ch!='e')
{
switch(ch)
{
case 'i':
cout<<"input the number of the node of your hfmtree :";
cin>>n;
if(n<=0) { cerr<<endl<<"Error :the number cannot be smaller than 0"<<endl;break;}
hfmtree.InithfmTree
;break;case 't':
if(!n||!m) { cerr<<"Error
lease init_tree and coding first !"<<endl;break;}
hfmtree.Treeprint();break;
case 'c':
m=1;
hfmtree.coding();break;
case 'd':
hfmtree.Decoding();break;
case 'p':
if((!n)||(!m)) { cerr<<"Error
lease init_tree and coding first !"<<endl;break;}
hfmtree.print();break;
default :
cerr<<"Error input char!"<<endl;
}
cout<<endl<<"------------------------------------------------------------------"<<endl
<<" input a char to select the work you want:"<<endl
<<"init_hfmtree: i "<<"treeprint: t "<<endl
<<"coding : c "<<"decoding: d "<<endl
<<"print : p "<<"exit : e "<<endl
<<"------------------------------------------------------------------";
cout<<endl;
cin>>ch;
}
}
四 图书馆图书的管理(B_树)
本程序完成了所要求部分内容，图书可插入、查询、借阅、归还，而只有删除算法，可能没有时间实现了，而且，刚测试知道，我的所有可执行程序，包括在Boland C++ Builder 6.0 和Visual C++.NET 调试过的，在没有这两个系统的计算机上因缺少相关.DLL文件而无法运行。不知道老师是否可以把可执行程序带回去检查。有一点可以说明，这四个程序，确实已调试好，且对可能有的错误，都具有较好的处理能力。
简单说一下本程序的设计。本程序如果扩充，事实上既是做一个数据库。而对于本次实习，重点在于掌握B_树这种数据结构，并通过设计过程，提高对复杂数据结构和程序的设计能力。所以，本程序的设计策略是，精简，突出重点，不铺枝漫叶，但作为一个系统，应对各种情况具有良好的反映能力。
本程序所使用的数据结构为：
1． B_树 ，由类（class） Btree 实现。
本程序的主要类及其主要结构与关系为：
class Book class BtreeNode class Btree
算法中，有两个难点，其一是插入的分裂算法，其一是删除的合并算法。其中分裂算法是由类Btree的protected成员函数 void Parting(BtreeNode *&
pp);实现的。这是一个递归函数。可祥见于程序的实现部分。
平台是Visual C++.NET。
/////////////////////////////////////
//btree.h：书类、B_树类（及其接点类）的定义
//B_树的阶定义为全局变量
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#pragma once
//B_树的阶
const int m=3;
const int n=m+1;
const int mhalf=2;
//mhalf 是m/2 的上整数
class Book
{//书类
public:
Book(void);
~Book(void);
int bookID;//本程序中，id作为索引
char name[40];
char writer[20];
int nowNum;
int totalNum;
};
class BtreeNode
{//接点类
public:
BtreeNode(void);
virtual ~BtreeNode(void);
protected:
int ikey;//
BtreeNode *parent;//指向父接点
Book books[n];
BtreeNode *ptr[n];//指向孩子接点
public:
int &
Getikey(void);
BtreeNode *&
Getparent(void);
Book &
Getbook(int i);
BtreeNode *&
Getptr(int i);
};
class BTree
{//B_树
public:
BTree(void);
virtual ~BTree(void);
protected:
BtreeNode *head;
BtreeNode *p;
public:
void InitBtree(int k);
void Insert(const Book &
node);
int Search(const Book &
node);
int Borrow(const Book &
node);
int Return(const Book &
node);
void Delete(const Book &node);
void Print(void);
protected:
void Letbe(Book &
book, const Book &
node);//把node的信息copy给book
void Parting(BtreeNode *&
pp);//分裂函数
};
///////////////////////////////////////////
//btree.cpp：所有类的实现
////////////////////////////////////////////////////////////////////////////////////////////////
#include "btree.h"
#using <mscorlib.dll>
#include<string.h>
#include<iostream>
using namespace std;
BTree::BTree(void)
{
head=p=new BtreeNode();
}
BTree::~BTree(void)
{
}
BtreeNode::BtreeNode(void)
: ikey(0)
, parent(NULL)
{
for(int i=0;i<n;i++)
ptr=NULL;//指针初始化为空
}
BtreeNode::~BtreeNode(void)
{
}
Book::Book(void)
: bookID(0)
, nowNum(0)
, totalNum(0)
{
}
Book::~Book(void)
{
}
int &
BtreeNode::Getikey(void)
{
return ikey;
}
BtreeNode * &
BtreeNode::Getparent(void)
{
return parent;
}
Book &
BtreeNode::Getbook(int i)
{
if((i>0)&&(i<n))
return books;
else
{
cerr<<"Error: book number is wrong..."<<endl;
exit(-1);
}
}
BtreeNode *&
BtreeNode::Getptr(int i)
{
//TODO: return statement
if(i>=0&&i<n)
return ptr;
else
{
cerr<<"Error: pointer number to children is wrong..."<<endl;
exit(-1);
}
}
void BTree::InitBtree(int k)
{
}
/////////////////////////
//public：插入函数
//基本思路：
// 通过bresult值找到该插入的叶接点，插入；
// 判断是否需要分裂，如是，调用递归分裂函数。
///////////////////////////////////////////////////////////////////////////////////////////////
void BTree::Insert(const Book &
node)
{
p=head;
int i,j=0,bresult=0;
//bresult值可判断是否是叶接点
while(1)
{
bresult=0;
if(!p) { cerr<<"Error
ointer point to NULL !"<<endl;return;}for(i=0;i<n;i++)
bresult=bresult||int(p->Getptr(i));
//判断叶接点的算法
for(i=1;i<n;i++)
if(node.bookID<p->Getbook(i).bookID||p->Getbook(i).bookID==0)
{
j=i;//记录该插入的位置
break;
}
if(!bresult) goto here;//到达叶接点，跳出
if(j) p=p->Getptr(j-1);//继续向下搜索，j记录了值
else
p=p->Getptr(p->Getikey());//否则j==0说明该搜索最右边的孩子
}
here:
for(i=n-1;i>j;i--)
Letbe(p->Getbook(i),p->Getbook(i-1));
Letbe(p->Getbook(j),node);//插入
p->Getikey()++;
//如果需要分裂，调用分裂函数
if(p->Getikey()>=m)
Parting(p);
}
////////////////////////////////////
//public：查询函数
//查询关键字是book-id
///////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Search(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book!"<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
cout<<" Search successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
////////////////////////////////////
//public：截阅函数
////////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Borrow(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book!"<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
if(p->Getbook(i).nowNum>0){
p->Getbook(i).nowNum--;
cout<<" Borrow successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
else
{
cout<<"Sorry:the library has no this book this time ,palease wait”
<<” for someone's return."<<endl;
return 0;
}
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
////////////////////////////////
//public：归还函数
////////////////////////////////////////////////////////////////////////////////////////////////
int BTree::Return(const Book &
node)
{
p=head;
if(!p){
cerr<<"Error:there is no book in the library!"<<endl;
return 0;
}
while(1)
{
if(!p) { cerr<<" no such book! maybe you want insert it..."<<endl;
return 0;}
int i,j=0;
for(i=1;i<=p->Getikey();i++)
if(p->Getbook(i).bookID==node.bookID)//
{
if(p->Getbook(i).nowNum<p->Getbook(i).totalNum){
p->Getbook(i).nowNum++;
cout<<" Return successful for:"<<endl
<<"book ID:"<<p->Getbook(i).bookID<<" "
<<"name :"<<p->Getbook(i).name<<endl
<<"now_number:"<<p->Getbook(i).nowNum<<" "
<<"total_number:"<<p->Getbook(i).totalNum<<" "
<<"writer :"<<p->Getbook(i).writer<<endl;
return 1;
}
else
{
cout<<"Sorry:this book is full already,are you sure you borrow it?"
<<endl;
return 0;
}
}
for(i=1;i<=p->Getikey();i++)
if(node.bookID<p->Getbook(i).bookID)
{
j=i;
break;
}
if(j!=0)
p=p->Getptr(j-1);
else
p=p->Getptr(p->Getikey());
}
return 1;
}
//////////////////////////////
//public：删除函数
//尚未写
////////////////////////////////////////////////////////////////////////////////////////////////
void BTree:
elete(const Book &node){
}
void BTree:
rint(void){
}
void BTree::Letbe(Book &
book, const Book &
node)
{
book.bookID=node.bookID;
strcpy(book.name,node.name);
book.nowNum=node.nowNum;
book.totalNum=node.totalNum;
strcpy(book.writer,node.writer);
}
///////////////////////////////////////
//protected：分裂函数
//基本思路：
// 生成书对象，保存需上提的book[mhalf]的信息；
// 生成新接点，以mhalf为界，把待分裂接点的信息分为两部分；
// 判断待分裂接点，如有父接点，则按照B_树分裂算法，把新接点插入，递归判断父接点是否需要分裂；//否则，待分裂接点为根接点，再生成一个新接点作为新的根接点，插入。
////////////////////////////////////////////////////////////////////////////////////////////////
void BTree:
arting(BtreeNode *&pp)
{
BtreeNode *pb=new BtreeNode();
Book book;
int i=0,j=0;
for(i=mhalf+1;i<=n-1;i++){
Letbe(pb->Getbook(++j),pp->Getbook(i));
Letbe(pp->Getbook(i),book);
}
j=0;
Letbe(book,pp->Getbook(mhalf));
Letbe(pp->Getbook(mhalf),pb->Getbook(mhalf));
pp->Getikey()=mhalf-1;
pb->Getikey()=m-mhalf;
if(pp->Getparent()==NULL)//如果无父接点
{
BtreeNode *phead=new BtreeNode();//新根接点
Letbe(phead->Getbook(1),book);
phead->Getptr(0)=pp;
phead->Getptr(1)=pb;
pp->Getparent()=phead;
pb->Getparent()=phead;
phead->Getikey()++;
head=phead;
return;
}
else
{//有父接点
BtreeNode *&pparent=pp->Getparent();
for(i=1;i<n;i++)
if(book.bookID<pparent->Getbook(i).bookID||pparent->Getbook(i).bookID==0)
{
j=i;//记录父接点中应存放books[mhalf]的位置
break;
}
for(i=n-1;i>j;i--)
Letbe(pparent->Getbook(i),pparent->Getbook(i-1));
Letbe(pparent->Getbook(j),book);
for(i=n-1;i>j;i--)
pparent->Getptr(i)=pparent->Getptr(i-1);
pparent->Getptr(j)=pb;
pb->Getparent()=pparent;
pparent->Getikey()++;
//如果父接点需要分裂，递归调用
if(pparent->Getikey()>=m)
Parting(pparent);
else
return;//否则返回
}
}
////////////////////////////////////////////
//fmain.cpp：测试文件
//设置菜单，测试图书管理系统，防止各种常规性错误录入
///////////////////////////////////////////////////////////////////////////////////////////////
#include"BTree.h"
#include<iostream>
using namespace std;
void main()
{
BTree library;
Book book;
char ch;int ID;
cout<<endl<<"input char todo
as follows:"<<endl
<<" insert :'i' "<<" "<<" search :'s' "<<endl
<<" borrow :'b' "<<" "<<" return :'r' "<<endl
<<" delete :'d' "<<" "<<" exit :'e' "<<endl;
cin>>ch;
while(1)
{
switch(ch)
{
case 'i':
cout<<"input :"<<endl
<<"book_id"<<" "<<"name"<<" "<<"now_num"<<" "<<"total_num"
<<" "<<"writer"<<endl;
cin>>book.bookID>>book.name>>book.nowNum>>book.totalNum>>book.writer;
if(book.bookID<=0){
cerr<<"Error input for book_id !"<<endl;break;
}
if(book.nowNum<=0||book.totalNum<=0){
cerr<<"Error for either now_num or total_num is not biger than 0 !"<<endl;break;
}
if(book.nowNum!=book.totalNum) {
cerr<<"Error input for now_num not equal to toatl_num !"<<endl;break;
}
library.Insert(book);
break;
case 's':
cout<<endl<<" input the book id you want to search:";
cin>>ID;
book.bookID=ID;
library.Search(book);
break;
case 'b':
cout<<endl<<" input the book id you want to borrow:";
cin>>ID;
book.bookID=ID;
library.Borrow(book);
break;
case 'r':
cout<<endl<<" input the book id you want to return:";
cin>>ID;
book.bookID=ID;
library.Return(book);
break;
case 'd':
cout<<"Sorry ..."<<endl;break;
case 'e':
goto exit;
default:
cout<<"Error input char !"<<endl;
}
cout<<endl<<"input char todo
as follows:"<<endl
<<" insert :'i' "<<" "<<" search :'s' "<<endl
<<" borrow :'b' "<<" "<<" return :'r' "<<endl
<<" delete :'d' "<<" "<<" exit :'e' "<<endl;
cin>>ch;
}
exit:
return;
}
<课程设计报告完>