數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告二

1、計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告【20 16 20 17 學(xué)年第1學(xué)期】【一、根本信息】【實(shí)驗(yàn)課程】數(shù)據(jù)結(jié)構(gòu)【設(shè)課形式】獨(dú)立口非獨(dú)立？【課程學(xué)分】4【實(shí)驗(yàn)工程】棧和隊(duì)列【工程類型】根底？綜合口 設(shè)計(jì)口 研究創(chuàng)新口 其它【工程學(xué)時(shí)】4【學(xué)生姓名】沈凱【學(xué)號(hào)】2021205377【系別專業(yè)】軟件開發(fā)【實(shí)驗(yàn)班組】15 級(jí)11班組臺(tái)【同組學(xué)生】【實(shí)驗(yàn)室名】綜合實(shí)驗(yàn)樓【實(shí)驗(yàn)日期】2021.【報(bào)告日期】2021.【一、實(shí)驗(yàn)教師對(duì)才聘的最終評(píng)價(jià)及處理意見】實(shí)驗(yàn)成績(jī)：涂改無(wú)效指導(dǎo)教師簽名：張振領(lǐng)2021 年 月曰注：要將實(shí)驗(yàn)工程、實(shí)驗(yàn)課程的成績(jī)?cè)u(píng)定及課程考核方法明確告知學(xué)生,并報(bào)實(shí)驗(yàn)治理中央備案【三、實(shí)驗(yàn)預(yù)習(xí)】實(shí)驗(yàn)?zāi)康暮鸵?/p>

2、求：1、熟練掌握棧和隊(duì)列的結(jié)構(gòu),以及這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)；2、會(huì)定義順序棧、循環(huán)隊(duì)列,能實(shí)現(xiàn)棧、隊(duì)列的根本操作;3、會(huì)利用棧解決典型問(wèn)題,如數(shù)制轉(zhuǎn)換等.實(shí)驗(yàn)內(nèi)容和原理或涉及的知識(shí)點(diǎn)：用C語(yǔ)言設(shè)計(jì)實(shí)現(xiàn)棧的初始化、入棧、出棧、判空等功能,并利用棧完成數(shù)制轉(zhuǎn) 換功能；設(shè)計(jì)實(shí)現(xiàn)循環(huán)隊(duì)列的定義、初始化、入隊(duì)、出隊(duì)、求隊(duì)列長(zhǎng)度等功能.實(shí)驗(yàn)條件：具有C語(yǔ)言集成開發(fā)環(huán)境的計(jì)算機(jī)實(shí)驗(yàn)設(shè)計(jì)方案：棧設(shè)計(jì)的算法有：1、初始化棧；2、入棧；3、出棧；4、判斷棧是否為空；5、十進(jìn)制轉(zhuǎn)換為八進(jìn)制隊(duì)列設(shè)計(jì)的算法有：1、初始化;2、入隊(duì);3、出隊(duì)；4、求隊(duì)列長(zhǎng)度實(shí)驗(yàn)預(yù)習(xí)成績(jī)涂改無(wú)效合格口不合格口【四、實(shí)驗(yàn)過(guò)程、數(shù)據(jù)和實(shí)驗(yàn)結(jié)果記錄

3、】/頁(yè))1、根據(jù)實(shí)驗(yàn)預(yù)習(xí)階段的實(shí)驗(yàn)設(shè)計(jì)方案,編寫順序棧的偽 C代碼如下.typedef struct (SElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(SqStack &S) (S.base = (SElemType *)malloc (STACK_INIT_SIZE*sizeof (SElemType);if (!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStackS

4、tatus Push(SqStack &S, SElemType e) (if (S.top-S.base>=S.stacksize) /棧滿( S.base=(SElemType *)realloc(S.base, (S.stacksize+STACKINCREMENT)* sizeof(SElemType);if (!S.base) exit (OVERFLOW);S.top = S.base + S.stacksize;S.stacksize+=STACKINCREMENT; / if*S.top+ = e; return OK; /PushStatus Pop(SqSta

5、ck &S, SElemType &e) (if(S.top = S.base)return ERROR;e = * - S.top;return OK; /PopStatus StackEmpty(SqStack S)(if (S.base=S.top)return TRUE;return FALSE;void conversion () (InitStack(S);scanf ("%d,&N);while (N) (Push(S, N % 8);N = N/8;while (!StackEmpty(S) (Pop(S,e);printf ( "%

6、d", e );) / conversion2、將算法細(xì)化為程序代碼.#include <stdio.h>#include <stdlib.h>#define LIST_INIT_SIZE 10#define LISTINCREMENT 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int S

7、tatus;typedef int SElemType;typedef structSElemType *base;SElemType *top;int stacksize; SqStack;Status InitStack(SqStack *S);Status Push(SqStack *S, SElemType e);Status Pop(SqStack *S, SElemType *e);Status StackEmpty(SqStack S);void conversion ();int main()printf("Please input a number to conve

8、r:n");conversion();return 0;Status InitStack(SqStack *S)S->base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof (SElemType);if (!S->base) exit (OVERFLOW);S->top = S->base;S->stacksize = STACK_INIT_SIZE;return OK;Status Push(SqStack *S, SElemType e)(if (S->top - S->base >= S

9、->stacksize) /棧滿(S->base = (SElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT)* sizeof(SElemType);if (!S->base) exit (OVERFLOW);S->top = S->base + S->stacksize;S->stacksize += STACKINCREMENT; / if*S->top+ = e;return OK; /PushStatus Pop(SqStack *S, SElemType *e

10、)(if(S->top = S->base)return ERROR;*e = *-S->top;return OK; /PopStatus StackEmpty(SqStack S)if (S.base = S.top)return TRUE;return FALSE;void conversion ()SqStack S;int N,e;InitStack(&S);scanf ("%d",&N);while (N)Push(&S, N % 8);N = N/8;while (!StackEmpty(S)Pop(&S, &

11、amp;e);printf ("%d", e);3、編譯、鏈接、運(yùn)行程序int main()(printf("Please input a number to conver:n");conversion();return 0;4、循環(huán)隊(duì)列的偽C代碼如下:#define MAXQSIZE 100/ 最大隊(duì)列長(zhǎng)度typedef struct (QElemType *base;/動(dòng)態(tài)分配存儲(chǔ)空間int front; /頭指針,假設(shè)隊(duì)列不空,/指向隊(duì)列頭元素int rear; /尾指針,假設(shè)隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置 SqQueue;Status In

12、itQueue (SqQueue &Q) /構(gòu)造一個(gè)空隊(duì)列 QQ.base = (ElemType *) malloc(MAXQSIZE *sizeof (ElemType);/if (!Q.base) exit (OVERFLOW);存儲(chǔ)分配失敗Q.front = Q.rear = 0;return OK;Status EnQueue (SqQueue &Q, ElemType e) /插入元素e為Q的新的隊(duì)尾元素if (Q.rear+1) % MAXQSIZE = Q.front)return ERROR; /隊(duì)列滿Q.baseQ.rear = e;Q.rear = (Q.

13、rear+1) % MAXQSIZE;return OK;Status DeQueue (SqQueue &Q, ElemType &e) / 假設(shè)隊(duì)列不空,那么刪除 Q的隊(duì)頭元素,/ 用e返回其值,并返回 OK;否那么返回ERRORif (Q.front = Q.rear) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1) % MAXQSIZE;return OK;int QueueLength(SqQueue Q)return (Q.rear - Q.front+MAXSIZE) % MAXSIZE;5、將算法細(xì)化成程

14、序代碼：#include <stdio.h>#include <stdlib.h>#define LIST_INIT_SIZE 10#define LISTINCREMENT 100#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define FALSE 0#define true 1#define false 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define OPSETSIZE 7#

15、define MAXQSIZE 100typedef int Status;typedef int ElemType;typedef int QElemType;typedef struct QNodeQElemType data;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue *Q);Status Push(LinkQueue *Q, QElemType e);Status Pop(LinkQueue *Q,

16、QElemType *e);int main()LinkQueue Q;QElemType e;InitQueue(&Q);Push(&Q, 1);Push(&Q, 2);Push(&Q, 3);Push(&Q, 4);printf("Push(&Q, 1);nPush(&Q, 2);nPush(&Q, 3);nPush(&Q, 4);n");while(Pop(&Q, &e)printf("Pop(&Q, &e);ne= %dn, e);DestoryQueu

17、e(&Q);return 0;Status InitQueue(LinkQueue *Q)(Q->front = Q->rear = (QueuePtr)malloc(MAXQSIZE * sizeof(QNode);if(!Q->front)exit(OVERFLOW);Q->front->next = NULL;return OK;Status DestoryQueue(LinkQueue *Q)(while(Q->front)(Q->rear = Q->front->next;free(Q->front);Q->f

18、ront = Q->rear;return OK;Status Push(LinkQueue *Q, QElemType e)(QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p->data = e;Q->rear->next = p;p->next = NULL;Q->rear = p;return OK;Status Pop(LinkQueue *Q, QElemType *e)if(Q->front = Q->rear)return ERROR;QueuePtr

19、p = Q->front->next;*e = p->data;Q->front->next = p->next;if(Q->rear = p)Q->rear = Q->front;free(p);return OK;6、編譯、鏈接、運(yùn)行程序.int main()LinkQueue Q;QElemType e;InitQueue(&Q);Push(&Q, 1);Push(&Q, 2);Push(&Q, 3);Push(&Q, 4);printf("Push(&Q, 1);nPush(

20、&Q, 2);nPush(&Q, 3);nPush(&Q, 4);n");while(Pop(&Q, &e)printf("Pop(&Q, &e);ne= %dn, e);DestoryQueue(&Q);return 0;實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)結(jié)果記錄棧程序的一個(gè)運(yùn)行實(shí)例如下a D-WDf?KVC?Vnain£xe-ticipLi" q rrjjQDEr *o con'r i1 B 1| L| U 4 d' JZjj04Process retirncd 0 (OxD) execut

21、icn time * 6. 100 wPrsss any k.2v to cont. intiE.隊(duì)列的一個(gè)運(yùn)行實(shí)例如下:C:UserspcDesktopsqqueueDebugsqqueuE exeO|choose operation: 6:1: enqueue 2: dequeue 1 PL«as» input ths 01«n»nt to insert: 3 PL事占等鼻 choo* operation： 0：it 11 «nqusu* 2: d*queu» 1 PLa&« input thw «l&

22、#171;*i»nt to insert 8 PLase choose npration: 0:axit 1: enqueue 2: dequeue 1 PLase input theto insert:7 Please cheo operation： fl:exit 1i «nqueu« 2： d«quu» 1 PLase input theto insert:6 Please choose operation： 6:exit 1: enqueue 2: dequeue q 9B7EPL甦甘9整 已he.在0 operation： .：整xit 1:登nquu尊2: d«quu»2 the deleted element is 9 Please choose ope