次課--鏈接存儲結(jié)構(gòu)上的排序和查找.ppt

1、首頁,本章挺難的吧。加油哦,教案,主要內(nèi)容,直接插入排序 鏈接存儲結(jié)構(gòu)上的直接插入排序 鏈接存儲結(jié)構(gòu)上的查找,排序回顧,在第5章中已介紹了冒泡排序和簡單選擇排序。 本章介紹另外一種常用的排序方法直接插入排序,直接插入排序,直接插入排序：通過順序地把待排序的對象按其關(guān)鍵字值的大小插入到已排序?qū)ο蠹系倪m當位置來實現(xiàn)排序的,直接插入排序舉例,假定將數(shù)據(jù)按從小到大進行排序。對一組關(guān)鍵字（42，38，64，91，14，25） 進行排序,直接插入排序的基本思想,基本思路（對n個數(shù)據(jù)進行排序） 假設(shè)待排序的對象為R0、R1、R2、Rn-1。 （1）開始時，已排序?qū)ο蠹现挥幸粋€對象R0。 （2）尋找合適的

2、位置，把對象R1插入到已排好序的對象集合中去，使對象R0、R1排好序。 （3）依次類推，分別將對象R2、R3、Rn-1插入到已排好序的對象集合中去,直接插入排序舉例,運行程序(9_1,看源程序(9_1,補例】將一組數(shù)據(jù)（42，38，64，91，14，25）按從小到大進行排序。 流程圖,源程序,返回,鏈接存儲結(jié)構(gòu)上的直接插入排序,鏈表插入排序的最終排序結(jié)果是把對象集合按關(guān)鍵碼大小依次鏈接地存儲在一個鏈表中。 具體做法（單鏈表） （1）首先將第一個記錄看作只有一個記錄的有序子序列。 （2）然后將第二個記錄插入到該有序子序列中，再插入第三個記錄、，直到插入最后一個記錄為止。每趟插入，總是從鏈表的表頭

3、開始搜索適當?shù)牟迦胛恢?在黑板上用示例圖進行講解,單鏈表的直接插入排序舉例,例7-6】在【例7-5】的基礎(chǔ)上修改程序，使輸出的數(shù)據(jù)從小到大排序。 流程圖 源程序,思考：不用附加頭結(jié)點，任何修改？(9_3,運行程序(9_2,看源程序(9_2,任務相關(guān)部分,1）在任務程序中，要求按照不同的要求對數(shù)據(jù)進行排序。所以，我們可以設(shè)計成子菜單的形式，讓用戶根據(jù)菜單選擇，并按選定的功能號分別實現(xiàn)不同的排序。 （2）對鏈接存儲結(jié)構(gòu)的數(shù)據(jù)，可以采用前面講解的直接插入排序算法來實現(xiàn)。 （3）為避免編寫多個排序子函數(shù)，我們可以參考第6章中介紹的通用排序的思想來實現(xiàn),返回,查找回顧,在第5章中已介紹了順序查找法和折半

4、查找法。 對于順序存儲線性表，兩種查找法都可以用。 對于用鏈表存儲的線性表而言，適合用哪種查找法呢,鏈接存儲結(jié)構(gòu)上的查找,鏈接存儲結(jié)構(gòu)（單鏈表）上的查找只能從鏈表的首結(jié)點開始順序查找。 （1）若鏈表無序，則從鏈表的首結(jié)點開始，逐一檢查鏈表中每個結(jié)點的值，直至所找的結(jié)點找到或者直至考察到了鏈表的末結(jié)點后仍未找到。 （2）若鏈表有序，則順序查找時，發(fā)現(xiàn)結(jié)點的值比要查找的值大（或?。r，就可提早得出結(jié)論了,單鏈表的順序查找舉例,例7-7】改寫【例7-5】的create函數(shù)，使線性表中沒有相同的數(shù)據(jù)。 分析 （1）要使線性表中沒有相同的數(shù)據(jù)，則在輸入數(shù)據(jù)后要判斷該數(shù)據(jù)在鏈表中存在不存在，如不存在，才進

5、行插入操作。 （2）“判斷該數(shù)據(jù)在鏈表中存在不存在”就涉及到查找。 編寫一個函數(shù)，其功能是查找某個數(shù)據(jù)在鏈表中存在不存在,修改create函數(shù),單鏈表的順序查找舉例,例7-7】改寫【例7-5】的create函數(shù)，使線性表中沒有相同的數(shù)據(jù)。 查找子函數(shù) 流程圖,運行程序(9_4,看源程序(9_4,源程序,單鏈表的順序查找舉例,例7-7】改寫【例7-5】的create函數(shù)，使線性表中沒有相同的數(shù)據(jù)。 create函數(shù)流程圖,運行程序(9_4,看源程序(9_4,思考：不用附加頭結(jié)點，任何修改？(9_5,源程序,任務相關(guān)部分,在任務程序中，要求按照不同的要求對數(shù)據(jù)進行查找。所以，我們可以設(shè)計成子菜單的形式，讓用戶根據(jù)菜單選擇，并按選定的功能號分別實現(xiàn)不同的查找。 （1）查找指定學號的學生：可以先對學生數(shù)據(jù)按學號進行排序，然后查找時就不需要搜索整個鏈表，只要搜索到某個結(jié)點的學號等于或大于待查找的學號就可以提前結(jié)束了。 （2）查找符合三好生標準的學生（平均分=85分）：先對鏈表按照總分遞減排序，然后只要搜索到某個結(jié)點的平均分85分就可以提前結(jié)束。 （3）查找成績不及格的學生：只能采用搜索整個鏈表的方法,本次課總結(jié),排序回顧 直接插入排序 單鏈