?? bo9-5.c
字號:
/* bo9-5.c 動態查找表(雙鏈鍵樹)的基本操作 */
Status InitDSTable(DLTree *DT)
{ /* 操作結果: 構造一個空的雙鏈鍵樹DT */
*DT=NULL;
return OK;
}
void DestroyDSTable(DLTree *DT)
{ /* 初始條件: 雙鏈鍵樹DT存在。操作結果: 銷毀雙鏈鍵樹DT */
if(*DT) /* 非空樹 */
{
if((*DT)->kind==BRANCH&&(*DT)->a.first) /* *DT是分支結點且有孩子 */
DestroyDSTable(&(*DT)->a.first); /* 銷毀孩子子樹 */
if((*DT)->next) /* 有兄弟 */
DestroyDSTable(&(*DT)->next); /* 銷毀兄弟子樹 */
free(*DT); /* 釋放根結點 */
*DT=NULL; /* 空指針賦0 */
}
}
Record *SearchDLTree(DLTree T,KeysType K)
{ /* 在非空雙鏈鍵樹T中查找關鍵字等于K的記錄,若存在, */
/* 則返回指向該記錄的指針,否則返回空指針。算法9.15,有改動 */
DLTree p;
int i;
if(T)
{
p=T; /* 初始化 */
i=0;
while(p&&i<K.num)
{
while(p&&p->symbol!=K.ch[i]) /* 查找關鍵字的第i位 */
p=p->next;
if(p&&i<K.num) /* 準備查找下一位 */
p=p->a.first;
++i;
} /* 查找結束 */
if(!p) /* 查找不成功 */
return NULL;
else /* 查找成功 */
return p->a.infoptr;
}
else
return NULL; /* 樹空 */
}
void InsertDSTable(DLTree *DT,Record *r)
{ /* 初始條件: 雙鏈鍵樹DT存在,r為待插入的數據元素的指針 */
/* 操作結果: 若DT中不存在其關鍵字等于(*r).key.ch的數據元素, */
/* 則按關鍵字順序插r到DT中 */
DLTree p=NULL,q,ap;
int i=0;
KeysType K=r->key;
if(!*DT&&K.num) /* 空樹且關鍵字符串非空 */
{
*DT=ap=(DLTree)malloc(sizeof(DLTNode));
for(;i<K.num;i++) /* 插入分支結點 */
{
if(p)
p->a.first=ap;
ap->next=NULL;
ap->symbol=K.ch[i];
ap->kind=BRANCH;
p=ap;
ap=(DLTree)malloc(sizeof(DLTNode));
}
p->a.first=ap; /* 插入葉子結點 */
ap->next=NULL;
ap->symbol=Nil;
ap->kind=LEAF;
ap->a.infoptr=r;
}
else /* 非空樹 */
{
p=*DT; /* 指向根結點 */
while(p&&i<K.num)
{
while(p&&p->symbol<K.ch[i]) /* 沿兄弟結點查找 */
{
q=p;
p=p->next;
}
if(p&&p->symbol==K.ch[i]) /* 找到與K.ch[i]相符的結點 */
{
q=p;
p=p->a.first; /* p指向將與K.ch[i+1]比較的結點 */
++i;
}
else /* 沒找到,插入關鍵字 */
{
ap=(DLTree)malloc(sizeof(DLTNode));
if(q->a.first==p)
q->a.first=ap; /* 在長子的位置插入 */
else /* q->next==p */
q->next=ap; /* 在兄弟的位置插入 */
ap->next=p;
ap->symbol=K.ch[i];
ap->kind=BRANCH;
p=ap;
ap=(DLTree)malloc(sizeof(DLTNode));
i++;
for(;i<K.num;i++) /* 插入分支結點 */
{
p->a.first=ap;
ap->next=NULL;
ap->symbol=K.ch[i];
ap->kind=BRANCH;
p=ap;
ap=(DLTree)malloc(sizeof(DLTNode));
}
p->a.first=ap; /* 插入葉子結點 */
ap->next=NULL;
ap->symbol=Nil;
ap->kind=LEAF;
ap->a.infoptr=r;
}
}
}
}
typedef struct
{
char ch;
DLTree p;
}SElemType; /* 定義棧元素類型 */
#include"c3-1.h"
#include"bo3-1.c"
void TraverseDSTable(DLTree DT,void(*Vi)(Record))
{ /* 初始條件: 雙鏈鍵樹DT存在,Vi是對結點操作的應用函數, */
/* ViR是對記錄操作的應用函數 */
/* 操作結果: 按關鍵字的順序輸出關鍵字及其對應的記錄 */
SqStack s;
SElemType e;
DLTree p;
int i=0,n=8;
if(DT)
{
InitStack(&s);
e.p=DT;
e.ch=DT->symbol;
Push(&s,e);
p=DT->a.first;
while(p->kind==BRANCH) /* 分支結點 */
{
e.p=p;
e.ch=p->symbol;
Push(&s,e);
p=p->a.first;
}
e.p=p;
e.ch=p->symbol;
Push(&s,e);
Vi(*(p->a.infoptr));
i++;
while(!StackEmpty(s))
{
Pop(&s,&e);
p=e.p;
if(p->next) /* 有兄弟結點 */
{
p=p->next;
while(p->kind==BRANCH) /* 分支結點 */
{
e.p=p;
e.ch=p->symbol;
Push(&s,e);
p=p->a.first;
}
e.p=p;
e.ch=p->symbol;
Push(&s,e);
Vi(*(p->a.infoptr));
i++;
if(i%n==0)
printf("\n"); /* 輸出n個元素后換行 */
}
}
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -