数据结构（Java语言） 课件 项目九 查找-分数查询

项目九查找---分数查询目录项目九5123

典型工作任务9.1查找项目需求分析典型工作任务9.2查找数据结构设计典型工作任务9.3查找软件代码设计典型工作任务9.4查找软件测试执行典型工作任务9.5查找软件文档编写46典型工作任务9.6查找项目验收交付知识目标掌握查找的常用概念和术语掌握基于线性表的查找掌握给定数据结构的查找操作掌握提高查找效率的方法技能目标能进行项目需求分析会进行查找的算法设计、分析及编程能用查找的算法解决实际数据结构问题能进行软件测试及项目功能调整能撰写格式规范的软件文档思政目标培养数据抽象能力，理论联系实际训练复杂程序设计能力，培养团结协作、自作学习的能力要求编写的程序结构清楚和正确易读，养成良好程序设计能力培养学生发现问题、思考问题和解决问题的能力总体要求

学生成绩管理一直是管理的主要业务之一，学生成绩查询是每个学生都需要使用到的功能，能够提高成绩管理效率，方便学生和教师办公，提高成绩管理的自动化、现代化和信息化，对于学校教育教学管理工作有着极其重要的作用。随着学校办学规模的逐步扩大，招生名额和指标不断增加，成绩查询业务也在不断增加，较好地解决成绩查询问题已经成为迫切需要，学生分数查询模块图如图9-1所示。图9-1分数查询模块图典型工作任务9.1查找项目需求分析

以某职院为例，会按照相应规则为每个入学的学生分配唯一的学号，每个学生在大学里都会获得所有所学课程的成绩。如表9-1所示，当用计算机处理大学生考试成绩时，全部考生的成绩可以存储在表中，表中每一行为一个记录，学生的学号为记录的关键字。假设给定值为14，则通过查找可得学生张三的各科成绩和总分，此时查找为成功。若给定值为20，则表中没有相应数据，查找不成功。

表9-1学生成绩表示例典型工作任务9.1查找项目需求分析学号姓名学生成绩.........14马慧10015张三6516李四9017王宇8018赵六9419孙七789.2.1基本概念

1.数据项

数据项可以是字母、数字或两者的组合。通过数据类型（逻辑的、数值的、字符的等）及数据长度来描述。数据项用来描述实体的某种属性。2.数据元素

数据元素是数据的基本单位，由数据项组成。在不同的条件下,数据元素又可称为元素、结点、顶点、记录等。3.关键字

数据元素（或记录）中某个数据项的值，用它可以识别一个数据元素（或记录）。若此关键字可以唯一地识别一个记录，则称此关键字为主关键字，若可以识别若干记录的关键字成为次关键字。4.查找

在一个含有众多的数据元素（或记录）的查找表中找出目标数据元素（或记录），查找又称检索，是对查找表进行操作，在数据集合中寻找满足要求的的数据元素成为查找。典型工作任务9.2查找数据结构设计9.2.1基本概念

5.查找表

用于查找的数据集合叫做查找表，由同一类型的数据元素组成。对查找表的操作一般有以下四种：

（1）查找操作：查找某个元素是否在查找表中；（2）读取操作：访问目标元素并输出；（3）插入操作：向查找表中插入元素；（4）删除操作：从查找表中删除元素6.平均查找长度

为确定数据元素在查找表中的位置，需要和给定的值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。

对于长度为n的查找表，查找成功时的平均查找长度为

Pi为查找查找表中第i个数据元素的概率，Ci为找到表中第i个数据元素时，已经进行的关键字的比较次数。典型工作任务9.2查找数据结构设计9.2.2静态查找表

静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。静态查找表在查找的过程中不改变表的状态—，即不增加不减少。适合用于不变动或者不常变动的表的查找，如高考成绩表、本单位职工信息表等。1.顺序查找1）概念顺序查找又叫线性查找，它的关键流程为：从表中第一个或最后一个记录开始，逐个对比该记录中的关键词与待查找关键词是否相等，如果某条记录中的关键词与待查找关键词相等，则表示查找成功，返回所查找记录；如果直到最后一条记录，其关键词与待查找关键词都不相等，则查找失败。顺序查找的特点是用所给的关键字与线性表中各元素的关键字逐个进行比较，直到成功或失败。典型工作任务9.2查找数据结构设计

2）结构定义

（1）顺序表的结构定义publicclassSequenceList<T>implementIterable<T>{privateT[]arr;//存储元素的数据privateintN;//记录当前顺序表中的元素个数publicSequenceList(intcapacity){//构造方法this.arr=(T[])newObject[capacity];This.N=0;}}

（2）顺序查找的结构定义publicintindexof(Tt){for(inti=0;i<N;i++){if(arr[i]==t)returni;}return-1;}典型工作任务9.2查找数据结构设计

3）算法

算法的基本思想是：在查找表的一端设置一个称为“监视哨”的附加单元，存放要查找的数据元素关键字。然后从表的另一端开始查找，如果在“监视哨”位置找到给定关键字，则失败，否则成功返回相应元素的位置。实践证明，在查找表的规模n≥1000时，进行一次查找所需的平均时间几乎减少一半。

查找表接口定义如下：publicinterfaceSearchTable{publicintgetSize();//查询查找表当前的规模publicbooleanisEmpty();//判断查找表是否为空search(Objectele);//返回查找表中与元素ele关键字相同的元素位置；否则，返回nullpublicNodepublicIteratorsearchAll(Objectele);//返回所有关键字与元素ele相同的元素位置publicvoidinsert(Objectele);//按关键字插入元素elenullpublicObjectremove(Objectele);//若查找表中存在与元素ele关键字相同元素//则删除一个并返回；否则，返回}典型工作任务9.2查找数据结构设计顺序查找代码如下：publicstaticintT(int[]arr,intq){//传入主方法定义好的数组和输入的参数inti;intnum=0;//记录次数，刚开始没有，初始化0System.out.println("进入顺序查找");for(i=0;i<arr.length;i++){//遍历数组num=num+1;if(arr[i]==q){//判断System.out.println("找到了，下标值为："+i);System.out.println("查找成功且比较的次数为："+num);returni;//返回下标}}if(i==arr.length){System.out.println("没找到");System.out.println("查找不成功且比较的次数为："+num);}return-1;//返回-1表示没找到}典型工作任务9.2查找数据结构设计4)分析假设查找表长度为n，查找每个数据元素的概率相等，均为1/n。并且将监视哨设置在高端，那么查找第i个数据元素时需要进行i次比较，即Ci=i，则平均查找长度为2.折半查找1）概念折半查找又称为二分查找，这种查找方法需要待查的查找表满足两个条件：首先，查找表必须使用顺序的存储结构；其次，查找表必须按关键字大小有序排列。2）结构定义publicstaticintC(int[]arr,inta){intbegin=0;//数据定义intend=arr.length-1;intmid=0;while(begin<=end){//循环条件比较，分别与中间值进行比较，返回大于、等于或者小于三种情况。if(a>arr[mid]){//查找的数比中间值大，改变begin}elseif(a<arr[mid]){//查找的数比中间值小，改变end}else{//相等即找到a==arr[mid]}典型工作任务9.2查找数据结构设计3)算法折半查找算法的基本思想是：首先，将查找表中间位置数据元素的关键字与给定关键字比较，如果相等则查找成功；否则利用中间元素将表一分为二，如果中间元素关键字大于给定关键字，则在前一子表中进行折半查找，否则在后一子表中进行折半查找。重复以上过程，直到找到满足条件的元素，则查找成功；或直到子表为空为止，此时查找不成功。publicstaticintC(int[]arr,inta){//传已定义好的数组和要找的数intbegin=0;intend=arr.length-1;intmid=0;intnum=0;//记录次数System.out.println("进入二分查找");while(begin<=end){//循环条件是begin要小于等于endnum++;mid=(begin+end)/2;if(a>arr[mid]){//查找的数比中间值大，改变beginbegin=mid+1;}elseif(a<arr[mid]){//查找的数比中间值小，改变endend=mid-1;}else{//相等即找到a==arr[mid]System.out.println("找到了,下标值为"+mid);System.out.println("查找成功且比较的次数为："+num);returnmid;//返回下标}}System.out.println("没找到");System.out.println("查找不成功且比较的次数为："+num);return-1;//返回-1，表示没找到}}典型工作任务9.2查找数据结构设计4)分析从折半查找过程看，以表的中间元素为比较对象，并以中间元素将表分割为两个子表，对定位到的子表继续这种操作。采用折半查找，当查找成功时，最少比较次数为1次，最多经过log2n次比较，直到查找子表为空或者只剩下一个结点，因此，要确定查找师表，需要log2n或log2n+1次比较，折半查找的平均查找长度为：折半查找的效率比顺序查找高，但折半查找只适合于有序表，且限于顺序存储结构，插入删除困难。折半查找的高查找效率是以牺牲排序为代价的，因此折半查找适用于不经常变动而查找频繁的有序表。典型工作任务9.2查找数据结构设计9.2.3动态查找表动态查找表指在查找过程同时插入插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素。1.概念二叉查找树(binarysearchtree,BST)或者是一棵空树；或者是具有以下性质的二叉树：（1）若它的左子树不空，则其左子树中所有结点的值不大于根结点的值；（2）若它的右子树不空，则其右子树中所有结点的值不小于根结点的值；（3）它的左、右子树都是二叉查找树。典型工作任务9.2查找数据结构设计2.结构定义二叉查找树节点的定义publicclassBSTree<TextendsComparable<T>>{privateBSTNode<T>mRoot;//根结点publicclassBSTNode<TextendsComparable<T>>{Tkey;//关键字(键值)BSTNode<T>left;//左孩子BSTNode<T>right;//右孩子BSTNode<T>parent;//父结点publicBSTNode(Tkey,BSTNode<T>parent,BSTNode<T>left,BSTNode<T>right){this.key=key;this.parent=parent;this.left=left;this.right=right;}}}典型工作任务9.2查找数据结构设计3.

算法基本思想是：若查找树不为空，将待查关键字与根结点元素关键字比较，若相等则返回根结点；否则判断待查关键字与根结点关键字的大小，如果待查关键字小，则递归的在查找树的左子树中查找，否则递归的在查找树的右子树中查找。//本例为查找最大结点：返回tree为根结点的二叉树的最大结点privateBSTNode<T>maximum(BSTNode<T>tree){if(tree==null)returnnull;while(tree.right!=null)tree=tree.right;returntree;}publicTmaximum(){BSTNode<T>p=maximum(mRoot);if(p!=null)returnp.key;returnnull;}典型工作任务9.2查找数据结构设计返回v在中序遍历序列中的后续结点privateBinTreeNodegetSuccessor(BinTreeNodev){if(v==null)returnnull;if(v.hasRChild())return(BinTreeNode)min(v.getRChild());while(v.isRChild())v=v.getParent();returnv.getParent();}确定结点v的直接前驱结点的算法思想与确定前驱结点的算法正好对称。返回v在中序遍历序列中的前驱结点privateBinTreeNodegetPredecessor(BinTreeNodev){if(v==null)returnnull;if(v.hasLChild())return(BinTreeNode)max(v.getLChild());while(v.isLChild())v=v.getParent();returnv.getParent();}典型工作任务9.2查找数据结构设计

以学生成绩查询为例，用Java语言实现简单的学生成绩查询系统，可以实现成绩录入、查询等功能，其中分别使用顺序查找方式、折半查找方式和二叉树查找方式实现学生成绩的查询示。

图9-2分数查询程序框图典型工作任务9.3查找软件代码设计第1部分程序，定义学生类，定义学生的姓名、学号、分数，并实现设置和获取学生基本信息功能。

典型工作任务9.3查找软件代码设计classStudent{privateStringstuNo;privateStringname;privatefloatscore;publicStringgetStuNo(){returnstuNo;}publicvoidsetStuNo(StringstuNo){this.stuNo=stuNo;}publicStringgetName(){returnname;}publicvoidsetName(Stringname){=name;

}publicfloatgetScore(){returnscore;}publicvoidsetScore(floatscore){this.score=score;}}

第2部分程序，定义学生节点类，分别包含数据信息，左结点和右结点。

典型工作任务9.3查找软件代码设计classNode{Studentdata;Nodeleft;Noderight;

Node(Studentdata){this.data=data;}}

第3部分主程序，实现查询学生成绩功能。

典型工作任务9.3查找软件代码设计

privatestaticintcount=20;privatestaticStudent[]students=newStudent[count];//学生数组privatestaticintsize=0;publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intchoice;Noderoot=null;do{System.out.println("请输入以下指令执行对应的操作：");System.out.println("1.添加学生信息");System.out.println("2.顺序查找学生信息");System.out.println("3.折半查找学生信息");System.out.println("4.二叉排序树查找学生信息");System.out.println("5.打印全部学生信息");System.out.println("0.退出程序");System.out.print("请选择操作：");choice=scanner.nextInt();scanner.nextLine();//读取换行符

典型工作任务9.3查找软件代码设计

switch(choice){case1:addStudent(scanner);//添加学生sortByStuNo();//按学号排序for(inti=0;i<size;i++){//构建二叉树root=insert(root,students[i]);}break;case2:searchStudentByOrder(scanner);break;case3:binarySearch(scanner);break;case4:System.out.print("请输入要查找的学号：");Stringid=scanner.nextLine();Studentstudent=searchByTree(root,id);if(student==null){System.out.println("未找到该学号的学生信息");}else{System.out.println("学号\t姓名\t成绩");System.out.println(student.getStuNo()+"\t"+student.getName()+"\t"+student.getScore());}break;

典型工作任务9.3查找软件代码设计case5:for(inti=0;i<size;i++){System.out.println("学号\t姓名\t成绩");System.out.println(students[i].getStuNo()+"\t"+students[i].getName()+"\t"+students[i].getScore());}break;case0:System.out.println("程序已退出,Bye");break;default:System.out.println("无效的操作，请重新选择");break;}}while(choice!=0);}

典型工作任务9.3查找软件代码设计//添加学生信息privatestaticvoidaddStudent(Scannerscanner){if(size>=count){System.out.println("最多只可以添加"+count+"个学生，无法添加");return;}Studentstudent=newStudent();System.out.print("请输入学号：");student.setStuNo(scanner.nextLine());System.out.print("请输入姓名：");student.setName(scanner.nextLine());System.out.print("请输入成绩：");student.setScore(scanner.nextFloat());scanner.nextLine();//读取换行符students[size]=student;size++;System.out.println("学生信息添加成功");}

典型工作任务9.3查找软件代码设计//顺序查找学生信息privatestaticvoidsearchStudentByOrder(Scannerscanner){System.out.print("请输入要查找的学号：");StringstuNo=scanner.nextLine();for(inti=0;i<size;i++){if(students[i].getStuNo().equals(stuNo)){System.out.println("学号\t姓名\t成绩");System.out.println(students[i].getStuNo()+"\t"+students[i].getName()+"\t"+students[i].getScore());return;}}System.out.println("未找到该学号的学生信息");}

典型工作任务9.3查找软件代码设计//顺序查找学生信息privatestaticvoidsearchStudentByOrder(Scannerscanner){System.out.print("请输入要查找的学号：");StringstuNo=scanner.nextLine();for(inti=0;i<size;i++){if(students[i].getStuNo().equals(stuNo)){System.out.println("学号\t姓名\t成绩");System.out.println(students[i].getStuNo()+"\t"+students[i].getName()+"\t"+students[i].getScore());return;}}System.out.println("未找到该学号的学生信息");}

典型工作任务9.3查找软件代码设计//折半查找学生信息privatestaticvoidbinarySearch(Scannerscanner){System.out.print("请输入要查找的学号：");Stringid=scanner.nextLine();intbegin=0;intend=size-1;while(begin<=end){intmidIndex=(begin+end)/2;if(students[midIndex].getStuNo().equals(id)){System.out.println("学号\t姓名\t成绩");System.out.println(students[midIndex].getStuNo()+"\t"+students[midIndex].getName()+"\t"+students[midIndex].getScore());return;}elseif(pareTo(students[midIndex].getStuNo())<0){end=midIndex-1;}else{begin=midIndex+1;}}System.out.println("未找到该学号的学生信息");}

典型工作任务9.3查找软件代码设计//按学号排序privatestaticvoidsortByStuNo(){for(inti=0;i<size-1;i++){for(intj=i+1;j<size;j++){if(students[i].getStuNo().compareTo(students[j].getStuNo())>0){Studenttemp=students[i];students[i]=students[j];students[j]=temp;}}}}//向二叉排序树中插入节点privatestaticNodeinsert(Noderoot,Studentstudent){if(root==null){returnnewNode(student);}

典型工作任务9.3查找软件代码设计if(student.getStuNo().compareTo(root.data.getStuNo())<0){root.left=insert(root.left,student);}else{root.right=insert(root.right,student);}returnroot;}//在二叉排序树中查找指定学号的学生信息privatestaticStudentsearchByTree(Noderoot,Stringid){if(root==null){returnnull;}if(id.equals(root.data.getStuNo())){returnroot.data;}elseif(pareTo(root.data.getStuNo())<0){returnsearchByTree(root.left,id);}else{returnsearchByTree(root.right,id);}}}

在Eclipse工具中执行成绩查询代码，选择指令“1”，添加表9-1中的学生信息，此操作完成本项目学生基本信息添加，主要包含学生的学号、姓名和成绩，建立学生基本信息数据库，便于后续的查询，如图9-3至图9-8所示。

图9-3添加学生信息1图9-4添加学生信息2

典型工作任务9.4查找软件测试执行图9-5添加学生信息3图9-6添加学生信息4图9-7添加学生信息5图9-8添加学生信息6

典型工作任务9.4查找软件测试执行

选择“2”按学号进行顺序查找，此操作是完成本项目顺序查找学生信息，通过对数据库信息的查询，用算法实现顺序查找学生信息，如图9-9所示。选择“3”进行折半查找，此操作通过对数据库信息的查询，完成本项目折半查找学生信息，如图9-10所示。

图9-9顺序查找学生信息

图9-10折半查找学生信息

典型工作任务9.4查找软件测试执行

图9-11二叉树查找学生信息

图9-12打印学生信息

图9-13查询失败

图9-14查询结束

典型工作任务9.4查找软件测试执行

9.5.1

添加学生信息算法模块测试

本模块主要测试学生基本信息添加情况，包含信息是否可以添加成功，以及添加学号、姓名和成绩等信息。

典型工作任务9.5查找软件文档编写编号摘要描述预期结果正确代码addStudent添加信息可以添加size>=countaddStudent添加信息不可添加size<countnewStudent()分配空间分配成功Studentstudent=newStudent()setStuNo()输入学号输入成功student.setStuNo(scanner.nextLine())setName()输入姓名输入成功student.setName(scanner.nextLine())setScore()输入成绩输入成功student.setScore(scanner.nextFloat())

9.5.2

顺序查找学生信息算法模块测试

典型工作任务9.5查找软件文档编写编号摘要描述预期结果正确代码searchStudentByOrder()顺序表查找找到for(inti=0;i<size;i++){if(students[i].getStuNo().equals(stuNo)){System.out.println("学号\t姓名\t成绩");System.out.println(students[i].getStuNo()+"\t"+students[i].getName()+"\t"+students[i].getScore());

return;}}searchStudentByOrder()顺序表查找未找到System.out.println(“未找到该学号的学生信息”)；

9.5.3折半查找学生信息算法模块测试