本文關(guān)鍵詞：編程珠璣，由筆耕文化傳播整理發(fā)布。

問(wèn)題描述

輸入：一個(gè)最多包含n個(gè)正整數(shù)的文件，每個(gè)數(shù)都小于n，其中n=107。如果在輸入文件中有任何正數(shù)重復(fù)出現(xiàn)就是致命錯(cuò)誤。沒(méi)有其他數(shù)據(jù)與該正數(shù)相關(guān)聯(lián)。

輸出：按升序排列的輸入正數(shù)的列表。

約束：最多有1MB的內(nèi)存空間可用，有充足的磁盤(pán)存儲(chǔ)空間可用。運(yùn)行時(shí)間最多幾分鐘，運(yùn)行時(shí)間為10秒就不需要進(jìn)一步優(yōu)化。

程序設(shè)計(jì)與實(shí)現(xiàn)概要：

應(yīng)用位圖或位向量表示集合。可用一個(gè)10位長(zhǎng)的字符串來(lái)表示一個(gè)所有元素都小于10的簡(jiǎn)單的非負(fù)整數(shù)集合，例如，，可以用如下字符串表示集合{1,2,4,5,8}:

0  1  1  1  0  1  0  0  1  0  0

代表集合中數(shù)值的位都置為1，其他左所有的位置為0.編程珠璣當(dāng)中建議是一年個(gè)一個(gè)具有1000萬(wàn)個(gè)位的字符串來(lái)表示這個(gè)文件，那么這個(gè)文件的所占容量為10000000 bit=107bit，不到1MB的大小，其中，當(dāng)且精當(dāng)整數(shù)i在文件中存在，第i為1，這個(gè)表示利用了該問(wèn)題的三個(gè)在排序問(wèn)題中不常見(jiàn)的屬性：輸入數(shù)據(jù)限制在相對(duì)較小的范圍內(nèi)；數(shù)據(jù)沒(méi)有重復(fù)；而且對(duì)于每條記錄而言，除了單一個(gè)整數(shù)外沒(méi)有其他關(guān)聯(lián)數(shù)據(jù)。

如給定表示文件中整數(shù)集合的位圖數(shù)據(jù)結(jié)構(gòu)，則可以分三個(gè)階段來(lái)編寫(xiě)程序

第一階段：將所有的位都置為0，從而將集合初始化為空。

第二階段：通過(guò)讀入文件中的每個(gè)整數(shù)來(lái)建立集合，將每個(gè)對(duì)應(yīng)的位置都置為1。

第三階段：檢驗(yàn)每一位，如果該為為1，就輸出對(duì)應(yīng)的整數(shù)，有此產(chǎn)生有序的輸出文件。

下面的C語(yǔ)言的實(shí)現(xiàn)和C++的實(shí)現(xiàn)代碼

C語(yǔ)言：

所申請(qǐng)的int數(shù)組如下所示：

字節(jié)位置=數(shù)據(jù)/32;(采用位運(yùn)算即右移5位)

位位置=數(shù)據(jù)%32;(采用位運(yùn)算即跟0X1F進(jìn)行與操作)。

#include

  本文關(guān)鍵詞：編程珠璣，由筆耕文化傳播整理發(fā)布。