数据结构实验报告二.doc

上传人:小** 文档编号:3019564 上传时间:2020-06-22 格式:DOC 页数:22 大小:132.19KB
返回 下载 相关 举报
数据结构实验报告二.doc_第1页
第1页 / 共22页
数据结构实验报告二.doc_第2页
第2页 / 共22页
点击查看更多>>
资源描述

《数据结构实验报告二.doc》由会员分享,可在线阅读,更多相关《数据结构实验报告二.doc(22页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、!-LIAOCHENG UNIVERSITY计算机学院实验报告【20 16 20 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) ex

4、it (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.

5、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,

6、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 OVE

7、RFLOW -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 inpu

8、t 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)

9、/栈满 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-to

10、p; 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 numbe

11、r 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 (ElemTy

12、pe); 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) / 若队列不空,则删

13、除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_

14、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;

15、 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);

16、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);

17、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-rea

18、r = 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); Pus

19、h(&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;实验数据和实验结果记录栈程序的一个运行实例如下。队列的一个运行实例如下:记录成绩(涂改无效)合格不合格【五、实验结果分析】1、分析数制转换时后进先出的特点;2、分析如果将数转换为二进制, conversion函数的修改;3、分析如果没有初始化栈的操作时程序的运行结果;3、写出自己的心得体会。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 技术资料 > 其他杂项

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁