第一篇：數據結構棧與隊列報告
棧和隊列上機實習
1、實驗目的：
（1）熟練掌握棧的邏輯結構和操作規則，能在相應的實際問題中正確選用該結構。（2）熟練掌握棧的2種存儲結構實現方法（順序棧和鏈棧），兩種存儲結構和基本運算的實
現算法，注意棧空盒滿的判斷條件及它們的描述方法。
（3）熟練掌握隊列的邏輯結構和操作規范，能在相應的實際問題中正確選用該結構。（4）掌握循環隊列與鏈隊列兩種存儲結構的實現，熟練掌握各種隊列基本運算的實現。
2、實驗要求：
（1）順序棧的插入、刪除，棧頂數據元素的讀取。（2）鏈棧的插入、刪除，棧頂數據元素的讀取。（3）循環隊列的插入、刪除。（4）鏈隊列的插入、刪除。
3、實驗內容: ① 棧
（1）抽象數據類型定義
typedef struct
{
ElemType data[MaxSize];
//棧的空間大小為MaxSize
int top;
//設置棧頂指針
}SqStack;
//棧的結構定義
在本次實驗中，首先建立一個空棧，進入主程序后首先初始化棧為其分配空間，然后進入菜單選擇界面，通過不同的數字輸入，實現入棧，出棧，讀取棧頂元素，顯示棧的所有元素，棧的長度，釋放棧等操作。
（2）存儲結構定義及算法思想
在棧結構體的定義中，typedef int Typeelem 為整型，存儲結構（入棧）如下：
cin>>a;
s->top++;
//在入棧是首先將棧頂指針向上加1
s->data[s->top]=a;
//與數組賦值一樣，直接賦值
//其他存儲與此類似，都是直接賦值與數組的某一位
退棧函數模塊：
void Pop(SqStack * &s){
//對指針的引用
if(s->top ==-1){
cout<<“棧是空棧，不能退棧”< //首先判斷是否為空棧，若為空，則退出 return;} cout<<“退棧的元素為：”< //顯示退棧元素 s->top--; //棧頂元素減1，指向實際棧的最上面 } 顯示棧所有元素函數模塊： void DispStack(SqStack *s){ //從棧頂到棧底順序顯示所有元素 int i;cout<<“棧的元素分別為：”< //同過循環實現實現從棧頂元素到棧底元素的遍歷以輸出 } cout< 棧結構的入棧和退棧是兩個相反的過程，先進后出，入棧是先讓棧頂指針加1,指向未被賦值位置，然后進行賦值，退棧是先取出退棧元素，然后棧頂元素減1，指向推展后的實際棧頂。諸如讀取棧頂元素，顯示棧的元素，讀取棧的長度，都是用過對棧頂指針實現相關操作。 （3）實驗結果與分析 ② 循環隊列 （1）抽象數據類型定義 typedef struct { ElemType elem[Maxqsize]; //循環隊列的長度為MaxSize int front,rear; //設置隊列的頭指針和尾指針 }SqQueue; //循環隊列的結構體定義 在本次實驗中，首先建立一個空隊列，進入主程序后首先初始化隊列為其分配空間，然后進入菜單選擇界面，通過不同的數字輸入，實現入隊，出隊，顯示隊列的所有元素，隊列的長度，釋放隊列等操作。 （2）存儲結構定義及算法思想 在隊列結構體的定義中，typedef int Typeelem 為整型，存儲（入隊）結構如下： q->rear=(q->rear+1)%Maxqsize; //尾指針加1 q->elem[q->rear]=a; //將入隊元素裝到新的空尾部 在此隊列的存儲結構的實現：先讓隊尾指針進1，再將新的元素加入到隊尾指針所指示的位置，因此，隊尾指針指示實際的隊尾位置，隊頭指針指示實際隊頭的前一位置，要想退出隊頭元素，必須先讓隊頭指針進1，才能取出隊頭元素。 退隊函數模塊如下： void deQueue(SqQueue *&q){ //對指針的引用 if(QueueEmpty(q)) { //調用帶返回值的判斷空隊函數 cout<<“隊列為空”< //判斷隊列是否為空 } q->front=(q->front+1)%Maxqsize; //隊頭指針進1 cout<<“退隊的元素為：”< //取出隊頭元素 } 遍歷隊表函數： void displayqueue(SqQueue *q){ int m;m=q->front+1; //隊頭元素進1，指向實際隊頭 if(QueueEmpty(q)) { cout<<“隊列為空”< //判斷是夠為空隊 } cout<<“所有隊列元素為：”< while(q->rear+1>m){ cout< //通過循環遍歷所有元素 m++; } cout< 循環隊列的入隊和退隊分別是在隊尾與隊頭跟別進行操作的，通過隊頭隊尾指針的操作便可實現對隊列的相關操作。 （3）實驗結果與分析 ③ 心得體會 本次上機是做棧與隊列的操作，這次實驗，我有意的用到了對指針的引用與指針實現子函數功能的調用，剛開始編譯的時候也有錯誤，但是在慢慢的摸索中，也逐漸掌握了它們的用法，這次實驗也讓我熟練了對隊列與棧存儲結構的應用。 附錄： 順序表源代碼: 棧： #include void InitStack(SqStack * &s) //建立一個空棧，即將棧頂指針指向-1即可 的引用 { s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;} void ClearStack(SqStack * &s) //釋放棧s占用的存儲空間 { free(s);} void StackLength(SqStack *s) { cout<<“棧的長度為：” <<(s->top +1)< int StackEmpty(SqStack *s){ return(s->top==-1);} void Push(SqStack *&s){ if(s->top==MaxSize-1) { cout<<“棧滿”< // s=(SqStack *)realloc(s,sizeof(SqStack));} int a; 指針 cout<<“請輸入入棧元素”< void Pop(SqStack * &s){ if(s->top ==-1){ cout<<“棧是空棧，不能退棧”< return;} cout<<“退棧的元素為：”< void GetTop(SqStack * &s,ElemType &e){ if(s->top==-1){cout<<“空棧”< void DispStack(SqStack *s) //從棧頂到棧底順序顯示所有元素 { int i;cout<<“棧的元素分別為：”< cout<<“請選擇功能”< cout<<“ 入棧 1”< cout<<“ 出棧 2”< cout<<“ 讀取棧頂元素 3”< cout<<“ 顯示棧所有元素 4”< cout<<“ 棧的長度 5”< cout<<“ 釋放棧 6”< cin>>k; switch(k) { case 1: Push(s);break; case 2: Pop(s);break; case 3: GetTop(s,e);cout<<“棧頂元素為： ”< case 4: DispStack(s);break; case 5: StackLength(s);break; case 6: ClearStack(s);break; default :break; } } } 隊列： #include TypeElem elem[Maxqsize]; int front,rear;}SqQueue;void InitQueue(SqQueue *&q){ q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=0;} void ClearQueue(SqQueue *&q){ free(q);exit(0);} void QueueLength(SqQueue *q){ cout<<“隊列長度為：”<<(q->rear-q->front+Maxqsize)%Maxqsize< return(q->front==q->rear); } void enQueue(SqQueue *&q){ int a; if((q->rear+1)%Maxqsize==q->front) { cout<<“隊列已滿，無法插入”< } cout<<“請輸入插入元素”< cin>>a; q->rear=(q->rear+1)%Maxqsize; q->elem[q->rear]=a;} void deQueue(SqQueue *&q){ if(QueueEmpty(q)) { cout<<“隊列為空”< } q->front=(q->front+1)%Maxqsize; cout<<“退隊的元素為：”< } void displayqueue(SqQueue *q){ int m;m=q->front+1; if(QueueEmpty(q)) { cout<<“隊列為空”< } cout<<“所有隊列元素為：”< while(q->rear+1>m) { cout< m++; } cout< int k=0; SqQueue *q; InitQueue(q); if(QueueEmpty(q))cout<<“隊列為空”< while(1){ cout<<“請選擇功能”< cout<<“ 入隊 cout<<” 出隊 cout<<“ 隊列長度 cout<<” 顯示隊列元素 cout<<“ 釋放棧 cin>>k; switch(k) { case 1: enQueue(q);break; case 2: deQueue(q);break; case 3: QueueLength(q);break; case 4: displayqueue(q);break; case 5: ClearQueue(q);break; default :break; } } } 1”< 2“< 4“< 實驗二 棧和隊列及其應用 一、實驗目的 1.掌握棧和隊列這兩種抽象數據類型的特點，并能在相應的應用問題中正確選用它們。 2.熟練掌握棧類型的兩種實現方法。 3.熟練掌握循環隊列和鏈隊列的基本操作實現算法。 二、實驗內容 用隊列求解迷宮問題 [問題描述] 以一個M*N的長方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。[基本要求] 實現一個以順序存儲結構的隊列類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，pre）的形式輸出，其中：（i，j）指示迷宮中的一個坐標，pre表示本路徑中上一個方塊在隊列中的下標。 [測試數據] 由學生任意指定。 三、源代碼 # include //行數 //列數 //隊最多元素個數 //一個迷宮,其四周要加上均為1的外框{1,1, #define MaxSize 100 int mg[M+2][N+2]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1}, {1,0,1,0,0,1,1}, {1,0,1,0,1,0,1}, {1,0,0,0,0,0,1}, {1,1,1,1,1,1,1} }; typedef struct {int i,j;int pre;} Box;typedef struct { Box data[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,int xe,int ye)//搜索路徑為：（xi，yi）{ void print(QuType qu, int front);->(xe,ye) int i,j,find=0,di;QuType qu;//定義順序隊 qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi;//(xi,yi)進隊 qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j;if(i==xe&&j==ye){find=1;print(qu,qu.front); } for (di=0;di<4;di++) { switch(di) { case 0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case 1 :i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case 2 :i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case 3 :i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break; } if(mg[i][j]==0) {find=1; qu.rear++; qu.data[qu.rear].i=i;qu.data[qu.rear].j=j; qu.data[qu.rear].pre=qu.front; mg[i][j]=-1; } } } } void print(QuType qu, int front){ int k=front,j,ns=0; printf(“n”);do {j=k; k=qu.data[k].pre; qu.data[j].pre=-1; } while(k!=0);printf(“迷宮路徑如下：n”);k=0;while(k ns++; printf(“t(%d,%d)”,qu.data[k].i,qu.data[k].j); if(ns%5==0)printf(“n”);} k++;} printf(“n”);} void main() { mgpath1(1,1,M,N);printf(“迷宮所有路徑如下:n”); } 四、測試結果： 五、心得體會 做實驗首先要掌握大量的理論知識，然后認真去完成實驗。做實驗過程會碰見較大的困難，這就要需要我們的毅力。小小的迷宮隱藏大大的奧秘。 實驗報告三 棧和隊列 班級： 姓名： 學號： 專業： 一、實驗目的： （1）掌握棧的基本操作的實現方法。 （2）利用棧先進后出的特點，解決一些實際問題。（3）掌握鏈式隊列及循環隊列的基本操作算法。（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(); 粘貼測試數據及運行結果： 三、心得體會：（含上機中所遇問題的解決辦法，所使用到的編程技巧、創新點及編程的心得） 隊列實驗報告 小組成員：xxxxxxxx日期：xxxxxxxx 一、需求分析（xxx） 1.鏈隊列 1）在本演示程序中，首先要鏈隊列添加一個頭結點，并判斷隊列是否為空，它只允許在表的一端進行插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端則為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。最后銷毀隊列，釋放空間。2）演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“歡迎來到鏈隊列”“元素入隊”“元素出隊”“銷毀隊列”“清空隊列”之后。由用戶在鍵盤上輸入演示程序中規定的運算命令，相應的運算數據和顯示結果顯示在其后。3）程序執行的命令包括： 歡迎來到鏈隊列 1輸出隊列長度 2元素入隊 3元素出隊 4銷毀隊列 5清空隊列 6對頭元素 7退出鏈隊列 4）測試數據 入隊 1 2 3 4 5 分別執行“元素入隊”“元素出隊”“銷毀隊列”“清空隊列”等操作。2.順序隊列 1）在本演示程序中，首先要順序隊列添加一個頭結點，并判斷隊列是否為空，它只允許在表的一端進行插入，而在另一端刪除元素，允許插入的一段叫隊尾，允許刪除的一端則為對頭，接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2）演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“歡迎來到鏈隊列”“元素入隊”“元素出隊”“取得頭結點”“輸出顯示”之后。由用戶在鍵盤上輸入演示程序中規定的運算命令，相應的運算數據和顯示結果顯示在其后。3）程序執行的命令包括： 歡迎來到順序隊列 1入隊 2出隊 3判斷是否為空 4取得頭結點 5輸出顯示 6退出順序隊列 4）測試數據 入隊 1 2 3 4 5 分別執行“元素入隊”“元素出隊”等操作。3循環隊列 1）在本演示程序中，首先要順序隊列添加一個頭結點，并判斷隊列是否為空，初始化建空隊列時，令front=rear=0,每當插入新的隊列尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。接著訪問隊列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2）演示程序以用戶和計算機的對話方式執行，即在計算機終端上顯示“歡迎來到鏈隊列”“元素入隊”“元素出隊”“取得頭結點”“輸出顯示”之后。由用戶在鍵盤上輸入演示程序中規定的運算命令，相應的運算數據和顯示結果顯示在其后。3）程序執行的命令包括： 歡迎來到循環隊列 1入隊 2出隊 3判斷是否為空 4取得頭結點 5輸出顯示 6退出順序隊列 4）測試數據 入隊 1 2 3 4 5 分別執行“元素入隊”“元素出隊”等操作。 二．概要設計(xxxx) ⒈ 為實現上述算法，需要順序表的抽象數據類型，抽象數據類型定義如下： ADT Queue { 數據對象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 數據關系: R={ 操作結果：隊列Q已被銷毀。ClearQueue(&Q)初始條件：隊列Q已存在。 操作結果：將Q清為空隊列。QueueEmpty(Q)初始條件：隊列Q已存在。 操作結果：若Q為空隊列，則返回TRUE,否則FALSE。QueueLength(Q)初始條件：隊列Q已存在。 操作結果：返回Q元素的個數，即隊列的長度。GetHead(Q,&e)初始條件:Q為非空隊列。 操作結果：用e返回Q的隊頭元素。EnQueue(&Q,e)初始條件：隊列Q已存在。 操作結果：插入e返回Q的新的隊尾元素。DeQueue(&Q，&e)初始條件：Q為非空隊列。 操作結果：刪除Q的隊頭元素，并用e返回其值。}ADT Queue 2.單鏈隊列 typedefstructQNode { QElemType;structQNode *next;//指針域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//構造一個空隊列。 Status DestroyQueue(LinkQueue&Q)//銷毀隊列Q，Q不存在。 Status ClearQueue(LinkQueue&Q)//將Q清為空隊列。 Status QueueEmpty(LinkQueueQ)//若Q為空隊列，則返回TRUE,否則FALSE。intQueueLength(LinkQueueQ)//返回Q元素的個數，即隊列的長度。 Status GetHead(LinkQueueQ,QElemType&e)//若隊列不為空，則用e返回Q的隊頭元素，并返回OK;否則返回ERROR。 Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的隊尾元素。 Status DeQueue(LinkQueue&Q,QElemType&e)//若隊列不空，則刪除Q的隊頭元素，并用e返回其值，并返回OK;否則返回ERROR。 三．詳細設計（xxx） 1.順序隊列的實現和運算 1）元素的類型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的隊列的構造 void InitSqueue(Squeue *p)/*初始化隊列*/ { p->front=0;p->rear=0;} 3）元素的入隊 int Ensqueue1(Squeue1 *q, Datatype e)/*入隊*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n隊列已滿n”);return 0;} 4）元素的出隊 int DeSqueue1(Squeue1 *q,Datatype *e)/*出隊*/ { if(q->front==q->rear){ printf(“隊列已空,無法出隊!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判斷隊列是否為空 int QueueEmpty1(Squeue1 q)// 判斷是否為空 { if(q.front==q.rear)return 1;else return 0;} 6）隊頭元素的取值的算法 int Gethead1(Squeue1 *q,Datatype *e)// 取對頭元素 { if(q->front==q->rear){ printf(“隊列已空，無法出隊!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍歷順序隊列的算法 void display1(Squeue1 q)//遍歷順序對列 { printf(“此隊列數據為:n”);if(q.front==q.rear)printf(“此隊列為空!”);else { while(q.front void InitQueue2(LinkQueue *q){ // 構造一個空隊列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入隊算法 void EnQueue2(LinkQueue *q, QElemType e)//將元素e進隊 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//創建新節點 if(!p)//如果內存分配成功 exit(1); p->data=e;//初始化新節點數據為e p->next=NULL; q->rear->next=p; q->rear=p;} 3）元素的出隊的算法 int DeQueue2(LinkQueue *q,QElemType e)//隊頭結點出隊,將出隊的元素存入e { QueuePtr p;if(q->front==q->rear)//隊列為空 return 0;p=q->front->next;//初始化temp為要出隊的結點指針 if(q->front->next==q->rear)//要出隊的結點為最后一個結點 q->rear=q->front;e=p->data;//要出隊的數據元素為e q->front->next=p->next;//使下一個結點變為對頭 free(p);//刪除要出隊的結點 return e;} 4）隊列的長度算法 void QueueLength2(LinkQueue *q)//返回隊列長度 { QueuePtr p;int i=0;p=q->front->next;while(p){ ++i; p=p->next;} printf(“鏈隊列長度為:%dn”,i);} 5）隊列的銷毀 void DestroyQueue2(LinkQueue *q){ while(q->front){ q->rear=q->front->next; free(q->front); q->front=q->rear; if(!q->rear) free(q->rear);} free(q->front);} 6）隊列的輸出算法 void output2(LinkQueue *q)//輸出隊列 { QueuePtr p;p=q->front->next;printf(“鏈隊列元素依次為:”);while(p){ printf(“%d->”,p->data); p=p->next;} printf(“n”);} 7）隊列的清空的算法 void Clear2(LinkQueue *q)//清空隊列 { QueuePtr temp=q->front->next;while(temp){ QueuePtrtp=temp; temp=temp->next; free(tp);} temp=q->front; q->front=q->rear=NULL;free(temp);} 8）返回對頭元素的算法 int GetHead2(LinkQueue *q, int *e)//返回對頭結點元素，存入e { if(q->front==q->rear) return 0;*e=q->front->next->data;return 1;} 3.循環隊列的實現和運算 1）隊列的初始化算法 void InitSqueue3(Squeue3 *p)/*初始化隊列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入隊的算法 int Ensqueue3(Squeue3 *q, Datatype e)/*入隊*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n隊列已滿n”);return 0;} else q->base[q->rear]=e;/*將接收到得值付給隊尾所指的節點*/ q->rear=(q->rear+1)% MAXSIZE;/*隊尾向后移一位完成入隊*/ return 1;} 3）出隊的算法 int DeSqueue3(Squeue3 *q,Datatype *e)/*出隊*/ { if(q->front==q->rear){ printf(“隊列已空,無法出隊!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判斷隊列是否為空的算法 int QueueEmpty3(Squeue3 q)// 判斷是否為空 { if(q.front==q.rear)return 1;else return 0;} 5）對頭元素的返還的算法 int Gethead3(Squeue3 *q,Datatype *e)// 取對頭元素 { if(q->front==q->rear){ printf(“隊列已空，無法出隊!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍歷循環隊列的算法 void display3(Squeue3 *q)//遍歷循環對列 { int tail;tail=q->front;printf(“此隊列數據為:n”);if(q->front==q->rear)printf(“此隊列為空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函數的算法 void main(){ int choice;Datatype e1;int i1,a1,x1,s1,j1;//順序隊列定義的量 int e2,i2,n2,s2,a2;//鏈隊列定義的量 int i3,a3,x3,s3,j3;//循環隊列定義的量 Datatype e3; Squeue1 Q1; //******************************* LinkQueue q; //******************************** Squeue3 Q; //**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://順序隊列 { system(“cls”);InitSqueue1(&Q1);printf(“創建隊列完成!n”);printf(“請輸入數據個數j1=”);scanf(“%d”,&j1);for(i1=1;i1<=j1;i1++)//輸入的數據個數不要超過MAXSIZE,多了的部分沒有插入隊列 { printf(“請輸入第%d個數據:”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1); } printf(“對頭為:%dn”,Q1.data[Q1.front]);printf(“隊尾為:%dn”,Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0) { scanf(“%d”,&s1);switch(s1) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“請輸入入隊元素:n ”);scanf(“%d”,&x1);Ensqueue1(&Q1,x1);display1(Q1); s1=-1; start1();break; } case 2: { system(“cls”);DeSqueue1(&Q1,&e1);display1(Q1);s1=-1; start1();break; } case 3: { system(“cls”);if(QueueEmpty1(Q1))printf(“此隊列為空!n”);else printf(“此隊列不為空!n”); } s1=-1; start1();break;case 4: { system(“cls”); Gethead1(&Q1,&e1);printf(“對頭元素為:%dn”,e1); s1=-1; start1();break; } case 5: { system(“cls”);display1(Q1);s1=-1; start1();break; } }//switch } //while }//case1 break;//************************************************* case 2: { system(“cls”); InitQueue2(&q);printf(“創建隊列完成!n”);printf(“輸入將建立鏈隊列元素的個數:n2=”);scanf(“%d”,&n2);printf(“請輸入隊列的元素：n”);for(i2=1;i2<=n2;i2++) { printf(“請輸入第%d個元素:”,i2); scanf(“%d”,&e2); EnQueue2(&q,e2); } a2=-1;start2();while(a2!=0) { scanf(“%d”,&a2); switch(a2) { case 1:system(“cls”); QueueLength2(&q); a2=-1;start2(); break; case 2:{ system(“cls”); printf(“請輸入入隊元素:”); scanf(“%d”,&e2);EnQueue2(&q,e2); output2(&q);a2=-1;start2(); }break; case 3: system(“cls”); e2=DeQueue2(&q,e2); output2(&q); printf(“出隊元素為:%dn”,e2);a2=-1;start2(); break; case 4:DestroyQueue2(&q);printf(“隊列已銷毀!n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 5: Clear2(&q);printf(“隊列已清空n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 6: system(“cls”);GetHead2(&q,&e2); printf(“隊頭元素為:%dn”,e2);s2=-1; start2(); break; case 0: system(“cls”); choice=-1; Begin(); break; }//switch }//while }//case2 break;//************************************************** case 3: { system(“cls”); InitSqueue3(&Q);printf(“創建隊列完成!n”);printf(“請輸入數據個數j3=”);scanf(“%d”,&j3);for(i3=1;i3<=j3;i3++)//輸入的數據個數不要超過MAXSIZE,多了的部分沒有插入隊列 { printf(“請輸入第%d個數據:”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3); } printf(“對頭為:%dn”,Q.base[Q.front]);printf(“隊尾為:%dn”,Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0) { scanf(“%d”,&s3);switch(s3) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“請輸入入隊元素:n ”);scanf(“%d”,&x3);Ensqueue3(&Q,x3);display3(&Q); s3=-1; start3();break; } case 2: { system(“cls”);DeSqueue3(&Q,&e3);display3(&Q);s3=-1; start3();break; } case 3: { system(“cls”);if(QueueEmpty3(Q))printf(“此隊列為空!n”);else printf(“此隊列不為空!n”); } s3=-1; start3();break;case 4: { system(“cls”); Gethead3(&Q,&e3);printf(“對頭元素為:%dn”,e3); s3=-1; start3();break; } case 5: { system(“cls”);display3(&Q);s3=-1; start3();break; } }//switch } //while }//case 3 break; case 0: printf(“ 謝謝使用！！n”); break; //*************************** }//switch }//while }//main 四．調試分析（xxx） 順序隊列 1.編譯并調試，運行程序。 2.設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。3.判斷隊列是否為空。隊列是否為空的標志就是隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等。 4.隊列滿時候不能入隊列，否則會出現溢出現象。即先要判斷隊列是否已經已滿，因為隊尾指針的最大值是MAXQSIZE，所以通過檢查隊尾指針rear是否等于MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。 5.在元素出隊操作，先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空，空時不能操作，這是要注意的。 6.程序滿足了本次試驗的目的和任務要求，可以進行人機交互，在后來的程序中將會做些改進，以增強人機交互性。 7.本程序存在較多不足，如有問題，參考用戶手冊。 8.在程序語句中，原本使用了大量的生僻的函數名，經過改進，目前使用都是通俗易懂的函數名稱，方便用戶理解。 鏈隊列 1.編譯并調試，運行程序。2.設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。 3.要注意設定一個在鏈隊列添加一個頭結點并令指針指向頭結點。同時，刪除不可以在最后面進行刪除，但是插入可以最后一個進行插入，這點需要注意 4.需要分別指向隊頭和隊尾的指針。 5.程序滿足了本次試驗的目的和任務要求，可以進行人機交互，在后來的程序中將會做些改進，以增強人機交互性。 6.本程序存在較多不足，如有問題，參考用戶手冊。 7.在程序語句中，原本使用了大量的生僻的函數名，經過改進，目前使用都是通俗易懂的函數名稱，方便用戶理解。 循環隊列 1.編譯并調試，運行程序。 2.設計測試用例，分析測試結果，以驗證所完成的系統是否達到預期效果。 3.為了避免順序隊列造成的“假溢出”現象，我們通常采用順序循環隊列實現隊列的順序存儲。4.隊頭指針和對尾指針與隊列元素之間關系和順序隊列一樣，不變。5.先判斷隊列是否為空。就是看隊頭指針和隊尾指針是否同時指向隊列中的同一個位置，即隊頭指針和隊尾指針是否相等，空時不能操作，這是要注意的。 6.在將元素插入到隊列之前首先要判斷隊列是否已經已滿，根據順序循環隊列隊滿條件front==(rear+1)%MAXQSIZE來判斷隊列是否已滿。在刪除隊首元素時，應首先通過隊頭指針和隊尾指針是否相等判斷隊列是否已空。 6.程序滿足了本次試驗的目的和任務要求，可以進行人機交互，在后來的程序中將會做些改進，以增強人機交互性。 7.本程序存在較多不足，如有問題，參考用戶手冊。 8.在程序語句中，原本使用了大量的生僻的函數名，經過改進，目前使用都是通俗易懂的函數名稱，方便用戶理解。 五、用戶手冊(xx)1.鏈隊列 (1)本程序的運行環境為DOS操作系統，執行文件名為：j.exe.(2)進入演示程序后即顯示文本方式的用戶界面，輸入元素1,2,3,4,5創建隊列。 （3）根據提示，選擇操作2執行元素入隊操作。回車，輸入入隊元素0，回車，將0插入到隊列中。 （4）選擇操作3執行元素出隊操作，回車，隊首元素1出隊。 （5）選擇操作1執行輸出隊列長度操作，回車，輸出隊列長度為5.（6）選擇操作5執行清空隊列操作，回車，清空。 （7）選擇操作6執行輸出隊頭元素操作，回車，輸出元素2。 2.順序隊列 （1）創建隊列，輸入數據 1,2,3,4,5.（2）選擇操作1，執行入隊操作.輸入入隊元素0 （3）選擇操作2，執行出隊操作。 隊首元素1出隊.（4）選擇操作3，判斷對是否為空 （5）選擇操作4，輸出對頭元素2.（6）選擇操作5，顯示隊列元素 3、循環隊列 （1）創建隊列，輸入數據 1,2,3,4,5.（2）選擇操作1，執行入隊操作.輸入入隊元素0 （3）選擇操作2，執行出隊操作。隊首元素1出隊.（3）選擇操作3，判斷對是否為空 （5）選擇操作4，輸出對頭元素2.（6）選擇操作5，顯示隊列元素為,2,3,4,5,0 六．測試結果（xxx）1.順序隊列的實現和運算 1）輸入1即可進行進入到順序隊列 2）順序隊列的建立，輸入元素的個數為5，輸入的數據分別為1，2，3，4，5，對頭為1，隊尾為5，此時隊列的數據為1 2 3 3）輸入2即可進行入隊運算，輸入的入隊元素為0，此時的隊列的數據為1 2 3 4 5 0 4）輸入3即可進行判斷隊列的是否為空，如下圖： 5）輸入4即可進行去的對頭元素的算法，如下圖所示： 6）此時的隊列的數 據 為 0，如 下 圖 ： 7）輸入0即可退出順序隊列，如下圖： 8）輸入3即可進行順序隊列的算法，如下圖所示： 9）輸入1即可進 行 相 應的入 隊 運 算，如 下 10）輸入2即可進行隊列的出隊運算，如下圖所示： 所 示 圖 ：11）輸入3 即可判斷順序隊列是否為空的算法，如下圖所示： 12）輸入4即可進行去的頭結點的運算，如下圖所示： 13）輸入5即可進行隊列的輸出顯示的運算，如 14）輸入0即可進行退出順序隊列的算法，如下圖所示： 下圖所示：2.鏈式隊列的實現和運算 1）隊列的建立以及隊列的個數輸入為5，輸入的數據分別為1，2，3，4，5.如下圖： 2）輸入2即可進入到元素的入隊運算，輸入入隊的元素的為0，輸入3即可進行相應的元素的出隊運算，出隊元素為1.如下圖： 3）則此時的隊列的長度為5，輸入4即可進行隊列的銷毀以及輸入5即可進行隊列的清空運算，如下圖： 4）輸入6即可進行輸出隊列的對頭元素，輸入0即可進行退出鏈隊列的運算 3．循環隊列的實現和運算 1）輸入3即可進行循環隊列的操作，輸入5個數據，它們分別為1 2 3 4 5，輸入1，即可進行入隊操作，輸入入隊的元素為0，則此時的數據為1 2 3 4 5 0，如下圖所示： 2）輸入2即可進行出隊運算，如下圖所示： 3）輸入3即可進行判斷隊列的是否為空，如下圖所示： 4）輸入4即可進行取得對頭元素，如 下 5)輸入5即可進行輸出所有的數據顯示，如下圖所示： 所示圖： 七．心得體會（xx） 隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。 在隊列這種數據結構中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出” 的線性表。注意的是為了避免順序隊列造成的“假溢出”現象，我們通常采用順序循環隊列實現隊列的順序存儲。還有要注意的是在C語言中不能用動態分配的一維數組來實現循環隊列，如果用戶的應用程序中設有循環隊列，則必須為它設定一個最大隊列長度；若用戶無法估計所用隊列的最大長度，則宜采用鏈式隊列。 PHP 程序員學數據結構與算法之《棧》 介紹 “要成高手，必練此功”。 要成為優秀的程序員，數據結構和算法是必修的內容。而現在的Web程序員使用傳統算法和數據結構都比較少，因為很多算法都是包裝好的，不用我們去操心具體的實現細節，如PHP的取棧操作array_pop,進棧操作array_push，都有指定的庫函數，導致我們對基礎算法的研究越來越少，最后成為一個工具的傀儡而已。 所以我還是建議更多的coder從基礎開始學習。這篇就先講我們最熟悉的棧操作開始入手,讓我們熟悉棧。 棧為何物？ 口訣“后進先出”，這是我印象最深的一句話，也是老師一坨講解中，印象最深刻的。 定義：棧是限制插入和刪除都只能發生在一個位置上進行的線性表，該位置是線性表的末端，叫做棧的頂。 過程：先進入的數據被壓入棧底，最后的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最后一個數據被第一個讀出來）。 分析 通過定義和過程，我們分析出數據結構（紅色標識），動作部分（藍色標識），以及動作的規則（黃色標識）。 請看 lv包包、古奇女包、coach包:www.tmdps.cn|兔毛皮草、獺兔皮草、皮草服飾：www.tmdps.cn 組成成分 數據：線性表（用array結構保存命名為data），末端索引（用int結構保存命名為end，初始值為null——因為開始線性表是沒有元素的，所以就沒有末端索引這么一說，而且由于不斷取數據，添加數據，這個末端是變化的元素。）。 動作（方法）：壓入（push：規則，放在線性表最后面），彈出（pop：規則，從最后取出，并且末端位置向前移動）。 編碼 lv包包、古奇女包、coach包:www.tmdps.cn|兔毛皮草、獺兔皮草、皮草服飾：www.tmdps.cn 運行結果 lv包包、古奇女包、coach包:www.tmdps.cn|兔毛皮草、獺兔皮草、皮草服飾：www.tmdps.cn 總結 以上是本人對棧的分析理解過程，由于我是一名php coder，所以我用php的角度去分析和編碼。 如果是C語言去編碼，數組應該指定最大寬度，因為C語言數組不像php數組能自行增長，必須要有一個初始寬度。 lv包包、古奇女包、coach包:www.tmdps.cn|兔毛皮草、獺兔皮草、皮草服飾：www.tmdps.cn第二篇：2數據結構-實驗報告二(棧和隊列及其應用)
第三篇：實驗三 棧和隊列
第四篇：數據結構 隊列實驗報告
第五篇：PHP 程序員學數據結構與算法之《棧》
點擊咨詢 