오늘부터 겨울방학 의 필기 생활 을 시작한다.본 약 재 는 기 말 세례 를 받 은 후에 컴퓨터 학과 수업 을 계속 하기 시 작 했 습 니 다. 곧 춘수 에 참가 할 것 이기 때문에 가장 기본 적 이 고 가장 중요 한 데이터 구조 부터 복습 합 니 다.예전 에 필기시험 산법 문 제 를 풀 때 손 에 익 은 편 이 라 고 생각 했 지만 기초 가 튼튼 하지 않 은 부분 이 있다 고 생각 하여 왕도 대학원 에 진학 하 는 데이터 기 구 를 이용 하여 기 초 를 다 졌 습 니 다. 면접 에서 더욱 잘 표현 되 기 를 바 랍 니 다. 그 다음 에 에서 익숙 하지 않 은 문 제 를 위 에 올 릴 수도 있 습 니 다. 쓸데없는 소리 하지 말고 제1장 의 기본 개념 1. 데이터 구조의 기본 개념 기본 개념 과 용어
데이터 데 이 터 는 정보의 매개체 로 객관 적 인 사물 속성 을 묘사 하 는 수, 문자 와 컴퓨터 에 입력 되 고 컴퓨터 프로그램 에 의 해 식별 되 고 처리 되 는 모든 기호의 집합 이다.
데이터 요소 데이터 요 소 는 데이터 의 기본 단위 로 전체적으로 고려 하고 처리한다.하나의 데이터 요 소 는 몇 개의 데이터 항목 으로 구성 할 수 있다.데이터 항목 은 데이터 요 소 를 구성 하 는 불가 분 의 최소 단원 이다.예 를 들 어 학생 기록 은 하나의 데이터 요소 로 학 번, 성명, 성별 등 데이터 항목 으로 구성 된다.
데이터 대상 데이터 대상 은 같은 성질 을 가 진 데이터 요소 의 집합 으로 데이터 의 서브 집합 이다.예 를 들 어 정수 데이터 대상 은 집합 {0, + - 1, + - 2...}
데이터 형식 데이터 형식 은 하나의 값 의 집합 과 정의 입 니 다. 이 집합 에서 이전 작업 의 총칭
원자 유형: 그 값 은 다시 나 눌 수 없다
구조 유형: 그 수 치 는 몇 가지 성분
으로 나 눌 수 있다.
추상 적 인 데이터 유형: 추상 적 인 데이터 조직 과 이와 관련 된 조작
추상 데이터 형식 (ADT) ADT 는 수학 모델 과 이 모델 에 정 의 된 조작 을 말한다.추상 적 인 데이터 유형의 정 의 는 그의 논리 적 특성 에 만 달 려 있 고 컴퓨터 내부 에서 어떻게 실현 하고 표현 하 는 지 와 무관 하 다. 내부 구조 가 어떻게 변화 하 든 그의 수학 적 특성 이 변 하지 않 으 면 외부 사용 에 영향 을 주지 않 는 다.일반적으로 (데이터 대상, 데이터 관계, 기본 조작 집합) 과 같은 3 원 그룹 으로 추상 적 인 데이터 형식
을 나타 낸다.
데이터 구 조 는 그 어떠한 문제 에서 도 데이터 요 소 는 독립 적 으로 존재 하지 않 고 그들 사이 에 특정한 관계 가 존재 하 는데 이런 데이터 요소 간 의 관 계 는 구조 가 된다.데이터 구 조 는 서로 한 가지 또는 여러 가지 특정한 관계 가 존재 하 는 데이터 요소 의 집합 이다.데이터 구 조 는 세 가지 내용, 논리 구조, 저장 구조, 데이터 의 연산 을 포함한다.데이터 논리 구조 와 저장 구 조 는 밀접 한 두 가지 측면 이다.알고리즘 의 디자인 은 선택 한 논리 구조 에 달 려 있 고 알고리즘 의 실현 은 사용 하 는 저장 구조 에 의존한다.
데이터 구조의 세 가지 요소 데이터 의 논리 구조 논리 구 조 는 요소 간 의 논리 적 관계, 즉 논리 적 관계 에서 데 이 터 를 묘사 하 는 것 이다.그것 은 데이터 의 저장 과 상 관 없 이 컴퓨터 에 독립 되 어 있다.데이터 의 논리 구 조 는 선형 구조 와 비 선형 구조 로 나 뉘 는데 선형 표 는 전형 적 인 선형 구조 이다.집합, 나무, 그림 은 전형 적 인 비 선형 구조 이다. 집합: 구조 중의 요 소 는 같은 집합 에 속 하 는 관 계 를 제외 하고 다른 관계 선형 구조 가 없다. 구조 중의 데이터 간 에 1 대 1 의 관계 비 선형 구조 만 존재 한다. 구조 중의 데이터 간 에 1 대 다 의 관계 도형 구조 & 그물 모양 구조 가 존재 한다. 구조 중의 요소 간 에 다 중 관계 가 존재 한다. 데이터 의 저장 구조 저장 구 조 는 데이터 구조 가 컴퓨터 에서 나타 나 는 것 을 가리 키 며 물리 구조 라 고도 부른다.그것 은 데이터 요소 의 표시 와 관계 의 표 시 를 포함한다.데이터 의 저장 구 조 는 논리 구조 가 컴퓨터 언어 로 이 루어 지 는 것 으로 컴퓨터 언어 에 의존한다.데이터 의 저장 구 조 는 주로 순서 저장, 체인 저장, 색인 저장 과 해시 저장 이 있다.
순서 저장: 논리 적 으로 인접 한 요 소 를 물리 적 위치 에서 도 인접 한 저장 장치 에 저장 하고 요소 간 의 관 계 는 저장 장치 의 인접 관계 에 의 해 나타난다.장점: 무 작위 로 액세스 할 수 있 고 모든 요소 가 가장 적은 저장 공간 을 차지 합 니 다.단점: 인접 한 저장 장치 만 사용 하면 외부 파편 이 많이 생 길 수 있 습 니 다.
링크 저장 소: 논리 적 으로 인접 한 단원 이 물리 적 으로 도 인접 하도록 요구 하지 않 습 니 다.지시 요소 의 주 소 를 저장 하 는 지침 을 통 해 요소 간 의 논리 적 관 계 를 나타 낸다.장점: 파편 현상 이 나타 나 지 않 고 모든 저장 부 를 충분히 활용 한다.단점: 모든 요 소 는 포인터 저장 으로 인해 추가 저장 공간 을 차지 하고 순서 액세스 만 가능 합 니 다.
색인 저장: 정 보 를 저장 하 는 동시에 추가 색인 표를 만 듭 니 다.색인 표 의 모든 항목 은 색인 항목 이 되 고 색인 항목 의 일반적인 형식 은: (키워드, 주소) 입 니 다.검색 속도 가 빠 르 고 추가 색인 표를 추가 해 저장 공간 을 많이 차지 하 는 것 이 단점 이다.데 이 터 를 삭제 하고 추가 할 때 색인 표를 수정 하 는 데 시간 이 많이 걸린다.
해시 저장: 요소 의 키워드 에 따라 해당 요소 의 저장 주 소 를 직접 계산 하여 HASH 라 고도 부른다.검색, 증가, 노드 삭제 속도 가 빠르다 는 것 이 장점 이다.단점: 해시 함수 가 좋 지 않 으 면 요소 저장 장치 의 충돌 이 발생 할 수 있 습 니 다. 충돌 을 해결 하려 면 시간 과 공간 비용 을 늘 려 야 합 니 다.
데이터 의 연산 데이터 에 가해 지 는 연산 은 연산 의 정의 와 실현 을 포함한다.논리 구 조 를 정의 합 니 다. 구체 적 인 기능 을 지적 하고 저장 구 조 를 실현 합 니 다. 연산 의 구체 적 인 절 차 를 지적 합 니 다. 기본 개념 1 끝!!(이전에 이런 것들 을 체계적으로 복습 한 적 이 없 는데, 일정한 코드 량 이 생 긴 후에 이런 개념 을 보면 정말 제호 가 정수리 에 들 어 오 는 느낌 이 든다) 다음은 첫 번 째 부분의 연습 문제 에 대한 지식 추출 입 니 다.
데 이 터 를 저장 할 때 각 데이터 요소 의 값 뿐만 아니 라 데이터 요소 간 의 관계 도 저장 해 야 한다.
체인 저장 디자인 을 할 때 접점 안의 저장 장치 주 소 는 반드시 연속 된다.
추상 적 인 데이터 형식 으로 완전한 데이터 구 조 를 정의 할 수 있다.
퀴즈:
두 가지 서로 다른 데이터 구조 에 대해 논리 구조 와 물리 구 조 는 반드시 같 지 않 습 니까?A: 데이터 의 연산 도 데이터 구조의 중요 한 부분 입 니 다.예 를 들 어 이 진 트 리 와 이 진 트 리 의 논 리 는 물리 구조 와 완전히 같다.양자 의 연산 정 의 는 다르다.이 진 트 리 는 일반적으로 계층 관 계 를 나타 내 고 이 진 트 리 는 정렬 과 찾기 에 사용 된다.
예 를 들 어 같은 논리 구조 에 대해 같은 연산 이 서로 다른 저장 방식 에서 이 루어 지고 연산 효율 이 다르다 는 것 을 설명 한다.A: 선형 표 는 순서대로 저장 할 수도 있 고 체인 으로 저장 할 수도 있 습 니 다.삽입 삭제 의 경우 순서 저장 O (n), 체인 저장 O (1), 액세스 가 반대 입 니 다.
다음은 기초 지식 두 번 째 부분 을 정리 하 겠 습 니 다. 알고리즘 과 알고리즘 평가 알고리즘 의 기본 개념 알고리즘 은 특정 문제 의 해결 절차 에 대한 설명 이다.그것 은 명령 의 우선 순위 이다. 그 중에서 모든 명령 은 하나 이상 의 조작 을 나타 낸다.알고리즘 은 다음 과 같은 다섯 가지 특성 을 가지 고 있다.
가난 성 이 있 습 니 다. 하나의 알고리즘 은 항상 (모든 합 법 적 인 입력 값 에 대해) 실행 이 끝 난 후에 끝나 야 하고 모든 단 계 는 가난 한 시간 안에 완성 해 야 합 니 다.
확정 성: 알고리즘 중의 모든 명령 은 반드시 정확 한 의 미 를 가 져 야 하고 독자 가 이해 할 때 이의 성 이 생기 지 않 는 다.같은 입력 에 대해 서 는 같은 출력 만 생 성 할 수 있 습 니 다.
타당 성: 하나의 알고리즘 은 실행 가능 하 다.알고리즘 에서 설명 한 조작 은 모두 이미 실 현 된 기본 연산 을 통 해 유한 하 게 실 현 될 수 있다.
입력: 한 알고리즘 에 0 개 이상 의 입력 이 있 습 니 다.특정한 대상 에서 추출 한 집합 을 입력 하 십시오.
출력: 하나의 알고리즘 이 여러 개 또는 한 개의 출력 이 있 습 니 다.출력 은 입력 과 특정한 관 계 를 가 진 양 이다.
좋 은 알고리즘 은 다음 과 같은 목 표를 고려 해 야 한다.
정확성
가 독성
건장 성: 불법 데 이 터 를 입력 하 는 데 도 적절 한 반응 을 보이 거나 처리 해 야 한다.
저 저장량 수요 보다 효율 적
알고리즘 효율 의 도량 알고리즘 효율 의 도량 은 시간 복잡 도와 공간 복잡 도 를 통 해 묘사 한 것 이다. 시간 복잡 도 최 악의 시간 복잡 도: 최 악의 상황 에서 의 시간 복잡 도 평균 시간 복잡 도: 모든 입력 인 스 턴 스 가 등 확률 로 나타 나 는 상황 에서 알고리즘 의 기대 운행 시간 이 가장 좋 은 시간 복잡 도 분석 시간 복잡 도의 두 가지 guize
덧셈 규칙: T (n) = T1 (n) + T2 (n) = O (f (n) + O (g (n) = O (max (f (n), g (n)))
곱셈 규칙: T () = T1 (n) * T2 (n) = O (f (n) * O (g (n) = O (f (n) * g (n)) 흔히 볼 수 있 는 점진 적 시간 복잡 도 는 O (1) n)
공간 복잡 도 이 알고리즘 이 소모 하 는 저장 공간 으로 정의 합 니 다. 그 는 문제 규모 n 의 함수 입 니 다.점진 적 공간 복잡 도 는 흔히 공간 복잡 도 라 고 부른다.S (n) = O (g (n) 프로그램 에서 데 이 터 를 조작 하 는 작업 단원 과 계산 을 실현 하기 위해 필요 한 정 보 를 저장 하 는 보조 공간 이 필요 합 니 다.만약 에 입력 데이터 가 차지 하 는 공간 이 문제 자체 에 만 달 려 있 고 알고리즘 과 무관 하 다 면 입력 과 프로그램 을 제외 한 추가 공간 만 분석 해 야 한다.알고리즘 제자리 작업 이란 알고리즘 에 필요 한 보조 공간 이 상수, 즉 O (1) 를 말한다. 두 번 째 부분의 지식 점 나열 이 끝 났 습 니 다. 다음은 연습 문제 에서 추출 한 맹점 분석 은 다음 과 같은 코드 의 집행 횟수 입 니 다.
int m = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 2 * i; j++) m++;
}
실행 횟수 n (n + 1) 피 보 나치 수열: 귀속 알고리즘 시간 복잡 도 O (2 ^ n) (구체 적 계산 은 약간 복잡), 비 귀속 시간 복잡 도 O (n) 뭐, 이것 이 바로 겨울방학 의 첫 번 째 노트 입 니 다. 썩 지 않 았 으 면 좋 겠 습 니 다. 썩 지 않 았 으 면 좋 겠 습 니 다!!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
