C语言程序设计-第十一章综合实训—学生成绩管理系统资料课件.ppt

1、C语言程序设计语言程序设计项目十一项目十一 综合实训综合实训-学生成绩管理系统学生成绩管理系统1项目项目十一十一 综合实训综合实训学生成绩管学生成绩管理系统理系统2【项目要求项目要求】将从键盘输入的十进制数转换为将从键盘输入的十进制数转换为N N（如二进制、八进制、（如二进制、八进制、十六进制）进制数据，利用顺序栈实现数制转换问题十六进制）进制数据，利用顺序栈实现数制转换问题 十进制转化成十进制转化成N进制的算法是进制的算法是/整数部分为除整数部分为除N取余法取余法,小数部分为小数部分为乘乘N取整法。例如：对取整法。例如：对1348这个数，转化为这个数，转化为N进制，也就是解方程进制，也就是解

2、方程1348=aN5+bN4+cN3+dN2+eN1+f，目标就是要求出系数，目标就是要求出系数a,b,c,d,e,f的值（也许的值（也许a的前面还有的前面还有w*N6甚至甚至7次方等等，但是次次方等等，但是次数太高的话就必然会是数太高的话就必然会是0），比如我们假定），比如我们假定N=10的话，那么求出来的话，那么求出来的结果必然是的结果必然是a=b=0,c=1,d=3,e=4,f=8 。对于。对于N进制来说，进制来说，a,b,c,d,e,f的值都必然要小于的值都必然要小于N（否则就会向高位进一），显然求（否则就会向高位进一），显然求解的过程是：将解的过程是：将1348除以除以10（令（令N

3、=10）,则余数就是则余数就是f ，即，即8,则商则商则是则是aN4+bN3+cN2+dN1+e，这样进一步除以，这样进一步除以10得得e,依次得依次得到到d,c,b,a,可用堆栈来实现。可用堆栈来实现。【项目分析项目分析】3问题情境及实现问题情境及实现v/*v 堆栈的应用-进制转换 v 将十进制转换成其他进制 v*/v#include v#define maNlen 100 v vtypedeftypedef structstruct /堆栈的结构大家应该都很熟悉了 v v intint datamaNlen;v intint top;vSeqStack;v vvoidvoid InitSt

4、ack(SeqStack*S)/置栈空 v v S-top=-1;v v 4问题情境及实现问题情境及实现vvoidvoid Pop(SeqStack*S,intint*N)/出栈，N用来接受被弹出的数的 v v *N=S-dataS-top;v S-top-;v v vvoidvoid Push(SeqStack*S,intint N)/入栈 v v S-top+;v S-dataS-top=N;v v vvoidvoid Conversion(SeqStack*S,intint n,intint d)/n为一个十进制数，d为进制 v v ifif(d 0)v printf(ERROR!n);

5、v ifif(n 0)v n=-n;v ifif(n=0)v Push(S,0);v whilewhile(n)v v Push(S,n%d);v n/=d;v v 5问题情境及实现问题情境及实现vintint main()v v intint n,d,N;/n为一个十进制数，d为进制 v SeqStack stack,*S;v S=&stack;v v whilewhile(scanf(%d%d,&n,&d)!=EOF)v v InitStack(S);/初始化 v Conversion(S,n,d);v ifif(n top!=-1)v v Pop(S,&N);v ifif(N top=0

6、;s-top=0;v v 判空栈判空栈vint empty(stack int empty(stack*s)s)v if(s-top=0)return if(s-top=0)return 1;1;v else return 0;else return 0;v 12 入栈入栈 vvoid push(stack void push(stack*s,datatype N)s,datatype N)v if(s-top=MAN-1)if(s-top=MAN-1)v printf(printf(栈满栈满););v else else v s-top+;s-top+;v s-datas-top=N;s-d

7、atas-top=N;v v 13 出栈出栈 vvoid pop(stack void pop(stack*s,datatype s,datatype*N)N)v if(empty(s)if(empty(s)v printf(printf(栈空栈空););v else elsev *N=s-datas-top;N=s-datas-top;v s-top-;s-top-;v v 14 取栈顶元素取栈顶元素 vdatatype get(stack datatype get(stack*s)s)v if(empty(s)if(empty(s)v printf(printf(栈空栈空););v els

8、e else v return(s-datas-top);return(s-datas-top);v 151.3 1.3 双栈的操作双栈的操作v让两个栈共享一个数组的存储空间，让一个栈的让两个栈共享一个数组的存储空间，让一个栈的栈底为该空间的始端，另一个栈的栈底为该空间的末栈底为该空间的始端，另一个栈的栈底为该空间的末端，当元素进栈时，都从两端向中间靠拢，这样就可端，当元素进栈时，都从两端向中间靠拢，这样就可以达到在使用过程中有的栈占有的空间多一些，有的以达到在使用过程中有的栈占有的空间多一些，有的栈占有的空间少一些，公共的剩余空间可以调节使用，栈占有的空间少一些，公共的剩余空间可以调节使用，

9、从而提高了存储空间的利用率。从而提高了存储空间的利用率。1 12 23 3 n n m mm+1 m+1 MAN-1MAN-1 data data a1 a2 a3 an bm b2 b1top1top2栈栈2底底栈栈1底底 双栈共享存储空间双栈共享存储空间 16存储结构可定义为存储结构可定义为v#define MAN#define MAN 双栈中允许存放元素的最大个数双栈中允许存放元素的最大个数vtypedef structtypedef structv datatype dataMAN;datatype dataMAN;v int top1,top2;int top1,top2;vboth

10、stack;bothstack;用用bothstack可以定义一个双栈可以定义一个双栈ds：bothstack ds;或或bothstack*ds；171.1.进栈进栈 vvoid push(bothstack void push(bothstack*ds,datatype N)ds,datatype N)v if(ds-top2=ds-top1+1)if(ds-top2=ds-top1+1)v printf(printf(栈满栈满););v else elsev ds-top2-;ds-top2-;v ds-datads-top2=N;ds-datads-top2=N;v v 182 2出栈

11、出栈 vvoid pop(bothstack void pop(bothstack*ds,datatype ds,datatype*N)N)v if(ds-top2=MAN)if(ds-top2=MAN)v printf(printf(栈空栈空););v else elsev *N=ds-datads-top2;N=ds-datads-top2;v ds-top2+;ds-top2+;v v 191.4 1.4 栈的应用栈的应用算法思路：把十进制数转换为二进制数采用的方法是算法思路：把十进制数转换为二进制数采用的方法是“除除2取余取余”，直到商为，直到商为0。依次得到的余数是。依次得到的余数是

12、k1,k2,k3,km,而转换后的二进制数是而转换后的二进制数是km km-1k3 k2 k1，从结果看恰好与计算过程相反，因此转换过程中每得到一位从结果看恰好与计算过程相反，因此转换过程中每得到一位二进制数则进栈保存，转换完毕后依次出栈则正好是转换结二进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。此种方法同样适用于将十进制数转换为果。此种方法同样适用于将十进制数转换为r进制的数。把十进制的数。把十进制整数进制整数11转换为二进制的过程如下：转换为二进制的过程如下：211 余数余数二进制位二进制位 低低 高高 25 1k1 1 22 1k2 2 21 0 k3 30 1k4 4例例 2

13、-3 编写一个算法将给定的十进制数转换为二进制数输出。编写一个算法将给定的十进制数转换为二进制数输出。20数值转换的算法数值转换的算法v typedef int datatype;#define MAN 10typedef int datatype;#define MAN 10v void transfer(int n,int r)void transfer(int n,int r)void transfer(int n,int r)void transfer(int n,int r)v stack s;int sMAN,top;/stack s;int sMAN,top;/*定义一定义一个顺

14、序栈个顺序栈*/v datatype N;int N;datatype N;int N;v init(s);init(s);top=0;top=0;/*初始化栈初始化栈*/v while(n)while(n)while(n)while(n)v push(s,n%r);push(s,n%r);s+top=n%r;/s+top=n%r;/*余数入栈余数入栈*/v n=n/r;n=n/r;n=n/r;n=n/r;/*商作为被除数继续商作为被除数继续*/v v while(!empty(s)while(top!=0)while(!empty(s)while(top!=0)v pop(s,N);pop(

15、s,N);N=stop-;N=stop-;v printf(%d,N);printf(%d,N);printf(%d,N);printf(%d,N);v v v 算法一算法一 算法二算法二21例例2-4 2-4 栈与递归栈与递归 v下面以下面以 n!n!为例，介绍如何将递归的算法改写为为例，介绍如何将递归的算法改写为堆栈的非递归算法。堆栈的非递归算法。n!=1 n n=0 0或或n n=1/1/*递归终止条件递归终止条件*/n n*(n-1)!(n-1)!n0 /n0 /*递归步骤递归步骤*/int fact(int n)if(n=0|n=1)return 1;else return(n*fa

16、ct(n-1);22程序的执行过程图示程序的执行过程图示fact(3)n=3f=3*fact(2)return ff=3*2*1*1n=2f=2*fact(1)return ff=2*1*1n=1f=1*fact(0)return ff=1*1n=0f=1return ff=1int fact(int n)if(n=0|n=1)return 1;else return(n*fact(n-1);23阶乘的堆栈算法阶乘的堆栈算法(非递归非递归)v typedef int datatype;#define MAN 20typedef int datatype;#define MAN 20v int

17、fact(int n)int fact(int n)int fact(int n)int fact(int n)v stack s;datatype N;int m=1;int sMAN,top=0,N,m=1;stack s;datatype N;int m=1;int sMAN,top=0,N,m=1;v init(s);init(s);if(n=0|n=1)if(n=0|n=1)m=1;m=1;v if(n=0|n=1)m=1;else while(n1)if(n=0|n=1)m=1;else while(n1)v else while(n1)else while(n1)s+top=n;

18、s+top=n;v push(s,n);n-;push(s,n);n-;n-;n-;v v while(!empty(s)while(top!=0)while(!empty(s)while(top!=0)v pop(s,N);pop(s,N);N=stop-;N=stop-;v m=m m=m*N;N;m=m m=m*N;N;v v v return m;return m;return m;return m;v v 算法一算法一 算法二算法二24例例2-5 2-5 算术表达式的求值算术表达式的求值 v1.1.算术表达式的两种表示方法算术表达式的两种表示方法v 中缀表达式中缀表达式 v所谓中缀表

19、达式就是把运算符放在两个运算对所谓中缀表达式就是把运算符放在两个运算对象之间的表达式。如象之间的表达式。如3+53+5*3 3。实际中缀表达式就是经。实际中缀表达式就是经常习惯使用的算术表达式。常习惯使用的算术表达式。v 有括号出现时先算括号内的，后算括号外的，有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；多层括号，由内向外进行；v 在无括号或同层括号内的情况下，先做乘除在无括号或同层括号内的情况下，先做乘除运算，运算，S S后做加减运算；后做加减运算；v 同一优先级运算，从左向右依次进行。同一优先级运算，从左向右依次进行。25 后缀表达式后缀表达式 v所谓后缀表达式就是把运

20、算符放在两个运算对所谓后缀表达式就是把运算符放在两个运算对象之后的表达式。如象之后的表达式。如3+53+5*3 3的后缀表达式是的后缀表达式是 3 5 3 3 5 3*+其中运算对象和运算符之间用空格隔开。其中运算对象和运算符之间用空格隔开。v在后缀表达式中，不再引入括号，所有的计算在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，即遇到按运算符出现的顺序，严格从左向右进行，即遇到运算符就将运算符前的两个运算对象进行计算，而运算符就将运算符前的两个运算对象进行计算，而不用再考虑运算规则和级别。所以计算机扫描一次不用再考虑运算规则和级别。所以计算机扫描一次就能完成运算

21、。就能完成运算。v把中缀表达式转换成对应的后缀表达式的规则把中缀表达式转换成对应的后缀表达式的规则是：把每个运算符都移到他的两个运算对象的后面，是：把每个运算符都移到他的两个运算对象的后面，然后删掉所有的括号即可。然后删掉所有的括号即可。26v例如例如:对下列各中缀表达式对下列各中缀表达式v 5/2-7 5/2-7v 15+6 15+6*(2+4(2+4）v 3 3*(N+y)/(2-y)(N+y)/(2-y)v(25+N)(25+N)*(a(a*(a+b)+b)(a+b)+b)v对应的后缀表达式分别为对应的后缀表达式分别为v 5 2/7-5 2/7-v 15 6 2 4+15 6 2 4+*

22、+v 3 N y+3 N y+*2 y-/2 y-/v 25 N+a a b+25 N+a a b+*b+b+*272.2.中缀表达式转换成后缀表达式中缀表达式转换成后缀表达式v在将中缀表达式转化为后缀表达示的算法中，在将中缀表达式转化为后缀表达示的算法中，为了讨论方便我们设表达式中的运算对象只有一位为了讨论方便我们设表达式中的运算对象只有一位数字，并将中缀表达式保存在字符数组数字，并将中缀表达式保存在字符数组a a中，转换中，转换后的后缀表达式存储在字符数组后的后缀表达式存储在字符数组b b中，用一个字符中，用一个字符数组数组s s作为栈，设字符作为栈，设字符=为表达式的结束符。算为表达式的

23、结束符。算法思路如下：法思路如下：28v 先将输入的中缀表达式，存入字符数组先将输入的中缀表达式，存入字符数组a a中，取出中，取出a a数组中数组中的每一个字符存于的每一个字符存于c c变量中，对于每一个变量中，对于每一个c c变量的值做如下变量的值做如下处理：处理：v 若若c c为数字，则存于数组为数字，则存于数组b b中；中；v 若若c c为左括号为左括号(，则将其压入栈，则将其压入栈s;s;v 若若c c为右括号为右括号)，则将栈，则将栈s s中左括号中左括号(以后的运以后的运算符依次出栈，存于数组算符依次出栈，存于数组b b中，然后将左括号中，然后将左括号(出栈；出栈；v 若若c c

24、为为+或或-，则将栈，则将栈s s中左括号中左括号(以后的所有以后的所有运算符依次出栈，存于数组运算符依次出栈，存于数组b b中，然后将中，然后将c c压入栈压入栈s s中；中；v 若若c c为为*或或/，则将栈，则将栈s s中的栈顶端连续的中的栈顶端连续的*或或/出栈，存于数组出栈，存于数组b b中，然后将中，然后将c c压入栈压入栈s s中中v 若若c c为为=，则将栈，则将栈S S中的所有运算符依次出栈，存于数中的所有运算符依次出栈，存于数组组b b中，然后将中，然后将c c存于数组存于数组b b中，最后得到的后缀表达式存储中，最后得到的后缀表达式存储在字符数组在字符数组b b中。中。2

25、9v 中缀转后缀的算法如下所示中缀转后缀的算法如下所示:v#define MAN 50#define MAN 50v Void trans()Void trans()v char aMAN,bMAN,char aMAN,bMAN,v sMAN,c;sMAN,c;v int i=0,j,t=1,top=0;int i=0,j,t=1,top=0;v do dov i+;i+;v scanf(%c,&ai);scanf(%c,&ai);v while(ai!=&iMAN);while(ai!=&i=0&c=0&c=9)v bt=c;t+;bt=c;t+;v else if(c=()else if(

26、c=()v top+;stop=c;top+;stop=c;v else if(c=)else if(c=)v while(stop!=()while(stop!=()v bt=stop;top-;t+bt=stop;top-;t+v top-;top-;v v else if(c=+|c=-)else if(c=+|c=-)v while(top!=0&stop!=()while(top!=0&stop!=()v bt=stop;top-;t+;bt=stop;top-;t+;v top+;stop=c;top+;stop=c;v v else if(c=else if(c=*|c=/)|c

27、=/)v while(stop!=while(stop!=*|stop!=/)|stop!=/)v bt=stop;top-;t+;bt=stop;top-;t+;v top+;stop=c;top+;stop=c;v v c=ai;i+;c=ai;i+;v v while(top!=0)while(top!=0)v bt=stop;t+;top-;bt=stop;t+;top-;v bt=;bt=;v for(j=1;jt;j+)printf(%c,bj);for(j=1;j=0&c=0&cf=q-r=0;判空队列判空队列 int empty(queue*q)if(q-f=0&q-r=0)r

28、eturn 1;else return 0;40 入队入队 v入队时，首先判队是否满了，队满的条件为：入队时，首先判队是否满了，队满的条件为：q-r=MAN-1q-r=MAN-1，队满时，不能入队，可以进行溢出，队满时，不能入队，可以进行溢出错误处理，若可以入队则先将队尾指针后移错误处理，若可以入队则先将队尾指针后移 (q-r+)(q-r+)，再将元素赋给队尾单元。，再将元素赋给队尾单元。void insert(queue*q,datatype N)if(q-r=MAN-1)printf(队满队满);else if(q-f=0&q-r=0)q-f=+q-r;else q-r+;q-dataq-

29、r=N;41 出队列出队列 v先判队列是否为空，为空时不能出队，若可以出先判队列是否为空，为空时不能出队，若可以出队，则可先将队首元素赋给指定变量（若不需要保留，队，则可先将队首元素赋给指定变量（若不需要保留，可以省去这一步），队首指针后移（可以省去这一步），队首指针后移（q-f-q-f-）。）。void delete(queue*q,datatype*N)if(empty(q)printf(队空队空);else *N=q-dataq-f;if(q-f=q-r)q-f=q-r=0;else q-f+;42 取队首元素取队首元素 v先判队列是否为空，为空时不能取元素，否则先判队列是否为空，为空时

30、不能取元素，否则取出队首元素，但队首指针保持不变。取出队首元素，但队首指针保持不变。datatype get(queue*q)if(empty(q)printf(队空队空);else return(q-dataq-f);43rf01a9a8a7a6a52.3 2.3 循环队列循环队列v将队列的数据区将队列的数据区data1data1至至dataMANdataMAN看成头尾看成头尾相接的循环结构，头尾指针的关系不变，将其称为相接的循环结构，头尾指针的关系不变，将其称为循环队列循环队列 .44 入队入队 vvoid insert(queue void insert(queue*q,datatype

31、 N)q,datatype N)v if(q-r%(MAN-1)+1=q-f)if(q-r%(MAN-1)+1=q-f)v printf(printf(队满队满););v else else v q-r=q-r%(MAN-1)+1;q-r=q-r%(MAN-1)+1;v q-dataq-r=N;q-dataq-r=N;v v 45 出队出队 vvoid delete(queue void delete(queue*q,datatype q,datatype*N)N)v if(q-r=0&q-f=0)if(q-r=0&q-f=0)v printf(printf(队空队空););v else elsev *N=q-dataq-f;N=q-dataq-f;v if(q-f=q-r)if(q-f=q-r)v q-f=q-r=0;q-f=q-r=0;v else q-f=q-f%(MAN-1)+1;else q-f=q-f%(MAN-1)+1;v v