数据结构学习总结——栈和队列算法设计题

本文主要是介绍数据结构学习总结——栈和队列算法设计题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一个位置r为队尾元素的位置 假定队列元素的个数小于n，计算队列中元素个数的公式？

解答：对于非循环队列来说，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能是负值 所以需要将差值加上MAXSIZE(本题是n),然后与MAXSIZE(本题是N)求余，即是(r-f+n)%n

(1)将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端 当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第一号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长 试编写双栈初始化，判断栈空，栈满，进栈，出栈等等算法的函数 双栈数据结构的定义如下所示

 `////-----栈的数据结构定义-----
   typedef struct
  {
         int top[2],bot[2];   ///栈顶和栈底指针
         SElemtype   *v;      //栈数组
         int m;              //栈最大可容纳元素个数
     }DblStack;`

   `///-----双栈的初始化-----
     int init()
     { S.top[0]=-1;     ///第0号栈为空
       S.top[1]=m;      ///第一号栈为空
       return 1;      ///初始化成功
       }  `      


    `////------判断栈空-------
       int Empty()
  {   return(S.top[0]==-1&&S.top[1]==m);   }` 

   `////-----入栈操作-----
     int push(Stack &s,int i,int x)////i为栈号，i=0表示左栈，i=1表示右栈，x是入栈元素 ，入栈成功返回1，失败返回0;
    { if(i<0||i>1)
      { count<<"栈号输入不对"<<endl;
         exit(0);
          }
     if(S.top[1]-S.top[0]==1)
        {count<<"栈已经满"<<endl; return(0);  }
     switch(i)   
       {  case 0: S.v[++S.top[0]]=x; return(1);       ///第零号栈入栈操作
           break;
          case 1：S.V[--S.top[1]]=x; }                ///第一号栈入栈操作            
           } `
  

    `////------出栈操作----------
        ElemType pop (Stack &s,int i)    ///退栈，i代表栈号 i=0表示左栈
       { if(i<0||i>1)
          { count<<"栈号输入不对"<<endl;
             exit(0); }
           Switch(i)
             {case 0: if(S.top[0]==-1)          ////判断栈是否为空能否出栈
                  {count<<"栈空"<<endl;return(-1); }
                  else 
                     return(S.V[S.top[0]--]);
              case 1: if(S.top[1]==m) 
                {count<<"栈空"<<endl;return(-1); }
                  else 
                     return (S.V[S.top[1]++]); }        
                     }`       

回文是指正读反读均相同的字符序列，如“abba"和"abdba"均是回文 但是"good"不是回文试写一个算法判断给定的字符序列是否为回文（提示：将一半字符入栈)

      `////-----回文判断------
         #define StackSize  100  //假定预分配的栈空间最多为100个元素
         typedef char DataType;   //假定栈元素的数据类型为字符
         typedef  Struct
         {DataType data[StackSize];
            int top;
         }SeqStack;        ///栈数据结构的定义
        int IsHuiwen (char *t)
          { //判断t字符向量是否为回文，若是返回1，不是返回0
            SeqStack S;
            int i,length;
            char temp;        ///temp存储暂时变量
            initStack(&S);
            length=strlength(t);  ///求向量长度
            for(i=0;i<length/2;i++)       
            push(&S,t[i]);    ///将一半的字符入栈
         while(!EmptyStack(&S))
           { ///每弹出一个字符与相应字符比较
              temp=Pop(&S);
              if(temp!=S[i])     
                   return 0; ///不等则返回0；
               else 
                    i++;}
                return 1;   ///比较完毕若相等则返回1

       }`

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针）以此编写相应的置空队列，判断队列是否为空 入队和出队等算法。

     `////------预定义链队的结构------
        typedef struct queuenode
          {  Datatype data;
             struct queuenode *next;
           } QueueNode;   //结点类型的定义
           typedef struct
           {   queueNode *rear;   ///只设一个指向队尾元素的指针
               }Linkqueue;`
              
      `///-----置空队--------
          void initQueue(LinkQueue *Q)
           {   ///置空队就是让头结点成为队尾元素
                  QueueNode *s;
                  Q.rear=Q.rear->next;   //将队尾指针指向头结点
                  while(Q.rear!=Q.rear->next)  ///当队列非空将队中元素逐个出队
                    { S=Q.rear->next;    ///S指向队尾元素
                      Q.rear->next=S->next;  //修改尾结点的指针域
                     delete S;    }    //回收结点空间
                     }`  
          
         `///----判队空-------
            int EmptyQueue (LinkQueue &Q)
            { //判断队空 当头结点的next指针 指向自己时为空队
                 return Q.rear->next->next==Q.rear->next;   }`        
                               
          `///----入队操作-----
           void EnQueue (LinkQueue &Q , Datatype x)
             {    //入队，也就是尾结点处插入元素
                  QueueNode *p=new QueueNode;  //申请新结点
                  p->data=x;
                  p->next=Q.rear->next;    ///初始化新结点并链入
                  Q.rear->next=p;
                  Q.rear=p;    //将尾指针移至新结点
                 }` 

           `////-------出队操作--------
              Datatype DeQueue (LinkQueue *Q)
                { //出队，把头结点之后的元素摘下
                   Datatype t;
                   QueueNode *p;      //定义下头结点
                  if(EmptyQueue(Q))
                    Error("Queue underflow");
                    p=Q.rear->next->next;//p指向将要摘下的结点
                    x=p->data;   //保存结点中的数据
                    if(p==Q.rear)           
                    {  //当队列中只有一个结点时，P结点出队后，要将队尾指针指向头结点
                        Q.rear=Q.rear->next;
                        Q.rear->next=p->next;  }
                    else 
                        Q.rear->next->next=p-next;  //摘下结点p
                        delete p; //释放被删除结点
                        return x;   }`

已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法

1. 求链表的最大整数

2. 求链表的结点个数

3. 求所有整数的平均值

       `///------求链表中的最大整数--------
          int GetMax(Linklist p)
          {   if(!p->next)
               return p->data;
              else 
                 { 
                  int max=GetMax(p->next);
                   return p->data>=max? p->data:max;
                   }
                 } `
   
   
        `///-----求链表的结点个数------- 
           int Getlength(Linklist p)
           {  if(!p->next)
                 return 1;
              else {
                   return Getlength(p->next) +1;
                      }
                   }`
                       
                
          `///-----求所有整数的平均值-------
             double GetAverage(Linklist p,int n)
           {  
              if(!p->next)
                 return p->data;
              else
                 {
                  double ave=GetAverage(p-next,n-1);
                    return (ave *(n-1)+p->data)/n;
                   }
                       }`

这篇关于数据结构学习总结——栈和队列算法设计题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！