《 큰소리 데이터 구 조 》 노트 - day 2

선형 표 의 순서 저장 구조
                           

순서 저장 구조의 세 가지 속성 을 설명 합 니 다. 1. 저장 공간의 시작 위치 2. 선형 표 의 최대 저장량 3. 선형 표 의 현재 길이
데이터 길이 와 선형 표 길이 의 차이
  • 배열 의 길 이 는 선형 표를 저장 하 는 저장 공간의 길이 로 보통 변 하지 않 는 다
  • .
  • 선형 표 의 길 이 는 선형 표 에서 데이터 요소 의 개 수 는 임 의 시간 에 선형 표 의 길 이 는 배열 의 길이
  • 보다 작 아야 한다.
    주소 계산 방법
    메모리 의 모든 저장 부 는 자신의 번 호 를 가지 고 있 는데 이 번 호 는 주소 계산 선형 표 의 위치 라 고 한다.
    LOC (ai + 1) = LOC (ai) + c (c 는 각 요소 가 사용 하 는 저장 장치) LOC (ai) = LOC (a1) + (i - 1) * c
    순차 저장 구조의 삽입 과 삭제
    삽입 알고리즘:
  • 삽입 위치 가 합 리 적 이지 않 으 면 이상 을 던진다
  • 선형 표 의 길이 가 배열 의 길이 보다 크 면 이상 또는 동적 증가 용량
  • 을 던진다.
  • 마지막 요소 부터 i 번 째 위치 로 옮 겨 다 니 며 각각 한 자 리 를 뒤로 이동 합 니 다
  • 위치 i 에 요 소 를 삽입 합 니 다
  • 시계 길이 플러스 1
  • 삭제 작업
  • 삭제 위치 가 불합리 하면 이상 던 지기
  • 삭제 요소 추출
  • 요소 의 위 치 를 삭제 하 는 것 부터 마지막 요소 의 위 치 를 옮 겨 다 니 며 각각 한 위 치 를 앞으로 이동 합 니 다
  • 표 장 감 1
  • 선형 표 의 순서 저장 구조:
  • 저장, 데 이 터 를 읽 을 때 어느 위치 든 시간 복잡 도 는 O (1)
  • 이다.
  • 삽입 또는 삭제 시 시간 복잡 도 는 모두 O (n) / / 최 악의 경우
  • 장단 점
    장점.
  • 표 에서 요소 간 의 논리 관 계 를 나타 내기 위해 추가 저장 공간 을 추가 할 필요 가 없다
  • 빠 른 액세스 표 의 어느 위치 에 있 는 요소
  • 결점.
  • 삽입 과 삭제 작업 은 대량의 요 소 를 이동 해 야 합 니 다
  • 선형 표 의 길이 변화 가 비교적 클 때 저장 공간의 용량
  • 을 확정 하기 어렵다.
  • 저장 공간 을 조성 하 는 '파편'
  • 선형 표 의 체인 식 저장 구조
  • 임의의 저장 장치 로 선형 표 의 데이터 요 소 를 저장 합 니 다. 이 저장 장 치 는 연속 일 수도 있 고 연속 되 지 않 을 수도 있 습 니 다.
  • 데이터 요소 정 보 를 저장 하 는 것 외 에 후계 요소 의 저장 주소 도 저장 해 야 한다
  • 구조
  • 데이터 필드: 데이터 요소 정 보 를 저장 하 는 필드
  • 포인터 필드: 직접 후계 위 치 를 저장 하 는 도 메 인, 포인터 필드 의 정 보 를 또는
  • 라 고 합 니 다.
  • 결점: 이 두 부분의 정 보 는 데이터 요 소 를 구성 하 는 저장 이미지 n 개의 노드 체인 이 하나의 링크 로 연결 되 는데 그것 이 바로 선형 표 의 체인 저장 구조 이다. 이 링크 의 모든 노드 에 하나의 지침 도 메 인 만 포함 되 어 있 기 때문에 헤드 포인터 라 고 한다. 링크 의 첫 번 째 노드 의 저장 위치 마지막 노드 는 NULL 또는 ^
  • 이다.
    두 결점: 단일 체인 표 의 첫 번 째 결점 앞 에 결점 을 부설 한다.
  • 정 보 를 저장 하지 않 아 도 된다
  • 선형 표 의 길이 등 도 저장 할 수 있다
  • 헤드 포인터
  • 헤드 포인터 란 체인 시계 가 첫 번 째 결점 을 가리 키 는 지침 을 말 하 는데 약 한 체인 시계 에 머리 결점 이 있 으 면 머리 결점 을 가리 키 는 지침
  • 을 말한다.
  • 헤드 포인터 가 표지 역할 을 하기 때문에 자주 헤드 포인터 에 링크 의 이름
  • 을 붙인다.
  • 체인 시계 가 비어 있 든 없 든 헤드 포인터 가 비어 있 지 않다.헤드 포인터 가 체인 시계
  • 두 결점
  • 두 결점 은 조작의 통일 과 편 의 를 위해 설립 된 것 으로 첫 번 째 원소 의 결점 에 놓 이기 전에 그 데이터 역 은 일반적으로 무의미 하 다
  • 두 결점 이 생 겼 다. 첫 번 째 요소 의 결점 전에 결점 을 삽입 하고 첫 번 째 결점 을 삭제 하면 그 조작 은 다른 결점 과 통일 된다
  • .
  • 두 결점 이 반드시 링크 의 필수 요소 가 아니다
  • 좋은 웹페이지 즐겨찾기