一、 实验目的
掌握栈及队列基本操作的实现
一、 源程序
栈与队列基本操作：
#include<iostream> using namespace std; #define OK 1 #define OVERFLOW -1 #define ERROR 0 #define MAXSIZE 100 int typedef Status; typedef struct StackNode//链栈的定义 { int data; struct StackNode *next; }StackNode,*LinkStack; Status InitStack(LinkStack &S)//链栈初始化 { S = NULL; return OK; } Status Push(LinkStack &S, int e)//入栈 { StackNode *p = new StackNode; p->data = e; p->next = S; S = p; return OK; } Status Pop(LinkStack &S, int &e)//链栈的出栈 { if (S == NULL)return ERROR; e = S->data; StackNode *p = S; S = S->next; delete p; return OK; } Status Print(LinkStack &S)//链栈显示 { if (S == NULL)return ERROR; while (S != NULL) { cout << S->data<<" "; S = S->next; } return OK; } int GetTop(LinkStack S)//取栈顶元素 { if (S != NULL) return S->data; } typedef struct QNode//链队定义 { int data; struct QNode *next; }QNode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue(LinkQueue &Q)//链队初始化 { Q.front = Q.rear = new QNode; Q.front->next = NULL; return OK; } Status EnQueue(LinkQueue &Q, int e)//入队 { QNode *p = new QNode; p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } Status DeQueue(LinkQueue &Q, int &e)//出队 { if (Q.front == Q.rear)return ERROR; QNode *p = Q.front->next; e = p->data; Q.front->next = p->next; delete p; cout << e << " "; return OK; } int GetHead(LinkQueue Q)//取队头元素 { if (Q.front != Q.rear) return Q.front->next->data; } int main() { StackNode *A1,* A2; int N,M; InitStack(A1); InitStack(A2); cout << "请输入栈的四个元素依次为：" << endl; for (int i = 0; i < 4; i++) { cin >> M; Push(A1, M); } Pop(A1, N); Push(A2, N); Pop(A1, N); int a1 = N; Pop(A1, N); int a2 = N; Pop(A1, N); Push(A2, N); cout << "出栈元素：" << a1 << " " << a2 << endl;; cout << "现在在栈中的元素为：" << endl; Print(A2); cout << endl; LinkQueue B1, B2; InitQueue(B1); InitQueue(B2); cout << "请输入四个元素入队" << endl; for (int i = 0; i < 4; i++) { cin >> M; EnQueue(B1, M); } cout << "链队出对：" << endl; for (int i = 0; i < 4; i++) { DeQueue(B1, N); } }
运算符表达式：
#include<iostream> #include<string> #include<malloc.h> #include<stdlib.h> using namespace std; #define OK 1 #define OVERFLOW -1 #define ERROR 0 #define MAXSIZE 100 int N = 0; int typedef Status; typedef struct//顺序栈的定义 { char *base; char *top; int stacksize; }SqStack; Status InitStack(SqStack &S)//顺序栈初始化 { S.base = (char*)malloc(sizeof(char)*MAXSIZE); if (!S.base)exit(OVERFLOW); S.top = S.base; S.stacksize = MAXSIZE; return OK; } Status Push(SqStack &S, char e)//入栈 { if (S.top - S.base == S.stacksize){ return ERROR; } *S.top++ = e; return OK; } Status Pop(SqStack &S, char &e)//出栈 { if (S.top == S.base)return ERROR; e = *--S.top; return OK; } char GetTop(SqStack S) { if (S.top != S.base) { return *(S.top - 1); } } void In(char c) { if (c == '(' || c == ')' || c == '[' || c == ']' || c == '!' || c == '+' || c == '-' || c == '~' || c == '++' || c == '--' || c == '*' || c == '/' || c == '%' || c == '<<' || c == '>>' || c == '>=' || c == '==' || c == '!=' || c == '&' || c == '^' || c == '|' || c == '&&' || c == '||' || c == '?:') { cout << c<<"这是运算符" << endl; N = N + 1; } else cout <<c<< "不是运算符" << endl; } char Preccede(char t1, char t2) { int a1=0; int b1 = 0; char M; if (t1 == '(' || t1 == ')' || t1 == '[' || t1 == ']') { a1 = 14; } if (t2 == '(' || t2 == ')' || t2 == '[' || t2 == ']') { b1 = 14; } if (t1 == '!' || t1 == '~' || t1 == '++' || t1 == '--')a1 = 13; if (t2 == '!' || t2 == '+' || t2 == '-' || t2 == '~' || t2 == '++' || t2 == '--')b1 = 13; if (t1 == '*' || t1 == '/' || t1 == '%')a1 = 12; if (t2 == '*' || t2 == '/' || t2 == '%')b1 = 12; if (t1 == '+' || t1 == '-')a1 = 11; if (t2 == '+' || t2 == '-')b1 = 11; if (t1 == '<<' || t1 == '>>' || t1 == '>>>')a1 = 10; if (t2 == '<<' || t2 == '>>' || t2 == '>>>')b1 = 10; if (t1 == '<' || t1 == '<=' || t1 == '>' || t1 == '>=')a1 = 9; if (t2 == '<' || t2 == '<=' || t2 == '>' || t2 == '>=')b1 = 9; if (t1 == '==' || t1 == '!=')a1 = 8; if (t2 == '==' || t2 == '!=')b1 = 8; if (t1 == '&')a1 = 7; if (t2 == '&')b1 = 7; if (t1 == '^')a1 = 6; if (t2 == '^')b1 = 6; if (t1 == '|')a1 = 5; if (t2 == '|')b1 = 5; if (t1 == '&&')a1 = 4; if (t2 == '&&')b1 = 4; if (t1 == '||')a1 = 3; if (t2 == '||')b1 = 3; if (t1 == '?:')a1 = 2; if (t2 == '?:')b1 = 2; if (t1 == '=' || t1 == '+=' || t1 == '-=' || t1 == '/=')a1 = 1; if (t2 == '=' || t2 == '+=' || t2 == '-=' || t2 == '/=')b1 = 1; if (a1 > b1) { M=t1; return M; } if (a1 == b1){ M = t1; return M; } if (a1<b1){ M = t2; return M; } } char Operate(char a, char theta, char b) { char M; a = a - '0'; b = b - '0'; if (theta == '+') { M = a + b+'0'; } if (theta == '-') { M = a - b + '0'; } if (theta == '*') { M = a*b + '0'; } if (theta == '/') { M = a / b + '0'; } return M; } int main(){ cout << Preccede('(', '+') << "优先级更高" << endl;; cout << Operate('1', '+', '2') << endl; SqStack s; InitStack(s); char n ; cout << "请输入运算符（# 退出）：" << endl; while (1){ cin >> n; if (n == '#'){ break; } Push(s, n); } while (1){ Pop(s, n); In(n); if (s.top == s.base)break; } cout << "运算符个数：" << N; }