数据结构实验报告二

1、.LIAOCHENG UNIVERSITY计算机学院实验报告【20 1620 17学年第 1学期】【一、基本信息】【实验课程】数据结构【设课形式】独立非独立?【课程学分】4【实验项目】栈和队列【项目类型】基础? 综合设计研究创新其它【项目学时】4【学生姓名】沈凯【学号】2015205377【系别专业】软件开发【实验班组】15级11班组台【同组学生】【实验室名】综合实验楼【实验日期】2016.【报告日期】2016.【二、实验教师对报告的最终评价及处理意见】实验成绩：（涂改无效）指导教师签名：张振领2016年月日注：要将实验项目、实验课程的成绩评定及课程考核办法明确告知学生，并报实验管理中心备案.

2、【三、实验预习】实验目的和要求：1、熟练掌握栈和队列的结构，以及这种数据结构的特点；2、会定义顺序栈、循环队列，能实现栈、队列的基本操作；3、会利用栈解决典型问题，如数制转换等。实验内容和原理或涉及的知识点：用 C语言设计实现栈的初始化、 入栈、出栈、判空等功能，并利用栈完成数制转换功能；设计实现循环队列的定义、初始化、入队、出队、求队列长度等功能。实验条件：具有 C语言集成开发环境的计算机实验设计方案：栈设计的算法有：1、初始化栈；2、入栈；3、出栈；4、判断栈是否为空；5、十进制转换为八进制。队列设计的算法有：1、初始化；.2、入队；3、出队；4、求队列长度。实验预习成绩（涂改无效）合格不

3、合格.【四、实验过程、数据和实验结果记录】.实验方法、步骤、操作过程的记录描述或程序代码。实验过程中输入/ 输出数据、程序运行结果的记录。（可加附页）1、根据实验预习阶段的实验设计方案，编写顺序栈的伪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、将算法细化为程序代码。#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、编译、链接、运行程序。int main()printf("Please input a number to conver:n");conversion();return 0;4、循环队列的伪C 代码如下：#define MAXQSIZE 100 /最大队列长度typedef struct QElemType *base; /动态分配存储空间int front;/头指针，若队列

12、不空，/指向队列头元素int rear;/尾指针，若队列不空，指向队列尾元素的下一个位置 SqQueue;Status InitQueue (SqQueue &Q) /构造一个空队列QQ.base = (ElemType *) malloc(MAXQSIZE *sizeof (ElemType);if (!Q.base) exit (OVERFLOW);/存储分配失败Q.front = Q.rear = 0;return OK;Status EnQueue (SqQueue &Q, ElemType e) /插入元素e 为 Q的新的队尾元素if (Q.rear+1) % MAX

13、QSIZE = Q.front)return ERROR; /队列满.Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXQSIZE;return OK;Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除 Q的队头元素，/用 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、将算法细化成程序代码：#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