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

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

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

4、ack(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);int Pop(Se

5、qStack *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("輸入要壓入的元素個(gè)數(shù)（50以內(nèi)）:n");scanf("%d",&l);printf("輸入要壓入的元素：n&q

6、uot;);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;LinkStack

7、Node;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(sizeof(LinkSta

8、ckNode); 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()LinkStackNode *s; I

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

10、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->front) retur

11、n(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->rear) return(

12、TRUE);elsereturn(FALSE); void main()SeqQueue s;InitQueue(&s);int x,i,l;if(IsEmpty (&s)printf("此時(shí)為空隊(duì)列n");printf("請(qǐng)輸入進(jìn)隊(duì)元素個(gè)數(shù)n");scanf("%d",&l);printf("請(qǐng)輸入元素n");for(i=0;i<l;i+)scanf("%d",&x);EnterQueue(&s,x);printf("出隊(duì)：n"

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

14、 ;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 EnterQueu

15、e(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->fr

16、ont=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("此時(shí)為空隊(duì)列n");printf("請(qǐng)輸入進(jìn)隊(duì)元個(gè)數(shù)素n");scanf(&quo

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