淮海工學院數(shù)據(jù)結構第2次實驗

1、.淮海工學院計算機科學系實驗報告書課程名：數(shù)據(jù)結構題 目： 線性數(shù)據(jù)結構實驗 （棧與對立隊列及其應用）班 級： 學 號： 2012122693姓 名： 評語：成績： 指導教師： 批閱時間： 年 月 日. v.線性表算法實現(xiàn)與應用報告要求1目的與要求:1）掌握棧與隊列的數(shù)據(jù)類型描述及特點；2）掌握棧的順序和鏈式存儲存表示與基本算法的實現(xiàn)；3）掌握隊列的鏈式和循環(huán)存儲表示與基本操作算法實現(xiàn);4) 掌握棧與隊列在實際問題中的應用和基本編程技巧;5）按照實驗題目要求，獨立完成實際程序的編寫編寫、調試和運行，并通過用例數(shù)的運行過程抓獲相關屏面驗證程序設計的正確性；7）由于國慶節(jié)占用授課時間，所以本次實驗

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

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

4、ck(SeqStack *S) S->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);i

5、nt Pop(SeqStack *S,int *x)/彈出 if(S->top = -1) return(FALSE);else *x = S->elemS->top;S->top-; return(TRUE);void main() SeqStack S;int x,y,i,l; InitStack(&S); if(!IsFull(&S)printf("?？眨簄");printf("輸入要壓入的元素個數(shù)（50以內）:n");scanf("%d",&l);printf("輸入要

6、壓入的元素：n");for(i=0;i<l;i+)scanf("%d",&y);Push(&S,y);printf("彈出：n");while(!IsEmpty(&S) Pop(&S,&x); printf("%dn",x);第二題：*define TRUE 1*define FALSE 0*include <stdio.h>*include <stdlib.h>typedef struct nodeint data;struct node *next;L

7、inkStackNode;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 Push(LinkStack S, int x)LinkStackNode *temp;temp=(LinkStackNode *)malloc(s

8、izeof(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->data;free(temp); return(TRUE);void main()LinkSt

9、ackNode *s; InitStack(&s);int x,i,l;if(IsEmpty(s)printf("?？?n");printf("請輸入壓入元素個數(shù)(50以內)：n"); scanf("%d",&l);printf("請輸入壓入元素：n");for(i=0;i<l;i+)scanf("%d",&x);Push(s,x);printf("彈出：n");while(!IsEmpty(s)Pop(s, &x);printf(&qu

10、ot;%dn",x);第三題：*include <stdio.h>*include <stdlib.h>*define TRUE 1*define FALSE 0*define MAXSIZE 50 typedef struct int 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->

11、;front) return(FALSE);Q->elementQ->rear=x;Q->rear=(Q->rear+1)%MAXSIZE; return(TRUE); int DeleteQueue(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->

12、rear) return(TRUE);elsereturn(FALSE); void main()SeqQueue s;InitQueue(&s);int x,i,l;if(IsEmpty (&s)printf("此時為空隊列n");printf("請輸入進隊元素個數(shù)n");scanf("%d",&l);printf("請輸入元素n");for(i=0;i<l;i+)scanf("%d",&x);EnterQueue(&s,x);printf(&qu

13、ot;出隊：n");while(!IsEmpty(&s)DeleteQueue(&s,&x);printf("%dn",x);if(IsEmpty (&s)printf("此時為空隊列n");第四題：*include <stdio.h>*include <stdlib.h>*define TRUE 1*define FALSE 0typedef struct Nodeint data;struct Node *next;LinkQueueNode;typedef structLinkQue

14、ueNode *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(FA

15、LSE);int EnterQueue(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)LinkQueueN

16、ode *p;if(Q->front=Q->rear)return(FALSE);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;InitQueue(&q);if(IsEmpty(&q)printf("此時為空隊列n");printf("請輸入進隊元個數(shù)素n

17、");scanf("%d",&l);printf("請輸入元素：n");for(i=0;i<l;i+)scanf("%d",&x);EnterQueue(&q,x);printf("出隊：n");for(i=0;i<l;i+)DeleteQueue(&q,&x); printf("%dn",x);if(IsEmpty(&q)printf("此時為空隊列n");4 測試數(shù)據(jù)與實驗結果（可以抓圖粘貼）5結果分析與實驗體會開始在編寫第一題時，將所有代碼完成后一直報錯，反復檢查代碼沒有錯誤，后來看到頭文件名是*include <iostream.h>因為C+習慣導致錯誤，后來改為<stdio.h>就正確了，