栈和队列的实验结果分析 数据结构实验报告二

下面是好好范文网小编收集整理的栈和队列的实验结果分析 数据结构实验报告二，仅供参考，欢迎大家阅读！

一、实验目的

1、掌握栈的结构特性及其入栈，出栈操作；

2、掌握队列的结构特性及其入队、出队的操作，掌握循环队列的特点及其操作。

二、实验内容和要求

1、阅读下面程序，将函数Push和函数Pop补充完整。要求输入元素序列1 2 3 4 5 e，运行结果如下所示。

#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10  /*存储空间初始分配量*/#define STACKINCREMENT 5  /*存储空间分配增量*/typedefint ElemType;/*定义元素的类型*/typedefstruct{   ElemType *base;   ElemType *top;int stacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack *S);/*构造空栈*/SqStack *S,ElemType e);/*入栈*/SqStack *S,ElemType *e);/*出栈*/intCreateStack(SqStack *S);/*创建栈*/voidPrintStack(SqStack *S);/*出栈并输出栈中元素*/intInitStack(SqStack *S){   S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemTypeS->base)return ERROR;   S->top=S->base;   S->stacksize=STACK_INT_SIZE;return OK;}/*InitStack*/SqStack *S,ElemType eS->topS->base)==S->stacksize){       S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemTypeS->basereturn ERROR;       S->top=S->base+S->stacksize;       S->stacksize=S->stacksize+STACKINCREMENTS->top=e;   S->top++;return OK;}/*Push*/SqStack *S,ElemType *eS->top==S->base)return ERROR       S->tope=*S->top;return OK/*Pop*/intCreateStack(SqStack *S eInitStack(S))printf("Init Success!n"printf("Init Fail!n");return ERROR;}printf("input data:(Terminated by inputing a character)n"eS,e);return OK;}/*CreateStack*/voidPrintStack(SqStack *S){   ElemType eS,&e))printfe/*Pop_and_Print*/   SqStack ss;printf("n1-createStackn");CreateStack(&ss);printf("n2-Pop&Printn");PrintStack(&ss);return
算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么特性？
  先进后出（后进先出）
2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。
实现代码
#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define STACK_INT_SIZE 10  /*存储空间初始分配量*/#define STACKINCREMENT 5  /*存储空间分配增量*/typedefint ElemType;/*定义元素的类型*/typedefstruct{    ElemType *base;    ElemType *top;int stacksize;/*当前已分配的存储空间*/}SqStack;intInitStack(SqStack *S);/*构造空栈*/SqStack *S,ElemType e);/*入栈*/SqStack *S,ElemType *e);/*出栈*/intCreateStack(SqStack *S);/*创建栈*/voidPrintStack(SqStack *S);/*出栈并输出栈中元素*/intInitStack(SqStack *S){    S->base=(ElemType *)malloc(STACK_INT_SIZE *sizeof(ElemTypeS->base)return ERROR;    S->top=S->base;    S->stacksize=STACK_INT_SIZE;return OK;}/*InitStack*/SqStack *S,ElemType eS->topS->base)==S->stacksize){        S->base=(ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemTypeS->basereturn ERROR;        S->top=S->base+S->stacksize;        S->stacksize=S->stacksize+STACKINCREMENTS->top=e;    S->top++;return OK;}/*Push*/SqStack *S,ElemType *eS->top==S->base)return ERROR        S->tope=*S->top;return OK/*Pop*/intCreateStack(SqStack *S eInitStack(S))printf("Init Success!n"printf("Init Fail!n");return ERROR;}printf("input data:(Terminated by inputing a character)n"eS,e);return OK;}/*CreateStack*/voidPrintStack(SqStack *S){    ElemType eS,&e))printfe/*Pop_and_Print*/intIsEmpty(SqStack *SS->top==S->base)return OK;elsereturn ERRORConversion(int N){    SqStack S;int x;InitStack(&SN        x=NS,x);        N=NIsEmpty(&SS,&x);printfx nn);Conversion(n);return
验证
  正确
3、阅读并运行程序，并分析程序功能。
#include<stdio.h>#include<malloc.h>#include<string.h>#define M 20#define  elemtype  chartypedefstruct{    elemtype stack[M top;}stacknodestacknode *ststacknode *st,elemtype xstacknode *ststacknode *st){    st->topstacknode *st,elemtype xst->top==M)printf("the stack is overflow!n"        st->top=st->top        st->stack[st->top]=xstacknode *stst->top  st->topprintf(“Stack is Empty!n” s[M i;    stacknode *sp;printf("create a empty stack!n");    sp=malloc(sizeof(stacknodesp);printf("input a expression:n"sii<strlen(s);is[isp,s[is[ispsp->topprintf("'('match')'!n"printf("'('not match')'!n");return
输入：2+((c-d)*6-(f-7)*a)/6
运行结果：’(‘match’)’!
输入：a-((c-d)*6-(s/3-x)/2
运行结果：’(‘not match’)’!
程序的基本功能：判断给定表达式中所包含的括号是否正确配对出现
4、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。
  实现代码：
#include<bits/stdc++.h>#include<conio.h>#define TRUE 1#define FALSE 0#define QelemType inttypedefstruct Node{    QelemType data;struct Node *next;} Node,*LinkQNode;typedefstruct{    LinkQNode rear;} LinkQueue;voidInitLinkQueue(LinkQueue &Q){    Q.rear=(LinkQNode)malloc(sizeof(Node    Q.rear->next=Q.rearIsLQEmpty(LinkQueue &QQ.rear->next==Q.rear)return TRUE;elsereturn FALSEEnLinkQueue(LinkQueue &Q,QelemType x){    LinkQNode NewNode;    NewNode=(LinkQNode)malloc(sizeof(LinkQNodeNewNode        NewNode->data=x;        NewNode->next=Q.rear->next;        Q.rear->next=NewNode;        Q.rear=NewNode;return TRUEreturn FALSEDeLinkQueue(LinkQueue &Q,QelemType *x){    LinkQNode pQ.rear->next==Q.rear)return FALSE;    p=Q.rear->next->next;    Q.rear->next->next=p->nextQ.rear==p)        Q.rear=Q.rear->next;*x=p->datap);return TRUE t;char a;    QelemType tt;    LinkQueue Q;InitLinkQueue(QIsLQEmpty(Q))printf("该队列目前为空!n"printf("该队列不为空!n");printf("输入入队列的元素个数："t i i<=t; i        QelemType ys;printf("n输入第%d个入列元素：",iysEnLinkQueue(Q,ys))printf("元素%d成功入列!n",ysprintf("n输入字母‘e’开始出列n");getcharagetcharaprintf("n输入字母'e'继续出列n");continueDeLinkQueue(Q,&tt))printf("元素%d成功出列n",ttIsLQEmpty(Qprintf("该队列目前为空!n"printf("该队列不为空!n");printf("n输入字母'e'继续出列n"return