체인 대기 열의 기본 조작

4236 단어 데이터 구조
1. 대기 열의 개념 --- 한 끝 에 만 데 이 터 를 삽입 하고 다른 한 끝 에서 데 이 터 를 삭제 하 는 특수 선형 표 만 허용 합 니 다.
                            삽입 작업 을 하 는 한 끝 을 파티 끝 이 라 고 합 니 다 (대기 열 에 들 어 갑 니 다)
                            삭제 작업 을 진행 하 는 한 끝 을 파티 헤드 라 고 합 니 다 (대기 열 밖으로)
                            대기 열 은 선진 선 출 (FIFO) 의 특성 을 가지 고 있다.
2. 대열 의 성질 --- 대 미 삽입, 대 두 산 삭제
3. 대기 열 저장 구조
순서 대기 열 --- 팀 헤드 포인터 가 움 직 이지 않 고 대량의 요 소 를 옮 겨 야 합 니 다.
                      팀 헤드 포인터 이동, 가짜 넘 침 존재
가짜 넘 침: 순서 대기 열 은 여러 번 대기 열 에 들 어가 거나 대기 열 작업 을 한 후에 나타 나 는 저장 공간 이 있 지만 더 이상 대기 열 작업 을 할 수 없 는 넘 침 입 니 다. 순서 대기 열 최대 저장 공간 이 가득 차 있 고 대기 열 작업 을 요구 하 는 데 발생 하 는 넘 침 입 니 다.가짜 넘 침 을 해결 하 는 방법 은 순환 대기 열 입 니 다. 머리 와 끝 이 연결 되 는 순서 로 대기 열 을 저장 하 는 것 입 니 다.그러나 순환 대기 열 은 배열 이 넘 칠 수 있 는 문제 에 직면 하고 있 습 니 다. 그러면 순환 대기 열 은 대기 열 이 비어 있 고 꽉 찬 것 을 어떻게 판단 합 니까?
  • 저장 소 를 하나 덜 사용 합 니 다
  • 표지 판 설정
  • 카운터 설정
  •  
    //.h
    ​
    ​
    #pragma once//          
    
    #include
    #include
    #include
    #include
    
    typedef int DataType;
    typedef struct Node
    {
     DataType _data;//       
     struct Node* _pNext;//       
    }Node,*pNode;
    typedef struct Queue
    {
     pNode _pHead;//       
     pNode _pTail;//       
    }Queue;
    void QueueInit(Queue* q);//      
    pNode BuyNode(DataType data);//     
    void QueuePush(Queue* q, DataType data);//   
    void QueuePop(Queue* q);//   
    DataType QueueFront(Queue* q);//     
    DataType Queueback(Queue* q);//     
    int QueueSize(Queue* q);//          
    int QueueEmpty(Queue* q);//        
    
    ​
    
    ​

    //Queue.c
    ​
    #define _CRT_SECURE_NO_WARNINGS 1
    #include"Queue.h"
    //      
    void QueueInit(Queue* q)
    {
     assert(q);
     q->_pHead = NULL;
     q->_pTail = NULL;
    }
    //     
    pNode BuyNode(DataType data)
    {
     pNode pNewNode = (pNode)malloc(sizeof(Node));
     if (NULL == pNewNode)
     {
      return NULL;
     }
     else
     {
      pNewNode->_data = data;
      pNewNode->_pNext = NULL;
     }
     return pNewNode;
    }
    //   (     )
    void QueuePush(Queue* q, DataType data)
    {
     assert(q);
     pNode pNewNode = BuyNode(data);
     if (NULL == q->_pTail)//     ,           
     {
      q->_pHead = pNewNode;
      q->_pTail = pNewNode;
     }
     else
     {
      q->_pTail = q->_pTail->_pNext;
      q->_pTail = pNewNode;
     }
    }
    //void QueuePrint(Queue* q)//    
    //{
    // while (q->_pHead)
    // {
    //  printf("%d-->", q->_pHead->_data);
    //  q->_pHead = q->_pHead->_pNext;
    // }
    // printf("NULL
    "); //} // void QueuePop(Queue* q) {  assert(q);  if (NULL == q->_pHead)  {   return;  }  //  if (NULL == q->_pHead->_pNext)  {   q->_pHead = NULL;   free(q->_pHead);   return;  }  //  else  {   q->_pHead = q->_pHead->_pNext;  }  free(q->_pHead->_pNext);  q->_pHead->_pNext = NULL; } // DataType QueueFront(Queue* q) {  assert(q);  return q->_pHead->_data; } // DataType Queueback(Queue* q) {  assert(q);  return q->_pTail->_data; } // int QueueSize(Queue* q) {  assert(q);  int count = 0;  while (q->_pHead)  {   count++;   q->_pHead = q->_pHead->_pNext;  }  return count; } // int QueueEmpty(Queue* q) {  if (NULL == q)  {   return 0;  }  return 1; } ​

    //test.c
    ​
    #define _CRT_SECURE_NO_WARNINGS 1
    #include"Queue.h"
    void testQueuePush()
    {
     Queue q;
     QueueInit(&q);
     QueuePush(&q, 1);
     QueuePush(&q, 2);
     QueuePush(&q, 3);
     QueuePush(&q, 4);
     QueuePush(&q, 5);
    }
    void testQueuePop()
    {
     Queue q;
     QueueInit(&q);
     QueuePush(&q, 1);
     QueuePush(&q, 2);
     QueuePush(&q, 3);
     QueuePush(&q, 4);
     QueuePush(&q, 5);
     QueuePop(&q);
     QueuePop(&q);
    }
    void testQueue()
    {
     Queue q;
     QueueInit(&q);
     QueuePush(&q, 1);
     QueuePush(&q, 2);
     QueuePush(&q, 3);
     QueuePush(&q, 4);
     QueuePush(&q, 5);
     printf("%d
    ", QueueFront(&q));//  printf("%d
    ", Queueback(&q));//  printf("%d
    ", QueueSize(&q));//  printf("%d
    ", QueueEmpty(&q));// } int main() {  //testQueuePush();//  //testQueuePop();//  testQueue();  system("pause");  return 0; } ​

    좋은 웹페이지 즐겨찾기