栈和队列

这个作业属于哪个班级 数据结构--网络2011/2012
这个作业的地址 DS博客作业02--栈和队列
这个作业的目标 学习栈和队列的结构设计及运算操作
姓名

0.PTA得分截图

栈和队列

1.本周学习总结(0-5分)

1.1 栈

画一个栈的图形,介绍如下内容。

  • 顺序栈的结构、操作函数

顺序栈的存储结构

栈和队列

顺序栈的进栈操作

栈和队列

/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
    if(S->top == MAXSIZE -1) /* 栈满 */
    {
        return ERROR;
    }
    S->top++;				/* 栈顶指针增加一 */
    S->data[S->top]=e;  /* 将新插入元素赋值给栈顶空间 */
    return OK;
}

顺序栈的出栈操作

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(SqStack *S,SElemType *e)
{
    if(S->top==-1)
        return ERROR;
    *e=S->data[S->top];	/* 将要删除的栈顶元素赋值给e */
    S->top--;				/* 栈顶指针减一 */
    return OK;
}

获取顺序栈的栈顶元素

/* 若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR */
Status GetTop(SqStack S,SElemType *e)
{
    if (S.top==-1)
        return ERROR;
    else
        *e=S.data[S.top];
    return OK;
}

  • 链栈的结构、操作函数

链栈的存储结构

栈和队列

链栈的进栈操作

栈和队列

/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
    LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
    s->data=e;
    s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继,见图中① */
    S->top=s;         /* 将新的结点s赋值给栈顶指针,见图中② */
    S->count++;
    return OK;
}

链栈的出栈操作

栈和队列

/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
    LinkStackPtr p;
    if(StackEmpty(*S))
        return ERROR;
    *e=S->top->data;
    p=S->top;					/* 将栈顶结点赋值给p,见图中① */
    S->top=S->top->next;    /* 使得栈顶指针下移一位,指向后一结点,见图中② */
    free(p);                    /* 释放结点p */
    S->count--;
    return OK;
}

链栈的初始化操作

/*  构造一个空栈S */
Status InitStack(LinkStack *S)
{
    S->top = (LinkStackPtr)malloc(sizeof(StackNode));
    if(!S->top)
        return ERROR;
    S->top=NULL;
    S->count=0;
    return OK;
}

链栈的遍历操作

Status StackTraverse(LinkStack S)
{
    LinkStackPtr p;
    p=S.top;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

Status visit(SElemType c)
{
    printf("%d ",c);
    return OK;
}

判断栈是否为空

/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
Status StackEmpty(LinkStack S)
{
    if (S.count==0)
        return TRUE;
    else
        return FALSE;
}

1.3 队列

  • 顺序队列的结构、操作函数

顺序队列的存储结构

栈和队列

/* QElemType类型根据实际情况而定,这里假设为int */
typedef int QElemType;

/* 循环队列的顺序存储结构 */
typedef struct
{
	QElemType data[MAXSIZE];
	int front;    	/* 头指针 */
	int rear;		/* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}SqQueue;

顺序队列的入队操作

/* 若队列未满,则插入元素e为Q新的队尾元素 */
Status EnQueue(SqQueue *Q,QElemType e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
								/* 若到最后则转到数组头部 */
	return  OK;
}

顺序队列的出队操作

/* 若队列不空,则删除Q中队头元素,用e返回其值 */
Status DeQueue(SqQueue *Q,QElemType *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置, */
									/* 若到最后则转到数组头部 */
	return  OK;
}

判断顺序队列是否为空

Status QueueEmpty(SqQueue Q)
{
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}
  • 环形队列的结构、操作函数
  • 链队列的结构、操作函数

链队列的存储结构

栈和队列

#include "stdio.h"

/* QElemType类型根据实际情况而定,这里假设为int */
typedef int QElemType;

typedef struct QNode	/* 结点结构 */
{
    QElemType data;
    struct QNode *next;
} QNode,*QueuePtr;

typedef struct			/* 队列的链表结构 */
{
    QueuePtr front,rear; /* 队头、队尾指针 */
} LinkQueue;

int main()
{
    return 0;
}

链队列的初始化

/* 构造一个空队列Q */
Status InitQueue(LinkQueue *Q)
{
	Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
	if(!Q->front)
		exit(OVERFLOW);
	Q->front->next=NULL;
	return OK;
}

链队列的入队操作

栈和队列

/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{
    QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
    if(!s) /* 存储分配失败 */
        exit(OVERFLOW);
    s->data=e;
    s->next=NULL;
    Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继,见图中① */
    Q->rear=s;		/* 把当前的s设置为队尾结点,rear指向s,见图中② */
    return OK;
}

链队列的出队

栈和队列

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继 */
	if(Q->rear==p)		/* 若队头就是队尾,则删除后将rear指向头结点 */
		Q->rear=Q->front;
	free(p);
	return OK;
}

  • 队列应用,要有具体代码操作。

2.PTA实验作业(4分)

2.1 符号配对

代码

2.1.1 解题思路及伪代码

定义一个字符串str用来存储表达式
输入表达式
定义一个字符栈st来存储左符号 
定义变量flag来判断左右符号是否配对 
for i=0 to str[i]                                //遍历字符串
    if  遇到左符号 do
            左符号入栈                           //如果遇到左符号,将左符号入栈 
    if  遇到右符号 do  
	    if 栈空 do
		输出no 
      结束程序                         //如果栈为空,说明没有左符号与右符号配对
     if 栈不空 do
	取栈顶
     if 左右符号配对  do
        flag=1;
     if 左右符号不匹配  do
        输出栈定符号;
        输出no;
       结束程序;                   //如果左右符号不匹配,直接输出然后退出程序 
     出栈                  
end for
if 栈空&&flag=1 do            
      输出yes
else
      取栈顶
      出栈 
      输出栈中无法配对到右符号的左符号 
      输出no 

2.1.2 总结解题所用的知识点

栈的结构体定义
stack的函数调用
flag的标记作用

2.2 银行业务队列简单模拟

代码

2.2.1 解题思路及伪代码

定义Q1存储a柜台的元素,定义Q2存储b柜台的元素,定义Q3存储存储最终表达式
int a=1    \\做Q3顺序标记
while Q1.front != Q1.rear || Q2.front != Q2.rear    \\a柜台入Q3操作
     if a==1||a==2 do
                Q3.base[Q3.rear] = Q1.base[Q1.front];
                Q3.rear = (Q3.rear + 1) % MAXSIZE;
                Q1.front = (Q1.front + 1) % MAXSIZE;
     else                                             \\b柜台入Q3操作
         if Q2.front != Q2.rear
                Q3.base[Q3.rear] = Q2.base[Q2.front];
                Q3.rear = (Q3.rear + 1) % MAXSIZE;
                Q2.front = (Q2.front + 1) % MAXSIZE;
     a++
     if a>3 do                                         \\调整a,b柜台在Q3的排序
     a=1
for  i = 0  i to s-1
Q3元素的表达

2.2.2 总结解题所用的知识点

设a=1当a>3时a=1,用于调整Q3中Q1,Q2的位置

3.阅读代码(0--1分)

1份优秀代码,理解代码功能,并讲出你所选代码优点及可以学习地方。主要找以下类型代码:

注意:不能选教师布置在PTA的题目。完成内容如下。

3.1 题目及解题代码

可截图,或复制代码,需要用代码符号渲染。

3.2 该题的设计思路及伪代码

链表题目,请用图形方式展示解决方法。同时分析该题的算法时间复杂度和空间复杂度

3.3 分析该题目解题优势及难点。

上一篇:3-12(队列的结束以及树的开始)


下一篇:6个可以隐藏运行bat,浏览器等程序的方法