数据结构 实验报告

?数 据 结 构?

《数据结构》实验报告五

实验内容： 简单查找类算法的应用和比较——顺序查找和折半查找 学号： 姓名： [题目] 学生成绩表已按成绩非递增有序排列，请分别用顺序查找和折半查找算法，找出指定成绩的学生信息，并分别指出所用的比较次数。给出查找成功和不成功两种情况。 一、问题分析及设计思想： 先要设计一个学生的顺序表，再进行查找，顺序查找（从表的一端开始，一次将记录的关键字和给定值进行比较，若某个记录的关键字和给定值相等，则查找成功；反之，若扫描整个表后，仍未找到关键字和给定值相等的记录，则查找失败）；折半查找（从表的中间记录开始，如果给定值和中间纪录的关键字相等，则查找成功；如果给定值大于或小于中间记录的关键字，则在表中大于或小于中间记录的那一半中查找，这样重复操作，直到查找成功，或者在某一步中查找区间为空，则代表查找失败）。 二、存储结构定义： #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define MAX_LENGTH 100 三、函数声明： struct ElemType // 数据元素类型 typedef struct void Creat_Seq(SSTable &ST,ElemType r[],int n) // 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST void Ascend(SSTable &ST) // 重建静态查找表为按关键字非降序排序 Status Destroy(SSTable &ST) // 初始条件：静态查找表ST存在。操作结果：销毁表ST int Search_Seq(SSTable ST,KeyType key) // 在顺序表ST中顺序查找其关键字等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0。 四、完整程序示例： 顺序查找： #include #include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; #define MAX_LENGTH 100 typedef long KeyType; // 设关键字域为长整型 #define key number // 定义关键字为学号 struct ElemType // 数据元素类型 { long number; // 学号，与关键字类型同 char name[9]; // 姓名 }; int total; // 总分 typedef struct { ElemType *elem; int length; }SSTable; void Creat_Seq(SSTable &ST,ElemType r[],int n) { // 操作结果：由含n个数据元素的数组r构造静态顺序查找表ST int i; ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType)); // 动态生成n+1 个数据元素空间(0号单元不用) if(!ST.elem) } void Ascend(SSTable &ST) { // 重建静态查找表为按关键字非降序排序 exit(ERROR); for(i=1;i<=n;i++) ST.elem[i]=r[i-1]; // 将数组r的值依次赋给ST ST.length=n; } int i,j,k; for(i=1;i

本文来源：https://www.bwwdw.com/article/sj0d.html