1、下載可編輯課程設計報告一.問題的分析與定義題目：汽車拍照的排序與查找問題此題目主要要求對汽車牌照進行基數排序,和用二分查找的思想進行查找,這兩種方法思想并不難,但是要對汽車牌照進行排序和查找,此問題涉及到的主要問題是：首先的問題就是,用何種存儲結構對汽車信息和汽車牌照進行存儲汽車牌照,然后汽車牌照不是單單是數字,而且是漢字、字母與數字混合排列的,這就不僅僅對數字進行基數排序了,還要對字母進行相關處理,方可用基數排序的方法進行排序.經過最后查找資料、分析將漢字、字母轉化為數字處理,漢字代表汽車牌照的地區,共有34個省市自治區簡稱,即34個漢字,26個英語大寫字母,分別用數組存儲這34個漢字和26

2、個大寫字母,將他們轉化為數字,最后再用基數排序,方可到達題目要求.在二分查找問題中,是對汽車牌進行查找,首先將要查找的汽車牌轉換為數字形式,再用二分查找遞歸算法,找不到返回一個值,找到再返回一個值,再找到這個位置,輸出查找的所有信息,即可到達題目要求.二.數據結構的選擇和概要設計1 .數據結構的選擇對于汽車牌照進行排序和查找,為了使程序盡可能的實用性,我將定義,車主,車牌號,車色,車型為一個結構類型,用鏈表的形式存儲這些信息,為了方便對汽車牌照進行排序,在定義一個數組存儲將漢字、字母轉化后的長數據類型,漢字和字母都用兩個字符來表示.在基數排序中,基數排序每趟的收集由兩個鏈隊列收集,鏈隊列的個數

3、為基數的個數.在二分查找中,是對汽車牌號進行查找,首先將汽車牌號轉化為數字,再用遞歸算法查找.最后再將所有車輛信息輸出,到達題目要求.2.概要設計為了實現上述功能,需要的函數及其功能如下：1) .主函數main()2)車輛信息錄入函數Setlist()3)基數每一趟的分配函數Distribute()4)基數每一趟的收集函數Collect.5)基數排序函數paixu()6)二分查找函數search()7)輸出函數print()各函數關系如下：.專業.整理.下載可編輯主函數流程圖:.專業.整理.下載可編輯鏈式基數排序就是在鏈式存儲結構下通過反復的分配、收集運算來進行排序的.首先將待排序的記錄分成假

4、設干個子關鍵字,排序時,先按最低位的關鍵字對記錄進行初步排序；在此根底上,再按次低位關鍵字進一步排序,以此類推,由低位到高位,由此關鍵字到主關鍵字,每一趟排序都在前一趟排序的根底上,直到按最高位關鍵對記錄進行排序后,基數排序完成.車牌號是由一個漢字、一個大寫字母和五個數字組成,由于有34個省自治區簡稱,字母有26個,本來基數應該是34,但這樣一來太麻煩,而且不好分析,故將漢字、字母轉換為十進制數再進行基數排序,這樣做的好處是,基數都是從09,比擬簡便,而且易懂.為了更好的分析此算法,舉一個例子：一組記錄的關鍵字為：83,8,184,505,930,589,63,109,278采用基數排序方法對

5、其進行排序.上述這組關鍵字的值都在0三K三99的范圍內,我們可以把每一個數位上的十進制數字看成是一個關鍵字,即將關鍵字K看成由3個關鍵字K5,k,K2組成.其中,K5是百位上的數字,K1是十位上的數字,K2是個位上的數字.由于十進制的基數是10,所以,每個數位上的數字都可能是09中的任何一個.先按關鍵字K2來分配所有參與排序的元素,將K2=0的元素放在一組、K2=1的元素放在一組、K2=9的元素放在一組.再按K2的值由0到9的順序收集各組元素,形成序列(930,063,083,184,505,278,008,109,589,269).對上述序列中的元素再按關鍵字K1來分配,也分成10組.然后再

6、按K的值由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).基數排序完成.分析該例,可以看出基數排序的思想是：首先將待排序的記錄分成假設干個子關鍵字,排序時,先按最低位的關鍵字對記錄進行初步排序；在此根底上,再按次地位關鍵字進一步排序.依次類推,由低位到高位,由次關鍵字到主關鍵字,每一趟排序都在前一趟排序的基礎上,直到按最高位關鍵字對記錄進行排序后,基數排序

7、完成.因此,在汽車牌照的基數排序中,首先將汽車牌照的漢字、字母全部轉化為十進制數,以便于基數排序.漢字和字母是由兩個字符表示,轉換好前方可進行基數排序.接下來就是如何收集各組記錄.從上述例子可看出,各組記錄的收集遵循“先進入該組的記錄將先被收集的原那么可知,各組序列以列來描述較為精確.由于要進行屢次的分配與收集,為節省存儲空間及運算方便,采用鏈隊列來存儲各組序列.鏈隊列的數量與基數一致,假設基數為RAX那么令f0卜fRAX-1分別指向RAX個鏈隊列的隊頭節點,令r0rRAX-1分別指向RAX個隊列的隊尾節點.每次分配前,將RAX個鏈隊列置空,即for(i=0;iRAX-1;i+)fi=ri=N

8、ULL;.專業.整理.三.詳細設計和編碼1.汽車節點類型typedefstructnodeintkeynumM;/charkey10;/charcolor10;/chartype10;/charname10;/structnode*next;/Rnode;2.基數排序的過程汽車牌照轉換為十進制后的數據汽車牌照號汽車顏色汽車類型車主姓名指向下一個節點的指針域下載可編輯Rnode*fRAX,*rRAX;/*fRAX,*rRAX分別為鏈隊列的隊頭指針和隊尾指針longintelementMAX;/數組存儲轉換后的車牌號主要算法：1) .數據錄入函數Rnode*SetList(Rnode*L,intn

9、)Rnode*p;intm,j,k,i;intt=0,count=1;stringr;L=NULL;for(i=0;in;i+)cout請輸入第count個車主的所有信息endl;coutendl;cout車輛的車牌號是由一個漢字,一個大寫字母和五個數字組成！endl;coutp-key;stringkey1=(string)p-key;stringkey2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(inth=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%1

10、0;p-keynum3=s;for(intn=3;nkeyn-48;p-keynumn+1=c;count+;p-next=L;L=p;returnL;2).基數排序假設關鍵字為整型數據,那么存放待排序記錄的單鏈表可以這樣構造：.專業.整理.下載可編輯#defineNRnode*LL=NULL8,*1for(i=1/N為待排記錄的個數p；/鏈表L初始化為空;ip-key;p-next=L+j)/分別率入M個子關鍵字voidDistribute(Rnode*L,inti)Rnode*p;intj,k;for(k=0;knext;j=p-keynumi;/if(fj=NULL)/fj=p;else

11、rj-next=p;/將RAX個鏈隊列初始化為空用記錄中第i位關鍵字的值即為相應的隊列號將結點*p分配到相應的鏈隊列fi中隊尾指針向后移動一位rj=p;rj-next=NULL;p=L;Rnode*Collect()Rnode*L;inti=0/while(fi=NULL)i+L=fi;for(j=i,k=i+1從鏈隊列knext=fkreturnLRnode*paixu(Rnode*L)/Rnode*q;排序函數f0開始,依次收集各鏈隊列中的節點查找第一個不空的鏈隊列+k)；j=k；inta=0;q=L;for(inti=M-1;i=0;i-)Distribute(L,i);L=Collec

12、t();.專業.整理.下載可編輯到此基數排序算法結束.從算法中容易看出,對于n個記錄(每個記錄含M個子關鍵字,每個子關鍵字的取值范圍為RAX個值)進行鏈式排序白時間復雜度為O(M(n+RAX),其中每一趟分配算法的時間復雜度為O(n),每一趟收集算法的時間復雜度為O(RAX),整個排序進行M趟分配和收集,所需輔助空間為2XRAX個隊列指針.當然,由于需要鏈表作為存儲結構,那么相對于其它以順序結構存儲記錄的排序方法而言,還增加了n個指針域空間.3)二分查找的算法思想當汽車牌照號都轉換為數字形式后,需要用一個longintelementMAX進行存儲,以便進行查找.(1.)將表中間位置記錄的關鍵字

13、與給定K值比擬,如果兩者相等,那么查找成功.(2)、如果兩者不等,利用中間位置記錄將表分成前、后兩個子表,如果中間位置記錄的關鍵字大于給定K值,那么進一步查找前一子表,否那么進一步查找后后一子表.(3)、重復以上過程,直到找到滿足條件的記錄,那么查找成功,或者直到分解出的子表不存在為止,此時查找不成功.例如對一有序的數組a(1,2,3,4,5,6,7,8,9)進行查找數key=6;首先定義low=0,high=8,mid=(low+high)/2=4;第一步：將amid與key比擬,我們發現amidkey,此時再令high=mid-1=5;mid=(low+high)/2=5;第三步：將ami

14、d與key比擬,此時amid=key,查找結束,返回mid；第四步：如果仍未找到,那么繼續進行,直到lowhigh,此時返回-1,查找失敗；對于該程序最嚴重的問題就是如何對鏈表進行二分查找,經過查找資料以及思考,要想純粹的輸入一個車牌號不做相應的變換就進行查找,這種思路雖然很清楚,但運行起來不太方便,由于這不僅要對數字進行查找,而且還對漢字、字母進行查找.因此,這種思路不合理.最后,我想到用一個長整型的數組來存儲變換后的車牌號,對這組車牌號再進行相關查找和相關操作,最后具體實現.該局部的具體代碼為：returnL;intTwsearch(Rnode*L,longintkey,intlow,in

15、thigh)/遞歸二分查找算法intmid;if(lowhigh)return-1;elsemid=(high+low)/2;if(elementmid=key)returnmid;elseif(keyd;stringkey1=(string)d;stringkey2=key1.substr(0,2);for(intg=0;g=0;g+)for(intj=0;jN;j+)stringkey3=(string)a1j;if(key2=key3)k=j;s=k/10*100000000+k%10*10000000;for(inth=0;hK;h+)if(d2=a2h)m=h;s=s+m/10*10

16、00000+m%10*100000;s=s+(longint)d3卜48)*10000+(int)d4卜48)*1000+(int)d5卜48)*100+(int)d6卜48)*10+(int)d7-48;intc=BinSrch(p,s,0,b);if(c=-1)cout抱歉,沒有您要查找的記錄！endlendl;elsecout查找成功,此車的詳細信息為：endl;cout車主車牌號車色車型endl;for(inti=0;inext;coutnamekeycolortypeendl;coutendl;四.上機調試剛開始著手做這個程序的時候,由于對數進行基數排序,我還以為很好做,但是要進行漢

17、字、字母和數字混排的數進行基數排序,不知道該如何進行處理,修改屢次程序都不能正確滿足要求,最后,通過查找資料,可以把漢字、字母轉換為十進制數在進行基數排序,最后得以實現.在進行基數排序時,由于基數排序算法在書本中有詳細介紹,因此沒有出現太大的問題.在調試過程中假設輸入的車輛牌照有皖A12345,但在查找此車牌號時確顯示沒有您要查找的記錄,經過一步一步的調試發現輸入要查找的車牌號是存儲在一個一維字符數組中的,例如chara=3,使用強制類型轉換intb=(int)a,得到的b是等于51的.這是由于一個數字以字符形式存儲和以整型數據存儲它們的ASCII碼是不同的.只要將上述的強制類型轉換語句改為i

18、ntb=(int)a-48即可得到正確的結果,此問題得以解決.在實現車輛信息查找時,如果在查找前并沒有進行排序,不會輸出結果的.因此,在進行查找時,先進行.專業.整理.下載可編輯排序,這樣一來很麻煩了.經過修改,將排序函數直接加到查找函數中,這樣不管怎么樣,都排序了.五.測試結果及其分析1 .添加車輛首先會提示輸入要添加的車輛數4 4：輸巴信息5 5：退出選擇向尊執行的菜單的桀d d請輸人要添加的車鈉教.迷輸入第L L個車主內所有信息請輸入笫片卜車主的所有信息2.選擇你要執行的菜單功能3 DetnfSfi.DetnfSfi.eie,*P:WelnieXSfi.*P:WelnieXSfi.neM

19、 M? ?M MO OR R-=II由髀售型主是本顏斗車01的的為牌豐華牛車nn內人小J J | |X XIII翼饕黠椎蠢】寫字母和五個籌組曲一口人耍車的靜色二二 入讀車的車型身跑車人讀車的本主姓名工工二請輸入第*個半主的所專信息- -Q1Q1四字用馬季次黑T Te e: :一號：姓由牌盤主是魯本車口將為的加牌軍車車車凌漫嚏亥的人人長_-4|后五月五舊史舊昊你想繼竦執行菜單功能.請輸入1 1刷-0.0.否那么退出,FEFE丁6 6迭擇你要執行的菜單獨能：2 2果你想轆排執行菜單獨靛,請銜入 3 3目=瓦否那么退出,口=e e請i i先擇你要執行的菜單獨株:3 3一找成功.此車的詳細信息為： 主

20、主車髀號4646二京GGE7GGE7匹熏.專業.整理.下載可編輯六.用戶使用說明按提示操作,首先將彈出一個菜單,按提示輸入你要執行的菜單功能,選擇1,添加車輛,會提示添加的車輛數,再按提示輸入相關數據信息,輸入結束后,會提示一行字,flag=0,繼續操作,否那么退出.選擇flag=0,繼續執行菜單功能,選擇2,進行排序,選擇3,按車牌號進行查找,選擇4,是輸出所有車輛信息,5退出程序.七.參考文獻1.王昆侖、李紅主編.數據結構與算法.出版地：中國地道出版社,2022年2.李紅、王昆侖主編.“數據結構與算法設計指導2022年3.鄭莉等著.C+語言程序設計第三版.北京：清華大學出版社,2022.專

21、業.整理.F3701F3701S S京C62905BA3C62905BA36B906B904年型寶馬跑車奔馳年色紅:.pll黑南想批續執行菜單功能.請輸入門阿=見否那么退出.F F1a=11a=1翼棕嗯泄續執行菜串功能.請輸入F F%姓必否那么退出,門33S S&3Sanvkey&3Sanvkey七.conibinucconibinuc,門DebuDebuC C課程. .e e工.二四二三請選擇爾要執行的菜串功能；4 4一口八.附錄源代碼：#includestdio.h#includeiostream#includemalloc.h#includestring#defineNU

22、LL0usingnamespacestd;#defineM9/#defineN34/#defineK26/#defineRAX10/#defineMAX100/typedefstructnodeintkeynumM;charkey10;charcolor10;chartype10;charname10;structnode*next;Rnode;stringa1N=澳,JI,鄂,甘,贛,港,貴,桂,黑,滬,吉,津,晉,京,遼,魯,閩,內,寧,青,瓊,山,陜,蘇,臺,皖,湘,新,冀,渝,豫,云,藏,浙?chara2K=A,B,C,D,E,F,G,H,T,J,K,L,M,N,O,P,Q,R,S,T

23、,U,V,W7X,Y,Z;Rnode*fRAX,*rRAX;/*fRAX,*rRAX分別為鏈隊列的隊頭指針和隊尾指針longintelementMAX;intb;/汽車牌照轉換為數字后最后一個汽車牌照的數組中的下標Rnode*SetList(Rnode*L,intn)Rnode*p;intm,j,k,i;intt=0,count=1;stringr;L=NULL;for(i=0;in;i+)cout請輸入第count個車主的所有信息endl;coutendl;cout車輛的車牌號是由一個漢字,一個大寫字母和五個數字組成！endl;coutp-key;stringkey1=(string)p-k

24、ey;.專業.整理.下載可編輯stringkey2=key1.substr(0,2);for(t=0;t=0;t+)for(j=0;jkeynum0=s;s=k%10;p-keynum1=s;for(inth=0;hkey2=a2h)m=h;s=m/10;p-keynum2=s;s=m%10;p-keynum3=s;for(intn=3;nkeyn-48;p-keynumn+1=c;coutp-color;coutp-type;coutp-name;coutnext=L;L=p;returnL;voidDistribute(Rnode*L,inti)Rnode*p;intj,k;for(k=0

25、;knext;j=p-keynumi;if(fj=NULL)fj=p;elserj-next=p;/隊尾指針向后移動一位.專業.整理.下載可編輯rj=P；rj-next=NULL;P=L；Rnode*Collect()Rnode*L;inti=0,j,k;while(fi=NULL)i+;L=fi;for(j=i,k=i+1;knext=fk;j=k;returnL;intTwsearch(Rnode*L,longintkey,intlow,inthigh)intmid;if(lowhigh)return-1;elsemid=(high+low)/2;if(elementmid=key)ret

26、urnmid;elseif(keyd;stringkey1=(string)d;stringkey2=key1.substr(0,2);for(intg=0;g=0;g+)for(intj=0;jN;j+)stringkey3=(string)a1j;if(key2=key3)k=j;s=k/10*100000000+k%10*10000000;for(inth=0;hK;h+)if(d2=a2h)m=h;.專業.整理.下載可編輯s=s+m/10*1000000+m%10*100000;s=s+(longint)d3-48)*10000+(int)d4-48)*1000+(int)d5-48)

27、*100+(int)d6-48)*10+(int)d7-48;intc=Twsearch(p,s,0,b);if(c=-1)cout抱歉,沒有您要查找的記錄！endlendl;elsecout查找成功,此車的詳細信息為：endl;cout車主車牌號車色車型endl;for(inti=0;inext;coutnamekeycolortypeendl;coutendl;voidprint(Rnode*L)Rnode*p;p=L;cout車主車牌號車色車型endl;while(p!=NULL)coutnamekeycolortypenext;cout=0;i-)Distribute(L,i);L=Collect();while(q!=NULL)elementa=q-keynum0*100000000+q-keynum1*10000000+q-keynum2*1000000+q-keynum3*100000+q-keynum4*10000+q-keynum5*1000+q-keynum6*100+q-keynum7*10+q-keynum8;q=q-next;b=a;.專業.整理.下載可編輯a+;returnL;voidmain()RnodeL,*p=&L;intflag=0;intt;intm;cout車輛信息唯