汽車牌照排序與查找課程設(shè)計報告

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大小：257.50KB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、們可以將單關(guān)鍵字看成由若干個關(guān)鍵字復(fù)合而成。　　上述這組關(guān)鍵字的值都在0~999的范圍內(nèi)，我們可以把一個數(shù)位上的十進制數(shù)字看成是一個關(guān)鍵字，即將關(guān)鍵字K看成由3個關(guān)鍵K0，K1，K2組成。其中，K0是百位上的數(shù)字，K1是十位上的數(shù)字，K2是個位上的數(shù)字。　　因為十進制的基數(shù)是10，所以，每個蘇偉山的數(shù)字都可能是0~9中的任何一個。我們先將關(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）。　　對上述序列中的元素再按關(guān)鍵字K1來分配，也分成10組，如下（b）圖所示。然后，再按K1的值由0到9的順序

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

51、　}　　cout<<"排序已完成!"<<endl;　　while(q!=NULL){　　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];　　q=q->next;　　b=a;<p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

74、對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;　　break;　　}　　s=s+m/10*1000000+m%10*100000;　　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;　　c=BinSrch(q,s,0,b);　　if(-1==c)　　cout<<"

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

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

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

79、>　　}　　cout<<endl;　　}　　四、上機調(diào)試　　1、語法錯誤及修改：由于本算法使用了鏈式基數(shù)排序和二分查找，所以程序相對來說得到

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

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

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

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

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

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

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

87、;　　#include "iostream"　　#include "fstream"　　#include "stdlib.h"　　#include "malloc.h"

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

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

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

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

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

93、uot;豫","云","藏","浙"};　　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'};　　Rnode *f[RA

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

120、/p>　　if(m>25||m<0)　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;　　s=s+m/10*1000000+m%10*100000;　　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;　　c=BinSrch(q,s,0,b);　　if(-1==c)　　cout<<"==對不起,沒有找到您要

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

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

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

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

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

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

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

129、gt;　　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>　　q=q->next;　　b=a;　　a++;}　　flag=0;　　return p; }

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

汽車牌照排序與查找課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

汽車牌照排序與查找課程設(shè)計報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載