2022年数据结构：栈子系统 2.pdf

《2022年数据结构：栈子系统 2.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构：栈子系统 2.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、/* *题目：设计一个字符型的链栈。* 编写进栈、出栈、显示栈中全部元素的程序。*题目：编写一个把十进制整数转换为二进制数的应用程序*题目：编写一个把中缀表达式转换为后缀表达式（逆波兰式）的应用程序*题目：设计一个选择式菜单，以菜单方式选择上述操作。* 栈子系统* * * * 1-进栈* * * 2-出栈* * * 3-显示* * * 4-数值转换* * * 5-逆波兰式* * * 0-返回* * * * 请选择菜单号（0-5） ：*/ #include #include #define STACKMAX 50 typedef struct sta / 栈的存储结构 int data; str

2、uct sta *next; stackNode; typedef struct / 指向栈顶的指针 stackNode *top; linkStack; void conversion(int n); void push(linkStack *p, int x); int pop(linkStack *p); void showStack(linkStack *p); void sufflx(); /* Function: main() Description: 主调函数Calls: push() pop() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

3、- - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - showStack() conversion() Input: NULL Return: void Others: NULL */ void main() int x, choice, i = 1; linkStack p; p.top = NULL; / 置空栈while (i) printf(n 栈子系统 n); printf(*n); printf(* 1-进栈*n); printf(* 2-出栈*n); printf(* 3-显示*n); printf(

4、* 4-数值转换*n); printf(* 5-逆波兰式*n); printf(* 0-返回*n); printf(*n); printf( 请选择菜单号（0-5） ：); fflush(stdin); / 清空输入的缓存区choice = getchar(); switch(choice) case 1: while (1) printf( 请输入一个整数（ 0表示结束）并按回车：); scanf(%d, &x); if (x != 0) push(&p, x); / 入栈 else break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

5、- - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - break; case 2: x = pop(&p); / 出栈if (x 0) printf( 出栈元素为：%dn, x); else printf( 栈为空，没有元素可以出栈！n); break; case 3: showStack(&p); / 显示栈元素break; case 4: printf( 请输入十进制数：); scanf(%d, &x); conversion(x); / 数值转换break; case 5: sufflx(); break; case 0

6、: i = 0; break; default: i = 1; break; /* Function: conversion() Description: 十进制数转换二进制数Calls: push() pop() Input: n :输入的要转换的数Return: void Others: NULL */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - void conversion(int n) linkStack s; i

7、nt x, i = 1; s.top = NULL; / 置空栈do x = n%2; / 求余数n = n/2; / 求新商push(&s, x); / 入栈while (n); printf( 转化的二进制为：); while (i) x = pop(&s); / 出栈if (x != -1) / 判断是否全部出栈 printf(%d, x); else i = 0; printf(n); void sufflx() char strSTACKMAX; / 存储中缀表达式char expSTACKMAX; / 存储后缀表达式char starkSTACKMAX; / 顺序栈来存放运算符in

8、t top = 0; / 顺序栈置空int sum, t, i = 0; char ch; printf( 请输入一个算术表达式（运算符只能包含+，-，*， /） ，以 #结束： n); fflush(stdin); do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - i+; scanf(%c, &stri); while (stri != # & i != STACKMAX); / 存储用户输入的中缀表达式sum = i;

9、/ 保存表达式的长度i = t = 1; ch = stri; i+; while (ch != #) switch (ch) case (: / 读取到（时，入栈top+; starktop = ch; break; case ): / 读取到）时while (starktop != () expt+ = starktop-; / 出栈并赋值给输出数组expt+ = ,; / 添加分割符号 top-; / 栈顶元素为 （时，出栈break; case +: / 读取到 +时while (top != 0 & starktop != () / 判断符号优先级 expt+ = starktop-

10、; expt+ = ,; stark+top = ch; / 栈为空时入栈break; case -: / 读取到 -时while (top != 0 & starktop != () expt+ = starktop-; expt+ = ,; stark+top = ch; / 栈为空时入栈break; case *: / 读取到 *时while (starktop = * | starktop = /) /* 、/运算级最高 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页

11、，共 8 页 - - - - - - - - - expt+ = starktop-; expt+ = ,; stark+top = ch; / 运算符优先级高的入栈break; case /: / 读取到 /时while (starktop = * | starktop = /) expt+ = starktop-; expt+ = ,; stark+top = ch; / 运算符优先级高的入栈break; case : / 读取到空格时忽略break; default: / 不是运算符号时while (ch = 0 & ch = z) / 限制输入的变量 expt+ = ch; ch =

12、stri+; i-; / 上面多加的要去掉expt+ = ,; break; ch = stri+; while (top != 0) / 顺序栈中仍有数值时 expt+ = starktop-; if (top != 0) expt+ = ,; printf( 中缀表达式为：); / 输出for (i = 1; i sum; i+) printf(%c, stri); printf(n后缀表达式为：); for (i = 1; i data = x; q-next = p-top; p-top = q; /* Function: pop() Description: 出栈Calls: NUL

13、L Input: *p：栈的栈顶指针Return: int Others: NULL */ int pop(linkStack *p) / 出栈 stackNode *q; int x; if (p-top != NULL) q = p-top; x = q-data; p-top = q-next; free(q); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - return x; / 返回栈顶元素 else return

14、-1; /* Function: showStack() Description: 显示栈中元素Calls: NULL Input: *p：栈的栈顶指针Return: void Others: NULL */ void showStack(linkStack *p) stackNode *q; q = p-top; if (q != NULL) printf( 栈元素为： ); while (q != NULL) printf(%4d, q-data); q = q-next; printf(n); else printf( 栈为空。 n); return; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -