数据结构课程设计(4)

{

char *Data; int Top; }Stack;

void InitStack(Stack &s); void Push(Stack &s,char e); void Pop(Stack &s,char e); char Pop(Stack &s); int IsEmpty(Stack s); int IsFull(Stack s); char CalExp(char exp[]); void expressionmenu(); #endif

表达式的源文件 #include #include #include \

void InitStack(Stack &s) {

s.Data = (char*)malloc(N*sizeof(char)); s.Top = -1; }

void Push(Stack &s,char e) {

if(s.Top==N) {

printf(\栈溢出\ } else {

s.Top++;

s.Data[s.Top] = e; } }

void Pop(Stack &s,char e) {

if(s.Top< 0 ) {

printf(\栈为空\ } else {

e = s.Data[s.Top]; s.Top--;

14

} }

char Pop(Stack &s) {

char e;

if(s.Top< 0 ) {

printf(\栈为空\ } else {

e = s.Data[s.Top]; s.Top--; }

return e; }

int IsEmpty(Stack s) {

if(s.Top< 0 ) return 1; return 0; }

int IsFull(Stack s) {

if(s.Top==N ) return 1; return 0; }

int IsOperator(char ch) {

if(ch=='+' || ch =='-' || ch =='*'||ch=='/'||ch=='#') return 1; return 0; }

char Calculate(char a, char oper,char b) {

int c; int aa,bb; aa = atoi(&a); bb = atoi(&b); switch(oper) {

case '+':

15

c = aa + bb; break; case '-':

c = bb - aa; break; case '*':

c = aa * bb; break; case '/':

c = bb / aa; break; }

return c+'0'; }

char CalExp(char exp[]) {

Stack s; char a,b,c; int cur = 0; InitStack(s);

while(exp[cur] != '\\0') {

if(IsOperator(exp[cur])) {

a = Pop(s); b = Pop(s);

c = Calculate(a, exp[cur],b); Push(s,c); } else {

Push(s,exp[cur]); }

cur++; }

return Pop(s); }

表达式的菜单文件 #include \#include #include

void expressionmenu() {

16

}

char exp[N]; int i;

char value; while(1) {

printf(\ printf(\你输入的是1功能: 表达式求值\\n\ printf(\

printf(\输入表达式请按 1 ************\\n\ printf(\表达式结果请按 2 ************\\n\ printf(\返回主菜单请按 0 ************\\n\ scanf(\ if(i==0) {

printf(\数据结构基本内容\\n\\n\\n\ printf(\单链表基本操作\\n\\n\ printf(\二叉树基本操作\\n\\n\ printf(\表达式求值\\n\\n\

printf(\二叉排序树基本操作\\n\\n\ printf(\最小生成树\\n\\n\ printf(\拓扑排序\\n\\n\ printf(\图\\n\\n\

printf(\退出程序。\\n\\n\\n\\n\ break; }

else if(i==1) {

printf(\请输入后缀表达式:\ scanf(\ }

else if(i==2) {

value = CalExp(exp);

printf(\表达式的结果为：\\n\

printf(\ } else {

printf(\输入选择错误！请重新输入\\n \ } }

17

二叉树的头文件 #ifndef _BITREE_H #define _BITREE_H

typedef char TreeData; //结点数据类型 typedef struct BinTreeNode { //结点定义

TreeData data;

struct BinTreeNode * leftChild, * rightchild; } BinTreeNode,* BinTree;

BinTree creatbitree(BinTree &T); void PreOrder(BinTree &T); void InOrder(BinTree &T); void PostOrder(BinTree &T); int LeafCount(BinTree &T); void bitreemenu(); #endif

二叉树的源文件 #include #include #include #include \#define NULL 0

BinTree creatbitree(BinTree &T) {

TreeData ch;

scanf(\ if(ch=='#') T=NULL; else {

if(!(T=(BinTreeNode*)malloc(sizeof(BinTreeNode)))) printf(\ T->data=ch;

creatbitree(T->leftChild); creatbitree(T->rightchild); }

return T; }

int LeafCount(BinTree &T) {

int sum=0,m,n; if(T){

if((!T->leftChild)&&(!T->rightchild)) sum++;

18