汽車牌照課程設(shè)計(jì)報(bào)告.doc

課程設(shè)計(jì)報(bào)告一. 問(wèn)題的分析與定義題目：汽車拍照的排序與查找問(wèn)題此題目主要要求對(duì)汽車牌照進(jìn)行基數(shù)排序，和用二分查找的思想進(jìn)行查找，這兩種方法思想并不難，但是要對(duì)汽車牌照進(jìn)行排序和查找，此問(wèn)題涉及到的主要問(wèn)題是：首先的問(wèn)題就是，用何種存儲(chǔ)結(jié)構(gòu)對(duì)汽車信息和汽車牌照進(jìn)行存儲(chǔ)汽車牌照，然后汽車牌照不是單單是數(shù)字，而且是漢字、字母與數(shù)字混合排列的，這就不僅僅對(duì)數(shù)字進(jìn)行基數(shù)排序了，還要對(duì)字母進(jìn)行相關(guān)處理，方可用基數(shù)排序的方法進(jìn)行排序。經(jīng)過(guò)最后查找資料、分析將漢字、字母轉(zhuǎn)化為數(shù)字處理，漢字代表汽車牌照的地區(qū)，共有34個(gè)省市自治區(qū)簡(jiǎn)稱，即34個(gè)漢字，26個(gè)英語(yǔ)大寫字母，分別用數(shù)組存儲(chǔ)這34個(gè)漢字和26個(gè)大寫字母，將他們轉(zhuǎn)化為數(shù)字，最后再用基數(shù)排序，方可達(dá)到題目要求。在二分查找問(wèn)題中，是對(duì)汽車牌進(jìn)行查找，首先將要查找的汽車牌轉(zhuǎn)換為數(shù)字形式，再用二分查找遞歸算法，找不到返回一個(gè)值，找到再返回一個(gè)值，再找到這個(gè)位置，輸出查找的所有信息，即可達(dá)到題目要求。二數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計(jì)1.數(shù)據(jù)結(jié)構(gòu)的選擇 對(duì)于汽車牌照進(jìn)行排序和查找，為了使程序盡可能的實(shí)用性，我將定義，車主，車牌號(hào)，車色，車型為一個(gè)結(jié)構(gòu)類型，用鏈表的形式存儲(chǔ)這些信息，為了方便對(duì)汽車牌照進(jìn)行排序，在定義一個(gè)數(shù)組存儲(chǔ)將漢字、字母轉(zhuǎn)化后的長(zhǎng)數(shù)據(jù)類型，漢字和字母都用兩個(gè)字符來(lái)表示。在基數(shù)排序中，基數(shù)排序每趟的收集由兩個(gè)鏈隊(duì)列收集，鏈隊(duì)列的個(gè)數(shù)為基數(shù)的個(gè)數(shù)。在二分查找中，是對(duì)汽車牌號(hào)進(jìn)行查找，首先將汽車牌號(hào)轉(zhuǎn)化為數(shù)字，再用遞歸算法查找。最后再將所有車輛信息輸出，達(dá)到題目要求。2.概要設(shè)計(jì)為了實(shí)現(xiàn)上述功能，需要的函數(shù)及其功能如下：1).主函數(shù)main()2)車輛信息錄入函數(shù)Setlist()3)基數(shù)每一趟的分配函數(shù)Distribute()4)基數(shù)每一趟的收集函數(shù)Collect()5)基數(shù)排序函數(shù)paixu()6)二分查找函數(shù)search()7)輸出函數(shù)print()各函數(shù)關(guān)系如下：mainSetlistpaixusearchprintDistributeCollectTwsearch主函數(shù)流程圖：開始結(jié)束n=1輸入nn=2n=3n=5調(diào)用子函數(shù)SetList(p)調(diào)用子函數(shù)print()調(diào)用子函數(shù)search(p)調(diào)用子函數(shù)paixu(p)n=4YNNYYYYNNNNNNNN三詳細(xì)設(shè)計(jì)和編碼1.汽車節(jié)點(diǎn)類型typedef struct nodeint keynumM; /汽車牌照轉(zhuǎn)換為十進(jìn)制后的數(shù)據(jù)char key10; /汽車牌照號(hào)char color10; /汽車顏色char type10; /汽車類型char name10; /車主姓名struct node *next; /指向下一個(gè)節(jié)點(diǎn)的指針域Rnode;2.基數(shù)排序的過(guò)程 鏈?zhǔn)交鶖?shù)排序就是在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下通過(guò)反復(fù)的分配、收集運(yùn)算來(lái)進(jìn)行排序的。首先將待排序的記錄分成若干個(gè)子關(guān)鍵字，排序時(shí)，先按最低位的關(guān)鍵字對(duì)記錄進(jìn)行初步排序；在此基礎(chǔ)上，再按次低位關(guān)鍵字進(jìn)一步排序，以此類推，由低位到高位，由此關(guān)鍵字到主關(guān)鍵字，每一趟排序都在前一趟排序的基礎(chǔ)上，直到按最高位關(guān)鍵對(duì)記錄進(jìn)行排序后，基數(shù)排序完成。車牌號(hào)是由一個(gè)漢字、一個(gè)大寫字母和五個(gè)數(shù)字組成，由于有34個(gè)省自治區(qū)簡(jiǎn)稱，字母有26個(gè)，本來(lái)基數(shù)應(yīng)該是34，但這樣一來(lái)太麻煩，而且不好分析，故將漢字、字母轉(zhuǎn)換為十進(jìn)制數(shù)再進(jìn)行基數(shù)排序，這樣做的好處是，基數(shù)都是從09，比較簡(jiǎn)便，而且易懂。為了更好的分析此算法，舉一個(gè)例子：一組記錄的關(guān)鍵字為：83，8，184，505，930，589，63，109，278采用基數(shù)排序方法對(duì)其進(jìn)行排序。 上述這組關(guān)鍵字的值都在0K99的范圍內(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ù)字。因?yàn)槭M(jìn)制的基數(shù)是10，所以，每個(gè)數(shù)位上的數(shù)字都可能是09中的任何一個(gè)。先按關(guān)鍵字K2來(lái)分配所有參與排序的元素，將K2=0的元素放在一組、K2=1的元素放在一組、K2=9的元素放在一組。再按K2的值由0到9的順序收集各組元素，形成序列（930，063，083，184，505，278，008，109，589，269）。 對(duì)上述序列中的元素再按關(guān)鍵字K1來(lái)分配，也分成10組。然后再按K1的值由0到9的順序收集各組元素，形成序列（505，008，109，930，063，269，278，083，184，589）。對(duì)該序列中的元素再按關(guān)鍵字K0來(lái)分配。然后按K0的值由0到9的順序收集各組元素，形成序列（008，063，083，109，184，267，278，505，589，930）?；鶖?shù)排序完成。分析該例，可以看出基數(shù)排序的思想是：首先將待排序的記錄分成若干個(gè)子關(guān)鍵字，排序時(shí)，先按最低位的關(guān)鍵字對(duì)記錄進(jìn)行初步排序；在此基礎(chǔ)上，再按次地位關(guān)鍵字進(jìn)一步排序。依次類推，由低位到高位，由次關(guān)鍵字到主關(guān)鍵字，每一趟排序都在前一趟排序的基礎(chǔ)上，直到按最高位關(guān)鍵字對(duì)記錄進(jìn)行排序后，基數(shù)排序完成。因此，在汽車牌照的基數(shù)排序中，首先將汽車牌照的漢字、字母全部轉(zhuǎn)化為十進(jìn)制數(shù)，以便于基數(shù)排序。漢字和字母是由兩個(gè)字符表示，轉(zhuǎn)換好后方可進(jìn)行基數(shù)排序。接下來(lái)就是如何收集各組記錄。從上述例子可看出，各組記錄的收集遵循“先進(jìn)入該組的記錄將先被收集”的原則可知，各組序列以列來(lái)描述較為精確。因?yàn)橐M(jìn)行多次的分配與收集，為節(jié)省存儲(chǔ)空間及運(yùn)算方便，采用鏈隊(duì)列來(lái)存儲(chǔ)各組序列。鏈隊(duì)列的數(shù)量與基數(shù)一致，若基數(shù)為RAX，則令f0fRAX-1分別指向RAX個(gè)鏈隊(duì)列的隊(duì)頭節(jié)點(diǎn)，令r0rRAX-1分別指向RAX個(gè)隊(duì)列的隊(duì)尾節(jié)點(diǎn)。每次分配前，將RAX個(gè)鏈隊(duì)列置空，即for(i=0;iRAX-1;i+)fi=ri=NULL;Rnode *fRAX,*rRAX; /*fRAX,*rRAX分別為鏈隊(duì)列的隊(duì)頭指針和隊(duì)尾指針 long int elementMAX; /數(shù)組存儲(chǔ)轉(zhuǎn)換后的車牌號(hào)主要算法:1).數(shù)據(jù)錄入函數(shù)Rnode *SetList(Rnode *L,int n)Rnode *p;int m,j,k,i;int t=0,count=1; string r; L=NULL;for(i=0;in;i+)cout請(qǐng)輸入第count個(gè)車主的所有信息endl;coutendl;cout車輛的車牌號(hào)是由一個(gè)漢字，一個(gè)大寫字母和五個(gè)數(shù)字組成!endl;coutp-key;string key1=(string)p-key;string key2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(int h=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%10;p-keynum3=s;for(int n=3;nkeyn-48;p-keynumn+1=c; ;count+;p-next=L;L=p;return L;2).基數(shù)排序若關(guān)鍵字為整型數(shù)據(jù)，則存放待排序記錄的單鏈表可以這樣構(gòu)造： #define N 8 /N為待排記錄的個(gè)數(shù) Rnode *L，*p； L = NULL； /鏈表L初始化為空 for(i = 1；i=N；+i) /頭插法建單鏈表L p = malloc(sizeof(Rnode)； for (j = 0；jp-key; p-next = L；L = p； void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;knext;j=p-keynumi; /用記錄中第i位關(guān)鍵字的值即為相應(yīng)的隊(duì)列號(hào)if(fj=NULL) /將結(jié)點(diǎn)*p分配到相應(yīng)的鏈隊(duì)列fi中fj=p;elserj-next=p;/隊(duì)尾指針向后移動(dòng)一位 rj=p; rj-next=NULL;p=L;Rnode *Collect() /從鏈隊(duì)列f0開始，依次收集各鏈隊(duì)列中的節(jié)點(diǎn) Rnode *L； int i = 0，j； while(fi= =NULL) i+； /查找第一個(gè)不空的鏈隊(duì)列 L=fi； for (j=i，k=i+1；knext=fk；j = k； return L；Rnode *paixu(Rnode *L) /排序函數(shù)Rnode *q;int a=0;q=L;for(int i=M-1;i=0;i-)Distribute(L,i);L=Collect();到此基數(shù)排序算法結(jié)束。從算法中容易看出，對(duì)于個(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)然，由于需要鏈表作為存儲(chǔ)結(jié)構(gòu)， 則相對(duì)于其它以順序結(jié)構(gòu)存儲(chǔ)記錄的排序方法而言， 還增加了個(gè)指針域空間。3)二分查找的算法思想當(dāng)汽車牌照號(hào)都轉(zhuǎn)換為數(shù)字形式后，需要用一個(gè)long int elementMAX進(jìn)行存儲(chǔ)，以便進(jìn)行查找。(1.)將表中間位置記錄的關(guān)鍵字與給定K值比較，如果兩者相等，則查找成功。（2）、如果兩者不等，利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于給定K值，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后后一子表。（3）、重復(fù)以上過(guò)程，直到找到滿足條件的記錄，則查找成功，或者直到分解出的子表不存在為止，此時(shí)查找不成功。例如對(duì)一有序的數(shù)組a（1，2 ，3，4，5，6，7，8，9）進(jìn)行查找數(shù)key=6；首先定義low=0，high=8，mid=（low+high）/2=4； 第一步：將amid與key比較，我們發(fā)現(xiàn)a midkey，此時(shí)再令high=mid-1=5；mid=（low+high）/2=5； 第三步：將amid與key比較，此時(shí)amid=key，查找結(jié)束，返回mid； 第四步：如果仍未找到，則繼續(xù)進(jìn)行，直到lowhigh，此時(shí)返回-1，查找失??；對(duì)于該程序最嚴(yán)重的問(wèn)題就是如何對(duì)鏈表進(jìn)行二分查找，經(jīng)過(guò)查找資料以及思考，要想純粹的輸入一個(gè)車牌號(hào)不做相應(yīng)的變換就進(jìn)行查找，這種思路雖然很清晰，但運(yùn)行起來(lái)不太方便，因?yàn)檫@不僅要對(duì)數(shù)字進(jìn)行查找，而且還對(duì)漢字、字母進(jìn)行查找。因此，這種思路不合理。最后，我想到用一個(gè)長(zhǎng)整型的數(shù)組來(lái)存儲(chǔ)變換后的車牌號(hào)，對(duì)這組車牌號(hào)再進(jìn)行相關(guān)查找和相關(guān)操作，最后具體實(shí)現(xiàn)。該部分的具體代碼為：return L;int Twsearch(Rnode *L,long int key,int low,int high) /遞歸二分查找算法int mid;if(lowhigh)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(keyd;string key1=(string)d;string key2=key1.substr(0,2);for(int g=0;g=0;g+)for(int j=0;jN;j+)string key3=(string)a1j;if(key2=key3) k=j;s=k/10*100000000+k%10*10000000;for(int h=0;hK;h+)if(d2=a2h)m=h; s=s+m/10*1000000+m%10*100000;s=s+(long int)d3-48)*10000+(int)d4-48)*1000+(int)d5-48)*100+(int)d6-48)*10+(int)d7-48;int c= BinSrch(p,s,0,b);if(c=-1)cout抱歉,沒(méi)有您要查找的記錄!endlendl;elsecout查找成功,此車的詳細(xì)信息為:endl;cout車主 車牌號(hào) 車色 車型endl;for(int i=0;inext;coutname key color typeendl;coutendl;四上機(jī)調(diào)試剛開始著手做這個(gè)程序的時(shí)候，因?yàn)閷?duì)數(shù)進(jìn)行基數(shù)排序，我還以為很好做，但是要進(jìn)行漢字、字母和數(shù)字混排的數(shù)進(jìn)行基數(shù)排序，不知道該如何進(jìn)行處理，修改多次程序都不能正確滿足要求，最后，通過(guò)查找資料，可以把漢字、字母轉(zhuǎn)換為十進(jìn)制數(shù)在進(jìn)行基數(shù)排序，最后得以實(shí)現(xiàn)。在進(jìn)行基數(shù)排序時(shí)，由于基數(shù)排序算法在書本中有詳細(xì)介紹，因此沒(méi)有出現(xiàn)太大的問(wèn)題。在調(diào)試過(guò)程中若輸入的車輛牌照有皖A(yù)12345，但在查找此車牌號(hào)時(shí)確顯示沒(méi)有您要查找的記錄，經(jīng)過(guò)一步一步的調(diào)試發(fā)現(xiàn)輸入要查找的車牌號(hào)是存儲(chǔ)在一個(gè)一維字符數(shù)組中的，例如char a=3，使用強(qiáng)制類型轉(zhuǎn)換int b=（int）a，得到的b是等于51的。這是因?yàn)橐粋€(gè)數(shù)字以字符形式存儲(chǔ)和以整型數(shù)據(jù)存儲(chǔ)它們的ASCII碼是不同的。只要將上述的強(qiáng)制類型轉(zhuǎn)換語(yǔ)句改為int b=（int）a-48即可得到正確的結(jié)果，此問(wèn)題得以解決。在實(shí)現(xiàn)車輛信息查找時(shí)，如果在查找前并沒(méi)有進(jìn)行排序,不會(huì)輸出結(jié)果的。因此，在進(jìn)行查找時(shí)，先進(jìn)行排序，這樣一來(lái)很麻煩了。經(jīng)過(guò)修改，將排序函數(shù)直接加到查找函數(shù)中，這樣不管怎么樣，都排序了。五測(cè)試結(jié)果及其分析1.添加車輛首先會(huì)提示輸入要添加的車輛數(shù)2.選擇你要執(zhí)行的菜單功能 33.退出六用戶使用說(shuō)明按提示操作，首先將彈出一個(gè)菜單，按提示輸入你要執(zhí)行的菜單功能，選擇1，添加車輛，會(huì)提示添加的車輛數(shù)，再按提示輸入相關(guān)數(shù)據(jù)信息，輸入結(jié)束后，會(huì)提示一行字，flag=0,繼續(xù)操作，否則退出。選擇flag=0，繼續(xù)執(zhí)行菜單功能，選擇2，進(jìn)行排序，選擇3，按車牌號(hào)進(jìn)行查找，選擇4，是輸出所有車輛信息，5退出程序。七參考文獻(xiàn)1.王昆侖、李紅主編. 數(shù)據(jù)結(jié)構(gòu)與算法. 出版地：中國(guó)地道出版社，2007年2.李紅、王昆侖主編.“數(shù)據(jù)結(jié)構(gòu)與算法”設(shè)計(jì)指導(dǎo) 2009年2.鄭莉等著. C+語(yǔ)言程序設(shè)計(jì)（第三版）. 北京:清華大學(xué)出版社,2003.八.附錄源代碼：#include stdio.h#include iostream#include malloc.h#include string#define NULL 0using namespace std;#define M 9 /關(guān)鍵字的個(gè)數(shù)#define N 34 /省市自治區(qū)的個(gè)數(shù)#define K 26 /大寫字母的個(gè)數(shù)#define RAX 10 /基數(shù)的個(gè)數(shù)#define MAX 100 /最大能夠處理的車輛數(shù)typedef struct nodeint keynumM;char key10;char color10;char type10;char name10;struct node *next;Rnode;string a1N=澳,川,鄂,甘,贛,港,貴,桂,黑,滬,吉,津,晉,京,遼,魯,閩,內(nèi),寧,青,瓊,山,陜,蘇,臺(tái),皖,湘,新,冀,渝,豫,云,藏,浙; char a2K=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; Rnode *fRAX,*rRAX;/*fRAX,*rRAX分別為鏈隊(duì)列的隊(duì)頭指針和隊(duì)尾指針 long int elementMAX; int b;/汽車牌照轉(zhuǎn)換為數(shù)字后最后一個(gè)汽車牌照的數(shù)組中的下標(biāo)Rnode *SetList(Rnode *L,int n)Rnode *p;int m,j,k,i;int t=0,count=1; string r; L=NULL;for(i=0;in;i+)cout請(qǐng)輸入第count個(gè)車主的所有信息endl;coutendl;cout車輛的車牌號(hào)是由一個(gè)漢字，一個(gè)大寫字母和五個(gè)數(shù)字組成!endl;coutp-key;string key1=(string)p-key;string key2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(int h=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%10;p-keynum3=s;for(int n=3;nkeyn-48;p-keynumn+1=c;coutp-color;coutp-type;coutp-name;coutnext=L;L=p;return L;void Distribute(Rnode *L,int i)Rnode *p;int j,k;for(k=0;knext;j=p-keynumi;if(fj=NULL)fj=p;elserj-next=p;/隊(duì)尾指針向后移動(dòng)一位 rj=p; rj-next=NULL;p=L;Rnode *Collect()Rnode *L;int i=0,j,k;while(fi=NULL)i+;L=fi;for(j=i,k=i+1;knext=fk;j=k;return L;int Twsearch(Rnode *L,long int key,int low,int high)int mid;if(lowhigh)return -1;elsemid=(high+low)/2;if(elementmid=key)return mid;else if(keyd;string key1=(string)d;string key2=key1.substr(0,2);for(int g=0;g=0;g+)for(int j=0;jN;j+)string key3=(string)a1j;if(key2=key3) k=j;s=k/10*100000000+k%10*10000000;for(int h=0;hK;h+)if(d2=a2h)m=h; s=s+m/10*1000000+m%10*100000;s=s+(long int)d3-48)*10000+(int)d4-48)*1000+(int)d5-48)*100+(int)d6-48)*10+(int)d7-48;int c= Twsearch(p,s,0,b);if(c=-1)cout抱歉,沒(méi)