【正文】 群體數(shù)據(jù)的組織 C++語言程序設(shè)計 清華大學(xué) 鄭莉 59 內(nèi)部排序方法 ? 插入排序 ? 選擇排序 ? 交換排序 群體數(shù)據(jù)的組織 C++語言程序設(shè)計 清華大學(xué) 鄭莉 60 插入排序的基本思想 ? 每一步將一個待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當位置上，直到待排序元素插入完為止。 ? 在排序過程中需要完成兩種基本操作： – 比較兩個數(shù)的大小 – 調(diào)整元素在序列中的位置 群體數(shù)據(jù)的組織 C++語言程序設(shè)計 清華大學(xué) 鄭莉 58 內(nèi)部排序與外部排序 ? 內(nèi)部排序： 待排序的數(shù)據(jù)元素存放在計算機內(nèi)存中進行的排序過程。一個數(shù)據(jù)元素可由若干數(shù)據(jù)項組成。 – 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位。 //類的實現(xiàn)略 C++語言程序設(shè)計 清華大學(xué) 鄭莉 51 特殊的線性群體 ——隊列 隊列是只能向一端添加元素，從另一端刪除元素的線性群體 a1 a2 an1 an …… 隊頭 隊尾 入隊 出隊 a0 C++語言程序設(shè)計 清華大學(xué) 鄭莉 52 隊列的基本狀態(tài) ? 隊空 – 隊列中沒有元素 ? 隊滿 – 隊列中元素個數(shù)達到上限 ? 一般狀態(tài) – 隊列中有元素，但未達到隊滿狀態(tài) 特殊的線性群體——隊列 a0 a1 an1 an ?? 隊頭 隊尾 入隊 出隊 數(shù)組下標 0 1 n1 n max (一般狀態(tài) ) ?? 隊頭 隊尾 入隊 出隊 數(shù)組下標 0 1 n1 n max (隊空狀態(tài) ) a0 a1 an1 an amax ?? 隊頭 隊尾 入隊 出隊 數(shù)組下標 0 1 n1 n max (隊滿狀態(tài) ) 元素移動方向 元素移動方向 53 C++語言程序設(shè)計 清華大學(xué) 鄭莉 54 循環(huán)隊列 在想象中將數(shù)組彎曲成環(huán)形，元素出隊時，后繼元素不移動，每當隊尾達到數(shù)組最后一個元素時，便再回到數(shù)組開頭。 bool isFull() const。peek() const。 void clear()。item)。 public: Stack()。 an ┆ a2 a1 入棧 出棧 棧頂 棧底 特殊的線性群體——棧 C++語言程序設(shè)計 清華大學(xué) 鄭莉 39 棧的應(yīng)用舉例 ——表達式處理 b a / a/b+c*d (a) t1 + a/b+c*d t1=a/b (b) d c t1 * + a/b+c*d (c) t3 a/b+c*d t3=t1+t2 (e) t2 t1 + a/b+c*d t2=c*d (d) 特殊的線性群體——棧 C++語言程序設(shè)計 清華大學(xué) 鄭莉 40 棧的基本狀態(tài) ? ?？? – 棧中沒有元素 ? 棧滿 – 棧中元素個數(shù)達到上限 ? 一般狀態(tài) – 棧中有元素，但未達到棧滿狀態(tài) 特殊的線性群體——棧 棧頂 ┆ an ┆ a1 a0 入棧 出棧 數(shù)組下標 max n 1 0 一般狀態(tài) 棧頂 入棧 出棧 數(shù)組下標 初始狀態(tài)（?？眨? max n 1 0 棧頂 amax ┆ an ┆ a1 a0 入棧 出棧 數(shù)組下標 max n 1 0 棧滿狀態(tài) 41 C++語言程序設(shè)計 清華大學(xué) 鄭莉 42 棧的基本操作 ? 初始化 ? 入棧 ? 出棧 ? 清空棧 ? 訪問棧頂元素 ? 檢測棧的狀態(tài)（滿、空） 特殊的線性群體——棧 C++語言程序設(shè)計 清華大學(xué) 鄭莉 43 棧類模板 (例 98) 特殊的線性群體——棧 // ifndef STACK_H define STACK_H include cassert template class T, int SIZE = 50 class Stack { private: T list[SIZE]。 return 0。 while (!()) { cout () 。 } cout List: 。 while (!()) { if (() == key) ()。 cin key。 int key。 ()。 ()。 (item)。 i++) { int item。 for (int i = 0。 C++語言程序設(shè)計 清華大學(xué) 鄭莉 37 鏈表類應(yīng)用舉例 (例 97) 順序訪問的線性群體 // include iostream include using namespace std。然后從鍵盤輸入一個待查找整數(shù)，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點（如果出現(xiàn)多次，全部刪除），然后輸出刪除結(jié)點以后的鏈表。 }。 const Tamp。 Tamp。 T deleteFront()。 void insertAfter(const T amp。 void insertAt(const T amp。 void insertRear(const T amp。 void insertFront(const T amp。 bool endOfList() const。 bool isEmpty() const。L)。 LinkedListT amp。L)。 public: LinkedList()。 void copy(const LinkedListTamp。item,NodeT *ptrNext=NULL)。 int position。 } tempPtr C++語言程序設(shè)計 清華大學(xué) 鄭莉 34 鏈表的基本操作 ? 生成結(jié)點 ? 插入結(jié)點 ? 查找結(jié)點 ? 刪除結(jié)點 ? 遍歷鏈表 ? 清空鏈表 順序訪問的線性群體 C++語言程序設(shè)計 清華大學(xué) 鄭莉 35 鏈表類模板 (例 96) 順序訪問的線性群體 ifndef LINKEDLIST_H define LINKEDLIST_H include template class T class LinkedList { private: //數(shù)據(jù)成員： NodeT *front, *rear NodeT *prevPtr, *currPtr。 next = tempPtrnext。 //當前節(jié)點的指針域指向 p } 順序訪問的線性群體 C++語言程序設(shè)計 清華大學(xué) 鄭莉 33 刪除結(jié)點之后的結(jié)點 順序訪問的線性群體 data1 data2 data3 … … NodeT *NodeT::deleteAfter(void) { NodeT *tempPtr = next。 順序訪問的線性群體 C++語言程序設(shè)計 清華大學(xué) 鄭莉 32 在結(jié)點之后插入一個結(jié)點 data1 data2 … p data … template class T void NodeT::insertAfter(NodeT *p) { //p節(jié)點指針域指向當前節(jié)點的后繼節(jié)點 pnext = next。 NodeT *nextNode() const。 void insertAfter(NodeT *p)。 Node(const Tamp。 順序訪問的線性群體 C++語言程序設(shè)計 清華大學(xué) 鄭莉 30 單鏈表 data1 data2 data3 datan NULL ? head rear 順序訪問的線性群體 C++語言程序設(shè)計 清華大學(xué) 鄭莉 31 單鏈表的結(jié)點類模板 template class T class Node { private: NodeT *next。 ? 每一個結(jié)點包括 數(shù)據(jù)域 和指向鏈表中下一個結(jié)點的 指針 （即下一個結(jié)點的地址）。 } 28 C++語言程序設(shè)計 清華大學(xué) 鄭莉 29 鏈表 ? 鏈表是一