数据结构第四周作业（栈、队列、递归）

1.

元素a, b, c, d顺序入栈，请写出出栈时的所有可能的顺序和按栈操作不可能出现的序列。

应该有14种情况()

a第一个出栈：abcd; acbd; acdb; abdc; adcb;

a第二个出栈：bacd; badc;

a第三个出栈：cbad; bcad;

a第四个出栈：bcda; cbda; cdba; bdca; dcba;

不可能出现的序列：

adbc; cabd; cadb; dacb; dabc;

cdab; dcab; bdac; dbac; dbca;

通过归纳法可以得出的是n个数依次出栈的出栈顺序满足

在这里插入图片描述
这个实际上是卡特兰数（Catalan number）卡塔兰数的通项公式为

2.

编写算法，用两个大小相同的栈来模拟一个队列的操作(包括入队操作和出队操作两个算法) 。

#include <stdio.h>
#include <stdlib.h>
 
#define STACK_INIT_SIZE 100   //存储空间初始分配量
#define STACKINCREMENT   //存储空间分配增量
 
typedef struct{
    int *base;   //栈底
    int *top;    //栈顶
    int stacksize;
}stack;

//构造一个空栈
int initStack(stack *s){
    s->base = (int*)malloc(sizeof(int)*STACK_INIT_SIZE);
    if(s->base == NULL){
        printf("Memory allocate failed!\n");
        return -1;
    }
    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
    return 1;
}
 
//压栈的方法，i为需要压入栈顶的元素
int push(stack *s, int i){
    //判断栈容量是否已经满了，如果已满，重新分配存储空间
    if(s->top - s->base >= s->stacksize){
        s->base = (int*)realloc(s->base, (s->stacksize+STACK_INIT_SIZE)*sizeof(int));
    }
    if(s->base == NULL){
        printf("Memory allocate failed!\n");
        return -1;
    }
    *s->top++ = i;   //把元素压入
    return 1;
}
 
//弹栈的方法
int pop(stack *s){
    if(s->base == s->top)
        return -1;
    
    return *--s->top;
}
int main(){
    int i;
    stack st1, st2; 
    initStack(&st1);
    initStack(&st2);
    
    //假设传入的队列为1,2,3,4,5,6
    //则出栈的队列顺序为1,2,3,4,5,6
    
    printf("Enter list is :\n");
    for(i = 0; i < 7; i++){
        push(&st1, i);
        printf("%d ", i);
    }
    printf("\n");   
    //出栈的时候每次先把1栈中除栈顶元素之外的所有元素弹到2栈中
    //然后在弹出1栈栈底元素
    //最后再把2栈中的元素压入1栈中
    //重复以上动作，直到1栈为空
    printf("Exit the list is: ");
    while(st1.base != st1.top){
        while((st1.top - st1.base) > 1){
            push(&st2, pop(&st1));
        }
        printf("%d ", pop(&st1));
        
        while((st2.top - st2.base) > 0){
            push(&st1, pop(&st2));
        }
    }
    printf("\n");
    
    return 0;
}

在这里插入图片描述

3.

编写一个非递归算法，将十进制数转换成十六进制数，并输出转换后的数。

#include <stdio.h>

int main(){
    int i = 0, num, x;      //num为输入的十进制数字，x为目标进制类型
    int arr[32] = { 0 };  //存放每一次余数的数组
    printf("请输入你要转换的十进制数num和转的换的目标进制x：");
    scanf("%d %d", &num, &x);
    while (num != 0){   //当num不等于0 时进入循环
        i++;   
        arr[i] = num % x;
        num = num / x;
        if (arr[i] > 9){
            arr[i] = 'a' + (arr[i] - 10);  //对余数的判断  主要针对16进制
        }else{
            arr[i] = arr[i] + '0';
        }
    }
    for (int j = i; j > 0; j--){  //倒序输出数组
        printf("%c", arr[j]);
    }
    return 0;
}

在这里插入图片描述

16进制的数主要问题在于大于10的话要用对应的字母来表示，所以多加一条语句，把数字当做对应的字符来存储并打印。

4.

编写一个非递归算法，利用栈计算如下函数的值：

当 n=0时；
当 n>0时。

#include <stdio.h>
#define Maxsize 10      //栈的最大容量，此时n能取的最大值为11

int fun(int n);  //函数声明

int main(){
    int n = 0;
    printf("输入n:", n);
    scanf("%d", &n);
    
    printf("计算结果为%d", fun(n));
    return 0;
}

//使用栈实现递归操作
int fun(int n){     
    if (n == 0) return 1;
    struct stack{       //定义栈
        int no;         //n
        int val;        //pn(x)
    }st[Maxsize];

    int fv0 = 1;        //边界
    int top = -1;                   //初始栈顶
    for (int i = n; i > 0; i--){    //将n存入栈
        top++;
        st[top].no = i;
    }
    while (top >= 0){           //将Pn(x)存入栈
        st[top].val = n*(st[top].no/2);         //迭代
        fv0 = st[top].val;      //迭代，当top=0时，此时no为n，val所存的值即为最终结果
        top--;
    }
    return fv0;
}

递归算法

#include <stdio.h>

int fun(int n);
int main(){
    int n;
    printf("n = ",n);
    scanf("%d",&n);

    printf("the result is %d",fun(n));
}
int fun(int n){
    if(n==0){
        return n+1;
    }else{
        return n*fun((n/2));
    }
}

在这里插入图片描述