蔡霖《汽車牌照管理系統(tǒng)》

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流蔡霖汽車牌照管理系統(tǒng)2015-2016學(xué)年 第一學(xué)期1308210102數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報告題目：車牌管理系統(tǒng)專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級：13計(jì)科2班姓名：蔡霖指導(dǎo)教師：鄧明成績：計(jì)算機(jī)學(xué)院2015年11月16日目錄1.設(shè)計(jì)內(nèi)容及要求11.1 概述11.2 主要功能11.3 目的和要求12.概要設(shè)計(jì)12.1數(shù)據(jù)設(shè)計(jì)12.2 所需函數(shù)及框架23.設(shè)計(jì)過程或程序代碼43.1基數(shù)排序的過程43.2 二分查找的算法思想63.3主要函數(shù)及功能64.設(shè)計(jì)結(jié)果與分析124.1調(diào)試過程124.2用戶手冊135.參考文獻(xiàn)14附：源程序15.精品文檔.學(xué)號1.設(shè)

2、計(jì)內(nèi)容及要求1.1 概述排序和查找是在數(shù)據(jù)處理中使用頻度極高的操作，為加快查找的速度需現(xiàn)對數(shù)據(jù)記錄按關(guān)鍵字排序。在汽車數(shù)據(jù)的信息模型中，汽車牌照是關(guān)鍵字，而且是具有結(jié)構(gòu)特點(diǎn)的一類關(guān)鍵字，因?yàn)槠嚺普仗柺菙?shù)字和字母混編的，例如01B7328，這種記錄集合是一個適于利用多關(guān)鍵字進(jìn)行排序的典型例子。 1.2 主要功能（1）首先利用鏈?zhǔn)交鶖?shù)排序方法實(shí)現(xiàn)排序，然后利用折半查找方法，實(shí)現(xiàn)對汽車記錄按關(guān)鍵字進(jìn)行查找。 （2）汽車記錄集合可以人工錄入，也可以按自動方式隨機(jī)生成。本人采用的人工錄入。1.3 目的和要求1、在處理每個題目時，要求從分析題目的需求入手，按設(shè)計(jì)抽象數(shù)據(jù)類型、構(gòu)思算法、通過設(shè)計(jì)實(shí)現(xiàn)抽象數(shù)

3、據(jù)類型、編制上機(jī)程序和上機(jī)調(diào)試等若干步驟完成題目，最終寫出完整的分析報告。前期準(zhǔn)備工作完備與否直接影響到后序上機(jī)調(diào)試工作的效率。在程序設(shè)計(jì)階段應(yīng)盡量利用已有的標(biāo)準(zhǔn)函數(shù)，加大代碼的重用率。 2、.設(shè)計(jì)的題目要求達(dá)到一定工作量（300行以上代碼），并具有一定的深度和難度。3、程序設(shè)計(jì)語言推薦使用C/C+，程序書寫規(guī)范，源程序需加必要的注釋;2.概要設(shè)計(jì)2.1數(shù)據(jù)設(shè)計(jì)#define KEY_SIZE 8#define LIST_SIZE 100typedef structchar keyKEY_SIZE; 將車牌號以字符的形式存儲char name10; 車主的名字char carname20; 車

4、的品牌int next;RecordType;typedef struct RecordType rLIST_SIZE; 是一個RecordType類型的數(shù)組 int length;int keynum;SLinkList;2.2 所需函數(shù)及框架main()：主函數(shù)noun()：輸出提示信息菜單GetData()：從鍵盤添加車輛函數(shù)Distribute()：進(jìn)行基數(shù)排序每一趟的分配函數(shù)Collect()：進(jìn)行基數(shù)排序每一趟的收集函數(shù)Binsrch ()：二分查找函數(shù)print()：輸出所有車輛信息函數(shù)Radixsort ()：基數(shù)排序函數(shù)Zl（）：基數(shù)排序后的整理 main()Distribu

5、te()noun ()print()Collect()GetData()Radixdort()zl()Binsrch()圖1各函數(shù)之間基本關(guān)系n=1i=2i=3調(diào)用子函數(shù)GetData ()調(diào)用子函數(shù)Binsrch ()調(diào)用子函數(shù)Radixsort ()調(diào)用子函數(shù)print()i=4YNNYYNN開始輸入iNNYi=0NNY結(jié)果NN圖2程序執(zhí)行的流程圖3.設(shè)計(jì)過程或程序代碼 3.1基數(shù)排序的過程首先將待排序的記錄分成若干個子關(guān)鍵字，排序時，先按最低位的關(guān)鍵字對記錄進(jìn)行初步排序；在此基礎(chǔ)上，再按次低位關(guān)鍵字進(jìn)一步排序，以此類推，由低位到高位，由此關(guān)鍵字到主關(guān)鍵字，每一趟排序都在前一趟排序的基礎(chǔ)上

6、，直到按最高位關(guān)鍵對記錄進(jìn)行排序后，基數(shù)排序完成。在基數(shù)排序中，基數(shù)是各個關(guān)鍵只的取值范圍。若待排序的記錄是十進(jìn)制，則基數(shù)是10；若待排序的記錄是由若干個字母組成的單詞，則基數(shù)為26，也就是說，從最右邊的字母開始對記錄進(jìn)行排序，每次排序都將待排序記錄分成26組，但在此問題中，車牌號是由漢字，字母以及數(shù)字組成，若直接進(jìn)行排序，則需要分成34組，為了提高算法的空間性能，可以將漢字及字母轉(zhuǎn)換為十進(jìn)制數(shù)后再進(jìn)行基數(shù)排序。例如：一組記錄的關(guān)鍵字為：（278，109，63，930，589，184，505，269，8，83）可以看出，這組關(guān)鍵字與以前說過的用來排序的關(guān)鍵字并無差別，且也是針對但關(guān)鍵字對一組記

7、錄進(jìn)行排序。但在基數(shù)排序中，我們可以將單關(guān)鍵字看成由若干個關(guān)鍵字復(fù)合而成。上述這組關(guān)鍵字的值都在0999的范圍內(nèi)，我們可以把一個數(shù)位上的十進(jìn)制數(shù)字看成是一個關(guān)鍵字，即將關(guān)鍵字K看成由3個關(guān)鍵K0，K1，K2組成。其中，K0是百位上的數(shù)字，K1是十位上的數(shù)字，K2是個位上的數(shù)字。因?yàn)槭M(jìn)制的基數(shù)是10，所以，每個蘇偉山的數(shù)字都可能是09中的任何一個。我們先將關(guān)鍵字K2來分配所有參與排序的元素，將K2=0的元素防在一組、K2=1的元素放在一組、 、K2=9的元素放在一組。這樣，將上述一組元素分成10組，如下（a）圖所示。然后，再將K2的值由0到9的順序收集各組元素，形成序列（930，063，083

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

9、930） 269 083 008 589930 063 184 505 278 109k2=0 k2=1 k2=2 k2=3 k2=4 k2=5 k2=6 k2=7 k2=8 k2=9（a）、按個位數(shù)大小將元素分成10組一趟分配后的一組元素（930，063，083，184，505，278，008，109，589，269）109 589 008 269 184 505 930 063 278 083K1=0 k1=1 k1=2 k1=3 k1=4 k1=5 k1=6 k1=7 k1=8 k1=9 （b）、按十位數(shù)大小將元素分成10組二趟收集后的元素序列（505，008，109，930，063，2

10、69，278，083，184，589）083 063 184 278 589 008 109 269 505 930K0=0 k0=1 k0=2 k0=3 k0=4 k0=5 k0=6 k0=7 k0=8 k0=9（c）、按百位數(shù)大小將元素分成10組三趟收集后的元素序列（008，063，084，109，184，269，278，505，589，930）3.2 二分查找的算法思想（1）、將表中間位置記錄的關(guān)鍵字與給定K值比較，如果兩者相等，則查找成功。（2）、如果兩者不等，利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于給定K值，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后后一子表。

11、（3）、重復(fù)以上過程，直到找到滿足條件的記錄，則查找成功，或者直到分解出的子表不存在為止，此時查找不成功。例如對一有序的數(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 mid<key，令low=mid+1=5；mid=（low+high）/2=6第二步：將amid與key比較，我們發(fā)現(xiàn)a mid>key，此時再令high=mid-1=5；mid=（low+high）/2=5；第三步：將amid與key比較，此時amid=key，查找結(jié)束，返回mid

12、;第四步：如果仍未找到，則繼續(xù)進(jìn)行，直到low>high，此時返回-1，查找失??；3.3主要函數(shù)及功能（1）void Radixsort(SLinkList *l) /基數(shù)排序/Length 個記錄存放在數(shù)組r中，執(zhí)行本算法進(jìn)行基數(shù)排序后，鏈表中的記錄將按關(guān)鍵字從小到大的順序鏈接。/int n=l->length;zimu head,tail;shuzi heads,tails;for(int i=0;i<=n-1;i+)l->ri.next=i+1;l->rn.next=0;for(i=6;i>2;i-) / 下標(biāo)大的為低位，從低位開始Distribute

13、_s(l->r,i,heads,tails); /調(diào)用分配函數(shù) Collect_s(l->r,heads,tails); /調(diào)用收集函數(shù)Distribute_z(l->r,2,head,tail); /調(diào)用分配函數(shù)Collect_z(l->r,head,tail); /調(diào)用收集函數(shù)for(i=1;i>=0;i-) Distribute_s(l->r,i,heads,tails); Collect_s(l->r,heads,tails); （2）Void Distribute_s(RecordType r,int i,shuzi head,shuzi t

14、ail)/記錄 數(shù)組r中已按低位關(guān)鍵字keyi+1,keyd進(jìn)行低位優(yōu)先排序，本算法 按第i個關(guān)鍵字keyi建立10個隊(duì)列，同一個隊(duì)列中記錄的keyi相同。Headj和tailj分別指向各自隊(duì)列中第一個和最后一個記錄（j=0,1,2,9）.headj=0表示相應(yīng)隊(duì)列為空隊(duì)列。/*_s表示對數(shù)字進(jìn)行的操作。在程序中還有_z表示對字母的操作*int j,p;for(j=0;j<=隊(duì)列的個數(shù);j+)/初始化隊(duì)列隊(duì)列的頭指針=0;全部為0對列的尾指針=0;全部為0 p=第一個數(shù)據(jù)在數(shù)組中的位置while(第一個數(shù)據(jù)在數(shù)組中的位置!=0)j=第一個數(shù)據(jù)的第i位在第幾個隊(duì)列if(頭指針=0) 頭指針

15、=第一個數(shù)據(jù)載表中的位置; else 該隊(duì)列已有數(shù)據(jù)的下一個位置=p 否則將該數(shù)在靜態(tài)鏈表中的位置放在在同一個隊(duì)列的數(shù)據(jù)之后尾指針=p; tialj=該數(shù)在靜態(tài)鏈表中的位置p=下一個數(shù)據(jù)的位置值; void Distribute_z(RecordType r,int i,zimu head,zimu tail) int p,j;for(j=0;j<=25;j+)headj=0;tailj=0; p=r0.next;while(p!=0)j=int(int(rp.keyi)-'A');if(headj=0)headj=p;else rtailj.next=p;tailj=p

16、;p=rp.next;（3）Void collect_s(RecordType r,shuzi head,shuzi tail)/本算法從0到9掃描個隊(duì)列將所有非空隊(duì)列首尾相接，重新鏈接成一個鏈表。/int j=0,t;while(headj=0)+j; /找第一個不為空的隊(duì)列r0.next=headj;t=tailj; /把headj給第一個數(shù)據(jù)的位置while(j<9)+j;while(j<9)&&(headj=0) 找到不為0的隊(duì)列+j;if(headj!=0) rt.next=headj; t=tailj;rt.next=0; /使最后一個數(shù)的next=0v

17、oid Collect_z(RecordType r,zimu head,zimu tail) /字母類型收集重新構(gòu)成鏈表int j=0,t;while(headj=0)+j;r0.next=headj;t=tailj;while(j<25)+j;while(j<25)&&(headj=0)+j;if(headj!=0)rt.next=headj;t=tailj;rt.next=0;（4）.void zl(SLinkList *l) /整理鏈表順序int p,q;RecordType buf; p=第一個元素在表中的位置; for(int i=1;i<表的長度

18、;i+)while(p<i)p=第p個元素的下一個數(shù)在表中的位置; q=第p個元素的下一個數(shù)在表中的位置;if(p!=i)buf=第p個元素的地址;第p個元素的地址=第i個元素的地址; 交換第i個元素的地址與第p個元素的地址第i個元素的地址=buf;第i個元素的下一個數(shù)在表中的位置=p;p=q;（5）int Binsrch_bin(SLList l,char s) /二分查找,s為要找的內(nèi)容 定義整形三個位置變量 mid ,high,low,并能后兩個賦初值；(mid表示中間，high表示高位，low表示低位) While(low<=high) 用mid=(high+low)/2求

19、得mid的值； 如果L->rmid.keys(要查找的內(nèi)容)；則返回它在表中的位置mid 如果L->rmid.key<s;則將最低位變?yōu)閙id+1; 如果L->rmid.key>s;則將最高位變?yōu)閙id1執(zhí)行到些證明在表中沒找到要查找的內(nèi)容，返回0；（6） void GetData(SLinkList *L) /從鍵盤獲得數(shù)據(jù)，存在表L中。 定義輸入的狀態(tài)變量x;x不為0既認(rèn)為要輸入 定義記錄個數(shù)的整型變量j;輸出輸入的提示信息;scanf("%d",&x);輸入x的狀態(tài)； while(x)x=0;printf("t車牌號：&

20、quot;); 輸出提示scanf("%s",&(L->rj.key);輸入節(jié)點(diǎn)中對應(yīng)的量printf("t車主名：");scanf("%s",&(L->);printf("t車 名：");scanf("%s",&(L->rj.carname);printf("*按任意不為0的數(shù)字繼續(xù)錄入*:");scanf("%d",&x);if(x)j+;L->length=j;將個數(shù)賦給表的長度（

21、7） void print(SLinkList *L)遍歷靜態(tài)表int i;printf("t");printf("車牌號 車主名 車名n");for(i=1;i<=鏈表的長度;i+) 輸出各部分對應(yīng)的值；（8） int Equal(char key1,char key2) /折半查找輔助比較，判斷是否想等，只比較前7位，第八位是結(jié)束符for(int i=0;i<7;i+)if(key1i!=key2i) 任意一個不相等就不相等 ，返回0return 0;return 1;執(zhí)行到這說明都相等，返回不為0的值（9）. int xiao(char

22、 key1,char key2) /折半查找輔助比較，判斷較小for(int i=0;i<7;i+)if(key1i<key2i)return 1;else if(key1i>key2i) return 0;return 0;4.設(shè)計(jì)結(jié)果與分析4.1調(diào)試過程圖3程序主界面這部分執(zhí)行成功，為了能夠輸出對稱、格式整齊，所以要不斷的調(diào)試、修改直到滿意。（1）調(diào)試功能1添加車輛信息：從鍵盤輸入以下幾組數(shù)據(jù)； 車牌號 車主名 車名（按提示輸入，以0結(jié)束輪作輸入）輸入成功，退出輸入功能也成功，但是要注意在輸入時，每個量中間不能輸入空格。這樣會使程序默認(rèn)下個量輸入結(jié)束。（2）實(shí)現(xiàn)功能 2輸

23、出所有車輛信息：輸出的車輛信息與輸入和一致。此部部執(zhí)行成功。（3）實(shí)現(xiàn)功能3按車牌號進(jìn)行排序（從小到大）按照2.進(jìn)行輸入：在這里也套用了功能2，從結(jié)果可以看出排序成功。（4）實(shí)現(xiàn)功能4按車牌號碼查找車輛：在上面的基礎(chǔ)上分別查找01A1234和02A1234圖4查詢過程由此可能看出兩部分都執(zhí)行成功。（5）實(shí)現(xiàn)功能5，即退出程序。圖5退出程序退出程序成功。4.2用戶手冊（1）運(yùn)行程序，根據(jù)菜單選擇要實(shí)現(xiàn)的功能，輸入相應(yīng)的數(shù)字。（1：輸入數(shù)據(jù)；2:輸出所有元素3：實(shí)現(xiàn)鏈?zhǔn)交鶖?shù)排序；4：用二分查找在表中按車牌號查找；0：退出程序）（2）當(dāng)選擇功能1后，根據(jù)提示輸入相應(yīng)的信息，在輸入時，每個字符串之間不

24、要有空格。按0退出輸入。（在輸入時輸入2位數(shù)字，一個大寫字母，然后再輸入四位數(shù)字）（3）當(dāng)選擇功能2后，會按格式輸出所有節(jié)點(diǎn)信息。（4）當(dāng)選擇功能3后。會輸出進(jìn)行鏈?zhǔn)脚判蚝蟮乃泄?jié)點(diǎn)信息。（5）當(dāng)先擇功能4后，請輸入您要查找車輛的車牌號碼。程序會輸入相應(yīng)信息。（6）在沒有執(zhí)行第4步前，不能執(zhí)行第五步。退出程序請按0，然后安任意鍵會關(guān)閉運(yùn)行窗口。5.參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民，米寧等.數(shù)據(jù)結(jié)構(gòu)（C語言版）M .北京：清華大學(xué)出版社，20072 譚浩強(qiáng)著.C程序設(shè)計(jì)（第三版）M .北京：清華大學(xué)出版社，20053 耿國華.數(shù)據(jù)結(jié)構(gòu)C語言描述M.北京：高等教育出版社，20104 嚴(yán)蔚敏,吳偉民，米寧

25、等.數(shù)據(jù)結(jié)構(gòu)題集（C語言版）M .北京：清華大學(xué)出版社，20115 嚴(yán)蔚敏,李冬梅等. 數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）M .北京：清華大學(xué)出版社，2014附：源程序#include<stdio.h>#define KEY_SIZE 8#define LIST_SIZE 100typedef structchar keyKEY_SIZE;char name10;char carname20;int next;RecordType;typedef struct RecordType rLIST_SIZE;int length;int keynum;SLinkList;typedef i

26、nt shuzi10;typedef int zimu26;void InitSLList(SLinkList *L) L->length=0;L->keynum=7;void Distribute_s(RecordType r,int i,shuzi head,shuzi tail) /數(shù)字分配int j,p;for(j=0;j<=9;j+)headj=0;tailj=0; p=r0.next;while(p!=0)j=int(rp.keyi-'0');if(headj=0)headj=p;else rtailj.next=p;tailj=p;p=rp.ne

27、xt;void Distribute_z(RecordType r,int i,zimu head,zimu tail) int p,j;for(j=0;j<=25;j+)headj=0;tailj=0; p=r0.next;while(p!=0)j=int(int(rp.keyi)-'A');if(headj=0)headj=p;else rtailj.next=p;tailj=p;p=rp.next;void Collect_s(RecordType r,shuzi head,shuzi tail) /收集重新構(gòu)成鏈表int j=0,t;while(headj=0)+

28、j;r0.next=headj;t=tailj;while(j<9)+j;while(j<9)&&(headj=0)+j;if(headj!=0)rt.next=headj;t=tailj;rt.next=0;void Collect_z(RecordType r,zimu head,zimu tail) /字母類型收集重新構(gòu)成鏈表int j=0,t;while(headj=0)+j;r0.next=headj;t=tailj;while(j<25) +j;while(j<25)&&(headj=0)+j;if(headj!=0)rt.n

29、ext=headj;t=tailj;rt.next=0;void Radixsort(SLinkList *l) /基數(shù)排序int n=l->length;zimu head,tail;shuzi heads,tails;for(int i=0;i<=n-1;i+)l->ri.next=i+1;l->rn.next=0;for(i=6;i>2;i-) / 下標(biāo)大的為低位，從低位開始Distribute_s(l->r,i,heads,tails); /調(diào)用分配函數(shù) Collect_s(l->r,heads,tails); /調(diào)用收集函數(shù)Distribut

30、e_z(l->r,2,head,tail); /調(diào)用分配函數(shù)Collect_z(l->r,head,tail); /調(diào)用收集函數(shù)for(i=1;i>=0;i-) Distribute_s(l->r,i,heads,tails); Collect_s(l->r,heads,tails); void zl(SLinkList *l) /進(jìn)行排序后整理順序int p,q;RecordType buf;p=l->r0.next; /p指向第一個記錄的當(dāng)前位置for(int i=1;i<l->length;i+)while(p<i)p=l->r

31、p.next; /找到第i個記錄，并用p指示其在表中的當(dāng)前位置。 q=l->rp.next;if(p!=i)buf=l->rp;l->rp=l->ri;l->ri=buf; /交換p與il->ri.next=p; /使得被移走的記錄使得以后可以由while循環(huán)找回p=q;void GetData(SLinkList *L)/從鍵盤獲得數(shù)據(jù)int x;int j=1;printf("請輸入車牌號碼及車主名與車名n");printf("例如: 01B1234"); printf("n");printf(

32、"如要錄入請按任意不為0的數(shù)字，退出此功能請按0:");scanf("%d",&x);printf("n"); while(x)x=0;printf("t車牌號：");scanf("%s",&(L->rj.key);printf("t車主名：");scanf("%s",&(L->);printf("t車 名：");scanf("%s",&(L->rj.c

33、arname);printf("*按任意不為0的數(shù)字繼續(xù)錄入*:");scanf("%d",&x);if(x)j+;L->length=j;void print(SLinkList *L) /輸出出所有元素int i;printf("t");printf("車牌號 車主名 車名");printf("n");for(i=1;i<=L->length;i+)printf("t%s",L->ri.key);printf(" %s"

34、 , (L->);printf(" %sn",L->ri.carname);int Equal(char key1,char key2) /折半查找輔助比較，判斷是否想等，只比較前7位，第八位是結(jié)束符for(int i=0;i<7;i+)if(key1i!=key2i) return 0;return 1;int xiao(char key1,char key2) /折半查找輔助比較，mid位的數(shù)據(jù)小于查找的數(shù)for(int i=0;i<7;i+)if(key1i<key2i)return 1;else if(key1i>key2i) return 0;return 0;int Binsrch(SLinkList *L,char s8) /按車牌號，(.key)折半查找int mid,high,low; low=1;high=L->length;while(low<=high)mid=(high+low)/2;if(Equal(s,L->rmid.key)return(mid);else if(xiao(s,L->rmid.key)high=mid-1;elselow=mid+1;return(0);void noun() /輸出提示操作 printf(&quo