美文网首页
数据结构与算法-栈

数据结构与算法-栈

作者: MrDemon_ | 来源:发表于2020-05-17 22:38 被阅读0次

    前言:

    栈和队列的特点: 都是线性结构,同样也是线性表,特殊性在于读取的基本操作上不一样, 线性表是可以读取任何一个元素,而栈和队列则不同。

    栈结构特点:

    出栈和进栈、插入和删除都在栈顶

    栈结构

    队列结构特点:

    遵循先进先出,读取元素只能有一个方向——队列头a1。插入元素只能从队尾插入

    队列结构

    如何实现一个栈

    我们知道逻辑结构分:线性结合,集合结构,树形结构,图像结构;物理结构分:顺序储存结构/链式储存结构,链表属于物理结构,栈属于物理结构。

    • 栈的顺序存储
    //栈定义
    
    typedef struct{   
        SElemType data[MAXSIZE];
        int top; /* 用于栈顶指针 */
    }SqStack;
    
    //构建一个空栈
    
    Status InitStack(sqStack *S){
        S->top = -1;//-1表示一个空栈
        return OK;
    }
    
    //置空栈
    
    Status ClearStack(SqStack *S){    
    //将栈置空,只需要修改top标签就可以了,不必要将顺序栈的元素都清空   
     S->top = -1;  
      return OK;
    }
    
    //判断一个栈是否为空
    
    Status StackEmpty(SqStack S){ 
       if (S.top == -1)  
          return TRUE;  
       else      
       return FALSE;
    
    }
    
    //栈的长度    
    
    int StackLength(SqStack S){    
        return S.top + 1;
    }
    
    //获取栈顶    
    
    Status GetTop(SqStack S,SElemType *e){    
         if (S.top == -1)        
            return ERROR;  
          else       
            *e = S.data[S.top];   
      return OK;
    }
    
    // 压栈(入栈)
    
    Status PushData(SqStack *S,SElemType *e){  
      if (S->data == MAXSIZE - 1) return ERROR;//MAXSIZE - 1:-1是因为从0开始  
         S->top ++;  
         S->data[S->top] = e;    
      return OK;
    }
    
    //出栈
    
    Status Pop(SqStack *S,SElemType *e){   
         if (S->top == -1) return ERROR;  
         *e = S->data[S->top];    
         S->top --; 
      return OK;
    }
    
    //遍历栈    
    
    Status StackTraverse(SqStack S){ 
         int i = 0;   
         if (S.top == - 1) {  
           return ERROR;  
         }    
         printf("此栈所有元素:");    
         while (i <= S.top) {    
            printf("%d",S.data[i++]);  
        }   
        printf("\n");  
      return OK;
    }
    

    链式栈结构

    栈顶top永远指向栈顶元素,结点与结点之间的链接由next指针

    链式栈结构
    /* 栈里结点 */
    typedef struct StackNode{  
        SElemType data;   
        struct StackNode *next;
    }StackNode,*LinkStackPtr;
    
    /* 链栈结构 */
    typedef struct{  
        LinkStackPtr top;    
        int count;
    }LinkStack;
    
    //构造一个空栈S
    Status InitStack(LinkStack *S){  
      S->top=NULL;   
      S->count=0;   
      return OK;
    }
    
    //把链栈S置为空栈
    Status ClearStack(LinkStack *S){  
        LinkStackPtr p,q;  
        p = S->top;   
        while (p) {    
        q = p;      
        p = p->next;    
        free(q);    
      }   
      S->count = 0;   
      return OK;
    }
    
    /*若栈S为空栈,则返回TRUE, 否则返回FALSE*/
    Status StackEmpty(LinkStack S){  
        if (S.count == 0)     
          return TRUE;   
        else
         return FALSE;
    }
    
    //插入元素e到链栈S (成为栈顶新元素)
    Status Push(LinkStack *S, SElemType e){   
       //创建新结点temp   
        LinkStackPtr temp = (LinkStackPtr)malloc(sizeof(StackNode));    
    
        //赋值  
        temp->data = e;    //把当前的栈顶元素赋值给新结点的直接后继, 参考图例第①步骤;   
        temp->next = S->top;    //将新结点temp 赋值给栈顶指针,参考图例第②步骤;  
        S->top = temp;  
        S->count++;  
      return OK;
    }
    
    //若栈不为空,则删除S的栈顶元素,用e返回其值. 并返回OK,否则返回ERROR*/
    Status Pop(LinkStack *S,SElemType *e){   
       //if (S.count == 0) return ERROR;   
        if (StackEmpty(*S)) {    
            return ERROR;   
        }  
    
        LinkStackPtr p;
    
        //将栈顶元素赋值给*e   
        *e = S->top->data;  
    
        //将栈顶结点赋值给p,参考图例①   
         p = S->top;   
    
         //使得栈顶指针下移一位, 指向后一结点. 参考图例②   
         S->top= S->top->next;   
    
        //释放p    
        free(p);    
    
        //个数--    
        S->count--;       
      return OK;
    }
    
    //遍历链栈
    Status StackTraverse(LinkStack S){  
       LinkStackPtr p; 
       p = S.top;   
       while (p) {    
           printf("%d ",p->data);      
           p = p->next; 
         }  
        printf("\n");    
     return OK;
    }
    
    main函数:
    int main {
        int j;   
        LinkStack s;  
        int e;   
    
        if(InitStack(&s)==OK)   
        for(j=1;j<=10;j++)       
        Push(&s,j);   
    
        printf("栈中元素依次为:");  
        StackTraverse(s);   
        Pop(&s,&e);   
        printf("弹出的栈顶元素 e=%d\n",e);  
        StackTraverse(s); 
        printf("栈空否:%d(1:空 0:否)\n",StackEmpty(s));   
        GetTop(s,&e); 
        printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s)); 
    
        ClearStack(&s);  
        printf("清空栈后,栈空否:%d(1:空 0:否)\n",StackEmpty(s));
    }
    
    
    • 递归思想

    定义是递归:数学定义是递归 阶乘 /斐波拉契数列

    数据结构是递归,链表的结构设计也是递归

    问题是递归可以用递归

    分治法:将大问题分解成小问题;大问题和小问题的解法是高度相同的;递归出口,边界。

    兔子繁衍问题

    如果兔子2个⽉之后就会有繁衍能力,那么一对兔子每个月能⽣生出一对兔子; 假设所有的兔子都不死,那么n个月后能生成多少只兔子?

    数据分析

    调用函数分析

    调用分析

    此问题是一个斐波拉契数列

    int Fbi(int i){ 
        if(i < 2)    
        return i == 0 ? 0 : 1;  
        return Fbi(i - 1) + Fbi(i - 2);
    }
    
    int main(int argc, const char * argv[]) {   
     // 1 1 2 3 5 8 13 21 34 55 89 144   
     for (int i =0; i < 10; i++) {       
          printf("%d  ",Fbi(i)); 
         }   
         printf("\n");  
       return 0;
    }
    

    Hanoi塔问题:

    问题描述: 假如有3个分别命名为A,B,C的塔座,在塔座A上插有n个直接大小各不不相同的,从小到大的 编号为1,2,3...n的圆盘. 现在要求将塔座A上的n个圆盘移动到塔座C上. 并仍然按照同样的顺序叠 排. 圆盘移动时必须按照以下的规则:1. 每次只能移动⼀个圆盘;2. 圆盘可以插在A,B,C的任⼀塔座 上;3. 任何时刻都不能将⼀个较大的圆盘压在小的圆盘之上.

    代码实现

    int m = 0;
    void moves(char X,int n,char Y){   
       m++; 
       printf("%d: from %c ——> %c \n",n,X,Y);
    }
    
    //n为当前盘子编号. ABC为塔盘
    void Hanoi(int n ,char A,char B,char C){   
         //目标: 将塔盘A上的圆盘按规则移动到塔盘C上,B作为辅助塔盘;   
         //将编号为1的圆盘从A移动到C上   
         if(n==1) moves(A, 1, C);   
         else  
        {       
            //将塔盘A上的编号为1至n-1的圆盘移动到塔盘B上,C作为辅助塔;      
           Hanoi(n-1, A, C, B);        //将编号为n的圆盘从A移动到C上;        
           moves(A, n, C);        //将塔盘B上的编号为1至n-1的圆盘移动到塔盘C上,A作为辅助塔;   
           Hanoi(n-1, B, A, C);   
        }
    }
    
    int main(int argc, const char * argv[]) {   
        printf("Hanoi 塔问题\n");    
        Hanoi(3, 'A', 'B', 'C');   
        printf("盘子数量为3:一共实现搬到次数:%d\n",m);
    
        Hanoi(4, 'A', 'B', 'C');    
        printf("盘子数量为3:一共实现搬到次数:%d\n",m); 
        return 0;
    }
    
    

    相关文章

      网友评论

          本文标题:数据结构与算法-栈

          本文链接:https://www.haomeiwen.com/subject/hhmeohtx.html