| 这个作业属于哪个班级 | 数据结构--网络2012 |
|---|---|
| 这个作业的地址 | DS博客作业02--栈和队列 |
| 这个作业的目标 | 学习栈和队列的结构设计及运算操作 |
| 姓名 | 李兴果 |
0.PTA得分截图
1.本周学习总结（0-5分）
1.1 栈
画一个栈的图形，介绍如下内容：
（1）顺序栈的结构、操作函数
顺序栈:
栈空条件：s->top==-1;
栈满条件：s->top==MaxSize-1;
进栈操作：s->top++;s->data[s->top]=e;
出栈操作：e=s->data[s->top];s->top--;
共享栈:
栈空条件：top1==-1;top2==MaxSize;
栈满条件：top1==top2-1;
进栈操作：top++;data[top1]=x; top2--;data[top2]=x;
出栈操作：x=data[top1];top1--; x=data[top2];top2++;
数据类型：
typedef struct
{
ElemType data[MaxSize];//存放栈中元素
int top;//栈顶指针，存放栈顶元素下标
}SqStack;
初始化栈：
void InitStack(SqStack*&s)
{
s = (SqStack*)malloc(sizeof(SqStack));//分配顺序栈空间，首地址存放在s中
s->top = -1;//栈顶置-1处
}
销毁栈：
void DestoryStack(SqStack*&s)
{
free(s);
}
判断是否为空：
void StackEmpty(SqStack*s)
{
return (s->top == -1);
}
进栈：
bool Push(SqStack*& s, ElemType e)
{
if (s->top == MaxSize - 1)//栈满
return false;
s->top++;//向上移动一个位置
s->data[s->top] = e;//放在顶指针处
return true;
}
出栈：
bool Pop(SqStack*& s, ElemType e)
{
if (s->top == - 1)//栈空
return false;
e=s->data[s->top] ;//取栈顶元素
s->top--;//移动
return true;
}
取栈顶元素:
bool GetTop(SqStack*& s, ElemType e)
{
if (s->top == - 1)//栈空
return false;
e=s->data[s->top] ;//取栈顶元素
return true;
}
（2）链栈的结构、操作函数
条件：
栈空条件：s->next==NULL;
栈满条件：无栈满
进栈操作：p->next=e;
p->next=s->next;//p结点插入作为首节点
s->next=p;
出栈操作： p=s->next;//p指向首结点
e=p->data;//取首结点值
s->next=p->next;//删除首结点
free(p);
类型：
typedef struct linknode
{
Elem Type data;//数据域
struct linknode;//指针域
}LinkStNode;//结点类型
初始化栈:
void IniStack(LiStack &s)
{
s=new LiNode;//新建头结点
s->next=NULL;//初始化为空
}
销毁链栈:
void DestroyStack(LiStack *&s)
{
LiStack node;
while(s!=NULL)
{
node=s;
s=s->next;//遍历
delete node;
}
}
判断栈是否为空:
bool StackEmpty(LiStack* s)
{
return (s->next==NULL);
}
进栈:
void Push(LiStack*& s, ElemType *e)
{
LiStack p;
p=new LiNode;//新建结点
p->next=e;
p->next=s->next;//p结点插入作为首节点
s->next=p;
}
出栈：
bool Pop（LiStack*& s, ElemType& e）
{
LiStack p;
if(s->next==NULL)
return false;
p=s->next;//p指向首结点
e=p->data;//取首结点值
s->next=p->next;//删除首结点
free(p);
return true;
}
取栈顶元素:
bool GetTop（LiStack*& s, ElemType& e）
{
if(s->next==NULL)
return false;
e=s->next->data;
return false;
}
1.2 栈的应用
表达式
- 中缀表达式
例如：1+3*3 最常用的表达式 - 后缀表达式
例如：1+23的后缀表达式为 123+ 没有括号 已经考虑了运算符号的优先级 越放在前面的运算符越优先执行 - 前缀表达式
例如： 1+23的前缀 +123
（1）中缀转后缀表达式
转换时需要从左到右扫描算数表达式，遇到操作数直接存放到后缀表达式
1.优先级比栈顶运算符高入栈
2.低或相等，一直出栈到栈顶为空或者更高，写入后缀表达式
读入数时,将其放入到输出中,操作符不立即输出,将其放入栈中
如果我们见到一个右括号,那么我们就从栈中弹出栈元素直至遇到一个左括号,左右括号都只被弹出而不输出
如果见到任何其他的符号+ * (,那么从栈中弹出栈元素,直至发现优先级更低的元素为止, 但是有一个例外: 除非是在处理一个)的时候,否则绝不从栈中移除(,+的优先级最低,(的优先级最高,当从栈中弹出元素的工作完成后,我们再将其操作符压入栈中。
最后,如果读到输入的末尾,我们将栈元素弹出直至该栈变成空栈,将符号写到输出中
（2）举例：
输入为a + b * c + (d * e + f)*g
读a,输出
读到+,入栈
到b，输出
到*，因为*优先级比+高，将至压入栈中
到+，因为*高于+，弹出*，栈中下一个元素+ 与当前+一样，输出栈中这个+，再将刚刚的+入栈
读到（，优先级最高，入栈
读到*，因为只有遇到）时才会弹出，所以*继续压入栈中
读到e，输出
读到+，弹出*并输出，+压入
到f输出
读到）后，将到（之间元素全部输出
到* 压入
到g输出
到末尾后，栈中还剩* + 直接输出
1.3 队列
画一个队列的图形，介绍如下内容
（1）顺序队列的结构、操作函数
条件
队空条件：q->front==q->rear;
队满条件：q->raer=MaxSize-1;
进队操作：q->rear++;q->data[q->rear]=e;
出队操作：q->front++;e=q->data[q->front];
数据类型:
typedef struct
{
Elem Type data[MaxSize];
int front,rear;//头尾
}SqQueue;
初始化队列:
void InitQueue(SqQueue &q)
( q=new Queue;
q->front=q->rear=-1;//初始位置为-1
}
销毁队列:
void Destory(SqQueue &q)
{
delete q;
}
判断队列是否为空:
bool QueueEmpty（SqQueue q）
{
return （q->front==q->rear);
}
进队列:
bool enQueue(SqQueue &q,ElemType e)
{
//此时下标从-1开始，先增一再入值
if(q->rear+1==MaxSize)
return false;
q->rear=q->rear+1;//队尾加1
q->data[q->rear]=e;//rear插入元素e
return true;
}
出队列:
booldenQueue(SqQueue &q,ElemType e)
{
if(q->front==q->rear)
return false;
q->front=q->front+1;
e=q->data[q->data];
return true;
（2）环形队列的结构、操作函数
初始化:
void InitQueue(SqQueue &q)
( q=new Queue;
q->front=q->rear=0;//开始时在同一位置当存入数时。front指向数的前一个位置，rear在尾部位置
}
销毁队列:
void Destory(SqQueue &q)
{
delete q;
}
判断队列是否为空:
bool QueueEmpty（SqQueue q）
{
return （q->front==q->rear);
}
进队列:
bool enQueue(SqQueue &q,ElemType e)
{
if((q->rear+1)%MaxSize==q->front)//队满条件
return false;
q->rear=(q->rear+1)%MaxSize;//循环增一
q->]data[q->rear]=e;//存入
return true;
}
出队列:
booldenQueue(SqQueue &q,ElemType e)
{
if(q->front==q->rear)//空队时
return false;
e=q->data[q->front];//取值
q->front=(q->front+1)%MaxSize;//循环增一
return true;
（3）链队列的结构、操作函数
条件:
队空条件：q->rear==NULL;
队满条件：不考虑
进队操作：q->data=e;p->rear->data=q;p->next=q;
出队操作：p->front=p->front->next;e=q->data;
数据类型：
typedef struct
{
QNode *front;//头指针
QNode *rear;//尾指针
}LinkQueue;
typedef struct qnode
{
Elem data；//数据元素
struct qnode *next;
}QNode;
链队初始化:
Status InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new QNode;
if(!Q.front)
exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
或者
void InitQueue(LinkQuNode *&q)
{
q=(LinkQueNode *)malloc(sizeof(LinkQueNode));//创建链队结点
q->front=q->reaar=NULL;
}
判断链队是否为空:
Status QueueEmpty(LinkQueue Q)
{
return (Q.front==Q.rear)//队空
}
求链队队头元素:
Status GetQueue (LinkQueue Q，QElemType &e)
{
if(Q.front==Q.rear)
retuen ERROR;
e=Q.front->next->data;//取元素
return OK;
}
链队列入队:
Status EnQueue (LinkQueue &Q，QElemType e)
{
p=new QNode;//新建结点
if(!p)
exit(OVERFLOW)
P->data=e;
p->next=NULL;
Q.rear->next=p;//尾指针指向p
Q.rear=p;
return OK;
}
链队出队:
Status DeQueue (LinkQueue &Q，QElemType e)
{
if(Q.front==Q.rear)//队空
return ERROR;
p=Q.front->next;
e=p->data;//取队头元素
Q.front->next=p->next;//结点指向p下一个
if(Q.rear==p)//最后一个元素被删除，改队尾
Q.rear=Q.front;
delete p;//删除结点p
return OK;
}
（4）队列应用，要有具体代码操作。
- 求解报数问题
1.问题描述：
n人站成一排，数1 2 1 2...数1的同学出列，2
的同学靠右直到第n个人出列
2.数据组织：
使用环形队列
3.设计运算算法：
先将n个人编号进队，反复执行以下操作，直到队列为空
出队一个元素 输出其编号
若队列不为空，再出队一个元素，将刚出列的元素入队
void number(int n)
{
int i;
ElemType e;
SqQueue* q;
InitQueue(q);//初始化
for (i = 1; i <= n; i++)
enQueue(q, i);//进队
while (!QueueEmpty(q))
{
deQueue(q, e);//出
if (!!QueueEmpty(q))
{
deQueue(q, e);
enQueue(q, e);//将刚出的进队
}
}
DestoryQueue(q);//销毁
}
(2)求解迷宫问题
使用链队解决
1.数据组织
//使用一个顺序队qu保存走过的方块
typedef struct
{
int i, j;//方块的位置
int pre;//本路径中上一方块在队列中的下标
}Box;
typedef struct
{
Box data[MaxSize];
int front, rear;//队头队尾指针
}QuType;
// 此处qu不是环形队列，找出口时需要利用队列中所有方块找一条迷宫路径，
2.设计运算算法
搜索路径(xi,yi)->(xe,ye)从入口进队，队不为空时循环，出队一个方块，找其相邻方块，使其进队，将他们的pre都置为front
typedef struct
{
int i, j; //方块的位置
int pre; //本路径中上一方块在队列中的下标
} Box; //方块类型
typedef struct
{
Box data[MaxSize];
int front, rear; //队头指针和队尾指针
} QuType; //定义顺序队类型
void print(QuType qu, int front) //从队列qu中输出路径
{
int k = front, j, ns = 0;
printf("\n");
do //反向找到最短路径,将该路径上的方块的pre成员设置成-1
{
j = k;
k = qu.data[k].pre;
qu.data[j].pre = -1;
} while (k != 0);
printf("迷宫路径如下:\n");
k = 0;
while (k <= front) //正向搜索到pre为-1的方块,即构成正向的路径
{
if (qu.data[k].pre == -1)
{
ns++;
printf("\t(%d,%d)", qu.data[k].i, qu.data[k].j);
if (ns % 5 == 0)
printf("\n"); //每输出每5个方块后换一行
}
k++;
}
printf("\n");
}
int mgpath(int xi, int yi, int xe, int ye) //搜索路径为:(xi,yi)->(xe,ye)
{
int i, j, find = 0, di;
QuType qu; //定义顺序队
qu.front = qu.rear = -1;
qu.rear++;
qu.data[qu.rear].i = xi;
qu.data[qu.rear].j = yi; //(xi,yi)进队
qu.data[qu.rear].pre = -1;
mg[xi][yi] = -1; //将其赋值-1,以避免回过来重复搜索
while (qu.front != qu.rear && !find) //队列不为空且未找到路径时循环
{
qu.front++; //出队,由于不是环形队列，该出队元素仍在队列中
i = qu.data[qu.front].i;
j = qu.data[qu.front].j;
if (i == xe && j == ye) //找到了出口,输出路径
{
find = 1;
print(qu, qu.front); //调用print函数输出路径
return(1); //找到一条路径时返回1
}
for (di = 0; di < 4; di++) //循环扫描每个方位,把每个可走的方块插入队列中
{
switch (di)
{
case 0:
i = qu.data[qu.front].i - 1;
j = qu.data[qu.front].j;
break;
case 1:
i = qu.data[qu.front].i;
j = qu.data[qu.front].j + 1;
break;
case 2:
i = qu.data[qu.front].i + 1;
j = qu.data[qu.front].j;
break;
case 3:
i = qu.data[qu.front].i, j = qu.data[qu.front].j - 1;
break;
}
if (mg[i][j] == 0)
{
qu.rear++; //将该相邻方块插入到队列中
qu.data[qu.rear].i = i;
qu.data[qu.rear].j = j;
qu.data[qu.rear].pre = qu.front; //指向路径中上一个方块的下标
mg[i][j] = -1; //将其赋值-1,以避免回过来重复搜索
}
}
}
return(0); //未找到一条路径时返回1
}
2.PTA实验作业（4分）
#include<iostream>
#include<cstdlib>
using namespace std;
//#define ERROR NULL
const int MaxSize=109;
typedef char ElementType;
struct Stack{
ElementType Symbol[MaxSize];
int Top;
};
Stack* Create();
bool Push(Stack* S,ElementType X);
ElementType Pop(Stack* S);
ElementType getTop(Stack* S);///获取栈顶元素
int main()
{
Stack* S=Create();
char str[1000],stacktop;
int i,flag=0,flag2=0,flag_i=0;
while(true)
{
cin.getline(str,1000); ///用gets发生编译错误
if(str[0]=='.') break;///一行一行地读取，遇到'.'时结束
for(i=0;str[i]!='\0';i++)
{
flag_i=0;
/** 遇到左符号，入栈*/
if(str[i]=='('||str[i]=='['||str[i]=='{')
Push(S,str[i]);
if(str[i]=='/'&&str[i+1]=='*')
{
flag_i=1;///遇到/*的标志
Push(S,str[i]);
Push(S,str[i+1]);
/// i++; 若在此处使i++，则下面的if语句中i值被改变
}
/** 遇到右符号，与栈顶符号配对*/
if(str[i]==')')
{
if(S->Top==-1)///栈为空，则当前右符号缺少左符号，结束循环
{
cout<<"NO"<<endl;
cout<<"?-"<<str[i]<<endl;
flag=1;///栈空时判断是否YES的标志
flag2=1;///跳出while循环的标志
break;
}
stacktop=getTop(S);
if(stacktop!='(')///栈顶元素与当前右符号不匹配，结束循环
{
flag2=1;
break;
}
else
Pop(S); ///匹配则出栈
}
if(str[i]==']')
{
if(S->Top==-1)
{
cout<<"NO"<<endl;
cout<<"?-"<<str[i]<<endl;
flag=1;
flag2=1;
break;
}
stacktop=getTop(S);
if(stacktop!='[')
{
flag2=1;
break;
}
else
Pop(S);
}
if(str[i]=='}')
{
if(S->Top==-1)
{
cout<<"NO"<<endl;
cout<<"?-"<<str[i]<<endl;
flag=1;
flag2=1;
break;
}
stacktop=getTop(S);
if(stacktop!='{')
{
flag2=1;
break;
}
else
Pop(S);
}
if(str[i]=='*'&&str[i+1]=='/')
{
if(S->Top==-1)
{
cout<<"NO"<<endl;
cout<<"?-*/"<<endl;
flag=1;flag2=1;
break;
}
stacktop=getTop(S);
if(stacktop!='*')
{
flag2=1;
break;
}
else
{
Pop(S);
Pop(S);
}
i++;/// */比较完毕后i同样++
}
if(flag_i)
i++;/// 缺少该语句将使 /*/ 被判定为配对成功
}
if(flag2)
break;
}
if(S->Top!=-1)///栈不空，则栈顶元素缺少右符号
{
cout<<"NO"<<endl; ///YES NO 注意大写
if(getTop(S)=='*')
cout<<"/*-?"<<endl;
else
cout<<Pop(S)<<"-?"<<endl;
}
else if(!flag)///栈空且flag==0，全部配对成功
cout<<"YES"<<endl;
system("pause");
delete S;
return 0;
}
Stack* Create()
{
Stack* S=new Stack;
S->Top=-1;
return S;
}
bool Push(Stack* S,ElementType X)
{
if(S->Top==MaxSize-1)
return false;
S->Symbol[++(S->Top)]=X;
return true;
}
ElementType Pop(Stack* S)
{
// if(S->Top==-1)
// return ERROR;
return S->Symbol[(S->Top)--];
}
ElementType getTop(Stack* S)
{
ElementType top=Pop(S);
Push(S,top);
return top;
}
2.1 符号配对
2.1.1 解题思路及伪代码
从头遍历：
1.遇到左符号：入栈；
2.遇到右符号：若此时栈空则表示当前右符号缺少与之匹配的左符号，跳出循环；栈不空，则与栈顶元素进行配对，若配对成功则栈顶符号出栈，否则跳出循环。
遍历结束后，若栈空（除上述栈空的情况外）则说明全部符号均配对成功
2.1.2 总结解题所用的知识点
注意第一个用例中/*/的判断，并且注意右字符与栈内字符不匹配时的情况。 右字符与栈内字符不匹配时有两种：栈内为空，则此右字符缺失左字符；栈不为空，则栈内左字符缺失右字符；
2.2 银行业务队列简单模拟
2.2.1 解题思路及伪代码
解题思路：把偶数的数字存到B窗口，将奇数的数字存到A窗口，是先进先出，采用队列，将偶数的放在B队列，将奇数的放在A队列
然后每输出两个A队列中的元素
再输出一个B队列中的元素；
还有一个点就是，最后是A队列中的元素结尾还是B队列中的元素结尾，主要是控制空格的问题
伪代码：
创建结构体
data[1002]用于存队列的数据；
定义 rear来记录从尾部插入了多少个元素；
front计数队头，方便取出队头的元素；
实现队列的push用法；传入类型为 queue 的指针 q；传入要入队的数tmp；
q->tail ++/每入队一个元素，尾部计数器+1；
将元素入队；
函数pop(queue *q) //取出队列的数字，从前端取出；此时要利用head记数
返回队头的元素
void init(queue *q) 初始化
将尾和头记数均初始化为-1
notEmpty(queue *q)判断队列是否为空
如果尾和头的记数一样，则队列为空
用countA记录入A队列的个数；用countB 记录入B队列的个数
queue A定义
queue B定义
初始化A队列，并要用引用符号
初始化B队列，并用引用符号
输入m，
push(&b,c)如果是偶数，则进b队列
countB相应+1
否则A
分情况，注意最后到底是A队列的数结尾还是B队列的数结尾
if countA大于两倍countB，是A队列的元素结尾，则A最后一个元素后面不能加空格
当A队列不空或者B队列不空时；
ifA 不为空
输出
ifB 不为空
输出
countA小于等于两倍countB，是B队列的元素结尾，则B最后一个元素后面不能加空格
当A队列不空或者B队列不空时
ifA 不为空
输出
输出一个b队列的元素，注意b队列最后一个元素的后面不能加空格
3.1迷宫问题
求出出口到入口的路径
typedef struct
{
int i,j;
int pre; //本路径中上一方块在队列中的下标
} Box; //方块类型
typedef struct
{
Box data[MaxSize];
int front,rear;
} QuType;
void print(QuType qu,int front) //从队列qu中输出路径
{
int k=front,j,ns=0;
printf("\n");
do //反向找到最短路径,将该路径上的方块的pre成员设置成-1
{
j=k;
k=qu.data[k].pre;
qu.data[j].pre=-1;
}
while (k!=0);
printf("迷宫路径如下:\n");
k=0;
while (k<=front) //正向搜索到pre为-1的方块,即构成正向的路径
{
if (qu.data[k].pre==-1)
{
ns++;
printf("\t(%d,%d)",qu.data[k].i,qu.data[k].j);
if (ns%5==0)
printf("\n");
}
k++;
}
printf("\n");
}
int mgpath(int xi,int yi,int xe,int ye) //搜索路径为:(xi,yi)->(xe,ye)
{
int i,j,find=0,di;
QuType qu;
qu.front=qu.rear=-1;
qu.rear++;
qu.data[qu.rear].i=xi;
qu.data[qu.rear].j=yi; //(xi,yi)进队
qu.data[qu.rear].pre=-1;
mg[xi][yi]=-1; //将其赋值-1,以避免回过来重复搜索
while (qu.front!=qu.rear && !find)
{
qu.front++;
i=qu.data[qu.front].i;
j=qu.data[qu.front].j;
if (i==xe && j==ye) //找到了出口,输出路径
{
find=1;
print(qu,qu.front);
return(1); //找到一条路径时返回1
}
for (di=0; di<4; di++) //循环扫描每个方位,把每个可走的方块插入队列中
{
switch(di)
{
case 0:
i=qu.data[qu.front].i-1;
j=qu.data[qu.front].j;
break;
case 1:
i=qu.data[qu.front].i;
j=qu.data[qu.front].j+1;
break;
case 2:
i=qu.data[qu.front].i+1;
j=qu.data[qu.front].j;
break;
case 3:
i=qu.data[qu.front].i, j=qu.data[qu.front].j-1;
break;
}
if (mg[i][j]==0)
{
qu.rear++; //将该相邻方块插入到队列中
qu.data[qu.rear].i=i;
qu.data[qu.rear].j=j;
qu.data[qu.rear].pre=qu.front; //指向路径中上一个方块的下标
mg[i][j]=-1; //将其赋值-1,以避免回过来重复搜索
}
}
}
return(0); //未找到一条路径时返回1
}
int main()
{
mgpath(1,1,M,N);
return 0;
}
3.2 该题的设计思路及伪代码
思路：从上一个节点开始，任意找下一个能走的点，当找不到能走的点时，退回上一个点寻找是否有其他方向的点。
使用栈存储当前路径。后进先出，方便回退到上一个点
typedef struct
{
定义 i,j//方块的位置
pre//本路径中上一方块在队列中的下标
} Box;//方块类型
Box data[MaxSize];
int front,rear; //队头指针和队尾指针
//定义顺序队类型
print(QuType qu,int front) //从队列qu中输出路径
//反向找到最短路径,将该路径上的方块的pre成员设置成-1
while (k!=0);
printf("迷宫路径如下:\n");
while (k<=front) //正向搜索到pre为-1的方块,即构成正向的路径
//每输出每5个方块后换一行
mgpath(int xi,int yi,int xe,int ye)搜索路径为:(xi,yi)->(xe,ye)
//定义顺序队
//(xi,yi)进队
//将其赋值-1,以避免回过来重复搜索
while (qu.front!=qu.rear && !find) //队列不为空且未找到路径时循环
//出队,由于不是环形队列，该出队元素仍在队列中
//找到了出口,输出路径
print(qu,qu.front)调用print函数输出路径
return(1)找到一条路径时返回1
for (di=0; di<4; di++)扫描每个方位,把每个可走的方块插入队列中
if (mg[i][j]==0)
qu.rear++将该相邻方块插入到队列中
qu.data[qu.rear].i=i;
qu.data[qu.rear].j=j;
qu.data[qu.rear].pre=qu.front指向路径中上一个方块的下标
3.3 分析该题目解题优势及难点。
总结算法就是：创建一个空栈，首先将入口位置进栈。当栈不空时循环：获取栈顶元素，寻找下一个可走的相邻方块，如果找不到可走的相邻方块，说明当前位置是死胡同，进行回溯（就是讲当前位置出栈，看前面的点是否还有别的出路）
使用栈来解决迷宫问题，虽然实现起来比较简单，但是它的路径并不是最短的，很可能会绕远，如果想走最短路径可以使用队列来做