【正文】 ?由 基本的數(shù)據(jù)類型 組成 , 并包括 一組相關(guān)的服務(wù) （或稱操作） ?信息隱蔽 和 數(shù)據(jù)封裝 ，使用與實(shí)現(xiàn)相分離 抽象數(shù)據(jù)類型 查找 登錄 刪除 修改 符 號 表 自然數(shù)的抽象數(shù)據(jù)類型定義 ADT NaturalNumber is objects: 一個整數(shù)的有序子集合 ,它開始于 0,結(jié)束 于機(jī)器能表示的最大整數(shù) (MaxInt)。 j n。 operator (istreamamp。 OuStream “數(shù)組當(dāng)前大小 : ” endl。 } } 使用模板的選擇排序算法的主函數(shù) include “” const int SIZE = 10。 int k = seqsearch (a, n, x)。 //針對 for 語句 s += a[i]。 for ( int i = 0。 exchange ){ exchange = 0。amp。 in 。 count++。 return i。 } template class Type void dataListType::Sort ( ) { //按非遞減順序?qū)?ArraySize個關(guān)鍵碼 //Element[0]到 Element[ArraySize1]排序 for ( int i = ArraySize 1。 for (int i = 0。 operator (ostreamamp。 } ? 細(xì)化程序： 程序 SelectSort 算法設(shè)計 自頂向下，逐步求精 void selectSort ( int a[ ], const int n ) { //對 n個整數(shù) a[0],a[1],…,a[n 1]按遞增順序排序 for ( int i = 0。 ? 數(shù)值性數(shù)據(jù) ? 非數(shù)值性數(shù)據(jù) 數(shù)據(jù)對象 (data object) ? 數(shù)據(jù)的子集。 i n1。 public: dataList (int size = 10) : ArraySize (size), Element (new Type [Size]) { } dataList ( ) {delete [ ] Element。 } template class Type ostreamamp。 i++) { cout “元素 ” i “:” 。amp。 i++ ) s += a[i]。 } 注意 ： 一個語句本身的程序步數(shù)可能不等于該語句一次執(zhí)行所具有的程序步數(shù)。 } 漸進(jìn)時間復(fù)雜度為 O(max (m*n, m)) template class Type //起泡排序 void dataListType :: bubbleSort ( ) { //對表逐趟比較 , ArraySize 是表當(dāng)前長度 int i = 1。 j) if ( Element[j1] Element[j] ) { Swap ( j 1, j )。 //數(shù)據(jù)累加 for ( int j = 0。 //針對 for 的最后一次 count++。 double runTime = stop start。 cout TestList endl。 operator (istreamamp。 } 類中所有操作作為模板函數(shù)的實(shí)現(xiàn) include “” template class Type void dataList Type :: Swap (int m1, int m2) { //交換由 m1, m2為下標(biāo)的數(shù)組元素的值 Type temp = Element [m1]。 a[i] = a[k]。 Zero( ) : NaturalNumber 返回自然數(shù) 0 。 False, True ? Boolean, +、 、 、 ==、 =等都是可用的服務(wù)。 int temp = a[i]。 inList)。 } template class Type istreamamp。 cin TestList。stop)。 } //針對賦值語句 count++。 i++ ) { //x中各行