汽車牌照課程設計報告.doc

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