데이터 구조 (DS) 와 추상 데이터 형식 (ADT)

데이터 구조 (데이터 구조)
데이터 구조 가 무엇 인지 알 기 위해 서 는 먼저 데이터 와 구조 가 무엇 인지 명 확 히 해 야 한다.
데이터 (데이터)
데 이 터 는 정보의 매개체 이다.그것 은 컴퓨터 에 의 해 식별 되 고 저장 되 며 가공 처 리 될 수 있 으 며 컴퓨터 프로그램 이 가공 한 원료 이다.컴퓨터 응용 분야 가 확 대 됨 에 따라 데이터 의 범 주 는 정수, 실수, 문자열, 이미지 와 소리 등 을 포함한다.
데이터 요소 (데이터 요소)
데이터 요 소 는 데이터 의 기본 단위 이다.데이터 요 소 는 원소, 결점, 정점, 기록 이 라 고도 부른다.하나의 데이터 요 소 는 여러 개의 데이터 항목 (필드, 도 메 인, 속성 이 라 고도 할 수 있 음) 으로 구성 할 수 있다.데이터 항목 은 독립 적 인 의 미 를 가 진 최소 표지 단위 이다.
데이터 구조 (데이터 구조)
데이터 구 조 는 데이터 간 의 상호 관계, 즉 데이터 의 조직 형식 을 가리킨다.
데이터 구조의 구성 부분
논리 구조
데이터 요소 간 의 논리 적 관 계 는 데이터 의 논리 적 구조 (Logical Structure) 라 고도 부른다.데이터 의 논리 구 조 는 논리 적 관계 에서 데 이 터 를 묘사 하 는 것 으로 데이터 의 저장 과 상 관 없 이 컴퓨터 에 독립 된 것 이다.데이터 의 논리 구 조 는 구체 적 인 문제 에서 추상 화 된 수학 모델 로 볼 수 있다.

선형 구조: 선형 구조의 논리 적 특징 은 만약 에 구조 가 비어 있 지 않 으 면 하나의 시작 점 과 하나의 단말기 결점 만 있 고 모든 결점 은 하나의 직접적인 전진 과 하나의 직접적인 후계 만 있다 는 것 이다.예 를 들 어 선형 표 는 전형 적 인 선형 구조 이다.창고, 대열, 직렬 등 은 모두 선형 구조 이다.

비 선형 구조: 비 선형 구조의 논리 적 특징 은 하나의 결점 이 여러 개의 직접적인 전진 과 직접적인 후계 가 있 을 수 있다 는 것 이다.배열, 광의 표, 나무 와 그림 등 데이터 구 조 는 모두 비 선형 구조 이다.

기억 구조
데이터 요소 와 그 관 계 는 컴퓨터 메모리 에 표 시 됩 니 다. 데이터 의 저장 구조 (Storage Structure, 데이터 의 저장 구 조 는 논리 구조 가 컴퓨터 언어 로 실현 되 는 것 (이미지 라 고도 함) 으로 컴퓨터 언어 에 의존 합 니 다. 기계 언어 에 있어 저장 구 조 는 구체 적 입 니 다.
데이터 의 저장 구 조 는 다음 과 같은 네 가지 가 있다.

순서 저장 방법: 이 방법 은 논리 적 으로 인접 한 결점 을 물리 적 위치 에 인접 한 저장 장치 에 저장 하고, 결점 간 의 논리 적 관 계 는 저장 장치 의 인접 관계 에 의 해 나타난다. 이 를 통 해 얻 은 저장 소 는 순서 저장 구조 (Sequential Storage Structure) 라 고 한다.일반적으로 프로그램 언어의 배열 설명 을 통 해 이 방법 은 선형 데이터 구조 에 주로 사용 된다. 비 선형 데이터 구조 도 특정한 선형 화 방법 으로 순서 적 으로 저장 할 수 있다.

링크 저장 방법: 이 방법 은 논리 적 으로 인접 한 노드 가 물리 적 위치 에서 도 인접 하도록 요구 하지 않 습 니 다. 노드 간 의 논리 관 계 는 부가 적 인 지침 필드 에 의 해 표 시 됩 니 다. 이 를 통 해 얻 은 저장 소 는 체인 저장 구조 (Linked Storage Structure) 라 고 부 르 며 프로그램 언어의 지침 유형 설명 을 통 해 이 루어 집 니 다.

색인 저장 방법: 이 방법 은 보통 노드 정 보 를 저장 하 는 동시에 추가 색인 표를 만 듭 니 다. 색인 표 는 여러 색인 항목 으로 구성 되 어 있 습 니 다. 각 노드 가 색인 표 에 하나의 색인 항목 이 있다 면 이 색인 표 는 조밀 한 색인 (Dense Index) 이 라 고 합 니 다. 만약 한 그룹 이 색인 표 에 하나의 색인 항목 만 대응 한다 면 이 색인 표 는 희소 한 색인 표 라 고 합 니 다.(Spare Index). 색인 항목 의 일반적인 형식 은: (키워드, 주소)

입 니 다.

해시 저장 방법: 이 방법의 기본 사상 은 결점 의 키워드 에 따라 이 결점 의 저장 주 소 를 직접 계산 하 는 것 이다.

네 가지 기본 저장 방법 은 단독으로 사용 할 수도 있 고 조합 하여 데이터 구조 에 대해 이미 지 를 저장 할 수도 있다. 같은 논리 구 조 는 서로 다른 저장 방법 을 사용 하여 서로 다른 저장 구 조 를 얻 을 수 있다. 어떤 저장 구 조 를 선택 하여 해당 하 는 논리 구 조 를 나타 내 는 지 구체 적 인 요구 에 따라 정 하고 연산 편의 와 알고리즘 의 시공 간 요 구 를 고려한다.
추상 데이터 형식 (추상 데이터 형식)
추상 데이터 형식 (Abstract Data Type 은 ADT 로 약칭) 은 수학 모델 과 이 수학 모델 을 정의 하 는 작업 을 말한다. 추상 데이터 형식 은 고유 데이터 형식 (고급 프로 그래 밍 언어 에서 실 현 된 데이터 형식) 을 통 해 이 루어 져 야 한다.추상 적 인 데이터 형식 은 표시 와 무관 한 데이터 형식 으로 데이터 모델 과 이 모델 에 정 의 된 연산 입 니 다.
ADT 의 설명

ADT ADT-Name{
    Data://    
                 
    Operations://    
    Operation1://  1，     C C﹢﹢        
    Input:        
    Preconditions:              //       
    Process:        
    Output:        
    Postconditions:           //"  "         


    Operation2://  2
    ……
  }//ADT 

추상 적 인 데이터 형식 (ADT) 은 순수 이론 실체 로 추상 적 인 알고리즘 을 묘사 하고 데이터 구 조 를 분류 하고 평가 하 며 프로 그래 밍 언어 를 형식 으로 묘사 하 는 유형 시스템 이다. 하나의 ADT 는 특정한 데이터 형식 이나 데이터 구조 로 이 루어 질 수 있 으 며 많은 프로 그래 밍 언어 에서 여러 가지 실현 방식 이 있 거나 형식 으로 언어 설명 을 규범화 시 킬 수 있다. ADT 는 항상 모듈 (module) 로 이 루어 진다.: 모듈 의 인 터 페 이 스 는 ADT 작업 에 대응 하 는 루틴 (procedure) 을 설명 하고 가끔 주석 으로 제약 을 설명 합 니 다.