《数据结构与算法分析——c语言描述》读后笔记 8
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《数据结构与算法分析——c语言描述》读后笔记 8,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3140字,纯文字阅读大概需要5分钟。
内容图文
二叉树
表达式树的树叶是操作数(operand),比如常数或变量,而其他的节点为操作符(operator)。这里限定操作符只能为+,-,*,/四个操作符。
把后缀表达式转变成表达式树:
程序:
//expression_tree.h
struct TreeNode; typedef struct TreeNode *PtrToNode; typedef PtrToNode Tree; typedef char Type; PtrToNode CreateNode(char ch); struct TreeNode { Type Element; Tree Left; Tree Right; };
//expression_tree.c
#include "expression_tree.h" #include<stdlib.h> #include<stdio.h> PtrToNode CreateNode(char ch) { PtrToNode p=malloc(sizeof(struct TreeNode)); if(p==NULL) { printf("The node is NULL !\n"); return p; } p->Element=ch; return p; }
//stack.h
#include "expression_tree.h" typedef Tree ElementType; #ifndef _Stack_h struct Node; typedef struct Node *Stack; int IsEmpty(Stack S); int IsFull(Stack S); Stack CreateStack( int MaxElements ); void DisposeStack(Stack S); void MakeEmpty(Stack S); void Push( ElementType X, Stack S); ElementType Top( Stack S); void Pop(Stack S); ElementType TopAndPop( Stack S ); #define EmptyTOS (-1) #define MinStackSize (5) struct Node { int Capacity; int TopOfStack; ElementType *Array; }; #endif
//stack.c
#include "stack.h" #include<stdio.h> #include<error.h> #include<stdlib.h> int IsEmpty(Stack S) { return S->TopOfStack==EmptyTOS; } int IsFull(Stack S) { return S->TopOfStack==(S->Capacity-1); } Stack CreateStack( int MaxElements ) { Stack S; if(MaxElements<MinStackSize) error(1,1,"Stack size is too small"); S=malloc(sizeof(struct Node)); if(S==NULL) error(1,1,"Out of space!!!"); S->Array=malloc(sizeof(ElementType)*MaxElements); if(S->Array==NULL) error(1,1,"Out of space!!!"); S->Capacity=MaxElements; MakeEmpty(S); return S; } void DisposeStack(Stack S) { if(S!=NULL) { free(S->Array); free(S); } } void MakeEmpty(Stack S) { S->TopOfStack=EmptyTOS; } void Push(ElementType X,Stack S) { if(IsFull(S)) error(1,1,"Full stack"); else { S->TopOfStack++; S->Array[S->TopOfStack]=X; } } ElementType Top( Stack S) { if(!IsEmpty(S)) return S->Array[S->TopOfStack]; error(1,1,"Empty stack 3"); return 0; } void Pop( Stack S) { if(IsEmpty(S)) error(1,1,"Empty stack 2"); else S->TopOfStack--; } ElementType TopAndPop( Stack S) { if(!IsEmpty(S)) { return S->Array[ S->TopOfStack--]; } error(1,1,"Empty stack 1"); return 0; }
//MainProgram.c
#include<stdio.h> #include<stdlib.h> #include<string.h> #include"stack.h" Tree CreateTree(char* str) { Tree T,p,q; int len=strlen(str); Stack S=CreateStack(len); int i; for(i=0;i<len;++i) { switch(str[i]) { case ‘+‘: case ‘-‘: case ‘*‘: case ‘/‘: { T=CreateNode(str[i]); p=TopAndPop(S); q=TopAndPop(S); T->Left=q; T->Right=p; Push(T,S); break; } default: { T=CreateNode(str[i]); Push(T,S); break; } } } return Top(S); } void outtree(Tree t) { if(t!=NULL) { outtree(t->Left); outtree(t->Right); printf("%c",t->Element); } } int main() { char* ss="ab+cde+**"; Tree TT=CreateTree(ss); outtree(TT); printf("\n"); return 0; }
利用后缀表达式构造一个表达式树,然后以后序遍历策略输出该树:
原文:http://yuzwei.blog.51cto.com/10126623/1685455
内容总结
以上是互联网集市为您收集整理的《数据结构与算法分析——c语言描述》读后笔记 8全部内容,希望文章能够帮你解决《数据结构与算法分析——c语言描述》读后笔记 8所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。