棧的應用舉例編程序判斷一個字符序列是否是回文。

編程思想：

設字符數組str中存放了要判斷的字符串。把字符數組中的字符逐個分別存入隊列和堆棧，然后逐個出隊列和退棧并比較出隊列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。算法思想：1、初始化一個棧和隊列2、將字符數組輸入棧和隊列3、從棧和隊列分別刪除一個元素，并比較2個元素：若相同，則重復步驟3，直到棧和隊列空為止；若不相同，則退出。

voidHuiWen(charstr[]){ length=strlen(str);

QueueInitiate(&myQueue);StackInitiate(&myStack);

for(i=0;i<length;i++)

{EnQueue(&myQueue,str[i]); StackPush(&myStack,str[i]); }

while(！QueueEmpty(myQueue)&&！StackEmpty(myStack)){DeQueue(&myQueue,&x)；

StackPop(&myStack,&y)

If（x!=y){ printf(“%s不是回文!\n",str); return;

}

}if(！QueueEmpty(myQueue)||！StackEmpty(myStack)) printf("%s不是回文!\n",str); else printf("%s是回文!\n",str);}voidmain(void){ charstr1[]="ABCDEDCBA"; charstr2[]="ABCDEDCAB"; HuiWen(str1); HuiWen(str2);}typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點信息

AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點數，弧數

GraphKindkind;//圖的種類標志

}MGraph;StatusCreateGraph(Mgraph*G){//建立圖的鄰接矩陣的結構

scanf(G->kind);switch(G->kind){caseDG:returnCreateDG(G);caseDN:returnCreateDN(G);caseUDG:returnCreateUDG(G);caseUDN:returnCreateUDN(G);default:returnERROR;}StatusCreateUDN(Mgraph*G){//建立無向網

scanf(G->vexnum,G->arcnum,&info);//info為0,表示各弧無信息

for(i=0;i<G->vexnum;++i)scanf(G->vexs[i]);//構造頂點向量

for(i=0;i<G->vexnum;++i)//初始化鄰接矩陣

for(j=0;j<G->vexnum;++j)G->arcs[i][j]={INFNITY,NULL};

for(k=0;k<G->arcnum;k++){scanf(&v1,&v2,&w);//輸入一條邊依附的及權值

i=LocateVex(G,v1);j=LocateVex(G,v2);//確定v1、v2在圖中的位置

G->arcs[i][j].adj=w;//弧的<v1,v2>的權值

if(info)InPut(*G->arcs[i][j].info);//若弧有相關信息G->arcs[j][i]=G->arcs[i][j];}//置<v1,v1>的對稱弧<v2,v1>}//END在鄰接矩陣存儲結構上實現FIRST-ADJ(G,V)算法:1、用LocatVex（G，V）找到V在圖中的位置i；2、找出二維數組中第i行第一個非零值對應的列號j；3、j就是V的第一個鄰接點在圖中的位置；4、G.Vex（j）就是V的第一個鄰接點.在鄰接矩陣存儲結構上實現FIRST-ADJ(G,V)算法:1、用LocatVex（G，V）找到V在圖中的位置i；2、找出二維數組中第i行第一個非零值對應的列號j；3、j就是V的第一個鄰接點在圖中的位置；4、G.Vex（j）就是V的第一個鄰接點.二、圖的鄰接表存儲表示它是一種順序存儲與鏈式存儲相結合的存儲方法，順序存儲部分用來保存圖中頂點的信息，鏈式存儲部分用來保存圖中邊（或弧的信息）adjvexnextarcinfo弧的結點結構datafirstarc頂點的結點結構typedefstructArcNode{

intadjvex;//該弧所指向的頂點的位置

structArcNode*nextarc;//指向下一條弧的指針

InfoType*info;//該弧相關信息的指針}ArcNode;adjvexnextarcinfo弧的結點結構typedefstructVNode{

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧

}VNode,AdjList[MAX_VERTEX_NUM];datafirstarc頂點的結點結構typedefstruct{

AdjListvertices;

intvexnum,arcnum;

intkind;//圖的種類標志

}ALGraph;圖的結構定義

無向圖的鄰接表創建算法voidcreateadjgraph(ALGraph*g){scanf("%d%d",&g->Vexnum,&g->Arcnum);/*輸入頂點數與邊數*/for(i=0;i<g->Vexnum;i++){scanf(“%c”,&g->Vertices[i].data);/*讀入頂點信息*/g->vertices[i].firstarc=NULL;}/*初始化一維數組

/*建立各單鏈表*/for(k=0;k<g->Arcnum;k++)/*循環e次建立邊表*/{scanf("%d%d",&i,&j);/*輸入無序對（i,j）*/ s=(Arcnode*)malloc(sizeof(Arcnode));s->adjvex=j;/*鄰接點序號為j*/ s->next=g->Vertices[i].firstarc;g->Vertices[i].firstarc=s;/*將新結點*s插入頂點vi的邊表頭部*s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;/*鄰接點序號為i*/ s->next=g->Vertices[j].firstarc; g->Vertices[j].firstarc=s;/*將新結點*s插入頂點vj的邊表頭部*/}對于下面的AOE網：1、求出各個事件的最早發生時間和最晚發生時間，并回答完成整個工程最少需要多少時間？2、計算各個活動的最早開始時間和最遲開始時間，并找出所有的關鍵活動和關鍵路徑。v0v1v3v2v4v5v6v7v8v9358564427365893#defineMAX_TREE_SIZE100//二叉樹的最大結點數typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點SqBiTreebt;一、二叉樹的順序存儲表示例如:

ABDCEF

0123456789101112130ABCDEF1413261、統計二叉樹中葉子結點的個數算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結點，并計數。由此，需在遍歷算法中增添一個“計數”的參數，并將算法中“訪問結點”的操作改為：若是葉子，則計數器增1。void

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對葉子結點計數

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf

在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，統計樹中具有度為1的結點數目的算法。intLevel(BiTree*bt){intnum=0;//num統計度為1的結點的個數

if(bt){QueueInit(Q);QueueIn(Q,bt)；//Q是以二叉樹結點指針為元素的隊列

while(!QueueEmpty(Q)){p=QueueOut(Q);printf(p->data);//出隊,訪問結點if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度為1的結點if(p->lchild)QueueIn(Q,p->lchild);//非空左子女入隊if(p->rchild)QueueIn(Q,p->rchild);//非空右子女入隊}}//if(bt)return(num);}//返回度為1的結點的個數

在一棵以二叉鏈表表示的二叉樹上，試寫出用按層次順序遍歷二叉樹的方法，統計樹中具有度為1的結點數目的算法。intLevel(BiTree*bt){intnum=0;//num統計度為1的結點的個數

if(bt){QueueInit(Q);QueueIn(Q,bt)；

while(!QueueEmpty(Q)){p=QueueOut(Q);printf(p->data);//出隊,訪問結點if(p->lchild&&!p->rchild||!p->lchild&&p->rchild)num++;//度為1的結點if(p->lchild)QueueIn(Q,p->lchild);//非空左子女入隊if(p->rchild)QueueIn(Q,p->rchild);//非空右子女入隊}}//if(bt)return(num);//返回度為1的結點的個數

}typedefstructArcCell{//弧的定義

VRTypeadj;//VRType是頂點關系類型。

//對無權圖，用1或0表示相鄰否；

//對帶權圖，則為權值類型。

InfoType*info;//該弧相關信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{//圖的定義

VertexTypevexs[MAX_VERTEX_NUM];//頂點信息

AdjMatrixarcs;//弧的信息

intvexnum,arcnum;//頂點數，弧數

GraphKindkind;//圖的種類標志

}MGraph;StatusCreateGraph(Mgraph*G){//建立圖的鄰接矩陣結構

scanf(G->kind);switch(G->kind){caseDG:returnCreateDG(G);caseDN:returnCreateDN(G);caseUDG:returnCreateUDG(G);caseUDN:returnCreateUDN(G);default:returnERROR;}StatusCreateUDN(Mgraph*G){//建立無向網

scanf(G->vexnum,G->arcnum,&info);//info為0,表示各弧無信息

for(i=0;i<G->vexnum;++i)scanf(G->vexs[i]);//構造頂點向量

for(i=0;i<G->vexnum;++i)//初始化鄰接矩陣

for(j=0;j<G->vexnum;++j)G->arcs[i][j]={INFNITY,NULL};for(k=0;k<G->arcnum;k++){scanf(&v1,&v2,&w);//輸入一條邊依附的及權值

i=LocateVex(G,v1);//確定v1,v2在圖中的位置j=LocateVex(G,v2);//確定v1,v2在圖中的位置

G->arcs[i][j].adj=w;//弧的<v1,v2>的權值

if(info)InPut(*G->arcs[i][j].info);//若弧有相關信息G->arcs[j][i]=G->arcs[i][j];}//置<v1,v1>的對稱弧<v2,v1>}//END在鄰接矩陣存儲結構上實現FIRST-ADJ(G,V)算法:(1)用LocatVex（G，V）找到V在圖中的位置i；(2)找出二維數組中第i行第一個非零值對應的列號j；(3)j就是V的第一個鄰接點在圖中的位置；(4)G.Vex（j）就是V的第一個鄰接點。2.圖的鄰接表存儲表示它是一種順序存儲與鏈式存儲相結合的存儲方法，順序存儲部分用來保存圖中頂點的信息，鏈式存儲部分用來保存圖中邊（或弧的信息）adjvexnextarcinfo弧的結點結構datafirstarc頂點的結點結構typedefstructArcNode{

intadjvex;//該弧所指向的頂點的位置

structArcNode*nextarc;//指向下一條弧的指針

InfoType*info;//該弧相關信息的指針}ArcNode;adjvexnextarcinfo弧的結點結構typedefstructVNode{

VertexTypedata;//頂點信息

ArcNode*firstarc;//指向第一條依附該頂點的弧

}VNode,AdjL