精品国产乱码久久久久软件,亚洲综合五月天国产av,全黄H全肉边做边吃奶视频

第一章為程序設(shè)計基礎(chǔ)，本文為1.6.3泛型編程。

>>>>1.泛型編程

下面將進一步以一個簡單的循環(huán)查找為例，全面考察算法的泛化問題。假設(shè)要編寫一個findValue()函數(shù)，在array數(shù)組中尋找一個特定的int值，詳見程序清單 1.29。

程序清單 1.29 findValue()查找函數(shù)（1）

1 int *findValue(int *arrayHead, int arraySize, int value)

2 {

3 for(int i =0; i < arraySize; ++i)?

4 if(arrayHead[i] == value)

5 break;

6 return &(arrayHead[i]);

7 }

該函數(shù)在某個范圍內(nèi)查找value，返回的是一個指針，指向它所找到的第一個符合條件的元素。如果沒有找到，則返回最后一個元素的下一個位置（地址）?！白詈笤氐南乱粋€位置”稱為end，其作用是返回end表示“查找無結(jié)果”，為何不返回null呢？因為end指針可以對其它種類的數(shù)據(jù)結(jié)構(gòu)帶來泛化的效果，這是null做不到的。

在學習數(shù)組時，我們就被告誡，千萬不要超越其下標范圍，但事實上一個指向array元素的指針，不但可以合法地指向array的任何位置，也可以指向array尾端以外的任何位置。只不過，當指針指向array尾端以外的位置時，它只能用于與其它array指針相比較，不能間接引用其值。findValue()函數(shù)的使用方式如下：

const int arraySize = 7;

int array[arraySize] = {0, 1, 2, 3, 4, 5, 6};

int *end = array + arraySize;

int *ip = findValue(array, sizeof(array) / sizeof(int), 4);

if(ip == end)

return false;

else

return true;

顯然，findValue()函數(shù)暴露了數(shù)組的實現(xiàn)細節(jié)，比如，arraySize，太過于依賴特定的數(shù)據(jù)結(jié)構(gòu)。那么，如何設(shè)計一個算法，使它適用于大多數(shù)數(shù)據(jù)結(jié)構(gòu)呢？或者說，如何在即將處理的未知的數(shù)據(jù)結(jié)構(gòu)上，正確地實現(xiàn)所有的操作呢？事實上，一個序列有開始和結(jié)尾，既可以使用++得到下一個元素，也可以使用“*”得到當前元素的值。

顯然，讓閱讀代碼的人理解你的本意，至關(guān)重要是取一個不會讓人產(chǎn)生誤解的名字。對于包含范圍，常用first和last。對于包含/排序范圍，常用begin和end。比如，對于大多數(shù)需要分片的數(shù)組，使用begin和end表示包含/排除范圍是最好的選擇。遺憾的是，類似limit、filter和length這樣具有多義性的英文單詞會帶來一定的困惑，而定義一個值的上限或下限時，max_和min_就是很好的前綴。

為了讓findValue()函數(shù)適用于所有類型的數(shù)據(jù)結(jié)構(gòu)，其操作應(yīng)該更抽象化，讓findValue()函數(shù)接受兩個指針作為參數(shù)，表示一個操作范圍，詳見程序清單 1.30。

程序清單1.30findValue()查找函數(shù)（2）

1 int *findValue(int *begin, int *end, int value)

2 {

3 while(begin != end && *begin != value)

4 ++begin;

5 return begin;

6 }

由于findValue函數(shù)的返回值begin是一個指針，因此該函數(shù)是一個返回指針的函數(shù)，即指針函數(shù)。這個函數(shù)在“前閉后開”范圍[begin, end)內(nèi)（包含了begin迭代器的當前元素，而到end迭代器的前一個元素為止）查找value，并返回一個指針，指向它所找到的第一個符合條件的元素，如果沒有找到就返回end。這里之所以用“!=”，而不是用“<”判斷是否到達數(shù)組的尾部，因為這樣處理更精確。findValue()函數(shù)的使用方式如下：

const int arraySize = 7;

int array[arraySize] = {0, 1, 2, 3, 4, 5, 6};

int *end = array + arraySize;

int *ip = findValue(array, end, 4);

if(ip == end)

return false;

else

return true;

當然，findValue()函數(shù)也可以方便地用于查找array的子范圍：

int *ip = findValue(array + 2, array + 5, 3);

if(ip == end)

return false;

else

return ture;

由此可見，findValue()函數(shù)中并無任何操作是針對特定的整數(shù)array的，即只要將操作對象的類型加以抽象化，且將操作對象的表示法和范圍目標的移動行為抽象化，則整個算法就可以工作在同一個抽象層面上了。通常將整個算法的過程稱為算法的泛型化，簡稱泛化。泛化的目的旨在使用同一個findValue()函數(shù)處理各種數(shù)據(jù)結(jié)構(gòu)，通過抽象創(chuàng)建可重用代碼。

如果一個序列是有序的，則不需要用finValue()從開始位置查找，可以使用標準C提供的bsearch()二分查找算法。對于一個更長的序列，二分查找也比findValue()線性查找法的速度更快。即使序列中只有10個元素，也足以體現(xiàn)二分查找的比較優(yōu)勢。對于一個有1000個元素的序列，最多需要進行10次比較，其查找的速度要快200倍。

顯然，求數(shù)組中元素的最大值，其最好的方法是通過傳遞2個指針指定元素范圍。一個指針標識數(shù)組的開頭，另一個指針標識數(shù)組的尾部。比如：

int iMax(const int *begin, const int *end);

顯然，如果只是傳遞指針，數(shù)據(jù)就有被修改的可能。如果不希望數(shù)據(jù)被修改，就要傳遞指向整數(shù)常量的指針。使用for循環(huán)的示例如下：

for(ptr = begin; ptr != end; ptr++)

total = total +*ptr;

將ptr設(shè)置為待處理的第一個元素（begin指向的元素）的指針，并將*ptr（元素的值）加入到total中。然后循環(huán)通過遞增操作來更新ptr，使之指向下一個元素。只要ptr不等于end，這一過程將繼續(xù)下去。當ptr等于end時，它將指向范圍中的最后一個元素后面的位置，此時循環(huán)結(jié)束。其次，請注意不同的函數(shù)調(diào)用是如何指定數(shù)組中不同的范圍的。比如：

int array[] = {39, 33, 18, 64, 73, 30, 49, 51, 81};

int n = sizeof(array) / sizeof(array[0]);

int *past = array + n;

int max = iMax(array, array + n);

int max = iMax(array, array + 3);

int max = iMax(array +3, array + 8);

指針array+n指向最后一個元素后面的一個位置（數(shù)組只有n個元素，最后一個元素的地址為array+n-1），因此范圍[array，array+n]指定的是整個數(shù)組。同樣array，array+3指定了前3個元素，依此類推。注意，根據(jù)指針減法規(guī)則，表達式end–begin是一個整數(shù)值，等于數(shù)組的元素個數(shù)。

聲明：本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人，不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學習之用，如有內(nèi)容侵權(quán)或者其他違規(guī)問題，請聯(lián)系本站處理。舉報投訴