數(shù)據(jù)結(jié)構(gòu)實習(xí)報告

數(shù)據(jù)構(gòu)造課程實習(xí)匯報姓名：王倩倩學(xué)號：1002193班號：116102-12指導(dǎo)老師:陳亮、陳占龍中國地質(zhì)大學(xué)信息工程學(xué)院/2/13實習(xí)匯報內(nèi)容停車場管理系統(tǒng)（1）需求規(guī)格闡明【問題描述】：設(shè)停車場是一種可停放n輛汽車的狹長通道，且只有一種大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛抵達(dá)時間的先后次序，依次由北向南排列（大門在最南端，最先抵達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等待，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述規(guī)定進(jìn)行管理的模擬程序。【基本規(guī)定】：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“抵達(dá)”或“拜別”信息，汽車牌照號以及抵達(dá)或拜別的時刻。對每一組輸入的數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛抵達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛拜別，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。棧以次序構(gòu)造實現(xiàn)，隊列以鏈表構(gòu)造實現(xiàn)。（2）總體分析與設(shè)計【算法設(shè)計】設(shè)計思想：用棧來模擬停車場，隊列用來模擬便道，根據(jù)主界面輸入的數(shù)據(jù)來對停車場進(jìn)行管理，創(chuàng)立一種構(gòu)造體Car用它來存儲有關(guān)汽車的所有信息（車牌號、停入的時間信息等），當(dāng)一種車進(jìn)入停車場時把車子的信息存入構(gòu)造體中，然后對構(gòu)造體Car進(jìn)行壓棧，或壓入隊列，并輸出車子的停車信息；當(dāng)車子離開時，把構(gòu)造體從棧中彈出，并根據(jù)離開時間計算出停車所需的停車費用。主界面二、設(shè)計表達(dá)：主界面退出系統(tǒng)停車費用查詢便道車輛查詢車輛離開車輛抵達(dá)退出系統(tǒng)停車費用查詢便道車輛查詢車輛離開車輛抵達(dá)Add()Arrival()Add()Add()Arrival()Add()QueueStackIsFull()QueueStackIsFull()Delete()IsEmpty（）Delete()IsEmpty（）Leave()leaveDelete()()Leave()leaveDelete()()（3）程序構(gòu)造分析：由于停車場中，每輛車子都是按次序停入的，要有先后次序，且只有一種進(jìn)出口，后進(jìn)先出，因此要用棧模擬的停車場，創(chuàng)立一種構(gòu)造體存入車輛信息，車子進(jìn)入停車場時用Stack的Add（）函數(shù)把已存入車輛信息的構(gòu)造體對象進(jìn)行壓棧，當(dāng)停車場停滿即棧滿時，用Queue的Add（）函數(shù)把車子停入此外一種便道，讓車子在便道等待，等棧內(nèi)有空位時，再將車停入停車場；當(dāng)車輛離開時先用Leave（）函數(shù)判斷，車子與否在停車場中，若在Leave（）函數(shù)調(diào)用Stack的Delete（）函數(shù)，若不在輸出“您要查找的車不在！”。（4）編程碰到的問題計算法改善：1、有關(guān)車輛信息的保留：由于車輛信息需要保留不止一項，因此需要建立一種可以保留信息的東西，剛開始我用的是類，信息雖然存進(jìn)去了可是類卻不會壓棧，最終放棄，創(chuàng)立一種構(gòu)造體Car，它功能和類差不多并且應(yīng)用比較簡樸。2、車輛離開時的判斷：當(dāng)車輛離開時，首先要判斷車子與否在停車站內(nèi)，當(dāng)棧不為空時，從棧頂開始一種個判斷輸入的車牌號與否在棧內(nèi)，這時就用到了Top（）函數(shù)判等（park.Top().carnumber==Carnumber）若不等尋找下一種，若相等把它彈出棧。（5）編碼定義構(gòu)造體Car：structCar{intcarnumber; inthour; intmin;};車輛抵達(dá)時的Arrival（）函數(shù)：intArrival(){CarCa;cout<<"請輸入車牌號:"; cin>>Ca.carnumber; cout<<"請輸入車輛停入時間:"<<endl; cin>>Ca.hour; cin>>Ca.min; cout<<"目前時間為:"<<Ca.hour<<":"<<Ca.min<<endl;if(park.IsFull()){cout<<"目前停車位已滿，請到便道等待！"<<endl; wait.Add(Ca); i++; cout<<"目前車子位置在："<<i<<endl; } Elsepark.Add(Ca); j++; cout<<"目前車子的位置在："<<j<<endl; return0;}車輛離開是的Leave（）函數(shù)：intLeave(){ // Stack<Car>park(2); // Stack<Car>tem(2); intCarnumber; intH,M; cout<<"請輸入車牌號:"; cin>>Carnumber; CarC; charm; if(!park.IsEmpty()) { while(park.Top().carnumber!=Carnumber) { park.Delete(C); j--; tem.Add(C); m++; if(park.IsEmpty()) {cout<<"您要查找的車不在！"<<endl;} } if(park.Top().carnumber==Carnumber) { park.Delete(C); j--; cout<<"請輸入車輛離開時間:"<<endl; cin>>H>>M; cout<<"目前時間為:"<<H<<":"<<M<<endl; intprice; price=((H-C.hour)*60+(M-C.min))*5; cout<<"應(yīng)繳費用為："<<price<<endl; } } else cout<<"您要查找的車不在！"<<endl; return0;}停車費用的計算：cout<<"請輸入車輛停入時間："; intinhour,inmin; cin>>inhour>>inmin; cout<<"請輸入車輛離開時間："; intouhour,oumin; cin>>ouhour>>oumin; cout<<"應(yīng)繳納的費用為："<<((ouhour-inhour)*60+(oumin-inmin))*0.5<<endl;break;主界面的設(shè)計即main（）函數(shù)：intmain(){ //LinkedQueuequeue; cout<<"歡迎進(jìn)入停車場管理系統(tǒng),很快樂為您服務(wù)!"<<endl; cout<<"請選擇您要進(jìn)行的操作:"<<endl; cout<<"A:車輛停入;"<<endl; cout<<"D:車輛離開;"<<endl; cout<<"B:便道車輛查詢；"<<endl; cout<<"F:停車費用查詢；"<<endl; cout<<"K:退出系統(tǒng);"<<endl; chara; do{ cin>>a; { switch(a) { case'A':Arrival();break; case'D':Leave();break; case'B':break; case'F':cout<<"請輸入車輛停入時間："; intinhour,inmin; cin>>inhour>>inmin; cout<<"請輸入車輛離開時間："; intouhour,oumin; cin>>ouhour>>oumin; cout<<"應(yīng)繳納的費用為："<<((ouhour-inhour)*60+(oumin-inmin))*0.5<<endl;break; case'K':cout<<"謝謝您的使用！"<<endl;break; default:break; } } }while(a!='k'); return0;}（6）附錄：運行成果1、主界面設(shè)計：2、有關(guān)車輛停入：3、車輛離開：4、停車費用的查詢：5、退出系統(tǒng)：二、排序應(yīng)用（職工分房排序）（1）需求規(guī)格闡明【問題描述】：假定文本文獻(xiàn)A1.txt中是我校所有參與南望山莊二期挑房職工的信息，請編寫程序，讀出文獻(xiàn)中的內(nèi)容，再按挑房的先后次序排隊后將排序號和姓名以文本方式寄存到文獻(xiàn)A2.txt中。排隊原則：先按職稱排，同職稱按分房工齡排，同工齡按年齡排。職稱編號：校級干部0專家、正處級1副專家、副處級2講師、科級3其他4【基本規(guī)定】：本題由于排序所需的數(shù)據(jù)放在一種文本文獻(xiàn)中，因此要在程序中建立程序和文本文獻(xiàn)的聯(lián)絡(luò)，讀入文本文獻(xiàn)，在程序中進(jìn)行排序，然后再輸出并保留在此外一種文本文獻(xiàn)中。（2）總體設(shè)計與規(guī)定【算法設(shè)計】：設(shè)計思想：Infile（）函數(shù)a1文本SInfile（）函數(shù)a1文本Swap（）函數(shù)a2文本Outfile（）函數(shù)a2文本Outfile（）函數(shù)Bubble（）函數(shù)設(shè)計表達(dá)：主函數(shù)：main（）互換位置函數(shù)：swap（）排序函數(shù)（冒泡排序）：bubble（）讀入文獻(xiàn)：infile（）讀出文獻(xiàn)：outfile（）（3）程序構(gòu)造分析：在本程序中重要考慮的是怎樣把程序和外存中的文本聯(lián)絡(luò)起來，尚有一種冒泡排序，因此程序總體構(gòu)造不是太復(fù)雜，只要將文本的讀入和讀出尚有排序關(guān)系處理好就沒問題了。（4）編程碰到的問題及改善措施：由于程序自身不是太難，因此碰到的問題也就不是諸多，一般都是小問題，尚有一種值得尤其注意的地方就是，由于本題中排序需要比較的數(shù)據(jù)有三個，因此要寫三個排序用for循環(huán)來嵌套。（5）編碼1、存儲教師信息的構(gòu)造體：structteacher{ charname[10]; intzhicheng; intworktime; intage;};2、有關(guān)排序:voidswap(int&a,int&b){ intt; t=a; a=b; b=t; }voidBubble(teacher*tea,intn=510){ for(inti=1;i<n;i++) { for(intj=0;j<n-i;j++) { if(tea[j].zhicheng>tea[j+1].zhicheng) { swap(tea[j],tea[j+1]); } else if(tea[j].zhicheng==tea[j+1].zhicheng) { if(tea[j].worktime<tea[j+1].worktime) { swap(tea[j],tea[j+1]); } elseif(tea[j].worktime==tea[j+1].worktime) { if(tea[j].age<tea[j+1].age) { swap(tea[j],tea[j+1]); } } } } }}3、文本文獻(xiàn)的讀入和讀出：ifstreaminfile("a1.txt"); ofstreamoutfile("a2.txt"); charline[50]; while(!infile.) infile.getline(line,50); outfile<<line<<endl; infile.close(); for(intm=0;m<510;m++) { infile>>Name>>Zhicheng>>Worktime>>Age; strcpy(tea[m].name,Name); tea[m].zhicheng=Zhicheng; tea[m].worktime=Worktime; tea[m].age=Age; }//teachera[505];//intn; for(inti=n;i>1;i--) Bubble(tea,550); for(inti=0;i<550;i++) { oufile<<setiosflags(ios_base::left)<<setw(13)<<tea[j].name<<setw(8)<<tea[j].zhicheng<<setw(8)<<tea[j].worktime<<setw(8)<<tea[j].age<<endl; // outfile<<tea[i].name<<""<<tea[i].zhicheng<<""<<tea[i].worktime<<""<<tea[i].age<<endl; // outfile.close(); }（6）附錄：運行成果運行前：運行后：三、電話號碼查詢：（1）需求規(guī)格闡明：【問題描述】：人們在平常生活中常常需要查找某個人或某個單位的電話號碼，本試驗將實現(xiàn)一種簡樸的個人電話號碼查詢系統(tǒng)，根據(jù)顧客輸入的信息（例如姓名等）進(jìn)行迅速查詢?！净疽?guī)定】：（1）在外存上，用文獻(xiàn)保留電話號碼信息；（2）在內(nèi)存中，設(shè)計數(shù)據(jù)構(gòu)造存儲電話號碼信息；（3）提供查詢功能：根據(jù)姓名實現(xiàn)迅速查詢；（4）提供其他維護(hù)功能：例如插入、刪除、修改等。（2）總體設(shè)計與規(guī)定：【算法設(shè)計】：設(shè)計思想：由于需要管理的電話號碼信息較多，并且要在程序運行結(jié)束后仍然保留電話號碼信息，因此電話號碼信息采用文獻(xiàn)的形式寄存到外存中。在系統(tǒng)運行時，需要將電話號碼信息從文獻(xiàn)調(diào)入內(nèi)存來進(jìn)行查找等操作，為了接受文獻(xiàn)中的內(nèi)容，要有一種數(shù)據(jù)構(gòu)造TeleNumber與之對應(yīng)，里面保留著人們的電話信息（固定電話、移動電話和電子郵箱），并設(shè)計一種鏈表類classTele來對系統(tǒng)進(jìn)行操作。Insert（）Insert（）插入主界面Show（）顯示主界面Show（）ClassTeleDelete（）刪除ClassTeleDelete（）Sort（）排序Sort（）a1.txtChange（）修改a1.txtChange（）Search（）Search（）Save（）Save（）（3）程序構(gòu)造分析：本題相對于分房排序來說難度有所增長，由于分房排序中對內(nèi)存沒有規(guī)定，只需將外存文獻(xiàn)讀入，在內(nèi)存中進(jìn)行排序然后再輸出就好了。而本題還需要將電話號碼信息在內(nèi)存中，需要建立一種存儲構(gòu)造與外存文獻(xiàn)相對應(yīng)。（4）編程碰到的問題及改善措施：由于本題需要在內(nèi)存中建立一種對應(yīng)的存儲構(gòu)造與外存文獻(xiàn)相對應(yīng)，剛開始時根據(jù)老師說的建立二叉搜索樹進(jìn)行排序，由于對我來說難度太大，因此把它改成了冒泡排序法，它要比二叉搜索樹慢些。（5）編碼：電話號碼（構(gòu)造體）：structTeleNumber{ charname[10];//姓名intphoneNumber;//固定電話號碼intmobileNumber;//移動電話號碼charemail[10];//電子郵箱 ints; TeleNumber*Next; voidReadFile(istream&infile); voidinput(); voiddisplay();};對系統(tǒng)進(jìn)行操作的Tele類：classTele//功能類{ public: Tele();//構(gòu)造函數(shù) ~Tele();//析構(gòu)函數(shù) voidSave();//數(shù)據(jù)保留到文獻(xiàn) TeleNumber*Search(char*);//信息查找 voidSort();//排序 voidInsert();//插入 voidDelete();//刪除 voidChange();//更改個人信息 voidShow();//顯示個人信息 voidSwap(TeleNumber*,TeleNumber*); private: TeleNumber*End,*Head; ifstreaminfile;//定義讀，寫文獻(xiàn)對象 ofstreamoutfile;};在Tele的構(gòu)造函數(shù)中建立單鏈表存儲構(gòu)造體TeleNumber：Tele::Tele(){ Head=newTeleNumber;//頭插法建立單鏈表 Head->Next=newTeleNumber; End=Head->Next; infile.open("a1.text");//打開外存文獻(xiàn)，看與否有數(shù)據(jù)存在 while(!infile.eof())//假如有，則打開，并將數(shù)據(jù)讀取到程序 { End->ReadFile(infile); if(End->name[0]=='\0')break; End->Next=newTeleNumber; End=End->Next; } // infile.close(); }文獻(xiàn)保留：voidTele::Save()//保留文獻(xiàn){ outfile.open("a1.txt");//建立外存文獻(xiàn)a1.txt for(TeleNumber*p=Head->Next;p!=End;p=p->Next) outfile<<p->name<<""<<p->phoneNumber<<""<<p->mobileNumber<<""<<p->email<<endl;//將數(shù)據(jù)存到外存文獻(xiàn)里 outfile.close(); cout<<"保留成功！"<<endl;}主界面及其功能設(shè)計：intmain(){ boolflag=true; Teletele; charname[20]; while(flag) { //system("cls"); Cout<<“個人電話號碼查詢系統(tǒng)"<<endl; cout<<"請選擇您所需要的操作："<<endl; cout<<"A.增長電話號碼"<<endl; cout<<”B.顯示電話號碼"<<endl; cout<<"C.排序個人電話"<<endl; cout<<"D.查找個人電話"<<endl; cout<<"E.刪除個人信息"<<endl; cout<<"F.修改個人信息"<<endl; cout<<"G.保留個人信息"<<endl; cout<<"K.退出系統(tǒng)"<<endl;charx; do{ cin>>x; { switch(x) { case'A':tele.Insert();break; case'B':tele.Show();break; case'C':tele.Sort();break; case'D':cout<<"請輸入查找人姓名"<<endl; cin>>name; tele.Search(name);break; case'E':tele.Delete();break; case'F':tele.Change();break; case'G':tele.Save();break; case'K':cout<<"謝謝您的使用！"<<endl; default:break; } } }while(x!='K'); } return0;}（6）附錄：運行成果查找：修改：四、火燒連營（1）需求規(guī)格闡明：【問題描述】：“火燒連營”是三國演義中的著名典故之一廣為流傳，假定文本文獻(xiàn)c1.txt是火燒連營中的軍營分布圖，每個字符A代表一種營帳，營帳是可燃物，其他字符代表不可燃的空白地段，文獻(xiàn)共有40行70列，從鍵盤輸入任意點的x和y值（x<70,y<40）作為著火點，“火燒連營”后，被燃燒的營帳標(biāo)上字符’X’。【基本規(guī)定】：從文本c1.txt讀入內(nèi)容，再從鍵盤輸入任意點的x和y值（x<70,y<40）作為著火點，“火燒連營”后，被燃燒的營帳標(biāo)上字符’X’，并把整個成果輸出到文獻(xiàn)c2.txt（2）總體設(shè)計與規(guī)定：【算法設(shè)計】：設(shè)計思想：在上課時老師給我們講過一種迷宮的例子，就是從一種點出發(fā)，前后左右遍歷跟這個點有關(guān)聯(lián)的連通點，而這道題目就和迷宮題有相似之處，只要開辟一種堆棧，先將著火點壓棧，然后反復(fù)一下操作：棧頂點出棧并標(biāo)識X，同步將符合被燃燒條件的鄰居點入棧。。。。，直到棧空為止。設(shè)計表達(dá)：讀入數(shù)據(jù)Infile.c1.txt讀入數(shù)據(jù)Infile.c1.txtFile.IsEmpty（）File.IsEmpty（）fire.[i][j]fire.[i][j]判斷與否可燃判斷與否可燃著火點壓棧yazhan著火點壓棧yazhanDeleteDelete（）Stack.FStack.File.Add()可燃點彈出輸出成果輸出成果（3）程序構(gòu)造分析:本程序雖然也是波及到外存與內(nèi)存但沒有規(guī)定互相對應(yīng)，只需將外存數(shù)據(jù)讀入內(nèi)存，在內(nèi)存中把著火點表達(dá)出來就好了，因此相對來說還是比電話號碼查詢要簡樸，最重要的環(huán)節(jié)就是前后左右遍歷著火點，直到所有與之連通點都被遍歷就好了，這需要幾種if語句想嵌套就好了。(