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

1、.LIAOCHENG UNIVERSITY計(jì)算機(jī)學(xué)院實(shí)驗(yàn)報(bào)告【20 1620 17學(xué)年第 1學(xué)期】【一、基本信息】【實(shí)驗(yàn)課程】數(shù)據(jù)結(jié)構(gòu)【設(shè)課形式】獨(dú)立非獨(dú)立?【課程學(xué)分】4【實(shí)驗(yàn)項(xiàng)目】棧和隊(duì)列【項(xiàng)目類型】基礎(chǔ)? 綜合設(shè)計(jì)研究創(chuàng)新其它【項(xiàng)目學(xué)時(shí)】4【學(xué)生姓名】沈凱【學(xué)號(hào)】2015205377【系別專業(yè)】軟件開發(fā)【實(shí)驗(yàn)班組】15級(jí)11班組臺(tái)【同組學(xué)生】【實(shí)驗(yàn)室名】綜合實(shí)驗(yàn)樓【實(shí)驗(yàn)日期】2016.【報(bào)告日期】2016.【二、實(shí)驗(yàn)教師對(duì)報(bào)告的最終評(píng)價(jià)及處理意見(jiàn)】實(shí)驗(yàn)成績(jī)：（涂改無(wú)效）指導(dǎo)教師簽名：張振領(lǐng)2016年月日注：要將實(shí)驗(yàn)項(xiàng)目、實(shí)驗(yàn)課程的成績(jī)?cè)u(píng)定及課程考核辦法明確告知學(xué)生，并報(bào)實(shí)驗(yàn)管理中心備案.

2、【三、實(shí)驗(yàn)預(yù)習(xí)】實(shí)驗(yàn)?zāi)康暮鸵螅?、熟練掌握棧和隊(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ú)效）合格不

3、合格.【四、實(shí)驗(yàn)過(guò)程、數(shù)據(jù)和實(shí)驗(yàn)結(jié)果記錄】.實(shí)驗(yàn)方法、步驟、操作過(guò)程的記錄描述或程序代碼。實(shí)驗(yàn)過(guò)程中輸入/ 輸出數(shù)據(jù)、程序運(yùn)行結(jié)果的記錄。（可加附頁(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)

4、;S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStackStatus 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+=

5、STACKINCREMENT; / if*S.top+ = e;return OK; /PushStatus Pop(SqStack &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(

6、S, N % 8);N = N/8;while (!StackEmpty(S) .Pop(S,e);printf ( "%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#de

7、fine ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;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 c

8、onversion ();int main()printf("Please input a number to conver: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;.Stat

9、us 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-

10、>top+ = e;return OK; /PushStatus Pop(SqStack *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 ()SqStack S;int N,e;InitStack(&S);scanf ("%d",&N);while (

11、N)Push(&S, N % 8);N = N/8;while (!StackEmpty(S)Pop(&S, &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;/頭指針，若隊(duì)列

12、不空，/指向隊(duì)列頭元素int rear;/尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置 SqQueue;Status InitQueue (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) % MAX

13、QSIZE = Q.front)return ERROR; /隊(duì)列滿.Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXQSIZE;return OK;Status DeQueue (SqQueue &Q, ElemType &e) / 若隊(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(Sq

14、Queue Q)return (Q.rear - Q.front+MAXSIZE) % MAXSIZE;5、將算法細(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 true 1#define false 0.#define OK 1#define ERROR

15、 0#define INFEASIBLE -1#define OVERFLOW -2#define OPSETSIZE 7#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);St

16、atus DestoryQueue(LinkQueue *Q);.Status Push(LinkQueue *Q, QElemType e);Status Pop(LinkQueue *Q, 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(&

17、;Q, 4);n");while(Pop(&Q, &e)printf("Pop(&Q, &e);ne= %dn", e);DestoryQueue(&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 De

18、storyQueue(LinkQueue *Q)while(Q->front)Q->rear = Q->front->next;free(Q->front);Q->front = 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;QueuePt