精华内容
下载资源
问答
  • 个栈共享块存储空间新解

    千次阅读 2014-05-17 22:22:19
    采用顺序存储方式存储,现两共享空间V[1..m], top[i]代表第i个栈( i =1,2)栈顶,1的底在v[1],2的底在V[m],则栈满条件是( )。 A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=...

         前段时间数据结构的作业里有一个这样的题跟大家分享一下:

         若栈采用顺序存储方式存储,现两栈共享空间V[1..m], top[i]代表第i个栈( i =1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是( )。

     

      A. |top[2]-top[1]|=0      B. top[1]+1=top[2] 

     

      C. top[1]+top[2]=m      D. top[1]=top[2]

     

           这是两个栈共享一块存储空间的实例。关于栈的初始化可谓是各有各的小算盘,栈顶指针有的初始化为0,有的初始化为1,还有的初始化为-1。先不管它,按照C语言的规则,咱们还是把栈顶指针初始化为0,这样便于计算。那首先大家想象一下有这么一块内存,大小为50,由于栈限定只能在栈顶进行操作,那么我们就把这块内存空间的顶端和低端分别作为2栈和1栈的栈底,当入栈时相当于两列火车相向而行,等待着相撞的那一瞬间,只要不撞车就继续前行,这样就降低了上溢发生的机率,节省了内存空间。

           于是乎问题来喽,什么时候算是满栈,有人说了不就是等到两个栈相遇的时候嘛,那怎么判定两个栈相遇呢?又有人说了等到栈顶指针相遇时不就是栈满了嘛,yes,关键就是这里,我当初也就是纠结这两个栈顶指针。脑子里出现了很多画面,两个栈顶指针top1和top2从两端出发,期待着能与彼此相遇,走啊走走啊走,终于等到了相见的那一天。由于栈顶指针总是位于栈顶元素的下一个位置,所以当top1和top2相遇时,即top1+1=top2,两个栈满员,经过了多少风风雨雨,有情人终成眷属,祝福他们吧。

           但是当两个栈顶指针相遇时,它们所指的是两个空的存储单元,那这不就浪费了嘛,所以我就想能不能把这两个栈顶指针所指的空间填满,这不就完美了么,于是乎问题又来了,如果是1栈先加入元素,那么top1不就与top2重合了嘛,反之一样,最理想的就是两个栈同时入栈元素,但想到这里已经知道自己错了,不可能会出现歧义,其实更为神奇的是我居然想到当两个栈顶指针重合时再入栈元素的话,那么top1不就越过top2了嘛,于是就有了top2+1=top1,哎,各种版本都有啊,我是彻底无力了。

           为此在网上搜集了各种相关资料,真是众说纷纭啊,也是充斥着各种版本,不过最后答案一致指向B,还是top1+1=top2。最后求救于老师,老师的看法是当两个栈顶指针相遇时就算是栈满,至于那两小块空出来的内存空间就当是标记,就像循环队列一样,最后也是留出两个小空间用于说明头指针和尾指针,就是这么个情况。

     

           通过这个例子又想起了那个最传统的问题,关于常规的入栈,当top=Maxsize-1即栈顶指针到达真正的栈顶时,如果再入栈元素,那么栈顶指针是指向Maxsize还是保持不动。假如是前者的话,那么top将指向一个未知的空间;如果是后者的话又不符合栈的入栈规则,但也不排斥有这种特殊规定。反正这两者都不是一个满意的答复,在下将继续探索,相信总会等到拨云雾见蓝天的那一刻。

    ————————————————————————————————————————————————————

    这是2014.5.17的文章,之前不知为何显示审核未通过,经过几次修改终于重见天日了,但这个发表时间也就变成了2019.12.20,很不合理啊

    展开全文
  • firstsize 为创建一个栈时这个的初始大小,这里为100。addsize 为当栈满时,再想入栈的话每次大小的增量,这里用10来代替。 create函数为创建函数。push为入栈函数。empty函数用来判断 是否为空,print函数...

    顺序栈,遵循先进后出后进先出原则。我在写的时候,宏定义的
    firstsize 为创建一个栈时这个栈的初始大小,这里为100。addsize
    为当栈满时,再想入栈的话每次栈大小的增量,这里用10来代替。
    create函数为创建栈函数。push为入栈函数。empty函数用来判断
    栈是否为空,print函数用来出栈。
    //以下为全部代码

    #include "stdio.h"
    #include "malloc.h"
    #define firstsize 100
    #define addsize 10
    typedef struct{
     int *base;
     int *top;
     int size;
    }Sq;
    
    void create(Sq &s)
    {
     s.base=(int*)malloc(firstsize*sizeof(int));
     if(s.base)printf("create OK!\n");
     s.top=s.base;
     s.size=firstsize;
    }
    
    void push(Sq &s,int e)
    {
     if(s.top-s.base>=s.size)
     {
     s.base=(int*)realloc(s.base,(s.size+addsize)*sizeof(int));
     printf("栈内空间分配成功\n");
     }
     *s.top=e;
     s.top++;
     printf("元素[%d]已入栈!\n",e);
    }
    
    void print(Sq &s)
    {
     if(empty(s))printf("抱歉,栈已满,无法出栈\n");
     else
     {
       s.top--;
       printf("出栈:[%d]\n",*s.top);
      }
    }
    
    int empty(Sq &s)
    {
     if(s.top==s.base||s.top<s.base)
     { printf("栈空\n");
     return 1;}
     else {printf("栈未空\n");
     return 0;}
    }
    
    void main()
    {
    int i; Sq s;
    do
    {
    printf("\n----------------\n1-");
    printf("创建一个栈\n2-判断栈是否为空\n3-入栈\n4-出栈\n0-退出");
    printf("\n----------------\n\n");
    scanf("%d",&i);
    switch(i)
    {
     case 1:create(s);break;
     case 2:empty(s);break;
     case 3:
     {
     int e;
     printf("输入入栈元素:\n");
     scanf("%d",&e);
     push(s,e);
     }break;
     case 4:print(s);break;
     case 0:break;
     default:
     {printf("输入错误,请重新输入\n");
     }continue;
     }
     }while(i!=0);
     printf("程序已退出\n");
    }
    
    
    

    运行结果:sxz

    展开全文
  • B A.-15 B.15 C.-20 D.20 2-15假定利用数组a[n]顺序存储一个栈,用top表示栈顶指针,用top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为(C)。 A.a[–top]=x B.a[top–]=x C.a[++top]=x D.a[top++]=x ...

    1-1所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。F
    1-2队列和栈都是运算受限的线性表,只允许在表的两端进行运算。 F
    1-3An algorithm to check for balancing symbols in an expression uses a stack to store the symbols. T
    1-4在n个元素连续进栈以后,它们的出栈顺序和进栈顺序一定正好相反。 T
    1-5n个元素通过一个栈产生n个元素的出栈序列,其中进栈和出栈操作的次数总是相等的。T
    1-6通过对堆栈S操作:Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为:123。 F
    1-7在用数组表示的循环队列中,front值一定小于等于rear值。 F
    1-8不论是入队列操作还是入栈操作,在顺序存储结构上都需要考虑"溢出"情况。T
    1-9队列是一种插入和删除操作分别在表的两端进行的线性表,是一种先进后出的结构。F
    1-10"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array. F
    1-11栈是插入和删除只能在一端进行的线性表;队列 是插入在一端进行,删除在另一端进行的线性表。T
    1-12n个元素进队的顺序和出队的顺序总是一致的。T
    1-13栈底元素是不能删除的元素。F
    1-14顺序栈中元素值的大小是有序的。 F
    1-15栈顶元素和栈底元素有可能是冋一个元素。 T
    1-16栈是一种对进栈、出栈操作总次数做了限制的线性表。F
    1-17对顺序栈进行进栈、出栈操作不涉及元素的前、后移动问题。T
    1-18环形队列中有多少个元素可以根据队首指针和队尾指针的值来计算。 T
    1-19若采用“队首指针和队尾指针的值相等”作为环形队列为空的标志,则在设置一个空队时只需将队首指针和队尾指针赋同一个值,不管什么值都可以。 T
    1-20栈和队列的插入和删除操作特殊,所以,栈和队列是非线性结构。 F
    1-21两个栈共享一片连续空间,可以将两个栈的栈底分别设在这片空间的两端。 T
    1-22不论是入队还是入栈操作,在顺序存储结构下都应考虑溢出现象。 T
    1-23可以通过少用一个存储空间的方法解决循环队列假溢出现象。 F

    2-1设一个栈的输入序列是1、2、3、4、5,则下列序列中,是栈的合法输出序列的是?A
    A.3 2 1 5 4
    B.5 1 2 3 4
    C.4 5 1 3 2
    D.4 3 1 2 5

    2-2下列关于栈的叙述中,错误的是:

    采用非递归方式重写递归程序时必须使用栈
    函数调用时,系统要用栈保存必要的信息
    只要确定了入栈次序,即可确定出栈次序
    栈是一种受限的线性表,允许在其两端进行操作 A

    A.仅 1
    B.仅 1、2、3
    C.仅 1、3、4
    D.仅 2、3、4

    2-3循环顺序队列中是否可以插入下一个元素(A)。
    A.与队头指针和队尾指针的值有关
    B.只与队尾指针的值有关,与队头指针的值无关
    C.只与数组大小有关,与队首指针和队尾指针的值无关
    D.与曾经进行过多少次插入操作有关

    2-4设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定是: D
    A.1
    B.3
    C.5
    D.1或者5

    2-5设栈S和队列Q的初始状态均为空,元素{1, 2, 3, 4, 5, 6, 7}依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是{2, 5, 6, 4, 7, 3, 1},则栈S的容量至少是: D
    A.1
    B.2
    C.3
    D.4

    2-6若借助堆栈将中缀表达式a+bc+(de+f)*g转换为后缀表达式,当读入f时,堆栈里的内容是什么(按堆栈自底向上顺序)?B
    A.+( *+
    B.+(+
    C.++(+
    D.abcde

    2-7表达式a*(b+c)-d的后缀表达式是: A
    A.a b c + * d -
    B.a b c d * + -
    C.a b c * + d -
    D.- + * a b c d

    2-8若采用带头、尾指针的单向链表表示一个堆栈,那么该堆栈的栈顶指针top应该如何设置? A
    A.将链表头设为top
    B.将链表尾设为top
    C.随便哪端作为top都可以
    D.链表头、尾都不适合作为top

    2-9利用大小为n的数组(下标从0到n-1)存储一个栈时,假定栈从数组另一头开始且top==n表示栈空,则向这个栈插入一个元素时,修改top指针应当执行: C
    A.top=0
    B.top++
    C.top–
    D.top不变

    2-10若已知一队列用单向链表表示,该单向链表的当前状态(含3个对象)是:1->2->3,其中x->y表示x的下一节点是y。此时,如果将对象4入队,然后队列头的对象出队,则单向链表的状态是: B
    A.1->2->3
    B.2->3->4
    C.4->1->2
    D.答案不唯一

    2-11若用一个大小为6的数组来实现循环队列,且当前rear和fornt的值分别为0和3。从当前队列中删除一个元素,再加入两个元素后,rear和front的值分别为( B )。
    A.1和5
    B.2和4
    C.4和2
    D.5和1

    2-12判断一个循环队列QU(最多元素为MaxSize)为空的条件是(A)。
    A.QU.front == QU.rear
    B.QU.front != QU.rear
    C.QU.front == (QU.rear + 1) % MaxSize
    D.QU.front != (QU.rear + 1) % MaxSize

    2-13用单链表表示的链队的队头在链表的(A)位置。
    A.链头
    B.链尾
    C.链中
    D.均可以

    2-14Suppose that all the integer operands are stored in the stack S​1​​, and all the operators in the other stack S​2​​. The function F() does the following operations sequentially:

    (1) Pop two operands a and b from S​1​​;
    (2) Pop one operator op from S​2​​;
    (3) Calculate b op a; and
    (4) Push the result back to S​1​​.

    Now given { 5, 8, 3, 2 } in S​1​​ (where 2 is at the top), and { *, -, + } in S​2​​ (where + is at the top). What is remained at the top of S​1​​ after F(B) is executed 3 times? B
    A.-15
    B.15
    C.-20
    D.20

    2-15假定利用数组a[n]顺序存储一个栈,用top表示栈顶指针,用top==-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为(C)。
    A.a[–top]=x
    B.a[top–]=x
    C.a[++top]=x
    D.a[top++]=x

    2-16经过以下栈的操作后,变量x的值为(A)。

    InitStack(st);Push(st,a);Push(st,b);Pop(st,x);Top(st,x);
    A
    A.a
    B.b
    C.NULL
    D.FALSE

    2-17若已知一个栈的入栈序列是1,2,3,4,其出栈序列为P​1​​,P​2​​,P​3​​,P​4​​,则P​2​​,P​4​​不可能是(A)。
    A.2,4
    B.2,1
    C.4,3
    D.3,4

    2-18设有一个顺序共享栈Share[0:n-1],其中第一个栈顶指针top1的初值为-1,第二个栈顶指针top2的初值为n,则判断共享栈满的条件是(A)。
    A.top2-top1== 1
    B.top1-top2 == 1
    C.top1==top2
    D.以上都不对

    2-19循环队列放在一维数组A[0…M-1]中,end1指向队头元素,end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作,队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中,正确的是(A)。
    A.队空:end1 == end2;队满:end1 == (end2+1)mod M
    B.队空:end1 == end2;队满:end2 == (end1+1)mod (M-1)
    C.队空:end2==(end1+1) mod M;队满:end1==(end2+1) mod M
    D.队空:end1==(end2+1) mod M;队满:end2==(end1+1)mod (M-1)

    2-20下列说法中,正确的是(A)。
    A.消除递归不一定需要使用栈
    B.对同一输入序列进行两组不同的合法入栈和出栈组合操作,所得的输出序列也一定相同
    C.通常使用队列来处理函数或过程调用
    D.队列和栈都是运算受限的线性表,只允许在表的两端进行运算

    2-21数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为( D )。
    A.r-f
    B.(n+f-r)%n
    C.n+r-f
    D.(n+r-f)%n

    2-22设有一个递归算法如下
    int fact(int n)
    { //n大于等于0
    if(n<=0) return 1;
    else return n * fact(n-1);
    }
    则计算fact(n)需要调用该函数的次数为
    (A)。
    A.n+1
    B.n-1
    C.n
    D.n+2

    2-23若一个栈以向量V[1…n]存储,初始栈顶指针top设为n+1,则元素x进栈的正确操作是( C )。
    A.top++; V[top]=x;
    B.V[top]=x; top++;
    C.top–; V[top]=x;
    D.V[top]=x; top–;

    2-24下列与队列结构有关联的是 D
    A.函数的递归调用
    B.数组元素的引用
    C.多重循环的执行
    D.先到先服务的作业调度

    5-1本题要求求出不带头结点的单链表中的最大值并返回。

    /* 求单链表值最大的结点 */
    int getMaxNode(LinkNode* head)
    {
        if (head == NULL)
            return INT_MIN;
        int first = head->data;
        int m = *getMaxNode(head->next);*(4);
        if (m > first)return m;
        else return first;
    }
    

    5-2本题要求采用递归方式求不带头结点的单链表的长度。
    其中, 单链表结点类型定义如下:

    typedef struct LNode {
        int data;
        struct LNode* next;
    } LinkNode;
    ///求单链表长度
    int getLength(LinkNode* L) {
        if (L == NULL)
            return 0;
        return   *getLength(L->next)+1;*(3);
    }
    
    

    5-3已知循环队列的结构定义如下:

    typedef struct
    {
        int size, front, rear;
        int *element;
    } AQUEUE;
    

    说明:element 为存储队列数据元素的动态数组,size 为动态数组的尺寸,front 为队首元素的下标,rear 为队尾元素下一位置的下标。
    假设有以下定义:

    AQUEUE *queue;
    

    判断 queue 所指队列为空的条件是*:queue->front == queue->rear*(4分);
    判断 queue 所指队列为满的条件是: (queue->rear + 1) % queue->size == queue->front(2分);
    queue 所指队列的长度是:(queue->rear - queue->front + queue->size) % queue->size(2分)。

    注:请填写正确的C表达式,以便于检查答案是否正确。

    展开全文
  • 栈的基本运算 任务: 顺序栈的基本操作 任务描述: 本关任务:实现顺序栈的基本操作,...栈未满才执行以下进栈操作 s->top++; s->data[s->top]=x; - 出栈 出栈操作需要判断栈是否为空 栈空条件:s->to

    栈的基本运算

    任务一
    顺序栈的基本操作

    任务描述
    本关任务:实现顺序栈的基本操作,包括栈的初始化、置空栈、进栈、出栈、判栈空、栈的输出(遍历)等。

    相关知识
    为了完成本关任务,你需要掌握:

    - 顺序栈的初始化

    规定空栈时s->top=-1

    - 进栈

    进栈操作需要先判断时候是否栈满
    栈满条件:s->top==MAXSIZE-1
    栈未满才执行以下进栈操作
    s->top++;
    s->data[s->top]=x;

    - 出栈

    出栈操作需要判断栈是否为空
    栈空条件:s->top==-1;
    如果栈空,返回-1表示操作失败
    若栈非空,才执行以下出栈操作,返回栈顶元素的值:
    s->top–;
    return s->top[s->top+1];
    想想为什么?

    - 栈中元素的遍历(输出)

    可以实现逆向输出。
    两种方式:

    1、whie(栈不为空)
    {出栈;
    输出栈顶元素;
    }

    2、顺序栈本质上就是一个顺序表
    for(i=s->top;i>=0;i–)
    输出s->data[i]

    建议使用第一种方式

    编程要求

    本关中,需要定义两个完整的函数,补充一个函数

    测试说明

    从键盘输入字符串,以#作为结束符。
    平台会对你编写的代码进行测试:

    please input an express end with symbol ‘#’:
    hello#
    olleh

    • 示例代码如下:(温馨提示:本文全部代码只在 EduCoder 平台上通过测试,仅供参考,如有运行错误请自行改正)
    #include "stdio.h"
    #define MAXSIZE 100
    typedef int datatype;
     /*顺序栈的结构体类型定义*/
    typedef struct   
    {datatype stack[MAXSIZE];
     int top;
    }seqstack;
    
    /*函数功能:置空栈,请在下面给出函数的完整定义,定义时注意函数的返回值、形参个数、形参类型等*/
    
    void setnull(seqstack *s) /*置空栈—由于c语言的数组下标是从0开始的,所以置空栈操作时将栈顶指针放在下标为0之前,即-1处。*/
    {s->top=-1;}
    
               
    /*判断当前栈是否为空栈*/
    int empty(seqstack *s) 
    {if(s->top<0)
         return 1; 
     else
         return 0;
     }
    
    /*函数功能:把元素x压入栈s中,请在下面给出函数的完整定义。注意函数返回值、形参类型等*/
     
      int push(seqstack *s,datatype x) /*把元素x压入栈s中*/
     {if(s->top>=MAXSIZE-1)
       {printf("stack overflow!\n"); /*发生上溢*/
        return -1;
        }
       else
        {
    	s->top++;
    	s->stack[s->top]=x;
    	
         return s;
        }
     } 
     
     
    /*函数功能:弹出当前栈s的栈顶元素,若成功返回栈顶元素;不成功,返回-1.请在下面补充代码,函数原型已经给出了头部*/
     datatype pop(seqstack *s) 
     {
     if(s->top==-1)
       {printf("stack empty!\n"); /*栈空,返回空值*/
        return -1;
        }
      else
        {
    		s->top--; 
         return(s->stack[s->top+1]);
         }
     
      } 
    
     
     int main()
     {
     char ch;
     seqstack q;/*定义一个顺序栈变量*/
     setnull(&q);/*初始化一个顺序栈*/
    
    /*从键盘输入一个表达式入栈。表达式以#结尾*/
     ch=getchar();
     while(ch!='#')  
          {push(&q,ch);
           ch=getchar();
    	  }
     while(empty(&q)!=1)
         {ch=pop(&q);
          putchar(ch);
         }
    
     return 0;
     }
    
    
    

    任务二
    括号匹配算法

    任务描述
    本关任务:括号配对检查。试设计一个程序对任意输入的语句或数学表达式,判断其括号是否匹配。若匹配,则返回1,否则返回0。调试程序并对相应的输出作出分析;加深对算法的理解。

    相关知识
    你需要掌握:
    1.栈的基本操作
    2.括号匹配算法
    3.程序设计技巧

    - 顺序栈的基本操作

    这是上一关的内容,这里我们重点讲解这里为什么要用到栈结构?
    给定一个表达式
    {a【b/(c+d)】-a}b
    上面这个表达式中括号出现的顺序{[()]}
    在进行括号匹配的时候,我们发现
    最早读入的左括号,最后匹配
    最后读入的左括号,最先匹配
    也就是说后读入的左括号先匹配
    符合栈后进先出的特点
    因此在算法中
    我们可以将所有左括号依次入栈
    当读到右括号的时候,这个右括号应该最先跟栈顶的左括号匹配
    如果不匹配,算法结束
    如果匹配,那就出栈,这样栈顶的左括号永远是最“迫切匹配的”
    左括号的迫切匹配程度是越后读入的左括号越高

    - 括号匹配算法

    假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例:
    {()() [()]}(这里忽略了表达式中除括号外其他字符)
    方法:每出现一个左括号,保留起来;对于出现的右括号,检查后出现的左括号是否与它匹配。
    分析可能出现的不匹配的情况:
    1)到来的右括号不是所期待的;
    2)到来的是“不速之客”; —右括号多了
    3)直到结束,也没有到来“所期待的”—右括号少了
    首先建立一个栈结构,且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式,以#结束。扫描表达式exps,当遇到“(”、“[”、“{”时,将其入栈。遇到“)”、“]”、“}”时,判断栈顶是否有相匹配的括号。遇到其他字符跳过不处理。匹配成功返回1,不成功返回0.
    symb接收键盘接收过来的字符
    根据字符类型不同,处理方式不同
    ……
    switch(symb)
    {
    case ‘(‘:
    case ‘[‘:
    case ‘{‘: push(s,symb);break;
    case ‘)’:
    ch=pop(s);
    if(ch!=’(‘) return FALSE;
    break;
    case ‘]’:
    ch=pop(s);
    if(ch!=’[‘) return FALSE;
    break;
    case ‘}’:
    ch=pop(s);
    if(ch!=’{‘) return FALSE;
    break;
    default:;
    }

    用到的程序设计技巧

    在空栈中放入#垫底,push(s,‘#’)作用:
    (1)执行出栈操作不用判断栈空!因为有#垫底,当左括号匹配完了,栈顶元素为#,这时它与右括号肯定不匹配,所以就会直接返回false,避免了空栈时还要出栈的情况。
    (2)当栈顶元素为#时,说明当前栈里的左括号已经全部出栈了。

    编程要求
    需要写出judge函数原型定义。

    测试说明
    从键盘输入字符串,以#作为结束符。
    平台会对你编写的代码进行测试:
    左括号多了:
    please input an express end with symbol ‘#’:
    a+(b*(c+d)/(a+b)#
    no

    右括号多了
    please input an express end with symbol ‘#’:
    a+(b*(c+d)/(a+b)#
    no

    括号类型不匹配
    please input an express end with symbol ‘#’:
    【(a+b)/[c+d])#
    no

    完全匹配:
    please input an express end with symbol ‘#’:
    {a+(b*(c+d)/a)*a}-1#
    no

    • 示例代码如下:(温馨提示:本文全部代码只在 EduCoder 平台上通过测试,仅供参考,如有运行错误请自行改正)
    #include "stdio.h"
    #define MAXSIZE 100
    #define TRUE 1
    #define FALSE 0
    typedef int datatype;
    typedef struct    /*顺序栈的结构体类型定义*/
    {datatype stack[MAXSIZE];
     int top;
    }seqstack;
    
    int judge(seqstack *s);
    
    /*置空栈-由于c语言的数组下
    标是从0开始的,所以置空栈操作时将栈顶指针放在下标为0之前,
    即-1处。*/
    void setnull(seqstack *s) 
    {s->top=-1;}               
    
    int empty(seqstack *s) /*判断当前栈是否为空栈*/
    {if(s->top<0)
         return TRUE; 
     else
         return FALSE;
     }
    
     int push(seqstack *s,datatype x) /*把元素x压入栈s中*/
     {if(s->top>=MAXSIZE-1)
       {printf("stack overflow!\n"); /*发生上溢*/
        return FALSE;
        }
       else
        {s->stack[++s->top]=x; /*栈顶指针上移,数据元素入栈*/
         return TRUE;
        }
     }
    
     datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/
     {if(s->top<0)
       {printf("stack empty!\n"); /*栈空,返回空值*/
        return -1;
        }
      else
        {s->top--; 
         return(s->stack[s->top+1]);
         }
    }
     /*括号匹配检查算法。--遇到"("、"["、"{"时,将其压入 栈s中。请在下面写出匹配算
     法的函数原型,注意函数名、形参的个数、类型在main函数已给出*/    
     int judge(seqstack *s)
     {
    	 datatype symb,ch,store;
       push(s,'#');
       symb=getchar();/*从键盘接受字符*/
       while(symb!='#')
       {
          switch(symb)
          {
          case '(':
          case '[':
          case '{': push(s,symb);break;
          case ')':
    	               ch=pop(s);
    	               if(ch!='(') return FALSE;
    	               break;
          case ']':
    	               ch=pop(s);
    	               if(ch!='[') return FALSE;
    	              break;
           case '}':
    	              ch=pop(s);
    	              if(ch!='{') return FALSE;
    	              break;
           default:;
    
     }
             symb=getchar(); 
       }
       if(pop(s)=='#') return TRUE;
       else return FALSE;
    
     }
     
     
     
     
     
     
      
     int main()
     {char ch;
     seqstack q;
     setnull(&q);
     //printf("please input an express end with symbol '#':\n");
     if(judge(&q)) printf("yes\n"); 
      /*括号匹配,则输出yes*/
     else          printf("no\n");  
     /*括号不匹配,则输出no*/
      return 0;
     }
    
    

    任务三
    进制转换问题

    任务描述
    编写一个进制转换算法

    相关知识
    你需要掌握:
    1.为什么用到栈
    2.算法的实现。

    -为什么用到栈

    先来看一下十进制转二进制的计算过程。就以121为例,用 2 除 121,取余数,然后再用 2 去除得到的商,取余数……如此循环往复,直到商为零,将余数逆序输出即可得到 121 的二进制表示。
    具体过程,我这里就不赘述了。
    由于我们要将计算过程中产生的余数逆序输出,即121的二进制表示为:1111001,也就是先产生的余数要后输出,这恰恰符合栈的操作规则,所以当我们把该进制转换的算法实现为程序时,就可以用栈来存储计算过程中产生的余数序列。

    -算法的实现

    设被除数变量为m,要转换的进制数为N
    while(m不为0)
    {把m%N(即余数)入栈
    m=m/n}
    最后将栈中元素依次出栈可得到结果。

    测试说明

    平台会对你编写的代码进行测试:
    请输入一个十进制数m和要转换的进制数n:
    58 2
    111010

    请输入一个十进制数m和要转换的进制数n:
    50 8
    62

    • 示例代码如下:(温馨提示:本文全部代码只在 EduCoder 平台上通过测试,仅供参考,如有运行错误请自行改正)
    #include "stdio.h"
    #define MAXSIZE 100
    #define TRUE 1
    #define FALSE 0
    typedef int datatype;
    typedef struct    /*顺序栈的结构体类型定义*/
    {datatype stack[MAXSIZE];
     int top;
    }seqstack;
    
    /*置空栈-由于c语言的数组下
    标是从0开始的,所以置空栈操作时将栈顶指针放在下标为0之前,
    即-1处。*/
    void setnull(seqstack *s) 
    {s->top=-1;}               
    
    int empty(seqstack *s) /*判断当前栈是否为空栈*/
    {if(s->top<0)
         return TRUE; 
     else
         return FALSE;
     }
    
     int push(seqstack *s,datatype x) /*把元素x压入栈s中*/
     {if(s->top>=MAXSIZE-1)
       {printf("stack overflow!\n"); /*发生上溢*/
        return FALSE;
        }
       else
        {s->stack[++s->top]=x; /*栈顶指针上移,数据元素入栈*/
         return TRUE;
        }
     }
    
     datatype pop(seqstack *s) /*弹出当前栈s的栈顶元素*/
     {if(s->top<0)
       {printf("stack empty!\n"); /*栈空,返回空值*/
        return -1;
        }
      else
        {s->top--; 
         return(s->stack[s->top+1]);
         }
    }
     /*进制转换算法*--将十进制的m转换为n进制,请在下面写出进制转换函数的原型定义,
    提示:从main函数中的函数调用语句确定函数名、函数参数的个数和类型*/
     transform(seqstack *s,int m,int n)
     {
    	 int i=0,p,x;
    	
    	 while (m!=0)
        { p=m%n;
    	 push(s,p);
    	 m=m/n;
    	}
    	while (!empty(s))
    	{
    		x=pop(s);
    		printf("%d",x);
    	}
     }
    
      
     int main()
     {char ch;
     int m,n;
     seqstack q;
     setnull(&q);
     /*printf("请输入一个十进制数m和要转换的进制数n:\n");*/
     scanf("%d%d",&m,&n);
     transform(&q,m,n);/*调用进制转换函数进行调用*/
      return 0;
     }
    
    

    我把我目前写的关于数据结构 题目 的链接全部汇总整理在下面,有需要的小伙伴自己点击哈。

    实验:

    好了,关于栈的基本运算的相关实验差不多就是这样了。本文只是提供一种思路,可能会有更好、更简洁的代码,等着我们去思考探索。

    展开全文
  • 数据结构——的详解

    万次阅读 多人点赞 2020-04-20 00:02:43
    和队列是两种重要的线性结构,从数据结构的角度看,和...C语言和C++中的C语言中的栈栈的定义C语言中的基本操作的初始化判断是否为空栈判断是否为满栈入栈出栈C语言实现的具体代码C++中的C++中的基...
  • 堆与的区别

    万次阅读 多人点赞 2018-06-29 15:24:05
    堆(Heap)与(Stack)是开发人员必须面对的两概念,在理解这两概念时,需要放到具体的场景下,因为不同场景下,堆与代表不同的含义。一般情况下,有两层含义: (1)程序内存布局场景下,堆与表示的是...
  • 第三章 和队列 的实现

    千次阅读 多人点赞 2020-06-22 21:52:49
    第三章 和队列   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客 本文原创为亓官劼,请大家支持原创,部分平台... 初始化一个空栈S
  • 和队列

    2019-10-29 08:27:39
    1.的基本概念 的定义:是只允许在一端进行插入或删除的线性表 的相关名词 : 1. 栈顶:线性表允许进行插入和删除的那一端 2. 底:固定的不进行...S,x):进栈,若S未满,则将x加入使之成为新栈顶...
  • 目录基本概念:定义:基本操作:存储结构:顺序存储:判断栈空:进栈:出栈:读出栈顶元素:共享栈:链式存储:栈的应用:括号匹配:表达式求值:前缀表达式:中缀表达式后缀表达式...进栈:若栈未满,将 X 插入使...
  • StackEmpty(S) 判断一个栈是否为空,若为空则返回true,否则返回 false Push(&S,x) 进栈,若S未满,则将加入使之成为新栈顶。 Pop(&S,&x) 出栈,若非空,则弹出栈顶元素,并用x返回。 GetT
  • 在进行各类操作时,底指针固定不动,掌握空、栈满判断条件。 (2)实验内容 用顺序存储结构,实现教材定义的的基本操作,提供数制转换功能,将输入的十进制整数转换成二进制、八进制或十六进制。 (3)...
  • 数据结构 -- 和队列的实现及应用

    万次阅读 多人点赞 2018-09-06 18:04:39
    1、 1.1 的定义 1.2 的顺序存储结构实现 顺序的操作示意图如下: 顺序的实现如下: 1.3 的链式存储结构实现 链栈的操作示意图如下: 链栈的实现如下: 1.4 两种的效率分析 1.5 的应用 破...
  • 顺序的主要缺点在于难以预先估计准确的存储空间大小,因此需要余弦分配一个较大的空间,这可能造成存储空间的浪费;有时需要处理大量的数据,有可能造成预先分配的空间不够使用的问题。 为了充分使用存储空间,...
  • 的一些习题

    万次阅读 多人点赞 2016-04-19 15:43:35
    1.栈和队列具有相同的( )。 A.抽象数据类型 B.逻辑结构 C.存储结构 D.运算 2.栈是()。 A.顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D....A....C.判断栈是否为空 D.将栈置为空栈
  • /* ... *All right resvered . *文件名称: 后缀表达式.cpp *作 者: 郑兆涵 *和队列(一)——的实践(3)——... 问题:利用sqstack.h中的基本运算,实现将一个中缀表达式转换为对应的后缀表达式的算法。 编程代
  • 编写一个算法,检查一个程序中的花括号、方括号和圆括号是否配对,若全部配对,则返回1,否则返回0.对于程序中出现的对单引号或双引号内的字符不进行括号配对检查。39为单引号的ASCII值,34为双引号的ASCII值,单引号...
  • 1.栈的定义 1.栈:只允许在一端进行插入或删除操作的线性表。 2.栈顶:允许删除或插入的一端 3.栈底:不允许删除或插入的一端 ...Push()进栈,栈未满情况 Pop()出栈,栈非空 GetTop()读取栈...
  • 数据结构-和队列

    千次阅读 多人点赞 2021-03-10 16:58:15
    栈和队列 栈 定义: 只能在一端进行插入或删除操作的线性表 约束条件: 只能在一端进行插入或删除操作 一端: 可以插入或者删除元素的一端叫栈顶,另一端叫栈底 ...判断栈满: if(top==maxSize-1) return 1; 链
  • 第三章 和队列 队列

    千次阅读 多人点赞 2020-06-22 21:54:22
    第三章 和队列   大家好,我叫亓官劼(qí guān jié ),在CSDN中记录学习的点滴历程,时光荏苒,未来可期,加油~博客地址为:亓官劼的博客 本文原创为亓官劼,请大家支持原创,部分平台一直在盗取博主的...
  • ​ 2019王道《数据结构》——和队列 重点 (出入的过程、出栈序列的合法性)和队列的操作及其特征是重中之重。...StackEmpty(S): 判断一个栈是否为空,若S为空返回True,否则返回false Push(&S,x): 进栈...
  • 的定义: (堆栈)是种线性表,它的特点是仅允许在的一端进行插入、删除等操作。底固定,栈顶浮动。其特性为后进先出。一般中元素为0时,称为空栈。它有两种实现方式,顺序与链栈,下面将简单的...
  • C语言数组实现

    2020-08-06 22:51:36
    C语言数组实现 C语言数组形式实现 1.的定义 ​ 我们把允许插入和删除的一端称为栈顶,另一端称为底,不包含任何数据元素的称为... InitStack(*S):初始条件,建立一个空栈S; DestroyStack(*S):若
  • 与队列

    2017-03-23 22:16:01
    的定义 定义:(stack):是限定仅在表的一端进行插入或删除操作的线性表。 我们把允许插入和删除操作的一端称为栈顶(top),另一端称为底(bottom)。不含任何数据元素的称为空栈。又称为“后进...
  • 的C语言源码

    千次阅读 2015-08-21 14:34:08
    和队列是检索数据的种常用的数据结构。和队列是两种非常重要的数据结构,从数据结构来看,和队列也是线性表。是操作受限的线性表,只能在一端(栈顶)进行插入和删除,队列只能在一端(队尾)进行插入在另...
  • 3.和队列

    千次阅读 2017-08-03 14:07:15
    【考纲内容】(和队列的基本概念(二)和队列的顺序存储结构(三)和队列的链式存储结构(四)和队列的应用(五)特殊矩阵的压缩存储【知识框架】栈栈的基本概念(Stack):只允许在一端进行插入或...
  • 的定义定义:(stack):是限定仅在表的一端进行插入或删除操作的线性表。我们把允许插入和删除操作的一端称为栈顶(top),另一端称为底(bottom)。不含任何数据元素的称为空栈。又称为“后进先出...
  • 的应用 种先进后出(FILO)的数据结构 1.1 的操作实现 清空(clear): // 的清空操作就是把栈顶top置为-1 void clear(){ top=-1; } // 清空,由于没有直接用于清空栈的元素,所以使用while和pop...
  • 共享存储空间算法

    千次阅读 2017-12-26 07:50:37
    对于一个栈,我们只能经理设计出合适大小的数组进行处理,但是对于2个相同类型的,我们可以共享其存储空间,最大限度的利用事先开辟的存储空间进行操作。 关键思路:他们是数组的两端,向中间靠拢。top1和...
  • 【数据结构】两共享空间的进一步理解

    千次阅读 多人点赞 2019-01-03 23:03:55
    栈满条件的理解: 总结  前言 在阅读《大话数据结构》时,对文中“两共享空间”中部分知识点存在困惑,多读了几遍后,将其中的疑惑进行梳理一下。 (关于书中“两共享空间”的知识点,大家可以看一下我...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,528
精华内容 7,011
关键字:

判断一个栈为满的条件