第一篇：數(shù)據(jù)結(jié)構(gòu) 隊(duì)列實(shí)驗(yàn)報告
隊(duì)列實(shí)驗(yàn)報告
小組成員：xxxxxxxx日期：xxxxxxxx
一、需求分析（xxx）
1.鏈隊(duì)列
1）在本演示程序中，首先要鏈隊(duì)列添加一個頭結(jié)點(diǎn)，并判斷隊(duì)列是否為空，它只允許在表的一端進(jìn)行插入，而在另一端刪除元素，允許插入的一段叫隊(duì)尾，允許刪除的一端則為對頭，接著訪問隊(duì)列中所有元素，并輸出，輸出是每個元素之間用空格來完成。最后銷毀隊(duì)列，釋放空間。2）演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“歡迎來到鏈隊(duì)列”“元素入隊(duì)”“元素出隊(duì)”“銷毀隊(duì)列”“清空隊(duì)列”之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的運(yùn)算數(shù)據(jù)和顯示結(jié)果顯示在其后。3）程序執(zhí)行的命令包括： 歡迎來到鏈隊(duì)列 1輸出隊(duì)列長度 2元素入隊(duì) 3元素出隊(duì) 4銷毀隊(duì)列 5清空隊(duì)列 6對頭元素 7退出鏈隊(duì)列 4）測試數(shù)據(jù) 入隊(duì) 1 2 3 4 5 分別執(zhí)行“元素入隊(duì)”“元素出隊(duì)”“銷毀隊(duì)列”“清空隊(duì)列”等操作。2.順序隊(duì)列
1）在本演示程序中，首先要順序隊(duì)列添加一個頭結(jié)點(diǎn)，并判斷隊(duì)列是否為空，它只允許在表的一端進(jìn)行插入，而在另一端刪除元素，允許插入的一段叫隊(duì)尾，允許刪除的一端則為對頭，接著訪問隊(duì)列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2）演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“歡迎來到鏈隊(duì)列”“元素入隊(duì)”“元素出隊(duì)”“取得頭結(jié)點(diǎn)”“輸出顯示”之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的運(yùn)算數(shù)據(jù)和顯示結(jié)果顯示在其后。3）程序執(zhí)行的命令包括： 歡迎來到順序隊(duì)列 1入隊(duì) 2出隊(duì)
3判斷是否為空 4取得頭結(jié)點(diǎn) 5輸出顯示 6退出順序隊(duì)列 4）測試數(shù)據(jù) 入隊(duì) 1 2 3 4 5 分別執(zhí)行“元素入隊(duì)”“元素出隊(duì)”等操作。3循環(huán)隊(duì)列
1）在本演示程序中，首先要順序隊(duì)列添加一個頭結(jié)點(diǎn)，并判斷隊(duì)列是否為空，初始化建空隊(duì)列時，令front=rear=0,每當(dāng)插入新的隊(duì)列尾元素時，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時，“頭指針增1”。接著訪問隊(duì)列中所有元素，并輸出，輸出是每個元素之間用空格來完成。2）演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“歡迎來到鏈隊(duì)列”“元素入隊(duì)”“元素出隊(duì)”“取得頭結(jié)點(diǎn)”“輸出顯示”之后。由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的運(yùn)算數(shù)據(jù)和顯示結(jié)果顯示在其后。3）程序執(zhí)行的命令包括： 歡迎來到循環(huán)隊(duì)列 1入隊(duì) 2出隊(duì)
3判斷是否為空 4取得頭結(jié)點(diǎn) 5輸出顯示 6退出順序隊(duì)列 4）測試數(shù)據(jù) 入隊(duì) 1 2 3 4 5 分別執(zhí)行“元素入隊(duì)”“元素出隊(duì)”等操作。
二．概要設(shè)計(jì)(xxxx)
⒈ 為實(shí)現(xiàn)上述算法，需要順序表的抽象數(shù)據(jù)類型，抽象數(shù)據(jù)類型定義如下：
ADT Queue { 數(shù)據(jù)對象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 數(shù)據(jù)關(guān)系: R={
操作結(jié)果：隊(duì)列Q已被銷毀。ClearQueue(&Q)初始條件：隊(duì)列Q已存在。
操作結(jié)果：將Q清為空隊(duì)列。QueueEmpty(Q)初始條件：隊(duì)列Q已存在。
操作結(jié)果：若Q為空隊(duì)列，則返回TRUE,否則FALSE。QueueLength(Q)初始條件：隊(duì)列Q已存在。
操作結(jié)果：返回Q元素的個數(shù)，即隊(duì)列的長度。GetHead(Q,&e)初始條件:Q為非空隊(duì)列。
操作結(jié)果：用e返回Q的隊(duì)頭元素。EnQueue(&Q,e)初始條件：隊(duì)列Q已存在。
操作結(jié)果：插入e返回Q的新的隊(duì)尾元素。DeQueue(&Q，&e)初始條件：Q為非空隊(duì)列。
操作結(jié)果：刪除Q的隊(duì)頭元素，并用e返回其值。}ADT Queue
2.單鏈隊(duì)列
typedefstructQNode { QElemType;structQNode *next;//指針域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//構(gòu)造一個空隊(duì)列。
Status DestroyQueue(LinkQueue&Q)//銷毀隊(duì)列Q，Q不存在。
Status ClearQueue(LinkQueue&Q)//將Q清為空隊(duì)列。
Status QueueEmpty(LinkQueueQ)//若Q為空隊(duì)列，則返回TRUE,否則FALSE。intQueueLength(LinkQueueQ)//返回Q元素的個數(shù)，即隊(duì)列的長度。
Status GetHead(LinkQueueQ,QElemType&e)//若隊(duì)列不為空，則用e返回Q的隊(duì)頭元素，并返回OK;否則返回ERROR。
Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的隊(duì)尾元素。
Status DeQueue(LinkQueue&Q,QElemType&e)//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，并用e返回其值，并返回OK;否則返回ERROR。
三．詳細(xì)設(shè)計(jì)（xxx）
1.順序隊(duì)列的實(shí)現(xiàn)和運(yùn)算
1）元素的類型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的隊(duì)列的構(gòu)造
void InitSqueue(Squeue *p)/*初始化隊(duì)列*/ { p->front=0;p->rear=0;} 3）元素的入隊(duì)
int Ensqueue1(Squeue1 *q, Datatype e)/*入隊(duì)*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n隊(duì)列已滿n”);return 0;} 4）元素的出隊(duì)
int DeSqueue1(Squeue1 *q,Datatype *e)/*出隊(duì)*/ { if(q->front==q->rear){ printf(“隊(duì)列已空,無法出隊(duì)!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判斷隊(duì)列是否為空
int QueueEmpty1(Squeue1 q)// 判斷是否為空 { if(q.front==q.rear)return 1;else return 0;} 6）隊(duì)頭元素的取值的算法
int Gethead1(Squeue1 *q,Datatype *e)// 取對頭元素 { if(q->front==q->rear){ printf(“隊(duì)列已空，無法出隊(duì)!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍歷順序隊(duì)列的算法
void display1(Squeue1 q)//遍歷順序?qū)α? { printf(“此隊(duì)列數(shù)據(jù)為:n”);if(q.front==q.rear)printf(“此隊(duì)列為空!”);else { while(q.front void InitQueue2(LinkQueue *q){ // 構(gòu)造一個空隊(duì)列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入隊(duì)算法 void EnQueue2(LinkQueue *q, QElemType e)//將元素e進(jìn)隊(duì) { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//創(chuàng)建新節(jié)點(diǎn) if(!p)//如果內(nèi)存分配成功 exit(1); p->data=e;//初始化新節(jié)點(diǎn)數(shù)據(jù)為e p->next=NULL; q->rear->next=p; q->rear=p;} 3）元素的出隊(duì)的算法 int DeQueue2(LinkQueue *q,QElemType e)//隊(duì)頭結(jié)點(diǎn)出隊(duì),將出隊(duì)的元素存入e { QueuePtr p;if(q->front==q->rear)//隊(duì)列為空 return 0;p=q->front->next;//初始化temp為要出隊(duì)的結(jié)點(diǎn)指針 if(q->front->next==q->rear)//要出隊(duì)的結(jié)點(diǎn)為最后一個結(jié)點(diǎn) q->rear=q->front;e=p->data;//要出隊(duì)的數(shù)據(jù)元素為e q->front->next=p->next;//使下一個結(jié)點(diǎn)變?yōu)閷︻^ free(p);//刪除要出隊(duì)的結(jié)點(diǎn) return e;} 4）隊(duì)列的長度算法 void QueueLength2(LinkQueue *q)//返回隊(duì)列長度 { QueuePtr p;int i=0;p=q->front->next;while(p){ ++i; p=p->next;} printf(“鏈隊(duì)列長度為:%dn”,i);} 5）隊(duì)列的銷毀 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）隊(duì)列的輸出算法 void output2(LinkQueue *q)//輸出隊(duì)列 { QueuePtr p;p=q->front->next;printf(“鏈隊(duì)列元素依次為:”);while(p){ printf(“%d->”,p->data); p=p->next;} printf(“n”);} 7）隊(duì)列的清空的算法 void Clear2(LinkQueue *q)//清空隊(duì)列 { 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)//返回對頭結(jié)點(diǎn)元素，存入e { if(q->front==q->rear) return 0;*e=q->front->next->data;return 1;} 3.循環(huán)隊(duì)列的實(shí)現(xiàn)和運(yùn)算 1）隊(duì)列的初始化算法 void InitSqueue3(Squeue3 *p)/*初始化隊(duì)列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入隊(duì)的算法 int Ensqueue3(Squeue3 *q, Datatype e)/*入隊(duì)*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n隊(duì)列已滿n”);return 0;} else q->base[q->rear]=e;/*將接收到得值付給隊(duì)尾所指的節(jié)點(diǎn)*/ q->rear=(q->rear+1)% MAXSIZE;/*隊(duì)尾向后移一位完成入隊(duì)*/ return 1;} 3）出隊(duì)的算法 int DeSqueue3(Squeue3 *q,Datatype *e)/*出隊(duì)*/ { if(q->front==q->rear){ printf(“隊(duì)列已空,無法出隊(duì)!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判斷隊(duì)列是否為空的算法 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(“隊(duì)列已空，無法出隊(duì)!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍歷循環(huán)隊(duì)列的算法 void display3(Squeue3 *q)//遍歷循環(huán)對列 { int tail;tail=q->front;printf(“此隊(duì)列數(shù)據(jù)為:n”);if(q->front==q->rear)printf(“此隊(duì)列為空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函數(shù)的算法 void main(){ int choice;Datatype e1;int i1,a1,x1,s1,j1;//順序隊(duì)列定義的量 int e2,i2,n2,s2,a2;//鏈隊(duì)列定義的量 int i3,a3,x3,s3,j3;//循環(huán)隊(duì)列定義的量 Datatype e3; Squeue1 Q1; //******************************* LinkQueue q; //******************************** Squeue3 Q; //**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://順序隊(duì)列 { system(“cls”);InitSqueue1(&Q1);printf(“創(chuàng)建隊(duì)列完成!n”);printf(“請輸入數(shù)據(jù)個數(shù)j1=”);scanf(“%d”,&j1);for(i1=1;i1<=j1;i1++)//輸入的數(shù)據(jù)個數(shù)不要超過MAXSIZE,多了的部分沒有插入隊(duì)列 { printf(“請輸入第%d個數(shù)據(jù):”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1); } printf(“對頭為:%dn”,Q1.data[Q1.front]);printf(“隊(duì)尾為:%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(“請輸入入隊(duì)元素: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(“此隊(duì)列為空!n”);else printf(“此隊(duì)列不為空!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(“創(chuàng)建隊(duì)列完成!n”);printf(“輸入將建立鏈隊(duì)列元素的個數(shù):n2=”);scanf(“%d”,&n2);printf(“請輸入隊(duì)列的元素：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(“請輸入入隊(duì)元素:”); scanf(“%d”,&e2);EnQueue2(&q,e2); output2(&q);a2=-1;start2(); }break; case 3: system(“cls”); e2=DeQueue2(&q,e2); output2(&q); printf(“出隊(duì)元素為:%dn”,e2);a2=-1;start2(); break; case 4:DestroyQueue2(&q);printf(“隊(duì)列已銷毀!n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 5: Clear2(&q);printf(“隊(duì)列已清空n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 6: system(“cls”);GetHead2(&q,&e2); printf(“隊(duì)頭元素為:%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(“創(chuàng)建隊(duì)列完成!n”);printf(“請輸入數(shù)據(jù)個數(shù)j3=”);scanf(“%d”,&j3);for(i3=1;i3<=j3;i3++)//輸入的數(shù)據(jù)個數(shù)不要超過MAXSIZE,多了的部分沒有插入隊(duì)列 { printf(“請輸入第%d個數(shù)據(jù):”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3); } printf(“對頭為:%dn”,Q.base[Q.front]);printf(“隊(duì)尾為:%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(“請輸入入隊(duì)元素: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(“此隊(duì)列為空!n”);else printf(“此隊(duì)列不為空!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(“ 謝謝使用?。”); break; //*************************** }//switch }//while }//main 四．調(diào)試分析（xxx） 順序隊(duì)列 1.編譯并調(diào)試，運(yùn)行程序。 2.設(shè)計(jì)測試用例，分析測試結(jié)果，以驗(yàn)證所完成的系統(tǒng)是否達(dá)到預(yù)期效果。3.判斷隊(duì)列是否為空。隊(duì)列是否為空的標(biāo)志就是隊(duì)頭指針和隊(duì)尾指針是否同時指向隊(duì)列中的同一個位置，即隊(duì)頭指針和隊(duì)尾指針是否相等。 4.隊(duì)列滿時候不能入隊(duì)列，否則會出現(xiàn)溢出現(xiàn)象。即先要判斷隊(duì)列是否已經(jīng)已滿，因?yàn)殛?duì)尾指針的最大值是MAXQSIZE，所以通過檢查隊(duì)尾指針rear是否等于MAXQSIZE來判斷隊(duì)列是否已滿。在刪除隊(duì)首元素時，應(yīng)首先通過隊(duì)頭指針和隊(duì)尾指針是否相等判斷隊(duì)列是否已空。 5.在元素出隊(duì)操作，先通過隊(duì)頭指針和隊(duì)尾指針是否相等判斷隊(duì)列是否已空，空時不能操作，這是要注意的。 6.程序滿足了本次試驗(yàn)的目的和任務(wù)要求，可以進(jìn)行人機(jī)交互，在后來的程序中將會做些改進(jìn)，以增強(qiáng)人機(jī)交互性。 7.本程序存在較多不足，如有問題，參考用戶手冊。 8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改進(jìn)，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。 鏈隊(duì)列 1.編譯并調(diào)試，運(yùn)行程序。2.設(shè)計(jì)測試用例，分析測試結(jié)果，以驗(yàn)證所完成的系統(tǒng)是否達(dá)到預(yù)期效果。 3.要注意設(shè)定一個在鏈隊(duì)列添加一個頭結(jié)點(diǎn)并令指針指向頭結(jié)點(diǎn)。同時，刪除不可以在最后面進(jìn)行刪除，但是插入可以最后一個進(jìn)行插入，這點(diǎn)需要注意 4.需要分別指向隊(duì)頭和隊(duì)尾的指針。 5.程序滿足了本次試驗(yàn)的目的和任務(wù)要求，可以進(jìn)行人機(jī)交互，在后來的程序中將會做些改進(jìn)，以增強(qiáng)人機(jī)交互性。 6.本程序存在較多不足，如有問題，參考用戶手冊。 7.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改進(jìn)，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。 循環(huán)隊(duì)列 1.編譯并調(diào)試，運(yùn)行程序。 2.設(shè)計(jì)測試用例，分析測試結(jié)果，以驗(yàn)證所完成的系統(tǒng)是否達(dá)到預(yù)期效果。 3.為了避免順序隊(duì)列造成的“假溢出”現(xiàn)象，我們通常采用順序循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列的順序存儲。4.隊(duì)頭指針和對尾指針與隊(duì)列元素之間關(guān)系和順序隊(duì)列一樣，不變。5.先判斷隊(duì)列是否為空。就是看隊(duì)頭指針和隊(duì)尾指針是否同時指向隊(duì)列中的同一個位置，即隊(duì)頭指針和隊(duì)尾指針是否相等，空時不能操作，這是要注意的。 6.在將元素插入到隊(duì)列之前首先要判斷隊(duì)列是否已經(jīng)已滿，根據(jù)順序循環(huán)隊(duì)列隊(duì)滿條件front==(rear+1)%MAXQSIZE來判斷隊(duì)列是否已滿。在刪除隊(duì)首元素時，應(yīng)首先通過隊(duì)頭指針和隊(duì)尾指針是否相等判斷隊(duì)列是否已空。 6.程序滿足了本次試驗(yàn)的目的和任務(wù)要求，可以進(jìn)行人機(jī)交互，在后來的程序中將會做些改進(jìn)，以增強(qiáng)人機(jī)交互性。 7.本程序存在較多不足，如有問題，參考用戶手冊。 8.在程序語句中，原本使用了大量的生僻的函數(shù)名，經(jīng)過改進(jìn)，目前使用都是通俗易懂的函數(shù)名稱，方便用戶理解。 五、用戶手冊(xx)1.鏈隊(duì)列 (1)本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行文件名為：j.exe.(2)進(jìn)入演示程序后即顯示文本方式的用戶界面，輸入元素1,2,3,4,5創(chuàng)建隊(duì)列。 （3）根據(jù)提示，選擇操作2執(zhí)行元素入隊(duì)操作?；剀?，輸入入隊(duì)元素0，回車，將0插入到隊(duì)列中。 （4）選擇操作3執(zhí)行元素出隊(duì)操作，回車，隊(duì)首元素1出隊(duì)。 （5）選擇操作1執(zhí)行輸出隊(duì)列長度操作，回車，輸出隊(duì)列長度為5.（6）選擇操作5執(zhí)行清空隊(duì)列操作，回車，清空。 （7）選擇操作6執(zhí)行輸出隊(duì)頭元素操作，回車，輸出元素2。 2.順序隊(duì)列 （1）創(chuàng)建隊(duì)列，輸入數(shù)據(jù) 1,2,3,4,5.（2）選擇操作1，執(zhí)行入隊(duì)操作.輸入入隊(duì)元素0 （3）選擇操作2，執(zhí)行出隊(duì)操作。 隊(duì)首元素1出隊(duì).（4）選擇操作3，判斷對是否為空 （5）選擇操作4，輸出對頭元素2.（6）選擇操作5，顯示隊(duì)列元素 3、循環(huán)隊(duì)列 （1）創(chuàng)建隊(duì)列，輸入數(shù)據(jù) 1,2,3,4,5.（2）選擇操作1，執(zhí)行入隊(duì)操作.輸入入隊(duì)元素0 （3）選擇操作2，執(zhí)行出隊(duì)操作。隊(duì)首元素1出隊(duì).（3）選擇操作3，判斷對是否為空 （5）選擇操作4，輸出對頭元素2.（6）選擇操作5，顯示隊(duì)列元素為,2,3,4,5,0 六．測試結(jié)果（xxx）1.順序隊(duì)列的實(shí)現(xiàn)和運(yùn)算 1）輸入1即可進(jìn)行進(jìn)入到順序隊(duì)列 2）順序隊(duì)列的建立，輸入元素的個數(shù)為5，輸入的數(shù)據(jù)分別為1，2，3，4，5，對頭為1，隊(duì)尾為5，此時隊(duì)列的數(shù)據(jù)為1 2 3 3）輸入2即可進(jìn)行入隊(duì)運(yùn)算，輸入的入隊(duì)元素為0，此時的隊(duì)列的數(shù)據(jù)為1 2 3 4 5 0 4）輸入3即可進(jìn)行判斷隊(duì)列的是否為空，如下圖： 5）輸入4即可進(jìn)行去的對頭元素的算法，如下圖所示： 6）此時的隊(duì)列的數(shù) 據(jù) 為 0，如 下 圖 ： 7）輸入0即可退出順序隊(duì)列，如下圖： 8）輸入3即可進(jìn)行順序隊(duì)列的算法，如下圖所示： 9）輸入1即可進(jìn) 行 相 應(yīng)的入 隊(duì) 運(yùn) 算，如 下 10）輸入2即可進(jìn)行隊(duì)列的出隊(duì)運(yùn)算，如下圖所示： 所 示 圖 ：11）輸入3 即可判斷順序隊(duì)列是否為空的算法，如下圖所示： 12）輸入4即可進(jìn)行去的頭結(jié)點(diǎn)的運(yùn)算，如下圖所示： 13）輸入5即可進(jìn)行隊(duì)列的輸出顯示的運(yùn)算，如 14）輸入0即可進(jìn)行退出順序隊(duì)列的算法，如下圖所示： 下圖所示：2.鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)和運(yùn)算 1）隊(duì)列的建立以及隊(duì)列的個數(shù)輸入為5，輸入的數(shù)據(jù)分別為1，2，3，4，5.如下圖： 2）輸入2即可進(jìn)入到元素的入隊(duì)運(yùn)算，輸入入隊(duì)的元素的為0，輸入3即可進(jìn)行相應(yīng)的元素的出隊(duì)運(yùn)算，出隊(duì)元素為1.如下圖： 3）則此時的隊(duì)列的長度為5，輸入4即可進(jìn)行隊(duì)列的銷毀以及輸入5即可進(jìn)行隊(duì)列的清空運(yùn)算，如下圖： 4）輸入6即可進(jìn)行輸出隊(duì)列的對頭元素，輸入0即可進(jìn)行退出鏈隊(duì)列的運(yùn)算 3．循環(huán)隊(duì)列的實(shí)現(xiàn)和運(yùn)算 1）輸入3即可進(jìn)行循環(huán)隊(duì)列的操作，輸入5個數(shù)據(jù)，它們分別為1 2 3 4 5，輸入1，即可進(jìn)行入隊(duì)操作，輸入入隊(duì)的元素為0，則此時的數(shù)據(jù)為1 2 3 4 5 0，如下圖所示： 2）輸入2即可進(jìn)行出隊(duì)運(yùn)算，如下圖所示： 3）輸入3即可進(jìn)行判斷隊(duì)列的是否為空，如下圖所示： 4）輸入4即可進(jìn)行取得對頭元素，如 下 5)輸入5即可進(jìn)行輸出所有的數(shù)據(jù)顯示，如下圖所示： 所示圖： 七．心得體會（xx） 隊(duì)列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進(jìn)行刪除操作，而在表的后端（rear）進(jìn)行插入操作，和棧一樣，隊(duì)列是一種操作受限制的線性表。進(jìn)行插入操作的端稱為隊(duì)尾，進(jìn)行刪除操作的端稱為隊(duì)頭。隊(duì)列中沒有元素時，稱為空隊(duì)列。 在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊(duì)列又稱為“先進(jìn)先出” 的線性表。注意的是為了避免順序隊(duì)列造成的“假溢出”現(xiàn)象，我們通常采用順序循環(huán)隊(duì)列實(shí)現(xiàn)隊(duì)列的順序存儲。還有要注意的是在C語言中不能用動態(tài)分配的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個最大隊(duì)列長度；若用戶無法估計(jì)所用隊(duì)列的最大長度，則宜采用鏈?zhǔn)疥?duì)列。 實(shí)驗(yàn)二 棧和隊(duì)列及其應(yīng)用 一、實(shí)驗(yàn)?zāi)康?/p> 1.掌握棧和隊(duì)列這兩種抽象數(shù)據(jù)類型的特點(diǎn)，并能在相應(yīng)的應(yīng)用問題中正確選用它們。 2.熟練掌握棧類型的兩種實(shí)現(xiàn)方法。 3.熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法。 二、實(shí)驗(yàn)內(nèi)容 用隊(duì)列求解迷宮問題 [問題描述] 以一個M*N的長方陣表示迷宮，0和1分別表示迷宮中的通路和墻壁。設(shè)計(jì)一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。[基本要求] 實(shí)現(xiàn)一個以順序存儲結(jié)構(gòu)的隊(duì)列類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，pre）的形式輸出，其中：（i，j）指示迷宮中的一個坐標(biāo)，pre表示本路徑中上一個方塊在隊(duì)列中的下標(biāo)。 [測試數(shù)據(jù)] 由學(xué)生任意指定。 三、源代碼 # include //行數(shù) //列數(shù) //隊(duì)最多元素個數(shù) //一個迷宮,其四周要加上均為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;//定義順序隊(duì) qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi;//(xi,yi)進(jìn)隊(duì) 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”); } 四、測試結(jié)果： 五、心得體會 做實(shí)驗(yàn)首先要掌握大量的理論知識，然后認(rèn)真去完成實(shí)驗(yàn)。做實(shí)驗(yàn)過程會碰見較大的困難，這就要需要我們的毅力。小小的迷宮隱藏大大的奧秘。 注意：實(shí)驗(yàn)結(jié)束后提交一份實(shí)驗(yàn)報告電子文檔 電子文檔命名為“學(xué)號+姓名”，如：E01214058宋思怡 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報告 （一）學(xué)號：姓名：專業(yè)年級： 實(shí)驗(yàn)名稱：線性表 實(shí)驗(yàn)日期：2014年4月14日 實(shí)驗(yàn)?zāi)康模?/p> 1、熟悉線性表的定義及其順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)； 2、熟練掌握線性表在順序存儲結(jié)構(gòu)上實(shí)現(xiàn)基本操作的方法； 3、熟練掌握在各種鏈表結(jié)構(gòu)中實(shí)現(xiàn)線性表基本操作的方法； 4、掌握用 C/C++語言調(diào)試程序的基本方法。 實(shí)驗(yàn)內(nèi)容： 一、編寫程序?qū)崿F(xiàn)順序表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個主程序完成如下功能： （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。 源代碼 調(diào)試分析（給出運(yùn)行結(jié)果界面） 二、編寫程序?qū)崿F(xiàn)單鏈表的各種基本運(yùn)算，并在此基礎(chǔ)上設(shè)計(jì)一個主程序完成如下功能： ???? ???? 小結(jié)或討論: （1）實(shí)驗(yàn)中遇到的問題和解決方法 （2）實(shí)驗(yàn)中沒有解決的問題 （3）體會和提高 南京信息工程大學(xué)實(shí)驗(yàn)（實(shí)習(xí)）報告 實(shí)驗(yàn)（實(shí)習(xí)）名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)（實(shí)習(xí)）日期 2011-11-2得分指導(dǎo)教師周素萍 系公共管理系專業(yè)信息管理與信息系統(tǒng)年級10級班次1姓名常玲學(xué)號2010230700 3實(shí)驗(yàn)一順序表的基本操作及C語言實(shí)現(xiàn) 【實(shí)驗(yàn)?zāi)康摹?/p> 1、順序表的基本操作及 C 語言實(shí)現(xiàn) 【實(shí)驗(yàn)要求】 1、用 C 語言建立自己的線性表結(jié)構(gòu)的程序庫，實(shí)現(xiàn)順序表的基本操作。 2、對線性表表示的集合，集合數(shù)據(jù)由用戶從鍵盤輸入（數(shù)據(jù)類型為整型），建立相應(yīng)的順序表，且使得數(shù)據(jù)按從小到大的順序存放，將兩個集合的并的結(jié)果存儲在一個新的線性表集合中，并輸出。 【實(shí)驗(yàn)內(nèi)容】 1、根據(jù)教材定義的順序表機(jī)構(gòu)，用 C 語言實(shí)現(xiàn)順序表結(jié)構(gòu)的創(chuàng)建、插入、刪除、查找等操作； 2、利用上述順序表操作實(shí)現(xiàn)如下程序：建立兩個順序表表示的集合（集合中無重 復(fù)的元素），并求這樣的兩個集合的并。 【實(shí)驗(yàn)結(jié)果】 [實(shí)驗(yàn)數(shù)據(jù)、結(jié)果、遇到的問題及解決] 一． 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; 三．// 將合并逆置后的結(jié)果放在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的前驅(qū)指針 // 保存pb的前驅(qū)指針 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;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//將當(dāng)前最小結(jié)點(diǎn)插入A表表頭 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 順序表就是把線性表的元素存儲在數(shù)組中，元素之間的關(guān)系直接通過相鄰元素的位置來表達(dá)。 優(yōu)點(diǎn)：簡單，數(shù)據(jù)元素的提取速度快； 缺點(diǎn)：（1）靜態(tài)存儲，無法預(yù)知問題規(guī)模的大小，可能空間不足，或浪費(fèi)存儲空間；（2）插入元素和刪除元素時間復(fù)雜度高——O（n） 求兩個集合的并集 該算法是求兩個集合s1和s2的并集，并將結(jié)果存入s引用參數(shù)所表示的集合中帶回。首先把s1集合復(fù)制到s中，然后把s2中的每個元素依次插入到集合s中，當(dāng)然重復(fù)的元素不應(yīng)該被插入，最后在s中就得到了s1和s2的并集，也就是在s所對應(yīng)的實(shí)際參數(shù)集合中得到并集。 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告 一． 題目要求 1）編程實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除； 2）對二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷； 3）每次對樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來。4）分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信息(至少包括學(xué)號、姓名、成績3項(xiàng)),對比查找效率，并說明在什么情況下二叉排序樹效率高,為什么? 二． 解決方案 對于前三個題目要求，我們用一個程序?qū)崿F(xiàn)代碼如下 #include typedefintElemType; //數(shù)據(jù)類型 typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉樹函數(shù) 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){//創(chuàng)建二叉樹函數(shù) BiTreebst=NULL;inti=0;while(i //數(shù)據(jù)域 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指向被刪除結(jié)點(diǎn)的前驅(qū) if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //刪除函數(shù)，在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(){//主函數(shù) printf(“ ---------------------二叉排序樹的實(shí)現(xiàn)-------------------”);printf(“n”);int layer;inti;intnum;printf(“輸入節(jié)點(diǎn)個數(shù):”);scanf(“%d”,&num);printf(“依次輸入這些整數(shù)（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉樹創(chuàng)建成功!”);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:插入節(jié)點(diǎn) 2:刪除節(jié)點(diǎn) 3:打印二叉樹 4:非遞歸遍歷二叉樹 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“輸入要插入的節(jié)點(diǎn):”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“樹狀圖為:n”); printtree(bst,layer); break; case 2: } printf(“輸入要刪除的節(jié)點(diǎn)”);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(“程序執(zhí)行完畢!”); return 0;} goto loop;} return 0;對于第四小問，要儲存學(xué)生的三個信息，需要把上面程序修改一下，二叉樹結(jié)構(gòu)變?yōu)?typedefintElemType; //數(shù)據(jù)類型 typedefstring SlemType; typedefint Status; //返回值類型 //定義二叉樹結(jié)構(gòu) typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //數(shù)據(jù)域 structBiTNode *lChild, *rChild;//左右子樹域 }BiTNode, *BiTree;參數(shù)不是key,而是另外三個 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉樹函數(shù) 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;} 其他含參函數(shù)也類似 即可完成50個信息存儲 用數(shù)組存儲50個信息，查看以往代碼 #include int main(){ cout<<“ 歡迎來到學(xué)生管理系統(tǒng)”< cout<<“該學(xué)號信息已經(jīng)存在，添加失敗”< break;} cout<<“重新輸入添加的學(xué)號”< 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<<“謝謝使用”< 二叉排序樹儲存數(shù)據(jù)界面（儲存學(xué)生信息略） 創(chuàng)建二叉樹： 插入節(jié)點(diǎn)： 刪除節(jié)點(diǎn)： 非遞歸遍歷： 退出： 數(shù)組儲存學(xué)生信息界面 分析查找效率： 因?yàn)槎鏄洳檎乙獎?chuàng)建二叉樹，而數(shù)組查找只創(chuàng)建一個數(shù)組，二叉樹的創(chuàng)建時間比較長，所以對于數(shù)據(jù)量較少的情況下數(shù)組的查找效率比較高。但當(dāng)數(shù)據(jù)量增加時，二叉樹的查找優(yōu)勢就顯現(xiàn)出來。所以數(shù)據(jù)量越大的時候，二叉樹的查找效率越高。 四． 總結(jié)與改進(jìn) 這個實(shí)驗(yàn)工作量還是很大的，做了很久。樹狀圖形輸出還是不美觀，還需要改進(jìn)。 一開始打算用棧實(shí)現(xiàn)非遞歸，但是根據(jù)書里面的偽代碼發(fā)現(xiàn)部分是在C++編譯器里運(yùn)行不了的（即使補(bǔ)充了頭文件和數(shù)據(jù)的定義），所以之后參考了網(wǎng)上的數(shù)組非遞歸，發(fā)現(xiàn)其功能和棧相似。 遞歸遍歷的實(shí)現(xiàn)比非遞歸的遍歷真的簡單很多。 開始時只看到前三問，所以沒有寫到儲存學(xué)生數(shù)據(jù)的代碼，里面還可以用clock（）函數(shù)加一個計(jì)算查找所要數(shù)據(jù)時間的代碼，讓二叉樹查找與數(shù)組查找到效率比較更加直觀。第二篇：2數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)報告二(棧和隊(duì)列及其應(yīng)用)
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告
第四篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告
第五篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告
點(diǎn)擊咨詢 