數(shù)據(jù)結構課程設計--汽車牌照的快速查找

1、<p><b>　　xx大學</b></p><p>　　課 程 設 計 實 踐 報 告</p><p>　　學 院：計算機與信息工程學院</p><p>　　課程名稱： 算法與數(shù)據(jù)結構</p><p>　　任課教師： xxx </p><p>　　班 級： xx班

2、 </p><p>　　學 號： xxx </p><p>　　姓 名： xxx </p><p><b>　　同組學生：</b></p><p>　　實踐地點: xx大學</p><p>　　實踐時間：2010年8月19日至2010年9月3日</p>

3、<p>　　實驗題目：汽車牌照的快速查找</p><p><b>　　實驗要求：</b></p><p>　　利用鏈式基數(shù)排序和折半查找對一批汽車牌照進行排序和查找</p><p><b>　　問題分析：</b></p><p>　　想要完成題目要求，需要選擇鏈表對汽車信息（包括汽車牌照、

4、汽車顏色、汽車商標、汽車的注冊時間、汽車所有者等）進行存儲，并在此基礎上進行多關鍵字排序，因為汽車牌號是漢字、字母和數(shù)字的組合?？紤]到對漢字進行排序是一件不可能的事，因此對各省市的簡稱可以放到字符串數(shù)組中，也就可以通過數(shù)組下標進行排序，字母可以選擇同漢字一樣的處理方法，數(shù)字卻很容易進行排序。因此，排好序的汽車牌照其實就是一組長整型數(shù)組，例如根據(jù)行政規(guī)劃對各省市的簡稱進行存儲，如汽車牌照京C0123，轉換為長整型數(shù)組后為00020123&

5、lt;/p><p>　　如何對排好序的車輛信息進行折半查找呢？因為存儲好的汽車信息其實就是一組長整型數(shù)組，而所輸入的信息就是一個長整型數(shù)據(jù)，然后再那個數(shù)組中進行折半查找既可以實現(xiàn)。</p><p><b>　　設計思路及流程： </b></p><p>　　為了完成所需的功能，需要的函數(shù)及其功能如下：</p><p>　　m

6、ain()：主函數(shù)模塊</p><p>　　SetList()：添加車輛函數(shù)</p><p>　　Distribute()：進行基數(shù)排序每一趟的分配函數(shù)</p><p>　　Collect()：進行基數(shù)排序每一趟的收集函數(shù)</p><p>　　find()：二分查找函數(shù)</p><p>　　menu()：主函數(shù)顯示菜單

7、模塊</p><p>　　print()：輸出所有車輛信息函數(shù)</p><p>　　paixu()：基數(shù)排序函數(shù)</p><p><b>　　以下為各函數(shù)流程圖</b></p><p>　　主函數(shù)流程圖： 汽車信息函數(shù)SetList(p)流程圖： </p&

8、gt;<p>　　排序子函數(shù)paixu(p)的流程圖 ： 查找子函數(shù)find(p)的流程圖</p><p><b>　　詳細算法思想：</b></p><p>　　1、基數(shù)排序的過程：</p><p>　　首先將待排序的記錄分成若干個子關鍵字，排序時，先按最低位的關鍵字對記錄進行初步排序；在此基礎上，再按次低位

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

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

11、看成由若干個關鍵字復合而成。</p><p>　　上述這組關鍵字的值都在0~999的范圍內，我們可以把一個數(shù)位上的十進制數(shù)字看成是一個關鍵字，即將關鍵字K看成由3個關鍵K0，K1，K2組成。其中，K0是百位上的數(shù)字，K1是十位上的數(shù)字，K2是個位上的數(shù)字。</p><p>　　因為十進制的基數(shù)是10，所以，每個蘇偉山的數(shù)字都可能是0~9中的任何一個。我們先將關鍵字K2來分配所有參與排序的元

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

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

14、（008，063，083，109，184，267，278，505，589，930）</p><p><b>　　269</b></p><p>　　083 008 589</p><p>　　930 063 184

15、 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>　　（a）、按個位數(shù)大小將元素分成10組</p><p>　　一趟分配后的一組元素（

16、930，063，083，184，505，278，008，109，589，269）</p><p>　　109 589 </p><p>　　008 269 1

17、84 </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><p>　

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

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

20、 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>　　2、二分查找的算法思想：</p><p&g

21、t;　?。?）、將表中間位置記錄的關鍵字與給定K值比較，如果兩者相等，則查找成功。</p><p>　　（2）、如果兩者不等，利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于給定K值，則進一步查找前一子表，否則進一步查找后后一子表。</p><p>　?。?）、重復以上過程，直到找到滿足條件的記錄，則查找成功，或者直到分解出的子表不存在為止，此時查找不成功。</p

22、><p>　　例如對一有序的數(shù)組a（1，2 ，3，4，5，6，7，8，9）進行查找數(shù)key=6；</p><p>　　首先定義low=0，high=8，mid=（low+high）/2=4；</p><p>　　第一步：將a[mid]與key比較，我們發(fā)現(xiàn)a [mid]<key，令low=mid+1=5；mid=（low+high）/2=6；</p>

23、<p>　　第二步：將a[mid]與key比較，我們發(fā)現(xiàn)a [mid]>key，此時再令high=mid-1=5；mid=（low+high）/2=5；</p><p>　　第三步：將a[mid]與key比較，此時a[mid]=key，查找結束，返回mid；</p><p><b>　　六、測試結果： </b></p><p>

24、;<b>　　1、添加車輛信息：</b></p><p>　　2、繼續(xù)添加車輛，輸出排序后的車輛信息：</p><p><b>　　3、查找汽車牌號：</b></p><p>　　4、程序結束，關閉窗口。</p><p><b>　　七、系統(tǒng)說明：</b></p>

25、<p>　　1、根據(jù)菜單選項進行相應的操作</p><p>　　2、在系統(tǒng)添加的同時對已有數(shù)據(jù)進行排序</p><p>　　3、添加的車輛牌號為漢字加大寫字母和4位數(shù)字，其中漢字為全國34個省市行政區(qū)相對應的簡稱</p><p>　　4、所輸入的車主姓名及汽車品牌等不能超過3個漢字</p><p>　　八、心得體會：（郭海新 張濤

26、 符祥華）</p><p>　　通過此次實踐，我們對基數(shù)排序和折半查找的有了更深的理解，通過查找資料，對相應的程序段也有了認識，知道了如何從偽碼過渡到程序語言。由于我們的編程成能力都不是很好，因此程序的部分代碼參考了相應的程序，并在此基礎上同本次實驗所要求得進行了相應的改進。讀得懂程序并不代表會寫程序，以前一直就有這鐘想法，此次更是，腦袋里有了程序的大致流程和走向，但是想要用程序語言把這種想法給落實出來，缺感到有

27、些力不從心。因此，在今后的學習中我們要加強自己的編程能力。大三即將開始，誰都不想以后一事無成，而作為其中最基本的編程能力我們還都不能夠熟練掌握，此后的路任重而道遠，只有加強練習才能提高自己，改變自己。</p><p>　　考慮到此程序并非原創(chuàng)，因此我們小組考慮如下申請成績：</p><p><b>　　xxx 良</b></p><p>&l

28、t;b>　　xxx 良</b></p><p><b>　　xxx 良</b></p><p>　　附錄：詳細代碼（DEVC調試）</p><p>　　#include "stdio.h"</p><p>　　#include "iostream"</p

29、><p>　　#include "malloc.h"</p><p>　　#include "string"</p><p>　　using namespace std;</p><p>　　#define M 8 //關鍵字的個數(shù)</p><p>　　#define N 34

30、 //省市自治區(qū)的個數(shù)</p><p>　　#define K 26 //大寫字母的個數(shù)</p><p>　　#define RAX 10 //基數(shù)的個數(shù)</p><p>　　#define MAX 100 //最大能夠處理的車輛數(shù)</p><p>　　typedef struct node{</p><p&g

31、t;　　int keynum[M];</p><p>　　char key[10];</p><p>　　char color[10];</p><p>　　char type[10];</p><p>　　char time[10];</p><p>　　char name[10];</p><p

32、>　　struct node *next;</p><p><b>　　}Rnode;</b></p><p>　　string name1[N]={"京","津","滬","渝","黑","吉","遼","蒙&q

33、uot;,"魯","冀","晉","豫","寧","陜","甘","青","新","藏","川","鄂","蘇","皖","浙","

34、;贛","湘","貴","云","桂","閩","臺","粵","瓊","港","澳"};</p><p>　　char name2[K]={'A','B','C&#

35、39;,'D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U',

36、'V','W','X','Y','Z'};</p><p>　　Rnode *f[RAX],*r[RAX];//*f[RAX],*r[RAX]分別為鏈隊列的隊頭指針和隊尾指針</p><p>　　long int A[MAX];</p><p>　　int b;//汽車牌照轉換為數(shù)字后最

37、后一個汽車牌照的數(shù)組中的下標</p><p><b>　　//錄入汽車信息 </b></p><p>　　Rnode *SetList(Rnode *q){</p><p>　　cout<<"請注意車輛的牌照號是由一個漢字，一個大寫字母和四個數(shù)字組成!"<<endl; </p><

38、p>　　Rnode *head,*p,*t;</p><p>　　int m,j,k;</p><p><b>　　int g=0;</b></p><p><b>　　string r;</b></p><p><b>　　head=q;</b></p>

39、<p>　　printf("請輸入該車的牌照號!\n");</p><p>　　p=(Rnode *)malloc(sizeof(Rnode));</p><p>　　p->next=NULL;</p><p>　　if(head==NULL)</p><p><b>　　head=p;</

40、b></p><p>　　cin>>p->key;</p><p>　　string key1=(string)p->key;</p><p>　　string key2=key1.substr(0,2);</p><p>　　for(g=0;g<=0;g++){</p><p>

41、　　// 將所輸入的漢字轉為相應的數(shù)組下標 </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></p><p&g

42、t;<b>　　}</b></p><p><b>　　}</b></p><p>　　if(k>33||k<0){</p><p>　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>

43、;　　break;</b></p><p><b>　　}</b></p><p>　　int s=k/10;</p><p>　　p->keynum[0]=s;</p><p><b>　　s=k%10;</b></p><p>　　p->keynu

44、m[1]=s;</p><p>　　for(int h=0;h<K;h++){</p><p>　　if(p->key[2]==name2[h])</p><p><b>　　m=h;</b></p><p><b>　　}</b></p><p>　　if(m

45、>25||m<0){</p><p>　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　

46、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;n++){</p><p>　　

47、int c=(int)p->key[n]-48;</p><p>　　p->keynum[n+1]=c;</p><p><b>　　}</b></p><p>　　printf("請輸入該車的顏色!\n");</p><p>　　cin>>p->color;</p

48、><p>　　printf("請輸入該車的車型!\n");</p><p>　　cin>>p->type;</p><p>　　printf("請輸入該車的注冊時間!\n");</p><p>　　cin>>p->time;</p><p>　　p

49、rintf("請輸入該車的車主姓名!\n");</p><p>　　cin>>p->name;</p><p><b>　　}</b></p><p>　　if(q!=NULL){</p><p>　　while(q!=NULL){</p><p>　　t=q

50、; //記錄q的前一節(jié)點</p><p>　　q=q->next;</p><p><b>　　}</b></p><p><b>　　q=t;</b></p><p>　　q->next=p;</p><p><b>　　}</b><

51、;/p><p><b>　　else</b></p><p><b>　　q=p;</b></p><p>　　return head;</p><p><b>　　}</b></p><p>　　//掃描鏈表L，按第i個關鍵字將各記錄分配到相應的鏈隊列中

52、</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++) //將RAX個鏈隊列初始化為空</p><p&

53、gt;　　f[i]=r[i]=NULL;</p><p><b>　　p=L;</b></p><p>　　while(p!=NULL){</p><p>　　L=L->next;</p><p>　　k=p->keynum[j]; //用記錄中第i位關鍵字的值即為相應的隊列號 </p><

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

55、;/p><p>　　r[k]->next=NULL;</p><p><b>　　p=L;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//從鏈隊列f[0]開始，依次收集各鏈隊列中的節(jié)點&

56、lt;/p><p>　　Rnode *Collect(){</p><p><b>　　Rnode *L;</b></p><p>　　int i=0,j,k;</p><p>　　while(f[i]==NULL)</p><p>　　i++; //查找第一個不空的鏈隊列</p>&

57、lt;p><b>　　L=f[i];</b></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];</p><p><b>　　j=k;</b></

58、p><p><b>　　}</b></p><p><b>　　return L;</b></p><p><b>　　}</b></p><p><b>　　//折半查找算法 </b></p><p>　　int BinSrch(Rn

59、ode *q,long int k,int low,int high){</p><p><b>　　int mid;</b></p><p>　　if(low>high)</p><p>　　return -1;</p><p><b>　　else{</b></p><

60、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><p><b&g

61、t;　　else</b></p><p>　　return (BinSrch(q,k,mid+1,high));</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//查找牌號 </b></p>

62、<p>　　void find(Rnode *q){</p><p><b>　　Rnode *p;</b></p><p><b>　　p=q;</b></p><p><b>　　int k,m;</b></p><p>　　char d[8];</p&g

63、t;<p>　　long int s;</p><p><b>　　cin>>d; </b></p><p>　　string key1=(string)d;</p><p>　　string key2=key1.substr(0,2);</p><p>　　for(int g=0;g<=

64、0;g++){</p><p>　　for(int j=0;j<N;j++){</p><p>　　string key3=(string)name1[j];</p><p>　　if(key2==key3)</p><p><b>　　k=j;</b></p><p><b>　

65、　}</b></p><p>　　if(k>33||k<0){</p><p>　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>　　break;</b></p><p><b>　　}<

66、;/b></p><p>　　s=k/10*10000000+k%10*1000000;</p><p>　　for(int h=0;h<K;h++){</p><p>　　if(d[2]==name2[h])</p><p><b>　　m=h;</b></p><p><b&

67、gt;　　}</b></p><p>　　if(m>25||m<0){</p><p>　　cout<<"對不起,您輸入的車牌號不合法,請重新輸入!"<<endl;</p><p><b>　　break;</b></p><p><b>　　

68、}</b></p><p>　　s=s+m/10*100000+m%10*10000;</p><p>　　s=s+((long int)d[3]-48)*10000+((int)d[4]-48)*1000+((int)d[5]-48)*100+(int)d[6]-48;</p><p>　　int c= BinSrch(q,s,0,b);</p&

69、gt;<p><b>　　if(-1==c)</b></p><p>　　cout<<"對不起,沒有您要的記錄,請重新輸入!"<<endl<<endl;</p><p><b>　　else{</b></p><p>　　cout<<&quo

70、t;查找成功,該車的詳細信息為:"<<endl;</p><p>　　cout<<"車主"<<"\t\t"<<"牌照號"<<"\t\t"<<"車色"<<"\t\t"<<"車型&qu

71、ot;<<"\t\t"<<"時間"<<endl;</p><p>　　for(int i=0;i<c;i++){</p><p>　　q=q->next;</p><p><b>　　}</b></p><p>　　cout<&

72、lt;q->name<<"\t\t"<<q->key<<"\t\t"<<q->color<<"\t\t"<<q->type<<"\t\t"<<q->time<<endl;</p><p><b

73、>　　}</b></p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b>　　}</b></p><p><b>　　//菜單界面 </b></p><p>　　void

74、 menu(){</p><p>　　cout<<"t:添加車輛!"<<endl;</p><p>　　cout<<"c:按車牌查找!"<<endl;</p><p>　　cout<<"s:輸出所有汽車信息!"<<

75、;endl;</p><p>　　cout<<"q:退出"<<endl<<endl;</p><p><b>　　}</b></p><p><b>　　//輸出汽車信息 </b></p><p>　　void print(Rnode

76、*p){</p><p>　　cout<<"車主"<<"\t\t"<<"牌照號"<<"\t\t"<<"車色"<<"\t\t"<<"車型"<<"\t\t"<

77、<"時間"<<endl;</p><p>　　while(p!=NULL){</p><p>　　cout<<p->name<<"\t\t"<<p->key<<"\t\t"<<p->color<<"\t\t&quo

78、t;<<p->type<<"\t\t"<<p->time<<endl;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　cout<<endl;</p><p><b

79、>　　}</b></p><p><b>　　//排序子函數(shù) </b></p><p>　　Rnode *paixu(Rnode *p){</p><p><b>　　Rnode *q;</b></p><p><b>　　int a=0;</b></

80、p><p>　　for(int i=M-1;i>=0;i--){</p><p>　　//分別按M個子關鍵字對待排序列進行分配和收集</p><p>　　Distribute(p,i);</p><p>　　q=p=Collect();</p><p><b>　　}</b></p>

81、<p>　　cout<<"排序已完成!"<<endl;</p><p>　　while(q!=NULL){</p><p>　　A[a]=q->keynum[0]*10000000+q->keynum[1]*1000000+q->keynum[2]*100000+q->keynum[3]*10000+q-&

82、gt;keynum[4]*1000+q->keynum[5]*100+q->keynum[6]*10+q->keynum[7];</p><p>　　q=q->next;</p><p><b>　　b=a;</b></p><p><b>　　a++;</b></p><p&g

83、t;<b>　　}</b></p><p><b>　　return p;</b></p><p><b>　　}</b></p><p><b>　　//主函數(shù) </b></p><p>　　int main()</p><p>

84、<b>　　{</b></p><p>　　cout<<"車 輛 信 息 管 理 系 統(tǒng)!"<<endl<<endl;</p><p><b>　　Rnode *p;</b></p><p><b>　　p=NULL;</b></p

85、><p><b>　　for(;;){</b></p><p><b>　　menu();</b></p><p><b>　　char n;</b></p><p>　　cout<<"請選擇:";</p><p><b

86、>　　cin>>n;</b></p><p>　　getchar();</p><p>　　switch(n){</p><p>　　case 't':p=SetList(p);p=paixu(p);break;//添加的同時對數(shù)據(jù)進行基數(shù)排序 </p><p>　　case 'c'

87、;:find(p);break;//查找號碼 </p><p>　　case 's':print(p);break;//輸出全部信息 </p><p>　　case 'q':exit(0);//退出系統(tǒng) </p><p>　　default:cout<<"您的輸入有誤,請重新輸入!"<<e