【文章內(nèi)容簡(jiǎn)介】 data。/*將隊(duì)頭元素賦值給e，取出隊(duì)頭元素*/return 1。} } /*出隊(duì)操作。*/ int DeleteQueue(LinkQueue *Q,DataType *x){/* 將隊(duì)列Q的隊(duì)頭元素出隊(duì)，并存放到x所指的存儲(chǔ)空間中 */ LQNode * p。if(Qfront==Qrear)return(0)。p=Qfrontnext。Qfrontnext=pnext。/* 隊(duì)頭元素p出隊(duì) */ if(Qfront==NULL)/* 如果隊(duì)中只有一個(gè)元素p，則p出隊(duì)后成為空隊(duì) */Qrear=Qfront。*x=pdata。free(p)。/* 釋放存儲(chǔ)空間 */ return(1)。} void YangHuiTriangle(int N)/*鏈?zhǔn)疥?duì)列實(shí)現(xiàn)打印楊輝三角*/ {int i,j,k,n。DataType e,t。int temp[MaxSize]。LinkQueue Q。k=0。InitQueue(amp。Q)。EnterQueue(amp。Q,1)。/*產(chǎn)生第中間n2行的元素*/ for(n=2。n在臨時(shí)數(shù)組中*/ {k=0。EnterQueue(amp。Q,1)。for(i=1。i并入隊(duì)列*/{DeleteQueue(amp。Q,amp。t)。temp[k++]=t。GetHead(Q,amp。e)。t=t+e。EnterQueue(amp。Q,t)。}DeleteQueue(amp。Q,amp。t)。temp[k++]=t。PrintArray(temp,k,N)。EnterQueue(amp。Q,1)。} k=0。while(!QueueEmpty(Q)){/*定義一個(gè)臨時(shí)數(shù)組，用于存放每一行的元素*/ /*初始化鏈隊(duì)列*/ /*第一行元素入隊(duì)*/ /*產(chǎn)生第i行元素并入隊(duì)，同時(shí)將第i1行的元素保存/*第i行的第一個(gè)元素入隊(duì)*/ /*利用隊(duì)列中第i1行元素產(chǎn)生第i行的中間i2個(gè)元素/*將第i1行的元素存入臨時(shí)數(shù)組*//*取隊(duì)頭元素*/ /*利用隊(duì)中第i1行元素產(chǎn)生第i行元素*/ /*將第i1行的最后一個(gè)元素存入臨時(shí)數(shù)組*/ /*第i行的最后一個(gè)元素入隊(duì)*/ /*將最后一行元素存入數(shù)組之前，要將下標(biāo)k置為0*/ /*將最后一行元素存入臨時(shí)數(shù)組*/DeleteQueue(amp。Q,amp。t)。temp[k++]=t。if(QueueEmpty(Q))PrintArray(temp,k,N)。} }void main(){ int n。printf(“請(qǐng)輸入要打印的行數(shù)：n=:”)。scanf(“%d”,amp。n)。YangHuiTriangle(n)。} void PrintArray(int a[],int n,int N)/*打印數(shù)組中的元素，使能夠呈正確的形式輸出*/ { int i。static count=0。/*記錄輸出的行*/ for(i=0。i/*打印空格*/printf(“”)。count++。for(i=0。i/*打印數(shù)組中的元素*/printf(“%6d”,a[i])。printf(“n”)。} l 用棧實(shí)現(xiàn)迷宮問題求解 include includedefine OVERFLOW1 define MAX 100 typedef struct {int x。int y。int d。}Data。typedef struct {int pos。Data data[MAX]。}SNode,*Stack。Stack InitStack(){Stack pStack。pStack=(Stack)malloc(sizeof(SNode))。if(!pStack)exit(OVERFLOW)。pStackpos=1。return pStack。}int IsEmpty(Stack pstack){return pstackpos==1。}void Push(Stack pStack,Data x){if(pStackpos=MAX1)exit(OVERFLOW)。else{pStackpos++。pStackdata[pStackpos]=x。} }void Pop(Stack pStack){if(pStackpos==1)exit(OVERFLOW)。elsepStackpos。}Data GetTop(Stack pStack){return pStackdata[pStackpos]。}Data SetStackElem(int x,int y,int d){Data element。=x。=y。=0。return element。}void DisplayPath(Stack pStack){Data element。printf(“The path is:n”)。while(!IsEmpty(pStack)){element=GetTop(pStack)。Pop(pStack)。printf(“The node is:(%d,%d)n”,)。} }void MazePath(int maze[8][11],int direction[4][2],int x1,int y1,int x2,int y2){int i,j,k,g,h。Stack pStack。Data element。pStack=InitStack()。maze[x1][y1]=2。Push(pStack,SetStackElem(x1,y1,0))。while(!IsEmpty(pStack)){element=GetTop(pStack)。Pop(pStack)。i=。j=。k = 。while(k{g=i+direction[k][0]。h=j+direction[k][1]。if(g==x2 amp。amp。 h==y2 amp。amp。 maze[g][h]==0){Push(pStack,SetStackElem(i,j,k))。Push(pStack,SetStackElem(x2,y2,k))。DisplayPath(pStack)。return。}if(maze[g][h]==0){maze[g][h]=2。Push(pStack,SetStackElem(i,j,k+1))。i=g。j=h。k=0。}elsek++。} }printf(“The path has not been foundn”)。}void main(){int direction[4][2]={0,1,1,0,0,1,1,0}。int maze[8][11]= {1,1,1,1,1,1,1,1,1,1,1，1,0,1,0,0,1,1,1,0,0,1，1,0,0,0,0,0,1,0,0,1,1，1,0,1,1,1,0,0,0,1,1,1，1,0,0,0,1,0,1,1,0,1,1，1,1,0,0,1,0,1,1,0,0,1，1,1,1,0,1,0,0,0,0,0,1，1,1,1,1,1,1,1,1,1,1,1 }。int i,j。printf(“The maze is:n”)。for(i=0。ifor(j=0。jprintf(“%2d”,maze[i][j])。printf(“n”)。}。MazePath(maze,direction,1,1,6,9)。} l 用隊(duì)列實(shí)現(xiàn)迷宮問題求解 include define r 64 define m2 8 define n2 10 int m=m22,n=n22。typedef struct { int x,y。//行列坐標(biāo)int pre。}sqtype。sqtype sq[r]。struct moved { int x, y。//坐標(biāo)增量，取值1，0，1 }move[8]。int maze[m2][n2]。int PATH(int maze[][n2])//找迷宮maze的路徑 { int i,j,k,v,front,rear,x,y。int mark[m2][n2]。for(i=0。ifor(j=0。jmark[i ][j]=0。printf(“Please Input move arrayn”)。for(i=0。i//標(biāo)記入口以到達(dá)過while(frontx=sq[front].x。y=sq[front].y。//(x,y)為出發(fā)點(diǎn)for(v=0。v{i=x+move[v].x。j=y+move[v].y。if((maze[i ][j]==0)amp。amp。(mark[i ][j]==0))//(i,j)為可以到達(dá)點(diǎn)，將起入隊(duì){rear++。sq[rear].pre=front。mark[i ][j]=1。//標(biāo)記(i,j)已經(jīng)到達(dá)過}if((i==m)amp。amp。(j==n))//到達(dá)出口{printf(“THE PATH: n”)。k=rear。do{printf(“(%d %d)k=sq[k].pre。//找前一點(diǎn)}while(k!=0)。//k=0是已經(jīng)到達(dá)for(i=1。iprintf(“%3d”,i)。printf(“n”)。for(i=1。iprintf(“%3d”,sq[i ].x)。printf(“n”)。for(i=1。iprintf(“%3d”,sq[i ].y)。printf(“n”)。for(i=1。iprintf(“%3d”,sq[i ].pre)。printf(“n”)。return(1)。//成功返回}}front++。//出隊(duì)，front 指向新的出發(fā)點(diǎn)}}//隊(duì)空，循環(huán)結(jié)束printf(“There is no path!n”)。return(0)。//迷宮沒有路徑返回 }main(){ int i,j。for(i=0。imaze[0][i ]=1。maze[7][i ]=1。} for(i=0。imaze[i ][0]=1。maze[i ][9]=1。} /*for(i=1。ifor(j=1。j{printf(“%d %d”,i,j)。scanf(“%d”,amp。maze[i ][j])。}*/maze[1][1]=0。maze[1][2]=1。maze[1][3]=0。maze[1][4]=1。maze[1][5]=1。maze[1][6]=0。maze[1][7]=1。maze[1][8]=1。maze[2][1]=1。maze[2][2]=0。maze[2][3]=0。maze[2][4]=1。maze[2][5]=1。maze[2][6]=0。maze[2][7]=1。maze[2][8]=0。maze[3][1]=0。maze[3][2]=1。maze[3][3]=1。maze[3][4]=0。maze[3][5]=0。maze[3][6]=1。maze[3][7]=1。maze[3][8]=1。maze[4][1]=1。maze[4][2]=0。maze[4][3]=0。maze[4][4]=1。maze[4][5]=1。maze[4][6]=0。maze[3][7]=0。maze[4][8]=1。maze[5][1]=1。maze[5][2]=1。maze[5][3]=0。maze[5][4]=0。maze[5][5]=1。maze[5][6]=1。maze[5][7]=0。maze[5][8]=1。maze[6][1]=0。maze[6][2]=1。maze[6][3]=1。maze[6][4]=1。maze[6][5]=0。maze[6][6]=0。maze[6][7]=0。maze[6][8]=0。printf(“n”)。for(i=0。ifor(j=0。jprintf(“%d”,maze[i ][j])。printf(“n”)。} PATH(maze)。}l 分別用隊(duì)列實(shí)現(xiàn)一個(gè)列車調(diào)度系統(tǒng)。實(shí)驗(yàn)3 樹的應(yīng)用一、實(shí)驗(yàn)?zāi)康念I(lǐng)會(huì)并理解二叉樹的類型定義。熟練掌握二叉樹的主要特性。熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。了遞歸算法的實(shí)現(xiàn)過程。二、實(shí)驗(yàn)內(nèi)容及步驟實(shí)現(xiàn)二叉樹的抽象數(shù)據(jù)類型。構(gòu)造一棵二叉樹并用遞歸實(shí)現(xiàn)其先序、中序、后序遍歷算法并驗(yàn)證。用非遞歸算法實(shí)現(xiàn)二叉樹的中序遍歷。給出一段報(bào)文和每個(gè)字符出現(xiàn)的概率，對(duì)其進(jìn)行哈夫曼編碼和解碼。三、實(shí)驗(yàn)步驟與調(diào)試過程利用棧來實(shí)現(xiàn)；根結(jié)點(diǎn)進(jìn)棧，之后棧非空，彈出，接著根節(jié)點(diǎn)的右結(jié)點(diǎn)進(jìn)棧，之后，左節(jié)點(diǎn)進(jìn)棧；接著，彈出棧頂元素,此結(jié)點(diǎn)的右結(jié)點(diǎn)進(jìn)棧，之后左節(jié)點(diǎn)進(jìn)棧，彈出棧頂元素，直到棧為空。從根節(jié)點(diǎn)開始，循環(huán)，只要有左子節(jié)點(diǎn)則進(jìn)棧，直到左子節(jié)點(diǎn)為空。接著彈出棧頂輸出，判斷該結(jié)點(diǎn)是否有右子節(jié)點(diǎn)，若有則進(jìn)棧，若沒有繼續(xù)彈棧。有右子節(jié)點(diǎn)的情況，判斷該節(jié)點(diǎn)是否有左子節(jié)點(diǎn)，有則進(jìn)棧，直到左子節(jié)點(diǎn)為空；若該右子節(jié)點(diǎn)沒有左子節(jié)點(diǎn)，則彈棧；判斷彈出的節(jié)點(diǎn)，是否有右子節(jié)點(diǎn)，若有則進(jìn)棧，沒有繼續(xù)彈棧；接著又要判斷剛進(jìn)棧的這個(gè)節(jié)點(diǎn)，是否有左子節(jié)點(diǎn)，有則進(jìn)棧，沒有則繼續(xù)彈棧。從根結(jié)點(diǎn)開始，只要左子節(jié)點(diǎn)非空，則進(jìn)棧，直到左子節(jié)點(diǎn)為空為止。取出棧頂元素，判斷取出的棧頂元素是否有右子節(jié)點(diǎn)，或者右子節(jié)點(diǎn)是否被訪問過，若滿足條件，則輸出該結(jié)點(diǎn)，同時(shí)彈棧，并且記錄下該訪問的節(jié)點(diǎn)。取出的棧頂元素，若有右子節(jié)點(diǎn)，且未被訪問過，則指針繼續(xù)移動(dòng)到右子節(jié)點(diǎn)。