《聊城大学计算机学院2016-2017学年第1学期《数据结构》实验报告》由会员分享，可在线阅读，更多相关《聊城大学计算机学院2016-2017学年第1学期《数据结构》实验报告（21页珍藏版）》请在金锄头文库上搜索。
1、LIAOCHENG UNIVERSITY计算机学院实验报告【20 16 20 17 学年第 1 学期】【一、基本信息】【实验课程】数据结构【设课形式】独立 非独立【课程学分】4【实验项目】栈和队列【项目类型】基础 综合 设计 研究创新 其它 【项目学时】4【学生姓名】【学 号】【系别专业】软件开发【实验班组】 15级 11班 组 台 【同组学生】 【实验室名】 综合实验楼 【实验日期】2016.【报告日期】2016.【二、实验教师对报告的最终评价及处理意见】实验成绩： （涂改无效） 指导教师签名：张XX 2016年 月 日注：要将实验项目、实验课程的成绩评定及课程考核办法明确告知学生，并报实验
2、管理中心备案21【三、实验预习】实验目的和要求：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+=S
5、TACKINCREMENT; / 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 =
6、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 -2type
7、def 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 t
8、o 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 =
9、 (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
10、; /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:
11、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) %
