第一篇：數據結構 隊列實驗報告
隊列實驗報告
小組成員：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插入到隊列中。 （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語言中不能用動態分配的一維數組來實現循環隊列，如果用戶的應用程序中設有循環隊列，則必須為它設定一個最大隊列長度；若用戶無法估計所用隊列的最大長度，則宜采用鏈式隊列。 實驗二 棧和隊列及其應用 一、實驗目的 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”); } 四、測試結果： 五、心得體會 做實驗首先要掌握大量的理論知識，然后認真去完成實驗。做實驗過程會碰見較大的困難，這就要需要我們的毅力。小小的迷宮隱藏大大的奧秘。 注意：實驗結束后提交一份實驗報告電子文檔 電子文檔命名為“學號+姓名”，如：E01214058宋思怡 《數據結構》實驗報告 （一）學號：姓名：專業年級： 實驗名稱：線性表 實驗日期：2014年4月14日 實驗目的： 1、熟悉線性表的定義及其順序和鏈式存儲結構； 2、熟練掌握線性表在順序存儲結構上實現基本操作的方法； 3、熟練掌握在各種鏈表結構中實現線性表基本操作的方法； 4、掌握用 C/C++語言調試程序的基本方法。 實驗內容： 一、編寫程序實現順序表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： （1）初始化順序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）輸出順序表L； （4）輸出順序表L長度； （5）判斷順序表L是否為空； （6）輸出順序表L的第3個元素； （7）輸出元素24的位置； （8）在L的第4個元素前插入元素0； （9）輸出順序表L； （10）刪除L的第5個元素； （11）輸出順序表L。 源代碼 調試分析（給出運行結果界面） 二、編寫程序實現單鏈表的各種基本運算，并在此基礎上設計一個主程序完成如下功能： ???? ???? 小結或討論: （1）實驗中遇到的問題和解決方法 （2）實驗中沒有解決的問題 （3）體會和提高 南京信息工程大學實驗（實習）報告 實驗（實習）名稱數據結構實驗（實習）日期 2011-11-2得分指導教師周素萍 系公共管理系專業信息管理與信息系統年級10級班次1姓名常玲學號2010230700 3實驗一順序表的基本操作及C語言實現 【實驗目的】 1、順序表的基本操作及 C 語言實現 【實驗要求】 1、用 C 語言建立自己的線性表結構的程序庫，實現順序表的基本操作。 2、對線性表表示的集合，集合數據由用戶從鍵盤輸入（數據類型為整型），建立相應的順序表，且使得數據按從小到大的順序存放，將兩個集合的并的結果存儲在一個新的線性表集合中，并輸出。 【實驗內容】 1、根據教材定義的順序表機構，用 C 語言實現順序表結構的創建、插入、刪除、查找等操作； 2、利用上述順序表操作實現如下程序：建立兩個順序表表示的集合（集合中無重 復的元素），并求這樣的兩個集合的并。 【實驗結果】 [實驗數據、結果、遇到的問題及解決] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非遞減的順序表va中插入元素x并使其仍成為順序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的編號從0開始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 將合并逆置后的結果放在C表中，并刪除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驅指針 // 保存pb的前驅指針 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//將當前最小結點插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當前最小結點插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲在數組中，元素之間的關系直接通過相鄰元素的位置來表達。 優點：簡單，數據元素的提取速度快； 缺點：（1）靜態存儲，無法預知問題規模的大小，可能空間不足，或浪費存儲空間；（2）插入元素和刪除元素時間復雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結果存入s引用參數所表示的集合中帶回。首先把s1集合復制到s中，然后把s2中的每個元素依次插入到集合s中，當然重復的元素不應該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應的實際參數集合中得到并集。 數據結構實驗報告 一． 題目要求 1）編程實現二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進行先根、中根、和后根非遞歸遍歷； 3）每次對樹的修改操作和遍歷操作的顯示結果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數組去存儲一個班(50人以上)的成員信息(至少包括學號、姓名、成績3項),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對于前三個題目要求，我們用一個程序實現代碼如下 #include typedefintElemType; //數據類型 typedefint Status; //返回值類型 //定義二叉樹結構 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//創建二叉樹函數 BiTreebst=NULL;inti=0;while(i //數據域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子樹為空重接它的左子樹 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子樹空則重新接它的右子樹 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被刪除結點的前驅 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數，在T中刪除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉樹 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非遞歸遍歷 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非遞歸遍歷 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函數 printf(“ ---------------------二叉排序樹的實現-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節點個數:”);scanf(“%d”,&num);printf(“依次輸入這些整數（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“樹狀圖為:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示輸入操作符************************:”);printf(“n”);printf(“ 1:插入節點 2:刪除節點 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節點:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要刪除的節點”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“刪除成功!”);printf(“樹狀圖為:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非遞歸遍歷二叉樹”);printf(“先序遍歷:n”);PreOrderNoRec(bst);printf(“中序遍歷:n”);InOrderNoRec(bst); printf(“后序遍歷:n”); PostOrderNoRec(bst); printf(“樹狀圖為:n”); printtree(bst,layer); break;case 5: printf(“程序執行完畢!”); return 0;} goto loop;} return 0;對于第四小問，要儲存學生的三個信息，需要把上面程序修改一下，二叉樹結構變為 typedefintElemType; //數據類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結構 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數據域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數不是key,而是另外三個 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含參函數也類似 即可完成50個信息存儲 用數組存儲50個信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學生管理系統”< cout<<“該學號信息已經存在，添加失敗”< break;} cout<<“重新輸入添加的學號”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“謝謝使用”< 二叉排序樹儲存數據界面（儲存學生信息略） 創建二叉樹： 插入節點： 刪除節點： 非遞歸遍歷： 退出： 數組儲存學生信息界面 分析查找效率： 因為二叉樹查找要創建二叉樹，而數組查找只創建一個數組，二叉樹的創建時間比較長，所以對于數據量較少的情況下數組的查找效率比較高。但當數據量增加時，二叉樹的查找優勢就顯現出來。所以數據量越大的時候，二叉樹的查找效率越高。 四． 總結與改進 這個實驗工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進。 一開始打算用棧實現非遞歸，但是根據書里面的偽代碼發現部分是在C++編譯器里運行不了的（即使補充了頭文件和數據的定義），所以之后參考了網上的數組非遞歸，發現其功能和棧相似。 遞歸遍歷的實現比非遞歸的遍歷真的簡單很多。 開始時只看到前三問，所以沒有寫到儲存學生數據的代碼，里面還可以用clock（）函數加一個計算查找所要數據時間的代碼，讓二叉樹查找與數組查找到效率比較更加直觀。第二篇：2數據結構-實驗報告二(棧和隊列及其應用)
第三篇：數據結構實驗報告
第四篇：數據結構實驗報告
第五篇：數據結構實驗報告
點擊咨詢 