数据结构：栈子系统课件

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

2、 /栈的存储结构 int data; struct 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() showStack() conversion()Input:

3、NULLReturn: voidOthers: 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-数值转换 *n"); printf(&q

4、uot;* 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

5、); /入栈 else break; 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); conversio

6、n(x); /数值转换 break; case '5': sufflx(); break; case '0': i = 0; break; default: i = 1; break; /*Function: conversion()Description: 十进制数转换二进制数Calls: push() pop()Input: n :输入的要转换的数Return: voidOthers: NULL*/void conversion(int n) linkStack s; int x, i = 1; s.top = NULL; /置空栈 do x = n%2;

7、/求余数 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; /顺序栈来存放运算符 int t

8、op = 0; /顺序栈置空 int sum, t, i = 0; char ch; printf("请输入一个算术表达式（运算符只能包含+，-，*，/），以#结束：n"); fflush(stdin); do i+; scanf("%c", &stri); while (stri != '#' && i != STACKMAX); /存储用户输入的中缀表达式 sum = i; /保存表达式的长度 i = t = 1; ch = stri; i+; while (ch != '#') switch

9、(ch) case '(': /读取到（时，入栈 top+; starktop = ch; break; case ')': /读取到）时 while (starktop != '(') expt+ = starktop-; /出栈并赋值给输出数组 expt+ = ',' /添加分割符号 top-; /栈顶元素为（时，出栈 break; case '+': /读取到+时 while (top != 0 && starktop != '(') /判断符号优先级 expt+ = star

10、ktop-; expt+ = ',' stark+top = ch; /栈为空时入栈 break; case '-': /读取到-时 while (top != 0 && starktop != '(') expt+ = starktop-; expt+ = ',' stark+top = ch; /栈为空时入栈 break; case '*': /读取到*时 while (starktop = '*' | starktop = '/') /*、/运算级最高 expt

11、+ = starktop-; expt+ = ',' stark+top = ch; /运算符优先级高的入栈 break; case '/': /读取到/时 while (starktop = '*' | starktop = '/') expt+ = starktop-; expt+ = ',' stark+top = ch; /运算符优先级高的入栈 break; case ' ': /读取到空格时忽略 break; default: /不是运算符号时 while (ch >= '0

12、' && ch <= 'z') /限制输入的变量 expt+ = ch; ch = 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); pri

13、ntf("n后缀表达式为："); for (i = 1; i < t; i+) printf("%c", expi); /*Function: push()Description: 入栈Calls: NULLInput: *p：栈的栈顶指针 x ：要入栈的数Return: voidOthers: NULL*/void push(linkStack *p, int x) /入栈 stackNode *q; q = (stackNode *)malloc(sizeof(stackNode); q->data = x; q->next = p

14、->top; p->top = q;/*Function: pop()Description: 出栈Calls: NULLInput: *p：栈的栈顶指针Return: intOthers: 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); return x; /返回栈顶元素 else return -1; /*Function: showStack()Description: 显示栈中元素Calls: NULLInput: *p：栈的栈顶指针Return: voidOthers: NULL*/void show