数据结构进阶实训五 栈与递归

Data structure advanced training course notes and algorithm exercises

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

---

题目1

假设算术表达式只包含“+”、“-”、“*”、“/”，正整数和括号的合法数学表达式。根据算符优先关系，
  - 将算术表达式的中缀表示法转换为后缀表示法。
  - 对得到的后缀表达式进行求值

1.1 算法设计思想

1.1.1 转后缀表达式：

• 从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。
• 如果扫描到的字符是一个操作符，分三种情况：
  （1）如果堆栈是空的，直接将操作符存储到堆栈中（pushCStack it）
  （2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（pushCStack it）
  （3）如果该操作符的优先级低于堆栈出口的操作符，就将堆栈出口的操作符导出（popCStack it）,直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（pushCStack）
• 如果遇到的操作符是左括号”（”，就直接将该操作符输出到堆栈当中。
  该操作符只有在遇到右括号“ )”的时候移除。这是一个特殊符号该特殊处理。
• 如果扫描到的操作符是右括号“ ”，将堆栈中的操作符导出（popCStack）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（popCStack ）。继续扫描下一个字符。
• 如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。

1.1.3 求值

后缀表达式求值的算法是:
遍历后缀表达式，如果遇到运算数，那么运算数入栈
如果遇到运算符，那么弹出栈里面两个元素，先弹出的是右运算数，后弹出的是左运算数，计算运算结果，然后将结果入栈
最后遍历到后缀表达式末尾，当结果只有一个元素时，就是答案

1.2 源代码

#define StackSize 50
#define INFINITY 32768

// 定义运算符栈
typedef struct{
  char elem[StackSize];
  int top;
}SeqCStack;

void InitCStack(SeqCStack *S){
  S->top=-1;
}

void pushCStack(SeqCStack *S, char operator){
  if(S->top == StackSize - 1){   // 栈满
    return ;
  }
  else{
    S->top++;
    S->elem[S->top] = operator;
    return ;
  }
}

void popCStack(SeqCStack *S, char *e){
  if(S->top == -1){   // 栈空
    return ;
  }
  else{
    *e = S->elem[S->top];
    S->top--;
    return ;
  }
}

char getCStackTop(SeqCStack S){
  if(S.top == -1){   // 栈空
    return '#';
  }
  else{
    return S.elem[S.top];
  }
}

void traverse(SeqCStack S){
  int i=0;
  while(i <= S.top){
    printf("%c  ", S.elem[i++]);
  }
  printf("\n");
}

// 定义运算数栈
typedef struct{
  int data[StackSize];
  int top;
}SeqNStack;

void InitNStack(SeqNStack *S){
  S->top=-1;
}

void pushNStack(SeqNStack *S, int num){
  if(S->top == StackSize - 1){   // 栈满
    return ;
  }
  else{
    S->top++;
    S->data[S->top] = num;
    return ;
  }
}

void popNStack(SeqNStack *S, int *e){
  if(S->top == -1){   // 栈空
    return ;
  }
  else{
    *e = S->data[S->top];
    S->top--;
    return ;
  }
}

int getNStackTop(SeqNStack S){
  if(S.top == -1){   // 栈空
    return INFINITY;
  }
  else{
    return S.data[S.top];
  }
}

char compare(char operator, char top){
  if(top == '#')   // 空栈，操作符直接进栈
    return '>';
  else if(operator==')' && top=='(')
    return '=';
  else if(top=='(')
    return '>';
  else if(operator=='+')    // 如果操作符是'+', 无论栈顶元素是什么, '+'优先级都小
    return '<';
  else if(operator=='-')
    return '<';
  else if(operator=='*' && top=='+')
    return '>';
  else if(operator=='*' && top=='-')
    return '>';
  else if(operator=='*' && top=='*')
    return '<';
  else if(operator=='*' && top=='/')
    return '<';
  else if(operator=='*' && top=='(')
    return '<';
  else if(operator=='/' && top=='+')
    return '>';
  else if(operator=='/' && top=='-')
    return '>';
  else if(operator=='/' && top=='*')
    return '<';
  else if(operator=='/' && top=='(')
    return '<';
  else if(operator=='(')
    return '>';
  else if(operator==')')
    return '<';
}

int caculate(int left, int right, char c){
  int re = 0;
  switch (c){
  case '+':
    re = left + right;
    break;
  case '-':
    re = left - right;
    break;
  case '*':
    re = left * right;
    break;
  case '/':
    re = left / right;
    break;
  default:
    break;
  }
  return re;
}

void main(){
  SeqCStack OS, SuffixExp;
  SeqNStack NS;
  /* 初始化运算符栈 */
  InitCStack(&OS);
  /* 初始化运算数栈 */
  InitNStack(&NS);
  /* 初始后缀表达式栈 */
  InitCStack(&SuffixExp);

  char exp[] = {'5', '+', '2', '*', '(', '1', '+', '6', ')', '-', '8', '/', '2', '\0'};
  printf("Infix expression is: %s\n", exp);
  char suffixstr[50], temp;
  int i = 0, tempNum;
  while (exp[i]!='\0'){
    if(isdigit(exp[i])){    // 如果是数字直接进后缀表达式栈
      pushCStack(&SuffixExp, exp[i]);
      // printf("num------%c\n", exp[i]);
      i++;
    }
    else{
      // printf("char------\n");
      // printf("compare----%c\n", compare(exp[i], getCStackTop(OS)));
      switch(compare(exp[i], getCStackTop(OS))){
        case '>': 
          pushCStack(&OS, exp[i]);
          // printf("case1 >---%c\n", exp[i]);
          i++;
          break;
        case '=': 
          popCStack(&OS, &temp);   // 脱括号
          // printf("case2 =---%c\n", temp);
          i++;
          break;
        case '<':
          while(compare(exp[i], getCStackTop(OS))=='<'){
            // printf("case3 <---%c\n", exp[i]);
            // printf("case3 getCStackTop %c\n", getCStackTop(OS));
            popCStack(&OS, &temp);
            // printf("case3 after getCStackTop %c\n", getCStackTop(OS));
            pushCStack(&SuffixExp, temp);
          }
          // if(exp[i]!=')'){i++;}
          break;
      }
    }
  }
  /* 最后把栈中剩余的运算符依次弹栈打印 */
  while(getCStackTop(OS)!='#'){
    popCStack(&OS, &temp);
    pushCStack(&SuffixExp, temp);
  }
  traverse(SuffixExp);
  for(i=SuffixExp.top; i>=0; i--){
    popCStack(&SuffixExp, &temp);
    suffixstr[i] = temp;
  }
  printf("Infix expression to suffix expression is: %s\n", suffixstr);
  /*
    后缀表达式求值的算法是:
    遍历后缀表达式，
    如果遇到运算数，那么运算数入栈
    如果遇到运算符，那么弹出栈里面两个元素，先弹出的是右运算数，后弹出的是左运算数，
    计算运算结果，然后将结果入栈。
    最后遍历到后缀表达式末尾，当结果只有一个元素时，就是答案
  */
  char *p=suffixstr;
  while (*p != '\0'){
    if (isdigit(*p)){
      pushNStack(&NS, *p-'0');
    }
    else{
      popNStack(&NS, &tempNum);
      int rightNum = tempNum;
      // printf("rightNum:::%d\n", rightNum);
      // free(temp);
      popNStack(&NS, &tempNum);
      int leftNum = tempNum;
      // free(temp);
      
      int result = caculate(leftNum, rightNum, *p);
      // printf("caculate result----%d\n", result);
      pushNStack(&NS, result);
    }
    p++;
  }
  printf("result: %d\n", getNStackTop(NS));

  system("pause");
}

1.3 运行情况截图

---

---

题目2

设L为带头结点的单链表，实现从尾到头反向输出链表中每个结点的值。（递归思想）

2.1 算法设计思想

递归语句在打印之前就可以了

2.2 源代码

void printReversely(LinkList L){
  if(L->next!=NULL){
    printReversely(L->next);
    printf("%c  ", L->next->data);
  }
}

2.3 运行情况截图

---

---

题目3

一只青蛙一次可以跳上1级台阶，也可以跳上2级。
编写代码求青蛙跳上一个n级的台阶，总共有多少种跳法？
  - 若条件改为：
  一只青蛙一次可以跳上1级台阶，也可以跳上2级，也可以跳上3级，...，也可以跳上n级。
  编写代码求青蛙跳上一个n级的台阶，总共有多少种跳法？

3.1 算法设计思想

Q：

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
求该青蛙跳上一个n级的台阶总共有多少种跳法。

A：

f(n) = f(n-1)+f(n-2)+…+f(1)
f(n-1) = f(n-2)+ f(n-3)…+f(1)
两式相减，得到f(n) = 2*f(n-1)

3.2 源代码

int Jump(int i, int n) {
  //表示当前台阶数大于总台阶数，很显然这种情况不符合，走不通，记为 0
  if (i > n) {
      return 0;
  }
  //表示当前台阶数正好等于总的台阶数，那么这种情况符合，记为 1
  if (i == n) {
      return 1;
  }
  return Jump(i + 1, n) + Jump(i + 2, n);
}

int JumpN(int num){
  if (num == 1){
    return 1;
  }
  else{
    return 2*JumpN(num-1);
  }
}

3.3 运行情况截图

---

---

题目4

用一个2X1的小矩形横着或竖着去覆盖更大的矩形。如下图
  - 具体：用8个2X1小矩形横着或竖着去覆盖2X8的大矩形，覆盖方法有多少种？
  - 编写代码求用2X1小矩形横着或竖着去覆盖2Xn的大矩形。输出总共有多少种覆盖方法

4.1 算法设计思想

当n=1时，覆盖方法有1种；
当n=2时，覆盖方法有2种；
当n=3时，覆盖方法有2+1=3种；
当n=4时，覆盖方法有3+2=5种；
按照规律就转化成了斐波那契数列问题

4.2 源代码

int Cover(int n){
  if(n<=0){
    return 0;
  }
  else if(n==1||n==2){
    return n;
  }
  else{
    return Cover(n-1) + Cover(n-2);
  }
}

4.3 运行情况截图

---

---

题目5

借助自定义栈以非递归形式求解汉诺塔问题（n,a,b,c）；
即将n个盘子从起始塔座a通过辅助塔座b移动到目标塔座c,
并保证每个移动符合汉诺塔问题的要求

5.1 算法设计思想

利用递归的思想，用栈来处理；
比如n=3时，转化的问题是：
先要移动A塔座上面2个盘子到B塔座，这个操作进栈后续处理；
然后移动A塔座上面最后一个大盘子到C塔座，这个操作进栈后续处理；
最后再移动B塔座上最后两个盘子到C塔座；
一直访问栈，如果栈顶处理的盘子数不是1，就在把操作细分，进栈；
直到盘子数为1，移动盘子；
直到栈为空

5.2 源代码

// 定义汉诺塔数据
typedef struct{
  char A;
  char B;
  char C;
  int n;
}HanoiData;

// 定义栈
typedef struct{
  HanoiData elem[StackSize];
  int top;
}SeqStack;

void InitStack(SeqStack *S){
  S->top=-1;
}

void push(SeqStack *S, HanoiData hd){
  if(S->top == StackSize - 1){   // 栈满
    return ;
  }
  else{
    S->top++;
    S->elem[S->top] = hd;
    return ;
  }
}

void pop(SeqStack *S, HanoiData *e){
  if(S->top == -1){   // 栈空
    return ;
  }
  else{
    *e = S->elem[S->top];
    S->top--;
    return ;
  }
}

// HanoiData getTop(SeqStack S){
//   if(S.top == -1){   // 栈空
//     return ;
//   }
//   else{
//     return S.elem[S.top];
//   }
// }

void move1(int n,char A,char B,char C){
  if(n==1){
    printf("%c-->%c\n",A,C);	
  }
  else{
    move1(n-1,A,C,B);
    move1(1,A,B,C);
    move1(n-1,B,A,C);
  }	
}

void hanoi(int n){
  SeqStack S;
  InitStack(&S);
  HanoiData h = {'A', 'B', 'C', n};
  push(&S,h);//初始栈 
  // hanoi_data x;//用来保存出栈的n,A,B,C 

  while(S.top!=-1){
    pop(&S, &h);//出栈并用x带回 
    if(h.n==1){
      printf("%c-->%c\n",h.A,h.C);//打印出移动方案  
    }
    else{
      HanoiData h1 = {h.B, h.A, h.C, h.n-1};
      push(&S,h1);
      HanoiData h2 = {h.A, h.B, h.C, 1};
      push(&S,h2);
      HanoiData h3 = {h.A, h.C, h.B, h.n-1};
      push(&S,h3);
    }
  }
}

5.3 运行情况截图

---