高等学校计算机实践教学用书 《数据结构》实验指导书 mulpoly *head while(p!=NULL) p-p->next; 整个实现的主程序如下: void maino i mulpoly *ha, *hb, *hc, *p, *q, *h, ha=creatpolyO polyout(ha) hb=creatpolyo polyout(hb) hc=polyadd(ha, hb) polyout(hc) polymulti (ha, hb) polyout(hc) 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 16 mulpoly *head; { mulploy *p , *q ; p=head->next; while(p!=NULL) { printf(“%d,%d”,p->coef,p->exp); p=p->next; } } 整个实现的主程序如下： void main() { mulpoly *ha, *hb, *hc ,*p, *q, *h; ha=creatpoly(); polyout(ha); hb=creatpoly(); polyout(hb); hc=polyadd(ha,hb)’; polyout(hc); h=polymulti(ha,hb); polyout(hc); }
高等学校计算机实践教学用书 《数据结构》实验指导书 实验二栈和队列 实验目的 掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下 灵活运用 2、握栈和队列的特点,即先进后出与先进先出的原则。 3、栈和队列的基本运算,如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 题目一表达式求值算法 问题描述] 表达式求值是程序设计语言编译中的一个基本算法。他的实现是栈应用 的一个典型例子。这里采用较为流行的“算符优先法”来实现对表达式的求 值。要把一个表达式翻译成正确求值的一个机器指令序列,或者是直接对表 达式求值,首先要能够正确解释表达式。那么就要了解算术四则运算的基本 规则 1)先乘除,后加减; 2)从左算到右; 4)先括号内,后括号外。 例如表达式:4+2*3-10/5的计算顺序为: 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译 或解释执行的 [基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求值, [实现提示] 任何表达式都由操作数、运算符、定界符组成,我们把运算符和定界符 统称为算符。它们构成的集合命名为OP,根据运算法则在每一步中,任意 两个算符优先级关系可以由下表来描述 Q2 () >>< >><<<> >>>><>> <<<<< >>>> > <<<< 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 17 实验二 栈和队列 一、 实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下 灵活运用。 2、 握栈和队列的特点，即先进后出与先进先出的原则。 3、栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 题目一 表达式求值算法 [问题描述] 表达式求值是程序设计语言编译中的一个基本算法。他的实现是栈应用 的一个典型例子。这里采用较为流行的“算符优先法”来实现对表达式的求 值。要把一个表达式翻译成正确求值的一个机器指令序列，或者是直接对表 达式求值，首先要能够正确解释表达式。那么就要了解算术四则运算的基本 规则： 1）先乘除，后加减； 2）从左算到右； 4）先括号内，后括号外。 例如表达式：4+2*3-10/5 的计算顺序为： 4+2*3–10/5=4+6–10/5=10–10/5=10–2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译 或解释执行的。 [基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求值。 [实现提示] 任何表达式都由操作数、运算符、定界符组成，我们把运算符和定界符 统称为算符。它们构成的集合命名为 OP，根据运算法则在每一步中，任意 两个算符优先级关系可以由下表来描述:
高等学校计算机实践教学用书 《数据结构》实验指导书 其中,Q1<Q2Q1的优先级低于Q2 Q1=Q2Q1的优先级等于Q2 Q1>Q2Q1的优先级高于Q2 “#”号表示表达式的开始与结束。 该表可以采用二维表表示,由先后两算符的序号做下标定位两者的优先 级,如“*”的序号为2,“+”的序号为1,则“*”与“+”相遇OP2,1 得到“>”所以“*”的优先级高 [程序实现] (1)算法思想 为了实现算符优先算法,可以使用两个工作栈,一个是操作数栈OPDS, 另一个是运算符栈OPS,分别存放操作数与算符。首先将标志“#”进运算 符栈OPS的底,按照栈后进先出的原则进行 ◆遇到操作数,进操作数栈,计算机继续扫描下一符号: 遇到运算符时,需要将此算符的优先级与OPS栈顶算符优先级比 若优先级比站顶元素高,则进OPS栈,继续扫描下一符号 若优先级比站顶元素低,则运算符优先级比站顶元素OPS栈 顶元素退栈形成一个操作码Q;同时,操作数栈OPDS两次退 栈,形成两个操作数ab.计算机对操作数与操作码完成一次运 算操作,即aQb.其运算结果存放在操作数OPDS栈,作为 次运算的中间结果进OPDS栈 若与栈OPS栈顶元素优先级相等,则栈顶元素退栈。当遇到 栈顶元素是“#”时,表示整个运算结果,否则,继续扫描下 个符号 (2)程序实现 /*初始化* #define false o #define true #define mAX 10 #include <stdio h> #include <stdlib. h> void push opdso; /*push opds stack. "* float pop opds(; /pop opds stack. * void push ops(: /push ops stack.*. float pop ops(; /*pop ops stack. * char relation( /*>,<, =* float operate(: /*+ ,* / float opds[MAⅪ];/° operands stack 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 18 其中， Q1<Q2 Q1 的优先级低于 Q2 Q1=Q2 Q1 的优先级等于 Q2 Q1>Q2 Q1 的优先级高于 Q2 “#”号表示表达式的开始与结束。 该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先 级，如“*”的序号为 2，“+”的序号为 1，则“*”与“+”相遇 OP[2，1] 得到“>”所以“*”的优先级高。 [程序实现] （1） 算法思想 为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈 OPDS， 另一个是运算符栈 OPS，分别存放操作数与算符。首先将标志“#”进运算 符栈 OPS 的底，按照栈后进先出的原则进行： ◆ 遇到操作数，进操作数栈，计算机继续扫描下一符号； ◆ 遇到运算符时，需要将此算符的优先级与 OPS 栈顶算符优先级比 较。 ➢ 若优先级比站顶元素高，则进 OPS 栈，继续扫描下一符号； ➢ 若优先级比站顶元素低，则运算符优先级比站顶元素 OPS 栈 顶元素退栈形成一个操作码 Q；同时，操作数栈 OPDS 两次退 栈，形成两个操作数 a,b.计算机对操作数与操作码完成一次运 算操作，即 aQb.其运算结果存放在操作数 OPDS 栈，作为一 次运算的中间结果进 OPDS 栈。 ➢ 若与栈 OPS 栈顶元素优先级相等，则栈顶元素退栈。当遇到 栈顶元素是“#”时，表示整个运算结果，否则，继续扫描下 一个符号。 （2） 程序实现 /* 初始化*/ #define FALSE 0 #define TRUE 1 #define MAX 10 #include <stdio.h> #include <stdlib.h> void push_opds(); /*push opds stack.*/ float pop_opds(); /*pop opds stack.*/ void push_ops(); /*push ops stack.*/ float pop_ops(); /*pop ops stack.*/ char relation();/*>,<,=*/ float operate();/*+,-,*,/*/ float opds[MAX]; /*operand's stack */
高等学校计算机实践教学用书 《数据结构》实验指导书 int ops(MAX]; /*operator's stack*/ int topd=0 int top=0; /*opds top*/ char symb *主函数,表达式求值 void maino char ch float a b printf("n Please input expression(# end): In") symb=getchar) while((symb!=#)l((char (ops[ topD!=#)) if(symb!=+)&&(symb!=-")&&(symb!=*)&&(symb!=/)&&(symb =(&&(symb!=)&&(symb=#)&&(symb!=) (*不是算符,则是操作数进OPDS栈 sh opds( symb) symb=getchar /*是算符,先比较优先级,在分情况处理 ch=relation((char )(ops top)), symb) case symb=getchar sy=pop opso sy=pop opso b=pop opds(; a=pop opds(; 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 19 int ops[MAX]; /*operator's stack */ int topd=0; /*opds's top*/ int top=0; /*opd's top*/ char symb; /*主函数，表达式求值 void main() { char sy; char ch; float a,b; printf("\n Please input expression(# end):\n"); push_ops('#'); symb=getchar(); while ((symb!='#')||((char)(ops[top])!='#')) { if((symb!='+')&&(symb!='-')&&(symb!='*')&&(symb!='/')&&(symb! ='(')&&(symb!=')')&&(symb!='#')&&(symb!=' ')) { /*不是算符，则是操作数进 OPDS 栈 push_opds(symb); symb=getchar(); } else { /*是算符，先比较优先级，在分情况处理 ch=relation((char)(ops[top]),symb); switch(ch) { case '<': push_ops(symb); symb=getchar(); break; case '=': sy=pop_ops(); symb=getchar(); break; case '>': sy=pop_ops(); b=pop_opds(); a=pop_opds();
高等学校计算机实践教学用书 《数据结构》实验指导书 topd=topd+ 1; /push opds stack*/ opds topd]=operate(a, sy, b) break. case printf("errorin"); printf("InThe result=%1.2f\n",opds( topd)); /*操作数压栈 void push opds( ch) int ch i if (topd=MAX-1) printf("the opds stack is overflow. In") chi=ch-0;/将字符转化为“值”:“3”转为3 opds topd=ch i /*操作数弹栈 float pop opdso pd=topd return(opds topd+ID) *操作符压栈 void push ops(ch) char ch t if(top=MAX-1) printf("the ops stack is overflow. In") 西南科技大学计算机科学学院
高等学校计算机实践教学用书 ★ 《数据结构》实验指导书 西南科技大学 计算机科学学院 20 topd=topd+1; /*push_opds stack*/ opds[topd]=operate(a,sy,b); break; case ' ': printf("error\n"); break; } } } printf("\nThe result=%1.2f\n",opds[topd]); getch(); } /*操作数压栈 void push_opds(ch) char ch; { int ch_i; if (topd==MAX-1) printf("the opds stack is overflow.\n"); else { ch_i=ch-'0'; /*将字符转化为“值”：“3”转为 3 topd++; opds[topd]=ch_i; } } /*操作数弹栈 float pop_opds() { topd=topd-1; return(opds[topd+1]); } /*操作符压栈 void push_ops(ch) char ch; { if (top==MAX-1) printf("the ops stack is overflow.\n"); else