索引與文件.ppt

1、1,索引與文件,2,索引查找 分塊查找 倒排表 樹表查找二叉排序樹 文件,索引與文件,3,索引查找 1.索引查找的思想,索引查找，又稱分級查找，它既是一種查找方法，又是一種存貯方法，稱為索引存貯。 它在我們的日常生活中有著廣泛的應(yīng)用。例如，在漢語字典中查找某個漢字時，若知道某個漢字讀者，則可以先在音節(jié)表中查找到對應(yīng)正文中的頁碼，然后再在正文中所對應(yīng)的頁中查出待查的漢字；若知道該漢字的字形，但不知道讀者，則可以先在部首表中根據(jù)字的部首查找到對應(yīng)檢字表中的頁碼，再在檢字表中根據(jù)字的筆畫找到該漢字所在的頁碼。在這里，整個字典就是索引查找的對象，字典的正文是字典的主要部分，被稱之為主表，而檢字表，部首

2、表和音節(jié)表都有是為了方便查找主表而建立的索引，所以被稱之為索引表。,4,在索引查找中，主表只有一個，其中包含的是待查找的內(nèi)容，而索引表可以有多個，包含一級索引，二級索引，所需的級數(shù)可根據(jù)具體問題而定。如剛才的利用讀音查找漢字為一級索引，而 利用字形查找漢字為二級索引（部首表檢字表漢字）。在此，我們僅討論一級索引。,索引查找是在線性表（主表）的索引存貯結(jié)構(gòu)上進(jìn)行的，而索引存貯的基本思想是：首先將一個線性表（主表）按照一定的規(guī)則分成若干個邏輯上的子表，并為每個子表分別建立一個索引項(xiàng)，由所有這些索引項(xiàng)得到主表的一個索引表，然后，可采用順序或鏈接的方法來存儲索引表和各個子表。索引表中的每個索引項(xiàng)通常包

3、含三個域：一是索引值域，用來存儲標(biāo)識對應(yīng)子表的索引值，它相當(dāng)于記錄的關(guān)鍵字，在索引表中由此索引值來唯一標(biāo)識一個索引項(xiàng)（子表）；二是子表的開始位置，用來存儲對應(yīng)子表的第一個元素的存儲位置；三是子表的長度，用來存儲對應(yīng)子表的元素個數(shù)。,5,索引文件：由索引表和主表共同構(gòu)成，索引表由關(guān)鍵字與物理記錄構(gòu)成，通常關(guān)鍵字是有序的。 索引查找的步驟： （1）先讀取索引表到內(nèi)存 （2）根據(jù)索引表所指物理地址將記錄所在的主表數(shù)據(jù)塊讀入內(nèi)存后查找 （3）返回查找結(jié)果 若主表的內(nèi)容按關(guān)鍵字排序，則稱為索引順序文件，否則稱為索引無序文件。索引順序文件可用于分塊查找。,6,100 140 180 220 260 300

4、 340 380,key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220,職工號 姓名 性別 職務(wù) 婚否 83 張珊 女 教師 已婚 08 李斯 男 教師 已婚 . 03 王魯 男 教務(wù)員 已婚 . 95 劉琪 女 實(shí)驗(yàn)員 未婚 . 24 岳跋 男 教師 已婚 . 47 周斌 男 教師 已婚 . 17 胡江 男 實(shí)驗(yàn)員 未婚 . 51 林青 女 教師 未婚 .,索引表,主表,索引無序文件,7,例如，設(shè)有一個學(xué)校部分教師檔案表如表8-1所示，設(shè)編號為主關(guān)鍵字，則該表可以用一個線性表L=（a1,a2, a3,a4,a5,a6

5、,a7,a8,a9,a10）來表示，其中ai (1in)表示第i位教師的信息（包含有編號，姓名，部門，職稱），而它的索引表可以按部門進(jìn)行，也可以按職稱進(jìn)行，按部門的索引表中有4個子表，分別為： 計算機(jī)系J=（ a1,a2,a3,a4） 電工系 D=(a5,a6,a7) 管理系G=(a8,a9) 成教部C=(a10),該4個子表示成一個索引表如表8-2所示。,8,表8-1 教師檔案表,表8-2 按部門的索引表,index start length,9,若按職稱進(jìn)行索引，則得到的索引表中也有4個子表，分別為： Jiaosou=(a1,a8) FuJiaosou=(a3,a7,a10) Jiangs

6、hi=(a2,a5,a9) Zhujiao=(a4,a6),這時的主表用順序存貯不太方便，因相同職稱的教師沒有連在一起，故用鏈?zhǔn)酱鎯Φ玫街鞅磔^方便。具體的存貯如圖8-4所示。在圖8-4中，箭頭上面的數(shù)字表示該元素在主表中的下標(biāo)位置（指針），每個子表中最后個元素的指針為-1，表示為空指針。,10,于是，可以得到如表8-3所示的職稱索引表。,表8-3 按職稱的索引表 index start length,11,從剛才的兩種索引表中，可以給出索引查找的基本思想如下： 第一步，在索引表中按index域查找所給值K1，這時可得到子表起始位置start 和長度length，若找不到K1，結(jié)束查找，表示查找

7、不成功。第二步，在主表的start位置開始，長度為length的范圍內(nèi)查找所給值K2，若找到，查找不成功，否則，查找不成功。,例如，對于按部門的索引查找，主表可以用順序存貯，假設(shè)K1=“D”，“D”代電工系，K2=“孫六”，則先在表8-2的索引表中找到的index域?yàn)椤癉”的項(xiàng)，得到start=4， length=3，然后從主表的第4個位置開始（即a5）找姓名為“孫六”的人，則在主表的第5個位置可以找到，故查找成功。若假設(shè)K1=“D”，K2=“楊九”，則索引表的查找與上面相同，然后在主表的第4個位置開始查找，沒找到，進(jìn)入第5個位置查找，還沒找到進(jìn)入第6位置查找，仍然沒找到，但查找的length

8、=3，既只允許3次查找，故查找不成功。若假設(shè)K1=“F”，K2=“張三”，則首先在索引表中就找不到“F”，故無需進(jìn)入主表進(jìn)行查找，查找不成功。,12,3.索引查找的性能分析,由于索引查找中涉及到兩方面查找，第一個是索引表的查找，第二個是主表的查找，假設(shè)兩種查找都按順序查找方式進(jìn)行，則索引表的平均查找長度為(m+1)/2，主表中的平均查找長度為（s+1）/2，(m為索引表的長度，S為主表中相應(yīng)子表的長度)，則索引查找的平均查找長度為：ASL=(m+1)/2+ (s+1）/2。若假定每個子表具有相同的長度，而主表的長度為n，則有n=m.s， 這時當(dāng)s= 時， 索引查找具有最小的平均查找長度，即AS

9、L=1+ 。 從該公式可以看出，索引查找的 性能優(yōu)先順序查找，但比二分查找要差，時間復(fù)雜度介于O(log2 n)O(n)之間。,13,分塊查找 1.分塊查找 的思想,分塊查找實(shí)際上就是一種索引查找，是索引查找與二分查找的結(jié)合，其性能更優(yōu)先于索引查找。原因是分塊查找的索引表是一個有序表，故可以用 二分查找 來代替 順序查找 實(shí)現(xiàn)索引表的快速查找。 具體實(shí)現(xiàn)如下：將一個含有n個元素的主表分成m個子表，但要求子表之間元素是按關(guān)鍵字有序排列的，而子表中元素可以無序的，然后建立索引表，索引表中索引域的值用每個子表最大關(guān)鍵字代替，則可以按索引查找思想找到表中元素。,14,例如，給定關(guān)鍵字序列如下：18,7

10、,26,34,15,42,36,70,60,55,83,90,78,72,74，假設(shè)m=3，s=5，即將該序序分成3個子表，每個子表有5 個元素，則得到的主表和索引表如圖8-5所 示。,15,3.分塊查找的性能分析,分塊查找實(shí)際上就是索引查找,但分塊查找中索引的域的類型與主表的關(guān)鍵字域的類型相同，且索引表按索引域遞增（或遞減）有序，故它的平均查找長度與索引查找接近，且優(yōu)于索引查找。,16,100 140 180 220 260 300 340 380,key addr 03 180 08 140 17 340 24 260 47 300 51 380 83 100 95 220,職工號 姓名

11、性別 職務(wù) 婚否 83 張珊 女 教師 已婚 08 李斯 男 教師 已婚 . 03 王魯 男 教務(wù)員 已婚 . 95 劉琪 女 實(shí)驗(yàn)員 未婚 . 24 岳跋 男 教師 已婚 . 47 周斌 男 教師 已婚 . 17 胡江 男 實(shí)驗(yàn)員 未婚 . 51 林青 女 教師 未婚 .,索引表,數(shù)據(jù)表,17,倒排表 (Inverted Index List),對包含有大量數(shù)據(jù)對象的數(shù)據(jù)表或文件進(jìn)行搜索時，最常用的是針對對象的主關(guān)鍵碼建立索引。主關(guān)鍵碼可以唯一地標(biāo)識該對象。用主關(guān)鍵碼建立的索引叫做主索引。 主索引的每個索引項(xiàng)給出對象的關(guān)鍵碼和對象在表或文件中的存放地址。 但在實(shí)際應(yīng)用中有時需要針對其它屬性進(jìn)

12、行搜索。例如，查詢?nèi)缦碌穆毠ば畔ⅲ?(1) 列出所有教師的名單；,對象關(guān)鍵碼 key 對象存放地址 addr,18,(2) 已婚的女性職工有哪些人？ 這些信息在數(shù)據(jù)表或文件中都存在，但都不是關(guān)鍵碼，為回答以上問題，只能到表或文件中去順序搜索，搜索效率極低。 因此，除主關(guān)鍵碼外，可以把一些經(jīng)常搜索的屬性設(shè)定為次關(guān)鍵碼，并針對每一個作為次關(guān)鍵碼的屬性，建立次索引。 在次索引中，列出該屬性的所有取值，并對每一個取值建立有序鏈表，把所有具有相同屬性值的對象按存放地址遞增的順序或按主關(guān)鍵碼遞增的順序鏈接在一起。,19,次索引的索引項(xiàng)由次關(guān)鍵碼、鏈表長度和鏈表本身等三部分組成。 例如，為了回答上述的查詢，

13、我們可以分別建立“性別”、“婚否”和“職務(wù)”次索引。,性別次索引,次關(guān)鍵碼 男 女 計 數(shù) 5 3 地址指針,指針 03 08 17 24 47 51 83 95,20,婚否次索引,次關(guān)鍵碼 已婚 未婚 計 數(shù) 5 3 地址指針,指針 03 08 24 47 83 17 51 95,職務(wù)次索引,次關(guān)鍵碼 教師 教務(wù)員 實(shí)驗(yàn)員 計 數(shù) 5 1 2 地址指針,指針 08 24 47 51 83 03 17 95,21,(1) 列出所有教師的名單； (2) 已婚的女性職工有哪些人？ 通過順序訪問“職務(wù)”次索引中的“教師”鏈，可以回答上面的查詢(1)。 通過對“性別”和“婚否”次索引中的“女性”鏈和“

14、已婚”鏈進(jìn)行求“交”運(yùn)算，就能夠找到所有既是女性又已婚的職工對象，從而回答上面的查詢(2)。 倒排表是次索引的一種實(shí)現(xiàn)。在表中所有次關(guān)鍵碼的鏈都保存在次索引中，僅通過搜索次索引就能找到所有具有相同屬性值的對象。,22,在次索引中記錄對象存放位置的指針可以用主關(guān)鍵碼表示: 可通過搜索次索引確定該對象的主關(guān)鍵碼, 再通過搜索主索引確定對象的存放地址。,23,樹表查找,二叉排序樹查找 1什么是二叉排序樹,二叉排序樹（Binary Sorting Tree），它或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹： (1)若它的左子樹非空，則左子樹上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字； (2)若它的右

15、子樹非空，則右子樹上所有結(jié)點(diǎn)的關(guān)鍵字均大于等于根結(jié)點(diǎn)的關(guān)鍵字； (3)左、右子樹本身又都是一棵二叉排序樹。,24,2二叉排序樹的數(shù)據(jù)類型描述,和第六章類似，可以用一個二叉鏈表來描述一棵二叉排序樹，具體為： struct Btreenode elemtype data; /代表關(guān)鍵字 Btreenode *left,*right; /代表左、右孩子 ;,3二叉排序樹的基本運(yùn)算,（1）二叉排序樹的插入 若二叉排序樹為空，則作為根結(jié)點(diǎn)插入，否則，若待插入的值小于根結(jié)點(diǎn)值，則作為左子樹插入，否則作為右子樹插入，算法描述為：,25,void Insert (Btreenode *BST ,elemtyp

16、e X ) if(BST= =NULL) Btreenode *p= new Btreenode; p - data = X; p-left=p-right=NULL; BST=p; else if (BST-data = X ) Insert ( BST - left,X); /在左子樹中扦入 else Insert (BST-right,X); /在右子樹中扦入,26,（2）二叉排序樹的建立 只要反復(fù)調(diào)用二叉排序樹的扦入算法即可，算法描述為：,Btreenode *Creat (int n) /建立含有n個結(jié)點(diǎn)的二叉排序樹 Btreenode *BST= NULL; for ( int i

17、=1; ix; /輸入關(guān)鍵字序列 Insert ( BST,x); return BST ;,27,例如，結(jié)定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖8-6所示。（注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二叉排序樹也不一樣）,28,29,4二叉排序 樹上的查找,（1）二叉排序 樹的查找思想 若二叉排樹為空，則查找 失敗，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟，若在查找過程中遇到二叉排序樹的葉子結(jié)點(diǎn)時，還沒有找到待找結(jié)點(diǎn)，則查找不成功。

18、,（2）二叉排序樹查找的算法實(shí)現(xiàn),30,Btreenode * find( Btreenode *BST,elentype x) /在以BST為根指針的二叉排隊(duì) 樹中查找值為x的結(jié)點(diǎn) if ( BST= =NULL) return NULL; /查找失敗 else if (BST-data= =x) /查找成功 return BST; else if (BST-datax) /進(jìn)入左子樹查找 return find ( BST-left,x); else /進(jìn)入右子樹查找 return find (BST-right,x); ,31,5二叉排序樹查找的性能分析,在二叉排序樹查找中，成功的查找次

19、數(shù)不會超過二叉樹的深度，而具有n個結(jié)點(diǎn)的二叉排序樹的深度，最好為log2n，最壞為n。因此，二叉排序樹查找的最好時間復(fù)雜度為O(log2n)，最壞的時間復(fù)雜度為O(n)，一般情形下，其時間復(fù)雜度大致可看成O(log2n)，比順序查找效率要好，但比二分查找要差。,平衡二叉樹查找 1平衡二叉樹的概念,平衡二叉樹(balanced binary tree)是由阿德爾森一維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。,32,習(xí)題,1.索引順序文件中，（）。 A. 主文件是無序的 B. 主文件是有序的 C. 不適宜隨機(jī)查找 D. 索引是

20、稠密索引 2.倒排文件中倒排表是指（）。 A. 主關(guān)鍵字索引 B. 次關(guān)鍵字索引 C. 物理順序與邏輯順序不一致 D. 多關(guān)鍵字索引 3.對625個元素采用分塊查找，若查找每個元素的概率相同，采用順序查找來確定結(jié)點(diǎn)所在的塊，則每塊分為（）結(jié)點(diǎn)最佳。 A. 9 B. 25 C. 6 D. 625 4.試比較順序文件、索引順序文件、索引無序文件、 倒排文件的優(yōu)劣。,33,作業(yè),設(shè)有一個職工文件，每個記錄包含：職工號、姓名、職稱、性別、工資，“職工號”為主關(guān)鍵字，其他為次關(guān)鍵字。試用下列結(jié)構(gòu)組織文件（1）索引無序文件（2）倒排文件,34,標(biāo)準(zhǔn)文件FILE結(jié)構(gòu)指針,FILE類型 保存被使用的文件的有關(guān)

21、信息 所有的文件操作都需要FILE類型的指針 FILE是庫文件中定義的結(jié)構(gòu)體的別名 注意不要寫成struct FILE 舉例 FILE *fp;,35,FILE類型,typedef struct short level; /*緩沖區(qū)滿空程度*/ unsigned flags; /*文件狀態(tài)標(biāo)志*/ char fd; /*文件描述符*/ unsigned char hold; /*無緩沖則不讀取字符*/ short bsize; /*緩沖區(qū)大小*/ unsigned char *buffer; /*數(shù)據(jù)緩沖區(qū)*/ unsigned char *curp; /*當(dāng)前位置指針*/ unsigned

22、istemp; /*臨時文件指示器*/ short token; /*用于有效性檢查*/ FILE;,36,文件的打開 (fopen函數(shù)),函數(shù)原型 FILE *fopen(char *filename, char *mode); 參數(shù)說明 filename:要打開的文件路徑 mode :打開模式 返回值 若成功，返回指向被打開文件的指針 若出錯，返回空指針NULL(0),37,文件的打開模式,38,文件的打開舉例,#include #include void main() FILE *fp1, *fp2, *fp3; char filename=file3.dat; /* 以文本只讀方式打開

23、file1 */ if (!(fp1=fopen(file1, r) printf(Cannot Open This File!n); exit(0); /* 退出程序 */ /* 以二進(jìn)制讀寫方式打開FILE2.TXT */ fp2=fopen(C:HOMEFILE2.TXT, rb+); /* 以二進(jìn)制讀寫方式打開file3.dat */ fp3=fopen(filename, ab+); ,39,文件的關(guān)閉 (fclose函數(shù)),函數(shù)原型 int fclose(FILE *fp); 參數(shù)說明 fp:要關(guān)閉的文件指針 返回值 若成功，返回0 若出錯，返回EOF(-1) 不用的文件應(yīng)關(guān)閉，防

24、止數(shù)據(jù)破壞丟失,40,文件的關(guān)閉舉例,FILE *fp; char file=D:USERSTUDENTS.DAT; if (!(fp=fopen(file, rb+) printf(Open file %s error!n, file); exit(0); . . fclose(fp);,41,讀寫操作(1),讀寫文件中字符的函數(shù) : 從磁盤文件讀取字符的函數(shù)是fgetc()，形式為： int fgetc (FILE *stream)； 詳細(xì)說明 將一個字符寫入磁盤文件的函數(shù)是 fputc()，其形式為： int fputc (int ch，F(xiàn)ILE *stream )；詳細(xì)說明 注：get

25、c() 和 fgetc() 功能相同，putc() 和 fputc() 相同 應(yīng)用舉例,42,讀寫操作(2),讀寫文件中字符串的函數(shù) : 從磁盤文件讀取字符串的函數(shù)是fgets()，形式為： char * fgets (char * str ，int n ，F(xiàn)ILE * stream) ; 詳細(xì)說明 將一個字符串寫入磁盤文件的函數(shù)是 fputs()，其形式為： char * fputs (char * str ，F(xiàn)ILE * stream) ； 詳細(xì)說明 注：getc() 和 fgetc() 功能相同，putc() 和 fputc() 相同 應(yīng)用舉例,43,讀寫操作(3),格式化讀寫函數(shù) 函數(shù)

26、原型 int fscanf(FILE *fp, char *format,address,.); int fprintf(FILE *fp, char *format,argument,.); 說明 與printf和scanf函數(shù)類似 從文件輸入或輸出到文件 應(yīng)用舉例,44,標(biāo)準(zhǔn)的隨機(jī)讀寫（1）,文件指針定位函數(shù) 文件位置指針 位置指針指向當(dāng)前讀寫的位置 每次讀寫文件，位置指針都會相應(yīng)移動 可以通過相關(guān)函數(shù)強(qiáng)制修改位置指針 相關(guān)函數(shù) rewind函數(shù) 詳細(xì)說明 fseek函數(shù) 詳細(xì)說明 ftell函數(shù) 詳細(xì)說明,45,標(biāo)準(zhǔn)的隨機(jī)讀寫（2）,文件隨機(jī)讀寫函數(shù)：fwrite和fread size_

27、t fwrite(void *buffer, size_t size, size_t count, FILE *fp); size_t fread (void *buffer, size_t size, size_t count, FILE *fp); 參數(shù)說明 應(yīng)用舉例,46,本章結(jié)束,再見！,同學(xué)們：,47,fgetc/getc函數(shù),函數(shù)原型 int fgetc(FILE *fp); int getc(FILE *fp); 參數(shù) fp:文件指針 返回值 若成功，返回輸入的字符 若失敗或文件結(jié)束，返回EOF,48,fputc/putc函數(shù),函數(shù)原型 int fputc(int c, FILE

28、 *fp); int putc(int c, FILE *fp); 參數(shù) c :要輸出到文件的字符 fp:文件指針 返回值 若成功，返回輸出的字符 若失敗或文件結(jié)束，返回EOF,49,讀寫文件中字符的函數(shù),#include #include void main() /讀取文件datafile.txt的內(nèi)容，并輸出至顯示器上 FILE *fp; /* 定義FILE結(jié)構(gòu)指針變量 */ char ch; if(fp = fopen (datafile.txt,r) = NULL )/* 打開并測試文件 */ printf (file cannot be opened n ); exit (1);/*

29、 若文件打開不成功，退出 */ while (ch = fgetc (fp) != EOF)/*讀文件并測試是否文件尾 */ fputc (ch,stdout);/* 輸出到標(biāo)準(zhǔn)設(shè)備文件（顯示器）顯示 */ fclose (fp);/* 關(guān)閉文件 */ ,50,fgets函數(shù),函數(shù)原型 char *fgets(char *s, int n, FILE *fp); 返回值 若成功，返回s首地址；若失敗，返回NULL 說明 從fp輸入字符串到s中 輸入n-1個字符，或遇到換行符或EOF為止 讀完后自動在字符串末尾添加0,51,fputs函數(shù),函數(shù)原型 int fputs(char *s, FILE

30、 *fp); 返回值 若成功，返回輸出字符個數(shù)(或最后的字符) 若失敗，返回EOF 說明 字符串的結(jié)束標(biāo)志0不會輸出到文件 也不會在字符串末尾自動添加換行符,52,讀寫文件中字符串的函數(shù),#include stdio.h #include void main() FILE *fp2; char buffer64; if (fp2=fopen (datafile2.txt,r) = NULL)/*以只讀方式打開文件，且測試*/ printf (cant open file n); exit (1);/* 打開不成功退出 */ while (!feof (fp2)/* 測試文件是否結(jié)束 */ if (fgets (buffer,64,fp2) != NULL)/*讀一行字符并測試是否為空*/ printf(%s,buffer) ;/* 顯示該行字符 */ fclose (fp2);/* 關(guān)閉文件 */ ,53,格式化讀寫函數(shù),#include