赞
踩
撰写的内容可能有错误的地方,如果有错误或者疑问,欢迎评论区或者私信指正,我会及时改正
(1)递归进层需要做的三件事。
(2)递归退层需要做的三件事。
(3)顺序队列的"假溢出"现象。
随着进队和入队,队头指针和队尾指针加1,最后出现队头指针和队尾指针指向超出顺序表索引,但是此时队列仍有空间的现象
(4)循环队列的判空、判满条件(少用一个空间区分队空队满)。
rear == front
(rear + 1) mod MAXSIZE == font
(1)输入序列为123,若进栈、出栈操作可以交替进行,则不能得到的出栈序列是(B)
A .321
B .312
C .123
D .132
(2)以下会用到栈的应用是(D)。
A .递归
B .子程序调用
C .括号匹配
D .以上选项均是
(3)栈和队列的共同点是(C)。
A .都是先进先出
B .都是先进后出
C .只允许在端点处插入和删除元素
D .它们没有共同点
(4)循环队列存储在数组 A [0.. m -1]中,则入队时 rear 应变化为(C)
A . rear ++
B . rear =( rear +1) mod ( m -1)
C . rear = (rear+1) mod m
D . rear = (rear + 1) mod (m+1)
(5)设有一个顺序共享栈 S [0.. n -1],其中第一个栈项指针 topl 的初值为﹣1,第二个栈顶指针top2的初值为 n ,则判断共享栈满的条件是(C)
A . topl ==top2
B .top1+top2== n
C . topl +1==top2
D . topl -1==top2
A-B*C/D+E^F
(1)编写算法,将原表达式转换为后缀表达式 。
(2)编写算法,对转换后的后缀表达式进行求值。
答:(1)
此处编写了一个完整的可运行代码,但是程序可能不太稳定,qaq
- #include<stdio.h>
-
- #define MaxSize 100
- char ch[MaxSize] = "a*b+(c-d/e)*f";
-
- //定义栈和队列结构
- typedef struct Stack{
- char data[MaxSize];
- int top;
- }Stack;
-
- //定义栈的函数
- //初始化
- void initStack(Stack * s){
- s->top = -1;
- }
- //判空
- int isEmptyStack(Stack *s){
- return s->top==-1;
- }
- //判满
- int isFullStack(Stack *s){
- return s->top==MaxSize;
- }
- //出栈
- char popStack(Stack * s){
- if(isEmptyStack(s))
- return '\0';
- return s->data[s->top--];
- }
- //入栈
- int pushStack(Stack * s,char elem){
- if(isFullStack(s))
- return 0;
- s->data[++s->top] = elem;
- return 1;
- }
- //获取栈顶元素
- char getTopStack(Stack *s){
- if(isEmptyStack(s))
- return '\0';
- return s->data[s->top];
- }
-
- //定义队列
- typedef struct Queue{
- char data[MaxSize];
- int rear;
- int front;
- }Queue;
-
- //初始化
- void initQueue(Queue *q){
- q->rear = 0;
- q->front= 0;
- }
- //判空
- int isEmptyQueue(Queue *q){
- return q->rear == q->front;
- }
- //判满
- int isFullQueue(Queue *q){
- return (q->rear+1)%MaxSize == q->front;
- }
-
- // 入队
- void enQueue(Queue *q, char elem) {
- if (isFullQueue(q))
- printf("queue is full!!!");
- q->data[q->rear++] = elem;
- return ;
- }
-
- // 出队
- char deQueue(Queue *q) {
- if (isEmptyQueue(q)){
- printf("queue is empty!!!");
- return '\0';
- }
- return q->data[q->front++];
- }
-
- //比较优先级
- int compare(char ch1,char ch2){
- if(ch1 == '+' || ch1 == '-'){
- if(ch2 == '+' || ch2 == '-')
- return 0;
- else{
- return -1;
- }
- }
- if(ch1 == '*' || ch1 == '/'){
- if(ch2 == '+' || ch2=='-'){
- return 1;
- }else{
- return 0;
- }
- }
- }
-
- void transform(){
- int i = 13;
- printf("please input your function\n");
- //获取表达式
- //while(scanf("%c",&ch[i])&&ch[i]!='\n'&&i<MaxSize)
- // i++;
- //将中缀表达式转换为后缀表达式
- /* 思路:
- * 初始化一个操作符栈和一个输出队列,一个运算符栈S,一个输出队列Q
- * 1.遇到操作数: 直接添加到输出队列
- * 2.遇到运算符: a:如果S1为空,或者栈顶元素为'(',直接入栈
- * b:否则比较优先级
- * 当前运算符比较级小于等于栈顶元素运算法与优先级,栈元素出栈并进入到输出队列
- * 否则 入栈
- * c:如果为')',S出栈并进入输出队列,直到遇到'(',左右括号出栈后不添加到输出队列
- * */
- //理论结束 实战开始
- //初始化栈和队列
- for(int j = 0;j<i;j++){
- printf("%c",ch[j]);
- }
- printf("\n");
- Stack s;
- Queue q;
- initStack(&s);
- initQueue(&q);
- printf("------------\n");
- for(int j=0;j<i;j++){
- //printf("%c",ch[j]);
- switch(ch[j]){
- case '+':
- case '-':
- case '*':
- case '/':
- if(isEmptyStack(&s) || getTopStack(&s) == '('){
- pushStack(&s,ch[j]);
- }else{
- int compareResult = compare(ch[j],getTopStack(&s));
- if(compareResult !=1){
- //循环比较并出栈进入到输出队列
- do{
- char dataTop = popStack(&s);
- enQueue(&q,dataTop);
- }while(compare(ch[j],getTopStack(&s))!=1 && !isEmptyStack(&s));
- pushStack(&s,ch[j]);
- }else{
- pushStack(&s,ch[j]);
- }
- }
- break;
- case '(':
- pushStack(&s,ch[j]);
- break;
- case ')':
- while(getTopStack(&s)!='(')
- enQueue(&q,popStack(&s));
- popStack(&s);
- break;
- default:
- enQueue(&q,ch[j]);
- }
- }
- while(!isEmptyStack(&s)){
- enQueue(&q,popStack(&s));
- }
- //队列元素循环出队
- while(!isEmptyQueue(&q)){
- printf("%c",deQueue(&q));
- }
- }
-
- void test(){
- Stack s;
- Queue q;
- initStack(&s);
- initQueue(&q);
-
- char ch4[] = {'a','b','c','d'};
- printf("------------");
- for(int i=0;i<4;i++){
- pushStack(&s,ch4[i]);
- enQueue(&q,ch4[i]);
- }
- printf("------------");
- while(!isEmptyStack(&s)){
- printf("%c",popStack(&s));
- }
- printf("\n");
- //队列元素循环出队
- while(!isEmptyQueue(&q)){
- printf("%c",deQueue(&q));
- }
-
- }
-
- int main(){
- //test();
- transform();
- return 0;
- }

(2)
求出后缀表达式后。后缀表达式的求值只需要将后缀表达式数字依次入栈,遇到运算符出栈两个元素并计算,然后继续执行上述步骤
- $ cat program5.c
- /*
- * 带头节点的循环链表表示队列,只设置一个尾指针,不设置
- * 头指针,编写相应的队列初始化、入队、出队算法
- * */
-
-
- typedef struct QueueNode{
- int data;
- struct QueueNnode *next;
- }Queue;
-
- void initStruct(Queue *q){
- q = NULL;
- }
-
- int enQueue(Queue *q,int elem){
-
- if(isFullQueue(q))
- return 0;
- struct QueueNode *node = (struct QueueNode *)malloc(sizeof(struct QueueNode));
- node->data = elem;
- if(q==NULL){
- //队列为空
- q = node;
- q->next = next;
- }else{
- node->next = q->next;
- q->next = node;
- q = node;
- }
- return 1;
-
- }
-
- int deQueue(Queue *q,int elem){
- if(isEmptyQueue(q))
- return 0;
- struct QueueNode *node = q->next;//q是尾指针,则q->next对应头结点
- struct QueueNode *s = node->next;//要删除的结点
- if(s == node){
- //只有一个结点
- free(s);
- q = NULL:
- }else{
- node->next = s->next;
- free(s);
- }
-
- return 1;
- }

- /*
- 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域 tag ,
- 以 tag 为0或1来区分头尾指针相同时的队列状态的空与满,试编写与此结
- 构相应的人队与出队算法。
- */
-
- #define MaxSize 100
- typedef struct Queue{
- int tag; //标志域 tag == 1 为满 tag == 0 为空
- int data[MaxSize]; //数据域
- int front,rear; //首尾指针
-
- }Queue;
-
- void InitQueue(Queue *q){
- q->front = 0;
- q->rear = 0;
- q->tag = 0;
- }
-
- void enQueue(Queue *q,int elem){
- if(tag){
- printf("队满!!!")
- return;
- }
- q->data[q->rear] = elem;
- q->rear++;
- q->rear %= MaxSize;
- if(q->rear == q->front){
- q->tag = 1;
- }
- }
-
- int deQueue(Queue *q){
- if(!tag){
- printf("队空!!!");
- return -1;
- }
- int temp = q->data[q->front];
- q->front++;
- q->front%=MaxSize;
- if(q->front == q->rear)
- tag = 0;
- return temp;
- }

四个元素1、2、3、4的排序种类有4*3*2*1=24种
依次为
1 2 3 4 , 1 2 4 3 , 1 3 2 4 ,1 3 4 2 , 1 4 2 3 , 1 4 3 2
2 1 3 4 , 2 1 4 3 , 2 3 1 4 , 2 3 4 1 , 2 4 1 3 , 2 4 3 1
3 1 2 4 , 3 1 4 2 , 3 2 1 4 , 3 2 4 1 , 3 4 1 2 , 3 4 2 1
4 1 2 3 , 4 1 3 2 , 4 2 1 3 , 4 2 3 1 , 4 3 1 2 , 4 3 2 1
红色为不可能的出栈顺序,黑色为可能的出栈顺序
n个元素进栈,可能的出栈顺序有
则四个元素进栈可能的出栈顺序有14种
(1)编写递归算法
- int funcG(int m,int n){
- if(m == 0)
- return 0;
- return funcG(m-1,2*n)+n;
- }
(2)给出g(3,5)的递归执行过程图示
(3)将递归算法改写为非递归算法
- int funcG(int m,int n){
- int sum = 0;
- while(m!=0){
- sum+=n;
- n*=2;
- m--;
- }
- return sum;
- }
- void bin(int b[],int n){
- if(n==1){
- b[1] = 2;
- b[2] = 2;
- }else{
- bin(b,n-1);
- b[n+1] = 2;
- for(int i=n;i>=2;i--){
- b[i] = b[i]+b[i-1];
- }
- }
- }
若调用 bin ( A ,5),给出 A 数组中第1个到第6个数组元素的值。
答:
数组中的值为
2 10 20 20 10 2
每次递归将后面一个元素赋值为2,然后前面的元素分别加等其前面的元素
假设柱子编号为 A B C
执行步骤:
(1)将上面的n-1个盘子从A经过C移动到B;
(2)将编号为n的盘子从A移到C;
(3)将B上的n-1个盘子经过A移动到C
此时需要先将B上的n-2个盘子经过C移动到A,然后将第n-1个盘子从B移动到C
设ai 为有i个盘子时需要移动的次数
则
a1 = 1
a2 = 3
a3 =
= 7
a4 =
= 15
.......
an =
=
为什么?
根据移动的三个步骤:
n个盘子时
将n-1个盘子从一个柱子经另一个柱子移动到剩余的柱子需要
步
将编号为n的盘子从A移动到C 需要1步
将n-1个盘子从一个柱子经另一个柱子移动到剩余的柱子需要
步
则 an =
![]()
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。