汽車牌照排序與查找課程設(shè)計(jì)報(bào)告

1、<p><b>　　計(jì)算機(jī)科學(xué)與技術(shù)系</b></p><p><b>　　課程設(shè)計(jì)報(bào)告</b></p><p>　　2009 ～20010 學(xué)年第 二 學(xué)期</p><p><b>　　20010年6月</b></p><p>　　題目：汽車牌照的排序與查找問題，實(shí)

2、現(xiàn)對汽車牌照按多關(guān)鍵字排序及快速查找。其中汽車牌照有漢字、字母和數(shù)字混合排列，例如：皖A(yù)12345。使用基數(shù)排序方法進(jìn)行排序，并在排序的基礎(chǔ)上，利用二分查找思想實(shí)現(xiàn)對汽車牌照按多關(guān)鍵字的查找。</p><p>　　一、問題分析和任務(wù)定義</p><p>　　此程序要完成如下要求：選擇一種數(shù)據(jù)結(jié)構(gòu)來存儲每個(gè)車輛的信息（如車主姓名,汽車等），在此基礎(chǔ)上進(jìn)行基數(shù)排序，而汽車牌照是由漢字、字母以及

3、數(shù)字組成，即多關(guān)鍵字，其中字母和數(shù)字的比較是比較容易實(shí)現(xiàn)的，考慮到漢字的存儲等各方面原因，對漢字的排序并不是很容易就能完成的，故不能直接對漢字排序。經(jīng)過分析可知，汽車牌照中的漢字是各個(gè)省市自治區(qū)的簡稱，共有34個(gè)。這些漢字可以根據(jù)其漢語拼音的規(guī)則進(jìn)行排序，然后預(yù)先存放到字符串?dāng)?shù)組中，這樣每個(gè)漢字就對應(yīng)著一個(gè)數(shù)組下標(biāo)，只要對數(shù)組下標(biāo)進(jìn)行排序就可以實(shí)現(xiàn)對漢字的排序了。在對車牌號進(jìn)行查找時(shí)，先對車牌號進(jìn)行排序，然后將車牌號中的漢字及字符均轉(zhuǎn)換

4、成一個(gè)長整形數(shù)據(jù)存儲在一個(gè)預(yù)先定義的一個(gè)一維數(shù)組中并把需要查找的車牌號碼也轉(zhuǎn)換成一個(gè)長整型數(shù)據(jù)，然后在原先的一維數(shù)組中使用二分查找來查找該車牌號碼對應(yīng)的車輛信息。</p><p>　　二、數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)</p><p>　　1、數(shù)據(jù)結(jié)構(gòu)的選擇：</p><p>　　程序要求實(shí)現(xiàn)對汽車牌照的排序與查找，而如果僅僅進(jìn)行牌照的排序與查找，則顯得程序沒有太大的實(shí)用

5、性，所以考慮在程序中加入例如車主的姓名以及車子的品牌等內(nèi)容來增加程序的實(shí)用性。為了能夠更好的完成這些功能，在這里選用鏈表來存儲所有車輛的信息，用鏈表中的單個(gè)節(jié)點(diǎn)來存儲一輛汽車的信息，而對應(yīng)的各個(gè)節(jié)點(diǎn)的域中則存儲其對應(yīng)的車輛信息（如車牌號碼、車主姓名、車的品牌等信息）。在存儲汽車牌照中的漢字時(shí)，由于漢字在內(nèi)存中占用兩個(gè)字節(jié)，需要使用字符串?dāng)?shù)據(jù)來存儲。其中的26個(gè)字母則使用一個(gè)一維字符數(shù)組來存儲。車主的姓名及車子的品牌則使用一維字符數(shù)組來存

6、儲。在基數(shù)排序時(shí)，每趟的數(shù)據(jù)收集由兩個(gè)鏈隊(duì)列來完成，鏈隊(duì)列的個(gè)數(shù)為基數(shù)的個(gè)數(shù)，兩個(gè)鏈隊(duì)列的隊(duì)列指針分別指向每組鏈隊(duì)列的隊(duì)頭和隊(duì)尾。</p><p><b>　　2、概要設(shè)計(jì)</b></p><p>　　為了實(shí)現(xiàn)上述功能，需要使用一下函數(shù)：</p><p>　　main()：主函數(shù)</p><p>　　Setlist()：

7、添加車輛函數(shù)</p><p>　　Distribute()：進(jìn)行基數(shù)排序每一趟的分配函數(shù)</p><p>　　Collect()：進(jìn)行基數(shù)排序每一趟的收集函數(shù)</p><p>　　find()：二分查找函數(shù)</p><p>　　menu()：菜單函數(shù)</p><p>　　print()：輸出所有車輛信息函數(shù)</p

8、><p>　　insort()：基數(shù)排序函數(shù)</p><p>　　圖1 各函數(shù)間關(guān)系如下：</p><p>　　圖2 主函數(shù)main()流程圖</p><p>　　圖3 添加車輛函數(shù)SetList(p)流程圖</p><p>　　圖4 排序子函數(shù)paixu(p)的流程圖</p><p>　　圖5

9、 查找子函數(shù)find(p)的流程圖</p><p><b>　　三、詳細(xì)設(shè)計(jì)和編碼</b></p><p><b>　　1、文件的的讀?。?lt;/b></p><p>　　在這個(gè)程序當(dāng)中采取了文件的讀取，主要實(shí)現(xiàn)的功能是從文件當(dāng)中讀取所要處理的數(shù)據(jù)，即為車牌的信息資料。如一個(gè)車牌的信息包括：車牌號（皖A(yù)12345）、車主姓名（

10、張三）和車的品牌（寶馬）三個(gè)內(nèi)容，在程序的操作過程過程是對文件進(jìn)行一個(gè)一個(gè)讀取，用fscanf(f1,”%s%s%s”,p->key,p->name,p->paizi)語句來實(shí)現(xiàn)，就是將車牌號（皖A(yù)12345）讀入到p->key當(dāng)中，將車主姓名讀入到p->name當(dāng)中，將車的品牌讀入到p->paizi當(dāng)中。讀入之后就可以對其進(jìn)行操作了。由于文件尾默認(rèn)為-1結(jié)束，所以對文件讀取的控制采用while(fs

11、canf(f1,"%s%s%s",p->key ,p->name ,p->paizi)!=EOF)來實(shí)現(xiàn)</p><p>　　還有就是讀入方法，這個(gè)程序是采用鏈表的存儲方式來存取信息的，所以讀入方式可以采取頭插法建立鏈表的方法來對每個(gè)文件進(jìn)行讀取。頭插法的具體操作為</p><p>　　head=NULL;</p><p>　

12、　p=(Rnode *)malloc(sizeof(Rnode));</p><p>　　p->next=NULL;</p><p>　　while(fscanf(f1,"%s%s%s",p->key,p->name,p->paizi)!=EOF) { if(head==NULL) {</p><p>&l

13、t;b>　　l=head=p;</b></p><p><b>　　}</b></p><p><b>　　else{</b></p><p>　　l->next=p;</p><p><b>　　l=p;}</b></p><p&g

14、t;　　p=(Rnode *)malloc(sizeof(Rnode));</p><p>　　p->next=NULL;</p><p><b>　　}</b></p><p>　　2、基數(shù)排序的過程：</p><p>　　首先將待排序的記錄分成若干個(gè)子關(guān)鍵字，排序時(shí)，先按最低位的關(guān)鍵字對記錄進(jìn)行初步排序；在此基

15、礎(chǔ)上，再按次低位關(guān)鍵字進(jìn)一步排序，以此類推，由低位到高位，由此關(guān)鍵字到主關(guān)鍵字，每一趟排序都在前一趟排序的基礎(chǔ)上，直到按最高位關(guān)鍵對記錄進(jìn)行排序后，基數(shù)排序完成。</p><p>　　在基數(shù)排序中，基數(shù)是各個(gè)關(guān)鍵只的取值范圍。若待排序的記錄是十進(jìn)制，則基數(shù)是10；若待排序的記錄是由若干個(gè)字母組成的單詞，則基數(shù)為26，也就是說，從最右邊的字母開始對記錄進(jìn)行排序，每次排序都將待排序記錄分成26組，但在此問題中，車牌號

16、是由漢字，字母以及數(shù)字組成，若直接進(jìn)行排序，則需要分成34組，為了提高算法的空間性能，可以將漢字及字母轉(zhuǎn)換為十進(jìn)制數(shù)后再進(jìn)行基數(shù)排序。</p><p>　　例如：一組記錄的關(guān)鍵字為：（278，109，63，930，589，184，505，269，8，83）</p><p>　　可以看出，這組關(guān)鍵字與以前說過的用來排序的關(guān)鍵字并無差別，且也是針對但關(guān)鍵字對一組記錄進(jìn)行排序。但在基數(shù)排序中，我

17、們可以將單關(guān)鍵字看成由若干個(gè)關(guān)鍵字復(fù)合而成。</p><p>　　上述這組關(guān)鍵字的值都在0~999的范圍內(nèi)，我們可以把一個(gè)數(shù)位上的十進(jìn)制數(shù)字看成是一個(gè)關(guān)鍵字，即將關(guān)鍵字K看成由3個(gè)關(guān)鍵K0，K1，K2組成。其中，K0是百位上的數(shù)字，K1是十位上的數(shù)字，K2是個(gè)位上的數(shù)字。</p><p>　　因?yàn)槭M(jìn)制的基數(shù)是10，所以，每個(gè)蘇偉山的數(shù)字都可能是0~9中的任何一個(gè)。我們先將關(guān)鍵字K2來分配

18、所有參與排序的元素，將K2=0的元素防在一組、K2=1的元素放在一組、 ……、K2=9的元素放在一組。這樣，將上述一組元素分成10組，如下（a）圖所示。然后，再將K2的值由0到9的順序收集各組元素，形成序列（930，063，083，184，505，278，008，109，589，269）。</p><p>　　對上述序列中的元素再按關(guān)鍵字K1來分配，也分成10組，如下（b）圖所示。然后，再按K1的值由0到9的順序

19、收集各組元素，形成序列（505，008，109，930，063，269，278，083，184，589）。</p><p>　　對該序列中的元素再按關(guān)鍵字K0來分配，分成如下（c）圖所示的10組。然后按K0的值由0~9的順序收集各組元素，形成序列（008，063，083，109，184，267，278，505，589，930）。這時(shí)，該序列已經(jīng)變成了一個(gè)有序序列。</p><p>　　一趟

20、分配前的一組元素（008，063，083，109，184，267，278，505，589，930）</p><p><b>　　269</b></p><p>　　083 008 589</p><p>　　930 063

21、 184 505 278 109</p><p>　　k2=0 k2=1 k2=2 k2=3 k2=4 k2=5 k2=6 k2=7 k2=8 k2=9</p><p>　?。╝）、按個(gè)位數(shù)大小將元素分成10組</p><p>　　一趟分

22、配后的一組元素（930，063，083，184，505，278，008，109，589，269）</p><p>　　109 589 </p><p>　　008 269

23、 184 </p><p>　　505 930 063 278 083</p><p>　　K1=0 k1=1 k1=2 k1=3 k1=4 k1=5 k1=6 k1=7 k1=8 k1=9 </p>&l

24、t;p>　?。╞）、按十位數(shù)大小將元素分成10組</p><p>　　二趟收集后的元素序列（505，008，109，930，063，269，278，083，184，589）</p><p>　　083 </p><p>

25、　　063 184 278 589 </p><p>　　008 109 269 505 930</p><p>　　K0=0 k0=1 k0=2

26、k0=3 k0=4 k0=5 k0=6 k0=7 k0=8 k0=9</p><p>　?。╟）、按百位數(shù)大小將元素分成10組</p><p>　　三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930）</p><p>　　3、鏈?zhǔn)交鶖?shù)排序算法實(shí)現(xiàn)的技術(shù)要點(diǎn)：</p&

27、gt;<p>　　要實(shí)現(xiàn)上述基數(shù)排序的過程，需要解決3個(gè)問題。</p><p>　　問題一：如何描述由待排序關(guān)鍵字分成的若干個(gè)子關(guān)鍵字？</p><p>　　問題二：每次分配記錄所形成的各組序列以何種結(jié)構(gòu)存儲？</p><p>　　問題三：如何收集各組記錄？</p><p>　　其實(shí)，當(dāng)問題三得以解決后，問題二也就解決了；因?yàn)閱?/p>

28、題三運(yùn)算方式?jīng)Q定了問題二的存儲結(jié)構(gòu)。</p><p>　　由上例可以看出，各組記錄的收集是本著“先進(jìn)入該組的記錄將首先被收集”的原則。這與隊(duì)列的“先進(jìn)先出”的原則相一致。這樣，各組序列就以隊(duì)列來描述。 </p><p>　　因?yàn)橐M(jìn)行多次的分配與收集，為節(jié)省存儲空間及運(yùn)算方便，我們采用鏈隊(duì)列來存儲各組序列。</p><p>　　其實(shí)，當(dāng)問題三得以解決后，問題二也

29、就解決了；因?yàn)閱栴}三運(yùn)算方式?jīng)Q定了問題二的存儲結(jié)構(gòu)。</p><p>　　鏈隊(duì)列的數(shù)量與基數(shù)一致，若基數(shù)為RAX，則令f[0]～f[RAX-1]分別指向RAX個(gè)鏈隊(duì)列的隊(duì)頭節(jié)點(diǎn)，令r[0]～r[RAX-1]分別指向RAX個(gè)隊(duì)列的隊(duì)尾節(jié)點(diǎn)。每次分配前，將RAX個(gè)鏈隊(duì)列置空：</p><p>　　for(i=0i<=RAX-1++i)</p><p>　　f[i

30、=r[i]=NULL； </p><p>　　對各鏈隊(duì)列所表示的序列進(jìn)行收集時(shí)，應(yīng)從鏈隊(duì)列f[0]開始，當(dāng)鏈隊(duì)列f[j+1]不為NULL時(shí)，將鏈隊(duì)列f[j]與其首尾相接：</p><p><b>　　i=0；</b></p><p>　　while(f[i]==NULL) </p><p>　　i++； //查找第一個(gè)

31、不空的鏈隊(duì)列</p><p>　　for(j=i，k=i+1；k<= RAX-1；++k)</p><p>　　if( f[k]!= NULL)</p><p>　　{ r[j]->next = f[k]；j=k；} </p><p>　　對于問題一，一個(gè)簡單的方法是，在存儲待排序記錄時(shí)，就將關(guān)鍵字按分成子關(guān)鍵字來存儲。為了運(yùn)算

32、方便，我們采用與鏈隊(duì)列中節(jié)點(diǎn)一致的節(jié)點(diǎn)結(jié)構(gòu)，以單鏈表來存儲待排序的一組記錄及收集后的記錄序列。節(jié)點(diǎn)的類型可以定義為：</p><p>　　#define M 3 //M為待排記錄中子關(guān)鍵字的個(gè)數(shù)</p><p>　　typedef struct node{</p><p>　　keytype key[M]；</p><p>　　st

33、ruct node *next；</p><p><b>　　} Rnode；</b></p><p>　　若關(guān)鍵字為整型數(shù)據(jù)，則存放待排序記錄的單鏈表可以這樣構(gòu)造：</p><p>　　#define N 8 //N為待排記錄的個(gè)數(shù)</p><p>　　Rnode *L，*p；</p>&

34、lt;p>　　L = NULL； //鏈表L初始化為空</p><p>　　for(i = 1；i<=N；++i){ //頭插法建單鏈表L</p><p>　　p = malloc(sizeof(Rnode))；</p><p>　　for (j = 0；j<= M-1；++j) //分別輸入M個(gè)子關(guān)鍵字</p><p&

35、gt;　　scanf(“%d”，&(p->key[j]))；</p><p>　　p->next = L；L = p；</p><p><b>　　} </b></p><p>　　綜上所述，以鏈表來存儲待排序記錄，基數(shù)排序算法如下：</p><p>　　#define M 3 //M為待排記

36、錄中子關(guān)鍵字的個(gè)數(shù)</p><p>　　#define RAX 10 // RAX為基數(shù)</p><p>　　typedef struct node{</p><p>　　keytype key[M]；</p><p>　　struct node *next；</p><p><b>　　}Rno

37、de；</b></p><p>　　Rnode *f[RAX]，*r[RAX]；</p><p>　　Rnode *SetList(){ //建待排序記錄組成的單鏈表L</p><p>　　Rnode *L，*p；</p><p><b>　　int i，j；</b></p><p>

38、;　　L=NULL； //鏈表L初始化為空</p><p>　　for (i=1；i<=n；++i){ </p><p>　　//頭插法建單鏈表L，n為待排序記錄個(gè)數(shù) </p><p>　　p=(Rnode *)malloc(sizeof(Rnode))；</p><p>　　for (j=0；j<=M-1；++j)

39、//分別輸入M個(gè)子關(guān)鍵字</p><p>　　scanf("%d"，&(p->key[j]))；</p><p>　　p->next=L；L=p；</p><p><b>　　}</b></p><p><b>　　return L；</b></p>

40、;<p><b>　　}</b></p><p>　　void Distribute(Rnode *L，int i){ </p><p>　　//掃描鏈表L，按第i個(gè)關(guān)鍵字將各記錄分配到相應(yīng)的鏈隊(duì)列中 </p><p>　　Rnode *p；int i，j；</p><p>　　for (i = 0；i&l

41、t;=RAX-1；++i)//將RAX個(gè)鏈隊(duì)列初始化為空</p><p>　　f[i] = r[i] = NULL；</p><p><b>　　p = L；</b></p><p>　　while(p!=NULL){</p><p>　　L = L->next；</p><p>　　j

42、= p->key[i]；//用記錄中第i位關(guān)鍵字的值即為相應(yīng)的隊(duì)列號 </p><p>　　if(f[j] = = NULL) </p><p>　　f[j] = p； //將節(jié)點(diǎn)*p分配到相應(yīng)的鏈隊(duì)列中f[j] </p><p>　　else r[j]->next = p；</p><p>　　r[j] = p；r[j]-&g

43、t;next = NULL；</p><p><b>　　p = L；</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　Rnode *Collect(){ </p><p>　　//從鏈隊(duì)列f[

44、0]開始，依次收集各鏈隊(duì)列中的節(jié)點(diǎn)</p><p><b>　　Rnode *L；</b></p><p>　　int i = 0，j；</p><p>　　while(f[i]= =NULL) i++； //查找第一個(gè)不空的鏈隊(duì)列</p><p><b>　　L=f[i]；</b></p&g

45、t;<p>　　for (j=i，k=i+1；k<=RAX-1；++k)</p><p>　　if(f[k]!=NULL){ r[j]->next=f[k]；j = k；}</p><p><b>　　return L；</b></p><p><b>　　}</b></p>&l

46、t;p>　　Rnode *RadixSort(int n){ //對n個(gè)記錄進(jìn)行基數(shù)排序</p><p><b>　　Rnode *L；</b></p><p>　　L=SetList()；//建待排序記錄組成的單鏈表L</p><p>　　for (i=M-1；i>=0；--i){ </p><p&g

47、t;　　//分別按M個(gè)子關(guān)鍵字對待排序列進(jìn)行分配和收集</p><p>　　Distribute(L，i)；L=Collect()；</p><p><b>　　}</b></p><p><b>　　return L；</b></p><p><b>　　} </b><

48、/p><p>　　從算法中容易看出，對于ｎ個(gè)記錄（每個(gè)記錄含M個(gè)子關(guān)鍵字， 每個(gè)子關(guān)鍵字的取值范圍為RAX個(gè)值）進(jìn)行鏈?zhǔn)脚判虻臅r(shí)間復(fù)雜度為Ｏ(M(ｎ+RAX))，其中每一趟分配算法的時(shí)間復(fù)雜度為Ｏ(ｎ)，每一趟收集算法的時(shí)間復(fù)雜度為Ｏ(RAX)，整個(gè)排序進(jìn)行M趟分配和收集，所需輔助空間為２×RAX個(gè)隊(duì)列指針。當(dāng)然，由于需要鏈表作為存儲結(jié)構(gòu)， 則相對于其它以順序結(jié)構(gòu)存儲記錄的排序方法而言， 還增加了ｎ個(gè)指針域

49、空間。 </p><p>　　4、對于此題目，車牌號是由漢字，字母和數(shù)字組成，而輸入的時(shí)候是以字符的形式接收的，首先應(yīng)該在鏈表的各個(gè)結(jié)點(diǎn)中申請一個(gè)整型數(shù)組用于存儲將漢字和字母轉(zhuǎn)換為整型數(shù)據(jù)的數(shù)字，以便基數(shù)排序的順利進(jìn)行。</p><p>　　針對此題目具體代碼段為：Rnode *insort(Rnode *p){</p><p><b>　　Rnode

50、*q;</b></p><p><b>　　int a=0;</b></p><p>　　for(int i=M-1;i>=0;i--){</p><p>　　Distribute(p,i);</p><p>　　q=p=Collect();</p><p><b>　

51、　}</b></p><p>　　cout<<"排序已完成!"<<endl;</p><p>　　while(q!=NULL){</p><p>　　A[a]=q->keynum[0]*100000000+q->keynum[1]*10000000+q->keynum[2]*1000000+

52、q->keynum[3]*100000+q->keynum[4]*10000+q->keynum[5]*1000+q->keynum[6]*100+q->keynum[7]*10+q->keynum[8];</p><p>　　q=q->next;</p><p><b>　　b=a;</b></p><p

53、><b>　　a++;</b></p><p><b>　　}</b></p><p><b>　　flag=0;</b></p><p><b>　　return p;</b></p><p><b>　　}</b></

54、p><p>　　void Distribute(Rnode *L,int j){</p><p><b>　　Rnode *p;</b></p><p>　　int i,k=0;</p><p>　　for(i=0;i<=RAX-1;i++)</p><p>　　f[i]=r[i]=NULL;&

55、lt;/p><p><b>　　p=L;</b></p><p>　　while(p!=NULL){</p><p>　　L=L->next;</p><p>　　k=p->keynum[j];</p><p>　　if(f[k]==NULL)</p><p>&l

56、t;b>　　f[k]=p;</b></p><p><b>　　else</b></p><p>　　r[k]->next=p;//隊(duì)尾指針向后移動(dòng)一位</p><p><b>　　r[k]=p;</b></p><p>　　r[k]->next=NULL;</p

57、><p><b>　　p=L;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　Rnode *Collect(){//每一趟的收集函數(shù)</p><p><b>　　Rnode *L;<

58、;/b></p><p>　　int i=0,j,k;</p><p>　　while(f[i]==NULL)</p><p><b>　　i++;</b></p><p><b>　　L=f[i];</b></p><p>　　for(j=i,k=i+1;k<=

59、RAX-1;k++)</p><p>　　if(f[k]!=NULL){</p><p>　　r[j]->next=f[k];</p><p><b>　　j=k;</b></p><p><b>　　}</b></p><p><b>　　return L;

60、</b></p><p><b>　　}</b></p><p>　　5、二分查找的算法思想：</p><p>　?。?）、將表中間位置記錄的關(guān)鍵字與給定K值比較，如果兩者相等，則查找成功。</p><p>　?。?）、如果兩者不等，利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于給定K值

61、，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后后一子表。</p><p>　?。?）、重復(fù)以上過程，直到找到滿足條件的記錄，則查找成功，或者直到分解出的子表不存在為止，此時(shí)查找不成功。</p><p>　　例如對一有序的數(shù)組a（1，2 ，3，4，5，6，7，8，9）進(jìn)行查找數(shù)key=6；</p><p>　　首先定義low=0，high=8，mid=（low+high）/

62、2=4；</p><p>　　第一步：將a[mid]與key比較，我們發(fā)現(xiàn)a [mid]<key，令low=mid+1=5；mid=（low+high）/2=6；</p><p>　　第二步：將a[mid]與key比較，我們發(fā)現(xiàn)a [mid]>key，此時(shí)再令high=mid-1=5；mid=（low+high）/2=5；</p><p>　　第三步：將

63、a[mid]與key比較，此時(shí)a[mid]=key，查找結(jié)束，返回mid；</p><p>　　第四步：如果仍未找到，則繼續(xù)進(jìn)行，直到low>high，此時(shí)返回-1，查找失??；</p><p>　　6、對于該程序最嚴(yán)重的問題就是如何對鏈表進(jìn)行二分查找，經(jīng)過查找資料以及大量的思考，這種想法對于我的能力來說幾乎不可能，最后我使用這樣一種思路，在每次的基數(shù)排序后就將鏈表中每個(gè)結(jié)點(diǎn)的車牌號關(guān)

64、鍵字存于一個(gè)全局一維長整型數(shù)組中，并記錄數(shù)組中最后一個(gè)元素的下標(biāo)。這樣再進(jìn)行二分查找就可以實(shí)現(xiàn)了。</p><p>　　該部分的具體代碼為：</p><p>　　int BinSrch(Rnode *q,long int k,int low,int high){</p><p><b>　　int mid;</b></p><

65、;p>　　if(low>high)</p><p>　　return -1;</p><p><b>　　else{</b></p><p>　　mid=(high+low)/2;</p><p>　　if(A[mid]==k)</p><p>　　return mid;</p&

66、gt;<p>　　else if(k<A[mid])</p><p>　　return (BinSrch(q,k,low,mid-1));</p><p><b>　　else</b></p><p>　　return (BinSrch(q,k,mid+1,high));</p><p><b&

67、gt;　　}</b></p><p><b>　　}</b></p><p>　　void find(Rnode *q)</p><p><b>　　{</b></p><p><b>　　Rnode *p;</b></p><p><

68、b>　　p=q;</b></p><p>　　int k,m,c,g;</p><p>　　char d[8];</p><p>　　long int s;</p><p>　　cout<<"==歡迎來到車輛牌照查詢系統(tǒng)=="<<endl;</p><p>

69、　　cout<<"==請注意車輛的牌照號是由一個(gè)漢字，一個(gè)大寫字母和五個(gè)數(shù)字組成!"<<endl;</p><p>　　cout<<"請輸入您要查找的車輛的汽車牌照:"<<endl;</p><p><b>　　cin>>d;</b></p><p&

70、gt;　　string key1=(string)d;</p><p>　　string key2=key1.substr(0,2);</p><p>　　for(g=0;g<=0;g++){</p><p>　　for(int j=0;j<N;j++){</p><p>　　string key3=(string)provinc

71、e[j];</p><p>　　if(key2==key3)</p><p><b>　　k=j;</b></p><p><b>　　}</b></p><p>　　if(k>33||k<0){</p><p>　　cout<<"對不起,您

72、輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　s=k/10*100000000+k%10*10000000;</p><p>　　for(int h=0;h<

73、K;h++){</p><p>　　if(d[2]==word[h])</p><p><b>　　m=h;</b></p><p><b>　　}</b></p><p>　　if(m>25||m<0){</p><p>　　cout<<"

74、對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p>　　s=s+m/10*1000000+m%10*100000;</p><p>　　s=s+((long int

75、)d[3]-48)*10000+((int)d[4]-48)*1000+((int)d[5]-48)*100+((int)d[6]-48)*10+(int)d[7]-48;</p><p>　　c=BinSrch(q,s,0,b);</p><p><b>　　if(-1==c)</b></p><p>　　cout<<"

76、==對不起,沒有找到您要查找的車輛信息,請重新輸入!"<<endl<<endl;</p><p><b>　　else{</b></p><p>　　cout<<"==查找成功,該車的詳細(xì)信息為:"<<endl;</p><p>　　cout<<"

77、;車牌號碼"<<"\t"<<"車主姓名"<<"\t"<<"車輛品牌"<<endl;</p><p>　　for(int i=0;i<c;i++){</p><p>　　q=q->next;</p><p>

78、<b>　　}</b></p><p>　　cout<<q->key<<"\t"<<q->name<<"\t\t"<<q->oem<<endl;</p><p><b>　　}</b></p><p

79、><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　四、上機(jī)調(diào)試</b></p><p>　　1、語法錯(cuò)誤及修改：由于本算法使用了鏈?zhǔn)交鶖?shù)排序和二分查找，所以程序相對來說得到

80、了很大的簡化，整體思路比較清晰，易于理解。程序中同時(shí)也出現(xiàn)了一下簡單的語法錯(cuò)誤，比如子函數(shù)和變量的定義，括號的配對，關(guān)鍵字以及函數(shù)名稱的書寫，不過這些錯(cuò)誤均可以通過編譯器的警告提示來進(jìn)行修改。</p><p>　　2、在實(shí)現(xiàn)車輛信息查找時(shí)，如果在查找前并沒有進(jìn)行排序，但此時(shí)的系統(tǒng)仍可進(jìn)行查找，但是會顯示沒有查找到要查找的信息，這與實(shí)際相違背，經(jīng)過不斷的修改和調(diào)試后，設(shè)想如果在程序中加一全局變量flag并同時(shí)賦值為

81、0，在添加和排序的子函數(shù)中對其進(jìn)行操作，若添加了車輛就將flag重新賦值為1，若程序調(diào)用排序函數(shù)就將flag賦值為0；最后在查找函數(shù)中加入一條判斷語句，若flag=0，則可進(jìn)行二分查找。若不等于，則直接跳出查找子程序，提示用戶重新選擇。</p><p>　　3、在程序調(diào)試過程中發(fā)現(xiàn)若輸入的車輛牌照有皖K12345，在查找此車牌號時(shí)顯示沒有您要查找的記錄，經(jīng)過分析和向老師咨詢發(fā)現(xiàn)輸入要查找的車牌號是存儲在一個(gè)一維字

82、符數(shù)組中的，例如char a=‘3’，使用強(qiáng)制類型轉(zhuǎn)換int b=（int）a，得到的b是等于51的。這是因?yàn)橐粋€(gè)數(shù)字以字符形式存儲和以整型數(shù)據(jù)存儲它們的ASCII碼是不同的。只要將上述的強(qiáng)制類型轉(zhuǎn)換語句改為int b=（int）a-48即可得到正確的結(jié)果，此問題便可以解決。</p><p>　　五、測試結(jié)果及其分析</p><p>　　圖1 菜單顯示頁面</p><

83、p>　　圖2 添加車輛信息</p><p>　　圖3 輸出用戶添加車輛信息完成后的所有車輛信息，這些信息的顯示是按照用戶從文件讀取的順序顯示的。</p><p>　　圖4 對車輛信息按照車牌號號碼進(jìn)行排序，并輸出排序后的結(jié)果。</p><p>　　圖5 對車輛信息排序后進(jìn)行查找，若查找成功，則顯示車輛信息</p><p>　　

84、圖6 對車輛信息排序后進(jìn)行查找，若未能查找到則顯示未能查找到該車輛信息。</p><p><b>　　六、用戶使用說明</b></p><p>　　本程序是以菜單的形式來提示用戶進(jìn)行相應(yīng)的操作，在添加車輛的信息時(shí)，牌照號是由一個(gè)漢字，一個(gè)大寫字母和五個(gè)數(shù)字組成。牌照中的第一個(gè)漢字是全國34個(gè)省市自治區(qū)的簡稱，若輸入錯(cuò)誤，程序會提示出錯(cuò)并請用戶重新選擇輸入。其中輸入的

85、各項(xiàng)信息的長度不能大于預(yù)先定義的字節(jié)數(shù)。在沒有經(jīng)過排序而選擇輸出所有車輛的信息時(shí)是按預(yù)先添加的順序來輸出的。在按車牌號碼進(jìn)行查找所需車輛信息時(shí)應(yīng)先對車輛的信息按車牌號碼進(jìn)行排序。在經(jīng)過排序后，用戶若想再添加新的車輛信息，應(yīng)再進(jìn)行一次排序后方能進(jìn)行查找，否則程序會提示未進(jìn)行排序。用戶推出程序時(shí)，可選擇0推出。</p><p><b>　　七、參考文獻(xiàn)</b></p><p&

86、gt;　　［1］王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京:中國鐵道出版社,2007年.</p><p>　?。?］譚浩強(qiáng)等編著. C程序設(shè)計(jì)（第三版）. 北京:清華大學(xué)出版社,2005年.</p><p>　?。?］嚴(yán)蔚敏,陳文博編著. 數(shù)據(jù)結(jié)構(gòu)及算法教程. 北京: 清華大學(xué)出版社,2001年.</p><p><b>　　八、附錄</b>

87、;</p><p>　　#include "iostream"</p><p>　　#include "fstream"</p><p>　　#include "stdlib.h"</p><p>　　#include "malloc.h"</p>

88、<p>　　#include "string"</p><p>　　using namespace std;</p><p>　　#define M 9 //關(guān)鍵字的個(gè)數(shù)</p><p>　　#define N 34 //省市自治區(qū)的個(gè)數(shù)</p><p>　　#defin

89、e K 26 //大寫字母的個(gè)數(shù)</p><p>　　#define RAX 10 //基數(shù)的個(gè)數(shù)</p><p>　　#define MAX 100 //最大能夠處理的車輛數(shù)</p><p>　　typedef struct node{</p><p>　　int keynum[M];<

90、;/p><p>　　char key[10];</p><p>　　char name[10];</p><p>　　char paizi[10];</p><p>　　struct node *next;</p><p><b>　　}Rnode;</b></p><p>　

91、　string name1[N]={"澳","川","鄂","甘","贛","港","貴","桂","黑","滬","吉","津","晉","京","

92、遼","魯","閩","內(nèi)","寧","青","瓊","山","陜","蘇","臺","皖","湘","新","冀","渝",&q

93、uot;豫","云","藏","浙"};</p><p>　　char name2[K]={'A','B','C','D','E','F','G','H','I','J','K&

94、#39;,'L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};</p><p>　　Rnode *f[RA

95、X],*r[RAX]; //*f[RAX],*r[RAX]分別為鏈隊(duì)列的隊(duì)頭指針和隊(duì)尾指針</p><p>　　long int A[MAX];</p><p>　　int flag=0; //記錄在查找前是否進(jìn)行了排序</p><p>　　int b; //汽車牌照轉(zhuǎn)

96、換為數(shù)字后最后一個(gè)汽車牌照的數(shù)組中的下標(biāo)</p><p>　　Rnode *SetList(){</p><p><b>　　FILE *f1;</b></p><p>　　Rnode *head,*p,*l;</p><p>　　int m,j,k;</p><p><b>　　str

97、ing r;</b></p><p>　　if((f1=fopen("汽車管理.txt","r"))==NULL)</p><p>　　printf("不能打開文件!");</p><p>　　head=NULL;</p><p>　　p=(Rnode *)malloc

98、(sizeof(Rnode));</p><p>　　p->next=NULL;</p><p>　　while(fscanf(f1,"%s%s%s",p->key ,p->name ,p->paizi)!=EOF){ //頭插法建鏈表</p><p>　　if(head==NULL) {</p>&l

99、t;p>　　l=head=p;}</p><p><b>　　else{</b></p><p>　　l->next=p;</p><p><b>　　l=p;}</b></p><p>　　p=(Rnode *)malloc(sizeof(Rnode));</p><

100、;p>　　p->next=NULL;</p><p><b>　　}</b></p><p><b>　　p=head;</b></p><p>　　while(p!=NULL){</p><p>　　string key1=(string)p->key;</p>&

101、lt;p>　　string key2=key1.substr(0,2);</p><p>　　for(j=0;j<N;j++){</p><p>　　string key3=(string)name1[j];</p><p>　　if(key2==key3)</p><p><b>　　k=j; }</b>

102、</p><p>　　if(k>33||k<0){</p><p>　　cout<<"==您輸入的車牌號碼錯(cuò)誤,請重新選擇輸入!"<<endl;</p><p><b>　　break; }</b></p><p>　　int s=k/10;</p>

103、<p>　　p->keynum[0]=s;</p><p><b>　　s=k%10;</b></p><p>　　p->keynum[1]=s;</p><p>　　for(int h=0;h<K;h++){</p><p>　　if(p->key[2]==name2[h])</

104、p><p><b>　　m=h;}</b></p><p>　　if(m>25||m<0){</p><p>　　cout<<"==您輸入的車牌號碼錯(cuò)誤,請重新選擇輸入!"<<endl;</p><p><b>　　break;}</b><

105、/p><p><b>　　s=m/10;</b></p><p>　　p->keynum[2]=s;</p><p><b>　　s=m%10;</b></p><p>　　p->keynum[3]=s;</p><p>　　for(int n=3;n<M-1;

106、n++){</p><p>　　int c=(int)p->key[n]-48;</p><p>　　p->keynum[n+1]=c; }</p><p>　　p=p->next; }</p><p><b>　　flag=1;}</b></p><p>　　return h

107、ead;</p><p><b>　　}</b></p><p>　　void Distribute(Rnode *q,int j){</p><p><b>　　Rnode *p;</b></p><p>　　int i,k=0;</p><p>　　for(i=0;i&l

108、t;=RAX-1;i++)</p><p>　　f[i]=r[i]=NULL;</p><p><b>　　p=q;</b></p><p>　　while(p!=NULL){</p><p>　　q=q->next;</p><p>　　k=p->keynum[j];</p&g

109、t;<p>　　if(f[k]==NULL)</p><p><b>　　f[k]=p;</b></p><p><b>　　else</b></p><p>　　r[k]->next=p; //隊(duì)尾指針向后移動(dòng)一位</p><p><b>　　r[k

110、]=p;</b></p><p>　　r[k]->next=NULL;</p><p><b>　　p=q; }</b></p><p><b>　　}</b></p><p>　　Rnode *Collect(){</p><p><b>　　R

111、node *L;</b></p><p>　　int i=0,j,k;</p><p>　　while(f[i]==NULL)</p><p><b>　　i++;</b></p><p><b>　　L=f[i];</b></p><p>　　for(j=i,k

112、=i+1;k<=RAX-1;k++)</p><p>　　if(f[k]!=NULL){</p><p>　　r[j]->next=f[k];</p><p><b>　　j=k; }</b></p><p>　　return L; }</p><p>　　int BinSrch(Rn

113、ode *q,long int k,int low,int high){ //遞歸調(diào)用折半查找</p><p><b>　　int mid;</b></p><p>　　if(low>high)</p><p>　　return -1;</p><p><b>　　else{</b><

114、;/p><p>　　mid=(high+low)/2;</p><p>　　if(A[mid]==k)</p><p>　　return mid;</p><p>　　else if(k<A[mid])</p><p>　　return (BinSrch(q,k,low,mid-1));</p><

115、;p><b>　　else</b></p><p>　　return (BinSrch(q,k,mid+1,high)); }</p><p><b>　　}</b></p><p>　　void find(Rnode *q){</p><p><b>　　Rnode *p;<

116、/b></p><p><b>　　p=q;</b></p><p>　　int k,m,c;</p><p>　　char d[8];</p><p>　　long int s;</p><p>　　cout<<"請輸入您要查找的車輛的汽車牌照:"<&

117、lt;endl;</p><p><b>　　cin>>d;</b></p><p>　　string key1=(string)d;</p><p>　　string key2=key1.substr(0,2);</p><p>　　for(int j=0;j<N;j++){</p>&

118、lt;p>　　string key3=(string)name1[j];</p><p>　　if(key2==key3)</p><p><b>　　k=j;}</b></p><p>　　if(k>33||k<0)</p><p>　　cout<<"對不起,您輸入的車牌號不合法

119、,請重新輸入!"<<endl;</p><p>　　s=k/10*100000000+k%10*10000000;</p><p>　　for(int h=0;h<K;h++){</p><p>　　if(d[2]==name2[h])</p><p><b>　　m=h; }</b><

120、/p><p>　　if(m>25||m<0)</p><p>　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p>　　s=s+m/10*1000000+m%10*100000;</p><p>　　s=s+((long int)d[3]-48)*10

121、000+((int)d[4]-48)*1000+((int)d[5]-48)*100+((int)d[6]-48)*10+(int)d[7]-48;</p><p>　　c=BinSrch(q,s,0,b);</p><p><b>　　if(-1==c)</b></p><p>　　cout<<"==對不起,沒有找到您要

122、查找的車輛信息,請重新輸入!"<<endl<<endl;</p><p><b>　　else{</b></p><p>　　cout<<"\t\t"<<"車牌號碼"<<"\t"<<"車主姓名"<<

123、;"\t"<<"車牌"<<endl;</p><p>　　for(int i=0;i<c;i++){</p><p>　　q=q->next; }</p><p>　　cout<<"\t\t"<<q->key<<"\t&

124、quot;<<q->name<<"\t\t"<<p->paizi<<endl; }</p><p>　　cout<<endl;</p><p><b>　　}</b></p><p>　　void print(Rnode *p){</p>

125、<p>　　cout<<"==所有車輛的信息如下:"<<endl<<endl;</p><p>　　cout<<"車牌照號"<<"\t"<<"車主姓名"<<"\t"<<"車牌"<&l

126、t;endl;</p><p>　　while(p!=NULL) {</p><p>　　cout<<p->key<<"\t"<<p->name<<"\t\t"<<p->paizi<<endl;</p><p>　　p=p->nex

127、t; }</p><p>　　cout<<endl; }</p><p>　　Rnode *paixu(Rnode *p){</p><p><b>　　Rnode *q;</b></p><p><b>　　int a=0;</b></p><p>　　for

128、(int i=M-1;i>=0;i--){</p><p>　　Distribute(p,i);</p><p>　　q=p=Collect();}</p><p>　　cout<<"==完成對車輛信息的排序!"<<endl;</p><p>　　while(q!=NULL){</p&

129、gt;<p>　　A[a]=q->keynum[0]*100000000+q->keynum[1]*10000000+q->keynum[2]*1000000+q->keynum[3]*100000+q->keynum[4]*10000+q->keynum[5]*1000+q->keynum[6]*100+q->keynum[7]*10+q->keynum[8];<

130、;/p><p>　　q=q->next;</p><p><b>　　b=a;</b></p><p><b>　　a++;}</b></p><p><b>　　flag=0;</b></p><p>　　return p; }</p>

131、<p>　　void menu()</p><p><b>　　{</b></p><p>　　cout<<"\t\t\t┏━┳━━━━━━━━━━━━━━┳━┓"<<endl;</p><p>　　cout<<"\t\t\t┣━┫　 車輛信息管理系統(tǒng)　

132、┣━┫"<<endl;</p><p>　　cout<<"\t\t\t┣━┻━━━━━━━━━━━━━━┻━┫"<<endl;</p><p>　　cout<<"\t\t\t┃ 1) 添加車輛信息 ┃"<<endl;</p>&l

133、t;p>　　cout<<"\t\t\t┣━━━━━━━━━━━━━━━━━━┫"<<endl; </p><p>　　cout<<"\t\t\t┃ 2) 按車牌號碼進(jìn)行排序 ┃"<<endl;</p><p>　　cout<<"\t\t\t┣━━━

134、━━━━━━━━━━━━━━━┫"<<endl;</p><p>　　cout<<"\t\t\t┃ 3) 按車牌號碼查找車輛 ┃"<<endl;</p><p>　　cout<<"\t\t\t┣━━━━━━━━━━━━━━━━━━┫"<<endl;<

135、/p><p>　　cout<<"\t\t\t┃ 4) 輸出所有車輛信息 ┃"<<endl;</p><p>　　cout<<"\t\t\t┣━━━━━━━━━━━━━━━━━━┫"<<endl;</p><p>　　cout<<"\

136、t\t\t┃ 0) 退出程序 ┃"<<endl;</p><p>　　cout<<"\t\t\t┗━━━━━━━━━━━━━━━━━━┛"<<endl;</p><p><b>　　}</b></p><p>　　void main(

137、){</p><p><b>　　Rnode *p;</b></p><p><b>　　int n;</b></p><p><b>　　menu();</b></p><p>　　cout<<"\t\t\t請您選擇(0～4):";</p