问题描述
- 排序与查找及其应用:设计一个程序，用于查询一个IP所在的机构设计一个程序，用于查询一个IP所在的机构
-
设计一个程序，用于查询一个IP所在的机构。具体要求：1. 设计一个函数，用于比较两个IP地址(字符串)的大小，
2. 从外部数据文件(IP.TXT)中读取IP数据;
3. 用平衡二叉排序树存储IP及其所属机构名称;4. 输入一个IP地址，查找并输出与此IP对应的机构名称;
5. 输入一个机构名称，查询与此机构对应的的IP地址;
解决方案
算法部分可以使用STL。
解决方案二：
#include //printf,scanf
#include //malloc
#include //getch
#define FALSE 0
#define TRUE 1
#define NULL 0
#define LH 1 //左高
#define EH 0 //等高
#define RH -1 //右高
typedef int KeyType;
typedef int Status;
typedef struct{
KeyType key; //按key字段排序
char s[10]; //另一字段,空着未用
}ElemType;
typedef struct BBSTNode{ //二叉平衡排序树
ElemType data; //数据元素
int bf; //平衡因子
struct BBSTNode *lchild,*rchild; //左右孩子
}BBSNode,*BBSTree; //结点及结点指针
Status Delete(BBSTree &);
void LeftBalance(BBSTree &);
void RightBalance(BBSTree &);
void R_Rotate(BBSTree &p);
void L_Rotate(BBSTree &p);
Status EQ(KeyType a,KeyType b)
{
if(a==b)return TRUE;
else return FALSE;
}
Status LT(KeyType a,KeyType b)
{
if(a<b)return TRUE;
else return FALSE;
}
Status SearchBBST(BBSTree T,KeyType key,BBSTree f,BBSTree &p)
{
if(!T) {p=f;return FALSE;}
else if (EQ(key,T->data.key)) {p=T;return TRUE;}
else if (LT(key,T->data.key)) return SearchBBST(T->lchild,key,T,p);
else return SearchBBST(T->rchild,key,T,p);
}
Status InsertBBST(BBSTree &T, ElemType e)
{
BBSTree p,s;
if(!SearchBBST(T,e.key,NULL,p))
{
s=(BBSTree)malloc(sizeof(BBSNode));
s->data=e;s->lchild=s->rchild=NULL;
if(!p)T=s;
else if (LT(e.key,p->data.key)) p->lchild=s;
else p->rchild=s;
return TRUE;
}
else return FALSE;
}
Status OTFSearch(BBSTree T,KeyType key,int &cnt) //仅用于查找，同时统计出查找次数
{ //在二叉排序树T中查找key
if(!T){return FALSE;} //查找不成功
else if(EQ(key,T->data.key)){cnt++;return TRUE;}//查找成功
else if(LT(key,T->data.key))
return OTFSearch(T->lchild,key,++cnt); //在左子树中继续查找
else return OTFSearch(T->rchild,key,++cnt); //在右子树中继续查找
}
Status DeleteBBST(BBSTree &T, KeyType key) //此算法自己完成,参见//algorithm9.7
{
if(!T)return FALSE;
else {
if (EQ(key,T->data.key)){return Delete(T);}
else if(LT(key,T->data.key))return DeleteBBST(T->lchild,key);
else return DeleteBBST(T->rchild,key);
}
}
Status Delete(BBSTree &p)//此算法自己完成,参见algorithm9.8 //程序中出现的delete s;相当于C中的free(s);
{
BBSTree 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->lchild;
delete s;
}
return TRUE;
}
Status InsertAVL(BBSTree &T,ElemType e,int &taller) //此算法自己完成,参见algorithm9.11 （开始点1）
{
if(!T){
T=(BBSTree) malloc(sizeof(BBSNode)); T->data=e;
T->lchild=T->rchild=NULL; T->bf=EH;taller=TRUE;
}
else
{
if(EQ(e.key,T->data.key))
{taller=FALSE;return 0;}
if(LT(e.key,T->data.key))
{
if(!InsertAVL(T->lchild,e,taller)) return 0;
if(taller)
switch(T->bf)
{
case LH:
LeftBalance(T);taller=FALSE;break;
case EH:
T->bf=LH;taller=TRUE;break;
case RH:
T->bf=EH;taller=FALSE;break;
}
}
else
{
if(!InsertAVL(T->rchild,e,taller))return 0;
if(taller)
switch(T->bf)
{
case LH:
T->bf=EH;taller=FALSE;break;
case EH:
T->bf=RH;taller=TRUE;break;
case RH:
RightBalance(T);taller=FALSE;break;
}
}
}
return 1;
}
void LeftBalance(BBSTree &T)//此算法自己完成,参见algorithm9.12 (2)
{
BBSTree rd,lc;
lc=T->lchild;
switch(lc->bf)
{
case LH:
T->bf=lc->bf=EH;
R_Rotate(T);break;
case RH:
rd=lc->rchild;
switch(rd->bf){
case LH:T->bf=RH;lc->bf=EH;break;
case EH:T->bf=lc->bf=EH;break;
case RH:T->bf=EH;lc->bf=LH;break;
}
rd->bf=EH;
L_Rotate(T->lchild);
R_Rotate(T);
}
}
void RightBalance(BBSTree &T) //T所指结点为根的二叉树作做右平衡旋转,结束时指针T指向新的根节点；
{
BBSTree rc,ld;
rc=T->rchild; //rc指向*T的右子树根结点
switch(rc->bf){ //检查*T的右子树平衡度,并作相应的平衡处理
case RH: //新结点插入在*T的右孩子的右子树上,要做单右旋处理
T->bf=rc->bf=EH;
L_Rotate(T);
break;
case LH: //新结点插入在*T的右孩子的左子树上，要做双旋处理
ld=rc->lchild; //rd指向*T的右孩子的左子树根
switch(ld->bf){ //修改*T及其右孩子的平衡因子
case LH:T->bf=LH;rc->bf=EH;break;
case EH:T->bf=rc->bf=EH;break;
case RH:T->bf=EH;rc->bf=RH;break;
}
ld->bf=EH;
R_Rotate(T->rchild); //对*T的右孩子做右旋平衡处理
L_Rotate(T); //对*T做左旋处理
}
}
void R_Rotate(BBSTree &p) //此算法自己完成,参见algorithm9.9 (3)
{
BBSTree lc;
lc=p->lchild;
p->lchild=lc->rchild;
lc->rchild=p;p=lc;
}
void L_Rotate(BBSTree &p)//此算法自己完成,参见algorithm9.10 (4)
{
BBSTree rc;
rc=p->rchild;
p->rchild=rc->lchild;
rc->lchild=p;p=rc;
}
void BBSTPrintMessage(BBSTree T) //输出值及平衡因子
{
if(T){
if(T->lchild)BBSTPrintMessage(T->lchild);
printf("%-5d%-5dn",T->data.key,T->bf);
if(T->rchild)BBSTPrintMessage(T->rchild);
}
}
void BBSTPrintTree(BBSTree p,int n) //按树形输出值
{
if(p!=NULL){
if(p->rchild)BBSTPrintTree(p->rchild,n+1);
for(int i=0;i
printf("-->%dn",p->data.key);
if(p->lchild)BBSTPrintTree(p->lchild,n+1);
}
}
void InitBBST(BBSTree &T) //初始化二叉平衡排序树BBST
{
T=NULL;
}
void CreatBBST(BBSTree &T,int n) //创建具有n个结点的BBS树
{
int i,taller=0;
ElemType e;
for(i=0;i<n;i++){
e.key=i+1; //取1到n的整数
InsertAVL(T,e,taller);
}
}
void DestroyBBST(BBSTree &T) //销毁二叉平衡排序树BBST
{
BBSTree lc,rc;
if(T){
lc=T->lchild;rc=T->rchild;
if(T->lchild)DestroyBBST(lc);
if(T->rchild)DestroyBBST(rc);
free(T);
T=NULL;
}
}
void main()
{
int n; //树的总结点数
BBSTree T; //存放树根结点
KeyType key; //存放待查找的关键字
int cnt=0; //用于统计查找次数
InitBBST(T); //初始化二叉平衡树BBST
printf("n输入结点数n=");
scanf("%d",&n);
CreatBBST(T,n); //创建具有15个结点值为1至15的BBST
BBSTPrintMessage(T); //显示BBST的结点元素值及平衡因子
BBSTPrintTree(T,0); //以树形显示BBST
printf("n输入待查关键字key=:");
scanf("%d",&key); //输入要查找的关键字
if(OTFSearch(T,key,cnt)) //若找到,显示关键字及查找次数
printf("n找到%d用%d次!n",key,cnt);
else printf("n查无此数!n"); //若找不到,输出无此关键字
DeleteBBST(T,key); //删除该关键字所在的结点
BBSTPrintTree(T,0); //显示删除后的树
DestroyBBST(T); //程序结束前销毁BBST
getch(); //按任意键结束程序
}