數(shù)據(jù)結(jié)構(gòu)-廣義表的建立與輸出

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告◎?qū)嶒?yàn)題目:廣義表的建立與輸出◎?qū)嶒?yàn)?zāi)康模?、掌握使用VisualC++6.0上機(jī)調(diào)試程序的根本方法；掌握廣義表的存儲(chǔ)結(jié)構(gòu)，學(xué)會(huì)廣義表的建立與輸出；提高自己分析問(wèn)題和解決問(wèn)題的能力，在實(shí)踐中理解教材上的理論。◎?qū)嶒?yàn)內(nèi)容：利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立廣義表，然后輸出該廣義表，在本實(shí)驗(yàn)中不使用遞歸的方法，而是用一個(gè)棧存儲(chǔ)結(jié)點(diǎn)的指針，以此完成實(shí)驗(yàn)要求。一、需求分析1、輸入的形式和輸入值的范圍：根據(jù)提示，輸入廣義表，按回車結(jié)束。2、輸出的形式：輸出結(jié)果為上一步所輸入的廣義表。3、程序所能到達(dá)的功能：輸入廣義表后，該程序可以建立廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，之后按照一定的順序訪問(wèn)結(jié)點(diǎn)并輸出相應(yīng)的值，從而完成廣義表的輸出。4、測(cè)試數(shù)據(jù)：輸入廣義表:((),a,b,((c,(d,()))),((())))輸出結(jié)果為:((),a,b,((c,(d,()))),((())))是否繼續(xù)?〔是,輸入1;否,輸入0〕:1輸入廣義表:廣義表未建立是否繼續(xù)?〔是,輸入1;否,輸入0〕:0Pressanykeytocontinue二概要設(shè)計(jì)1、廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，因此很難為每個(gè)廣義表分配固定大小的存儲(chǔ)空間，所以其存儲(chǔ)結(jié)構(gòu)采用動(dòng)態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。每個(gè)結(jié)點(diǎn)的形式如下列圖所示。tag為標(biāo)記域：假設(shè)tag=0,表示該結(jié)點(diǎn)的sublist域不為空，假設(shè)tag=1,表示該結(jié)點(diǎn)為表結(jié)點(diǎn)，那么sublist域中存放相應(yīng)子表第一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的地址；data域：存放廣義表中的字母；sublist域：存放相應(yīng)子表第一個(gè)元素對(duì)應(yīng)結(jié)點(diǎn)的地址；next域：存放與本元素同一層的下一個(gè)元素所在結(jié)點(diǎn)的地址，當(dāng)本元素是所在層的最后一個(gè)元素時(shí)，next域?yàn)榭?。廣義表的建立本程序中利用數(shù)組存儲(chǔ)所輸入的廣義表，然后從頭到尾掃描數(shù)組中的每一個(gè)字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成。在掃描前先申請(qǐng)一個(gè)結(jié)點(diǎn)作為頭結(jié)點(diǎn)，也是當(dāng)前指針?biāo)附Y(jié)點(diǎn)，在廣義表的建立的過(guò)程中，每次申請(qǐng)一個(gè)新結(jié)點(diǎn)，需對(duì)其進(jìn)行初始化，即令標(biāo)記域?yàn)?，data域?yàn)榭?。按照本程序的思路，廣義表(a,(b,c),())的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如下列圖所示。廣義表建立的具體過(guò)程見(jiàn)詳細(xì)設(shè)計(jì)局部。廣義表的輸出在廣義表的輸出過(guò)程中也需利用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成，初始時(shí)棧為空，廣義表輸出結(jié)束后棧也為空，所以在開(kāi)始時(shí)將頭結(jié)點(diǎn)入棧，之后根據(jù)當(dāng)前指針?biāo)附Y(jié)點(diǎn)的特性的不同執(zhí)行不同的操作，以?？兆鳛閺V義表輸出的結(jié)束條件。廣義表輸出的具體過(guò)程見(jiàn)詳細(xì)設(shè)計(jì)局部。4、本程序的根本操作和模塊：建立廣義表的函數(shù)：Create(GLNode*G,SeqStack&K,chars[]) 輸出廣義表的函數(shù)：Display(GLNode*G,SeqStack&K)主函數(shù)：main()函數(shù)的調(diào)用關(guān)系如下列圖所示:開(kāi)始開(kāi)始CreateCreate函數(shù)是是DisplayDisplay函數(shù)是否繼續(xù)是否繼續(xù)否否結(jié)束結(jié)束三詳細(xì)設(shè)計(jì)元素類型、結(jié)點(diǎn)類型1、廣義表結(jié)點(diǎn)的類型描述typedefstructLNode{ inttag; //tag為結(jié)點(diǎn)中的標(biāo)記域 chardata; //data用于存儲(chǔ)廣義表中的字母 structLNode*sublist,*next; //sublist為指向下層的指針，next為指向同一層的指針 }GLNode;順序棧的類型描述typedefstruct { GLNode*pin[20]; //指針數(shù)組，用于存儲(chǔ)廣義表結(jié)點(diǎn)指針 inttop; //棧頂指針 }SeqStack;每個(gè)模塊的分析主程序模塊main(){ ①定義數(shù)組，存儲(chǔ)輸入的字符串 ②定義并申請(qǐng)頭結(jié)點(diǎn) ③初始化順序棧 ④while(1) { 調(diào)用輸入廣義表的函數(shù)，建立廣義表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 調(diào)用輸出廣義表的函數(shù)，輸出所建立的廣義表 選擇是否繼續(xù)，假設(shè)是，那么重新執(zhí)行循環(huán)中的操作；假設(shè)否，那么退出循環(huán) }}建立廣義表的函數(shù)voidCreate(GLNode*G,SeqStack&K,chars[]) { ①定義表示當(dāng)前結(jié)點(diǎn)的指針p，和表示新申請(qǐng)結(jié)點(diǎn)的指針q令p指向頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的next域?yàn)榭铡?②輸入廣義表 ③從頭到尾掃描輸入的字符，進(jìn)入以下循環(huán)，當(dāng)遇到空字符時(shí)結(jié)束循環(huán)for(j=0;s[j]!='\0';j++) { ◎假設(shè)字符為'('，執(zhí)行以下操作 { 當(dāng)前結(jié)點(diǎn)的標(biāo)記域賦值為1，表示存在子表 當(dāng)前結(jié)點(diǎn)的指針進(jìn)棧申請(qǐng)新結(jié)點(diǎn)并令其標(biāo)記域?yàn)?，data域?yàn)榭兆址? 當(dāng)前結(jié)點(diǎn)p的sublist域指向新結(jié)點(diǎn)q 將新結(jié)點(diǎn)指針賦給當(dāng)前結(jié)點(diǎn)p } ◎假設(shè)字符為','，執(zhí)行以下操作 { 申請(qǐng)新結(jié)點(diǎn)并令其標(biāo)記域?yàn)?，data域?yàn)榭兆址? 當(dāng)前結(jié)點(diǎn)p的next域指向新結(jié)點(diǎn)q 將新結(jié)點(diǎn)指針賦給當(dāng)前結(jié)點(diǎn)p } ◎假設(shè)字符為')'，執(zhí)行以下操作 { 令當(dāng)前結(jié)點(diǎn)p的next域?yàn)榭? 出棧，將棧頂元素賦給當(dāng)前結(jié)點(diǎn)q } ◎假設(shè)字符為字母，執(zhí)行以下操作 { 令當(dāng)前結(jié)點(diǎn)p的data域?yàn)樵撟帜? 令當(dāng)前結(jié)點(diǎn)的sublist域?yàn)榭? }}}輸出廣義表的函數(shù)voidDisplay(GLNode*G,SeqStack&K) { ①定義表示當(dāng)前結(jié)點(diǎn)的指針p，并令p指向頭結(jié)點(diǎn)。 ②指向頭結(jié)點(diǎn)的指針p入棧,使棧不空，輸出廣義表里的第一個(gè)左括號(hào)'('。 ③將當(dāng)前結(jié)點(diǎn)p的sublist域所指結(jié)點(diǎn)賦給p。④當(dāng)棧不空時(shí)執(zhí)行以下操作 while(K.top!=-1) { ◎假設(shè)當(dāng)前結(jié)點(diǎn)指針p不為空，執(zhí)行以下操作 { 假設(shè)當(dāng)前結(jié)點(diǎn)標(biāo)記域?yàn)?,執(zhí)行以下操作 { 輸出'('，并當(dāng)前結(jié)點(diǎn)指針p入棧 將當(dāng)前結(jié)點(diǎn)p的sublist域所指結(jié)點(diǎn)賦給p } 假設(shè)當(dāng)前結(jié)點(diǎn)標(biāo)記域?yàn)?,執(zhí)行以下操作 { 假設(shè)當(dāng)前結(jié)點(diǎn)p的date域存有字母那么輸出該字母 假設(shè)當(dāng)前結(jié)點(diǎn)p的next域不為空，表示不是該層的結(jié)束，輸出',' 將當(dāng)前結(jié)點(diǎn)p的next域所指結(jié)點(diǎn)賦給p } } ◎假設(shè)當(dāng)前結(jié)點(diǎn)指針為空，執(zhí)行以下操作 { 輸出')' 出棧，將棧頂元素賦給當(dāng)前結(jié)點(diǎn)p， 假設(shè)當(dāng)前結(jié)點(diǎn)p的next域不為空，表示不是該層的結(jié)束，輸出',' 將當(dāng)前結(jié)點(diǎn)p的next域所指結(jié)點(diǎn)賦給p } }}四使用說(shuō)明、測(cè)試分析及結(jié)果程序使用說(shuō)明：本程序運(yùn)行環(huán)境為VisualC++6.0；根據(jù)界面提示進(jìn)行操作,注意輸入的字符為西文字符測(cè)試結(jié)果與分析：頁(yè)面提示“輸入廣義表：”輸入“((),a,b,((c,(d,()))),((())))”，按回車確定，頁(yè)面顯示如下：“ 輸出結(jié)果為:((),a,b,((c,(d,()))),((())))是否繼續(xù)?〔是,輸入1;否,輸入0〕: ”輸入序號(hào)“1”，按回車確定，表示繼續(xù)操作。頁(yè)面提示“輸入廣義表：”不輸入廣義表，直接按回車確定，那么頁(yè)面顯示如下：“ 廣義表未建立是否繼續(xù)?〔是,輸入1;否,輸入0〕: ”輸入序號(hào)“0”，按回車確定，表示結(jié)束操作，頁(yè)面顯示如下：“ Pressanykeytocontinue ”由上測(cè)試結(jié)果分析得，該程序功能滿足題目要求。調(diào)試過(guò)程中遇到的問(wèn)題及解決方法①當(dāng)代碼編寫完成后，編譯過(guò)程出現(xiàn)了很多小錯(cuò)誤，比方語(yǔ)句末尾漏掉分號(hào)，使用了某些變量卻未定義，但這些問(wèn)題很快發(fā)現(xiàn)并及時(shí)糾正；②在建立廣義表的函數(shù)中，建立結(jié)點(diǎn)后對(duì)其data域賦值不完整，一些特殊結(jié)點(diǎn)指針域的說(shuō)明也不完整，導(dǎo)致輸出結(jié)果有問(wèn)題。于是回頭進(jìn)一步梳理思路，是細(xì)節(jié)局部更加嚴(yán)謹(jǐn)，最后修改正確；③更多的問(wèn)題出現(xiàn)在了輸出廣義表的函數(shù)中，剛開(kāi)始出現(xiàn)廣義表的輸出少括號(hào)或多括號(hào)的情況，這里有一局部原因是建立廣義表的函數(shù)的問(wèn)題，兩局部同時(shí)作的修改。之后又出現(xiàn)輸入復(fù)雜的廣義表時(shí)，局部字母不能輸出，多重括號(hào)的輸出也只能輸出兩個(gè)，認(rèn)真分析后，發(fā)現(xiàn)還是對(duì)廣義表中右括號(hào)的處理不夠完善，于是在輸出時(shí)，進(jìn)一步細(xì)化了輸出結(jié)果的條件，比方對(duì)“〔a,b)”和“〔〕”這兩種形式采取不同的輸出條件和輸出結(jié)果。在不斷地查找問(wèn)題和完善中，最終修改正確。運(yùn)行界面五、實(shí)驗(yàn)總結(jié)因?yàn)楸敬螌?shí)驗(yàn)花費(fèi)了很多時(shí)間思考算法，所以在編寫程序上花費(fèi)的時(shí)間不算太多，我在10月26日晚上寫完代碼，并于當(dāng)天修改正確。在本次編寫程序過(guò)程中，問(wèn)題主要發(fā)生在輸出廣義表的函數(shù)上，反復(fù)查找思路中不嚴(yán)謹(jǐn)?shù)牡胤?，結(jié)合對(duì)輸入廣義表的函數(shù)的修改，一點(diǎn)一點(diǎn)地改良，最后才得以修改正確。在上次試驗(yàn)完成后便開(kāi)始思考和與別人討論可以實(shí)現(xiàn)題目要求的算法，最初的算法不夠完善，主要只考慮了簡(jiǎn)單的廣義表，但是對(duì)廣義表中出現(xiàn)多層括號(hào)等一些特殊情況的思考不夠深入，在與同學(xué)進(jìn)行了討論后，最后確定下來(lái)本實(shí)驗(yàn)中所采用的思路。因?yàn)樗媒滩纳蠈?duì)廣義表的講解很少，所以參考了一些其它資料。本次實(shí)驗(yàn)，我很感謝老師和同學(xué)對(duì)我的指點(diǎn)。通過(guò)本次實(shí)驗(yàn)，對(duì)廣義表的存儲(chǔ)結(jié)構(gòu)有了更深的認(rèn)識(shí)，對(duì)一些細(xì)節(jié)更加理解，收獲了很多。教師評(píng)語(yǔ)： 首先，我強(qiáng)調(diào)一下要注意細(xì)節(jié)，不管是對(duì)你而言簡(jiǎn)單的局部還是復(fù)雜的局部，這些都會(huì)影響你程序的編譯和調(diào)試，另外，在充分考慮并設(shè)計(jì)好程序后在進(jìn)行編寫操作這是一個(gè)良好的習(xí)慣，這樣能夠提高你的編程效率，降低出錯(cuò)的可能性，當(dāng)然，最好的話細(xì)分模塊是一個(gè)比擬好的習(xí)慣，當(dāng)然這主要是針對(duì)大型程序而言。實(shí)驗(yàn)成績(jī)：99指導(dǎo)教師簽名：批閱日期：代碼：#include<stdio.h>#include<stdlib.h>//——————————————————————————————————————————typedefstructLNode //廣義表結(jié)點(diǎn)的類型描述{ inttag; //tag為結(jié)點(diǎn)中的標(biāo)記域 chardata; //data用于存儲(chǔ)廣義表中的字母 structLNode*sublist,*next; //sublist為指向該結(jié)點(diǎn)下一層的指針，next為指向該結(jié)點(diǎn)同一層的指針}GLNode;//——————————————————————————————————————————typedefstruct //順序棧的類型描述{ GLNode*pin[20]; //指針數(shù)組，用于存儲(chǔ)廣義表結(jié)點(diǎn)指針 inttop; //棧頂指針}SeqStack;//——————————————————————————————————————————voidCreate(GLNode*G,SeqStack&K,chars[]) //建立廣義表函數(shù){ GLNode*p,*q; //p指針指向當(dāng)前結(jié)點(diǎn),q指針指向新申請(qǐng)的結(jié)點(diǎn) intj; //j用于標(biāo)記輸入的字符在數(shù)組中的位置 printf("輸入廣義表:"); //提示輸入廣義表的 gets(s); p=G; //令p指向頭結(jié)點(diǎn) p->next=NULL; //頭結(jié)點(diǎn)的next域?yàn)榭?for(j=0;s[j]!='\0';j++) //進(jìn)入循環(huán)，建立廣義表 { if(s[j]=='(') //假設(shè)字符為'('，執(zhí)行以下操作 { p->tag=1; //當(dāng)前結(jié)點(diǎn)的標(biāo)記域賦值為1，表示存在子表 K.top++; //當(dāng)前結(jié)點(diǎn)的指針進(jìn)棧 K.pin[K.top]=p; q=(GLNode*)malloc(sizeof(GLNode)); //申請(qǐng)新結(jié)點(diǎn) q->tag=0; //初始化新結(jié)點(diǎn)，標(biāo)記域賦值為0，data域賦空字符 q->data=NULL; p->sublist=q; //當(dāng)前結(jié)點(diǎn)的sublist域指向新申請(qǐng)的結(jié)點(diǎn) p=q; //令新申請(qǐng)的結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn) } else { if(s[j]==',') //假設(shè)字符為','，執(zhí)行以下操作 { q=(GLNode*)malloc(sizeof(GLNode)); //申請(qǐng)新結(jié)點(diǎn) q->tag=0; //初始化新結(jié)點(diǎn)，標(biāo)記域賦值為0，data域賦空字符 q->data=NULL; p->next=q; //當(dāng)前結(jié)點(diǎn)的next域指向新申請(qǐng)的結(jié)點(diǎn) p=q; //令新申請(qǐng)的結(jié)點(diǎn)成為當(dāng)前結(jié)點(diǎn) } else { if(s[j]==')') //假設(shè)字符為')'，執(zhí)行以下操作 { p->next=NULL; //令當(dāng)前結(jié)點(diǎn)的next域?yàn)榭? p=K.pin[K.top]; //出棧，令當(dāng)前結(jié)點(diǎn)為棧頂元素 K.top--; } else //假設(shè)字符為字母，執(zhí)行以下操作 { p->data=s[j]; //令當(dāng)前結(jié)點(diǎn)的data域?yàn)樵撟帜? p->sublist=NULL; //當(dāng)前結(jié)點(diǎn)的sublist域?yàn)榭? } } } }}//——————————————————————————————————————————voidDisplay(GLNode*G,SeqStack&K) //輸出廣義表的函數(shù){ printf("輸出結(jié)果為:"); //提示以下結(jié)果為輸出的廣義表 GLNode*p; //p指針指向當(dāng)前結(jié)點(diǎn) p=G; //初始時(shí)p指針指向頭結(jié)點(diǎn) K.top++; //指向頭結(jié)點(diǎn)的指針入棧 K.pin[K.top]=p; printf("("); //輸出第一個(gè)'(' p=p->sublist; //令當(dāng)前結(jié)點(diǎn)的sublist域所指結(jié)點(diǎn)為新的當(dāng)前結(jié)點(diǎn) while(K.top!=-1) //當(dāng)棧不為空時(shí)執(zhí)行以下操作 { if(p!=NULL) //假設(shè)當(dāng)前結(jié)點(diǎn)指針不為空，執(zhí)行以下操作 { if(p->tag==1) //假設(shè)當(dāng)前結(jié)點(diǎn)標(biāo)記域?yàn)?,執(zhí)行以下操作 { printf("("); //輸出'(' K.top++; //當(dāng)前結(jié)點(diǎn)指針入棧 K.pin[K.top]=p; p=p->sublist; //令當(dāng)前結(jié)點(diǎn)的sublist域成為當(dāng)前結(jié)點(diǎn) } else //假設(shè)當(dāng)前結(jié)點(diǎn)標(biāo)記域?yàn)?,執(zhí)行以下操作 { if(p->data!=NULL) //假設(shè)當(dāng)前結(jié)點(diǎn)的date域存有字母那么輸出該字母 printf("%c",p->data); if(p->next!=NULL)printf(","); //假設(shè)當(dāng)前結(jié)點(diǎn)的next域不為空，表示不是該層的最后一個(gè)結(jié)點(diǎn)，輸出',' p=p->next; //令當(dāng)前結(jié)點(diǎn)的next域成為當(dāng)前結(jié)點(diǎn) } } else //假設(shè)當(dāng)前結(jié)點(diǎn)指針為空，執(zhí)行以下操作 { p=K.pin[K.top];