數(shù)據(jù)結(jié)構(gòu)線性表的基本操作(編輯修改稿)
2025-07-27 20:54 本頁面
【文章內(nèi)容簡介】 其所建立的二叉樹的先序、中序遍歷結(jié)果一致）。四、數(shù)據(jù)結(jié)構(gòu)（1）樹要創(chuàng)建的二叉樹定義如下：typedef struct tnode{ char data。 struct tnode *lchild,*rbrother。//左孩子、右兄弟}tnode,*Tree。（2）棧定義如下：typedef struct{ Tree *top。 Tree *base。 int StackSize。}Stack。//定義棧五、模塊劃分void InitStack(Stack *S)初始化棧。 int StackEmpty(Stack S)判斷?？?，若?？辗祷?否則返回0。 void Push(Stack *S,Tree p)壓棧，將p壓入棧頂。 void Pop(Stack *S,Tree *p)出棧，將棧頂元素出棧并付給p。 int CreateTree(Tree amp。T)創(chuàng)建二叉樹T。 void PreOrderTraverse(Tree T)先序遍歷二叉樹并輸出到屏幕。 void InOrderTraverse(Tree T)中序遍歷二叉樹并輸出到屏幕。 void main()主函數(shù)，調(diào)用其他函數(shù)。六、源程序includeincludedefine OVERFLOW 2define INITSTACKSIZE 100typedef struct CSNode{ //樹的二叉鏈表存儲類型定義 int data。 struct CSNode *firstchild,*nextsibling。}CSNode,*CSTree。typedef struct{ //棧的順序存儲表示 CSTree *top。 CSTree *base。 int StackSize。}Stack。void InitStack(Stack *S){ (*S).base=(CSTree *)malloc(sizeof(CSNode))。 if(!(*S).base) exit(OVERFLOW)。 (*S).top=(*S).base。 (*S).StackSize=INITSTACKSIZE。}//構(gòu)造一個空棧int StackEmpty(Stack S){ if(==) return 1。 return 0。}//判空棧void Push(Stack *S,CSTree p){ if((*S).top(*S).base==(*S).StackSize) exit(OVERFLOW)。 *(*S).top++=p。}//進棧void Pop(Stack *S,CSTree *p){ if((*S).top==(*S).base) exit(OVERFLOW)。 *p=*(*S).top。}//出棧CSTree CreateCSTree(){ char ch。 CSTree T。 scanf(%c,amp。ch)。 if(ch==39。 39。) T=NULL。 else {if(!(T=(CSTree)malloc(sizeof(CSNode)))) exit(OVERFLOW)。 Tdata=ch。 Tfirstchild=CreateCSTree()。 Tnextsibling=CreateCSTree()。 } return T。}//建樹void Preorder(CSTree T){ //先序遍歷之非遞歸算法 CSTree p。 Stack S。 InitStack(amp。S)。 p=T。 while(p||!StackEmpty(S)){ if(p){ printf(%c,pdata)。//訪問結(jié)點 Push(amp。S,p)。 p=pfirstchild。 } else{ Pop(amp。S,amp。p)。 p=pnextsibling。 } }}//實現(xiàn)先根遍歷void PostTorder(CSTree T){ CSTree p。 Stack S。 InitStack(amp。S)。 p=T。 while(p||!StackEmpty(S)) { if(p) { Push(amp。S,p)。 p=pfirstchild。} else { Pop(amp。S,amp。p)。 printf(%c,pdata)。 p=pnextsibling。 } }}//實現(xiàn)樹的后根遍歷void main(){ CSTree T。 printf(構(gòu)造一棵樹\n)。 T=CreateCSTree()。 printf(\n樹的先根遍歷為\n)。 Preorder(T)。 printf(\n樹的后根遍歷為\n)。 PostTorder(T)。 printf(\n)。}七、測試數(shù)據(jù)樹 轉(zhuǎn)的二叉樹建立如上圖所示的樹，以字符串的形式“根 子樹”將一棵樹先序創(chuàng)建為一棵二叉樹。輸入數(shù)據(jù)次序為：ABECFDGH(為空格)。八、測試情況輸出結(jié)果： 重言式的判別，長度不超過一行，邏輯運算符包括|,amp。和~,分別表示或，與和非，運算符的優(yōu)先程度遞增，但可有括號改變，即括號內(nèi)的運算優(yōu)先。邏輯變元為大寫字母。表達式中的任何地方都可以含有多個空格符。，可以只顯示True forever或False forever, 否則顯示Satisfactible以及變量名序列，與用戶交互。若用戶對表達式中變元取定一組值，程序就求出表達式的值。，程序沒有語法檢查功能。：ADT Stack{數(shù)據(jù)對象：D={ai | ai∈IntSet，i=1，2，……，n，n≥0}數(shù)據(jù)關(guān)系：R1={ai1,ai | ai1,ai∈D,i=2，……，n}基本操作：InitStack(amp。S)操作結(jié)果：構(gòu)造一個空棧S。Push(amp。S,e)。初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(amp。S)。初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。DestroyStack(amp。s)初始條件：棧S已存在。操作結(jié)果：釋放棧S占有的內(nèi)存空間，將棧銷毀。}ADT Stack2. 本程序允許表達式中有空格，在利用算符優(yōu)先法建立二叉樹的存儲結(jié)構(gòu)之前應(yīng)將表達式中的空格刪除，利用遞歸算法借助二叉樹求出表達式的值，程序中設(shè)立軟計數(shù)器，產(chǎn)生變量的值的組合。3. 詳細設(shè)計typedef struct{ BiTree *base。 BiTree *top。 int stacksize。}Stack。/*棧的實現(xiàn)*/int InitStack(Stack amp。s){ =(BiTree *)malloc(
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1