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

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