[栈和队列](4)题集_续
第21到23题的前中缀表达式之间的关系，这跟我们之前接触到的表达式求值差不多，之前接触到的表达式求值就是求后缀表达式，这里主要用栈实现，后边接触到树以后，可以更加直观的了解他们，由于题目特殊，具体请看补充笔记
24、试编写如下定义的递归函数的递归算法，并根据算法画出求g(5,2)时栈的变化过程。
出口条件是m=0,n的值必须大于或等于0。
#include<stdio.h>
#include<stdlib.h>
int g(int m, int n);
int main()
{
int m, n;
scanf_s("%d,%d", &m, &n);
if (m >= 0 && n >= 0)
{
printf("%d",g(m, n));
}
else
{
printf("输入参数不合法\n");
}
system("pause");
return 0;
}
int g(int m, int n)
{
int sum;
if (m == 0)
{
sum = 0;
}
else
{
sum = g(m - 1, 2 * n);
sum += n;
}
return sum;
}简单来说，就是计算2的m幂次幂累加，当m=5，n=2的时候，就是2^m+2^m-1.....2^1，每次递都会保存这次的场景，然后等待最内层归。
图解如下：
25、试写出求递归函数F(n)的递归算法，并消除递归：
算法如下，这里使用了双精度，因为有除号，则出口条件不能为0，否则计算机识别不出来。
double F(double n)
{
if (n < 0.9)
{
n = 1;
}
else
{
n = n * F(n / 2.0);
}
return (double)n;
}消除递归，改为非递归程序，用栈模拟，将每次的n存入栈中，然后再从栈顶开始相乘即可
int Fstack(int n)
{
int F[1000];
int base = 0;
int top = base;;
F[top] = n;
top++;
while (n > 0)
{
n = n / 2;
if(n==0)
{
n = n + 1;
break;
}
F[top] = n;
top++;
}
top--;
while (top >= base)
{
n = n * F[top];
printf("%d\n", n);
top--;
}
return n;
}26、求解平方根√A的迭代函数定义如下：
递归算法：
float Sqrt(float A, float p, float e)
{
if (abs(p * p - A) < e)
{
return p;
}
else
{
return Sqrt(A, (p + A / p) / 2, e);
}
}转换为非递归算法如下：
float Sqrt_iter(float A, float p, float e)
{
while (abs(p * p - A) >= e)
{
p = (p + A / p) / 2;
}
return p;
}其中A为被开方数，p为近似值，越接近结果算的越快，e为结果允许存在的误差，值越小，误差越小，值越大，误差越大
运算结果：
计算8的平方根，近似值为2，误差为1
27、已知Ackerman函数定义如下：
从图可见算法，递归算法如下：
int akm(int m, int n)
{
if (m == 0)
{
return n += 1;
}
else if (m != 0 && n == 0)
{
return akm(m - 1, 1);
}
else
{
return akm(m - 1, akm(m, n - 1));
}
}我们可以看做：
非递归算法如下：
#include<stdio.h>
#include<stdlib.h>
typedef struct askStack
{
int m, n;
int re, re1;
int stack;
}StackDef;
StackDef S[2000];
int ptop = -1;
int empty();
void Push(int m,int n);
void Pop();
int askStack(int m, int n);
int main()
{
printf("%d",askStack(3, 6));
system("pause");
return 0;
}
void Push(int m,int n)
{
ptop += 1;
S[ptop].m = m;
S[ptop].n = n;
S[ptop].re = 0;
S[ptop].re1 = 0;
S[ptop].stack = 0;
}
void Pop()
{
ptop -= 1;
}
int empty()
{
if (ptop < 0)
{
return 1;
}
else
{
return 0;
}
}
int askStack(int m, int n)
{
Push(m, n);
while (!empty())
{
if (S[ptop].m == 0)//递归停止条件，函数返回
{
S[ptop].re = S[ptop].n + 1;
Pop();
}
else if (S[ptop].stack == 0)//进入函数
{
if (S[ptop].n == 0)//进入递归点1
{
S[ptop].stack = 3;
Push(S[ptop].m - 1, 1);
}
else//进入递归点2
{
S[ptop].stack = 1;
Push(S[ptop].m, S[ptop].n - 1);
}
}
else if (S[ptop].stack == 1)//递归点2返回，执行预计2，进入递归点3
{
S[ptop].stack = 2;
S[ptop].re1 = S[ptop + 1].re;//语句2
Push(S[ptop].m - 1, S[ptop].re1);
}
else if (S[ptop].stack == 2||S[ptop].stack==3)//递归点1,3返回，执行语句1，3
{
S[ptop].re = S[ptop + 1].re;//预计1,3，函数返回
Pop();
}
}
return S[0].re;
}我们对照代码来给栈做个模拟。
当akm(2,1)的时候，栈如下变化：
m=2，n=1，进入递归点2：
首先压入m和n，进行初始化
m和n首次递归，都不为0，进入递归点2
压入新的值，递归层次+1
n为0，进入一层递归。
此时m和n都不为0，再次进入递归点2
n为0，进入递归点一
此时m为0，达到结束条件，更新此层返回值
递归点3返回
更新这层返回值，弹出
此时层次为1，递归点2返回，进入递归点3
将上层返回值作为参数n进入递归，达到结束条件
达到结束条件，弹出，递归点3返回
更新返回值
此时递归三返回
更新返回值后，继续弹出
递归点2返回，进入递归点3
修改递归层次，更新返回值1，进入递归点3
此时递归层次为0，m和n都不等于0,
更新递归层次，进入递归点2（三次）
此时n=0，进入递归点1
此时m=0，执行结束条件
更新返回值，弹出
递归点3返回
更新返回值，继续弹出
递归点2返回，进入递归点3
更新返回值1，进入新的递归
达到结束条件
此时m等于0，达到结束条件，更新返回值，退回上一函数内
此时递归点2返回，进入递归点3
更新层次和返回值1，继续进入新的递归
达到结束条件，更新返回值，退回
递归点3返回
此时递归点2返回，进入递归点3
更新层次，更新返回值1
达到结束条件，更新返回值，退回
此时递归点3返回
此时递归点2返回，进入递归点3
更新层次和返回值1。
进入后达到结束条件，然后返回两次递归三的值
最后返回5
28、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化，入队列，和出对列的算法。
首先队列的特点是先进先出，添加在尾端，删除在头端的一种限定性线性表，完整算法如下所示：
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data;
struct LNode* next;
}LNode,*Queue;
Queue tali, node, Q;
void InitLinkList(Queue L)
{
L = (Queue)malloc(sizeof(LNode));
L->next = L;
tali = L->next;
system("pause");
}
void InsertList(Queue L, int data)
{
node = (Queue)malloc(sizeof(LNode));
node->data = data;
node->next = tali->next;
tali->next = node;
tali = tali->next;
}
int DeleteList(Queue L, int* data)
{
Queue p,s;
p = tali->next;
s = p->next;
if (s == p)
{
printf("队空\n");
return -1;
}
if (p->next == tali)
{
s = tali;
tali = p;
p->next = p;
free(s);
return 0;
}
p->next = s->next;
free(s);
}
void visit()
{
Queue p = tali->next->next;
while (p != tali->next)
{
printf("%d ", p->data);
p = p->next;
}
}
int main()
{
InitLinkList(Q);
int data = 0,i;
while (data < 10)
{
data++;
InsertList(Q, data);
}
visit();
data = 0;
while (data < 11)
{
DeleteList(Q, &i);
data++;
}
printf("\n");
visit();
return 0;
}这题注意只有一个元素的时候需要单独处理。
29、如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针的值相同时的队列是“空”还是“满”，试编写与此结构相应的入队列和出对列的算法，并从时间和空间角度讨论设标志域和不设标志域这两种方法的使用范围(如当循环队列容量较小而队列中每个元素占的空间交多时，哪一种方法比较好)
typedef struct
{
int data;
int tag;
}ElemType;
typedef struct
{
ElemType* base;
int fonrt;
int rear;
}Queue;
Queue Q;
void InitQueue(Queue *Q)
{
Q->base = (ElemType*)malloc(sizeof(ElemType) * SIZEQMAX);
Q->fonrt = 0;
Q->rear = 0;
int p = 0;
while (p < SIZEQMAX)
{
Q->base[p].tag = 0;
p++;
}
}
void EnQueue(Queue *Q, int data)
{
if (Q->rear == Q->fonrt && Q->base[Q->rear].tag == 1)
{
printf("队列满\n");
exit(0);
}
Q->base[Q->rear].data = data;
Q->base[Q->rear].tag = 1;
Q->rear = (Q->rear + 1) % SIZEQMAX;
}
void DeQueue(Queue* Q, int* data)
{
if (Q->rear == Q->fonrt && Q->base[Q->rear].tag == 0)
{
printf("队列空\n");
exit(0);
}
Q->base[Q->fonrt].tag = 0;
*data = Q->base[Q->fonrt].data;
Q->fonrt = (Q->fonrt + 1) % SIZEQMAX;
}当队列空间紧张的时候，设定标志域能更好的利用队列的空间，而当元素占的空间较大的时候，空出一个队列结点来判断空满能节省元素的大小。（Q.rear+1%SIZEQMAX）是否等于Q.front
30、假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法，在出队算法中要返回队头元素
void InitQueue(Queue* Q)
{
Q->base = (ElemType*)malloc(sizeof(ElemType) * SIZEQMAX);
Q->length = 0;
Q->rear = 0;
}
void Push(Queue* Q, int data)
{
if (Q->length == SIZEQMAX)
{
printf("队满\n");
exit(0);
}
Q->base[Q->rear].data = data;
Q->rear = (Q->rear + 1) % SIZEQMAX;
Q->length++;
}
void Pop(Queue* Q, int* data)
{
if (Q->length == 0)
{
printf("队空\n");
exit(0);
}
int head = ((Q->rear + SIZEQMAX) - Q->length) % SIZEQMAX;
Q->length--;
*data = Q->base[head].data;
}这儿需要注意的是怎么通过长度和队尾下标求的头元素的位置，利用下述表达式可求的：
- int head = ((Q->rear + SIZEQMAX) - Q->length) % SIZEQMAX;
图解如下：
某一状态下的循环队列
31、假设称正读和反读都相同的字符序列为“回文”，例如‘abba’和‘abcba’是“回文”，‘abcde’和‘ababab’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是‘回文’
利用顺序栈存储字符，然后碰到@结束读取，两个指针分别指向两端，一起前进，判断所指向的字符是否相等
int main()
{
InitStack(&S);
char ch;
ch = getchar();
while (ch != '@')
{
Push(&S, ch);
ch = getchar();
}
char* p, * s;
s = S.top - 1;
p = S.base;
while (s > p)
{
if (*s == *p)
{
s--;
p++;
}
else
{
printf("不是回文\n");
return -1;
}
}
printf("是回文\n");
return 0;
}32、试利用循环队列编写求k阶斐波那契中前n+1项(f0,f1,...,fn)的算法，要求满足：fn<=max而f(n+1)>max，其中max为某个约定的常数。(注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项f(n-k+1),...,fn)
void GetFib_CyQueue(int k, int n)
{
InitQueue(Q);
for (i = 0; i < k; i++)
{
Q.base[i] = 0;
}
Q.base[k - 1] = 1;
for (i = 0; i < k; i++)
{
printf("%d", Q.base[i]);
}
for (int i = k; i <= n; i++)
{
m = i % k;
sum = 0;
for (int j = 0; j < k; j++)
{
sum += Q.base[(m + j) % k];
Q.base[m] = sum;
printf("%d", sum);
}
}
}33、在顺序存储结构上实现输出受限的双端循环队列的入列和出列(只允许队头出列算法)，设每个元素表示一个待处理的作业，元素值表示作业的预计时间，入队列采取简化短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
这题需要考虑就是初始化的时候两指针放在那，应该从最后面的下标开始，才能访问到前面的下标，否则插入前端的时候不好插入。
入队的时候考虑元素值与队头队尾的平均值的大小，决定插入在那端，出队直接出就好了
算法如下：
void InitQueue(Queue* Q)
{
Q->base = (int*)malloc(sizeof(int) * MAXSIZE);
Q->fornt = MAXSIZE - 1;
Q->rear = MAXSIZE - 1;
}
void EnQueue(Queue* Q,int data)
{
if ((Q->rear + 1) % MAXSIZE == Q->fornt)
{
printf("队列满\n");
}
int temp = Q->base[Q->rear] + Q->base[Q->fornt];
if (data > temp)
{
Q->rear = (Q->rear + 1) % MAXSIZE;
Q->base[Q->rear] = data;
}
else
{
Q->fornt = (Q->fornt - 1) % MAXSIZE;
Q->base[Q->fornt] = data;
}
}
void DeQueue(Queue* Q, int* data)
{
if (Q->fornt == Q->rear)
{
printf("队列空\n");
}
*data = Q->base[Q->fornt];
Q->fornt = (Q->fornt + 1) % MAXSIZE;
}34、假设有在受限的双端队列中有n节车厢：硬座、硬卧和软卧等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后，试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列，分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出对列的操作，以字符A表示对双端队列的尾端进行入队列的操作。
P尾插，S头插，H尾插，最后让S出来，指向尾插，具体算法如下所示
#define MAXSIZE 100
#include<stdio.h>
#include<stdlib.h>
typedef struct QLnode
{
char data;
struct QLnode* next;
}Queue,*QList;
QList head,node;
InitQueue()
{
head = (QList)malloc(sizeof(Queue));
head->next = NULL;
}
void EnQueue(QList Q,char a)
{
node = (QList)malloc(sizeof(Queue));
node->data = a;
node->next = Q->next;
Q->next = node;
}
void DeQueue(QList Q, char* a)
{
QList p;
p = Q->next;
*a = p->data;
if (p == NULL)
{
printf("队列空\n");
exit(0);
}
Q->next = p->next;
free(p);
}
void AnQueue(QList Q, char a)
{
node = (QList)malloc(sizeof(Queue));
node->data = a;
node->next = NULL;
QList p;
p = Q;
while (p->next != NULL)
{
p = p->next;
}
p->next = node;
}
int main()
{
InitQueue(head);
char * train= "PHS";
char* p = train;
char temp;
while (*p != NULL)
{
switch (*p)
{
case'P':
EnQueue(head, *p);
p++;
break;
case'H':
EnQueue(head, *p);
DeQueue(head, &temp);
p++;
break;
case'S':
AnQueue(head, *p);
p++;
break;
}
}
AnQueue(head, temp);
while (head->next != NULL)
{
DeQueue(head, &temp);
printf("%c", temp);
}
system("pause");
}