추상 데이터 유형인 선형 목록입니다. 추상 데이터 유형 "목록". 추상 데이터 유형 “이진 검색 트리”
좋은 하루 되세요, 카브라 주민 여러분!
다음 글은 클래스와 ADT의 본질에 대한 나의 생각을 요약한 것이다. 이러한 생각은 소프트웨어 개발 전문가의 책에서 나온 흥미로운 인용문으로 보완됩니다.
소개
ADT의 정의에 점진적으로 접근하는 것부터 시작하겠습니다. ADT는 무엇보다도 데이터 유형이며 이는 다음을 의미합니다. 이 유형의 요소에 대해 사용 가능한 특정 작업이 있습니다.
이러한 작업이 수행되는 데이터(값 범위)도 마찬가지입니다.
"추상적"이라는 단어는 무엇을 의미합니까? 우선, "추상성"이라는 개념은 중요한 것에 주의를 집중하는 동시에 현재 중요하지 않은 세부 사항에 주의를 돌리는 것을 의미합니다. 추상화의 정의는 Grady Booch의 책에서 잘 다루고 있습니다. 정의는 다음과 같습니다.
추상화는 개념적 경계를 결정하고 다른 모든 유형의 객체와 구별되는 공통 속성의 객체 집합을 선택하고 전달하는 것입니다.
즉, 추상화를 통해 우리는 필요한 개체 데이터를 "밝게" 하고 동시에 우리에게 중요하지 않은 데이터를 "그림자"로 만들 수 있습니다.
그렇다면 "데이터 유형"과 "추상화"의 개념을 병합하면 어떻게 될까요? 우리는 이 데이터 유형의 객체 동작을 보장하는 특정 작업 세트를 제공하는 데이터 유형을 받게 되며, 이 데이터 유형은 또한 이 동작이 구현되는 데 도움을 받아 데이터를 숨길 것입니다. 따라서 우리는 ADT의 개념에 도달합니다.
ADT는 클라이언트로부터 내부 구현을 숨기는 데이터 유형입니다.
놀라운 점은 ADT를 사용하면 추상화를 적용하여 낮은 수준의 구현 세부 사항에 대해 걱정하지 않고 현실 세계의 높은 수준의 본질을 다룰 수 있다는 것입니다(Steve McConnell).
저는 ADT를 개발할 때 먼저 인터페이스를 정의해야 한다고 생각합니다. 인터페이스는 ADT의 내부 데이터 표현에 의존해서는 안 되기 때문입니다. 인터페이스를 구성하는 작업을 정의한 후에는 ADT의 지정된 동작을 구현할 데이터에 집중해야 합니다. 결과적으로 우리는 특정 데이터 구조, 즉 데이터를 저장하고 처리할 수 있는 메커니즘을 갖게 됩니다. 동시에 ADT의 장점은 데이터의 내부 표현을 변경하려는 경우 전체 프로그램을 헤매거나 변경하려는 데이터에 따라 모든 코드 줄을 변경할 필요가 없다는 것입니다. ADT는 이 데이터를 캡슐화하므로 전체 프로그램이 아닌 이 유형의 개체 작업을 변경할 수 있습니다.
ATD의 장점
ADT를 사용하면 많은 이점이 있습니다(설명된 모든 이점은 Steve McConnell의 저서 "Perfect Code"에서 찾을 수 있음).
- 구현 세부정보를 캡슐화합니다.
즉, ADT의 구현 세부 사항을 캡슐화한 후에는 ADT와 상호 작용할 수 있는 인터페이스를 클라이언트에 제공합니다. 구현 세부 사항을 변경해도 ADT 작업에 대한 클라이언트의 인식은 바뀌지 않습니다.
- 복잡성 감소.
구현 세부 사항을 추상화함으로써 우리는 인터페이스, 즉 ADT가 수행되는 방식보다는 ADT가 수행할 수 있는 작업에 중점을 둡니다. 게다가 ADT를 사용하면 현실 세계의 본질을 활용하여 작업할 수 있습니다.
- 데이터 사용 범위를 제한합니다.
ADT를 사용하면 ADT의 내부 구조를 나타내는 데이터가 코드의 다른 부분에 의존하지 않는다는 것을 확인할 수 있습니다. 이 경우 ADT의 '독립'이 실현된다.
- 매우 유익한 인터페이스.
ADT를 사용하면 도메인 엔터티 측면에서 전체 인터페이스를 표시할 수 있으므로 인터페이스의 가독성과 정보성이 향상됩니다.
Steve McConnell은 스택이나 목록과 같은 하위 수준 데이터 유형을 ADT로 표시할 것을 권장합니다. 이 목록이 무엇을 나타내는지 스스로에게 물어보세요. 은행 직원 목록을 나타내는 경우 ATD를 은행 직원 목록으로 간주합니다.
그래서 우리는 ADT가 무엇인지 알아보고, 그 활용의 장점을 정리해보았습니다. 이제 OOP에서 클래스를 개발할 때 먼저 ADT에 대해 생각해야 한다는 점은 주목할 가치가 있습니다. 동시에 Steve McConnell이 말했듯이 언어로 프로그래밍하는 것이 아니라 언어의 도움을 받아 프로그래밍합니다. 즉, 배열이나 단순한 데이터 유형의 측면에서 생각하는 데 국한되지 않고 언어의 경계를 넘어 프로그래밍하게 됩니다. 대신, 높은 수준의 추상화(예: 스프레드시트 또는 직원 목록 측면에서)에서 생각하게 됩니다. 클래스는 ADT 개념을 구현하는 추가 및 방법에 지나지 않습니다. 클래스를 공식으로 표현할 수도 있습니다.
클래스 = ADT + 상속 + 다형성.
그렇다면 클래스를 개발할 때 왜 ADT를 생각해야 할까요? 왜냐하면 먼저 미래 클래스의 인터페이스를 구성할 작업, 숨길 데이터, 공개 액세스를 제공할 작업을 결정해야 하기 때문입니다. 우리는 인터페이스를 매우 유익하게 만들고, 코드를 쉽게 최적화하고 테스트할 수 있도록 만들고, 낮은 수준의 구현 세부 사항이 아닌 실제 엔터티에 대해 생각할 수 있도록 올바른 추상화를 제공할 수 있는 방법에 대해 생각해야 합니다. 나는 ADT를 정의한 후에 상속과 다형성 문제에 대해 생각해야 한다고 믿습니다.
ADT의 개념이 OOP에서 폭넓게 적용되었다는 점은 주목할 가치가 있습니다. 왜냐하면 이 개념이 OOP를 보완하고 빠르게 변화하는 소프트웨어 요구 사항 세계에서 프로그램의 복잡성을 줄일 수 있게 해주기 때문입니다.
나는 작업의 질과 소프트웨어 개발을 향상시키기 위해 개발자들의 관심을 ADT로 끌어들이고자 이 글을 썼다.
사용된 소스:
스티브 맥코넬 - “완벽한 코드”;
Robert Sedgwick - “Java의 알고리즘.”
모든 내장 데이터 유형은 추상적이지만 그렇게 불리는 경우는 거의 없습니다.
추상화의 개념
추상화는 주어진 상황에서 필수적인 속성만 포함하는 일부 개체에 대한 판단 또는 아이디어입니다. 추상화를 사용하면 객체 인스턴스를 그룹으로 결합할 수 있으며, 이 그룹 내에서는 객체의 일반적인 속성을 고려할 필요가 없습니다. 그들로부터 추상화하십시오. 추상화는 프로그래밍 복잡성에 대한 효과적인 해독제이므로 프로그래머는 객체의 필수 속성에 집중할 수 있습니다. 추상화 유형: 프로세스 추상화그리고 데이터 추상화.
프로세스 추상화.모든 루틴은 프로세스 추상화입니다. 수행 방법에 대한 세부 사항을 지정하지 않고 프로그램이 일부 프로세스를 수행해야 하는지 결정하는 방식을 정의합니다. 서브루틴이 실행하는 알고리즘의 많은 세부 사항을 추상화하는 기능을 통해 대규모 프로그램을 만들고 읽고 이해할 수 있습니다. 모든 데이터 추상화는 프로세스 추상화로 정의된 작업입니다.
데이터 추상화.추상 데이터 유형은 특정 데이터 유형의 표현과 해당 데이터 유형에 대한 작업을 수행하는 루틴만 포함하는 캡슐화입니다. 액세스 제어를 사용하면 해당 유형을 사용하는 외부 모듈에서 유형 설명의 중요하지 않은 세부 정보를 숨길 수 있습니다. 추상 데이터 유형을 사용하는 프로그램 모듈은 유형의 실제 표현이 숨겨져 있더라도 해당 유형의 변수를 선언할 수 있습니다. 추상 데이터 유형의 인스턴스를 객체라고 합니다.
데이터 유형 추상화 및 프로세스 추상화를 만드는 이유는 복잡성에 대한 해독제로서 크고 복잡한 프로그램을 보다 쉽게 관리할 수 있도록 하기 위한 것입니다.
캡슐화
프로그램을 논리적으로 관련된 루틴 및 데이터 그룹을 포함하는 구문 컨테이너로 나눕니다. 이러한 구문 컨테이너를 모듈이라고 하며 이를 개발하는 프로세스를 모듈화라고 합니다.
프로그램의 나머지 부분을 다시 컴파일하지 않고도 각각 별도로 컴파일할 수 있는 서브루틴 및 데이터 모음에서 프로그램을 컴파일합니다. 이 세트를 컴파일 단위라고 합니다.
캡슐화는 서브루틴과 서브루틴이 처리하는 데이터를 하나의 전체로 결합하는 방법입니다. 개별적으로 또는 독립적으로 컴파일되는 캡슐화는 추상 시스템의 기초이자 해당 계산 집합의 논리적 구성입니다.
추상 사용자 정의 데이터 유형
추상 사용자 정의 데이터 유형에는 다음 속성이 있어야 합니다.
1) 프로그램 모듈이 이 유형의 변수를 선언하는 동시에 메모리에 이러한 변수의 실제 표현을 생성할 수 있도록 하는 유형 정의.
2) 주어진 유형의 객체를 조작하기 위한 일련의 작업.
사용자 정의 유형의 맥락에서 추상 데이터 유형의 형식적 정의: 추상 데이터 유형은 다음 두 가지 조건을 만족하는 데이터 유형입니다.
주어진 유형의 객체에 대한 표현(유형 정의) 및 작업은 하나의 구문 단위에 포함되어 있으며, 지정된 유형의 변수는 다른 모듈에서 생성될 수 있습니다.
특정 유형의 객체 표현은 이 유형을 사용하는 프로그램 모듈에서 숨겨집니다. 유형 정의에서 직접 제공되는 객체에 대해 작업을 수행할 수 있습니다.
유형 표현과 연산을 별도의 구문 단위로 패키징하면 프로그램을 별도로 컴파일할 수 있는 논리 단위로 구성할 수 있습니다. 둘째, 프로그램의 별도 부분에서 특정 유형의 개체 표현이나 해당 개체에 대한 작업을 수정하는 것이 가능해졌습니다. 유형 표현 세부사항을 숨기면 이점이 있습니다. 클라이언트는 객체 표현의 세부 사항을 "볼" 수 없으며 해당 코드는 해당 표현에 의존하지 않습니다. 이런 방식으로 클라이언트 코드를 변경할 필요 없이 언제든지 객체 표현을 변경할 수 있습니다. 정보 숨김의 또 다른 명백하고 중요한 이점은 신뢰성 향상입니다. 클라이언트는 의도적으로든 실수로든 객체의 기본 표현을 직접 변경할 수 없으므로 해당 객체의 무결성이 향상됩니다. 객체는 이 목적으로 제공된 작업을 통해서만 수정할 수 있습니다.
유형 개발 문제
추상화 클라이언트가 유형 이름과 서브루틴 헤더를 볼 수 있도록 하는 것이 가능해야 합니다. 이를 통해 클라이언트는 추상 유형의 변수를 선언하고 해당 값을 조작할 수 있습니다. 유형 이름은 외부에서 볼 수 있어야 하지만 해당 정의는 숨겨야 합니다.
유형 정의에서 제공하는 작업과 달리 추상 유형의 개체에 대해 수행할 수 있는 일반적인 내장 작업은 거의 없습니다. 이러한 작업에는 할당, 평등 및 불평등 테스트가 포함됩니다. 언어에서 사용자가 할당 연산자를 오버로드하는 것을 허용하지 않으면 이를 내장해야 합니다. 평등 및 불평등 테스트는 어떤 경우에는 미리 정의되어야 하지만 다른 경우에는 그렇지 않습니다. 유형 디자이너는 대부분의 추상 데이터 유형에 대한 작업을 직접 정의해야 합니다.
Smalltalk, C++ 및 Java는 추상 데이터 유형을 직접 지원합니다.
C++의 추상 데이터 유형
Ada 및 Modula-2 언어는 추상 데이터 유형을 모델링하는 데 사용할 수 있는 캡슐화를 제공하며 C++에서는 추상 데이터 유형을 직접 지원하는 클래스 개념을 도입합니다. C++에서 클래스는 유형이지만 Ada 패키지와 Modula-2 모듈은 유형이 아닙니다. 패키지와 모듈을 가져오므로 가져오는 프로그램 단위가 패키지나 모듈에 정의된 모든 유형의 변수를 선언할 수 있습니다. C++ 프로그램에서 변수는 주어진 클래스의 유형을 갖는 엔터티로 선언됩니다. 이러한 방식으로 클래스는 패키지나 모듈보다 내장 유형에 훨씬 더 가깝습니다. Ada의 패키지나 Modula-2의 모듈을 보는 소프트웨어 유닛은 이름만으로 모든 공공 기관에 액세스할 수 있습니다. 클래스의 인스턴스를 선언하는 C++ 프로그램 단위도 해당 클래스의 모든 공용 엔터티에 액세스할 수 있지만 해당 클래스의 인스턴스를 통해서만 가능합니다.
데이터에 대한 추상적 모델과 해당 데이터를 처리하는 방법을 개발하는 것은 컴퓨터 문제 해결의 중요한 구성 요소입니다. 일상적인 프로그래밍의 낮은 수준(예: 배열 및 연결 목록을 사용할 때)과 응용 문제를 해결할 때(조인-검색 포리스트를 사용하여 연결 문제를 해결할 때와 같이) 높은 수준에서 이에 대한 예를 볼 수 있습니다. "소개"에서) . 본 강의에서는 높은 수준의 추상화를 사용하여 프로그램을 만들 수 있는 추상 데이터 유형(이하 ADT)에 대해 설명합니다. 추상 데이터 유형을 사용하면 프로그램이 데이터에 대해 수행하는 추상(개념적) 변환을 데이터 구조의 구체적인 표현 및 알고리즘의 구체적인 구현과 분리할 수 있습니다.
모든 컴퓨팅 시스템은 추상화 수준을 기반으로 합니다. 실리콘 및 기타 재료의 특정 물리적 특성을 통해 0-1의 이진 값을 취할 수 있는 비트의 추상 모델을 채택할 수 있습니다. 그런 다음 특정 비트 세트 값의 동적 속성을 기반으로 기계의 추상 모델이 구축됩니다. 또한 기계어 프로그램의 제어하에 기계 작동 원리를 기반으로 프로그래밍 언어의 추상 모델이 구축됩니다. 마지막으로 알고리즘의 추상적인 개념이 구성되어 C++로 프로그램으로 구현됩니다. 추상 데이터 유형을 사용하면 이 프로세스를 더욱 계속할 수 있으며, C++ 시스템에서 제공하는 것보다 더 높은 수준에서 특정 계산 문제에 대한 추상 메커니즘을 개발하고, 특정 애플리케이션을 지향하고 수많은 애플리케이션 도메인의 문제를 해결하는 데 적합한 추상 메커니즘을 개발할 수 있습니다. , 또한 이러한 기본 설계를 사용하는 추상적인 상위 수준 메커니즘을 생성합니다. 추상 데이터 유형은 점점 더 많은 새로운 문제를 해결하기 위해 무한히 확장 가능한 도구 세트를 제공합니다.
한편으로 추상 구성을 사용하면 세부 구현에 대한 걱정이 없어집니다. 반면에 언제 성능프로그램이 중요하기 때문에 기본 작업을 수행하는 데 드는 비용을 알아야 합니다. 우리는 내장된 많은 기본 추상화를 사용합니다. 하드웨어컴퓨터 및 기계 명령의 기초 역할; 소프트웨어에서 다른 추상화를 구현합니다. 이전에 작성된 시스템 소프트웨어에서 제공한 추가 추상화를 사용합니다. 높은 수준의 추상 구성은 종종 더 간단한 구성에서 파생됩니다. 동일한 기본 원칙이 모든 수준에 적용됩니다. 프로그램에서 가장 중요한 작업과 데이터의 가장 중요한 특성을 찾은 다음 추상 수준에서 정확하게 정의하고 이를 구현하기 위한 효율적이고 구체적인 메커니즘을 설계합니다. 이번 강의에서 우리는 이 원리를 적용한 많은 예를 살펴볼 것입니다.
새로운 수준의 추상화를 개발하려면 (1) 조작해야 하는 추상 개체와 해당 개체에 대해 수행해야 하는 작업을 정의해야 합니다. (2) 일부 데이터 구조로 데이터를 표현하고 작업을 구현합니다. (3) 및 (가장 중요한) 이러한 객체가 적용된 문제를 해결하는 데 사용하기 편리하다는 것을 보장합니다. 이러한 사항은 간단한 데이터 유형에도 적용되므로 "기본 데이터 구조"에서 논의된 데이터 유형을 지원하기 위한 기본 메커니즘을 우리의 목적에 맞게 조정할 수 있습니다. 그러나 C++에서는 클래스라는 구조 메커니즘에 대한 중요한 확장을 제공합니다. 클래스는 추상화 계층을 생성하는 데 매우 유용하므로 이 책의 나머지 부분에서는 이 목적을 위해 사용되는 기본 도구로 간주됩니다.
정의 4.1. ADT(추상 데이터 유형)는 인터페이스를 통해서만 액세스할 수 있는 데이터 유형(값 집합 및 해당 값에 대한 작업 집합)입니다. ADT를 사용하는 프로그램을 클라이언트라고 하며 이 데이터 유형의 사양을 포함하는 프로그램을 구현이라고 합니다.
데이터 유형을 추상화하는 단어일 뿐입니다. ADT의 경우 클라이언트 프로그램은 인터페이스에 설명된 작업 이외의 어떤 방식으로도 데이터 값에 액세스할 수 없습니다. 이 데이터의 표현과 이러한 작업을 구현하는 기능은 구현에 포함되며 인터페이스에 의해 클라이언트와 완전히 분리됩니다. 인터페이스가 불투명하다고 말합니다. 클라이언트는 인터페이스를 통해 구현을 볼 수 없습니다.
C++ 프로그램에서는 다음을 포함하여 인터페이스를 만드는 것이 가장 쉽기 때문에 일반적으로 이러한 구별이 좀 더 명확해집니다. 데이터 프레젠테이션, 그러나 클라이언트 프로그램이 데이터에 직접 액세스할 수 없도록 지정합니다. 즉, 클라이언트 프로그램 개발자는 알 수 있습니다. 데이터 프레젠테이션, 그러나 어떤 방식으로도 사용할 수는 없습니다.
예를 들어, 섹션 3.1 "기본 데이터 구조"의 포인트(프로그램 3.3)에 대한 데이터 유형 인터페이스를 고려하십시오. 이 인터페이스는 점이 x와 y로 표시된 부동 소수점 숫자 쌍으로 구성된 구조로 표현됨을 명시적으로 선언합니다. 이러한 데이터 유형의 사용은 대규모 소프트웨어 시스템에서 일반적입니다. 우리는 데이터를 표현하기 위한 일련의 규칙을 개발하고(그리고 이와 관련된 작업 세트도 정의함) 클라이언트 프로그램에서 사용할 수 있도록 인터페이스를 통해 이러한 규칙을 사용할 수 있도록 합니다. 그것은 큰 시스템의 일부입니다. 데이터 유형은 시스템의 모든 부분이 기본 시스템 전체 데이터 구조를 일관되게 표현하도록 보장합니다. 이 전략이 아무리 훌륭하더라도 한 가지 결함이 있습니다. 변경해야 하는 경우 데이터 프레젠테이션을 클릭하면 모든 클라이언트 프로그램을 변경해야 합니다. 프로그램 3.3은 다시 간단한 예를 제공합니다. 이 데이터 유형을 설계하는 이유 중 하나는 클라이언트 프로그램이 점 작업을 더 쉽게 만들고 클라이언트가 필요할 때 개별 점 좌표에 액세스할 수 있기를 기대하는 것입니다. 그러나 모든 클라이언트 프로그램을 변경하지 않고는 다른 데이터 표현(예: 극좌표, 3D 좌표 또는 개별 좌표에 대한 다른 데이터 유형)으로 이동할 수 없습니다.
이와 대조적으로 프로그램 4.1에는 프로그램 3.3의 데이터 유형에 해당하는 추상 데이터 유형의 구현이 포함되어 있지만 데이터 및 관련 작업을 모두 즉시 정의하는 C++ 언어 클래스를 사용합니다. 프로그램 4.2는 이 데이터 유형으로 작동하는 클라이언트 프로그램입니다. 이 두 프로그램은 프로그램 3.3 및 3.8과 동일한 계산을 수행합니다. 이는 이제 살펴보게 될 클래스의 여러 기본 속성을 보여줍니다.
프로그램에서 int i와 같은 정의를 작성할 때, 우리는 i라는 이름으로 액세스할 수 있는 (내장) int 유형의 데이터에 대한 메모리 영역을 예약하도록 시스템에 지시합니다. C++ 언어에는 객체와 같은 엔터티에 대한 용어가 있습니다. 프로그램이 POINT p와 같은 정의를 작성할 때 p라는 이름으로 참조할 수 있는 POINT 클래스의 개체를 생성한다고 합니다. 이 예에서 각 개체에는 x와 y라는 두 개의 데이터 요소가 포함되어 있습니다. 구조와 마찬가지로 p.y.와 같은 이름으로 참조할 수 있습니다.
데이터 멤버 x와 y를 클래스의 데이터 멤버라고 합니다. 클래스는 이 데이터 유형과 관련된 작업을 구현하는 멤버 함수를 정의할 수도 있습니다. 예를 들어 프로그램 4.1에 정의된 클래스에는 POINT와 거리라는 두 개의 멤버 함수가 있습니다.
프로그램 4.2와 같은 클라이언트 프로그램은 구조체에 포함된 데이터 이름과 동일한 방식으로 이름을 지정하여 개체와 관련된 멤버 함수를 호출할 수 있습니다. 예를 들어, p.distance(q) 표현식은 점 p와 q 사이의 거리를 계산합니다(q.distance(p)를 호출하여 동일한 거리가 반환되어야 함). 프로그램 4.1의 첫 번째 함수인 POINT() 함수는 생성자라고 불리는 특수 멤버 함수입니다. 클래스와 이름이 동일하며 해당 클래스의 객체를 생성하려고 할 때 호출됩니다.
프로그램 4.1. POINT 클래스 구현
이 클래스는 "부동 소수점 숫자 쌍"(데카르트 평면의 점으로 해석되는 것으로 가정)인 값 세트와 모든 인스턴스에 대해 정의된 두 개의 멤버 함수로 구성된 데이터 유형을 정의합니다. POINT 클래스: 0과 1 사이의 임의의 값으로 좌표를 초기화하는 생성자 함수 POINT()와 다른 지점까지의 거리를 계산하는 함수 distance(POINT). 데이터 프레젠테이션비공개이며 멤버 함수로만 액세스하거나 수정할 수 있습니다. 멤버 함수 자체는 공개되어 있으며 모든 클라이언트에서 액세스할 수 있습니다. 예를 들어 POINT.cxx라는 파일에 코드를 저장할 수 있습니다.
#포함하다
프로그램 4.2. POINT 클래스용 클라이언트 프로그램(가장 가까운 지점 찾기)
이번 버전의 3.8 프로그램은 4.3 프로그램에서 정의한 POINT ADT를 사용하는 클라이언트이다. 새 작업에서는 POINT 개체의 배열을 만듭니다(POINT() 생성자를 호출하여 각 개체를 임의의 좌표 값으로 초기화). a[i].distance(a[j]) 표현식은 a[j] 인수를 사용하여 객체 a[i]에서 거리 멤버 함수를 호출합니다.
#포함하다
클라이언트 프로그램에서 POINT p를 정의하면 새 객체에 대한 메모리 영역이 할당되고 POINT() 함수를 사용하여 두 데이터 요소 각각에 0에서 1 범위의 임의 값이 할당됩니다.
객체 지향 프로그래밍이라고도 하는 이러한 프로그래밍 스타일은 C++ 클래스 구조에서 완전히 지원됩니다. 클래스는 데이터가 결합될 뿐만 아니라 이 데이터에 대한 작업도 정의되는 구조 개념의 확장으로 간주될 수 있습니다. 동일한 클래스에 속하는 다양한 개체가 있을 수 있지만 해당 데이터 멤버가 동일한 값 집합을 가질 수 있고 해당 데이터 멤버에 대해 동일한 작업 집합을 수행할 수 있다는 점에서 모두 유사합니다. 일반적으로 이러한 개체는 다음과 같습니다. 동일한 데이터 유형의 인스턴스. 객체 지향 프로그래밍에서 객체는 멤버 데이터를 처리하도록 설계되었습니다(객체에 저장된 데이터를 처리하기 위해 독립적인 함수를 사용하는 것과 반대).
우리는 클래스의 기본 기능에 익숙해지기 위해 위에서 설명한 소규모 클래스 예제를 살펴보겠습니다. 그래서 완성과는 거리가 멀다. 실제 코드에서는 포인트 클래스에 대해 더 많은 작업을 수행하게 됩니다. 예를 들어 프로그램 4.1에는 x, y 좌표 값을 알아내는 연산조차 없습니다. 앞으로 살펴보겠지만 이러한 작업과 기타 작업을 추가하는 것은 매우 간단한 작업입니다. Part 5에서는 점과 선 및 다각형과 같은 기타 기하학적 추상화에 대한 클래스를 자세히 살펴보겠습니다.
C++(C는 아님)에서 구조에는 연관된 기능이 있을 수도 있습니다. 클래스와 구조의 주요 차이점은 키워드로 특징지어지는 정보 액세스와 관련됩니다.
1.2. 추상 데이터 유형
이전 섹션에서 소개된 대부분의 개념은 일반적으로 프로그래밍 입문 과정에서 다루므로 익숙할 것입니다. 추상 데이터 유형만 새로운 것일 수 있으므로 먼저 프로그램 개발 프로세스에서 이들의 역할에 대해 논의해 보겠습니다. 먼저, 추상적인 데이터 유형을 프로시저와 같은 친숙한 개념과 비교해 보겠습니다.
통합 프로그래밍 도구인 프로시저(Procedure)는 연산자의 일반화된 개념으로 볼 수 있다. 기능이 제한된 프로그래밍 언어의 내장 연산자(덧셈, 곱셈 등)와는 달리, 프로시저의 도움으로 프로그래머는 자신만의 연산자를 만들고 이를 기본 연산자뿐만 아니라 다양한 유형의 피연산자에 적용할 수 있습니다. 것들. 이러한 연산자 프로시저의 예는 표준 행렬 곱셈 서브루틴입니다.
프로시저의 또 다른 장점(새 문을 생성하는 기능 외에)은 다음 작업에 사용할 수 있다는 것입니다. 캡슐화프로그램 기능의 특정 측면을 담당하는 모든 연산자를 프로그램의 별도 섹션에 배치하여 알고리즘의 일부를 구성합니다. 캡슐화의 예: 단일 프로시저를 사용하여 모든 유형의 입력을 읽고 유효성을 확인합니다. 캡슐화의 장점은 프로그램 기능에 문제가 발생할 경우 어떤 캡슐화된 명령문을 변경해야 하는지 알 수 있다는 것입니다. 예를 들어 입력 데이터에서 양수 값을 확인해야 하는 경우 코드 몇 줄만 변경하면 해당 줄이 어디에 있는지 정확히 알 수 있습니다.
추상 데이터 유형 정의
우리는 정의합니다 추상 데이터 유형(ATD)는 이 모델의 프레임워크 내에 정의된 일련의 연산자가 있는 수학적 모델입니다. ADT의 간단한 예는 합집합, 교차 및 집합 차이 연산자가 있는 정수 집합입니다. ADT 모델에서 연산자는 ADT에 의해 정의된 데이터뿐만 아니라 다른 유형의 데이터(프로그래밍 언어의 표준 유형 또는 다른 ADT에 정의됨)의 피연산자를 가질 수 있습니다. 운영자 작업의 결과는 지정된 ADT 모델에 정의된 것과 다른 유형일 수도 있습니다. 그러나 우리는 적어도 하나의 피연산자 또는 연산자의 결과가 해당 ADT 모델에 정의된 데이터 유형을 가지고 있다고 가정합니다.
위에서 설명한 프로시저의 두 가지 특징인 일반화와 캡슐화는 추상 데이터 유형을 완벽하게 특성화합니다. 프로시저가 단순 연산자(+, - 등)의 일반화인 것처럼 ADT는 단순 데이터 유형(정수, 실수 등)의 일반화로 생각할 수 있습니다. ADT는 유형의 정의와 해당 유형의 데이터에 대해 수행되는 모든 명령문이 단일 프로그램 섹션에 포함된다는 점에서 데이터 유형을 캡슐화합니다. ADT 구현을 변경해야 하는 경우 프로그램의 작은 섹션 하나에서 찾을 위치와 변경해야 할 내용을 알고 있으며 해당 데이터 유형으로 작업할 때 프로그램의 어느 곳에서나 오류가 발생하지 않을 것이라고 확신할 수 있습니다. . 또한 ADT 연산자 정의 섹션 외에 ADT 유형을 기본 유형으로 간주할 수 있습니다. 유형 선언은 공식적으로 구현과 관련이 없기 때문입니다. 그러나 이 경우 일부 명령문은 둘 이상의 ADT에 대해 시작될 수 있고 이러한 명령문에 대한 참조는 여러 ADT의 섹션에 있어야 하기 때문에 어려움이 발생할 수 있습니다.
ADT 생성으로 이어지는 기본 아이디어를 설명하기 위해 추상 데이터 유형 LIST(정수 목록)의 데이터에 대해 간단한 연산자를 사용하는 이전 섹션(목록 1.3)의 그리디 프로시저를 고려하십시오. 이러한 연산자는 LIST 유형의 newclr 변수에 대해 다음 작업을 수행해야 합니다.
1. 목록을 비워주세요.
2. 목록의 첫 번째 요소를 선택하고 목록이 비어 있으면 값을 반환합니다. 없는.
3. 목록의 다음 요소를 선택하고 값을 반환합니다. 없는,다음 요소가 없으면.
4. 목록에 정수를 삽입합니다.
설명된 작업을 효과적으로 수행할 수 있는 다양한 데이터 구조를 사용할 수 있습니다. (데이터 구조는 주제 2에서 자세히 논의됩니다.) 목록 1.3에서 해당 연산자를 표현식으로 대체하면
MAKENULL(newcJr);
w:= FIRST(newcJr);
w:= NEXT(newcfr);
INSERT(v, newclr);
이것은 추상 데이터 유형의 주요 측면(및 장점) 중 하나를 설명합니다. 어떤 방식으로든 데이터 유형을 구현할 수 있으며 이 유형의 객체를 사용하는 프로그램은 유형이 구현되는 방식에 의존하지 않습니다. 이는 이 데이터 유형에 대한 연산자를 구현하는 프로시저의 책임입니다.
추상 데이터 유형 GRAPH(그래프)로 돌아가 보겠습니다. 이 유형의 개체에는 다음을 수행하는 연산자가 필요합니다.
1. 페인팅되지 않은 첫 번째 정점을 선택합니다.
2. 두 꼭지점 사이에 가장자리가 있는지 확인합니다.
3. 꼭지점을 색상으로 표시합니다.
4. 그려지지 않은 다음 정점을 선택합니다.
분명히 그래프에 정점과 간선을 삽입하거나 그래프의 모든 정점을 음영 처리되지 않은 것으로 표시하는 등의 다른 연산자는 그리디 절차의 범위 밖에 있습니다. 이 데이터 유형을 지원하는 다양한 데이터 구조는 주제 6과 7에서 다룰 것입니다.
이 수학적 모델의 객체에 적용되는 연산자의 수는 제한되지 않는다는 점이 특히 강조되어야 합니다. 각 명령문 세트는 별도의 ADT를 정의합니다. 다음은 SET(Set) 추상 데이터 유형에 대해 정의할 수 있는 연산자의 예입니다.
1. MAKENULL(A), 이 프로시저는 집합 A를 빈 집합으로 만듭니다.
2. 유니온(A, B, C). 이 프로시저는 두 개의 "입력" 인수인 세트 A와 B를 사용하고 이러한 세트의 합집합을 "출력" 인수인 세트 C에 할당합니다.
3. 사이즈(A). 이 함수는 집합 인수 A를 취하고 집합 A의 요소 수와 동일한 정수 유형의 개체를 반환합니다. ADT 구현이라는 용어는 다음을 의미합니다. 이 추상 데이터 유형의 변수를 정의하는 선언의 프로그래밍 언어 명령문으로의 변환 및 ADT 개체에서 실행되는 각 문입니다. 구현은 다음 사항에 따라 달라집니다. 데이터 구조, ATD를 대표하는 각 데이터 구조는 해당 언어에서 사용할 수 있는 데이터 구조화 도구를 사용하여 사용되는 프로그래밍 언어의 기본 데이터 유형을 기반으로 구축됩니다. 배열 및 레코드 구조는 Pascal에서 사용할 수 있는 두 가지 중요한 데이터 구조화 도구입니다. 예를 들어, SET 유형의 변수 S의 가능한 구현 중 하나는 세트의 요소를 포함하는 배열일 수 있습니다. 에스.
동일한 모델 내에서 두 개의 서로 다른 ADT를 정의하는 주요 이유 중 하나는 이러한 ADT의 개체에 대해 서로 다른 작업을 수행해야 한다는 것입니다. 다양한 유형의 연산자를 정의합니다. 이 노트에서는 집합 이론 및 그래프 이론과 같은 몇 가지 기본 수학적 모델만 다루지만, 다양한 구현에서는 특정 ADT의 이러한 모델을 기반으로 다양한 연산자 집합을 구축합니다.
이상적으로는 기본 데이터 유형과 연산자가 ADT를 구현하기에 충분한 언어로 프로그램을 작성하는 것이 바람직합니다. 이러한 관점에서 볼 때 파스칼은 다양한 ADT를 구현하는 데 그다지 적합한 언어는 아니지만, 반면 ADT를 이렇게 직접 선언할 수 있는 다른 프로그래밍 언어를 찾는 것은 어렵습니다. 이러한 프로그래밍 언어에 대한 자세한 내용은 항목 끝에 있는 참고 문헌을 참조하세요.
추상은 일반적으로 프로그래밍 언어에 명시적으로 존재하지 않는 데이터 유형이라고 하며, 이는 상대적인 개념입니다. 한 프로그래밍 언어에 없는 데이터 유형이 다른 프로그래밍 언어에 있을 수 있습니다.
추상 데이터 유형 (ATD)는 구현 방법에 관계없이 정의됩니다.
이 유형의 가능한 값 세트,
이 유형의 값을 가진 일련의 작업.
ADT의 사용은 소프트웨어 개발 단계로 제한될 수 있지만 프로그램에서 명시적으로 사용하려면 프로그래밍 언어의 기존(및 이전에 구현된) 데이터 유형을 기반으로 구현해야 합니다.
이 유형의 값을 표현하는 방법,
이 유형의 값을 사용하여 작업을 구현합니다.
ADT는 프로그래밍 언어에 미리 정의되어 있지 않으며, 더욱이 언어에 미리 정의된 이러한 유형의 구성 작업은 개발자-프로그래머에게 이 유형의 값을 표현하고 값으로 작업을 구현하는 방법에 대한 질문을 옮깁니다. 이 유형의. 따라서 이러한 데이터 유형의 경우 문제는 다음 형식의 작업을 구현하기 위한 정의와 방법을 선택하는 것입니다. 건설자 (값 및 데이터 저장소) 이 유형의 선택자 그리고 수정자 이 유형의 구성 요소(값 및 데이터 저장소)는 프로그래머 개발자에게 있습니다.
ADT 개념에서 개념은 특별한 지위를 갖습니다. 상호 작용 , 사용자에게 공개 구현 , 그에게 숨겨졌습니다. ADT 개념에서 이러한 개념의 특별한 역할은 구현 방법에서 ADT 개념의 독립성에 대한 기본 입장과 관련이 있습니다.
현대의 "실용 프로그래밍 언어"에서는 일반적으로 미리 정의된 유형 구성 작업을 사용하여 ADT를 구성합니다. 수업 이는 개발자-프로그래머에게 데이터 및 작업(이 데이터 포함)을 단일 전체로 그룹화하는 수단뿐만 아니라 이러한 데이터가 구성되고 액세스되는 방식을 제어하는 캡슐화, 상속 및 다형성 수단도 제공합니다. 클래스는 ADT의 가능한 구현 중 하나를 설명하며 클래스와 ADT의 매핑은 추상화 함수로 표현되지만 역관계는 일반적으로 동일한 ADT의 여러 구현이 있을 수 없습니다.
추상적인 데이터 유형 연구에서 개념의 중요한 역할은 " 유형 매개변수화 " 실제로, 예를 들어 ADT "스택"은 스택 요소의 유형에 의존하지 않지만 "일부 동일한 유형의 요소"를 가리켜 이 ADT를 구현하는 것은 불가능합니다. Ada 프로그래밍 언어에는 매개변수화된 데이터 유형을 구성하기 위한 적절한 도구가 처음에 포함되었으며, 현대의 "실용 프로그래밍 언어"에는 STL 라이브러리를 사용한 개발이 출현한 이후에만 등장했습니다. 오늘날 "일반화 프로그래밍"이라는 개념은 "실용 프로그래밍 언어"에 포함되어 실제 프로그래밍에서 중요한 위치를 차지하고 있습니다. 매개변수화된 데이터 유형을 구성하기 위한 도구(템플릿, 주형 , 일반적인) .
위의 모든 것은 방법론적, 이론적 관점에서 "추상 데이터 유형" 개념에 대한 보다 자세하고 정확한 정의가 필요하다는 것을 의미합니다. 이론적으로 "추상 데이터 유형"의 개념은 일반적으로 다음과 같이 정의됩니다. 다중 정렬(다중 기본) 대수 시스템 , 가능한 값 집합(캐리어) 및 해당 값에 대한 작업 집합 외에도 다음 개념이 강조 표시됩니다.
정렬 및 서명 - 이러한 개념을 사용하면 유형에 따라 미디어 요소와 작업을 모두 분류할 수 있습니다(작업의 경우 인수 유형 및 반환 값에 따라).
술어는 캐리어 요소에 대한 관계입니다. 이를 통해 허용되는 값에 제한(요구 사항)을 적용하여 가능한 값의 범위를 결정할 수 있을 뿐만 아니라 이를 집합에 대한 소속 함수 또는 다중 함수로 해석하도록 강요하지 않고 자연스러운 해석으로 임의의 논리식을 사용하여 작업할 수 있습니다. 소중한 운영.
이를 바탕으로 이 유형의 객체에 대한 생성자(유형 및 값), 선택자 및 속성 수정자에 대한 질문을 포함하여 단일 전체론적 논리 대수적 관점에서 추상 데이터 유형을 고려하는 것이 가능합니다.
"데이터 구조"와 "추상 데이터 유형"의 개념은 어떤 면에서는 매우 유사합니다. 물론 이러한 개념은 단순히 동일한 것에 대한 두 가지 견해라고 가정할 수 있습니다. ADT가 값을 나타내는 방식은 항상 다소 복잡하거나 일부 데이터 구조를 기반으로 하며, 이러한 값에 대한 작업 구현은 당연히 선택한 데이터 구조에 따라 달라집니다. 반면에 우리가 정말로 원한다면 언제든지 ADT로서 우리가 관심을 갖는 데이터 구조를 설계할 수 있습니다.
그러나 우리는 다음을 고려하여 이 두 개념을 구별할 것입니다.
추상 데이터 유형 - 구현 방법에 관계없이 적용된(도메인 지향) 데이터 유형을 수정하기 위해 특정 수준의 추상화를 의미하며, 적어도 애플리케이션 라이브러리에 이 데이터 유형을 포함할 수 있습니다. 특정 소프트웨어 시스템의 특정 개발. ADT에는 다양한 데이터 구조를 기반으로 하는 여러 가지 대체 구현이 있을 수 있습니다.
데이터 구조는 오히려 데이터를 구성하고 관리하기 위한 체계로, 특정 문제를 해결하기 위해 특정 상황에서 사용할 때 적절한 사양이 필요합니다.
추상 데이터 유형에는 기본적으로 수학적 기본 대수 시스템(수열, 집합, 관계 및 매핑(함수 관계, 함수))이 포함됩니다. 그러나 프로그래밍에서 전경은 이러한 수학적 개념의 일반적인 속성에 대한 연구가 아니라 주제 영역의 문제 해결을 위한 모델 개발, 이러한 문제 해결을 위한 알고리즘 및 효과적인 구현에 이를 사용할 수 있는 가능성입니다. 개발된 알고리즘. 따라서 ADT 형태의 프로그래밍에서는 이러한 기본 대수 시스템의 제한된 버전이 일반적으로 형식화되고, 다른 한편으로는 응용 프로그램의 관점에서 실용적인 관심을 끄는 특수한 연산 세트로 확장됩니다. 적용 분야.