데이터 구조 필기 서론
1.1 데이터 구조의 연구 내용
데이터 구 조 는 주로 비 데이터 계산 문 제 를 연구한다. 즉, 수학 방법 으로 수학 모델 을 구축 할 수 없 는 문제 이다. 예 를 들 어 학생 정보 표 (선형), 인간 과 컴퓨터 의 대국 (나무), 최 단 경로 (그림) 등 이다.
1.2 기본 개념 과 용어
1.2.1 데이터, 데이터 요소, 데이터 항목, 데이터 대상
데이터: 객관 적 인 사물 의 기 호 는 컴퓨터 에 입력 되 고 컴퓨터 프로그램 에 의 해 처 리 될 수 있 는 모든 기호의 총칭 을 나타 낸다.숫자, 문자열, 그림.
데이터 요소: 데이터 의 기본 단위 로 컴퓨터 에서 일반적으로 하나의 전체 로 고려 하고 처리한다.예 를 들 어 학생 정보 표 에서 한 학생 의 정보, 인간 과 컴퓨터 가 대국 할 때의 상태, 그림 의 정점 이다.
데이터 항목: 데이터 요 소 를 구성 하 는 독립 적 인 의미 가 있 고 분할 할 수 없 는 최소 단위 입 니 다.예 를 들 어 학생 의 학 번, 성명, 나이 등 은 모두 데이터 항목 이다.
데이터 대상: 성질 이 같은 데이터 요소 의 집합 은 데이터 의 하위 집합 입 니 다.예 를 들 어 학생 중 20 세 이상 의 집합.
1.2.2 데이터 구조
데이터 구 조 는 서로 한 가지 또는 여러 가지 특수 관계 가 존재 하 는 데이터 소스 의 집합 이다.
데이터 구 조 는 논리 구조 와 저장 구조의 두 가지 차원 을 포함한다.
1. 논리 구조
데이터 의 논리 구 조 는 논리 적 관계 에서 데 이 터 를 묘사 하 는 것 이다.구체 적 인 문제 에서 추상 화 된 수학 모형 으로 볼 수 있다.
논리 구 조 는 두 가지 요소 가 있다. 하 나 는 데이터 요소 이 고 다른 하 나 는 관계 이다.네 가지 기본 적 인 논리 관계: 집합, 선형, 나무, 그림.
2 기억 구조
데이터 대상 이 컴퓨터 에 저장 되 어 있 는 것 을 저장 구조 라 고 한다.
데이터 요 소 는 컴퓨터 에서 두 가지 기본 적 인 저장 구조 가 있 는데 그것 이 바로 순서 저장 구조 (배열) 와 체인 저장 구조 (링크) 이다.
1.2.3 데이터 형식 과 추상 데이터 형식
데이터 형식, 예 를 들 어 C 언어 중의 정형, 부동 소수점 등 이다.추상 적 인 데이터 형식 은 사용자 가 스스로 정의 하고 응용 문 제 를 나타 내 는 데이터 형식 으로 C + 에서 클래스 로 표시 할 수 있다.
1.3 추상 적 인 데이터 유형의 표현 과 실현
예 를 들 어 복수 에 대해 조작 하 다.
① 정의 부분:
②
③ 실현 부분
ADT Complex{
Creat(&C, x, y);
// C， x, y
GetReal(C);
//
GetImag(C);
//
Add(C1, C2);
//
Sub(C1, C2);
//
} ADT Complex1.4 알고리즘 과 알고리즘 분석
데이터 구조 와 알고리즘 은 본질 적 인 관 계 를 가지 고 있다.
1.4.1 알고리즘 의 정의 및 특성
알고리즘 은 특정한 문 제 를 해결 하기 위해 규정된 유한 한 조작 서열 이다.
알고리즘 이 만족 해 야 할 특성: 빈곤 성, 확정 성, 타당 성, 입 출력 이 있 습 니 다.
1.4.2 평가 알고리즘 우열 의 기본 기준
알고리즘 의 우열 은 이 몇 가지 측면 에서 평가 할 수 있다. 정확성, 가 독성, 건장 성, 효율 성 (시간 복잡 도와 공간 복잡 도 포함) 이다.
1.4.3 알고리즘 의 시간 복잡 도
1. 문제 규모 와 문장의 빈도
문제 규 모 는 알고리즘 이 문 제 를 푸 는 입력 량 이 얼마 인지, 예 를 들 어 정렬 할 때 데이터 의 개수 이다.
한 문장의 중복 집행 횟수 를 문장의 빈도 라 고 한다.
알고리즘 의 시간 복잡 도 정의
상례 에서 n 이 무한대 에 가 까 워 지면 f (n)/n * n * n = 2 이다.
비 는 0 과 같 지 않 은 상수 로 f (n) 와 n 의 세 번 이 같은 수량 급 임 을 나타 내 고 T (n) = O (f (n) = O (n 의 세 번) 로 기록 합 니 다.
T (n) 는 시간 복잡 도 이다.
3. 알고리즘 시간 복잡 도 예
정리: T (n) = f (n) 중 최고 차 항 = O (n 의 m 회)
typedef struct
{
float Realpart; //
float Imagepart; //
}Complex;흔히 볼 수 있 는 시간 복잡 도 는 수량 급 에 따라 점차적으로 증가 하 는 것 은 상수 단계, 대수 단계, 선형 단계, 선형 대수 단계, 제곱 단계, 입방 단계, K 차방 단계, 지수 단계 이다.
4. 최 악, 평균 시간 복잡 도
동문서답
1.4.4 공간 알고리즘 복잡 도
예 를 들 어 설명 하 다.
4. 567913. 상기 두 알고리즘 에 비해 첫 번 째 는 보조 변수 t 만 사 용 했 고 공간 복잡 도 는 O (1) 이다.
두 번 째 는 하나의 배열 을 사 용 했 고 공간 복잡 도 는 O (n) 이다.
좋은 웹페이지 즐겨찾기
