栈和队列的应用.doc

实 验 报 告课程名称 数据结构 实验项目 栈和队列的应用 实验仪器 计算机 系 别 计算机学院学院 专 业 计算机科学与技术 学生姓名 徐申毅 实验日期 2013-4-10 成 绩 指导教师 实验2 一、实验目的（1） 理解栈和队列的数据结构（2） 会利用栈编制程序2、 实验内容 （1） 编写链式栈实现入栈，出栈，获取栈顶元素等基本操作（2） 编写循环队列实现元素增添与删除等基本操作（3） 用栈的数据结构实现输入表达式求值的计算器三、实验课时4课时四、实验步骤（1）链式栈声明出栈，入栈等基本操作的函数定义出栈，入栈等基本操作的函数定义主函数，在主函数中调用上述函数编译，运行（2） 循环队列定义结构体类型，头指针和尾指针声明并定义入队，出队等基本操作函数定义主函数，在主函数中调用基本操作函数编译，运行（3） 计算器定义两个栈，一个用于存放数字，一个用于存放操作符声明并定义操作符优先级比较函数定义主函数，实现加减乘除的运算方法调用操作符优先级比较函数编译，运行5、 实验心得本次实验让我了解了栈和队列两种数据结构，栈的特点是后进先出，队列的特点是先进先出，我还学会了利用栈后进先出的数据结构特点完成表达式计算器的应用。6、 程序运行结果截图以及C程序源代码（1）链式栈#include #define SIZE sizeof(LINKSTACK)#define PRINT_ITEM %d /定义输出项的宏#define SCANF_ITEM %d /定义输入项的宏 typedef int bool; /定义bool类型const bool true = 1; /定义bool类型true常量 const bool false = 0; /定义bool类型false常量 typedef int ELEMTYPE; /定义元素类型typedef struct snode /定义链栈 ELEMTYPE data; struct snode *next; LINKSTACK;const ELEMTYPE STACK_NULL = -9999;/定义常量栈为NULL的值 LINKSTACK * INITSTACK(); /初始化栈LINKSTACK * CREATESTACK(ELEMTYPE); /创建链栈 LINKSTACK * PUSH(LINKSTACK *,ELEMTYPE);/进栈操作 ELEMTYPE GETTOP(LINKSTACK *);/获取栈顶元素LINKSTACK * POP(LINKSTACK *);/出栈操作 bool EMPTY(LINKSTACK *);/判断栈是否为NULLLINKSTACK * CLEAR(LINKSTACK *); /清空链栈int CURRENT_SIZE(LINKSTACK *); /当前链栈中的元素个数void PRINT_STACK(LINKSTACK *);/打印链栈元素void menu(); /菜单void print_enter(); /打印回车 void print_tab(); /打印tab void print_menu_item(char *,char *); /打印菜单中的每一项 void print_str(char *);void print_info(char *,bool); /打印信息，bool意思是是否打印回车 ELEMTYPE get_input();/获取压栈的数据 LINKSTACK * stack_push(LINKSTACK *);/压入链栈 LINKSTACK * stack_pop(LINKSTACK *);/出栈 LINKSTACK * stack_get_top(LINKSTACK *); /获取栈顶元素 LINKSTACK * stack_empty(LINKSTACK *); /判断栈是否为空LINKSTACK * stack_cur_size(LINKSTACK *);/获取栈中的元素个数 LINKSTACK * stack_clear(LINKSTACK *);/清空栈中元素 LINKSTACK * link_stack_method(LINKSTACK *,LINKSTACK * (* fun)(LINKSTACK *); /定义函数指针 int main(int argc,char *argv) LINKSTACK * top = NULL; int select_menu_value; menu(); do print_info(请选择:,false); scanf(%d,&select_menu_value); switch(select_menu_value) case 0: menu(); break; case 7: break; case 1: top = link_stack_method(top,stack_push); break; case 2: top = link_stack_method(top,stack_pop); break; case 3: top = link_stack_method(top,stack_get_top); break; case 4: top = link_stack_method(top,stack_empty); break; case 5: top = link_stack_method(top,stack_cur_size); break; case 6: top = link_stack_method(top,stack_clear); break; default: menu(); break; while(7 != select_menu_value); return 0;LINKSTACK * INITSTACK() LINKSTACK * stack = malloc(SIZE); return stack; LINKSTACK * CREATESTACK(ELEMTYPE data) LINKSTACK * head = INITSTACK(); head-data = data; return head;LINKSTACK * PUSH(LINKSTACK * top,ELEMTYPE data) LINKSTACK *p = CREATESTACK(data); if (NULL = top) /当栈为NULL，则将当前的数据存放在栈底 p-next = NULL; else p-next = top; top = p; return top;ELEMTYPE GETTOP(LINKSTACK * top) ELEMTYPE result = STACK_NULL; if (top != NULL) result = top-data; return result;LINKSTACK * POP(LINKSTACK * top) LINKSTACK * del; if (! EMPTY(top) del = top; top = top-next; free(del); /释放内存 return top; bool EMPTY(LINKSTACK * top) bool result = false; if (top = NULL) result = true; return result;LINKSTACK * CLEAR(LINKSTACK * top) LINKSTACK * del; if (! EMPTY(top) del = top; top = top-next; free(del); top = CLEAR(top); /使用递归进行将栈置空操作 return top;int CURRENT_SIZE(LINKSTACK * top) int result = 0; while (top != NULL) result +; top = top-next; return result;void PRINT_STACK(LINKSTACK * top) while (top != NULL) printf(PRINT_ITEM,top-data); top = top-next; void menu() print_enter(); print_tab();print_info(链栈,true);print_enter(); print_menu_item(1,入栈操作); print_menu_item(2,出栈操作); print_menu_item(3,获取栈顶元素); print_menu_item(4,判断栈表是否为空); print_menu_item(5,栈中元素个数); print_menu_item(6,清空栈表); print_menu_item(0,返回到选择菜单); print_menu_item(7,退出程序);void print_enter() printf(n);void print_tab() printf(t);void print_menu_item(char * item,char * desc) print_tab(); print_str(item); print_tab(); print_str(desc); print_enter();void print_str(char *str) while(*str) printf(%c,*str+); void print_info(char * str,bool enter) print_tab(); print_str(str); if (enter) print_enter(); ELEMTYPE get_input() ELEMTYPE result; print_info(向栈中放入一个元素:,false); scanf(SCANF_ITEM,&result); return result; LINKSTACK * stack_push(LINKSTACK * top) ELEMTYPE data = get_input(); top = PUSH(top,data); print_info(添加成功！,true); return top;LINKSTACK * stack_pop(LINKSTACK * top) top = POP(top); print_info(删除元素.,true); return top;LINKSTACK * stack_get_top(LINKSTACK * top) ELEMTYPE result = GETTOP(top); print_tab(); if (result != STACK_NULL) printf(栈顶元素为 ); printf(PRINT_ITEM,result); else printf(error:此栈是空栈.); print_enter(); return top;LINKSTACK * stack_empty(LINKSTACK * top) bool result = EMPTY(top); if (! result) print_info(此栈不为空.,true); else print_info(此栈是空栈.,true); return top;LINKSTACK * stack_cur_size(LINKSTACK * top) int result = CURRENT_SIZE(top); print_tab(); printf(栈中元素个数为 %d ,result); print_enter(); return top; LINKSTACK * stack_clear(LINKSTACK * top) top = CLEAR(top); print_info(清空成功.,true); return top;LINKSTACK * link_stack_method(LINKSTACK * top,LINKSTACK * (* fun)(LINKSTACK * src_top) return (* fun)(top);（2） 循环队列#includeusing namespace std;#define MAXQSIZE 100typedef struct int *base; int front; int rear; SqQueue;SqQueue Q;void InitQueue (SqQueue &Q)Q.base=(int *)malloc(MAXQSIZE*sizeof(int);if (!Q.base) cout初始化失败！endl;else Q.front=Q.rear=0;cout初始化成功！endl;void PrintQueue(SqQueue Q)while(Q.front!=Q.rear)coutQ.baseQ.front ;Q.front=(Q.front+1)% MAXQSIZE;coutendl;int QueueLength(SqQueue Q)return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;void EnQueue (SqQueue &Q, int e)if (Q.rear+1) % MAXQSIZE=Q.front) cout操作失败!endl;elseQ.baseQ.rear=e;Q.rear = (Q.rear+1) % MAXQSIZE;void DeQueue(SqQueue &Q, int &e)if (Q.rear=Q.front) cout操作失败!endl;elsee=Q.baseQ.front;Q.front=(Q.front+1) % MAXQSIZE;cout删除后循环队列为: ;PrintQueue(Q);int QueueEmpty(SqQueue Q)if (Q.front=Q.rear) cout循环队列为空endl;return 0;else cout循环队列不为空endl;return 1;int GetHead(SqQueue Q)int e;if(Q.front=Q.rear) return 0;elsee=Q.baseQ.front;return e;void ClearQueue(SqQueue &Q)while (Q.rear!=Q.front) Q.front=(Q.front+1) % MAXQSIZE;void DestroyQueue(SqQueue Q)free(Q.base);cout循环队列已清除!endl;int main()cout -* 循环队列程序 *- endl;cout 0、队列的清除endl;cout 1、队列初始化endl;cout 2、队列的插入endl;cout 3、输出队列endl;cout 4、删除元素endl;cout 5、判断是否为空endl;cout 6、求队列的长度endl;cout 7、返回队列的队头元素endl;cout 8、退出程序endl;SqQueue Q;int n,k;for(n=0;n100;n+)coutk;if(k=0) DestroyQueue(Q);n=100;if(k=1) InitQueue(Q);if(k=3) PrintQueue(Q);if(k=2) int e;coute;EnQueue (Q,e);cout插入后队列为: ;PrintQueue(Q);if(k=4)int del;DeQueue (Q, del);if(k=5) QueueEmpty(Q);if(k=6) cout队列的长度为: QueueLength(Q)endl;if(k=7) cout队头元素为: GetHead(Q)endl; if(k=8) break; return 0;#include #include #includeusing namespace std;#define MAX 1000 struct save1 float nMAX; int top; stack1;struct save2 char nMAX; int top; stack2; /stack1存储数字，stack2存储运算符号.bool stackempty(save1 s) if (s.top= -1) return 1; else return 0; bool stackempty2(save2 s) if (s.top= -1) return 1; else return 0; void push(save1 &s,float e)/将e入栈 if(s.top=MAX-1) cout栈已满endl; return ; s.top+;s.ns.top=e; void push2(save2 &s,char e)/将e入栈 if(s.top=MAX-1) cout栈已满endl; return ; s.top+; s.ns.top=e; void pop(save1 &s,float &e)/将栈顶元素出栈，存到e中 if(s.top=-1) cout栈为空endl; else e=s.ns.top;s.top-; void pop2(save2 &s,char &e)/将栈顶元素出栈，存到e中 if(s.top=-1) cout栈为空endl; else e=s.ns.top; s.top-; int in(char e)/e在栈内的优先级别 if(e=- | e=+) return 2; if(e=* | e=/) return 4;if(e=) return 5; if(e=() return 0; if(e=) return 7; return -1; int out(char e)/e在栈外的优先级别 if(e=- | e=+) return 1; if(e=* | e=/) return 3;if(e=) return 6;if(e=() return 7;if(e=) return 0;return -1; void count(float a,char ope,float b)/进行计算并将计算结果入栈 float sum;if(ope=+) sum=a+b; if(ope=-) sum=a-b; if(ope=*) sum=a*b;if(ope=/) sum=a/b;if(ope=) sum=pow(a,b);push(stack1,sum); int main() int i=0,len,j,nofpoint,g=0;/len表示输入式子的长度。 g表示读入的字符是否是字母变量、数字以及运算符。 float a,b;/a、b用来存储操作数栈中弹出的操作数，便于代入函数中进行计算。char lineMAX,operate,temp20;cout请输入表达式line; len=strlen(line); stack1.top=-1;/将栈置为空stack2.top=-1;/将栈置为空 while(1) g=0;if(isdigit(linei)/若读入的字符为数字，则继续判断下一个字符，直到下一个字符不是数字或者不是小数点，即可保证该操作数是完整的小数，然后将该数入操作数栈。 j=0; g=1; nofpoint=0;/记录所存的数中小数点的个数while(isdigit(linei) | linei=.) if(linei=.) nofpoint+; tempj+=linei;i+;if(i=len) break; if( nofpoint1 | (ilen&(linei!=- & linei!=+ & linei!=* & linei!=/ & linei!= & linei!=) ) cout表达式有错=len) break; else if(linei=- | linei=+ | linei=* | linei=/ | linei= | linei=( | linei=) ) /若读入的字符为运算符的情况 g=1; if(linei=( & i=len) cout表达式有错endl; return 0; / “(”放表达式最后面，错误if(linei=- | linei=+ | linei=* | linei=/ | l