第一篇：棧隊列實驗指導書
數理學院實驗指導書
實驗三 棧與隊列的實現(xiàn)，棧的應用
【實驗目的】
1、掌握棧和隊列的特點，即先進后出與先進先出的原則。
2、掌握棧和隊列的順序存儲結構和鏈式存儲結構及其基本操作，以便在實際問題中靈活運用。
3、掌握棧和隊列的基本操作實現(xiàn)方法?！緦嶒瀮热荨?/p>
1、棧的實現(xiàn)：
用C語言實現(xiàn)棧，包括類型定義和各種基本運算的實現(xiàn)，并在此基礎上設計一個主程序，測試棧的一些基本運算：
(1).初始化(2).入棧(3).出棧
(4).取棧頂元素(5).遍歷棧(6).置空棧 請根據下面給出的程序（改進的順序棧），完成這次實驗，并與鏈棧的實現(xiàn)方法相比較：
/*Common.h*/ #define TRUE 1 //邏輯，是 #define FALSE 0 //邏輯，否 #define OK 1 //狀態(tài)，成功
#define FAILURE 0 //狀態(tài)，未成功 #define ERROR-1 //狀態(tài)，失敗 #define OVERFLOW 1 //溢出
typedef int BOOL;typedef int Status;
/*seqstack.h*/ #include
typedef int ElemType;
//棧
typedef struct { ElemType *elem;// 存儲空間基址
int top;// 棧頂指示
int currentsize;// 當前分配的長度 }SeqStack;
/*構造一個空的棧*/ SeqStack *CreateStack();/*釋放棧分配的空間*/ void DestroyStack(SeqStack *S);/*判空*/ int IsEmpty(SeqStack *S);/*入棧*/ Status Push(SeqStack *S, ElemType e);/*出棧*/ Status Pop(SeqStack *S, ElemType *e);/*取棧頂元素*/ Status GetTop(SeqStack *S, ElemType *e);/*遍歷*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int));
/*seqstack.c*/ #include
/*構造一個空的棧*/ SeqStack *CreateStack(){ SeqStack *S=(SeqStack *)malloc(sizeof(SeqStack));
if(S==NULL){ exit(OVERFLOW);} S->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(S->elem==NULL){ exit(OVERFLOW);} S->top =-1;S->currentsize = LIST_INIT_SIZE;return S;}
/*釋放棧分配的空間*/ void DestroyStack(SeqStack *S){ if(S!=NULL){
if(S->elem!=NULL)
{
free(S->elem);
}
S->elem=NULL;} }
/*判空*/ int IsEmpty(SeqStack *S){ return S->top==-1;}
/*入棧*/ Status Push(SeqStack *S, ElemType e){ if(S->top >= S->currentsize)// 當前存儲空間已滿，增加分配
{
ElemType *newbase=(ElemType *)realloc(S->elem,(S->currentsize + LISTINCREMENT)*sizeof(ElemType));
if(newbase==NULL)// 存儲分配失敗
{
exit(OVERFLOW);
}
S->elem = newbase;// 新基址
S->currentsize += LISTINCREMENT;//增加存儲容量
} ++(S->top);S->elem[S->top]=e;return OK;}
/*出棧*/ Status Pop(SeqStack *S, ElemType *e){ if(S->top==-1)//空棧
{
return FAILURE;}(*e)=S->elem[S->top];--(S->top);// 表長減1 return OK;}
/*取棧頂元素*/ Status GetTop(SeqStack *S, ElemType *e){ if(S->top==-1)//空棧
{
return FAILURE;}(*e)=S->elem[S->top];return OK;}
/*遍歷*/ void Traverse(SeqStack *S, void(*visit)(ElemType, int)){ int i;
for(i=0;i<=S->top;i++){
(*visit)(S->elem[i], i+1);} } 2.利用棧實現(xiàn)數制轉換：
在上述棧實現(xiàn)的基礎上，設計一個算法實現(xiàn)輸入一個10進制整數，輸出相應的2進制表示，并利用計算器工具設計若干測試數據后編寫測試代碼進行測試.#include
cout<<“除數不能為零”< sum*=m;return sum;} int Check(char ch){ switch(ch){ case '0': return 0; break;case '1': return 1; break;} return-1;} 3.隊列的實現(xiàn)： 用C語言實現(xiàn)隊列，包括類型定義和各種基本運算的實現(xiàn)，并在此基礎上設計一個主程序，測試隊列的一些基本運算： (1).初始化(2).入隊列(3).出隊列 (4).取對頭元素(5).遍歷隊列 請根據下面給出的程序（改進的鏈隊列），完成這次實驗，并與順序隊列的實現(xiàn)方法相比較，結合上述改進順序棧的方法改進書上的順序隊列使之能根據隊列使用情況自動擴展或縮短，從而解決順序隊列“上溢”的問題： /*Common.h*/ 見棧的實現(xiàn) /*queue.h*/ #include //鏈隊列 /*定義鏈隊列中的結點類型*/ typedef struct node { ElemType data;struct node *next;}LinkNode; typedef struct { LinkNode *front;LinkNode *rear;}LinkQueue; /*構造一個空的鏈隊列*/ LinkQueue *CreateQueue();/*銷毀鏈隊列*/ void DestroyQueue(LinkQueue *Q);/*判空*/ int IsEmpty(LinkQueue *Q);/*入隊列*/ Status AddQueue(LinkQueue *Q, ElemType e);/*出隊列*/ Status OutQueue(LinkQueue *Q, ElemType *e);/*取隊列頭元素*/ Status GetHead(LinkQueue *Q, ElemType *e);/*遍歷*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int)); /*queue.c*/ #include /*構造一個空的隊列*/ LinkQueue *CreateQueue(){ LinkQueue *Q=(LinkQueue *)malloc(sizeof(LinkQueue));if(Q==NULL){ exit(OVERFLOW);} Q->front=(LinkNode *)malloc(sizeof(LinkNode)); if(Q->front==NULL){ exit(OVERFLOW);} Q->front->next=NULL;/*填頭結點的next域為NULL*/ Q->rear=Q->front; /*讓尾指針也指向頭結點*/ return Q;} /*銷毀隊列*/ void DestroyQueue(LinkQueue *Q){ LinkNode *p; if(Q!=NULL){ while(Q->front!=Q->rear) { p=Q->front->next; free(Q->front); Q->front=p; } free(Q->front); Q->front=NULL; Q->rear=NULL;} } /*判空*/ int IsEmpty(LinkQueue *Q){ return Q->front==Q->rear;} /*入隊列*/ Status AddQueue(LinkQueue *Q, ElemType e){ LinkNode *p;p=(LinkNode *)malloc(sizeof(LinkNode)); if(p==NULL){ exit(OVERFLOW);} p->data=e; /*填入元素值*/ p->next=NULL; /*指針域填NULL值*/ Q->rear->next=p; /*新結點插入隊尾*/ Q->rear=p; /*修改隊尾指針*/ return OK;} /*出隊列*/ Status OutQueue(LinkQueue *Q, ElemType *e){ LinkNode *p;if(Q->front==Q->rear)//空隊列 { return FAILURE; } p=Q->front; /*p指向頭結點*/ Q->front=Q->front->next;free(p);(*e)= Q->front->data;return OK;} /*取隊列頂元素*/ Status GetHead(LinkQueue *Q, ElemType *e){ if(Q->front==Q->rear)//空隊列 { return FAILURE; }(*e)= Q->front->next->data;return OK;} /*遍歷*/ void Traverse(LinkQueue *Q, void(*visit)(ElemType, int)){ LinkNode *p;int i;p=Q->front;i=1;while(p!=Q->rear){ (*visit)(p->next->data, i); p=p->next; i++;} } 【實驗安排】 課時安排：2學時 【實驗提示】 1.實驗流程 根據所給的代碼編輯源程序，注意編寫的規(guī)范和體會實現(xiàn)的方法；設計一個主程序實現(xiàn)要求的測試；設計一個算法利用棧實現(xiàn)數制轉換..2.注意事項 記錄輸入和編譯的錯誤提示，書寫心得體會；記錄測試數據和程序的輸出；注意總結.作者:王鶴 QQ:583241212 VC++6.0中調式通過的代碼: #include “stdafx.h” #include 實驗報告三 棧和隊列 班級： 姓名： 學號： 專業(yè)： 一、實驗目的： （1）掌握棧的基本操作的實現(xiàn)方法。 （2）利用棧先進后出的特點，解決一些實際問題。（3）掌握鏈式隊列及循環(huán)隊列的基本操作算法。（4）應用隊列先進先出的特點，解決一些實際問題。 二、實驗內容： 1、使用一個棧，將一個十進制轉換成二進制。粘貼源程序： package Word1; public class Node } T data;Node } this.data=a;this.next=n;this(a,null); -----package Word1; public class Stack } public Node } T a=this.Top.data;this.Top=this.Top.next;return a;this.Top=new Node --package Word1; import java.util.*; public class Test { } static Scanner scan=new Scanner(System.in);static int temp=0;static int a=0;static Stack } temp=scan.nextInt();while(true){ } while(s.Top!=null){ } System.out.printf(“%d”,s.Out());a=temp%2;s.push(a);temp=temp/2;if(temp==0)break; 粘貼測試數據及運行結果： 2、回文是指正讀反讀均相同的字符序列，如“acdca”、“dceecd”均是回文，但“book”不是回文。利用1中的基本算法，試寫一個算法判定給定的字符串是否為回文。（提示：將一半字符入棧，依次彈出與另一半逐個比較）粘貼源程序：---------package Word1; import java.util.*;public class Test1 { } static Scanner sc=new Scanner(System.in);static char[] c={'a','b','c','b','a'};static Stack } public static String One(){ } public static String Two(){ } for(int i=0;i<(c.length/2);i++){ } for(int i=c.length/2;i } return “該字符串是回文”;if(s.Out()!=c[i])return “該字符不是回文”;s.push(c[i]);for(int i=0;i<(c.length/2);i++){ } for(int i=c.length/2+1;i } return “該字符串是回文”;if(s.Out()!=c[i])return “該字符串不是回文”;s.push(c[i]);if(c.length%2!=0){ } else{ } System.out.println(Two());System.out.println(One()); ------------- 粘貼測試數據及運行結果： 3、使用3個隊列分別保留手機上最近10個“未接來電”、“已接來電”、“已撥電話”。 粘貼源程序： package Word3; import java.util.*; public class Queue LinkedList } } System.out.printf(“%d n”,this.deQ()); package Word3; import java.util.*; public class Test { static Queue } static private void T2(){ int c;int[] a={22324,321321,222333};for(int i=0;i 1、查詢 2、增加”);c=sc.nextInt();if(c==1){ } else{ c=sc.nextInt();while(!(list2.isEmpty()))System.out.printf(“%d n”,list2.deQ());list2.enQ(a[i]);int c=0;System.out.println(“請選擇記錄類型：”);System.out.println(“ 1、未接來電 2、已接來電 3、已撥電話”);switch(c=sc.nextInt()){ } case 1:T1();break;case 2:T2();break;case 3:T3();break;Frame(); } } list2.enQ(c);while(!(list2.isEmpty()))System.out.printf(“%d n”,list2.deQ());sc.close();static private void T3(){ } static private void T1(){ int c;int[] a={12324,321321,222333};for(int i=0;i 1、查詢 2、增加”);c=sc.nextInt();if(c==1){ } else{ c=sc.nextInt();while(!(list1.isEmpty()))System.out.printf(“%d n”,list1.deQ());list1.enQ(a[i]);int c;int[] a={32324,321321,222333};for(int i=0;i 1、查詢 2、增加”);c=sc.nextInt();if(c==1){ } else{ } sc.close();c=sc.nextInt();list3.enQ(c);while(!(list3.isEmpty()))System.out.printf(“%d n”,list3.deQ());while(!(list3.isEmpty()))System.out.printf(“%d n”,list3.deQ());list3.enQ(a[i]); } } } list1.enQ(c);while(!(list1.isEmpty()))System.out.printf(“%d n”,list1.deQ());sc.close(); 粘貼測試數據及運行結果： 三、心得體會：（含上機中所遇問題的解決辦法，所使用到的編程技巧、創(chuàng)新點及編程的心得） 實驗總結報告—棧和隊列 學號： 姓名： 時間： 一、目的 1.做實驗的目的 加深對線性結構棧和隊列的理解，學會定義棧和隊列的存儲結構，加強對棧和隊列操作機制的理解，掌握棧和隊列的基本操作，了解棧和隊列的一些應用。2.撰寫實驗報告的目的 對本次實驗情況進行總結，加強對實驗內容的理解，對實驗過程有一個系統(tǒng)的認識，從中獲得本次試驗的經驗，并對實驗結果進行適當的分析，加深對棧和隊列的理解和認識。 二、內容 1.說明實驗次數及實驗內容 本次實驗用一次實驗課時完成 實驗內容： （1）、編寫函數CreatStack_sq(), DestoryStack_sq(), Push_sq(), Pop_sq(),StackEmpty_sq()和 StackTraverse_sq(),分別完成創(chuàng)建空棧,銷毀棧,入棧,出棧,判斷棧是否為空,遍歷棧底到棧頂依 次打印棧內元素等功能(不要修改原棧),完成后進行測試。測試要求:在main 中,建立棧；判斷棧是否為空；將0~9 入棧；將棧頂兩個元素出棧, 兩元素求和后再入棧；從棧底到棧頂依次打印元素,再從棧頂到棧底打印元素；銷毀棧。 void CreatStack_sq(SqStack &S, int msize = STACK_INIT_SIZE){...} void DestoryStack_sq(SqStack &S){...}void Push_sq(SqStack &S, ElementType e){...} bool Pop_sq(SqStack &S, ElementType &e){...} bool StackEmpty_sq(SqStack S){...} bool StackTraverse_sq(SqStack S){...}（2）、編寫函數, CreateQueue_L(), DestoryQueue_L(), EnQueue_L(),DeQueue_L(),分別完 成創(chuàng)建隊列,銷毀隊列,入隊列,出隊列等操作,完成后進行測試。測試要求:在主程序中,建立隊列,將0~9 依次入隊列,按入隊列順序出隊列并打印, 銷毀隊列。 void CreateQueue_L(LinkQueue &Q){ } void DestoryQueue_L(LinkQueue &Q){ } void EnQueue_L(LinkQueue &Q,int e){ } bool DeQueue_L(LinkQueue &Q, int &e){ }（3）、回文是指正讀反讀均相同的字符序列,如”abba”和”abdba”均是回文, 但”good”不是回文。根據第四章棧和隊列所學內容,試寫一個算法判 定給定的字符向量是否為回文。測試數據: 2.1 char* ch = “abccba”;2.2 char* ch = “abccbd”;（4）、(附加題)編寫函數void Knapsack(int w[],int T,int n),完成背包求解問題。測試數據: w[6] = {2,8,6,5,1,4};2.做實驗完成情況 實驗內容在實驗課時時間內完成（提前編寫了大概1/3部分的代碼），選做內容也完成。 本次實驗內容較多，為使代碼看著簡潔有條理，采用了建工程的方式。棧部分： 自定義了頭文件 L_stack.h： /*自定義頭文件*/ #include #define STACK_INIT_SIZE 100;#define STACKINCREMENT 100; /*自定義頭文件（棧相關）*/ #include /*棧的結構體定義*/ typedef struct{ ElemType *elem;int top;int stacksize;}SqStack; void CreateStack_sq(SqStack &S,int msize);//創(chuàng)建棧，msize為棧的大小 void DestroyStack_sq(SqStack &S);//銷毀棧 void Push(SqStack &S, ElemType e);// 進棧操作，e為入棧元素 int Pop_sq(SqStack &S, ElemType &e);//出站操作，成功返回0，不成功返回-1 void Increment(SqStack &S, int inc_size);//增加?？臻g int StackEmpty_sq(SqStack S);//判斷?？?，棧空返回0，棧非空返回-1； void StackTraverse_sq1(SqStack S);//遍歷棧底到棧頂，若棧非空則依次打印棧中元素 void StackTraverse_sq2(SqStack S);//遍歷棧頂到棧底，若棧非空則依次打印棧中元素 void Test_sq();//棧的檢測程序 void MatchBracket_sq(char exp[]);// 括號匹配 void MatchWord_sq(char exp[]);//判斷回文 void knapsack(int w[], int T, int n);//背包問題 在頭文件中對所有要用到的自定義函數進行了聲明，各函數的功能可見代碼注釋部分。 棧的創(chuàng)建： #include“L_stack.h” void CreateStack_sq(SqStack &S,int msize){ S.elem = new ElemType[msize];S.stacksize = msize;S.top =-1;}//end CreateStack_sq 此操作完成棧的創(chuàng)建，創(chuàng)建完成得到一個空棧。 棧的銷毀： #include“L_stack.h” void DestroyStack_sq(SqStack &S){ delete S.elem;S.top =-1;S.stacksize = 0;}//end DestroyStack_sq 此操作將棧銷毀。 入棧： #include“L_stack.h” #include void Push(SqStack &S, ElemType e){ if(S.top == S.stacksize0;break;case '}': if(!Pop_sq(S, e)|| e!= '{')matchstat = 0;break;}//end switch ch = *exp++;}//end while if(matchstat&&StackEmpty_sq(S))printf(“括號匹配n”);else printf(“括號不匹配n”);}//end MatchBracket_sq 該操作完成括號的匹配； 回文判斷： #include“L_stack.h” void MatchWord_sq(char exp[]){ int i, len=0,flag=1;SqStack S;CreateStack_sq(S, 100);char ch,e;for(i = 0;exp[i]!='
第二篇：實驗三 棧和隊列
第三篇：實驗總結報告-棧和隊列