數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐系列

題目1：學(xué)生成績(jī)檔案管理系統(tǒng)（實(shí)驗(yàn)準(zhǔn)備）

題目2：隱式圖的搜索問題（A*算法解決八數(shù)碼）

題目3：文本文件單詞的檢索與計(jì)數(shù)（實(shí)驗(yàn)準(zhǔn)備）

文章目錄

• 數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐系列
• • 題目1：學(xué)生成績(jī)檔案管理系統(tǒng)（實(shí)驗(yàn)準(zhǔn)備）
  • 題目2：隱式圖的搜索問題（A*算法解決八數(shù)碼）
  • 題目3：文本文件單詞的檢索與計(jì)數(shù)（實(shí)驗(yàn)準(zhǔn)備）
• 聲明
• • 實(shí)驗(yàn)要求
• 編程語(yǔ)言以及開發(fā)環(huán)境的選擇
• • 所需知識(shí)
• 所需知識(shí)導(dǎo)出
• • DAO運(yùn)用
  • 簡(jiǎn)單排序算法
  • • 雙向冒泡排序
    • 快速排序
    • 希爾排序
    • 堆排序

聲明

實(shí)驗(yàn)要求

• 學(xué)生信息錄入，信息包括學(xué)號(hào)、姓名、專業(yè)、四門課成績(jī)、總分、名次；
• 系統(tǒng)可對(duì)學(xué)生信息瀏覽、增加、刪除和修改；
• 按學(xué)生成績(jī)確定名次及信息輸出，雙向冒泡排序、希爾排序、快速排序、堆排序
• 要求可對(duì)學(xué)生信息查詢，根據(jù)學(xué)號(hào)或姓名進(jìn)行查找；
• 信息修改僅可修改四門課成績(jī)；
• 文件存取學(xué)生信息。

編程語(yǔ)言以及開發(fā)環(huán)境的選擇

編程語(yǔ)言：java
開發(fā)環(huán)境：IDE使用的是idea，jdk版本為1.8

所需知識(shí)

一些簡(jiǎn)單排序算法，以及DAO

所需知識(shí)導(dǎo)出

DAO運(yùn)用

DAO (Database Access Object) 數(shù)據(jù)訪問對(duì)象，將數(shù)據(jù)對(duì)象常用的訪問方法（增刪改查）封裝在指定的對(duì)象中，該對(duì)象就稱為DAO對(duì)象，DAO對(duì)象是數(shù)據(jù)層構(gòu)建的基礎(chǔ)，由業(yè)務(wù)層對(duì)象進(jìn)行調(diào)用，DAO中定義的數(shù)據(jù)訪問方法和業(yè)務(wù)無(wú)關(guān)。
DAO設(shè)計(jì)模式主要分為三層：

顯示層：主要使用JSP/Servlet進(jìn)行頁(yè)面效果的顯示

業(yè)務(wù)層：（Business Object，數(shù)據(jù)對(duì)象）會(huì)將多個(gè)原子性的DAO操作進(jìn)行組合，組合成一個(gè)完整的業(yè)務(wù)邏輯。

數(shù)據(jù)層：（DAO，Data Access Object，數(shù)據(jù)庫(kù)訪問對(duì)象）提供多個(gè)原子性的DAO操作，例如：增、刪、改、查，都是原子性操作。

其實(shí)也就是利用一個(gè)Dao對(duì)象，然后這個(gè)對(duì)象里面實(shí)現(xiàn)了相應(yīng)的增刪改查，不讓用戶去直接接觸到數(shù)據(jù)庫(kù)。感覺和windows中線性虛擬地址的運(yùn)用有著相同的味道

簡(jiǎn)單排序算法

雙向冒泡排序

傳統(tǒng)冒泡排序運(yùn)作如下：（從后往前）

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較

雙向冒泡排序算法的運(yùn)作如下：

傳統(tǒng)冒泡氣泡排序的雙向進(jìn)行，先讓氣泡排序由左向右進(jìn)行，再來(lái)讓氣泡排序由右往左進(jìn)行，如此完成一次排序的動(dòng)作

使用left與right兩個(gè)旗標(biāo)來(lái)記錄左右兩端已排序的元素位置。

public List<Student> doubleBubbleSort(List<Student> studentList){List<Student> list=studentList;Student student=null;int left=0,right=studentList.size()-1;while(left<right){for(int i=left+1;i<=right;i++){if(list.get(left).getSum()<list.get(i).getSum()){student=list.get(i);list.set(i,list.get(left));list.set(left,student);}}left++;for(int i=right-1;i>=left;i--){if(list.get(right).getSum()>list.get(i).getSum()){student=list.get(i);list.set(i,list.get(right));list.set(right,student);}}right--;}return list;}

快速排序

快速排序使用分治法（Divide and conquer）策略來(lái)把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。
快速排序算法的運(yùn)作如下：

從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”（pivot），

重新排序數(shù)列，所有比基準(zhǔn)值小的元素?cái)[放在基準(zhǔn)前面，所有比基準(zhǔn)值大的元素?cái)[在基準(zhǔn)后面（相同的數(shù)可以到任何一邊）。在這個(gè)分區(qū)結(jié)束之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱為分區(qū)（partition）操作

遞歸地（recursively）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

遞歸到最底部時(shí)，數(shù)列的大小是零或一，也就是已經(jīng)排序好了。這個(gè)算法一定會(huì)結(jié)束，因?yàn)樵诿看蔚牡?#xff08;iteration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。

public List<Student> quickSort(List<Student> studentList){List<Student> list=studentList;quickSort1(list,0,list.size()-1);return list;}public void quickSort1(List<Student> studentList,int left,int right){if(left<right){int i=left,j=right;Student student=studentList.get(left);double x=student.getSum();while(i<j){while((i<j)&&(studentList.get(j).getSum()<x)){j--;}if(i<j){studentList.set(i,studentList.get(j));i++;}while((i<j)&&(studentList.get(i).getSum()>x)){i++;}if(i<j){studentList.set(j,studentList.get(i));j--;}}studentList.set(i,student);quickSort1(studentList,left,i-1);quickSort1(studentList,i+1,right);}}

希爾排序

希爾排序是非穩(wěn)定排序算法，把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止。

public List<Student> shellSort(List<Student> studentList){List<Student> list=studentList;Student student=null;int j;for (int gap = list.size() / 2; gap > 0; gap /= 2) {for (int i = gap; i < list.size(); i++) {student=list.get(i);double tmp=student.getSum();for (j = i; j >= gap && tmp>list.get(j-gap).getSum(); j -= gap) {list.set(j,list.get(j-gap));}list.set(j,student);}}return list;}

堆排序

堆排序（英語(yǔ)：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

public List<Student> heapSort(List<Student> studentList){List<Student> list=studentList;int len = list.size();buildMaxHeap(list, len);for (int i = len - 1; i > 0; i--) {swap(list, 0, i);len--;heapify(list, 0, len);}return list;}private void buildMaxHeap(List<Student> studentList, int len) {for (int i = (int) Math.floor(len / 2); i >= 0; i--) {heapify(studentList, i, len);}}private void heapify(List<Student> studentList, int i, int len) {int left = 2 * i + 1;int right = 2 * i + 2;int largest = i;if (left < len && studentList.get(left).getSum() < studentList.get(largest).getSum()) {largest = left;}if (right < len && studentList.get(right).getSum() < studentList.get(largest).getSum()) {largest = right;}if (largest != i) {swap(studentList, i, largest);heapify(studentList, largest, len);}}private void swap(List<Student> studentList, int i, int j) {Student student=studentList.get(i);studentList.set(i,studentList.get(j));studentList.set(j,student);}

總結(jié)

以上是生活随笔為你收集整理的题目1：学生成绩档案管理系统（实验准备）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。