设计_查找实验1_2_07_.doc

线 性 表 的 查 找在表的组织方式中，线性表是最简单的一种。对线性表的查找一般有三种方法：顺序查找、二分查找、分块查找。一、顺序查找基本知识：线性表的数据类型定义及对线性表的顺序扫描操作。算法思想：从线性表一端开始，顺序扫描线性表，依次将扫描到的结点关健字与给定值key比较，若相等，则查找成功；若扫描结束后，仍末找到关健字等于key的结点，则查找失败。二、二分查找基本知识：线性表的数据类型定义、线性表中结点按其关健字有序排列。算法思想： 用待查值key与表的中间结点关健字比较（中间结点将线性表分为两个子表），若比较结果相等，则查找成功；若待查值key大于中间结点关健字，选右子表继续比较；若待查值key小于中间结点关健字，选左子表继续比较； 重复，直到查找成功或结束；三、分块查找基本知识：分块查找是把线性表分成若干块，各块中的结点顺序可任意亦可有序，但块与块之间必须按关健字大小有序，即前一块中的最大关健字要小于后一块中的最小关健字。因此，与线性表的顺序查找和二分查找不同，除定义线性表的数据类型外，还须定义一个递增有序的索引表，以描述线性表“分块有序”的状态算法思想：分块查找实际上是对索引表和线性表的两次查找。顺序查找或二分查找索引表：以确定待查结点在哪一块。由于索引表递增有序（即块与块之间按关健字大小有序），因此，索引表的查找常采用二分查找算法以提高算法效率。在所确定的块内顺序查找线性表：确定待查结点在线性表的确切位置。由于块内结点即可无序亦可有序，因此，块内查找一般采用顺序查找算法。查找实验（两次课完成）一、实验题目: 请编写一个完整的程序，用菜单驱动方法实现：利用分块查找算法在线性表（学生情况表）list中查找给定值key(学号)的结点，并将该结点的部分数据进行修改。注：在此实验中你还可以添加一个或几个你最熟悉的查找算法来实现此功能。二、解题思路：例：输入学号：30207； 选择课程名：语文； 输入修改成绩：100；在学生情况表中查找学号为“30207”的学生记录；将该学生记录的语文成绩修改为100；建立文件算法：建立待查找的数据文件SCORE.TXT的函数creat( )输入算法： 在待查找的数据文件SCORE.TXT中找输出算法： 将修改后的线性表（学生情况表）数据输出到文件SCORE.TXT中，算法要点： 分块查找的查找过程分两步进行: 先在线性表中确定待查找的结点属于哪一块。由于块与块之间按关健字大小有序，因此，块间查找可采用二分查找算法。 在所确定的块内查找待查结点，由于块内结点即可无序亦可有序，因此，块内查找一般可采用顺序查找算法。找到指定结点后，按要求修改结点中的有关数据。三、数据类型及算法1数据类型定义（1）学生的结点结构typedef struct char num8,name10; /学生的学号，姓名int age,chin,phy,chem,eng; /学生的年龄，中文、物理、化学和英语成绩 STUDENT;（2）线性表的结点结构typedef struct keytype key8; /关键字STUDENT stu; TABLE;（3）索引表的结点结构typedef struct keytype key8; int low,high; INDEX;2操作算法（1）输入算法从SCORE.TXT文件中读出数据、建立线性表及索引表可通过调用函数readtxt(void)完成，此函数算法如下：void readtxt(void) / 构造线性表list及索引表inlist FILE *fp; int i,d; char max8; fp=fopen(“score.txt”,”r”); /以只读方式打开SCORE.TXT文件 for(i=0;iM;i+) / 将SCORE.TXT中的M个数据输到线性表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.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个学生的学号设为关键字 for(i=0;iB;i+) / 构造索引表inlist,B是线性表的块数 inlisti.low=i+(i*(S-1); / 每块内结点数为S inlisti.high=i+(i+1)*(S-1); strcpy(max,list0.stu.num);/将第0个学生的学号复制到数组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) /设为线性表中第d个块的学号的最大值strcpy(max,listi+1.stu.num);/将线性表中的下一块的第一个学生的学号i+; /复制到max中,去求该块中的最大学号 fclose(fp); / 关闭SCORE.TXT文件 （2）动态分块查找算法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) /到前边的块内查找 high1=mid1-1; else low1=mid1+1; /到后边的块内查找 if (low1B)/以下是在所找到的块内查找 i=inlistlow1.low; j=inlistlow1.high; while(ij & strcmp(listi.key,key) i+;/在块内找学号相符的学生,可能找到,也可能找不到 if(strcmp(listi.key,key)=0)/找到了,根据所给的学号去修改相应的成绩 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文件 for(i=0;iM;i+) / 将修改后的数据输出到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); / 关闭SCORE.TXT文件 四、程序#include #define M 18 /线性表长 #define B 3 / 将线性表分成B块 #define S 6 / 每块内结点数为S typedef char datatype;/typedef char keytype;/定义关键字类型是字符型typedef struct / 定义学生的结点结构 char num8,name10; /学生的学号，姓名int age,chin,phy,chem,eng; /学生的年龄，中文、物理、化学和英语成绩 STUDENT;typedef struct / 定义线性表的结点结构 keytype key8; STUDENT stu; TABLE;typedef struct / 定义索引表的结点结构 keytype key8; int low,high; INDEX;TABLE listM; / 说明线性表变量 INDEX inlistB; / 索引表变量 /下面是主函数,各算法清单同前 void main( ) int kc,cj; char key8;creat(); / 创建数据文件SCORE.TXTprintf(“请输入欲修改成绩的学生号!n”);gets(key);printf(“选择欲修改成绩的课程:语文(1)物理(2)化学(3)英语(4)：”);scanf(“%d”,&kc);printf(“输入该课程的修改成绩：”);scanf(“%d”,&cj); readtxt(); / 调用输入数据函数 modify(key,kc,cj); / 调用分块查找及数据修改函数 writetxt(); / 调用输出数据函数 五、测试数据为提高分块查找的可操作性，算法中的输入数据可由数据文件SCORE.TXT提供，SCORE.TXT中的数据如下（文件中数据亦可自拟）：班号 姓名 语文 物理 化学 英语 10003 丁一 86 54 67 8910002 钱二 70 85 82 9010001 张三 72 81 92 6910023 李四 62 86 90 7510017 陈五 46 80 60 7510014 王六 86 50 62 8120110 马七 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数据在SCORE.TXT文件中的存放格式：数据之间以空格分隔，表头仅做示意用，不存放在文件中。六、程序运行结果请输入欲修改成绩的学生号： 30207选择欲修改成绩的课程:语文(1)物理(2)化学(3)英语(4)：1输入该课程的修改成绩：100程序运行后SCORE.TXT中的数据如下: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杨八