/* 判別給定二叉樹t是否為二叉排序樹。*/
/* 若是,則返回true,否則false */
二叉樹的型別bitree定義如下:
typedef struct elemtype;
typedef struct bitnode bitnode, *bitree;
status isbstree(bitree t)
/* 判別給定二叉樹t是否為二叉排序樹。*/
/* 若是,則返回true,否則false */
if(t->lchild!=null&&k>t->lchild->data.key)
if(isbstree(t->lchild))return true;
if(t->rchild!=null&&krchild->data.key)
if(isbstree(t->rchild))return true;
return false;
}9.33③ 編寫遞迴演算法,從大到小輸出給定二叉排序樹
中所有關鍵字不小於x的資料元素。要求你的演算法的時
間複雜度為o(log2n+m),其中n為排序樹中所含結點數,
m為輸出的關鍵字個數。
實現下列函式:
void orderout(bitree t, keytype x, void(*visit)(telemtype));
/* output is to use visit(t->data); */
二叉樹的型別bitree定義如下:
typedef struct elemtype;
typedef struct bitnode bitnode, *bitree;
void orderout(bitree t, keytype x, void(*visit)(telemtype))
/* output is to use visit(t->data); */
9.44④ 已知某雜湊表的裝載因子小於1,雜湊函式
h(key)為關鍵字(識別符號)的第乙個字母在字母表中
的序號,處理衝突的方法為線性探測開放定址法。
試編寫乙個按第乙個字母的順序輸出雜湊表中所有
關鍵字的演算法。
實現下列函式:
void printkeys(hashtable ht, void(*print)(strkeytype));
/* 依題意用print輸出關鍵字 */
雜湊表的型別hashtable定義如下:
#define success 1
#define unsuccess 0
#define duplicate -1
typedef char strkeytype[4];
typedef struct helemtype;
int hashsize = ;
typedef struct hashtable;
void printkeys(hashtable ht, void(*print)(strkeytype))
/* 依題意用print輸出關鍵字 */
}}9.45③ 假設雜湊表長為m,雜湊函式為h(x),用鏈位址法
處理衝突。試編寫輸入一組關鍵字並建造雜湊表的演算法。
實現下列函式:
int buildhashtab(chainhashtab &h, int n, hkeytype es);
/* 直接呼叫下列函式
/* 雜湊函式
/* int hash(chainhashtab h, hkeytype k); */
/* 衝突處理函式
/* int collision(chainhashtab h, hlink &p); */
雜湊表的型別chainhashtab定義如下:
#define num 7
#define nullkey -1
#define success 1
#define unsuccess 0
#define duplicate -1
typedef char hkeytype;
typedef struct hnode *hlink;
typedef struct chainhashtab; // 鏈位址雜湊表
int hash(chainhashtab h, hkeytype k)
status collision(chainhashtab h, hlink &p) else return unsuccess;
}int buildhashtab(chainhashtab &h, int n, hkeytype es)
/* 直接呼叫下列函式
/* 雜湊函式
/* int hash(chainhashtab h, hkeytype k); */
/* 衝突處理函式
/* int collision(chainhashtab h, hlink &p); */
; if(flag==0)}}}
資料結構課後習題答案第九章
第九章查詢 參 9.1 int seqsearch rectype r,keytype k 監視哨設在n個元素的公升序順序表低下標端,順序查詢關鍵字為k的資料 元素。若存在,則返回其在順序表中的位置,否則,返回0 r 0 key k i n while r i key k i if i 0 r i ...
《資料結構》第九章集合
第九章集合 一 選擇題 1.若查詢每個記錄的概率均等,則在具有n個記錄的連續順序檔案中採用順序查詢法查詢乙個記錄,其平均查詢長度asl為 北京航空航天大學 2000 一 8 2分 a n 1 2 b.n 2 c.n 1 2 d.n 2.對n個元素的表做順序查詢時,若查詢每個元素的概率相同,則平均查詢...
資料結構作業系統答案
2.11 設順序表l中的資料元素遞增有序。試寫一演算法,將x插入到l的適當位置上,並保 持該表的有序性。要求實現下列函式 void insertorderlist sqlist l,elemtype x 在有序的順序表 l 中保序插入資料元素 x 順序表型別定義如下 typedef struct s...