隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)(含源程序)

1、數(shù)學(xué)與計(jì)算科學(xué)學(xué)院實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)項(xiàng)目名稱隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)所屬課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)類型驗(yàn)證型實(shí)驗(yàn)日期2013年11月14日班級學(xué)號姓名成績-、實(shí)驗(yàn)概述：【實(shí)驗(yàn)?zāi)康摹筷?duì)列的邏輯結(jié)構(gòu)特征1.1是一種只允許在表的一端進(jìn)行插入，在另一端刪除元素的線性表;1.2是一種先進(jìn)先出的線性表。掌握隊(duì)列的特點(diǎn)及單鏈隊(duì)列在鏈?zhǔn)酱鎯Y(jié)構(gòu)上的實(shí)現(xiàn)。【實(shí)驗(yàn)原理】隊(duì)列的特點(diǎn)隊(duì)列是一種先進(jìn)先出的特殊線性表；隊(duì)列中，隊(duì)尾允許插入元素，隊(duì)頭允許刪除元素。單鏈隊(duì)列的類C語言隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)typedefstructQNodeQEIemTypedata;structQNode*next;QNode,*QueuePtr;typede

2、fstructQueuePtrfront;/隊(duì)頭指針QueuePtrrear;/隊(duì)尾指針LinkQueue;【實(shí)驗(yàn)環(huán)境】VC+6.0二、實(shí)驗(yàn)內(nèi)容:【實(shí)驗(yàn)方案】編寫主函數(shù)，調(diào)用初始化建空隊(duì)列、插入、刪除、銷毀隊(duì)列的算法，調(diào)試運(yùn)行，得出結(jié)果。【實(shí)驗(yàn)過程】（實(shí)驗(yàn)步驟、記錄、數(shù)據(jù)、分析）一.典型錯誤舉例1.運(yùn)行算法時(shí)遇到的典型錯誤例1:-Configuration:DebugCompiling上；*加5丘廠弓呂3訴|1童51上口戸數(shù)1居結(jié)枸卜彳幾、打也i.cppf35】：Erroir:LmtJEclBF-EididEmlLifieF上；*加5丘廠弓呂3訴|1童51上口戸數(shù)1居結(jié)枸卜彳幾、打也i.cpp

3、f35】：Erroir:LmtJEclBF-EididEmlLifieFCXOsgrsXsdnX&esktDpXfJzjfniXO-tppfSSl:errorC20：,=，!:cdniiotCftnuertfrumwstrtictQNude#BtuintThisconuersionrequiresarcinterpretastaC-stylecust-arFunction-stylecst錯誤分析：:undeclaredidentifier仔細(xì)觀察會發(fā)現(xiàn)此處是大小輸入錯誤,G.ipp導(dǎo)致報(bào)出錯誤P為定義，應(yīng)該把大寫的P改為小寫p。由于p的大小寫區(qū)別不大，因此每次在輸入時(shí)一定要格外小心，避免再出

4、現(xiàn)同樣的錯誤。例2:BiQ.cpp尸1召3油1)宦1：|卩魏*審結(jié)賀亡PPCT帝)：別-ITilF：?0E：.p士UfldEElNirFiliidFIltlFli.Fi*C:UsprssamDesfcfl-epp(3*:errorThiscanuersianrequiresareinterpretcast,EUsersAsafibe5k日|魏扌.嗒結(jié)辛勾上機(jī)-cpp(3R)terrnrC:UsersAs3fiDeskrDp?-rU0.cpp(3):errarC:Userssanbeskropg：.圧結(jié)？勾上】.cpp(39):errorCqduersionFrominite-qrailtype

5、topointertype*requiresreinterpret_castBC:UserssanDesktop|0-epp(:errarC?UH0:icannotconvertConversionFromlnti?qrailtypetopointerrequiresreinterpretjeastp執(zhí)行Cl，e時(shí)岀普一C2UD：:fannotconvertFranstru亡tQbiodetQintaC-5tylecasitorFumetian-stylecasl:C22Z7C22Z72410leftoFdatanustpaintto亡lasfi/ftruct/unifinleFto；F-ne

6、jtnustpaintto亡1ass/struet/union:cannotconurtFran1nt*tostructqHnde*C-stylecastorfunctian-stifle亡a)tFranint*tci百1:尸uttqHodeC-stylecastorfumctliDni-stjjilecaistdD.cb1error(sjptluarriing(E)錯誤分析:錯誤分析:errorC2065:*p:undeclaredidentifier表示未對P進(jìn)行定義,雙擊錯誤行，指向p=(QueuePtr)malloc(sizeof(QNode);StatusEnQueue(LinkQu

7、eue&QrQEiemTppee)插入元素e為Q的新的隊(duì)尾元素p=(QueuePtr)malloc(sizeof(QNode);iF(!p)exit(OUERFLOV/)；p-data=e:p-next=NULL;Q_rear-next=p;Qrear=p;returnOK;返回查看之后，發(fā)現(xiàn)不是把小寫p輸成大寫P了，所以錯誤就是p沒有給出定義故在所指行的前面加上QueuePtrp;對p進(jìn)行定義就可以了。2.編寫主函數(shù)時(shí)遇到的典型錯誤例：調(diào)試結(jié)果：-Cunfiguralluin：山囪-Uirk32DebugCompiling八4S.cppCUsersXsanDesktb0.epp(111fl)

8、:errorC2Q65ipDestrDijQueue1:uindeclaredidentifieK執(zhí)行cl.ewe時(shí)田措.JlAaibj1errgir(5),(Huairning(s)錯誤分析:錯誤分析:DEstrouQuEUE:und亡idEntiFiE曠表示DestroyQueue未定義,雙擊錯誤行，顯示:DestroyQueue(Q);s5t9n(*paus9);這里顯示的DestroyQueue未定義的錯誤只可能是DestroyQueue拼寫錯誤，錯誤所指行拼寫無誤，返回上面查找DestroyQueue的拼寫錯誤：StatusDestorQueue(LlnkiQuue&q)銷毀隊(duì)列Qu

9、hil?(Q,Front)將DestoryQueue改為DestroyQueue，再次調(diào)試：Configuration:40-Win32DebugCompiling.-0error(5)rSuarning(s)輸入主函數(shù)之前運(yùn)行算法時(shí)，由于后面沒有出現(xiàn)DestroyQueue，故不會出現(xiàn)前后不一致的情況，便不會報(bào)錯。完善主函數(shù)時(shí)遇到的典型錯誤例：調(diào)試結(jié)果：Configuration:CppSi-Win32DebugLinking.Cpp3U.exe-0error(s),0urarningfs)運(yùn)行結(jié)果：錯誤分析：觀察以上現(xiàn)象發(fā)現(xiàn)調(diào)試無誤，但是在輸完6個(gè)數(shù)后，卻沒有重新打印出順序棧，返回主函數(shù)初

10、始化建空棧的重新打印輸入的順序棧一行查找錯誤：For.top-s.base;i+)printf(-X的幀序聯(lián)hF重新打印輸入的順序棧printf(ll%d,*(S.base+i);printFCXn);發(fā)現(xiàn)打印順序棧的語句的位置放錯了，應(yīng)該放在for語句的前面：您輸入的順序桟)；重新打即輸入的順序桟For(i=O;KS-top-S.base;i+)printf(*dli,*(S.base+i)；改正之后運(yùn)行出結(jié)果:C:UserssamDeskto構(gòu)上機(jī)DebugCpp34.exe31425465olbeet=Bc寥_7:口b47.-f/oT-HJ/,r-F-t常#、盡兀訝y們黒初寫搠an土很諉

11、費(fèi)新SI臥s右為=-10-甘音簡捷半在程序運(yùn)行的過程中，往往容易忘記程序中算法的順序，導(dǎo)致運(yùn)行時(shí)不知怎么操作，于是在主函數(shù)中添加漢字提示，會使得程序運(yùn)行起來更加方便快捷。二測試數(shù)據(jù)1.前面幾次運(yùn)行，輸入棧的數(shù)字小而且單一，沒有代表性，于是需換些比較復(fù)雜一點(diǎn)的數(shù)字進(jìn)行測試。第一組測試，結(jié)果:C:UserssamDesktop邈據(jù)結(jié)構(gòu)上機(jī)DebugCpp34.exeV：5487736639屢舉其4L773桟頂兀恚壟e=3?勺兀素：448773ressanykeytocontinue曰IlliB639B6394487736639第二組測試，結(jié)果:nnSj678e150451-842150451i*e

12、ssanykeytoconcinu第三組測試，結(jié)果:T:UserssamDeskto結(jié)構(gòu)上機(jī)DebugCpp34.exe觀察上面的輸出窗口，發(fā)現(xiàn)此三組數(shù)據(jù)測試無誤。不會顯示任何數(shù)據(jù)，但是有一個(gè)閃動光標(biāo)暗示我們還需繼續(xù)輸入,當(dāng)輸入個(gè)數(shù)剛好等于pC:UserssamDesktopSS結(jié)彳3.當(dāng)輸入到棧中的元素不是數(shù)字而是字母時(shí)會報(bào)錯:C:UserssamDesktop磋5（據(jù)結(jié)構(gòu)上機(jī)DebugCpp34.exe3092丹陰75?03e=-8421504512.當(dāng)實(shí)際輸入的元素個(gè)數(shù)小于理論上應(yīng)該輸入的個(gè)數(shù)125456彳跖74n時(shí)，就按了Enter鍵，第三行36?77722C:UserssamDesk

13、to”鍛娠結(jié)構(gòu)上機(jī)bugCpp34.exe38?27851234567S903J561ZB1戔為灑9陰356:e-1678罠7t336977722309279S915J4S638?270S?n時(shí)，按Enter鍵，還是一樣會重新打印輸入的順序棧。請輸入懸要人棧的元素:隹的順屢松為：7590335勰晶蠡鑫器孺序桟知Pi*essansPtocontinue頂元素吝-1M6額&您聚人穩(wěn)徹簫,05I棧后的應(yīng)庠危如9G拓9舫昂無頂元辜為；-=0G74刪唏的棧頂元素后的順序棧為：亦Pressan屮kei/tocontinue?；羧氲牟畔葹?-842150451-842150451-842150451-842

14、150451-84215045142150451需歌翹費(fèi)愛雜羣;入桟后的顧序棧為：-842150451-842150451-842150451-B421504S1-8421B04S1新的瀕兀瓠棧是一種特殊的線性表，而線性表本身就是一種數(shù)據(jù)結(jié)構(gòu)，因此輸入字母是不對的【實(shí)驗(yàn)結(jié)論】（結(jié)果）C:LIserssamD笳就。p謂（據(jù)結(jié)構(gòu)上?lDebug41.exe【實(shí)驗(yàn)小結(jié)】（收獲體會）本次實(shí)驗(yàn)不僅加深了我對順序棧特點(diǎn)的理解，掌握了順序棧的基本運(yùn)算，而且實(shí)踐了用順序存儲結(jié)構(gòu)實(shí)現(xiàn)順序棧的基本操作。幾次實(shí)驗(yàn)之后，敲算法不出錯誤對我們來說已經(jīng)不是難事了，還記得第一次實(shí)驗(yàn)的時(shí)候，一堆輸入語法錯誤。因此敲算法不僅鍛

15、煉人的耐力，更能體現(xiàn)一個(gè)人做事的態(tài)度，多敲算法，多實(shí)踐總歸是好的。三、指導(dǎo)教師評語及成績：評語評語等級優(yōu)良中及格不及格1.實(shí)驗(yàn)報(bào)告按時(shí)完成，字跡清楚，文字?jǐn)⑹隽鲿?，邏輯性?qiáng)2.實(shí)驗(yàn)方案設(shè)計(jì)合理3.實(shí)驗(yàn)過程（實(shí)驗(yàn)步驟詳細(xì)，記錄完整，數(shù)據(jù)合理，分析透徹）4實(shí)驗(yàn)結(jié)論正確.成績：指導(dǎo)教師簽名：批閱日期：附錄1源程序#include#include#defineOK1#defineOVERFLOW-2#defineERROR0typedefintStatus;typedefintQEIemType;typedefstructQNodeQElemTypedata;structQNode*next;QNod

16、e,*QueuePtr;typedefstructQueuePtrfront;對頭指針QueuePtrrear;/隊(duì)尾指針LinkQueue;StatusInitQueue(LinkQueue&Q)/構(gòu)造一個(gè)空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);/存儲分配失敗Q.front-next=NULL;returnOK;StatusEnQueue(LinkQueue&Q,QEIemTypee)/插入元素e為Q的新的隊(duì)尾元素QueuePtrp;p=(QueuePtr)malloc(size

17、of(QNode);if(!p)exit(OVERFLOW);/存儲分配失敗p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,QElemType&e)/若隊(duì)列不空，則刪除Q的對頭元素，用e返回其值，并返回0K/否則返回ERRORQueuePtrp;if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;Stat

18、usDestroyQueue(LinkQueue&Q)/銷毀隊(duì)列Qwhile(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;returnOK;voidmain()LinkQueueQ;InitQueue(Q);/初始化建空隊(duì)列QueuePtrq,p;QElemTypee,n,i;printf(”請輸入您需要建立的空間個(gè)數(shù)n：);seanf(%d,&n);printf(請輸入n個(gè)數(shù):);for(i=n;iO;-i)Q.rear-next=(QueuePtr)malloc(sizeof(QNode);Q.rear=Q.rear-n

19、ext;scanf(%d,&Q.rear-data);/逐個(gè)輸入隊(duì)列元素Q.rear-next=NULL;p=Q.front;printf(輸入后的新隊(duì)列Q:);for(q=Q.front;Q.front-next;Q.front=Q.front-next)printf(%d,Q.front-next-data);printf(n);Q.front=p;printf(輸入元素e為Q的新的隊(duì)尾元素：);scanf(%d,&e);printf(”插入隊(duì)尾元素后的隊(duì)列Q:);EnQueue(Q,e);/插入新的隊(duì)尾元素，并用e返回p=Q.front;for(q=Q.front;Q.front-next;Q.front=Q.front-next)printf(%d”,Q.front-next-data);printf(n);Q.fron