【正文】 } return 1。 else if (key midvalue) high = mid1。 midvalue = list[mid]。 high=n1。 T midvalue。 } 順序查找函數(shù)模板 77 78 折半查找的基本思想 對(duì)于已按關(guān)鍵字排序的序列，經(jīng)過(guò)一次比較，可將序列分割成兩部分，然后只在有可能包含待查元素的一部分中繼續(xù)查找，并根據(jù)試探結(jié)果繼續(xù)分割，逐步縮小查找范圍，直至找到或找不到為止。i++) if (list[i] == key) return i。 ? 順序查找函數(shù)模板 – 例 914 群體數(shù)據(jù)的組織 template class T int SeqSearch(T list[], int n, T key) { for(int i=0。 } } 群體數(shù)據(jù)的組織 76 順序查找 ? 其基本思想 – 從序列的首元素開(kāi)始 ， 逐個(gè)元素與待查找的關(guān)鍵字進(jìn)行比較 ， 直到找到相等的 。 lastExchangeIndex = j。 j i。 while (i 0) { lastExchangeIndex = 0。 int lastExchangeIndex。 y = temp。 temp = x。x, T amp。對(duì) n個(gè)元素的序列，起泡排序最多需要進(jìn)行 n1趟。 – 對(duì)前 n1個(gè)元素進(jìn)行第二趟起泡排序，將其中最大元素交換到第 n1個(gè)位置。此過(guò)程稱為第一趟起泡排序。 群體數(shù)據(jù)的組織 73 最簡(jiǎn)單的交換排序方法 —— 起泡排序 對(duì)具有 n個(gè)元素的序列按升序進(jìn)行起泡排序的步驟： – 首先將第一個(gè)元素與第二個(gè)元素進(jìn)行比較，若為逆序，則將兩元素交換。 Swap(A[i], A[smallIndex])。 j n。 i++) { smallIndex = i。 for (i = 0。 } template class T void SelectionSort(T A[], int n) { int smallIndex。 x = y。y) { T temp。 ? 例 912 直接選擇排序函數(shù)模板（ 9） 群體數(shù)據(jù)的組織 template class T void Swap (T amp。 [5 4 10 20 12 3] 初始狀態(tài)： 3 [4 10 20 12 5] 3 4 [10 20 12 5] 第 i 次選擇后，將選出的那個(gè)記錄與第 i 個(gè)記錄做 交換 。 } A[j] = temp。 temp A[j1]) { A[j] = A[j1]。 while (j 0 amp。 i++) { j = i。 for (i = 1。 ? 例 911 直接插入排序函數(shù)模板（ ） 群體數(shù)據(jù)的組織 template class T void InsertionSort(T A[], int n) { int i, j。 群體數(shù)據(jù)的組織 65 內(nèi)部排序方法 ? 插入排序 ? 選擇排序 ? 交換排序 群體數(shù)據(jù)的組織 66 插入排序的基本思想 ? 每一步將一個(gè)待排序元素按其關(guān)鍵字值的大小插入到已排序序列的適當(dāng)位置上，直到待排序元素插入完為止。 ? 在排序過(guò)程中需要完成兩種基本操作： – 比較兩個(gè)數(shù)的大小 – 調(diào)整元素在序列中的位置 群體數(shù)據(jù)的組織 64 內(nèi)部排序與外部排序 ? 內(nèi)部排序： 待排序的數(shù)據(jù)元素存放在計(jì)算機(jī)內(nèi)存中進(jìn)行的排序過(guò)程。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。 – 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位。 }。 int QEmpty(void) const。 T QFront(void) const。 T QDelete(void)。 void QInsert(const Tamp。 T qlist[MaxQSize]。 const int MaxQSize = 50。 } 55 56 特殊的線性群體 —— 隊(duì)列 隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體 a1 a2 an1 an …… 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) a0 57 隊(duì)列的基本狀態(tài) ? 隊(duì)空 – 隊(duì)列中沒(méi)有元素 ? 隊(duì)滿 – 隊(duì)列中元素個(gè)數(shù)達(dá)到上限 ? 一般狀態(tài) – 隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài) 特殊的線性群體——隊(duì)列 a0 a1 an1 an …… 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (一般狀態(tài) ) …… 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (隊(duì)空狀態(tài) ) a0 a1 an1 an amax …… 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (隊(duì)滿狀態(tài) ) 元素移動(dòng)方向 元素移動(dòng)方向 58 59 循環(huán)隊(duì)列 在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動(dòng)，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開(kāi)頭。 } // include int main() { Calculator CALC。 break。 break。^39。/39。*39。+39。 break。: if (strlen(c)1) Enter(atoi(c))。 case 39。: ()。) switch(*c) { case 39。 while(cin c, *c != 39。 } else ()。()39。 } cout39。: (pow(operand2,operand1))。 case 39。} else (operand2/operand1)。: if (operand1 == 0) {cerr Divide by 0! endl。 case 39。: (operand2*operand1)。 case 39。: (operand2operand1)。 case 39。: (operand2+operand1)。 if (result) { switch(op) { case 39。 int operand1, operand2。 return True。 return False。 } opnd1 = ()。 opnd2) { if (()) { cerr Missing operand! endl。 } Boolean Calculator::GetTwoOperands(intamp。 }。 public: void Run(void)。 opnd2)。 Boolean GetTwoOperands(intamp。 include class Calculator { private: