C語(yǔ)言程序設(shè)計(jì)-第十一章綜合實(shí)訓(xùn)-學(xué)生成績(jī)管理系統(tǒng)資料課件

項(xiàng)目十一綜合實(shí)訓(xùn)—學(xué)生成績(jī)管理系統(tǒng)1項(xiàng)目十一綜合實(shí)訓(xùn)—學(xué)生成績(jī)管理系統(tǒng)1【項(xiàng)目要求】

將從鍵盤(pán)輸入的十進(jìn)制數(shù)轉(zhuǎn)換為N（如二進(jìn)制、八進(jìn)制、十六進(jìn)制）進(jìn)制數(shù)據(jù)，利用順序棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換問(wèn)題

十進(jìn)制轉(zhuǎn)化成N進(jìn)制的算法是//整數(shù)部分為除N取余法,小數(shù)部分為乘N取整法。例如：對(duì)1348這個(gè)數(shù)，轉(zhuǎn)化為N進(jìn)制，也就是解方程1348=aN^5+bN^4+cN^3+dN^2+eN^1+f，目標(biāo)就是要求出系數(shù)a,b,c,d,e,f的值（也許a的前面還有w*N^6甚至7次方等等，但是次數(shù)太高的話(huà)就必然會(huì)是0），比如我們假定N=10的話(huà)，那么求出來(lái)的結(jié)果必然是a=b=0,c=1,d=3,e=4,f=8

。對(duì)于N進(jìn)制來(lái)說(shuō)，a,b,c,d,e,f的值都必然要小于N（否則就會(huì)向高位進(jìn)一），顯然求解的過(guò)程是：將1348除以10（令N=10）,則余數(shù)就是f

，即8,則商則是aN^4+bN^3+cN^2+dN^1+e，這樣進(jìn)一步除以10得e,依次得到d,c,b,a,可用堆棧來(lái)實(shí)現(xiàn)?！卷?xiàng)目分析】2【項(xiàng)目要求】將從鍵盤(pán)輸入的十進(jìn)制數(shù)轉(zhuǎn)換為N（如二進(jìn)制、八問(wèn)題情境及實(shí)現(xiàn)

/*

堆棧的應(yīng)用---進(jìn)制轉(zhuǎn)換

將十進(jìn)制轉(zhuǎn)換成其他進(jìn)制

*/

#include

<stdio.h>

#define

maNlen

100

typedef

struct

//堆棧的結(jié)構(gòu)大家應(yīng)該都很熟悉了

{

int

data[maNlen];

int

top;

}SeqStack;

void

InitStack(SeqStack

*

S)

//置棧空

{

S->top

=

-1;

}

3問(wèn)題情境及實(shí)現(xiàn)

/*

3問(wèn)題情境及實(shí)現(xiàn)

void

Pop(SeqStack

*

S,

int

*

N)

//出棧，N用來(lái)接受被彈出的數(shù)的

{

*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為一個(gè)十進(jìn)制數(shù)，d為進(jìn)制

{

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問(wèn)題情境及實(shí)現(xiàn)

4問(wèn)題情境及實(shí)現(xiàn)

int

main()

{

int

n,d,N;

//n為一個(gè)十進(jìn)制數(shù)，d為進(jìn)制

SeqStack

stack,

*S;

S

=

&stack;

while(scanf("%d

%d",&n,&d)

!=

EOF)

{

InitStack(S);

//初始化

Conversion(S,

n,

d);

if(n

<

0)

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

//若是負(fù)數(shù)

while(S->top

!=

-1)

{

Pop(S,

&N);

if(N

<

10)

printf("%d",N);

else

printf("%c",N

+

55);

//使輸出的時(shí)候大于9的輸出為字母ABC

}

printf("\n");

}

return

0;

}

5問(wèn)題情境及實(shí)現(xiàn)

int

main()

5相關(guān)知識(shí)1.棧2.隊(duì)列本講小結(jié)6相關(guān)知識(shí)1.棧2.隊(duì)列本講小結(jié)61棧1.1棧的定義及順序存儲(chǔ)1.2棧的運(yùn)算1.3雙棧的操作1.4棧的應(yīng)用71棧1.1棧的定義及順序存儲(chǔ)7棧滿(mǎn)1.1棧的定義及順序存儲(chǔ)1.棧的定義棧又叫堆棧，允許在表的一端進(jìn)行插入和刪除。后進(jìn)先出的線(xiàn)性表（簡(jiǎn)稱(chēng)LIFO表）。MAN-1┇i┇210top空棧a11個(gè)元素a3a2a13個(gè)元素a3a2a12個(gè)元素an┇┇a3a2a1toptoptoptop8棧滿(mǎn)1.1棧的定義及順序存儲(chǔ)1.棧的定義棧又叫堆2.棧的順序存儲(chǔ)

#defineMAN棧中允許存放元素的最大個(gè)數(shù)typedefstruct{datatypedata[MAN];inttop;}stack;92.棧的順序存儲(chǔ)#defineMAN棧中允許存放元素1.2棧的運(yùn)算1.棧的基本操作⑴棧初始化：init(s)構(gòu)造了一個(gè)空棧；⑵判棧空：empty(s)若棧s為空棧返回為1，否則返回為0；⑶入棧：push(s,N)在棧s的頂部插入一個(gè)新元素N，使N成為新的棧頂元素；⑷出棧：pop(s)棧s的頂部元素從棧中刪除；⑸讀棧頂元素：get(s)取棧頂元素作為結(jié)果返回；⑹置棧空：clear(s)清除棧s中的所有元素，使之成為空棧。101.2棧的運(yùn)算1.棧的基本操作⑴棧初始化：init2.棧的基本算法的實(shí)現(xiàn)⑴棧的初始化voidinit(stack*s){s->top=0;}⑵判空棧intempty(stack*s){if(s->top==0)return1;elsereturn0;}112.棧的基本算法的實(shí)現(xiàn)⑴棧的初始化voidinit(⑶入棧voidpush(stack*s,datatypeN){if(s->top==MAN-1)printf("棧滿(mǎn)");else{s->top++;s->data[s->top]=N;}}12⑶入棧voidpush(stack*s,data⑷出棧voidpop(stack*s,datatype*N){if(empty(s))printf("棧空");else{*N=s->data[s->top]; s->top--; }}13⑷出棧voidpop(stack*s,datatyp⑸取棧頂元素datatypeget(stack*s){if(empty(s))printf("?？?); elsereturn(s->data[s->top]);}14⑸取棧頂元素datatypeget(stack*s1.3雙棧的操作讓兩個(gè)棧共享一個(gè)數(shù)組的存儲(chǔ)空間，讓一個(gè)棧的棧底為該空間的始端，另一個(gè)棧的棧底為該空間的末端，當(dāng)元素進(jìn)棧時(shí)，都從兩端向中間靠攏，這樣就可以達(dá)到在使用過(guò)程中有的棧占有的空間多一些，有的棧占有的空間少一些，公共的剩余空間可以調(diào)節(jié)使用，從而提高了存儲(chǔ)空間的利用率。123…n

mm+1…MAN-1

dataa1

a2

a3

…an

bm

…b2

b1top1top2棧2底棧1底雙棧共享存儲(chǔ)空間151.3雙棧的操作讓兩個(gè)棧共享一個(gè)數(shù)組的存儲(chǔ)空間，讓一個(gè)棧的存儲(chǔ)結(jié)構(gòu)可定義為#defineMAN雙棧中允許存放元素的最大個(gè)數(shù)typedefstruct{datatypedata[MAN];inttop1,top2;}bothstack;用bothstack可以定義一個(gè)雙棧ds：bothstackds;或bothstack*ds；16存儲(chǔ)結(jié)構(gòu)可定義為#defineMAN雙棧中允許存放元素的1.進(jìn)棧voidpush(bothstack*ds,datatypeN){if(ds->top2==ds->top1+1)printf("棧滿(mǎn)");else{ds->top2--;ds->data[ds->top2]=N;}}171.進(jìn)棧voidpush(bothstack*ds2．出棧voidpop(bothstack*ds,datatype*N){if(ds->top2==MAN) printf("?？?); else{*N=ds->data[ds->top2];ds->top2++; }}182．出棧voidpop(bothstack*ds,d1.4棧的應(yīng)用算法思路：把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)采用的方法是“除2取余”，直到商為0。依次得到的余數(shù)是k1,k2,k3,……,km,而轉(zhuǎn)換后的二進(jìn)制數(shù)是kmkm-1…k3k2k1，從結(jié)果看恰好與計(jì)算過(guò)程相反，因此轉(zhuǎn)換過(guò)程中每得到一位二進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。此種方法同樣適用于將十進(jìn)制數(shù)轉(zhuǎn)換為r進(jìn)制的數(shù)。把十進(jìn)制整數(shù)11轉(zhuǎn)換為二進(jìn)制的過(guò)程如下：211余數(shù)二進(jìn)制位

低高

25

1k1

22

1k2

21

0k30

1k4例2-3編寫(xiě)一個(gè)算法將給定的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)輸出。191.4棧的應(yīng)用算法思路：把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)采用的方法數(shù)值轉(zhuǎn)換的算法typedefintdatatype;#defineMAN10voidtransfer(intn,intr)voidtransfer(intn,intr){stacks;{ints[MAN],top;/*定義一個(gè)順序棧*/datatypeN;intN;init(s); top=0;/*初始化棧*/while(n) while(n){push(s,n%r); {s[++top]=n%r;/*余數(shù)入棧*/n=n/r; n=n/r;/*商作為被除數(shù)繼續(xù)*/} }while(!empty(s))while(top!=0){pop(s,N); {N=s[top--];printf("%d",N); printf("%d",N);} }} }

算法一算法二20數(shù)值轉(zhuǎn)換的算法typedefintdatatype;例2-4棧與遞歸

下面以n!為例，介紹如何將遞歸的算法改寫(xiě)為堆棧的非遞歸算法。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例2-4棧與遞歸下面以n!為例，介紹如何將遞歸的算法程序的執(zhí)行過(guò)程圖示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程序的執(zhí)行過(guò)程圖示fact(3)n=3f=3*fact(2)階乘的堆棧算法(非遞歸)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階乘的堆棧算法(非遞歸)typedefintdataty例2-5算術(shù)表達(dá)式的求值1.算術(shù)表達(dá)式的兩種表示方法⑴中綴表達(dá)式所謂中綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之間的表達(dá)式。如3+5*3。實(shí)際中綴表達(dá)式就是經(jīng)常習(xí)慣使用的算術(shù)表達(dá)式。①有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行；②在無(wú)括號(hào)或同層括號(hào)內(nèi)的情況下，先做乘除運(yùn)算，S后做加減運(yùn)算；③同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。24例2-5算術(shù)表達(dá)式的求值1.算術(shù)表達(dá)式的兩種表示方法⑵后綴表達(dá)式所謂后綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之后的表達(dá)式。如3+5*3的后綴表達(dá)式是353*+其中運(yùn)算對(duì)象和運(yùn)算符之間用空格隔開(kāi)。在后綴表達(dá)式中，不再引入括號(hào)，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行，即遇到運(yùn)算符就將運(yùn)算符前的兩個(gè)運(yùn)算對(duì)象進(jìn)行計(jì)算，而不用再考慮運(yùn)算規(guī)則和級(jí)別。所以計(jì)算機(jī)掃描一次就能完成運(yùn)算。把中綴表達(dá)式轉(zhuǎn)換成對(duì)應(yīng)的后綴表達(dá)式的規(guī)則是：把每個(gè)運(yùn)算符都移到他的兩個(gè)運(yùn)算對(duì)象的后面，然后刪掉所有的括號(hào)即可。25⑵后綴表達(dá)式所謂后綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之例如:對(duì)下列各中綴表達(dá)式①5/2-7②15+6*(2+4）③3*(N+y)/(2-y)④(25+N)*(a*(a+b)+b)對(duì)應(yīng)的后綴表達(dá)式分別為①52/7-②15624+*+③3Ny+*2y-/④25N+aab+*b+*26例如:對(duì)下列各中綴表達(dá)式262.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式在將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示的算法中，為了討論方便我們?cè)O(shè)表達(dá)式中的運(yùn)算對(duì)象只有一位數(shù)字，并將中綴表達(dá)式保存在字符數(shù)組a中，轉(zhuǎn)換后的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中，用一個(gè)字符數(shù)組s作為棧，設(shè)字符'='為表達(dá)式的結(jié)束符。算法思路如下：272.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式在將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)字符存于c變量中，對(duì)于每一個(gè)c變量的值做如下處理：①若c為數(shù)字，則存于數(shù)組b中；②若c為左括號(hào)'('，則將其壓入棧s;③若c為右括號(hào)‘)’，則將棧s中左括號(hào)‘(’以后的運(yùn)算符依次出棧，存于數(shù)組b中，然后將左括號(hào)'('出棧；④若c為‘+’或‘-’，則將棧s中左括號(hào)‘(’以后的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c壓入棧s中；⑤若c為'*'或'/'，則將棧s中的棧頂端連續(xù)的'*'或'/'出棧，存于數(shù)組b中，然后將c壓入棧s中⑥若c為'='，則將棧S中的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c存于數(shù)組b中，最后得到的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中。28先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)中綴轉(zhuǎn)后綴的算法如下所示:#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中綴轉(zhuǎn)后綴的算法如下所示:elseif(c=='+以中綴表達(dá)式2*(1+2)/2為例，其轉(zhuǎn)換過(guò)程如圖所示。其中a數(shù)組存放的是中綴表達(dá)式2*(1+2)/2=，b數(shù)組存放的是轉(zhuǎn)換后的后綴表達(dá)式212+*2/=，s數(shù)組作為棧，暫存運(yùn)算符。12345678910…a數(shù)組2*（1+2）/2=12345678910…b數(shù)組212+*2/=**（*（+/s棧30以中綴表達(dá)式2*(1+2)/2為例，其轉(zhuǎn)換過(guò)程如圖所示。其中3.后綴表達(dá)式求值后綴表達(dá)式值的計(jì)算是比較簡(jiǎn)單的，這是因?yàn)楸磉_(dá)式中即無(wú)括號(hào)又無(wú)優(yōu)先級(jí)的約束。具體做法：需要一個(gè)存放數(shù)值的棧s1，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存，每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)棧頂存放的值就是后綴表達(dá)式的結(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)后綴表達(dá)式已被存入一個(gè)字符數(shù)組b中，且以'='為結(jié)束字符，為了簡(jiǎn)化問(wèn)題，限定運(yùn)算數(shù)的位數(shù)僅為一位。313.后綴表達(dá)式求值后綴表達(dá)式值的計(jì)算是比較簡(jiǎn)單的，這是因?yàn)楹缶Y表達(dá)式求值算法:#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后綴表達(dá)式求值算法:#defineMAN5032

仍以中綴表達(dá)式2*(1+2)/2為例，他的后綴表達(dá)式存放在b數(shù)組中。后綴表達(dá)式212+*2/=的求值過(guò)程如下所示。222進(jìn)棧1211入棧22122入棧+231和2出棧，計(jì)算1+2，并將結(jié)果3入棧*62和3出棧，計(jì)算2*3，并將結(jié)果6入棧2622入棧/32和6出棧，計(jì)算6/2，并將結(jié)果3入棧=空結(jié)果3出棧33仍以中綴表達(dá)式2*(1+2)/2為例，他的后綴表達(dá)式存放2隊(duì)列2.1隊(duì)列的定義及順序存儲(chǔ)2.2隊(duì)列的運(yùn)算2.3循環(huán)隊(duì)列342隊(duì)列2.1隊(duì)列的定義及順序存儲(chǔ)342.1隊(duì)列的定義及順序存儲(chǔ)1.隊(duì)列的定義隊(duì)列(queue)簡(jiǎn)稱(chēng)隊(duì)。僅允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。把允許插入的一端叫隊(duì)尾(rear)，把允許刪除的一端叫隊(duì)首(front)。出隊(duì)a1a2a3a4a5入隊(duì)向隊(duì)列中插入新元素稱(chēng)作進(jìn)隊(duì)或入隊(duì)，新元素進(jìn)隊(duì)后就成為新的隊(duì)尾元素；從隊(duì)列中刪除元素稱(chēng)作出隊(duì)，出隊(duì)后，其后繼元素成為隊(duì)首元素。由于隊(duì)列的插入和刪除分別在兩端進(jìn)行，所以要?jiǎng)h除的元素是隊(duì)列中最先進(jìn)入的元素，因此又把隊(duì)列稱(chēng)作先進(jìn)先出(FirstInFirstOut，簡(jiǎn)稱(chēng)FIFO)表。352.1隊(duì)列的定義及順序存儲(chǔ)1.隊(duì)列的定義隊(duì)列(que2.隊(duì)列的順序存儲(chǔ)類(lèi)型定義如下：#defineMAN隊(duì)列的最大容量typedefstruct{datatypedata[MAN];intf,r;}queue;362.隊(duì)列的順序存儲(chǔ)類(lèi)型定義如下：36隊(duì)列的隊(duì)首、隊(duì)尾指針與隊(duì)中數(shù)據(jù)元素的關(guān)系

012345678…MAN-1fr012345678…MAN-1a1

a2

a3

fr空隊(duì)列f==r==0

3個(gè)元素

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

a2

a3

a4a5a6a7a8a9fr7個(gè)元素f==3,r==90123456789MAN-1a1

a2

a3

a4a5a6a7a8a9anfr

n-2個(gè)元素(隊(duì)滿(mǎn))f==3,r==n37隊(duì)列的隊(duì)首、隊(duì)尾指針與隊(duì)中數(shù)據(jù)元素的關(guān)系0123456782.2隊(duì)列的運(yùn)算1.隊(duì)列的基本操作⑴隊(duì)列初始化：init(q)構(gòu)造了一個(gè)空隊(duì)；⑵入隊(duì)操作：insert(q,N)在隊(duì)列q中插入一個(gè)元素N到隊(duì)尾；⑶出隊(duì)操作：delete(q,N)刪除隊(duì)首元素，可以返回其值；⑷讀隊(duì)頭元素：get(q,N)取隊(duì)頭元素作為結(jié)果返回;⑸判隊(duì)空操作：empty(q)若q為空隊(duì)則返回為1，否則返回為0;⑹置隊(duì)空：clear(q)清除隊(duì)列q中的所有元素，使之成為空隊(duì)列。382.2隊(duì)列的運(yùn)算1.隊(duì)列的基本操作⑴2.隊(duì)列的基本算法的實(shí)現(xiàn)⑴隊(duì)列的初始化voidinit(queue*q){q->f=q->r=0;}⑵判空隊(duì)列intempty(queue*q){if(q->f==0&&q->r=0)return1;elsereturn0;}392.隊(duì)列的基本算法的實(shí)現(xiàn)⑴隊(duì)列的初始化voidini⑶入隊(duì)入隊(duì)時(shí)，首先判隊(duì)是否滿(mǎn)了，隊(duì)滿(mǎn)的條件為：q->r==MAN-1，隊(duì)滿(mǎn)時(shí)，不能入隊(duì)，可以進(jìn)行溢出錯(cuò)誤處理，若可以入隊(duì)則先將隊(duì)尾指針后移(q->r++)，再將元素賦給隊(duì)尾單元。voidinsert(queue*q,datatypeN){if(q->r==MAN-1)printf("隊(duì)滿(mǎn)");else{if(q->f==0&&q->r==0)q->f=++q->r;elseq->r++;q->data[q->r]=N;}}40⑶入隊(duì)入隊(duì)時(shí)，首先判隊(duì)是否滿(mǎn)了，隊(duì)滿(mǎn)的條件為：q->r⑷出隊(duì)列先判隊(duì)列是否為空，為空時(shí)不能出隊(duì)，若可以出隊(duì)，則可先將隊(duì)首元素賦給指定變量（若不需要保留，可以省去這一步），隊(duì)首指針后移（q->f--）。voiddelete(queue*q,datatype*N){if(empty(q))printf("隊(duì)空");else{*N=q->data[q->f];if(q->f==q->r)q->f=q->r=0;elseq->f++; }}41⑷出隊(duì)列先判隊(duì)列是否為空，為空時(shí)不能出隊(duì)，若可以出隊(duì)，則⑸取隊(duì)首元素先判隊(duì)列是否為空，為空時(shí)不能取元素，否則取出隊(duì)首元素，但隊(duì)首指針保持不變。datatypeget(queue*q){if(empty(q))printf("隊(duì)空"); elsereturn(q->data[q->f]);}42⑸取隊(duì)首元素先判隊(duì)列是否為空，為空時(shí)不能取元素，否則取出rf01a9a8a7a6a5…2.3循環(huán)隊(duì)列將隊(duì)列的數(shù)據(jù)區(qū)data[1]至data[MAN]看成頭尾相接的循環(huán)結(jié)構(gòu)，頭尾指針的關(guān)系不變，將其稱(chēng)為循環(huán)隊(duì)列.43rf01a9a8a7a6a5…2.3循環(huán)隊(duì)列將隊(duì)列的數(shù)據(jù)⑴入隊(duì)voidinsert(queue*q,datatypeN){if((q->r%(MAN-1)+1==q->f)printf("隊(duì)滿(mǎn)");else{q->r=q->r%(MAN-1)+1;q->data[q->r]=N;}}44⑴入隊(duì)voidinsert(queue*q,d⑵出隊(duì)voiddelete(queue*q,datatype*N){if(q->r==0&&q->f==0))printf("隊(duì)空"); else{*N=q->data[q->f];if(q->f==q->r) q->f=q->r=0; elseq->f=q->f%(MAN-1)+1; }}45⑵出隊(duì)voiddelete(queue*q,da項(xiàng)目十一綜合實(shí)訓(xùn)—學(xué)生成績(jī)管理系統(tǒng)46項(xiàng)目十一綜合實(shí)訓(xùn)—學(xué)生成績(jī)管理系統(tǒng)1【項(xiàng)目要求】

將從鍵盤(pán)輸入的十進(jìn)制數(shù)轉(zhuǎn)換為N（如二進(jìn)制、八進(jìn)制、十六進(jìn)制）進(jìn)制數(shù)據(jù)，利用順序棧實(shí)現(xiàn)數(shù)制轉(zhuǎn)換問(wèn)題

十進(jìn)制轉(zhuǎn)化成N進(jìn)制的算法是//整數(shù)部分為除N取余法,小數(shù)部分為乘N取整法。例如：對(duì)1348這個(gè)數(shù)，轉(zhuǎn)化為N進(jìn)制，也就是解方程1348=aN^5+bN^4+cN^3+dN^2+eN^1+f，目標(biāo)就是要求出系數(shù)a,b,c,d,e,f的值（也許a的前面還有w*N^6甚至7次方等等，但是次數(shù)太高的話(huà)就必然會(huì)是0），比如我們假定N=10的話(huà)，那么求出來(lái)的結(jié)果必然是a=b=0,c=1,d=3,e=4,f=8

。對(duì)于N進(jìn)制來(lái)說(shuō)，a,b,c,d,e,f的值都必然要小于N（否則就會(huì)向高位進(jìn)一），顯然求解的過(guò)程是：將1348除以10（令N=10）,則余數(shù)就是f

，即8,則商則是aN^4+bN^3+cN^2+dN^1+e，這樣進(jìn)一步除以10得e,依次得到d,c,b,a,可用堆棧來(lái)實(shí)現(xiàn)?！卷?xiàng)目分析】47【項(xiàng)目要求】將從鍵盤(pán)輸入的十進(jìn)制數(shù)轉(zhuǎn)換為N（如二進(jìn)制、八問(wèn)題情境及實(shí)現(xiàn)

/*

堆棧的應(yīng)用---進(jìn)制轉(zhuǎn)換

將十進(jìn)制轉(zhuǎn)換成其他進(jìn)制

*/

#include

<stdio.h>

#define

maNlen

100

typedef

struct

//堆棧的結(jié)構(gòu)大家應(yīng)該都很熟悉了

{

int

data[maNlen];

int

top;

}SeqStack;

void

InitStack(SeqStack

*

S)

//置?？?/p>

{

S->top

=

-1;

}

48問(wèn)題情境及實(shí)現(xiàn)

/*

3問(wèn)題情境及實(shí)現(xiàn)

void

Pop(SeqStack

*

S,

int

*

N)

//出棧，N用來(lái)接受被彈出的數(shù)的

{

*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為一個(gè)十進(jìn)制數(shù)，d為進(jìn)制

{

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;

}

}

49問(wèn)題情境及實(shí)現(xiàn)

4問(wèn)題情境及實(shí)現(xiàn)

int

main()

{

int

n,d,N;

//n為一個(gè)十進(jìn)制數(shù)，d為進(jìn)制

SeqStack

stack,

*S;

S

=

&stack;

while(scanf("%d

%d",&n,&d)

!=

EOF)

{

InitStack(S);

//初始化

Conversion(S,

n,

d);

if(n

<

0)

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

//若是負(fù)數(shù)

while(S->top

!=

-1)

{

Pop(S,

&N);

if(N

<

10)

printf("%d",N);

else

printf("%c",N

+

55);

//使輸出的時(shí)候大于9的輸出為字母ABC

}

printf("\n");

}

return

0;

}

50問(wèn)題情境及實(shí)現(xiàn)

int

main()

5相關(guān)知識(shí)1.棧2.隊(duì)列本講小結(jié)51相關(guān)知識(shí)1.棧2.隊(duì)列本講小結(jié)61棧1.1棧的定義及順序存儲(chǔ)1.2棧的運(yùn)算1.3雙棧的操作1.4棧的應(yīng)用521棧1.1棧的定義及順序存儲(chǔ)7棧滿(mǎn)1.1棧的定義及順序存儲(chǔ)1.棧的定義棧又叫堆棧，允許在表的一端進(jìn)行插入和刪除。后進(jìn)先出的線(xiàn)性表（簡(jiǎn)稱(chēng)LIFO表）。MAN-1┇i┇210top空棧a11個(gè)元素a3a2a13個(gè)元素a3a2a12個(gè)元素an┇┇a3a2a1toptoptoptop53棧滿(mǎn)1.1棧的定義及順序存儲(chǔ)1.棧的定義棧又叫堆2.棧的順序存儲(chǔ)

#defineMAN棧中允許存放元素的最大個(gè)數(shù)typedefstruct{datatypedata[MAN];inttop;}stack;542.棧的順序存儲(chǔ)#defineMAN棧中允許存放元素1.2棧的運(yùn)算1.棧的基本操作⑴棧初始化：init(s)構(gòu)造了一個(gè)空棧；⑵判?？眨篹mpty(s)若棧s為空棧返回為1，否則返回為0；⑶入棧：push(s,N)在棧s的頂部插入一個(gè)新元素N，使N成為新的棧頂元素；⑷出棧：pop(s)棧s的頂部元素從棧中刪除；⑸讀棧頂元素：get(s)取棧頂元素作為結(jié)果返回；⑹置棧空：clear(s)清除棧s中的所有元素，使之成為空棧。551.2棧的運(yùn)算1.棧的基本操作⑴棧初始化：init2.棧的基本算法的實(shí)現(xiàn)⑴棧的初始化voidinit(stack*s){s->top=0;}⑵判空棧intempty(stack*s){if(s->top==0)return1;elsereturn0;}562.棧的基本算法的實(shí)現(xiàn)⑴棧的初始化voidinit(⑶入棧voidpush(stack*s,datatypeN){if(s->top==MAN-1)printf("棧滿(mǎn)");else{s->top++;s->data[s->top]=N;}}57⑶入棧voidpush(stack*s,data⑷出棧voidpop(stack*s,datatype*N){if(empty(s))printf("?？?);else{*N=s->data[s->top]; s->top--; }}58⑷出棧voidpop(stack*s,datatyp⑸取棧頂元素datatypeget(stack*s){if(empty(s))printf("棧空"); elsereturn(s->data[s->top]);}59⑸取棧頂元素datatypeget(stack*s1.3雙棧的操作讓兩個(gè)棧共享一個(gè)數(shù)組的存儲(chǔ)空間，讓一個(gè)棧的棧底為該空間的始端，另一個(gè)棧的棧底為該空間的末端，當(dāng)元素進(jìn)棧時(shí)，都從兩端向中間靠攏，這樣就可以達(dá)到在使用過(guò)程中有的棧占有的空間多一些，有的棧占有的空間少一些，公共的剩余空間可以調(diào)節(jié)使用，從而提高了存儲(chǔ)空間的利用率。123…n

mm+1…MAN-1

dataa1

a2

a3

…an

bm

…b2

b1top1top2棧2底棧1底雙棧共享存儲(chǔ)空間601.3雙棧的操作讓兩個(gè)棧共享一個(gè)數(shù)組的存儲(chǔ)空間，讓一個(gè)棧的存儲(chǔ)結(jié)構(gòu)可定義為#defineMAN雙棧中允許存放元素的最大個(gè)數(shù)typedefstruct{datatypedata[MAN];inttop1,top2;}bothstack;用bothstack可以定義一個(gè)雙棧ds：bothstackds;或bothstack*ds；61存儲(chǔ)結(jié)構(gòu)可定義為#defineMAN雙棧中允許存放元素的1.進(jìn)棧voidpush(bothstack*ds,datatypeN){if(ds->top2==ds->top1+1)printf("棧滿(mǎn)");else{ds->top2--;ds->data[ds->top2]=N;}}621.進(jìn)棧voidpush(bothstack*ds2．出棧voidpop(bothstack*ds,datatype*N){if(ds->top2==MAN) printf("?？?); else{*N=ds->data[ds->top2];ds->top2++; }}632．出棧voidpop(bothstack*ds,d1.4棧的應(yīng)用算法思路：把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)采用的方法是“除2取余”，直到商為0。依次得到的余數(shù)是k1,k2,k3,……,km,而轉(zhuǎn)換后的二進(jìn)制數(shù)是kmkm-1…k3k2k1，從結(jié)果看恰好與計(jì)算過(guò)程相反，因此轉(zhuǎn)換過(guò)程中每得到一位二進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。此種方法同樣適用于將十進(jìn)制數(shù)轉(zhuǎn)換為r進(jìn)制的數(shù)。把十進(jìn)制整數(shù)11轉(zhuǎn)換為二進(jìn)制的過(guò)程如下：211余數(shù)二進(jìn)制位

低高

25

1k1

22

1k2

21

0k30

1k4例2-3編寫(xiě)一個(gè)算法將給定的十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)輸出。641.4棧的應(yīng)用算法思路：把十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)采用的方法數(shù)值轉(zhuǎn)換的算法typedefintdatatype;#defineMAN10voidtransfer(intn,intr)voidtransfer(intn,intr){stacks;{ints[MAN],top;/*定義一個(gè)順序棧*/datatypeN;intN;init(s); top=0;/*初始化棧*/while(n) while(n){push(s,n%r); {s[++top]=n%r;/*余數(shù)入棧*/n=n/r; n=n/r;/*商作為被除數(shù)繼續(xù)*/} }while(!empty(s))while(top!=0){pop(s,N); {N=s[top--];printf("%d",N); printf("%d",N);} }} }

算法一算法二65數(shù)值轉(zhuǎn)換的算法typedefintdatatype;例2-4棧與遞歸

下面以n!為例，介紹如何將遞歸的算法改寫(xiě)為堆棧的非遞歸算法。n!=1

n==0或n==1/*遞歸終止條件*/n*(n-1)! n>0/*遞歸步驟*/intfact(intn){if(n==0||n==1)return1;elsereturn(n*fact(n-1));}66例2-4棧與遞歸下面以n!為例，介紹如何將遞歸的算法程序的執(zhí)行過(guò)程圖示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));}67程序的執(zhí)行過(guò)程圖示fact(3)n=3f=3*fact(2)階乘的堆棧算法(非遞歸)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;} }算法一 算法二68階乘的堆棧算法(非遞歸)typedefintdataty例2-5算術(shù)表達(dá)式的求值1.算術(shù)表達(dá)式的兩種表示方法⑴中綴表達(dá)式所謂中綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之間的表達(dá)式。如3+5*3。實(shí)際中綴表達(dá)式就是經(jīng)常習(xí)慣使用的算術(shù)表達(dá)式。①有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行；②在無(wú)括號(hào)或同層括號(hào)內(nèi)的情況下，先做乘除運(yùn)算，S后做加減運(yùn)算；③同一優(yōu)先級(jí)運(yùn)算，從左向右依次進(jìn)行。69例2-5算術(shù)表達(dá)式的求值1.算術(shù)表達(dá)式的兩種表示方法⑵后綴表達(dá)式所謂后綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之后的表達(dá)式。如3+5*3的后綴表達(dá)式是353*+其中運(yùn)算對(duì)象和運(yùn)算符之間用空格隔開(kāi)。在后綴表達(dá)式中，不再引入括號(hào)，所有的計(jì)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行，即遇到運(yùn)算符就將運(yùn)算符前的兩個(gè)運(yùn)算對(duì)象進(jìn)行計(jì)算，而不用再考慮運(yùn)算規(guī)則和級(jí)別。所以計(jì)算機(jī)掃描一次就能完成運(yùn)算。把中綴表達(dá)式轉(zhuǎn)換成對(duì)應(yīng)的后綴表達(dá)式的規(guī)則是：把每個(gè)運(yùn)算符都移到他的兩個(gè)運(yùn)算對(duì)象的后面，然后刪掉所有的括號(hào)即可。70⑵后綴表達(dá)式所謂后綴表達(dá)式就是把運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之例如:對(duì)下列各中綴表達(dá)式①5/2-7②15+6*(2+4）③3*(N+y)/(2-y)④(25+N)*(a*(a+b)+b)對(duì)應(yīng)的后綴表達(dá)式分別為①52/7-②15624+*+③3Ny+*2y-/④25N+aab+*b+*71例如:對(duì)下列各中綴表達(dá)式262.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式在將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)示的算法中，為了討論方便我們?cè)O(shè)表達(dá)式中的運(yùn)算對(duì)象只有一位數(shù)字，并將中綴表達(dá)式保存在字符數(shù)組a中，轉(zhuǎn)換后的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中，用一個(gè)字符數(shù)組s作為棧，設(shè)字符'='為表達(dá)式的結(jié)束符。算法思路如下：722.中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式在將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)字符存于c變量中，對(duì)于每一個(gè)c變量的值做如下處理：①若c為數(shù)字，則存于數(shù)組b中；②若c為左括號(hào)'('，則將其壓入棧s;③若c為右括號(hào)‘)’，則將棧s中左括號(hào)‘(’以后的運(yùn)算符依次出棧，存于數(shù)組b中，然后將左括號(hào)'('出棧；④若c為‘+’或‘-’，則將棧s中左括號(hào)‘(’以后的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c壓入棧s中；⑤若c為'*'或'/'，則將棧s中的棧頂端連續(xù)的'*'或'/'出棧，存于數(shù)組b中，然后將c壓入棧s中⑥若c為'='，則將棧S中的所有運(yùn)算符依次出棧，存于數(shù)組b中，然后將c存于數(shù)組b中，最后得到的后綴表達(dá)式存儲(chǔ)在字符數(shù)組b中。73先將輸入的中綴表達(dá)式，存入字符數(shù)組a中，取出a數(shù)組中的每一個(gè)中綴轉(zhuǎn)后綴的算法如下所示:#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");}74中綴轉(zhuǎn)后綴的算法如下所示:elseif(c=='+以中綴表達(dá)式2*(1+2)/2為例，其轉(zhuǎn)換過(guò)程如圖所示。其中a數(shù)組存放的是中綴表達(dá)式2*(1+2)/2=，b數(shù)組存放的是轉(zhuǎn)換后的后綴表達(dá)式212+*2/=，s數(shù)組作為棧，暫存運(yùn)算符。12345678910…a數(shù)組2*（1+2）/2=12345678910…b數(shù)組212+*2/=**（*（+/s棧75以中綴表達(dá)式2*(1+2)/2為例，其轉(zhuǎn)換過(guò)程如圖所示。其中3.后綴表達(dá)式求值后綴表達(dá)式值的計(jì)算是比較簡(jiǎn)單的，這是因?yàn)楸磉_(dá)式中即無(wú)括號(hào)又無(wú)優(yōu)先級(jí)的約束。具體做法：需要一個(gè)存放數(shù)值的棧s1，當(dāng)從左向右掃描表達(dá)式時(shí)，每遇到一個(gè)操作數(shù)就送入棧中保存，每遇到一個(gè)運(yùn)算符就從棧中取出兩個(gè)操作數(shù)進(jìn)行當(dāng)前的計(jì)算，然后把結(jié)果再入棧，直到整個(gè)表達(dá)式結(jié)束，這時(shí)棧頂存放的值就是后綴表達(dá)式的結(jié)果。下面是后綴表達(dá)式求值的算法，在下面的算法中假設(shè)后綴表達(dá)式已被存入一個(gè)字符數(shù)組b中，且以'='為結(jié)束字符，為了簡(jiǎn)化問(wèn)題，限定運(yùn)算數(shù)的位數(shù)僅為一位。763.后綴表達(dá)式求值后綴表達(dá)式值的計(jì)算是比較簡(jiǎn)單的，這是因?yàn)楹缶Y表達(dá)式求值算法:#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];}77后綴表達(dá)式求值算法:#defineMAN5032

仍以中綴表達(dá)式2*(1+2)/2為例，他的后綴表達(dá)式存放在b數(shù)組中。后綴表達(dá)式212+*2/=的求值過(guò)程如下所示。222進(jìn)棧1211入棧22122入棧+231和2出棧，計(jì)算1+2，并將結(jié)果3入棧*62和3出棧，計(jì)算2*3，并將結(jié)果6入棧2622入棧/32和6出棧，計(jì)算6/2，并將結(jié)果3入棧=空結(jié)果3出棧78仍以中綴表達(dá)式2*(1+2)/2為例，他的后綴表達(dá)式存放2隊(duì)列2.1隊(duì)列的定義及順序存儲(chǔ)2.2隊(duì)列的運(yùn)算2.3循環(huán)隊(duì)列792隊(duì)列2.1隊(duì)列的定義及順序存儲(chǔ)342.1隊(duì)列的定義及順序存儲(chǔ)1.隊(duì)列