【正文】 的值 ， 用它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素 （ 記錄 ） 。 表中 “ 學(xué)號(hào) ”即可看成主關(guān)鍵碼 ， “ 姓名 ” 則應(yīng)視為次關(guān)鍵碼 ， 因可能有同名同姓的學(xué)生 。 分為靜態(tài)查找表和動(dòng)態(tài)查找表兩類 。 按給定的某個(gè)值 kx， 在查找表中查找關(guān)鍵碼為給定值 kx的數(shù)據(jù)元素 （ 記錄 ） 。 要是整個(gè)表檢測(cè)完 ， 還沒有找到 ， 則查找失敗 ，此時(shí) ， 查找結(jié)果應(yīng)給出一個(gè) “ 空 ” 記錄或 “ 空 ” 指針 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 8 在手工繪制表格時(shí) ， 總是根據(jù)有多少數(shù)據(jù)項(xiàng) ， 每個(gè)數(shù)據(jù)項(xiàng)應(yīng)留多大寬度來確定表的結(jié)構(gòu) ， 即表頭的定義 。 在計(jì)算機(jī)中存儲(chǔ)的表與手工繪制的類似 ， 需要定義表的結(jié)構(gòu) ， 并根據(jù)表的大小為表分配存儲(chǔ)單元 。 /* 出生日期類型定義 */ typedef struct { char year[5]； /* 年：用字符型表示 ， 寬度為 4個(gè)字符 */ char month[3]； /* 月：字符型 ， 寬度為 2 */ char date[3]； /* 日：字符型 ， 寬度為 2 */ }BirthDate； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 9 /* 數(shù)據(jù)元素類型定義 */ typedef struct { char number[7]； /* 學(xué)號(hào)：字符型 ， 寬度為 6 */ char name[9]； /* 姓名：字符型 ， 寬度為 8 */ char sex[3]； /* 性別：字符型 ， 寬度為 2 */ BirthDate birthdate； /* 出生日期：構(gòu)造類型 ， 由該類型的寬度確定 */ char efrom[21]； /* 來源：字符型 ， 寬度為 20 */ int results； /* 成績(jī)：整型 ， 寬度由 “ 程序設(shè)計(jì) C語言工具軟件 ” 決定 */ } ElemType； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 10 以上定義的數(shù)據(jù)元素類型 ， 相當(dāng)于手工繪制的表頭 。 可以用數(shù)組分配 ， 即順序存儲(chǔ)結(jié)構(gòu)；也可以用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)動(dòng)態(tài)分配 。 /* 順序存儲(chǔ)結(jié)構(gòu) */ typedef struct{ ElemType *elem； /* 數(shù)組基址 */ int length； /* 表長(zhǎng)度 */ }S_TBL； 靜態(tài)查找表結(jié)構(gòu) 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 13 /* 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)結(jié)點(diǎn)類型 */ typedef struct NODE{ ElemType elem； /* 結(jié)點(diǎn)的值域 */ truct NODE *next； /* 下一個(gè)結(jié)點(diǎn)指針域 */ }NodeType； 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 14 順序查找 順序查找又稱線性查找 ， 是最基本的查找方法之一 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 15 【 算法 】 以順序存儲(chǔ)為例 ， 數(shù)據(jù)元素從下標(biāo)為 1的數(shù)組單元開始存放 ， 0號(hào)單元留空 。[i].keykx。 定義：在查找成功時(shí) ， 平均查找長(zhǎng)度 ASL是指為確定數(shù)據(jù)元素在表中的位置所進(jìn)行的關(guān)鍵碼比較次數(shù)的期望值 。 顯然 ， 不同的查找方法 ，Ci可以不同 。C i n ∑ i=1 n ∑ i=1 Pi=1 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 17 Ci為表中第 i個(gè)數(shù)據(jù)元素的關(guān)鍵碼與給定值 kx相等時(shí) ， 按算法定位時(shí)關(guān)鍵碼的比較次數(shù) 。 就上述算法而言 ， 對(duì)于 n個(gè)數(shù)據(jù)元素的表 ， 給定值 kx與表中第 i個(gè)元素關(guān)鍵碼相等 ， 即定位第 i個(gè)記錄時(shí) ， 需進(jìn)行 ni+1次關(guān)鍵碼比較 ， 即 Ci=ni+1。 算法中的基本工作就是關(guān)鍵碼的比較 ， 因此 ， 查找長(zhǎng)度的量級(jí)就是查找算法的時(shí)間復(fù)雜度 ， 其為 O(n)。（ ni+1） n ∑ i=1 n ∑ i=1 ASL= （ ni+1） = １ ─ ｎ ｎ＋１ ─── ２ 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 18 許多情況下 ， 查找表中數(shù)據(jù)元素的查找概率是不相等的 。 順序查找缺點(diǎn)是當(dāng) n很大時(shí) ， 平均查找長(zhǎng)度較大 ， 效率低；優(yōu)點(diǎn)是對(duì)表中數(shù)據(jù)元素的存儲(chǔ)沒有要求 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 19 有序表即是表中數(shù)據(jù)元素按關(guān)鍵碼升序或降序排列 。 不斷重復(fù)上述查找過程 ， 直到查找成功 ， 或所查找的區(qū)域無數(shù)據(jù)元素 ， 查找失敗 。 //取中點(diǎn) a. 若 kx[mid].key， high=mid1；轉(zhuǎn) ② // 查找在左半?yún)^(qū)進(jìn)行 b. 若 kx[mid].key， low=mid+1；轉(zhuǎn) ② // 查找在右半?yún)^(qū)進(jìn)行 c. 若 kx=[mid].key， 返回?cái)?shù)據(jù)元素在表中位置 // 查找成功 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 21 【 例 】 有序表按關(guān)鍵碼排列如下： 7， 14， 18， 21， 23， 29， 31， 35， 38，42， 46， 49， 52 在表中查找關(guān)鍵碼為 14和 22的數(shù)據(jù)元素 。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 28 【 性能分析 】 從折半查找過程看 ， 以表的中點(diǎn)為比較對(duì)象 ， 并以中點(diǎn)將表分割為兩個(gè)子表 ， 對(duì)定位到的子表繼續(xù)這種操作 。 49 38 29 18 7 42 52 31 23 46 35 14 21 圖 例 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 29 可以看到 ， 查找表中任一元素的過程 ， 即是判定樹中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵碼的比較次數(shù) ，也即該元素結(jié)點(diǎn)在樹中的層次數(shù) 。 因此 ， 折半查找在查找成功時(shí) ， 所進(jìn)行的關(guān)鍵碼比較次數(shù)至多為 。 為便于討論 ，以樹高為 k的滿二叉樹 (n=2k1)為例 。C i n ∑ i=1 =(1/n)[1 20+2 21+… ＋ k 2k1] =((n+1)/n) log2(n+1)1≈ log2(n+1)1 所以 ， 折半查找的時(shí)間效率為 O(log2n)。 ⑵ 左右子樹也都是二叉排序樹 。 58 42 98 70 90 63 45 55 83 67 10 二 .二叉排序樹查找過程 從其定義可見 ， 二叉排序樹的查找過程為： ① 若查找樹為空 ， 查找失敗 。 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 34 ③ 若相等 ， 查找成功 ， 結(jié)束查找過程 ， 否則 ， a． 當(dāng)給 kx小于根結(jié)點(diǎn)關(guān)鍵碼 ， 查找將在以左子女為根的子樹上繼續(xù)進(jìn)行 ， 轉(zhuǎn) ① b． 當(dāng)給 kx大于根結(jié)點(diǎn)關(guān)鍵碼 ， 查找將在以右子女為根的子樹上繼續(xù)進(jìn)行 ， 轉(zhuǎn) ① 以二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu) ， 則查找過程算法程序描述如下： typedef struct NODE { ElemType elem。 /*左 、 右指針字段 */ }NodeType。 *q=t。*q=(*q)rc。*q=(*q)lc。break。 } 2022年 10月 23日 數(shù)據(jù)結(jié)構(gòu)講義 36 三 .二叉排序樹插入操作和構(gòu)造一棵二叉排序樹 先討論向二叉排序樹中插入一個(gè)結(jié)點(diǎn)的過程：設(shè)待插入結(jié)點(diǎn)的關(guān)鍵碼為 kx， 為將其插入 ， 先要在二叉排序樹中進(jìn)行查找 ， 若查找成功 ， 按二叉排序樹定義 ， 待插入結(jié)點(diǎn)已存在 ， 不用插入；查找不成功時(shí) ， 則插入之 。 構(gòu)造一棵二叉排序樹則是逐個(gè)插入結(jié)點(diǎn)的過程 。 int flag=0。p,amp。 /*在 *t為根的子樹上查找 */ { s=(NodeType *)malloc(sizeof(NodeType))。 slc=NULL。 flag=1。 /*向空樹中插入時(shí) */ else if (kxp) prc=s。 /*插入結(jié)點(diǎn)為 p的左子女 */ } return flag。 理想的情況是依據(jù)關(guān)鍵碼直接得到其對(duì)應(yīng)的數(shù)據(jù)元素位置 ， 即要求關(guān)鍵碼與數(shù)據(jù)元素間存在一一對(duì)應(yīng)關(guān)系 ， 通過這個(gè)關(guān)系 ， 能很快地由關(guān)鍵碼得到對(duì)應(yīng)的數(shù)據(jù)元素位置 。 選取關(guān)鍵碼與元素位置間的函數(shù)為 f(key)=key mod 11