데이터 구조 학습 기록 (7) - 체인 대기 열

순서 저장 대기 열 에 가짜 넘 치 는 현상 이 나타 나 기 때문에 순환 대기 열 로 개선 되 지만 순환 대기 열 에 도 공간 이 원활 하지 않 은 문제 (순서 구조의 통폐) 가 존재 합 니 다. 즉, 저장 공간 (배열 정의 가 너무 큰) 을 낭비 할 때 도 있 고 공간 이 부족 할 때 도 있 습 니 다 (배열 정의 가 너무 작 습 니 다).
그래서 체인 대기 열 이 나 타 났 습 니 다.
단일 체인 시트 로 정 의 된 헤드 포인터 가 존재 하 는 대기 열 을 보 여 줍 니 다.
내 가 쓴 코드 는 다음 과 같다.

#ifndef CIRCLE_H
#define CIRCLE_H

typedef int ElemType;

//      
typedef struct LinkQueueNode
{
    ElemType data;
    Node next;
} LinkNode,*Node;

//      
struct LinkQueue
{
    Node rear,front;
};

//     
void InitLinkQueue(LinkQueue &Q)
{
    Q.rear=Q.front=(Node)malloc(sizeof(LinkNode));//     
    Q.rear->next=null;
}

//  
bool LinkQueueEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
        return true;
    else
        return false;
}

//  
bool EnLinkQueue(LinkQueue &Q,ElemType x)
{
    Q.rear->next=(Node)malloc(sizeof(LinkNode)); //                 next  
    if(Q.rear->next)                             //         
    {
        Q.rear=Q.rear->next;                     //        
        Q.rear->next=null;                       //    next    
        return true;
    }
    else                                         //      ，      
    {
        cout<next->data;                   //        
        Node p;
        p=Q.front->next;                         //p      
        if(p->next)                              //            
        {
            Q.front->next=p->next;               //   ，      p->next
        }
        else
        {
            Q.rear=Q.front;                      //  ，          
            Q.front->next=null;                  //      next    
        }
        free(p);                                 //  p    （     ）
    }
}

//     
bool GetLinkQueueHead(LinkQueue Q,ElemType &x)
{
    if(LinkQueueEmpty())
        return false;
    else
    {
        x=Q.front->next->data;
        return true;
    }
}


#endif

체인 대기 열 이 꽉 찬 상황 이 나타 나 지 않 으 면 동적 으로 메모 리 를 신청 하여 공간의 낭 비 를 초래 하지 않 지만 지침 을 저장 할 추가 공간 이 필요 하고 지침 설정 이 무시 되면 출입 팀 의 조작 시간 지출 이 급증 하 는 것 이 단점 이다.
이 대기 열 은 순환 링크 를 사용 하거나 양 방향 링크 등 다른 링크 구 조 를 사용 하여 실현 할 수 있다.
흔히 볼 수 있 는 데이터 구조 시험 문제 에서 흔히 볼 수 있 는 문 제 는 특정한 링크 구조 (단일 양 방향 과 순환 여부, 그리고 서로 다른 지침 이 존재 하 는 각종 조합) 를 제시 하고 특정한 데이터 구조 에 적합 하 냐 고 물 으 면 데이터 구조 에 필요 한 조작 과 결합 하여 이 물리 구조 가 완성 되 거나 완 성 된 시간 지출 이 합 리 적 인지 판단 해 야 한다.
예 를 들 어 대기 열 에 있어 체인 식 저장 소 를 사용 하면 표 두 위 치 는 팀 의 머리 위치 이 고 표 꼬리 위 치 는 팀 의 꼬리 위치 이다.대기 열 에서 진행 해 야 할 일반적인 작업 은 팀 에서 나 오 는 것 (팀 에서 요 소 를 삭제 하 는 것) 과 팀 에 들 어 가 는 것 (표 끝 에 요 소 를 추가 하 는 것) 입 니 다.

입단 작업 에 있어 체인 구조 에서 현재 끝 점 을 알 아야 합 니 다. 끝 점 의 next 를 새로 추 가 된 노드 주소 로 설정 하고 rear (꼬리 포인터) 를 rear - > next (새 노드 주소) 로 설정 한 다음 에 새로운 노드 next 를 비 웁 니 다.그래서 가장 좋 은 상황 은 단일 체인 표 에 팀 꼬리 포인터 나 양 방향 순환 대기 열 에 머리 나 꼬리 포인터 가 존재 하 는 것 이다 (상수 차 조작 을 통 해 끝 점 주 소 를 얻 을 수 있다) 등 이다.(꼬리 포인터 가 존재 하지 않 으 면 머리 포인터 에 만 저 장 된 단일 체인 시트 도 입 대 를 실현 할 수 있 지만 O (n) 시간 복잡 도가 있어 야 팀 의 꼬리 주 소 를 얻 을 수 있 습 니 다.)

팀 에서 나 오 는 작업 에 있어 체인 구조 에서 헤드 노드 주소 (헤드 노드 가 존재 하 는 체인 식 대기 열) 를 알 고 팀 헤드 요소 의 노드 (비 헤드 노드) 주 소 를 저장 한 다음 에 헤드 노드 의 next 는 두 번 째 요소 의 노드 (존재 하지 않 으 면 비어 있 고 단일 링크 가 있 으 면 rear 포인터 가 머리 노드 를 가리 키 는 동시에) 를 가리 키 고 팀 헤드 요 소 를 출력 해 야 한다.free 팀 헤드 요소 결점.그래서 가장 좋 은 상황 은 단일 체인 표 에 헤드 포인터 (헤드 요소 가 아 닌 헤드 노드 를 가리 키 는 것) 가 존재 하거나 단 방향 순환 체인 표 에 꼬리 포인터 가 존재 하거나 양 방향 체인 표 에 가리 키 는 노드 포인터 나 가리 키 는 헤드 요소 의 노드 포인터 가 존재 하거나 양 방향 순환 체인 표 에 머리 / 꼬리 / 첫 번 째 요소 의 노드 포인터 가 존재 하 는 등 이다.(가리 키 는 노드 포인터 가 존재 하지 않 는 단일 체인 시 계 는 팀 작업 을 완성 할 수 없습니다.)