数据结构实验报告二.doc

。LIAOCHENG UNIVERSITY计算机学院实验报告【20 16 20 17 学年第 1 学期】【一、基本信息】【实验课程】数据结构【设课形式】独立 非独立【课程学分】4【实验项目】栈和队列【项目类型】基础 综合 设计 研究创新 其它 【项目学时】4【学生姓名】沈凯【学 号】2015205377【系别专业】软件开发【实验班组】 15级 11班 组 台 【同组学生】 【实验室名】 综合实验楼 【实验日期】2016.【报告日期】2016.【二、实验教师对报告的最终评价及处理意见】实验成绩： （涂改无效） 指导教师签名：张振领 2016年 月 日注：要将实验项目、实验课程的成绩评定及课程考核办法明确告知学生，并报实验管理中心备案-可编辑修改-【三、实验预习】实验目的和要求：1、熟练掌握栈和队列的结构，以及这种数据结构的特点；2、会定义顺序栈、循环队列，能实现栈、队列的基本操作；3、会利用栈解决典型问题，如数制转换等。实验内容和原理或涉及的知识点：用C语言设计实现栈的初始化、入栈、出栈、判空等功能，并利用栈完成数制转换功能；设计实现循环队列的定义、初始化、入队、出队、求队列长度等功能。实验条件：具有C语言集成开发环境的计算机实验设计方案：栈设计的算法有：1、初始化栈；2、入栈；3、出栈；4、判断栈是否为空；5、十进制转换为八进制。队列设计的算法有：1、初始化；2、入队；3、出队；4、求队列长度。实验预习成绩（涂改无效）合格不合格 【四、实验过程、数据和实验结果记录】实验方法、步骤、操作过程的记录描述或程序代码。实验过程中输入/输出数据、程序运行结果的记录。（可加附页）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);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+=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; /Pop Status 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 ( %d, e ); / conversion2、将算法细化为程序代码。#include #include #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 Status;typedef int SElemType;typedef struct SElemType *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 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;Status 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(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 (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; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 队列尾元素 的下一个位置 SqQueue;Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.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) % MAXQSIZE = 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; 否则返回ERROR if (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、将算法细化成程序代码：#include #include #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#define MAXQSIZE 100typedef int Status;typedef int ElemType;typedef int QElemType;typedef struct QNode QElemType data; struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;Status InitQueue(LinkQueue *Q);Status 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(&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 DestoryQueue(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; QueuePtr 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、编译、链接、运行程序。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,