线性表的应用——简单仓库管理
建立一个简单的仓库管理程序,可以按货物编号和货物名称查询仓库存储情况,也可以增加或删除货物以及修改货物数量。
货物按编号从小到大存储,为方便查找,采用双向链表存储结构,节点结构如下:
typedef struct node{ /*定义结构体类型dnode*/
int number; /*货物编号*/
char name[MAX]; /*货物名称*/
int counter; /*货物数量*/
struct node *prior,*next; /*前驱和后继指针*/
}dnode;
程序要求:
(1)init函数用来建立双向链表,可以通过外部输入或预定义数组导入数据;
(2)insert函数用来增加新货物,通过外部输入导入数据;
(3)delete函数用于删除某种货物;
(4)amend函数用于修改某种货物的数量(当货物数量为0时,删除该货物);
(5)search函数用查找指定的货物(指定编号或名称);
(6)output_one函数用于输出某一种货物的存货信息,output函数用于输出整个仓库的存货信息;
(7)main函数根据输入的命令标示符,作相应的操作:
i增加新货物;
d删除某种货物;
a修改某种货物的数量;
s查找指定的货物(1按编号查找,2按名称查找);
o输出存货信息(1输出指定的某种货物的存货信息,2输出整个仓库的存货信息);
q退出程序。
栈的应用——中缀表达式转后缀表达式
中缀表达式就是我们最常见的那种表达式,运算符在两个操作数之间;后缀表达式一般用在编译程序中,运算符在两个操作数之后。后缀表达式不需要括号和指明运算符的优先级,其运算顺序由运算符和操作数在表达式中的顺序来决定。
下面是一个中缀表达式和后缀表达式的例子:
中缀表达式:A+B*(C/D-E)*F-G 后缀表达式:ABCD/E-*F*+G-
运算符优先级如下:
运算符 优先级
$ 0
(,) 1
+,- 2
*,/ 3
注:“$”表示中缀表达式结束
转化方法如下:
(1)指针指向的操作数依次进入队列;
(2)指针指向的运算符依次入栈;
(3)出栈的运算符(括号除外)依次进入队列;
(4)当指针指向“)”时,栈顶运算符依次出栈,直至有一个“(”出栈为止;
(5)当指针指向的运算符(括号除外)的优先级比栈顶运算符的优先级低或同级时,栈顶运算符依次出栈,直至指针指向的运算符的优先级比栈顶运算符的优先级高或栈空为止,指针指向的运算符入栈。
转化过程如下:
指针 栈(临时存放运算符) 队列(存放后缀表达式)
A+B*(C/D-E)*F-G$
A+B*(C/D-E)*F-G$ A
A+B*(C/D-E)*F-G$ + A
A+B*(C/D-E)*F-G$ + AB
A+B*(C/D-E)*F-G$ + * AB
A+B*(C/D-E)*F-G$ + * ( AB
A+B*(C/D-E)*F-G$ + * ( ABC
A+B*(C/D-E)*F-G$ + * ( / ABC
A+B*(C/D-E)*F-G$ + * ( / ABCD
A+B*(C/D-E)*F-G$ + * ( - ABCD/
A+B*(C/D-E)*F-G$ + * ( - ABCD/E
A+B*(C/D-E)*F-G$ + * ABCD/E-
A+B*(C/D-E)*F-G$ + * ABCD/E-*
A+B*(C/D-E)*F-G$ + * ABCD/E-*F
A+B*(C/D-E)*F-G$ - ABCD/E-*F*+
A+B*(C/D-E)*F-G$ - ABCD/E-*F*+G
A+B*(C/D-E)*F-G$ $ ABCD/E-*F*+G-
程序要求:
(1)postfix函数实现中缀表达式转后缀表达式;
(2)main函数将输入的中缀表达式转为后缀表达式输出。