設(shè)計(jì)_查找實(shí)驗(yàn)1_2_07_

1、線 性 表 的 查 找在表的組織方式中，線性表是最簡單的一種。對線性表的查找一般有三種方法：順序查找、二分查找、分塊查找。一、順序查找基本知識(shí)：線性表的數(shù)據(jù)類型定義及對線性表的順序掃描操作。算法思想：從線性表一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)健字與給定值key比較，若相等，則查找成功；若掃描結(jié)束后，仍末找到關(guān)健字等于key的結(jié)點(diǎn)，則查找失敗。二、二分查找基本知識(shí)：線性表的數(shù)據(jù)類型定義、線性表中結(jié)點(diǎn)按其關(guān)健字有序排列。算法思想： 用待查值key與表的中間結(jié)點(diǎn)關(guān)健字比較（中間結(jié)點(diǎn)將線性表分為兩個(gè)子表），若比較結(jié)果相等，則查找成功；若待查值key大于中間結(jié)點(diǎn)關(guān)健字，選右子表繼續(xù)比較；若待

2、查值key小于中間結(jié)點(diǎn)關(guān)健字，選左子表繼續(xù)比較； 重復(fù)，直到查找成功或結(jié)束；三、分塊查找基本知識(shí)：分塊查找是把線性表分成若干塊，各塊中的結(jié)點(diǎn)順序可任意亦可有序，但塊與塊之間必須按關(guān)健字大小有序，即前一塊中的最大關(guān)健字要小于后一塊中的最小關(guān)健字。因此，與線性表的順序查找和二分查找不同，除定義線性表的數(shù)據(jù)類型外，還須定義一個(gè)遞增有序的索引表，以描述線性表“分塊有序”的狀態(tài)算法思想：分塊查找實(shí)際上是對索引表和線性表的兩次查找。順序查找或二分查找索引表：以確定待查結(jié)點(diǎn)在哪一塊。由于索引表遞增有序（即塊與塊之間按關(guān)健字大小有序），因此，索引表的查找常采用二分查找算法以提高算法效率。在所確定的塊內(nèi)順序查找

3、線性表：確定待查結(jié)點(diǎn)在線性表的確切位置。由于塊內(nèi)結(jié)點(diǎn)即可無序亦可有序，因此，塊內(nèi)查找一般采用順序查找算法。查找實(shí)驗(yàn)（兩次課完成）一、實(shí)驗(yàn)題目: 請編寫一個(gè)完整的程序，用菜單驅(qū)動(dòng)方法實(shí)現(xiàn)：利用分塊查找算法在線性表（學(xué)生情況表）list中查找給定值key(學(xué)號(hào))的結(jié)點(diǎn)，并將該結(jié)點(diǎn)的部分?jǐn)?shù)據(jù)進(jìn)行修改。注：在此實(shí)驗(yàn)中你還可以添加一個(gè)或幾個(gè)你最熟悉的查找算法來實(shí)現(xiàn)此功能。二、解題思路：例：輸入學(xué)號(hào)：30207； 選擇課程名：語文； 輸入修改成績：100；在學(xué)生情況表中查找學(xué)號(hào)為“30207”的學(xué)生記錄；將該學(xué)生記錄的語文成績修改為100；建立文件算法：建立待查找的數(shù)據(jù)文件SCORE.TXT的函數(shù)crea

4、t( )輸入算法： 在待查找的數(shù)據(jù)文件SCORE.TXT中找輸出算法： 將修改后的線性表（學(xué)生情況表）數(shù)據(jù)輸出到文件SCORE.TXT中，算法要點(diǎn)： 分塊查找的查找過程分兩步進(jìn)行: 先在線性表中確定待查找的結(jié)點(diǎn)屬于哪一塊。由于塊與塊之間按關(guān)健字大小有序，因此，塊間查找可采用二分查找算法。 在所確定的塊內(nèi)查找待查結(jié)點(diǎn)，由于塊內(nèi)結(jié)點(diǎn)即可無序亦可有序，因此，塊內(nèi)查找一般可采用順序查找算法。找到指定結(jié)點(diǎn)后，按要求修改結(jié)點(diǎn)中的有關(guān)數(shù)據(jù)。三、數(shù)據(jù)類型及算法1數(shù)據(jù)類型定義（1）學(xué)生的結(jié)點(diǎn)結(jié)構(gòu)typedef struct char num8,name10; /學(xué)生的學(xué)號(hào)，姓名int age,chin,phy,

5、chem,eng; /學(xué)生的年齡，中文、物理、化學(xué)和英語成績 STUDENT;（2）線性表的結(jié)點(diǎn)結(jié)構(gòu)typedef struct keytype key8; /關(guān)鍵字STUDENT stu; TABLE;（3）索引表的結(jié)點(diǎn)結(jié)構(gòu)typedef struct keytype key8; int low,high; INDEX;2操作算法（1）輸入算法從SCORE.TXT文件中讀出數(shù)據(jù)、建立線性表及索引表可通過調(diào)用函數(shù)readtxt(void)完成，此函數(shù)算法如下：void readtxt(void) / 構(gòu)造線性表list及索引表inlist FILE *fp; int i,d; char max

6、8; fp=fopen(“score.txt”,”r”); /以只讀方式打開SCORE.TXT文件 for(i=0;iM;i+) / 將SCORE.TXT中的M個(gè)數(shù)據(jù)輸?shù)骄€性表list中 fscanf(fp,”%s”,listi.stu.num);/從文件SCORE.TXT中輸入第i個(gè)學(xué)生的學(xué)號(hào) fscanf(fp,”%s”,); /從SCORE.TXT中輸入第i個(gè)學(xué)生的姓名 fscanf(fp,”%d”,&listi.stu.chin); /從SCORE.TXT中輸入第i生的中文成績 fscanf(fp,”%d”,&listi.stu.phy); /從SCORE.

7、TXT中輸入第i生的物理成績 fscanf(fp,”%d”,&listi.stu.chem); /從SCORE.TXT中輸入第i生的化學(xué)成績 fscanf(fp,”%d”,&listi.stu.eng); /從SCORE.TXT中輸入第i生的英語成績 strcpy(listi.key,listi.stu.num); /將第i個(gè)學(xué)生的學(xué)號(hào)設(shè)為關(guān)鍵字 for(i=0;iB;i+) / 構(gòu)造索引表inlist,B是線性表的塊數(shù) inlisti.low=i+(i*(S-1); / 每塊內(nèi)結(jié)點(diǎn)數(shù)為S inlisti.high=i+(i+1)*(S-1); strcpy(max,list0.stu.num

8、);/將第0個(gè)學(xué)生的學(xué)號(hào)復(fù)制到數(shù)組max中d=0;for(i=1;iM;i+) if(strcmp(max,listi.stu.num)0) /串max小于串listi.stu.num strcpy(max,listi.stu.num); /將大的串放到max中,這是在線性表的一塊中找 if(i+1)%6 = 0 ) strcpy(inlistd.key,max); d+;/將索引表中第d個(gè)元素的inlistd.key if(iM-1) /設(shè)為線性表中第d個(gè)塊的學(xué)號(hào)的最大值strcpy(max,listi+1.stu.num);/將線性表中的下一塊的第一個(gè)學(xué)生的學(xué)號(hào)i+; /復(fù)制到max中,去

9、求該塊中的最大學(xué)號(hào) fclose(fp); / 關(guān)閉SCORE.TXT文件 （2）動(dòng)態(tài)分塊查找算法void modify (char *key,int kc,int cj)/kc是課程號(hào)cj是成績key是要找的學(xué)號(hào) int low1=0,high1=B-1,mid1,i,j; int flag=0; while(low10) /到前邊的塊內(nèi)查找 high1=mid1-1; else low1=mid1+1; /到后邊的塊內(nèi)查找 if (low1B)/以下是在所找到的塊內(nèi)查找 i=inlistlow1.low; j=inlistlow1.high; while(ij & strcmp(listi

10、.key,key) i+;/在塊內(nèi)找學(xué)號(hào)相符的學(xué)生,可能找到,也可能找不到 if(strcmp(listi.key,key)=0)/找到了,根據(jù)所給的學(xué)號(hào)去修改相應(yīng)的成績 if(kc=1) listi.stu.chin=cj; else if(kc=2) listi.stu.phy=cj; else if(kc=3) listi.stu.chem=cj; else if(kc=4) listi.stu.eng=cj;（3）輸出算法void writetxt(void) FILE *fp; int i; fp=fopen(“score.txt”,”w”); / 以寫方式打開SCORE.TXT文件

11、 for(i=0;iM;i+) / 將修改后的數(shù)據(jù)輸出到SCORE.TXT文件中 fprintf(fp,”%s “,listi.stu.num); fprintf(fp,”%s “,); fprintf(fp,”%d “,listi.stu.chin); fprintf(fp,”%d “,listi.stu.phy); fprintf(fp,”%d “,listi.stu.chem); fprintf(fp,”%d “,listi.stu.eng); fprintf(fp,”n”); fclose(fp); / 關(guān)閉SCORE.TXT文件 四、程序#include

12、#define M 18 /線性表長 #define B 3 / 將線性表分成B塊 #define S 6 / 每塊內(nèi)結(jié)點(diǎn)數(shù)為S typedef char datatype;/typedef char keytype;/定義關(guān)鍵字類型是字符型typedef struct / 定義學(xué)生的結(jié)點(diǎn)結(jié)構(gòu) char num8,name10; /學(xué)生的學(xué)號(hào)，姓名int age,chin,phy,chem,eng; /學(xué)生的年齡，中文、物理、化學(xué)和英語成績 STUDENT;typedef struct / 定義線性表的結(jié)點(diǎn)結(jié)構(gòu) keytype key8; STUDENT stu; TABLE;typedef

13、struct / 定義索引表的結(jié)點(diǎn)結(jié)構(gòu) keytype key8; int low,high; INDEX;TABLE listM; / 說明線性表變量 INDEX inlistB; / 索引表變量 /下面是主函數(shù),各算法清單同前 void main( ) int kc,cj; char key8;creat(); / 創(chuàng)建數(shù)據(jù)文件SCORE.TXTprintf(“請輸入欲修改成績的學(xué)生號(hào)!n”);gets(key);printf(“選擇欲修改成績的課程:語文(1)物理(2)化學(xué)(3)英語(4)：”);scanf(“%d”,&kc);printf(“輸入該課程的修改成績：”);scanf(“%

14、d”,&cj); readtxt(); / 調(diào)用輸入數(shù)據(jù)函數(shù) modify(key,kc,cj); / 調(diào)用分塊查找及數(shù)據(jù)修改函數(shù) writetxt(); / 調(diào)用輸出數(shù)據(jù)函數(shù) 五、測試數(shù)據(jù)為提高分塊查找的可操作性，算法中的輸入數(shù)據(jù)可由數(shù)據(jù)文件SCORE.TXT提供，SCORE.TXT中的數(shù)據(jù)如下（文件中數(shù)據(jù)亦可自擬）：班號(hào) 姓名 語文 物理 化學(xué) 英語 10003 丁一 86 54 67 8910002 錢二 70 85 82 9010001 張三 72 81 92 6910023 李四 62 86 90 7510017 陳五 46 80 60 7510014 王六 86 50 62 812

15、0110 馬七 72 64 68 8020120 楊八 64 68 76 9020114 梁九 82 56 87 8320117 趙十 80 64 87 7920111 趙一 58 84 66 8420112 梁二 68 60 68 8230213 楊三 70 50 60 6830207 馬四 80 60 76 8430202 王五 72 68 86 9030203 陳六 65 72 76 8930201 李七 68 80 86 8830221 張八 80 72 86 90數(shù)據(jù)在SCORE.TXT文件中的存放格式：數(shù)據(jù)之間以空格分隔，表頭僅做示意用，不存放在文件中。六、程序運(yùn)行結(jié)果請輸入欲修改成績的學(xué)生號(hào)： 30207選擇欲修改成績的課程:語文(1)物理(2)化學(xué)(3)英語(4)：1輸入該課程的修改成績：100程序運(yùn)行后SCORE.TXT中的數(shù)據(jù)如下:10003丁一86 54 67 89 10002錢二70 85 82 90 10001張三72 81 92 69 10023李四62 86 90 75 10017陳五46 80 60 75 10014王六86 50 62 81 20110馬七72 64 68 80 20120楊八