数据结构作业(2018/10/10)

Love The Way You Lie 2022-05-08 12:50 177阅读 0赞

## 1.基本的a+b（+ -\*/%） ##

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        
            int a,b;
            char ch;
            int ans;
            scanf("%d %d %c",&a,&b,&ch);
            switch(ch)
            {
        
                    case '+':
                            ans = a + b;
                            break ;
                    case '-':
                            ans = a - b;
                            break ;
                    case '*':
                            ans = a * b;
                            break ;
                    case '/':
                            ans = a / b;
                            break ;
                    case '%':
                            ans = a % b;
                            break ;
            } 
            printf("%d\n",ans);
            return 0;
    }

## 2.动态数组的实现（已经提供代码）； ##

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    int main()
    {
        
         int *array = 0, num, i;
         printf("please input the number of element: ");
         scanf("%d", &num);
         // 申请动态数组使用的内存块
         array = (int *)malloc(sizeof(int)*num);
         if (array == 0)             // 内存申请失败,提示退出
         {
        
             printf("out of memory,press any key to quit...\n");
             exit(0);             // 终止程序运行,返回操作系统
         }
         // 提示输入num个数据
          printf("please input %d elements: ", num);
          for (i = 0; i < num; i++)
             scanf("%d", &array[i]);
         // 输出刚输入的num个数据
         printf("%d elements are: \n", num);
         for (i = 0; i < num; i++)
             printf("%d,", array[i]);
         printf("\b \n");    // 删除最后一个数字后的分隔符逗号
         free(array);        // 释放由malloc函数申请的内存块
         system("pause");
         return 0;
    }

## 3.十进制转化为二进制（数组的实现）； ##

其中有两种写法(已经注释掉 )是利用的位运算，由于位运算的速度比数值计算速度快，因此我更喜欢利用位运算来解决十进制转换二进制问题

有兴趣的可以学习一下

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
            int a[70];
            int n;
            cout<<"请输入十进制数："<<endl;
            cin>>n;
            printf("%d的二进制数是:\n",n);
            int cnt=0;
    /*第一种写法*/
            while(n>0)
            {
        
                    a[cnt++] = n%2;
                    n/=2;
            }
    
    
    /*第二种写法*/
    //        while(n)
    //        {
        
    //                a[cnt++] = n&1;
    //                n>>=1;
    //        }
    
    
    /*第三种写法*/
    //        for(;n;n>>=1)
    //                a[cnt++]=n&1;
    
            for(int i=cnt-1;i>=0;i--)
                    cout<<a[i];
            cout<<endl;
            return 0;
    }

## 4.十进制转化为二进制（栈的实现）； ##

让背的带代码是这样子的  
它得手工实现栈，然后利用栈来解决十进制转化二进制问题

#include <stdio.h>
    #include <malloc.h>
    #include <iostream>
    using namespace std;
    typedef int SElemType;
    typedef int Status;
    #define INIT_SIZE 100
    #define STACKINCREMENT 10
    #define Ok 1
    #define Error 0
    #define True 1
    #define False 0
    typedef struct
    {
        
        SElemType *base;
        SElemType *top;
        int stacksize;
    } SqStack;
    
    //初始化栈
    Status InitStack(SqStack *s)
    {
        
        s->base = (SElemType *)malloc(INIT_SIZE * sizeof(SElemType));
        if(!s->base)
        {
        
            puts("存储空间分配失败！");
            return Error;
        }
        s->top = s->base;
        s->stacksize = INIT_SIZE;
        return Ok;
    }
    
    //清空栈
    Status ClearStack(SqStack *s)
    {
        
        s->top = s->base;
        return Ok;
    }
    
    //栈是否为空
    Status StackEmpty(SqStack *s)
    {
        
        if(s->top == s->base)
            return True;
        else
            return False;
    }
    
    //销毁栈
    Status Destroy(SqStack *s)
    {
        
        free(s->base);
        s->base = NULL;
        s->top = NULL;
        s->stacksize=0;
        return Ok;
    }
    
    
    
    
    //获得栈顶元素
    Status GetTop(SqStack *s, SElemType &e)
    {
        
        if(s->top == s->base)
            return Error;
        e = *(s->top - 1);
        return Ok;
    }
    
    //压栈
    Status Push(SqStack *s, SElemType e)
    {
        
        if(s->top - s->base >= s->stacksize)//栈满
        {
        
            s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
            if(!s->base)
            {
        
                puts("存储空间分配失败！");
                return Error;
            }
            s->top = s->base + s->stacksize;//修改栈顶位置
            s->stacksize += STACKINCREMENT;//修改栈长度
    
        }
        *s->top++ = e;
        return Ok;
    }
    
    //弹栈
    Status Pop(SqStack *s, SElemType *e)
    {
        
        if(s->top == s->base)
            return Error;
        --s->top;
        *e = *(s->top);
        return Ok;
    }
    
    //遍历栈
    Status StackTraverse(SqStack *s,Status(*visit)(SElemType))
    {
        
        SElemType *b = s->base;//此处不能直接用base或top移动，即不能改变原栈的结构
        SElemType *t = s->top -1;
        while(t >= b)
            visit(*t--);
    //        visit(*b++);
        printf("\n");
        return Ok;
    }
    
    Status visit(SElemType c)
    {
        
        printf("%d",c);
        return Ok;
    }
    
    int main()
    {
        
            SqStack a;
            SqStack *s = &a;
            SElemType e,n;
            InitStack(s);
            printf("请输入十进制数：");
            cin>>n;
            printf("\n%d的二进制数是:\n",n);
            InitStack(s);
            while(n)
            {
        
                    e = n%2;
                    Push(s,e);
                    n/=2;
            }
            StackTraverse(s,visit);
            puts("");
            Destroy(s);
        return 0;
    }

## 5. n!和斐波纳契数列的递归实现； ##

####  n ! &ThickSpace; \\large n!\\; n!递归实现 ####

定义 &ThickSpace;&ThickSpace; f ( n ) &ThickSpace;&ThickSpace; = &ThickSpace;&ThickSpace; n ! \\large \\;\\;f(n)\\;\\;=\\;\\;n! f(n)=n!  
 f ( n ) = \{ 1 n = = 0 n × f ( n − 1 ) n > 0 \\Large f(n)=\\begin\{cases\}1& n==0\\\\ n\\times f(n-1) & n>0 \\end\{cases\} f(n)=⎩⎪⎨⎪⎧1n×f(n−1)n==0n>0

#include<bits/stdc++.h>
    using namespace std;
    
    int f(int n)
    {
        
            if(0 == n)      return 1;
            else            return n*f(n-1);
    }
    
    int main()
    {
        
            int n;
            scanf("%d",&n);
            printf("%d\n",f(n));
            return 0;
    }

#### Fibonacci数列递归实现 ####

定义 &ThickSpace;&ThickSpace; f ( n ) &ThickSpace;&ThickSpace; \\large \\;\\;f(n)\\;\\; f(n)表示斐波那契数列的第 &ThickSpace; n &ThickSpace; \\; \\large n\\; n项  
 f ( n ) = \{ 1 n = = 0 ∣ ∣ n = = 1 f ( n − 1 ) + f ( n − 2 ) n > 1 \\Large f(n)=\\begin\{cases\}1& n==0||n==1\\\\ f(n-1)+f(n-2) & n>1 \\end\{cases\} f(n)=⎩⎪⎨⎪⎧1f(n−1)\+f(n−2)n==0∣∣n==1n>1

#include<bits/stdc++.h>
    using namespace std;
    
    int Fib(int n)
    {
        
            if(0 == n || 1 == n)    return 1;
            else                    return Fib(n-1) + Fib(n-2);
    }
    
    int main()
    {
        
            int n;
            printf("请输入Fibonacci数列的第n项:");
            scanf("%d",&n);
            printf("Fibonacci数列的第%d项是：%d\n",n,Fib(n));
            return 0;
    }

## 6. n!和斐波纳契数列的非递归实现； ##

####  n ! &ThickSpace; \\large n!\\; n!递归实现 ####

#include<bits/stdc++.h>
    using namespace std;
    
    int main()
    {
        
            int n;
            scanf("%d",&n);
            int ans=1;
            for(int i=1;i<=n;i++)
                    ans=ans*i;
            printf("%d\n",ans);
            return 0;
    }

#### Fibonacci数列递归实现 ####

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        
            /*非递归不就是递推了么？...*/
            /*递推实现：*/
            int f[10000];
            f[0]=f[1]=1;
            int n;
            scanf("%d",&n);
            for(int i=2;i<=n;i++)
                    f[i]=f[i-1]+f[i-2];
            printf("%d\n",f[n]);
            return 0;
    }