데이터 구조지식 포인트순환 링크 & 더 블 링크

1460 단어
1. 순환 링크
단일 체인 표 와 대체적으로 다 르 지 않 지만 다음 과 같은 두 가지 주의 가 필요 합 니 다. (1) 마지막 노드 의 지침 도 메 인 은 반드시 머리 결점 을 가리 켜 야 순환 할 수 있 습 니 다. (주의, 데이터 가 저 장 된 첫 번 째 노드 가 아 닌 데이터 헤드 결점 을 가리 키 는 것 을 가리 키 는 것 입 니 다)
(2) 머리핀 이 아 닌 꼬리 지침 을 사용 하여 체인 시 계 를 표시 합 니 다. 이렇게 머리 결점 과 꼬리 결점 을 찾 는 시간 복잡 도 는 O (1) 입 니 다.
2. 더 블 링크 정의
//    ，                    
typedef struct Node
{
    elemType data;
    Node *prior,*next;  
};

typedef Node *List;

3. 더 블 링크 만 들 기
여기 서 주의해 야 할 것 은 링크 가 비어 있 는 것 은 머리 결점 의 전구 지침 과 후계 지침 이 모두 자신 을 가리 키 는 것 이다.따라서 결점 을 만 들 거나 삽입 할 때 머리 결점 의 전구 지침 을 마지막 결점 으로 수정 하 는 것 을 기억 해 야 한다.
4. 삽입 및 삭제
삽입: 삽입 위 치 를 찾 고 전구 결점 과 후계 결점 을 수정 하 는 지침
bool insert(List &l,int i,elemType e)
{
    Node *p,*q,*s;
    int j;

    p = l->next;
    
    //       
    for(j = 1;jnext;
    }
    
    s = (Node *)malloc(sizeof(Node));
    s->data = e;
     
    s->prior = p->prior;
    s->next = p;
    
    //            
    p->prior->next = s;
    //            
    p->prior = s;   
}

삭제: 삭제 노드 를 찾 아 전구 결점 을 수정 하 는 후계 지침, 후계 결점 의 전구 지침 을 찾 습 니 다.
bool deleteNode(List &l,int i)
{
    Node *p;
    int j;
    
    p = l->next;
    
    for(j = 1;jnext;
    }
    
    //            
    p->prior->next = p->next;
    //            
    p->next->prior = p->prior;
    //     
    free(p);
}
데이터베이스 마스터링 - 중첩 레코드 액세스 - 시리즈 #10
음수 의 이 진 표시

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

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