第一章為程序設(shè)計(jì)基礎(chǔ),本文為1.6.3泛型編程。
>>>>1.泛型編程
下面將進(jìn)一步以一個(gè)簡(jiǎn)單的循環(huán)查找為例,全面考察算法的泛化問(wèn)題。假設(shè)要編寫(xiě)一個(gè)findValue()函數(shù),在array數(shù)組中尋找一個(gè)特定的int值,詳見(jiàn)程序清單 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ù)在某個(gè)范圍內(nèi)查找value,返回的是一個(gè)指針,指向它所找到的第一個(gè)符合條件的元素。如果沒(méi)有找到,則返回最后一個(gè)元素的下一個(gè)位置(地址)?!白詈笤氐南乱粋€(gè)位置”稱(chēng)為end,其作用是返回end表示“查找無(wú)結(jié)果”,為何不返回null呢?因?yàn)閑nd指針可以對(duì)其它種類(lèi)的數(shù)據(jù)結(jié)構(gòu)帶來(lái)泛化的效果,這是null做不到的。
在學(xué)習(xí)數(shù)組時(shí),我們就被告誡,千萬(wàn)不要超越其下標(biāo)范圍,但事實(shí)上一個(gè)指向array元素的指針,不但可以合法地指向array的任何位置,也可以指向array尾端以外的任何位置。只不過(guò),當(dāng)指針指向array尾端以外的位置時(shí),它只能用于與其它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ù)組的實(shí)現(xiàn)細(xì)節(jié),比如,arraySize,太過(guò)于依賴(lài)特定的數(shù)據(jù)結(jié)構(gòu)。那么,如何設(shè)計(jì)一個(gè)算法,使它適用于大多數(shù)數(shù)據(jù)結(jié)構(gòu)呢?或者說(shuō),如何在即將處理的未知的數(shù)據(jù)結(jié)構(gòu)上,正確地實(shí)現(xiàn)所有的操作呢?事實(shí)上,一個(gè)序列有開(kāi)始和結(jié)尾,既可以使用++得到下一個(gè)元素,也可以使用“*”得到當(dāng)前元素的值。
顯然,讓閱讀代碼的人理解你的本意,至關(guān)重要是取一個(gè)不會(huì)讓人產(chǎn)生誤解的名字。對(duì)于包含范圍,常用first和last。對(duì)于包含/排序范圍,常用begin和end。比如,對(duì)于大多數(shù)需要分片的數(shù)組,使用begin和end表示包含/排除范圍是最好的選擇。遺憾的是,類(lèi)似limit、filter和length這樣具有多義性的英文單詞會(huì)帶來(lái)一定的困惑,而定義一個(gè)值的上限或下限時(shí),max_和min_就是很好的前綴。
為了讓findValue()函數(shù)適用于所有類(lèi)型的數(shù)據(jù)結(jié)構(gòu),其操作應(yīng)該更抽象化,讓findValue()函數(shù)接受兩個(gè)指針作為參數(shù),表示一個(gè)操作范圍,詳見(jiàn)程序清單 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是一個(gè)指針,因此該函數(shù)是一個(gè)返回指針的函數(shù),即指針函數(shù)。這個(gè)函數(shù)在“前閉后開(kāi)”范圍[begin, end)內(nèi)(包含了begin迭代器的當(dāng)前元素,而到end迭代器的前一個(gè)元素為止)查找value,并返回一個(gè)指針,指向它所找到的第一個(gè)符合條件的元素,如果沒(méi)有找到就返回end。這里之所以用“!=”,而不是用“<”判斷是否到達(dá)數(shù)組的尾部,因?yàn)檫@樣處理更精確。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;
當(dāng)然,findValue()函數(shù)也可以方便地用于查找array的子范圍:
int *ip = findValue(array + 2, array + 5, 3);
if(ip == end)
return false;
else
return ture;
由此可見(jiàn),findValue()函數(shù)中并無(wú)任何操作是針對(duì)特定的整數(shù)array的,即只要將操作對(duì)象的類(lèi)型加以抽象化,且將操作對(duì)象的表示法和范圍目標(biāo)的移動(dòng)行為抽象化,則整個(gè)算法就可以工作在同一個(gè)抽象層面上了。通常將整個(gè)算法的過(guò)程稱(chēng)為算法的泛型化,簡(jiǎn)稱(chēng)泛化。泛化的目的旨在使用同一個(gè)findValue()函數(shù)處理各種數(shù)據(jù)結(jié)構(gòu),通過(guò)抽象創(chuàng)建可重用代碼。
如果一個(gè)序列是有序的,則不需要用finValue()從開(kāi)始位置查找,可以使用標(biāo)準(zhǔn)C提供的bsearch()二分查找算法。對(duì)于一個(gè)更長(zhǎng)的序列,二分查找也比f(wàn)indValue()線性查找法的速度更快。即使序列中只有10個(gè)元素,也足以體現(xiàn)二分查找的比較優(yōu)勢(shì)。對(duì)于一個(gè)有1000個(gè)元素的序列,最多需要進(jìn)行10次比較,其查找的速度要快200倍。
顯然,求數(shù)組中元素的最大值,其最好的方法是通過(guò)傳遞2個(gè)指針指定元素范圍。一個(gè)指針標(biāo)識(shí)數(shù)組的開(kāi)頭,另一個(gè)指針標(biāo)識(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è)置為待處理的第一個(gè)元素(begin指向的元素)的指針,并將*ptr(元素的值)加入到total中。然后循環(huán)通過(guò)遞增操作來(lái)更新ptr,使之指向下一個(gè)元素。只要ptr不等于end,這一過(guò)程將繼續(xù)下去。當(dāng)ptr等于end時(shí),它將指向范圍中的最后一個(gè)元素后面的位置,此時(shí)循環(huán)結(jié)束。其次,請(qǐng)注意不同的函數(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指向最后一個(gè)元素后面的一個(gè)位置(數(shù)組只有n個(gè)元素,最后一個(gè)元素的地址為array+n-1),因此范圍[array,array+n]指定的是整個(gè)數(shù)組。同樣array,array+3指定了前3個(gè)元素,依此類(lèi)推。注意,根據(jù)指針減法規(guī)則,表達(dá)式end–begin是一個(gè)整數(shù)值,等于數(shù)組的元素個(gè)數(shù)。
-
算法
+關(guān)注
關(guān)注
23文章
4710瀏覽量
95405 -
軟件設(shè)計(jì)
+關(guān)注
關(guān)注
3文章
63瀏覽量
18072 -
周立功
+關(guān)注
關(guān)注
38文章
130瀏覽量
38221
原文標(biāo)題:周立功:算法的泛化問(wèn)題,你應(yīng)該知道
文章出處:【微信號(hào):ZLG_zhiyuan,微信公眾號(hào):ZLG致遠(yuǎn)電子】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
周立功教你學(xué)C語(yǔ)言編程與程序設(shè)計(jì):這樣寫(xiě)函數(shù)指針數(shù)組最好用

基于labview周立功公司的USBCAN-II型CAN卡的各種通訊子VI
周立功寫(xiě)給學(xué)單片機(jī)的年輕人 經(jīng)典勵(lì)志
【微信精選】轉(zhuǎn)行or堅(jiān)守,是否每個(gè)硬件工程師都經(jīng)歷過(guò)這樣的迷思?
周立功寫(xiě)給學(xué)單片機(jī)的年輕人
周立功電子從業(yè)經(jīng)歷回顧一:初生牛犢不怕虎
周立功電子從業(yè)經(jīng)歷回顧二:柳暗花明又一村
嵌入式系統(tǒng)軟件設(shè)計(jì)中的常用算法 (周航慈 清晰完整版)
駕駛一輛被黑客黑掉 油門(mén)和剎車(chē)都失靈的車(chē)是什么體驗(yàn)?
TinyM0_tools.pdf周立功官方文件 教你怎么下載 很不錯(cuò)

評(píng)論