DS-HW-Chap3

• 注①：DS-HW均选自严蔚敏版习题册
• 注②：本人习惯使用C++，但并未使用模板与类，除了new与delete，与课程所授C无异，可放心食用。

3.28

• 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。

• 以下为算法部分代码实现：

• 诶，就是不写注释(^▽^)

  typedef struct Node *pNode;
  struct Node {
      int data;
      pNode next;
  };
  typedef pNode Position;
  
  typedef struct Queue *pQueue;
  struct Queue {
      Position rear;
  };
  
  pQueue createQueue(){
      pQueue Q = new Queue;
      Q->rear = NULL;
      return Q;
  }
  
  void enQueue(pQueue Q, int x){
      Position p = new Node;
      p->data = x;
      if(Q->rear == NULL){
          p->next = p;
          Q->rear = p;
      }
      else{
          p->next = Q->rear->next;
          Q->rear->next = p;
          Q->rear = p;
      }
  }
  
  int deQueue(pQueue Q){
      if(Q->rear == NULL){
          cout << "Queue is empty!" << endl;
          return -1;
      }
      else{
          Position p = Q->rear->next;
          int x = p->data;
          if(Q->rear == p){
              Q->rear = NULL;
          }
          else{
              Q->rear->next = p->next;
          }
          delete p;
          return x;
      }
  }

  3.29

  • 如果希望循环队列中的元素都能得到利用，则需设置一个标志域 tag，并以 tag 的值为 0 和 1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。

  • 以下为算法部分代码实现：

  • 还是没有注释哦~

    typedef int Position;
    typedef struct Queue *pQueue;
    struct Queue {
        int *data;
        Position front, rear;
        int maxSize;
        int tag;
    };
    
    pQueue createQueue(int maxSize){
        pQueue Q = new Queue;
        Q->data = new int[maxSize];
        Q->front = Q->rear = 0;
        Q->maxSize = maxSize;
        Q->tag = 0;
        return Q;
    }
    
    void enQueue(pQueue Q, int x){
        if((Q->rear + 1) % Q->maxSize == Q->front && Q->tag == 1){
            cout << "Queue is full!" << endl;
            return;
        }
        else{
            Q->data[Q->rear] = x;
            Q->rear = (Q->rear + 1) % Q->maxSize;
            Q->tag = 1;
        }
    }
    
    int deQueue(pQueue Q){
        if(Q->front == Q->rear && Q->tag == 0){
            cout << "Queue is empty!" << endl;
            return -1;
        }
        else{
            int x = Q->data[Q->front];
            Q->front = (Q->front + 1) % Q->maxSize;
            Q->tag = 0;
            return x;
        }
    }

  • 这次的作业到这里就结束啦，有什么想说的欢迎在评论区留言~