2 qq 24299835 qq_24299835 于 2014.12.07 15:42 提问

排序与查找及其应用:设计一个程序,用于查询一个IP所在的机构设计一个程序,用于查询一个IP所在的机构

设计一个程序,用于查询一个IP所在的机构。具体要求:1. 设计一个函数,用于比较两个IP地址(字符串)的大小,
2. 从外部数据文件(IP.TXT)中读取IP数据;
3. 用平衡二叉排序树存储IP及其所属机构名称;4. 输入一个IP地址,查找并输出与此IP对应的机构名称;
5. 输入一个机构名称,查询与此机构对应的的IP地址;

2个回答

devmiao
devmiao   Ds   Rxr 2014.12.07 16:07

算法部分可以使用STL。

zxt520886
zxt520886   2014.12.13 19:13

#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%-5d\n",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("-->%d\n",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(); //按任意键结束程序
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!