단일 체인 테이블 에서 O (1) 시간 복잡 도 삭제 노드 실현

1816 단어 데이터 구조
단일 체인 테이블 에서 O (1) 시간 복잡 도 삭제 노드 실현
링크 노드
struct LinkNode
{
    datatype data;
    LinkNode* next;
}

단일 체인 표 의 특정한 노드 를 삭제 할 때 가장 쉽게 생각 할 수 있 는 방법 은 먼저 삭제 할 점 p 의 이전 노드 q 를 찾 고 이 전구 노드 포인터 필드 의 값 을 이용 하여 p 의 위 치 를 확인 하 는 것 이다.그리고 아래 문장 을 사용 하여 노드 p 를 삭제 합 니 다.
p=p->next;

그러나 이 방법 은 p 의 전구 노드 를 찾 아야 하기 때문에 시간 복잡 도 O (n) 를 옮 겨 다 닌 다.
시간 복잡 도 O (1) 로 같은 삭제 효 과 를 낼 수 있 는 방법 을 소개 한다.이것 은 삭제 할 노드 p 만 알 고 삭제 할 노드 의 후계 노드 p - > next 를 알 수 있 습 니 다. 우 리 는 후계 노드 를 이용 하여 현재 삭제 할 노드 (후계 노드 가 데이터 구조 단위 로 이동) 를 덮어 쓰 는 방법 으로 이 노드 를 삭제 하 는 효 과 를 실현 할 수 있 습 니 다.
void DeleteNode(&LinkNode* Head，&LinkNode* Deleted)
{
    if(&Deleted->next!=NULL)
    {
        LinkNode* Next=Deleted->next；
        Deleted->next=Next->next；
        Deleted->data=Next->data；

        free(Next)；
    }

}
데이터 구조 vector ~ 기본 조작
Qt 노트14

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage