新學(xué)期開始了,小哈是小哼的新同桌(小哈是個小美女哦~),小哼向小哈詢問 QQ 號,小哈當(dāng)然不會直接告訴小哼啦,原因嘛你懂的贡必。所以小哈給了小哼一串加密過的數(shù)字,同時小哈也告訴了小哼解密規(guī)則帖族。規(guī)則是這樣的:首先將第 1 個數(shù)刪除,緊接著將第 2 個數(shù)放到這串?dāng)?shù)的 尾,再將第 3 個數(shù)刪除并將第 4 個數(shù)放到這串?dāng)?shù)的 尾,再將第 5 個數(shù)刪除......直到剩下最后一個數(shù),將最后一個數(shù)也刪除。按照剛才刪除的順序,把這些刪除的數(shù)連在一起就是小哈的 QQ 啦⊙仿眨現(xiàn)在你來幫幫小哼吧。小哈給小哼加密過的一串?dāng)?shù)是“6 3 1 7 5 8 9 2 4”。
OK,現(xiàn)在輪到你動手的時候了冒嫡∧床快去找出 9 張便簽或小紙片,將“6 3 1 7 5 8 9 2 4”這9 個數(shù)分別寫在 9 張便簽上,模擬一下解密過程。如果你沒有理解錯解密規(guī)則的話,解密后小哈的 QQ 號應(yīng)該是“6 1 5 9 4 7 2 8 3”孝凌。
其實(shí)解密的過程就像是將這些數(shù)“排隊(duì)”方咆。每次從最前面拿兩個,第 1 個扔掉,第 2 個放到尾部。具體過程是這樣的:剛開始這串?dāng)?shù)是“6 3 1 7 5 8 9 2 4”,首先刪除 6 并將 3 放到這串?dāng)?shù)的 尾,這串?dāng)?shù)更新為“1 7 5 8 9 2 4 3”蟀架。接下來刪除 1 并將 7 放到 尾,即更新為
“5 8 9 2 4 3 7”瓣赂。再刪除5并將8放到 尾即“9 2 4 3 7 8”,刪除9并將2放到 尾即“4 3 78 2”,刪除4并將3放到 尾即“7 8 2 3”,刪除7并將8放到 尾即“2 3 8”,刪除2并將3 放到 尾即“8 3”,刪除 8 并將 3 放到 尾即“3”,最后刪除 3。因此被刪除的順序是“61 5 9 4 7 2 8 3”,這就是小哈的 QQ 號碼了,你可以加她試試看_片拍。
既然現(xiàn)在已經(jīng)搞清楚了解密法則,不妨自己嘗試一下去編程,我相信你一定可以寫出來的煌集。
首先需要一個數(shù)組來存儲這一串?dāng)?shù)即 int q[101],并初始化這個數(shù)組即 int q[101]={0,6,3,1,7,5,8,9,2,4};(此處初始化是我多寫了一個 0,用來填充 q[0],因?yàn)槲冶容^喜歡從 q[1]開始用,對數(shù)組初始化不是很理解的同學(xué)可以去看一下我的上 書《啊哈 C!思考快你一步》)。接下來就是模擬解密的過程了捌省。
解密的第一步是將第一個數(shù)刪除,你可以想一下如何在數(shù)組中刪除一個數(shù)呢苫纤。最簡單的方法是將所有后面的數(shù)都往前面挪動一位,將前面的數(shù)覆蓋。就好比我們在排隊(duì)買票,最前面的人買好離開了,后面所有的人就需要全部向前面走一步,補(bǔ)上之前的空位,但是這樣的做法很耗費(fèi)時間纲缓。
<p>在這里,我將引入兩個整型變量 head 和 tail方面。head 用來記錄隊(duì)列的隊(duì)首(即第一位),tail 用來記錄隊(duì)列的隊(duì)尾(即最后一位)的下一個位置。你可能會問:為什么 tail 不直接記錄隊(duì)尾,卻要記錄隊(duì)尾的下一個位置呢?這是因?yàn)楫?dāng)隊(duì)列中只剩下一個元素時,隊(duì)首和隊(duì)尾重合會帶來一些麻煩色徘。我們這里規(guī)定隊(duì)首和隊(duì)尾重合時,隊(duì)列為空恭金。</p>
<p>現(xiàn)在有 9 個數(shù),9 個數(shù)全部放入隊(duì)列之后 head=1;tail=10;此時 head 和 tail 之間的數(shù)就是
目前隊(duì)列中“有效”的數(shù)。如果要刪除一個數(shù)的話,就將 head++就 OK 了,這樣仍然可以保持 head 和 tail 之間的數(shù)為目前隊(duì)列中“有效”的數(shù)褂策。這樣做雖然浪費(fèi)了一個空間,卻節(jié)省了大量的時間,這是非常劃算的横腿。新增加一個數(shù)也很簡單,把需要增加的數(shù)放到隊(duì)尾即 q[tail]之后再 tail++就 OK 啦。</p>
<p>我們來小結(jié)一下,在隊(duì)首刪除一個數(shù)的操作是 head++;斤寂。</p>
<p>在隊(duì)尾增加一個數(shù)(假設(shè)這個數(shù)是 x)的操作是 q[tail]=x;tail++;耿焊。</p>
<p>整個解密過程,請看下面這個霸氣外漏的圖。</p>
<p>最后的輸出就是 6 1 5 9 4 7 2 8 3,代碼實(shí)現(xiàn)如下遍搞。</p>
#include <stdio.h>
int main(){
int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail;int i;
//初始化隊(duì)列
head=1;
tail=10; //隊(duì)列中已經(jīng)有9個元素了,tail指向隊(duì)尾的后一個位置
while(head<tail) //當(dāng)隊(duì)列不為空的時候執(zhí)行循環(huán)
{
//打印隊(duì)首并將隊(duì)首出隊(duì)
printf("%d ",q[head]);
head++;
//先將新隊(duì)首的數(shù)添加到隊(duì)尾
q[tail]=q[head];
tail++;
//再將隊(duì)首出隊(duì)
head++;
}
getchar();getchar();
return 0;
}
<p>怎么樣,上面的代碼運(yùn)行成功沒有?現(xiàn)在我們再來總結(jié)一下隊(duì)列的概念罗侯。隊(duì)列是一種特殊的線性結(jié)構(gòu),它只允許在隊(duì)列的首部(head)進(jìn)行刪除操作,這稱為“出隊(duì)”,而在隊(duì)列的尾部(tail)進(jìn)行插入操作,這稱為“入隊(duì)”。當(dāng)隊(duì)列中沒有元素時(即 head==tail),稱為空隊(duì)列溪猿。在我們的日常生活中有很多情況都符合隊(duì)列的特性钩杰。比如我們之前提到過的買票,每個排隊(duì)買票的窗口就是一個隊(duì)列。在這個隊(duì)列當(dāng)中,新來的人總是站在隊(duì)列的最后面,來得越早的人越靠前,也就越早能買到票,就是先來的人先服務(wù),我們稱為“先進(jìn)先出”(FirstIn First Out,FIFO)原則诊县。</p>
<p>隊(duì)列將是我們今后學(xué)習(xí)廣度優(yōu)先搜索以及隊(duì)列優(yōu)化的 Bellman-Ford 最短路算法的核心數(shù)據(jù)結(jié)構(gòu)讲弄。所以現(xiàn)在將隊(duì)列的三個基 元素(一個數(shù)組,兩個變量)封裝為一個結(jié)構(gòu)體類型,如下。</p>
struct queue{
int data[100];//隊(duì)列的主體,用來存儲內(nèi)容
int head;//隊(duì)首
int tail;//隊(duì)尾
};
<p>上面定義了一個結(jié)構(gòu)體類型,我們通常將其放在 main 函數(shù)的外面,請注意結(jié)構(gòu)體的定義 尾有個;號依痊。struct 是結(jié)構(gòu)體的關(guān)鍵字,queue 是我們?yōu)檫@個結(jié)構(gòu)體起的名字避除。這個結(jié)構(gòu)體有三個成員分別是:整型數(shù)組 data、整型 head 和整型 tail。這樣我們就可以把這三個部分放在一起作為一個整體來對待瓶摆。你可以這么理解:我們定義了一個新的數(shù)據(jù)類型,這個新類型非常強(qiáng)大,用這個新類型定義出的每一個變量可以同時存儲一個整型數(shù)組和兩個整數(shù)凉逛。</p>
<p>有了新的結(jié)構(gòu)體類型,如何定義結(jié)構(gòu)體變量呢?很簡單,這與我們之前定義變量的方式是一樣的,具體做法如下。</p>
struct queue q;
<p>請注意 struct queue 需要整體使用,不能直接寫 queue q;群井。這樣我們就定義了一個結(jié)構(gòu)體變量 q鱼炒。這個結(jié)構(gòu)體變量就可以滿足隊(duì)列的所有操作了。那又該如何訪問結(jié)構(gòu)體變量的內(nèi)部成員呢?可以使用.號,它叫做成員運(yùn)算符或者點(diǎn)號運(yùn)算符,如下:</p>
q.head=1;
q.tail=1;
scanf("%d",&q.data[q.tail]);
<p>好了,下面這段代碼就是使用結(jié)構(gòu)體來實(shí)現(xiàn)的隊(duì)列操作蝌借。</p>
#include <stdio.h>
struct queue{
int data[100];//隊(duì)列的主體,用來存儲內(nèi)容
int head;//隊(duì)首
int tail;//隊(duì)尾
};
int main(){
struct queue q;
int i;//初始化隊(duì)列
q.head=1;
q.tail=1;
for(i=1;i<=9;i++){
//依次向隊(duì)列插入9個數(shù)
scanf("%d",&q.data[q.tail]);
q.tail++;
}
while(q.head<q.tail) //當(dāng)隊(duì)列不為空的時候執(zhí)行循環(huán){
//打印隊(duì)首并將隊(duì)首出隊(duì)
printf("%d ",q.data[q.head]);
q.head++;
//先將新隊(duì)首的數(shù)添加到隊(duì)尾
q.data[q.tail]=q.data[q.head];
q.tail++;
//再將隊(duì)首出隊(duì)
q.head++;
}
getchar();getchar();
return 0;
}
<p>上面的這種寫法看起來雖然冗余了一些,但是可以加強(qiáng)你對隊(duì)列這個算法的理解昔瞧。C++的 STL 庫已經(jīng)有隊(duì)列的實(shí)現(xiàn),有興趣的同學(xué)可以參看相關(guān)材料。隊(duì)列的起源已經(jīng)無法追溯菩佑。在還沒有數(shù)字計算機(jī)之前,數(shù)學(xué)應(yīng)用中就已經(jīng)有對隊(duì)列的記載了自晰。我們生活中隊(duì)列的例子也比比皆是,比如排隊(duì)買票,又或者吃飯時候用來排隊(duì)等候的叫號機(jī),又或者撥打銀行客服選擇人工服務(wù)時,每次都會被提示“客服人員正忙,請耐心等待”,因?yàn)榭头藛T太少了,撥打電話的客戶需要按照打進(jìn)的時間順序進(jìn)行等候等等。這里表揚(yáng)一下肯德基的宅急送,沒有做廣告的嫌疑啊,每次一打就通,基 不需要等待稍坯。但是我每次打銀行的客服(具體是哪家銀行就不點(diǎn)名了)基 都要等待很長時間,總是告訴我“正在轉(zhuǎn)接,請稍候”,嘟嘟嘟三聲后就變成“客服正忙,請耐心等待!”然后就給我放很難 的曲子酬荞。看來錢在誰那里誰就是老大啊......</p>
