마인드 맵 갤러리 데이터 구조 - 선형 테이블
이것은 데이터 구조, 즉 선형 테이블, 스택 및 큐를 포함한 선형 테이블에 대한 마인드 맵입니다. 이는 모두 제한된 작업을 수행하는 선형 테이블입니다.
데이터 구조
데이터 구조 마인드 맵
데이터 구조 선형 테이블 스택 큐 지식 포인트 노트
데이터 구조 2장 - 선형 테이블
데이터 구조 및 알고리즘의 기본 개념
데이터 구조 선형 테이블
데이터 구조 코스 프레임워크
선형 구조
선형 테이블
정의: 동일한 데이터 유형을 갖는 n개의 데이터 요소로 구성된 유한한 시퀀스인 논리적 구조입니다.
순차 저장
시퀀스 테이블(논리적 시퀀스와 물리적 시퀀스가 동일함)
특징
무작위 접근, 쉽게 찾을 수 있음
높은 저장 밀도
추가하거나 삭제하는 것이 번거롭습니다
확장이 까다롭습니다(malloc은 시간 복잡도를 증가시킵니다).
실현 방법
정적 할당
고정 길이 배열을 정의하면 시스템이 자동으로 공간을 회수합니다.
동적 할당
malloc 및 free 함수 사용(쌍으로 표시)
기본 조작
끼워 넣다
최고 O(1), 최악 O(n), 평균 O(n)
삭제
찾다
비트별 검색
최고/최악/평균 O(1)
값으로 찾기
주요 시간 비용은 움직이는 요소에서 발생합니다.
체인 스토리지
연결리스트(논리적 순서와 물리적 순서가 동일할 필요는 없음)
낮은 저장 밀도
삽입과 삭제가 쉽다
유연한 저장
단일 목록
생성(삽입)
헤더 플러그인 방식 확립
에)
꼬리 삽입 방법 확립
테이블 길이 문의
카운터만 추가하세요
이중 연결 리스트
오(1)
단일 연결 리스트를 순회하는 대신 선행 포인터를 직접 찾아서 수정할 수 있습니다.
순환 연결 리스트
순환형 단일 연결 리스트
헤드 노드 L이 꼬리를 가리키므로 꼬리 작업의 시간 복잡도는 O(n)입니다.
순환 이중 연결 리스트
정적 연결리스트
배열로 구현된 연결 목록, 커서는 배열 첨자를 나타냅니다.
주요 시간 오버헤드는 요소 이동에서 발생하므로 실제 문제를 처리할 때는 연결 목록 삽입/삭제가 순차 목록보다 효율적입니다.
스택과 큐는 모두 제한된 작업을 수행하는 선형 테이블입니다.
스택
대기줄