淮海工學(xué)院數(shù)據(jù)結(jié)構(gòu)第2次實驗

1、淮海工學(xué)院計算機(jī)科學(xué)系實驗報告書課程名：數(shù)據(jù)結(jié)構(gòu)題 目：線性數(shù)據(jù)結(jié)構(gòu)實驗（棧與對立隊列及其應(yīng)用）班 級：學(xué) 號： 2012122693姓 名：評語:成績： 指導(dǎo)教師： 批閱時間:線性表算法實現(xiàn)與應(yīng)用報告要求1 目的與要求 :1）掌握棧與隊列的數(shù)據(jù)類型描述及特點；2）掌握棧的順序和鏈?zhǔn)酱鎯Υ姹硎九c基本算法的實現(xiàn)；3）掌握隊列的鏈?zhǔn)胶脱h(huán)存儲表示與基本操作算法實現(xiàn);4）掌握棧與隊列在實際問題中的應(yīng)用和基本編程技巧 ;5）按照實驗題目要求，獨立完成實際程序的編寫編寫、調(diào)試和運行，并通過用例數(shù)的運行 過程抓獲相關(guān)屏面驗證程序設(shè)計的正確性；7）由于國慶節(jié)占用授課時間， 所以本次實驗將不做統(tǒng)一上機(jī)安排，要

2、求同學(xué)們節(jié)日期間自 行完成實驗任務(wù)，并于第 6 周周 4 以前按時提交實驗報告。2 實驗內(nèi)容或題目（一）必做題：1、實現(xiàn)順序棧的創(chuàng)建（初始化） 、壓入（插入） 、彈出（刪除）操作（數(shù)據(jù)元素類型自己選取， 如整型、字符型等） ，并給出棧的每次操作變化狀態(tài)；2、實現(xiàn)鏈棧的創(chuàng)建（初始化） 、壓入（插入） 、彈出（刪除）操作（數(shù)據(jù)元素類型自己選取，如 整型、字符型等） ，要求給出棧的操作變化過程；3、實現(xiàn)循環(huán)隊列的創(chuàng)建、 進(jìn)隊、出隊等基本操作 （數(shù)據(jù)元素類型自己選取， 如整型、 字符型等）， 并實時給出隊列的操作變化狀態(tài)；4、實現(xiàn)鏈?zhǔn)疥犃械膭?chuàng)建、 進(jìn)隊、出隊等基本操作 （數(shù)據(jù)元素類型自己選取， 如整型

3、、 字符型等）， 并實時給出隊列的操作變化狀態(tài)；（二）選做題（視自己能力而定，數(shù)量不限） ：任選一個或多個源程序（已經(jīng)發(fā)給學(xué)委） ，并閱 讀、調(diào)試和運行程序，而后給出程序功能分析和實例運行演示；1、實現(xiàn)表達(dá)式求值算法程序；2、用遞歸算法實現(xiàn)漢諾塔問題算法程序；3、使用循環(huán)隊列實現(xiàn)打印楊輝三角形算法程序。3 實驗步驟與源程序第一題：#include #include #define TRUE 1#define FALSE 0#define Size 50typedef structint elemSize;int top;SeqStack;void InitStack(SeqStack *S)S

4、-top =-1;int IsEmpty(SeqStack *S)return(S-top=-1?TRUE:FALSE);/ 判斷?？?為空是真 反之為假int IsFull(SeqStack *S)return(S-top=Size-1?TRUE:FALSE);/ 判斷棧滿 為滿是真 反之為假int Push(SeqStack *S,int x)/ 壓棧if(S-top=Size-1)return(FALSE);S-top+;S-elemS-top = x;return(TRUE);int Pop(SeqStack *S,int *x)/ 彈出if(S-top = -1) return(FA

5、LSE);else*x = S-elemS-top;S-top-; return(TRUE);void main()SeqStack S;int x,y,i,l;InitStack(&S);if(!IsFull(&S)printf( 棧空： n);:n);printf( 輸入要壓入的元素個數(shù)( 50 以內(nèi)) scanf(%d,&l);printf( 輸入要壓入的元素： n); for(i=0;il;i+)scanf(%d,&y); Push(&S,y);printf( 彈出： n);while(!IsEmpty(&S)Pop(&S,&x);printf(%dn,x);第二題：#define T

6、RUE 1#define FALSE 0#include #include typedef struct nodeint data;struct node *next;LinkStackNode;typedef LinkStackNode *LinkStack;int IsEmpty(LinkStack S)return NULL=S-next?TRUE:FALSE;int InitStack(LinkStack *S)*S=(node*)malloc(sizeof(node); if(NULL=*S)return FALSE;(*S)-next =NULL;return TRUE;int P

7、ush(LinkStack S, int x) LinkStackNode *temp; temp=(LinkStackNode *)malloc(sizeof(LinkStackNode); if(temp=NULL)return(FALSE); temp-data=x; temp-next=S-next; S-next=temp; return(TRUE);int Pop(LinkStack S, int *x) LinkStackNode * temp; temp=S-next; if(temp=NULL)return(FALSE); S-next=temp-next; *x=temp-

8、data; free(temp); return(TRUE); void main() LinkStackNode *s;InitStack(&s);int x,i,l; if(IsEmpty(s) printf( ?？?n);printf( 請輸入壓入元素個數(shù) (50 以內(nèi) ) ： n); scanf(%d,&l);printf( 請輸入壓入元素： n); for(i=0;il;i+)scanf(%d,&x); Push(s,x);printf( 彈出： n); while(!IsEmpty(s)Pop(s, &x);printf(%dn,x);第三題：#include #include #

9、define TRUE 1#define FALSE 0#define MAXSIZE 50typedef structint elementMAXSIZE;int front;int rear;SeqQueue;void InitQueue(SeqQueue *Q)Q-front=Q-rear=0;int EnterQueue(SeqQueue *Q, int x)if(Q-rear+1)%MAXSIZE=Q-front) return(FALSE);Q-elementQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;return(TRUE);int DeleteQueu

10、e(SeqQueue *Q, int *x)if(Q-front=Q-rear)return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE; return(TRUE);int IsEmpty(SeqQueue *Q)if(Q-front=Q-rear) return(TRUE);elsereturn(FALSE); void main() SeqQueue s; InitQueue(&s); int x,i,l;if(IsEmpty (&s) printf( 此時為空隊列 n);printf( 請輸入進(jìn)隊元素個數(shù) n); scan

11、f(%d,&l);printf( 請輸入元素 n); for(i=0;il;i+) scanf(%d,&x); EnterQueue(&s,x); printf( 出隊： n); while(!IsEmpty(&s)DeleteQueue(&s,&x); printf(%dn,x);if(IsEmpty (&s)printf( 此時為空隊列 n); 第四題：#include #include #define TRUE 1 #define FALSE 0 typedef struct Node int data; struct Node *next;LinkQueueNode; typedef

12、struct LinkQueueNode *front ; LinkQueueNode *rear;LinkQueue;int IsEmpty(LinkQueue *Q)return Q-front =Q-rear?TRUE:FALSE;int InitQueue(LinkQueue *Q)Q-front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL; return (TRUE);else return(FALSE);int EnterQueue(

13、LinkQueue *Q,int x)LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode); if(NewNode!=NULL)NewNode-data=x; NewNode-next=NULL; Q-rear-next=NewNode; Q-rear=NewNode; return (TRUE);else return(FALSE);int DeleteQueue(LinkQueue *Q,int *x)LinkQueueNode *p; if(Q-front=Q-rear) return(F

14、ALSE);p=Q-front-next ;Q-front-next =p-next ; if(Q-rear=p) Q-rear=Q-front;*x=p-data;free(p);return (TRUE);void main()LinkQueue q;int x,i,l;Ini tQueue(&q);if(lsEmpty(&q)printf( 此時為空隊列n”);printf(”請輸入進(jìn)隊元個數(shù)素n);scan f(%d,&l);printf(”請輸入元素：n);for(i=0;il;i+)scan f(%d，& x);En terQueue( &q,x);printf(出隊：n);for(i=0;il;i+)DeleteQueue(&q,&x);prin tf(%dn,x); if(IsEmpty(&q)printf( 此時為空隊列n”);4測試數(shù)據(jù)與實驗結(jié)果（可以抓圖粘貼）S3學(xué)習(xí)爾掠*gflg結(jié)構(gòu)蔑二次實驗冋5結(jié)果分析與實驗體會開始在編寫第一題時，將所有代碼完成后一直報錯， 反復(fù)檢查代碼沒有錯誤，后來 看到頭文件名是#inelude iostream.h因為C+習(xí)慣導(dǎo)致錯誤，后來改為stdio.h就 正確了， 而