數(shù)據(jù)結構（Java語言） 課件 項目九 查找-分數(shù)查詢

項目九查找---分數(shù)查詢目錄項目九5123

典型工作任務9.1查找項目需求分析典型工作任務9.2查找數(shù)據(jù)結構設計典型工作任務9.3查找軟件代碼設計典型工作任務9.4查找軟件測試執(zhí)行典型工作任務9.5查找軟件文檔編寫46典型工作任務9.6查找項目驗收交付知識目標掌握查找的常用概念和術語掌握基于線性表的查找掌握給定數(shù)據(jù)結構的查找操作掌握提高查找效率的方法技能目標能進行項目需求分析會進行查找的算法設計、分析及編程能用查找的算法解決實際數(shù)據(jù)結構問題能進行軟件測試及項目功能調(diào)整能撰寫格式規(guī)范的軟件文檔思政目標培養(yǎng)數(shù)據(jù)抽象能力，理論聯(lián)系實際訓練復雜程序設計能力，培養(yǎng)團結協(xié)作、自作學習的能力要求編寫的程序結構清楚和正確易讀，養(yǎng)成良好程序設計能力培養(yǎng)學生發(fā)現(xiàn)問題、思考問題和解決問題的能力總體要求

學生成績管理一直是管理的主要業(yè)務之一，學生成績查詢是每個學生都需要使用到的功能，能夠提高成績管理效率，方便學生和教師辦公，提高成績管理的自動化、現(xiàn)代化和信息化，對于學校教育教學管理工作有著極其重要的作用。隨著學校辦學規(guī)模的逐步擴大，招生名額和指標不斷增加，成績查詢業(yè)務也在不斷增加，較好地解決成績查詢問題已經(jīng)成為迫切需要，學生分數(shù)查詢模塊圖如圖9-1所示。圖9-1分數(shù)查詢模塊圖典型工作任務9.1查找項目需求分析

以某職院為例，會按照相應規(guī)則為每個入學的學生分配唯一的學號，每個學生在大學里都會獲得所有所學課程的成績。如表9-1所示，當用計算機處理大學生考試成績時，全部考生的成績可以存儲在表中，表中每一行為一個記錄，學生的學號為記錄的關鍵字。假設給定值為14，則通過查找可得學生張三的各科成績和總分，此時查找為成功。若給定值為20，則表中沒有相應數(shù)據(jù)，查找不成功。

表9-1學生成績表示例典型工作任務9.1查找項目需求分析學號姓名學生成績.........14馬慧10015張三6516李四9017王宇8018趙六9419孫七789.2.1基本概念

1.數(shù)據(jù)項

數(shù)據(jù)項可以是字母、數(shù)字或兩者的組合。通過數(shù)據(jù)類型（邏輯的、數(shù)值的、字符的等）及數(shù)據(jù)長度來描述。數(shù)據(jù)項用來描述實體的某種屬性。2.數(shù)據(jù)元素

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，由數(shù)據(jù)項組成。在不同的條件下,數(shù)據(jù)元素又可稱為元素、結點、頂點、記錄等。3.關鍵字

數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以識別一個數(shù)據(jù)元素（或記錄）。若此關鍵字可以唯一地識別一個記錄，則稱此關鍵字為主關鍵字，若可以識別若干記錄的關鍵字成為次關鍵字。4.查找

在一個含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出目標數(shù)據(jù)元素（或記錄），查找又稱檢索，是對查找表進行操作，在數(shù)據(jù)集合中尋找滿足要求的的數(shù)據(jù)元素成為查找。典型工作任務9.2查找數(shù)據(jù)結構設計9.2.1基本概念

5.查找表

用于查找的數(shù)據(jù)集合叫做查找表，由同一類型的數(shù)據(jù)元素組成。對查找表的操作一般有以下四種：

（1）查找操作：查找某個元素是否在查找表中；（2）讀取操作：訪問目標元素并輸出；（3）插入操作：向查找表中插入元素；（4）刪除操作：從查找表中刪除元素6.平均查找長度

為確定數(shù)據(jù)元素在查找表中的位置，需要和給定的值進行比較的關鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。

對于長度為n的查找表，查找成功時的平均查找長度為

Pi為查找查找表中第i個數(shù)據(jù)元素的概率，Ci為找到表中第i個數(shù)據(jù)元素時，已經(jīng)進行的關鍵字的比較次數(shù)。典型工作任務9.2查找數(shù)據(jù)結構設計9.2.2靜態(tài)查找表

靜態(tài)查找表是數(shù)據(jù)元素的線性表，可以是基于數(shù)組的順序存儲或以線性鏈表存儲。靜態(tài)查找表在查找的過程中不改變表的狀態(tài)—，即不增加不減少。適合用于不變動或者不常變動的表的查找，如高考成績表、本單位職工信息表等。1.順序查找1）概念順序查找又叫線性查找，它的關鍵流程為：從表中第一個或最后一個記錄開始，逐個對比該記錄中的關鍵詞與待查找關鍵詞是否相等，如果某條記錄中的關鍵詞與待查找關鍵詞相等，則表示查找成功，返回所查找記錄；如果直到最后一條記錄，其關鍵詞與待查找關鍵詞都不相等，則查找失敗。順序查找的特點是用所給的關鍵字與線性表中各元素的關鍵字逐個進行比較，直到成功或失敗。典型工作任務9.2查找數(shù)據(jù)結構設計

2）結構定義

（1）順序表的結構定義publicclassSequenceList<T>implementIterable<T>{privateT[]arr;//存儲元素的數(shù)據(jù)privateintN;//記錄當前順序表中的元素個數(shù)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查找數(shù)據(jù)結構設計

3）算法

算法的基本思想是：在查找表的一端設置一個稱為“監(jiān)視哨”的附加單元，存放要查找的數(shù)據(jù)元素關鍵字。然后從表的另一端開始查找，如果在“監(jiān)視哨”位置找到給定關鍵字，則失敗，否則成功返回相應元素的位置。實踐證明，在查找表的規(guī)模n≥1000時，進行一次查找所需的平均時間幾乎減少一半。

查找表接口定義如下：publicinterfaceSearchTable{publicintgetSize();//查詢查找表當前的規(guī)模publicbooleanisEmpty();//判斷查找表是否為空search(Objectele);//返回查找表中與元素ele關鍵字相同的元素位置；否則，返回nullpublicNodepublicIteratorsearchAll(Objectele);//返回所有關鍵字與元素ele相同的元素位置publicvoidinsert(Objectele);//按關鍵字插入元素elenullpublicObjectremove(Objectele);//若查找表中存在與元素ele關鍵字相同元素//則刪除一個并返回；否則，返回}典型工作任務9.2查找數(shù)據(jù)結構設計順序查找代碼如下：publicstaticintT(int[]arr,intq){//傳入主方法定義好的數(shù)組和輸入的參數(shù)inti;intnum=0;//記錄次數(shù)，剛開始沒有，初始化0System.out.println("進入順序查找");for(i=0;i<arr.length;i++){//遍歷數(shù)組num=num+1;if(arr[i]==q){//判斷System.out.println("找到了，下標值為："+i);System.out.println("查找成功且比較的次數(shù)為："+num);returni;//返回下標}}if(i==arr.length){System.out.println("沒找到");System.out.println("查找不成功且比較的次數(shù)為："+num);}return-1;//返回-1表示沒找到}典型工作任務9.2查找數(shù)據(jù)結構設計4)分析假設查找表長度為n，查找每個數(shù)據(jù)元素的概率相等，均為1/n。并且將監(jiān)視哨設置在高端，那么查找第i個數(shù)據(jù)元素時需要進行i次比較，即Ci=i，則平均查找長度為2.折半查找1）概念折半查找又稱為二分查找，這種查找方法需要待查的查找表滿足兩個條件：首先，查找表必須使用順序的存儲結構；其次，查找表必須按關鍵字大小有序排列。2）結構定義publicstaticintC(int[]arr,inta){intbegin=0;//數(shù)據(jù)定義intend=arr.length-1;intmid=0;while(begin<=end){//循環(huán)條件比較，分別與中間值進行比較，返回大于、等于或者小于三種情況。if(a>arr[mid]){//查找的數(shù)比中間值大，改變begin}elseif(a<arr[mid]){//查找的數(shù)比中間值小，改變end}else{//相等即找到a==arr[mid]}典型工作任務9.2查找數(shù)據(jù)結構設計3)算法折半查找算法的基本思想是：首先，將查找表中間位置數(shù)據(jù)元素的關鍵字與給定關鍵字比較，如果相等則查找成功；否則利用中間元素將表一分為二，如果中間元素關鍵字大于給定關鍵字，則在前一子表中進行折半查找，否則在后一子表中進行折半查找。重復以上過程，直到找到滿足條件的元素，則查找成功；或直到子表為空為止，此時查找不成功。publicstaticintC(int[]arr,inta){//傳已定義好的數(shù)組和要找的數(shù)intbegin=0;intend=arr.length-1;intmid=0;intnum=0;//記錄次數(shù)System.out.println("進入二分查找");while(begin<=end){//循環(huán)條件是begin要小于等于endnum++;mid=(begin+end)/2;if(a>arr[mid]){//查找的數(shù)比中間值大，改變beginbegin=mid+1;}elseif(a<arr[mid]){//查找的數(shù)比中間值小，改變endend=mid-1;}else{//相等即找到a==arr[mid]System.out.println("找到了,下標值為"+mid);System.out.println("查找成功且比較的次數(shù)為："+num);returnmid;//返回下標}}System.out.println("沒找到");System.out.println("查找不成功且比較的次數(shù)為："+num);return-1;//返回-1，表示沒找到}}典型工作任務9.2查找數(shù)據(jù)結構設計4)分析從折半查找過程看，以表的中間元素為比較對象，并以中間元素將表分割為兩個子表，對定位到的子表繼續(xù)這種操作。采用折半查找，當查找成功時，最少比較次數(shù)為1次，最多經(jīng)過log2n次比較，直到查找子表為空或者只剩下一個結點，因此，要確定查找?guī)煴?，需要log2n或log2n+1次比較，折半查找的平均查找長度為：折半查找的效率比順序查找高，但折半查找只適合于有序表，且限于順序存儲結構，插入刪除困難。折半查找的高查找效率是以犧牲排序為代價的，因此折半查找適用于不經(jīng)常變動而查找頻繁的有序表。典型工作任務9.2查找數(shù)據(jù)結構設計9.2.3動態(tài)查找表動態(tài)查找表指在查找過程同時插入插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已經(jīng)存在的某個數(shù)據(jù)元素。1.概念二叉查找樹(binarysearchtree,BST)或者是一棵空樹；或者是具有以下性質的二叉樹：（1）若它的左子樹不空，則其左子樹中所有結點的值不大于根結點的值；（2）若它的右子樹不空，則其右子樹中所有結點的值不小于根結點的值；（3）它的左、右子樹都是二叉查找樹。典型工作任務9.2查找數(shù)據(jù)結構設計2.結構定義二叉查找樹節(jié)點的定義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查找數(shù)據(jù)結構設計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查找數(shù)據(jù)結構設計返回v在中序遍歷序列中的后續(xù)結點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查找數(shù)據(jù)結構設計

以學生成績查詢?yōu)槔肑ava語言實現(xiàn)簡單的學生成績查詢系統(tǒng)，可以實現(xiàn)成績錄入、查詢等功能，其中分別使用順序查找方式、折半查找方式和二叉樹查找方式實現(xiàn)學生成績的查詢示。

圖9-2分數(shù)查詢程序框圖典型工作任務9.3查找軟件代碼設計第1部分程序，定義學生類，定義學生的姓名、學號、分數(shù)，并實現(xiàn)設置和獲取學生基本信息功能。

典型工作任務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部分程序，定義學生節(jié)點類，分別包含數(shù)據(jù)信息，左結點和右結點。

典型工作任務9.3查找軟件代碼設計classNode{Studentdata;Nodeleft;Noderight;

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

第3部分主程序，實現(xiàn)查詢學生成績功能。

典型工作任務9.3查找軟件代碼設計

privatestaticintcount=20;privatestaticStudent[]students=newStudent[count];//學生數(shù)組privatestaticintsize=0;publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intchoice;Noderoot=null;do{System.out.println("請輸入以下指令執(zhí)行對應的操作：");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;}}}}//向二叉排序樹中插入節(jié)點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工具中執(zhí)行成績查詢代碼，選擇指令“1”，添加表9-1中的學生信息，此操作完成本項目學生基本信息添加，主要包含學生的學號、姓名和成績，建立學生基本信息數(shù)據(jù)庫，便于后續(xù)的查詢，如圖9-3至圖9-8所示。

圖9-3添加學生信息1圖9-4添加學生信息2

典型工作任務9.4查找軟件測試執(zhí)行圖9-5添加學生信息3圖9-6添加學生信息4圖9-7添加學生信息5圖9-8添加學生信息6

典型工作任務9.4查找軟件測試執(zhí)行

選擇“2”按學號進行順序查找，此操作是完成本項目順序查找學生信息，通過對數(shù)據(jù)庫信息的查詢，用算法實現(xiàn)順序查找學生信息，如圖9-9所示。選擇“3”進行折半查找，此操作通過對數(shù)據(jù)庫信息的查詢，完成本項目折半查找學生信息，如圖9-10所示。

圖9-9順序查找學生信息

圖9-10折半查找學生信息

典型工作任務9.4查找軟件測試執(zhí)行

圖9-11二叉樹查找學生信息

圖9-12打印學生信息

圖9-13查詢失敗

圖9-14查詢結束

典型工作任務9.4查找軟件測試執(zhí)行

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折半查找學生信息算法模塊測試