数据结构实验报告二

LIAOCHENGUNIVERSITY

计算机学院实验报告

【2016～2017学年第1学期】

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

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

【四、实验过程、数据和实验结果记录】 ①实验方法、步骤、操作过程的记录描述或程序代码。②实验过程中输入/输出数据、程序运行结果的记录。（可加附页） 1、根据实验预习阶段的实验设计方案，编写顺序栈的伪C代码如下。 typedefstruct { SElemType *base; SElemType *top; intstacksize; }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; } //InitStack Status Push(SqStack&S, SElemType e) { { if (S.base==S.top) return TRUE; return FALSE; } void conversion () { InitStack(S); scanf (\"%d\ while (N) { Push(S, N % 8); N = N/8;

3

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; } //Push if(S.top == S.base)return ERROR; e = * -- S.top; return OK; } //Pop Status Pop(SqStack&S, SElemType&e) { Status StackEmpty(SqStack S) } while (!StackEmpty(S)) { Pop(S,e); printf ( \"%d\ } } // conversion 2、将算法细化为程序代码。 #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 -2 typedefint Status; typedefintSElemType; typedefstruct { SElemType *base; SElemType *top; intstacksize; } SqStack; Status InitStack(SqStack *S); Status Push(SqStack *S, SElemType e); Status Pop(SqStack *S, SElemType *e); Status StackEmpty(SqStack S);

4

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; } //Push Status Pop(SqStack *S, SElemType *e)

5

{ 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 () { SqStack S; intN,e; InitStack(&S); scanf (\"%d\ while (N) { Push(&S, N % 8); N = N/8; } while (!StackEmpty(S)) { Pop(&S, &e); printf (\"%d\ } } 3、编译、链接、运行程序。 int main()

6

{ printf(\"Please input a number to conver:\\n\"); conversion(); return 0; 4、循环队列的伪C代码如下： #define MAXQSIZE 100 //最大队列长度 typedefstruct { 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.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } Status DeQueue (SqQueue&Q, ElemType&e) { // 若队列不空，则删除Q的队头元素，

7

// 用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } intQueueLength(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 100 typedefint Status; typedefintElemType; typedefintQElemType; typedefstructQNode {

8

QElemType data; structQNode *next; }QNode, *QueuePtr; typedefstruct { 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= %d\\n\ } DestoryQueue(&Q); return 0; }

9

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;

10

} 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, 4);\\n\"); while(Pop(&Q, &e)) { printf(\"Pop(&Q, &e);\\ne= %d\\n\ } DestoryQueue(&Q); return 0; }

11

实验数据和实验结果记录 栈程序的一个运行实例如下。 队列的一个运行实例如下： 12

13

记录成绩（涂改无效） 合格□ 不合格□ 【五、实验结果分析】 1、分析数制转换时后进先出的特点； 2、分析如果将数转换为二进制， conversion函数的修改； 3、分析如果没有初始化栈的操作时程序的运行结果； 3、写出自己的心得体会。

14