【正文】 ? 實(shí)驗(yàn)任務(wù) – 實(shí)驗(yàn)八 。 } 群體數(shù)據(jù)的組織 C++語言程序設(shè)計(jì) 77 小結(jié)與復(fù)習(xí)建議 ? 主要內(nèi)容 – 模板、群體類和群體數(shù)據(jù)的組織 ? 達(dá)到的目標(biāo) – 理解模板的作用，學(xué)會(huì)簡單的應(yīng)用。 else low = mid+1。 if (key == midvalue) return mid。 while (low = high) { mid = (low+high)/2。 low=0。 群體數(shù)據(jù)的組織 C++語言程序設(shè)計(jì) 75 折半查找舉例 用折半查找法，在下列序列中查找值為 21的元素： L=1 5 13 19 21 37 56 64 75 80 88 92 H=11 M =INT((L+H)/2)=6 5 13 19 21 37 L=1 H=M1=5 M=INT((L+H)/2)=3 M 21 37 H L=M+1=4 L M=INT((L+H)/2)=4 M C++語言程序設(shè)計(jì) 76 例 915 折半查找函數(shù)模板 template class T int BinSearch(T list[], int n, T key) { int mid, low, high。 return 1。i n。若整個(gè)序列中沒有與待查找關(guān)鍵字相等的元素 ， 就是查找不成功 。 } i=lastExchangeIndex。 j++) if (A[j+1] A[j]) { Swap(A[j],A[j+1])。 for (j = 0。 i = n1。 } template class T void BubbleSort(T A[],int n) {int i,j。 x = y。y) { T temp。 群體數(shù)據(jù)的組織 C++語言程序設(shè)計(jì) 70 起泡排序舉例 對(duì)整數(shù)序列 8 5 2 4 3 按升序排序 8 5 2 4 3 5 2 4 3 8 2 4 3 5 8 2 3 4 5 8 2 3 4 5 8 初始狀態(tài) 第一趟結(jié)果 第二趟結(jié)果 第三趟結(jié)果 第四趟結(jié)果 小的逐漸上升 每趟沉下一個(gè)最大的 群體數(shù)據(jù)的組織 C++語言程序設(shè)計(jì) 71 例 913 起泡排序函數(shù)模板 template class T void Swap (T amp。 – 如此繼續(xù)，直到某一趟排序未發(fā)生任何交換時(shí)，排序完畢。經(jīng)過第一趟，最大的元素便被交換到第 n個(gè)位置。然后比較第二、第三個(gè)元素，依次類推，直到第 n1和第 n個(gè)元素進(jìn)行了比較和交換。 } } 直接選擇排序函數(shù)模板（ ） 67 C++語言程序設(shè)計(jì) 68 交換排序的基本思想 兩兩比較待排序序列中的元素，并交換不滿足順序要求的各對(duì)元素，直到全部滿足順序要求為止。 j++) if (A[j] A[smallIndex]) smallIndex = j。 for (j = i+1。 i n1。 int i, j。 y = temp。 temp = x。x, T amp。 3 4 5 [20 12 10] ... ... C++語言程序設(shè)計(jì) 66 直接選擇排序 ? 在選擇類排序方法中，從待排序序列中選擇元素的方法不同，又分為不同的選擇排序方法，其中最簡單的是通過順序比較找出待排序序列中的最小元素，稱為直接選擇排序。 } } 直接插入排序函數(shù)模板（ ） 64 C++語言程序設(shè)計(jì) 65 選擇排序的基本思想 每次從待排序序列中選擇一個(gè)關(guān)鍵字最小的元素，（當(dāng)需要按關(guān)鍵字升序排列時(shí)），順序排在已排序序列的最后，直至全部排完。 j。amp。 temp = A[i]。 i n。 T temp。 初始狀態(tài)： [5] 4 10 20 12 3 插入操作： 1 [4] [4 5] 10 20 12 3 2 [10] [4 5 10] 20 12 3 3 [20] [4 5 10 20] 12 3 4 [12] [4 5 10 12 20] 3 5 [3] [3 4 5 10 12 20] C++語言程序設(shè)計(jì) 63 直接插入排序 ? 在插入排序過程中，由于尋找插入位置的方法不同又可以分為不同的插入排序算法，這里我們只介紹最簡單的直接插入排序算法。 ? 外部排序： 待排序的數(shù)據(jù)元素?cái)?shù)量很大，以致內(nèi)存存中一次不能容納全部數(shù)據(jù)，在排序過程中尚需對(duì)外存進(jìn)行訪問的排序過程。 – 關(guān)鍵字： 數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。 //成員函數(shù)的實(shí)現(xiàn)略 C++語言程序設(shè)計(jì) 58 第三部分： 群 體數(shù)據(jù)的組織 ? 插入排序 ? 選擇排序 ? 交換排序 ? 順序查找 ? 折半查找 C++語言程序設(shè)計(jì) 59 排序（ sorting） ? 排序 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè) 數(shù)據(jù)元素 的任意序列，重新排列成一個(gè)按 關(guān)鍵字 有序的序列。 int QFull(void) const。 int QLength(void) const。 void ClearQueue(void)。 item)。 public: Queue (void)。 template class T class Queue { private: int front,rear,count。 特殊的線性群體——隊(duì)列 1 2 3 4 …… m1 m2 m3 0 am am+1 am+2 a3 隊(duì)頭 隊(duì)尾 a4 am2 am3 am1 隊(duì)滿狀態(tài) 元素個(gè)數(shù) =m 1 2 3 4 …… m1 m2 m3 0 隊(duì)尾 隊(duì)頭 隊(duì)空狀態(tài) 元素個(gè)數(shù) =0 隊(duì)尾 1 2 3 4 …… m1 m2 m3 0 a0 a1 a2 a3 隊(duì)頭 一般狀態(tài) 56 C++語言程序設(shè)計(jì) 57 例 910 隊(duì)列類模板 特殊的線性群體——隊(duì)列 ifndef QUEUE_CLASS define QUEUE_CLASS include iostream include cstdlib using namespace std。 ()。 } } void Calculator::Clear(void) { ()。 default: Enter(atoi(c))。: Compute(*c)。: case 39。: case 39。: case 39。 case 39。 else Compute(*c)。39。 break。c39。q39。 } 49 void Calculator::Run(void) { char c[20]。 39。=39。 break。^39。 break。 ()。/39。 break。*39。 break。39。 break。+39。 result = GetTwoOperands(operand1, operand2)。 } 48 void Calculator::Compute(char op) { Boolean result。 } opnd2 = ()。 if (()) { cerr Missing operand! endl。 return False。 opnd1,intamp。 47 void Calculator::Enter(int num)