C语言程序设计第十一章综合实训-学生成绩管理系统

项目十一综合实训—学生成绩管理系统1【项目要求】

将从键盘输入的十进制数转换为N（如二进制、八进制、十六进制）进制数据，利用顺序栈实现数制转换问题

十进制转化成N进制的算法是//整数部分为除N取余法,小数部分为乘N取整法。例如：对1348这个数，转化为N进制，也就是解方程1348=aN^5+bN^4+cN^3+dN^2+eN^1+f，目标就是要求出系数a,b,c,d,e,f的值（也许a的前面还有w*N^6甚至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=10）,则余数就是f

，即8,则商则是aN^4+bN^3+cN^2+dN^1+e，这样进一步除以10得e,依次得到d,c,b,a,可用堆栈来实现。【项目分析】2问题情境及实现

/*

堆栈的应用---进制转换

将十进制转换成其他进制

*/

#include

<stdio.h>

#define

maNlen

100

typedef

struct

//堆栈的结构大家应该都很熟悉了

{

int

data[maNlen];

int

top;

}SeqStack;

void

InitStack(SeqStack

*

S)

//置栈空

{

S->top

=

-1;

}

3问题情境及实现

void

Pop(SeqStack

*

S,

int

*

N)

//出栈，N用来接受被弹出的数的

{

*N

=

S->data[S->top];

S->top--;

}

void

Push(SeqStack

*

S,

int

N)

//入栈

{

S->top++;

S->data[S->top]

=

N;

}

void

Conversion(SeqStack

*

S,

int

n,

int

d)

//n为一个十进制数，d为进制

{

if(d

<

0)

printf("ERROR!\n");

if(n

<

0)

n

=

-n;

if(n

==

0)

Push(S,

0);

while(n)

{

Push(S,

n%d);

n

/=

d;

}

}

4问题情境及实现

int

main()

{

int

n,d,N;

//n为一个十进制数，d为进制

SeqStack

stack,

*S;

S

=

&stack;

while(scanf("%d

%d",&n,&d)

!=

EOF)

{

InitStack(S);

//初始化

Conversion(S,

n,

d);

if(n

<

0)

printf("%c",'-');

//若是负数

while(S->top

!=

-1)

{

Pop(S,

&N);

if(N

<

10)

printf("%d",N);

else

printf("%c",N

+

55);

//使输出的时候大于9的输出为字母ABC

}

printf("\n");

}

return

0;

}

5相关知识1.栈2.队列本讲小结61栈1.1栈的定义及顺序存储1.2栈的运算1.3双栈的操作1.4栈的应用7栈满1.1栈的定义及顺序存储1.栈的定义栈又叫堆栈，允许在表的一端进行插入和删除。后进先出的线性表（简称LIFO表）。MAN-1┇i┇210top空栈a11个元素a3a2a13个元素a3a2a12个元素an┇┇a3a2a1toptoptoptop82.栈的顺序存储

#defineMAN栈中允许存放元素的最大个数typedefstruct{datatypedata[MAN];inttop;}stack;91.2栈的运算1.栈的基本操作⑴栈初始化：init(s)构造了一个空栈；⑵判栈空：empty(s)若栈s为空栈返回为1，否则返回为0；⑶入栈：push(s,N)在栈s的顶部插入一个新元素N，使N成为新的栈顶元素；⑷出栈：pop(s)栈s的顶部元素从栈中删除；⑸读栈顶元素：get(s)取栈顶元素作为结果返回；⑹置栈空：clear(s)清除栈s中的所有元素，使之成为空栈。102.栈的基本算法的实现⑴栈的初始化voidinit(stack*s){s->top=0;}⑵判空栈intempty(stack*s){if(s->top==0)return1;elsereturn0;}11⑶入栈voidpush(stack*s,datatypeN){if(s->top==MAN-1)printf("栈满");else{s->top++;s->data[s->top]=N;}}12⑷出栈voidpop(stack*s,datatype*N){if(empty(s))printf("栈空");else{*N=s->data[s->top]; s->top--; }}13⑸取栈顶元素datatypeget(stack*s){if(empty(s))printf("栈空"); elsereturn(s->data[s->top]);}141.3双栈的操作让两个栈共享一个数组的存储空间，让一个栈的栈底为该空间的始端，另一个栈的栈底为该空间的末端，当元素进栈时，都从两端向中间靠拢，这样就可以达到在使用过程中有的栈占有的空间多一些，有的栈占有的空间少一些，公共的剩余空间可以调节使用，从而提高了存储空间的利用率。123…n

mm+1…MAN-1

dataa1

a2

a3

…an

bm

…b2

b1top1top2栈2底栈1底双栈共享存储空间15存储结构可定义为#defineMAN双栈中允许存放元素的最大个数typedefstruct{datatypedata[MAN];inttop1,top2;}bothstack;用bothstack可以定义一个双栈ds：bothstackds;或bothstack*ds；161.进栈voidpush(bothstack*ds,datatypeN){if(ds->top2==ds->top1+1)printf("栈满");else{ds->top2--;ds->data[ds->top2]=N;}}172．出栈voidpop(bothstack*ds,datatype*N){if(ds->top2==MAN) printf("栈空"); else{*N=ds->data[ds->top2];ds->top2++; }}181.4栈的应用算法思路：把十进制数转换为二进制数采用的方法是“除2取余”，直到商为0。依次得到的余数是k1,k2,k3,……,km,而转换后的二进制数是kmkm-1…k3k2k1，从结果看恰好与计算过程相反，因此转换过程中每得到一位二进制数则进栈保存，转换完毕后依次出栈则正好是转换结果。此种方法同样适用于将十进制数转换为r进制的数。把十进制整数11转换为二进制的过程如下：211余数二进制位

低高

25

1k1

22

1k2

21

0k30

1k4例2-3编写一个算法将给定的十进制数转换为二进制数输出。19数值转换的算法typedefintdatatype;#defineMAN10voidtransfer(intn,intr)voidtransfer(intn,intr){stacks;{ints[MAN],top;/*定义一个顺序栈*/datatypeN;intN;init(s); top=0;/*初始化栈*/while(n) while(n){push(s,n%r); {s[++top]=n%r;/*余数入栈*/n=n/r; n=n/r;/*商作为被除数继续*/} }while(!empty(s))while(top!=0){pop(s,N); {N=s[top--];printf("%d",N); printf("%d",N);} }} }

算法一算法二20例2-4栈与递归

下面以n!为例，介绍如何将递归的算法改写为堆栈的非递归算法。n!=1

n==0或n==1/*递归终止条件*/n*(n-1)! n>0/*递归步骤*/intfact(intn){if(n==0||n==1)return1;elsereturn(n*fact(n-1));}21程序的执行过程图示fact(3)n=3f=3*fact(2)returnff=3*2*1*1n=2f=2*fact(1)returnff=2*1*1n=1f=1*fact(0)returnff=1*1n=0f=1returnff=1intfact(intn){if(n==0||n==1)return1;elsereturn(n*fact(n-1));}22阶乘的堆栈算法(非递归)typedefintdatatype;#defineMAN20intfact(intn) intfact(intn){stacks;datatypeN;intm=1;{ints[MAN],top=0,N,m=1;init(s); if(n==0||n==1)m=1;if(n==0||n==1)m=1;else{while(n>1)else{while(n>1) {s[++top]=n; {push(s,n);n--; n--; } }while(!empty(s))while(top!=0) {pop(s,N); {N=s[top--];m=m*N; m=m*N; } }} }returnm; returnm;} }算法一 算法二23例2-5算术表达式的求值1.算术表达式的两种表示方法⑴中缀表达式所谓中缀表达式就是把运算符放在两个运算对象之间的表达式。如3+5*3。实际中缀表达式就是经常习惯使用的算术表达式。①有括号出现时先算括号内的，后算括号外的，多层括号，由内向外进行；②在无括号或同层括号内的情况下，先做乘除运算，S后做加减运算；③同一优先级运算，从左向右依次进行。24⑵后缀表达式所谓后缀表达式就是把运算符放在两个运算对象之后的表达式。如3+5*3的后缀表达式是353*+其中运算对象和运算符之间用空格隔开。在后缀表达式中，不再引入括号，所有的计算按运算符出现的顺序，严格从左向右进行，即遇到运算符就将运算符前的两个运算对象进行计算，而不用再考虑运算规则和级别。所以计算机扫描一次就能完成运算。把中缀表达式转换成对应的后缀表达式的规则是：把每个运算符都移到他的两个运算对象的后面，然后删掉所有的括号即可。25例如:对下列各中缀表达式①5/2-7②15+6*(2+4）③3*(N+y)/(2-y)④(25+N)*(a*(a+b)+b)对应的后缀表达式分别为①52/7-②15624+*+③3Ny+*2y-/④25N+aab+*b+*262.中缀表达式转换成后缀表达式在将中缀表达式转化为后缀表达示的算法中，为了讨论方便我们设表达式中的运算对象只有一位数字，并将中缀表达式保存在字符数组a中，转换后的后缀表达式存储在字符数组b中，用一个字符数组s作为栈，设字符'='为表达式的结束符。算法思路如下：27先将输入的中缀表达式，存入字符数组a中，取出a数组中的每一个字符存于c变量中，对于每一个c变量的值做如下处理：①若c为数字，则存于数组b中；②若c为左括号'('，则将其压入栈s;③若c为右括号‘)’，则将栈s中左括号‘(’以后的运算符依次出栈，存于数组b中，然后将左括号'('出栈；④若c为‘+’或‘-’，则将栈s中左括号‘(’以后的所有运算符依次出栈，存于数组b中，然后将c压入栈s中；⑤若c为'*'或'/'，则将栈s中的栈顶端连续的'*'或'/'出栈，存于数组b中，然后将c压入栈s中⑥若c为'='，则将栈S中的所有运算符依次出栈，存于数组b中，然后将c存于数组b中，最后得到的后缀表达式存储在字符数组b中。28中缀转后缀的算法如下所示:#defineMAN50Voidtrans(){chara[MAN],b[MAN],s[MAN],c;inti=0,j,t=1,top=0;do{i++;scanf("%c",&a[i]);}while(a[i]!='='&&i<MAN);i=1;c=a[i];i++;while(c!='='){if(c>='0'&&c<='9'){b[t]=c;t++;}elseif(c=='('){top++;s[top]=c;}elseif(c==')'){while(s[top]!='('){b[t]=s[top];top--;t++}top--;}

elseif(c=='+'||c=='-'){while(top!=0&&s[top]!='('){b[t]=s[top];top--;t++;}top++;s[top]=c;}elseif(c=='*'||c=='/'){while(s[top]!='*'||s[top]!='/'){b[t]=s[top];top--;t++;}top++;s[top]=c;}c=a[i];i++;}while(top!=0){b[t]=s[top];t++;top--;}b[t]='=';

for(j=1;j<t;j++)printf("%c",b[j]);printf("\n");}29以中缀表达式2*(1+2)/2为例，其转换过程如图所示。其中a数组存放的是中缀表达式2*(1+2)/2=，b数组存放的是转换后的后缀表达式212+*2/=，s数组作为栈，暂存运算符。12345678910…a数组2*（1+2）/2=12345678910…b数组212+*2/=**（*（+/s栈303.后缀表达式求值后缀表达式值的计算是比较简单的，这是因为表达式中即无括号又无优先级的约束。具体做法：需要一个存放数值的栈s1，当从左向右扫描表达式时，每遇到一个操作数就送入栈中保存，每遇到一个运算符就从栈中取出两个操作数进行当前的计算，然后把结果再入栈，直到整个表达式结束，这时栈顶存放的值就是后缀表达式的结果。下面是后缀表达式求值的算法，在下面的算法中假设后缀表达式已被存入一个字符数组b中，且以'='为结束字符，为了简化问题，限定运算数的位数仅为一位。31后缀表达式求值算法:#defineMAN50floatcalcul(char*b){floats1[MAN],d;charc;inti=0,t=0,top=0;c=*b++;while(c!='='){d=c-'0';if(c>='0'&&c<='9'){top++;s1[top]=d;}else{switch(c){case'+':s1[top-1]=s1[top-1]+s1[top]:break;

case'-':s1[top-1]=s1[top-1]-s1[top];break;case'*':s1[top-1]=s1[top-1]*s1[top];break;case'/':s1[top-1]=s1[top-1]/s1[top];break;}top--;}c=*b++;}returns1[top];}32

仍以中缀表达式2*(1+2)/2为例，他的后缀表达式存放在b数组中。后缀表达式212+*2/=的求值过程如下所示。222进栈1211入栈22122入栈+231和2出栈，计算1+2，并将结果3入栈*62和3出栈，计算2*3，并将结果6入栈2622入栈/32和6出栈，计算6/2，并将结果3入栈=空结果3出栈332队列2.1队列的定义及顺序存储2.2队列的运算2.3循环队列342.1队列的定义及顺序存储1.队列的定义队列(queue)简称队。仅允许在表的一端进行插入，而在表的另一端进行删除。把允许插入的一端叫队尾(rear)，把允许删除的一端叫队首(front)。出队a1a2a3a4a5入队向队列中插入新元素称作进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称作出队，出队后，其后继元素成为队首元素。由于队列的插入和删除分别在两端进行，所以要删除的元素是队列中最先进入的元素，因此又把队列称作先进先出(FirstInFirstOut，简称FIFO)表。352.队列的顺序存储类型定义如下：#defineMAN队列的最大容量typedefstruct{datatypedata[MAN];intf,r;}queue;36队列的队首、队尾指针与队中数据元素的关系

012345678…MAN-1fr012345678…MAN-1a1

a2

a3

fr空队列f==r==0

3个元素

f==1,r==30123456789MAN-1a1

a2

a3

a4a5a6a7a8a9fr7个元素f==3,r==90123456789MAN-1a1

a2

a3

a4a5a6a7a8a9anfr

n-2个元素(队满)f==3,r==n372.2队列的运算1.队列的基本操作⑴队列初始化：init(q)构造了一个空队；⑵入队操作：insert(q,N)在队列q中插入一个元素N到队尾；⑶出队操作：delete(q,N)删除队首元素，可以返回其值；⑷读队头元素：get(q,N)取队头元素作为结果返回;⑸判队空操作：empty(q)若q为空队则返回为1，否则返回为0;⑹置队空：clear(q)清除队列q中的所有元素，使之成为空队列。382.队列的基本算法的实现⑴队列的初始化voidinit(queue*q){q->f=q->r=0;}⑵判空队列intempty(queue*q){if(q->f=