순서 저장 구조의 세 가지 속성 을 설명 합 니 다. 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 또는 ^
이다. 두 결점: 단일 체인 표 의 첫 번 째 결점 앞 에 결점 을 부설 한다.
정 보 를 저장 하지 않 아 도 된다
선형 표 의 길이 등 도 저장 할 수 있다
헤드 포인터
헤드 포인터 란 체인 시계 가 첫 번 째 결점 을 가리 키 는 지침 을 말 하 는데 약 한 체인 시계 에 머리 결점 이 있 으 면 머리 결점 을 가리 키 는 지침
을 말한다.
헤드 포인터 가 표지 역할 을 하기 때문에 자주 헤드 포인터 에 링크 의 이름
을 붙인다.
체인 시계 가 비어 있 든 없 든 헤드 포인터 가 비어 있 지 않다.헤드 포인터 가 체인 시계
두 결점
두 결점 은 조작의 통일 과 편 의 를 위해 설립 된 것 으로 첫 번 째 원소 의 결점 에 놓 이기 전에 그 데이터 역 은 일반적으로 무의미 하 다
두 결점 이 생 겼 다. 첫 번 째 요소 의 결점 전에 결점 을 삽입 하고 첫 번 째 결점 을 삭제 하면 그 조작 은 다른 결점 과 통일 된다
.
두 결점 이 반드시 링크 의 필수 요소 가 아니다
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
