廣義表的非遞歸建立與遍歷

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告班級(jí):JS000904姓名:學(xué)號(hào):張鵬E-mail:日期:◎?qū)嶒?yàn)題目:廣義表的建立與遍歷輸出◎?qū)嶒?yàn)?zāi)康模毫私鈴V義表的結(jié)構(gòu)，掌握使用非遞歸算法建立和遍歷輸出廣義表◎?qū)嶒?yàn)內(nèi)容：使用非遞歸算法，以棧為輔助，使用進(jìn)棧和出棧建立和輸出廣義表一、需求分析廣義表的結(jié)構(gòu)在生活中很常見，但要在計(jì)算機(jī)中建立一個(gè)廣義表那么比擬困難，該程序使用非遞歸算法建立廣義表并遍歷輸出，在計(jì)算機(jī)內(nèi)部的存儲(chǔ)結(jié)構(gòu)并非顯示的括號(hào)字符那么簡(jiǎn)單。故編寫該程序一方面可用于廣義表的建立與遍歷，也可鍛煉鍛煉編者使用棧的能力1、以廣義表的形式輸入，包括左右括號(hào)，逗號(hào)和其他字符。注意左右括號(hào)要配對(duì)，相鄰子表之間要用逗號(hào)隔開，每個(gè)字符之間也需要用逗號(hào)隔開，可輸入空表。如輸入“〔〔〕，〔〔a，m〕，d〕〕〞2、輸出的形式；按輸入的形式再次輸出廣義表“〔〔〕，〔〔a，m〕，d〕〕〞3、程序所能到達(dá)的功能；程序可在計(jì)算機(jī)內(nèi)部以鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)廣義表，并實(shí)現(xiàn)輸出4、測(cè)試數(shù)據(jù)：正確的輸入：〔〔〕〕，〔〔a，d〕，d〕〕正確的輸入：〔〔〕〕，〔〔a，d〕，d〕〕錯(cuò)誤的輸入：〔a，mn〕錯(cuò)誤的輸出：〔a，n〕二概要設(shè)計(jì)本程需要定義兩種類型的節(jié)點(diǎn)：1：//定義鏈表節(jié)點(diǎn)使用結(jié)構(gòu)體一共四局部一個(gè)標(biāo)志域一個(gè)數(shù)據(jù)域兩個(gè)地址域其中一個(gè)指向子表一個(gè)指向后續(xù)節(jié)點(diǎn)typedefstructGnode {……}Gnode;2：//定義棧節(jié)點(diǎn)一個(gè)域存數(shù)據(jù)且數(shù)據(jù)為鏈表節(jié)點(diǎn)類型的指針一個(gè)存后續(xù)棧節(jié)點(diǎn)指針typedefstructSnode{……}Snode;本程序共有五個(gè)模塊：1主程序模塊；2創(chuàng)立廣義表模塊；3遍歷輸出廣義表模塊；4函數(shù)模塊；5出棧模塊；各個(gè)模塊之間的關(guān)系：主程序主程序創(chuàng)立廣義表遍歷輸出廣義表進(jìn)棧出棧進(jìn)棧出棧三詳細(xì)設(shè)計(jì)1定義兩種結(jié)構(gòu)體用來作為廣義表的節(jié)點(diǎn)和鏈棧的節(jié)點(diǎn)；//定義鏈表節(jié)點(diǎn)使用結(jié)構(gòu)體一共四局部一個(gè)標(biāo)志域一個(gè)數(shù)據(jù)域兩個(gè)地址域其中一個(gè)指向子表一個(gè)指向后續(xù)節(jié)點(diǎn)typedefstructGnode { inttag; chardata; structGnode*hp; structGnode*next;}Gnode;//定義棧節(jié)點(diǎn)一個(gè)域存數(shù)據(jù)且數(shù)據(jù)為鏈表節(jié)點(diǎn)類型的指針一個(gè)存后續(xù)棧節(jié)點(diǎn)指針typedefstructSnode{ Gnode*data; structSnode*next;}Snode;2進(jìn)棧函數(shù)與出棧函數(shù)，注意函數(shù)的接口：//入棧函數(shù)將要入棧的值〔Gnode型指針〕存入棧data中返回新棧頂Snode*Push(Snode*top,Gnode*input){ Snode*s; s=(Snode*)malloc(sizeof(Snode)); s->data=input; s->next=top; top=s; return(top);}//出棧函數(shù)注意此函數(shù)中雖然只返回top，但是傳入的形參output所代表實(shí)參也發(fā)生了變化，output變?yōu)槌鰲Ｄ莻€(gè)元素的指針//并注意函數(shù)接口，傳入的形參Gnode**outputoutput為指針的指針，并且最終指向的是Gnode型的節(jié)點(diǎn)即為節(jié)點(diǎn)地址的地址Snode*Pop(Snode*top,Gnode**output){ Snode*p; if(top==NULL) { *output=NULL; returnNULL; } else { *output=top->data; p=top; top=top->next; free(p); returntop; }}3以進(jìn)棧函數(shù)和出棧函數(shù)為輔助，使用非遞歸算法建立廣義表//廣義表的建立函數(shù)Gnode*creatlist(){ Gnode*Head,*R,*P; //定義頭指針開辟節(jié)點(diǎn)的指針移動(dòng)指針 Snode*Top;//定義棧頂Top=NULL;//棧頂賦空，那么?？?charread; R=(Gnode*)malloc(sizeof(Gnode));//開辟新節(jié)點(diǎn) R->tag=1;//第一個(gè)必定為左括號(hào) scanf("%c",&read);//讀掉第一個(gè)左括號(hào)Head=R;//頭指針指向該節(jié)點(diǎn) P=Head; Top=Push(Top,P);//該節(jié)點(diǎn)指針進(jìn)棧，棧不空 R=(Gnode*)malloc(sizeof(Gnode));//再開辟一個(gè)新節(jié)點(diǎn)R->tag=-1;//標(biāo)記為-1P->hp=R;//由于上一個(gè)讀入的為左括號(hào)，故要把新節(jié)點(diǎn)鏈為當(dāng)前節(jié)點(diǎn)的子表 P->tag=1;//左括號(hào)標(biāo)記1 P->data=NULL; P=P->hp; scanf("%c",&read);//再讀入一個(gè)字符后進(jìn)入循環(huán) while(Top!=NULL)//開始時(shí)有指針進(jìn)棧，棧不空，遇到左括號(hào)進(jìn)棧，右括號(hào)退棧，故當(dāng)棧空時(shí)左右括號(hào)數(shù)目相等，循環(huán)結(jié)束 { if(read=='(')//遇到左括號(hào)，申請(qǐng)新節(jié)點(diǎn)，新節(jié)點(diǎn)標(biāo)記均作-1，當(dāng)前節(jié)點(diǎn)標(biāo)記1，指針進(jìn)棧，新節(jié)點(diǎn)鏈到當(dāng)前節(jié)點(diǎn)的子表，移動(dòng)指針 { R=(Gnode*)malloc(sizeof(Gnode)); R->tag=-1; P->hp=R; P->tag=1; P->data=NULL; Top=Push(Top,P); P=P->hp; } elseif(read==',')//遇到逗號(hào)，申請(qǐng)新節(jié)點(diǎn)，標(biāo)記-1，鏈到當(dāng)前節(jié)點(diǎn)的后續(xù)，移動(dòng)指針 { R=(Gnode*)malloc(sizeof(Gnode)); R->tag=-1; P->next=R; P=P->next; } elseif(read==')')//遇到右括號(hào)，后續(xù)域置空，棧頂指針退棧，注意調(diào)用退棧函數(shù)后P指針也發(fā)生了變化 { P->next=NULL; Top=Pop(Top,&P); } else//遇到其他字符當(dāng)前節(jié)點(diǎn)標(biāo)記為0，數(shù)據(jù)域存字符 { P->tag=0; P->data=read; P->hp=NULL; } scanf("%c",&read);//再讀入下一個(gè)字符 } P->next=NULL;//循環(huán)結(jié)束，當(dāng)前節(jié)點(diǎn)的后續(xù)置空 return(Head);}4遍歷輸出廣義表//廣義表的輸出函數(shù)voidprint(Gnode*Head){ Gnode*P; Snode*Top; P=Head;//把活動(dòng)指針指到頭節(jié)點(diǎn) Top=NULL;//棧賦空 while(P!=NULL||Top!=NULL)//p空且?？諘r(shí)退出循環(huán)，因?yàn)橐婚_始時(shí)?？?，所以需要兩個(gè)控制條件，而且P空時(shí)假設(shè)棧不空那么仍未結(jié)束 { if(P!=NULL)//如果活動(dòng)指針不空，做三種判斷 { if(P->tag==1)//遇到標(biāo)記1輸出左括號(hào)，指針進(jìn)棧，活動(dòng)指針下移 { Top=Push(Top,P); printf("("); P=P->hp; } elseif(P->tag==0)//遇到標(biāo)記0，輸出字符，如果當(dāng)前節(jié)點(diǎn)還有后續(xù)，那么要輸出逗號(hào) { printf("%c",P->data); if(P->next!=NULL){printf(",");} P=P->next; } elseif(P->tag==-1)//遇到標(biāo)記-1，先出棧，出棧后P上移輸出右括號(hào)，假設(shè)后續(xù)不空要輸出逗號(hào) { Top=Pop(Top,&P); printf(")"); if(P->next!=NULL){printf(",");} P=P->next; } } else//假設(shè)P空，表示該層結(jié)束，退棧，指針上移，假設(shè)上移后仍不為空，且此時(shí)棧必定不空，輸出右括號(hào)，假設(shè)后續(xù)不為空，需輸出逗號(hào)，指針后移 { Top=Pop(Top,&P); printf(")"); if(P->next!=NULL){printf(",");} P=P->next; } } printf("\n");}函數(shù)之間的調(diào)用關(guān)系：主函數(shù)主函數(shù)voidmain(){ Gnode*Head; printf("請(qǐng)輸入廣義表：\n"); Head=creatlist(); printf("該廣義表為：\n"); print(Head);}//主函數(shù)voidmain(){ Gnode*Head; printf("請(qǐng)輸入廣義表：\n"); Head=creatlist(); printf("該廣義表為：\n"); print(Head);}//主函數(shù)voidmain(){ Gnode*Head; printf("請(qǐng)輸入廣義表：\n"); Head=creatlist(); printf("該廣義表為：\n"); print(Head);}廣義表的建立函數(shù)Gnode*creatlist(){ Gnode*Head,*R,*P; //定義頭指針開辟節(jié)點(diǎn)的指針移動(dòng)指針 Snode*Top;//定義棧頂Top=NULL;//棧頂賦空，那么?？?charread; R=(Gnode*)malloc(sizeof(Gnode));//開辟新節(jié)點(diǎn) R->tag=1;//第一個(gè)必定為左括號(hào) scanf("%c",&read);//讀掉第一個(gè)左括號(hào)Head=R;//頭指針指向該節(jié)點(diǎn) P=Head; Top=Push(Top,P);//該節(jié)點(diǎn)指針進(jìn)棧，棧不空 R=(Gnode*)malloc(sizeof(Gnode));//再開辟一個(gè)新節(jié)點(diǎn)R->tag=-1;//標(biāo)記為-1P->hp=R;//由于上一個(gè)讀入的為左括號(hào)，故要把新節(jié)點(diǎn)鏈為當(dāng)前節(jié)點(diǎn)的子表 P->tag=1;//左括號(hào)標(biāo)記1 P->data=NULL; P=P->hp; scanf("%c",&read);//再讀入一個(gè)字符后進(jìn)入循環(huán) while(Top!=NULL)//開始時(shí)有指針進(jìn)棧，棧不空，遇到左括號(hào)進(jìn)棧，右括號(hào)退棧，故當(dāng)?？諘r(shí)左右括號(hào)數(shù)目相等，循環(huán)結(jié)束 { if(read=='(')//遇到左括號(hào)，申請(qǐng)新節(jié)點(diǎn)，新節(jié)點(diǎn)標(biāo)記均作-1，當(dāng)前節(jié)點(diǎn)標(biāo)記1，指針進(jìn)棧，新節(jié)點(diǎn)鏈到當(dāng)前節(jié)點(diǎn)的子表，移動(dòng)指針 { R=(Gnode*)malloc(sizeof(Gnode)); R->tag=-1; P->hp=R; P->tag=1; P->data=NULL; Top=Push(Top,P); P=P->hp; } elseif(read==',')//遇到逗號(hào)，申請(qǐng)新節(jié)點(diǎn)，標(biāo)記-1，鏈到當(dāng)前節(jié)點(diǎn)的后續(xù)，移動(dòng)指針 { R=(Gnode*)malloc(sizeof(Gnode)); R->tag=-1; P->next=R; P=P->next; } elseif(read==')')//遇到右括號(hào)，后續(xù)域置空，棧頂指針退棧，注意調(diào)用退棧函數(shù)后P指針也發(fā)生了變化 { P->next=NULL; Top=Pop(Top,&P); } else//遇到其他字符當(dāng)前節(jié)點(diǎn)標(biāo)記為0，數(shù)據(jù)域存字符 { P->tag=0; P->data=read; P->hp=NULL; } scanf("%c",&read);//再讀入下一個(gè)字符 } P->next=NULL;//循環(huán)結(jié)束，當(dāng)前節(jié)點(diǎn)的后續(xù)置空 return(Head);}廣義表的輸出函數(shù)voidprint(Gnode*Head){ Gnode*P; Snode*Top; P=Head;//把活動(dòng)指針指到頭節(jié)點(diǎn) Top=NULL;//棧賦空 while(P!=NULL||Top!=NULL)//p空且棧空時(shí)退出循環(huán) { if(P!=NULL)//如果活動(dòng)指針不空，做三種判斷 { if(P->tag==1)//遇到標(biāo)記1輸出左括號(hào)，指針進(jìn)棧，活動(dòng)指針下移 { Top=Push(Top,P); printf("("); P=P->hp; } elseif(P->tag==0)//遇到標(biāo)記0，輸出字符，如果當(dāng)前節(jié)點(diǎn)還有后續(xù)，那么要輸出逗號(hào) { printf("%c",P->data); if(P->next!=NULL){printf(",");} P=P->next; } elseif(P->tag==-1)//遇到標(biāo)記-1，先出棧，出棧后P上移，判斷P是否空，不空輸出右括號(hào)，假設(shè)后續(xù)不空要輸出逗號(hào) { Top=Pop(Top,&P); if(P!=NULL) { printf(")"); if(P->next!=NULL){printf(",");} P=P->next; } } } else//假設(shè)P空，表示上一層結(jié)束，退棧，指針上移，假設(shè)上移后仍不為空，且此時(shí)棧必定不空，輸出右括號(hào)，假設(shè)后續(xù)不為空，需輸出逗號(hào)，指針后移 { Top=Pop(Top,&P); if(P!=NULL) { printf(")"); if(P->next!=NULL){printf(",");} P=P->next; } } } printf("\n");}出廣義表出棧函數(shù)進(jìn)棧函數(shù)出棧函數(shù)進(jìn)棧函數(shù)四使用說明、測(cè)試分析及結(jié)果1、使用說明：使用該程序時(shí)，按界面提示輸入廣義表，按回車結(jié)束，注意廣義表的結(jié)構(gòu)，并且此程序在讀取字符時(shí)只能識(shí)別一個(gè)字符，故不能聯(lián)系輸入字母或數(shù)字；輸入空表直接用〔〕表示2、測(cè)試結(jié)果與分析：在輸入正確的廣義表之后，程序按原廣義表自動(dòng)輸出，程序運(yùn)行正常。3、調(diào)試過程中遇到的問題及解決方法及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回憶討論和分析；遇到的問題：1，在第一次設(shè)計(jì)程序時(shí)沒有考慮第一個(gè)左括號(hào)的進(jìn)棧，在進(jìn)入循環(huán)之后以?？兆鳛檠h(huán)停止的標(biāo)志，這要導(dǎo)致在除了第一個(gè)左括號(hào)之外其余的左右括號(hào)配對(duì)足夠時(shí)，不能將后續(xù)的節(jié)點(diǎn)鏈入表中；2，程序在調(diào)用出棧函數(shù)時(shí)，由于只有一個(gè)返回值，在設(shè)計(jì)程序時(shí)只返回了棧頂指針的值，而沒有出棧元素的值，這樣使得在調(diào)用了出棧函數(shù)之后指針沒有回指，程序出現(xiàn)錯(cuò)誤；3，在前幾次編寫程序時(shí)沒有考慮子表是空表的情況，使得程序不夠完善解決的方法：1，由于廣義表輸入時(shí)