데이터 구조 알고리즘 - 단일 체인 테이블 및 그 조작

단일 체인 표 는 매우 자주 사용 하 는 데이터 구조 로 간단 하지만 관련 조작 은 실 수 를 하기 쉽다.본 고 는 단일 체인 테이블 의 몇 가지 조작 을 소개 할 것 이다. 주로 체인 테이블 의 반전, 체인 테이블 의 정렬 을 포함 하고 체인 테이블 의 꼴찌 k 개 값 을 구하 고 현재 노드 를 삭제 하고 체인 테이블 의 중간 노드 를 찾아낸다.더 많은 내용 은 다음 링크 를 참고 할 수 있 습 니 다.
https://www.61mon.com/index.php/archives/179/
단일 체인 테이블 노드 구조
단일 체인 표 의 노드 구 조 를 다음 과 같이 정의 합 니 다.

/*         */
struct Node
{
    int data;
    Node * next;
    Node() { data = 0; next = nullptr; }
};

/*       */
Node * header = new Node;

링크 반전
링크 반전 은 면접 필기시험 에서 흔히 볼 수 있 는 문제 형 으로 반전 과정 에서 중단 되 지 않도록 주의해 야 한다.예시: 1 - > 2 - > 3 - > 4 - > 5;반전 후: 5 - > 4 - > 3 - > 2 - > 1 반전 과정 에서 두 바늘 이 동시에 이동 합 니 다. 구체 적 인 코드 는 다음 과 같 습 니 다.

/*      */
void reverse(Node * header)
{
    if(!header->next || !header->next->next)//          
        return;

    Node* cur = header->next;//         
    Node* pre = nullptr;

    while(cur)
    {
        Node* tmp = cur->next;//      
        cur->next = pre;//      
        pre = cur;//pre      
        cur = tmp;//cur      
    }

    header->next = pre;//              
}

링크 정렬
정렬 은 빠 른 정렬 사상 을 사용 하여 두 개의 포인터 i 와 j 만 설정 하면 됩 니 다. 이 두 바늘 은 모두 next 방향 으로 이동 합 니 다. 이동 하 는 과정 에서 구간 [1, i] 의 data 는 모두 base (위치 0 은 주 원) 보다 작 고 구간 [i + 1, j) 의 data 는 모두 base 보다 크 면 j 가 끝까지 갈 때 지점 찾기 를 완성 합 니 다.

/**
 *       
 * 
 * begin         ，  header->next
 * end              next
 */
void asc_sort(Node * begin, Node * end)
{
    if(!begin || !begin->next)//            
        return;

    int base = begin->data;//     
    Node* i = begin;       // i       base
    Node* j = begin->next; // i   j       base

    while(j!=end)
    {
        if(j->data<base)
        {
            i = i->next;
            swap(i->data, j->data);
        }
        swap(i->data, begin->data);  //       i   
    }
    //
    asc_sort(begin, i);     //     
    asc_sort(i->next, end); //     
}

//    
asc_sort(header->next, nullptr);

링크 마지막 k 번 째 값 구하 기
링크 의 길 이 는 알 수 없 기 때문에 처음부터 링크 를 스 캔 한 후에 링크 의 길 이 를 얻 은 다음 에 처음부터 마지막 k 번 째 수 를 찾 을 수 있 습 니 다. 이런 방법 은 가장 직관 적 이지 만 시간 복잡 도가 비교적 높 습 니 다. 우 리 는 k 가 링크 의 길이 보다 작다 고 가정 하면 우 리 는 두 개의 포인터 p 와 q 를 설정 할 수 있 습 니 다. 이 두 개의 지침 이 링크 에서 의 거 리 는 k 입 니 다. 그러면 뒤에 있 는 지침 이 링크 까지 걸 어 갈 수 있 습 니 다.끝의 nullptr 일 때 다른 지침 은 링크 의 마지막 k 번 째 값 을 가리 킬 것 입 니 다.

/*        k   */
int kth_last(Node * header, int k)
{
    Node* p = header->next;
    Node* q = header->next;
    for(int i=0;i<k;i++)
    {
        if(!q)
            return -1; //      k

        q = q->next;
    }

    while(q)
    {
        p = p->next;
        q = q->next;
    }

    return p->data;
}

현재 노드 삭제
노드 삭제 요구 시간 평균 복잡 도 O (1)이렇게 하면 링크 를 스 캔 하여 현재 노드 의 이전 노드 를 가 져 올 수 없습니다. 포인터 가 현재 노드 의 이전 노드 에서 현재 노드 의 다음 노드 를 가리 키 지 못 하 는 이상 현재 노드 의 값 을 다음 노드 의 값 으로 바 꾸 고 다음 노드 를 삭제 합 니 다. 마지막 노드 를 삭제 하 는 경우 다음 절 이 없 기 때문에 주의해 야 합 니 다.점, 그러므로 이전 노드 를 찾 아야 하고 링크 를 스 캔 해 야 합 니 다.

/*        */
void del(Node * header, Node * position)
{
    if(!position->next)  //            
    {
        Node* p = header;
        while(p->next!=position)
            p = p->next;    //    position       

        p->next = nullptr;
        delete position;
    }
    else
    {
        Node* p = position->next;
        swap(position->data, p->data);
        position->next = p->next;
        delete p;
    }
}

링크 의 중간 노드 를 찾아내다.
마지막 k 개의 수 를 찾 는 조작 을 통 해 우 리 는 비슷 한 두 개의 지침 으로 조작 할 것 을 생각 할 수 있다. 여 기 는 빠 르 고 느 린 지침 을 사용 하고 느 린 지침 이 가 는 길 이 는 빠 르 고 느 린 지침 이 서로 떨 어 지 는 정도 와 같 기 때문에 이 성질 을 이용 하여 빠 른 지침 이 링크 끝 에 이 르 렀 을 때 느 린 지침 은 바로 중간 에 결점 이 있다.

/*            */
Node * find_middle(Node * header)
{
    Node* p = header;
    Node* q = p;
    while(q->next->next && p->next)
    {
        p = p->next;        //       
        q = q->next->next;  //       
    }

    return p;
}