데이터 구조 연구 노트 - 선형 표

1. 선형 표 의 정의
선형 표 는 같은 특성 요 소 를 가 진 유한 한 서열 이다.
함 유 된 요소 개수 = 선형 표 길이.
2. 선형 표 의 논리 적 특성
하나의 표 두 요소 만 있 고 하나의 표 미 요소 만 있 으 며 표 두 요 소 는 전구 가 없고 표 미 요 소 는 후계 가 없 으 며 다른 요 소 는 하나의 직접 전구 만 있 고 하나의 직접 후계 만 있다.
3. 선형 표 의 저장 구조
(1) 순서 저장 구조 (순서 표)
  • 무 작위 접근 특성
  • 연속 적 인 저장 공간 을 차지 해 야 한다
  • 삽입 작업 을 할 때 여러 요 소 를 이동 해 야 합 니 다
  • (2) 체인 식 저장 구조 (링크)
  • 무 작위 접근 은 지원 되 지 않 습 니 다
  • 결점 의 저장 공간 이 용 률 은 순서 표 보다 약간 낮다 (각 결점 은 일부 공간 을 그 어 다음 결점 위 치 를 가리 키 는 지침 을 저장 해 야 한다)
  • 저장 공간의 동적 분 배 를 지원 합 니 다
  • 삽입 작업 은 이동 요소 가 필요 하지 않 습 니 다
  • 링크 의 다섯 가지 형식:
    1) 싱글 체인 리스트
    ① 앞장 서 는 노드 의 단일 체인 표: 헤드 노드 는 정 보 를 저장 하지 않 고 (링크 의 속성 을 설명 하 는 정보 만 저장 하고 표 의 길이 와 같이) 표지 로 만 한다.헤드 포인터 헤드 가 헤드 노드 를 가리 키 며 NULL 과 같 지 않 습 니 다. head - > next 가 NULL 과 같 을 때 링크 가 비어 있 습 니 다.
    ② 앞장 서지 않 는 단일 체인 시트: 모든 노드 에 정 보 를 저장 합 니 다.헤드 포인터 헤드 는 시작 점 을 가리 키 며 헤드 가 NULL 과 같 을 때 링크 가 비어 있 습 니 다.
    노드 정의:
    typedef struct LNode
    {
       int data;               //data        
       struct LNode *next;     //         
    }LNode;                    //         

    2) 더 블 링크
    더 블 체인 시 계 는 단말기 결점 에서 시작 지점 까지 역방향 으로 걸 어 갈 수 있다.바로 단일 체인 표 노드 에 포인터 필드 를 추가 하여 현재 노드 의 앞 구 조 를 가리 키 는 것 입 니 다.
    노드 정의:
    typedef struct DLNode
    {
       int data;               //data        
       struct DLNode *prior;   //         
       struct DLNode *next;    //         
    }DLNode;

    3) 순환 싱글 체인 시트
    단일 체인 시트 의 마지막 포인터 영역 (빈 포인터) 을 링크 의 첫 번 째 노드 로 가리 킵 니 다.
    4) 순환 더 블 링크
    더 블 링크 단말기 결산 점 의 next 지침 을 링크 의 첫 번 째 결산 점 을 가리 키 고 링크 의 첫 번 째 결산 점 의 prior 지침 을 단말기 결산 점 을 가리킨다.
    아래 네 마디 중 임의의 한 마디 가 진실 이 라면 순환 쌍 링크 가 비어 있다 고 판단 할 수 있다.
    head->next==head;
    head->prior==head;
    head->next==head && head->prior==head;
    head->next==head || head->prior==head;

    5) 정적 링크
    일반 링크 노드 공간 은 전체 메모리 에서 나 오고 정적 링크 는 하나의 구조 체 배열 에서 나온다.

    좋은 웹페이지 즐겨찾기