設(shè)計_查找實驗1_2_07_

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

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

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

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

5、chem,eng; /學生的年齡，中文、物理、化學和英語成績 STUDENT;（2）線性表的結(jié)點結(jié)構(gòu)typedef struct keytype key8; /關(guān)鍵字STUDENT stu; TABLE;（3）索引表的結(jié)點結(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個數(shù)據(jù)輸?shù)骄€性表list中 fscanf(fp,”%s”,listi.stu.num);/從文件SCORE.TXT中輸入第i個學生的學號 fscanf(fp,”%s”,); /從SCORE.TXT中輸入第i個學生的姓名 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生的化學成績 fscanf(fp,”%d”,&listi.stu.eng); /從SCORE.TXT中輸入第i生的英語成績 strcpy(listi.key,listi.stu.num); /將第i個學生的學號設(shè)為關(guān)鍵字 for(i=0;iB;i+) / 構(gòu)造索引表inlist,B是線性表的塊數(shù) inlisti.low=i+(i*(S-1); / 每塊內(nèi)結(jié)點數(shù)為S inlisti.high=i+(i+1)*(S-1); strcpy(max,list0.stu.num

8、);/將第0個學生的學號復制到數(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個元素的inlistd.key if(iM-1) /設(shè)為線性表中第d個塊的學號的最大值strcpy(max,listi+1.stu.num);/將線性表中的下一塊的第一個學生的學號i+; /復制到max中,去

9、求該塊中的最大學號 fclose(fp); / 關(guān)閉SCORE.TXT文件 （2）動態(tài)分塊查找算法void modify (char *key,int kc,int cj)/kc是課程號cj是成績key是要找的學號 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)找學號相符的學生,可能找到,也可能找不到 if(strcmp(listi.key,key)=0)/找到了,根據(jù)所給的學號去修改相應的成績 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é)點數(shù)為S typedef char datatype;/typedef char keytype;/定義關(guān)鍵字類型是字符型typedef struct / 定義學生的結(jié)點結(jié)構(gòu) char num8,name10; /學生的學號，姓名int age,chin,phy,chem,eng; /學生的年齡，中文、物理、化學和英語成績 STUDENT;typedef struct / 定義線性表的結(jié)點結(jié)構(gòu) keytype key8; STUDENT stu; TABLE;typedef

13、struct / 定義索引表的結(jié)點結(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(“請輸入欲修改成績的學生號!n”);gets(key);printf(“選擇欲修改成績的課程:語文(1)物理(2)化學(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ù)亦可自擬）：班號 姓名 語文 物理 化學 英語 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ù)之間以空格分隔，表頭僅做示意用，不存放在文件中。六、程序運行結(jié)果請輸入欲修改成績的學生號： 30207選擇欲修改成績的課程:語文(1)物理(2)化學(3)英語(4)：1輸入該課程的修改成績：100程序運行后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楊八