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

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