콘하드

배열

정의

프로그래밍 언어를 지원하는 재료 유형 또는 컴퓨터 과학에 사용되는 재료 구조 중 하나입니다. 차례로, 숫자가 매겨진 요소는 연속적인 형태로 구성된 구조를 암시하며,이 경우 각 요소에 부착된 숫자를 종종 첨가제 (인덱스, 색인)라고합니다. 요소가 연속적으로 배열되기 때문에 각 요소에 대한 모든 첨부 파일에 접근하는 시간 복잡성은 O (1)입니다. 따라서 임의로 액세스 할 수 있는 데이터 구조에 속합니다. 메모리 주소는 연속성을 요구하기 때문에 배열 크기가 증가하는 것은 절대적으로 불가능하며 배열 크기가 커야 할 때 더 큰 크기의 새 배열을 만들고 기존 콘텐츠를 복사하고 일부 배열을 다른 위치에 연결하는 등의 방법이 필요합니다. 그것은 이용 가능합니다.

연결 목록과 비교하여 임의 접근을 사용할 수 있지만, 요소를 삽입 / 삭제하는 데는 단점이 있습니다. 반면에 연결 목록은 연속 접근만 가능하여서 어떤 위치에서든 요소를 찾는 것이 느리지만, 위치를 알면 삽입 / 삭제가 배치보다 빠릅니다.

데이터 구조와 데이터 구조의 차이

데이터 구조로서 배열은 색인을 가지며 차례로 구성된 데이터 구조를 의미하며 이 색인에 의해 접근할 수 있습니다. 데이터 유형으로서 배열은 프로그래밍 언어의 문법적 수준이며 기본 재료 유형으로 이러한 재료 구조, 배열을 지원합니다.

컴퓨터 과학 초기에 등장한 어셈블리 및 여러 프로그래밍 언어는 문법 수준에서 배열을 지원하지 못했습니다. 그러나 기본적으로 현실적인 필요성으로 FORTRAN, COBOL 및 ALGOL과 같은 초기 고급 언어에서 이를 지원하기 시작했으며 이후 거의 모든 프로그래밍 언어의 필수 구성 요소가 되었습니다.

일반적으로 유형 시스템이 있는 언어에서는 한 유형의 요소에 의해서만 받아들여지는 경우가 많지만, 이는 일반적으로 연속 메모리 공간의 값이 행 당이기 때문에 하드웨어 이유로 구현됩니다. C의 이 점은 가장 분명하게 느낄 수 있습니다.

같은 이유로 대부분의 프로그래밍 언어는 0에서 배열 첨부 파일을 시작합니다. N의 요소로 절차 A를 생성하면 해당 요소를 참조할 때 A [0], A [1], ..., A가됩니다. 그것은 [N-1]을 가리키며, 첫 번째 요소는 A [1]이 아니라 A [0]이기 때문에 프로그래밍에 익숙하지 않은 사람들 사이에서 혼란의 원인 중 하나가 됩니다.하드웨어와 역사적 이유, 논리적 이유 모두가 방법을 채택하기 위해 존재합니다.

리스트

정의

추상 데이터 유형, 데이터 구조 중 하나. 시퀀스라고도하며 시퀀스에 나열된 요소 집합으로 정의됩니다. 순서가 있다는 점에서 세트와 구별되며, 분리되지 않고 칼럼에 쓰여지고, 1단과 끝 각각이 하나뿐이라는 점에서 그래프와 구별됩니다.

연결 리스트는 컴퓨터에서 사용할 수 있도록 목록을 구현하는 목록입니다.

목록의 각 요소는 차례로 번호가 매겨질 수 있으며,이 숫자는 요소를 찾을 수 있는 작업을 추가하는 데 사용될 수 있지만, 따라서 배열은 목록 유형에서도 볼 수 있습니다. 때로는 C와 같이 만들기 어려운 언어로 목록이 필요할 때 동적으로 할당된 시퀀스와 같습니다. 필요한 연산을 구현하는 것은 장점, 단점 및 필요한 코드만 생성할 수 있으며 연산 제한이 필요한 경우 제어할 수 있습니다. 단점은 버그가 실제로 코드를 만들지 않는한 반드시 일어나야하는 구조라는 것입니다. 라이브러리를 사용하면 약점이 무엇인지 알기 때문에 이를 피하는 코드를 만들 수 있지만 직접 만들면 불가능합니다.

LISP는 원래 목록 작업을 위해 시작되며 언어의 모든 장소에서 목록을 적극적으로 사용하는 것은 말할 것도없고 LISP 프로그램 코드 자체도 즉시 목록 자체입니다. 목록을 적극적으로 작성하는 목록에서 사용되는 메모리를 관리하는 데 사용할 수 없는 가비지 수집 방법이 사용된 것은 이번이 처음입니다. 이로 인해 영향을받는 기능 언어의 경우 LISP와 마찬가지로 모든 위치에서 목록을 활용하지 않지만 목록을 작성하거나 관리하기가 더 쉽습니다.

자바의 경우 대표 목록 시리즈에는 벡터, 배열 목록 및 링크드 목록이 있습니다. 그것은 배열 목록이 벡터의 경우 발생하기 전에 사용했던 배열 기반 목록이며, 벡터는 가장 최근의 책에도 소개되지 않았습니다. 사실, ArrayList는 대부분의 경우 권장되지만 스레드별 동기화가 필요한 경우 ArrayList를 통해 벡터를 쓰는 것이 좋습니다.(그러나 링크드리스트에게 우리가 대부분의 알고리즘과 데이터 구조에서 배우는 연결 목록이 옳다고 말합니다. 가능한한 많이 사용하지 마십시오. 순수한 연결 목록과의 차이점은 피크 연산 (방법)과 팝 연산 (방법)을 사용하여 대기열로 사용할 수 있다는 것입니다.

해시

정의

해시 함수는 길이가 있는 모든 데이터에 대해 고정 길이의 데이터에 매핑하는 함수를 의미합니다. 이러한 해시 함수를 적용하여 나온 고정 길이의 값을 해시 값으로합시다. 해시 코드, 해시 아일랜드 (섬), 체크 아일랜드라고도합니다.

해시 함수는 일반적으로 덜 복잡한 알고리즘으로 구현되므로 상대적으로 CPU, 메모리 등과 같은 시스템 리소스를 소비하는 특성을 가지고 있습니다. 동일한 입력 값에 대해 동일한 출력이 보장되며,이 출력은 가능한한 균일하게 분포되는 특성을 가지고 있습니다. 또한 특수 목적을 위해 해시 값을 생성하고 동일한 입력에 대해 다른 출력 값을 가질 수 있는 원본의 다른 값을 입력하는 해시 함수가 있습니다.

해시 함수는 일반적으로 입력 값보다 출력 값의 범위가 좁기 때문에 입력의 차이에도 불구하고 동일한 값이 거의 출력되지 않을 때 존재합니다. 세부 원칙은 비둘기 집의 원칙과 생일을 나타냅니다. 이러한 경우를 충돌이라고합니다. 원칙적으로 해시 함수는 이러한 피할 수없는 충돌을 제외하고는 의도적으로 충돌을 계산할 수 없습니다. 간단한 설명은 위키 백과의 충돌 저항 부분을 나타냅니다.

이러한 속성에 의해 지원되고 다양한 목적으로 설계된 해시 함수가 있으며 다음과 같은 다양한 분야에서 매우 유용하게 사용됩니다.

해시를 이용한 데이터 구조

해시 값을 인덱스에 사용하여 빠른 검색, 정렬없이 빠른 삽입을 허용하는 데이터 구조입니다.

해시는 목록을 사용하는 것과 동일한 접근법이지만 색인 개념이 추가됩니다.한 번 충분한 공간을 할당 받고 다음 해시 함수를 사용하여 고유한 색인을 만듭니다. 그리고 이 독특한 색인과 일치하는 위치에 데이터를 저장합니다.

해시 함수가 나무 위키라는 단어에 적용되고 색인이 생성 될 때 목록 2642 색인에 나무 위키를 저장하는 방법의 예입니다. 해시 함수는 항상 동일한 해시 값을 반환하므로 트리 위키에 들어가면 항상 2642와 색인을 찾을 수 있으므로 정렬하지 않고 즉시 찾을 수 있습니다. 그러나 이러한 목적으로 사용되는 해시 함수는 해시 값을 계산하는 비용이 기존 검색 알고리즘보다 훨씬 적어야 한다는 전제 조건을 가지고 있습니다. 그렇지 않으면 이러한 방법을 사용하는 것은 의미가 없습니다.

해시 값이 충돌하는 경우와 동일한 색인이 때때로 생성됩니다. 예를 들어 해시 함수에 나중에 위키위키라는 단어를 입력하고 2642로 색인을 나오면 나무 위키와 같은 색인을 갖게 됩니다. 이 경우 일반적으로 사용되는 두 가지 방법이 있습니다. 하나는 목록의 각 색인을 연결 목록으로 만들고 다음 색인의 빈 위치에 배치하는 오픈 주소 방법이며, 새로운 입력이 획득 될 때마다 분리 연결이 있습니다.

이 충돌을 해결해도 충돌 성능을 막을 수 없기 때문에 수용률이 일정량을 초과하면 처음부터 목록 자체의 크기를 재조정하는 방법을 사용할 수 있습니다. 그런데 이 과정 자체가 굉장히 비싼 과정이기 때문에 실시간으로 빨리 처리할 수는 없습니다. 이렇게 되면 또 다른 큰 목록을 만들어서 점차적으로 적기에 이동하는 확장 방식도 있지만, 이동하는 기존 테이블을 제거하는 방식도 있습니다. 그런데 이 경우에 기억이 훨씬 더 많이 쓰이는 거죠.

또는 해시의 비트 수를 증가시키는 몇 가지 방법; 항목 수가 적을 때 비트 수는 1 비트 증가하며, 짧은 (덜 비트) 해시와 작은 스토리지를 사용하는 빈번한 충돌로 스토리지가 두 배가됩니다. 그리고 점차적으로 확장된 공간으로 항목을 전송함으로써 충돌을 줄일 수 있습니다. 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 일관된 망설임이라고합니다.

데이터가 기본적으로 정렬되지 않은 상태로 저장되기 때문에 정렬된 순서로 액세스하는 데 비용이 많이 들고 우회할 때도 잘못된 값이 많이 들고 실제 데이터 수를 우회하는 것보다 비용이 많이 들고 임계점을 많이 봐야 한다면 실제 데이터보다 더 많은 메모리를 사용할 것입니다.

그래프

정의

중국어로 차트를 작성한 건데, 테이블에 모인 통계를 간단히 보여주는 것도 좋지만 읽기 편해서 사람을 보는 게 참 답답합니다. 그러나 이러한 데이터를 점, 선 등을 사용하여 그래프로 표현하면 첫눈을 보는 것이 더 좋습니다. 변화의 추세와 추세를 파악하는 데 도움이됩니다. 데이터를 보는 사람들은 직관적이고 이해하기 쉽기 때문에 통계를 받아들이기 쉽습니다.이 장점은 많은 신문 기사, 서적, 논문 및 자료가 후원합니다.

데이터에 적합한 그래프가 있으며 일반적으로 막대 그래프, 끊어진 선 그래프, 하나의 그래프 (도넛 그래프), 방사형 그래프를 사용합니다.

컴퓨터 공학 개념

그래프는 정점과 정점을 연결하는 가장자리로 구성되며, 일반적으로 정점은 원으로 표시되며 가장자리는 화살표 또는 선으로 표시됩니다. 화살표로 변경을 나타내는 경우 해당 방향으로만 이동할 수 있으며이 그래프는 디그래프라고합니다. 반대로 선 세그먼트로 표현하면 양방향 모두 이동성이 있으며,이 그래프는 방향이없는 그래프라고하며 가장자리의 경우 특정 숫자를 가질 수 있지만 비늘 (가중치)을 만드는 데 사용할 수 있습니다. 가치).

예를 들어, 도시와 도시를 연결하는 도로를 고려할 때 그래프는 단순화된지도이며, 16 번은 도시를 도시와 연결하는 도로입니다. 도로 길이나 각 도로의 통행료를 적게 내면 도로의 무게입니다.

위에서 언급했듯이 그래프는 도시 나 도로와 유사할 수 있기 때문에 두 지점 사이의 최단 경로 (또는 가장 저렴한 경로)를 얻기 위해 널리 사용되며 그래프는 도시 사이의 최단 경로를 얻는 데 사용됩니다. 그것은 많은 지역뿐만 아니라 도로에서도 널리 사용되며 컴퓨터 네트워크 및 SNS에서의 우정을 포함하여 여러 상황을 모델링하는 데 사용됩니다. 예를 들어, 일부 웹 페이지가 있는 페이지에 연결된 링크를 다른 페이지의 가장자리로 볼 때 트리 위키를 거대한 그래프로 볼 수 있습니다.

위 그림에서 2, 3, 4, 5의 도시 (피크)는 서로 연결되어 순환 할 수 있으며, 이는 2 번가에서 3, 4 및 5 번가를 거쳐 2 번가에 다시 도달 할 수 있음을 의미합니다.이 비순환 그래프는 나무 (그래프)라고도합니다.

트라이

정의

우리가 여러 문자열을 가지고 있을 때, 그문자열이 어떤 문자열중 하나인지 어떻게 알 수 있을까요?

컴퓨터는 효율적이지 않으며 비교만 합니다. 예를 들어, 최대 길이가 mm인 nns 세트에서, 같은 방식으로, 최대 길이가 mm인 문자열이 문자열 세트에 포함되어 있는지 여부를 변경하면, 우리는 전처리가 필요하지 않지만 최악의 경우 O (nm)O (nm)의 비교 수가 필요합니다.

이 문자열을 정렬 한 후 이진 탐색이라는 강력한 알고리즘을 사용하여 O (m log n)O (mlogn)로 단축 할 수 있지만 정렬 프로세스 자체에는 O (n m log)가 있습니다. n)O (nmlogn) [1]에 시간이 걸리기 때문에 사양이없는 컴퓨터 인 경우 비효율적이지만 위에서 설명한 시간 복잡성을 압도합니다. 그것은 존재합니다. 프레드킨이 명명한 트리라는 재료의 구조를 설명하는 가장 효율적인 문자열 검색 방법은 이제입니다.

구조

기본적으로 영어 사전을 고려할 때 쉬운 K-jintrees의 구조가 있으며 접두사에서 c의 지수를 찾아 c라는 단어를 발견한 다음 a, n을 순서대로 검색합니다. 컴퓨터에 논리적으로 적용된 구조는 삼중 구조입니다. 예를 들어, tea라고 불리는 문자열이 입력되고 다음 e가 등록되면 초기 t가 순서대로 등록되고 다음 a가 끝에 발견되면 위치가 여기 문자열이 있다고합니다. 이것은 라고 불리며, 그러한 시작 문자열을 접두사라고합니다.

이러한 3 구조는 그들이 찾고 있는 많은 문자열 공간을 사용하는 대신 문자열의 길이에 따라 빠른 검색을 허용합니다.

일반적으로 동적 할당을 통해 생성되지만 배열을 통해 구현하는 방법을 설명합니다.

트리에 등록하려는 문자열 p를 처음 갖는 것입니다 (편의를 위해이 문자열이 알파벳 소문자로만 구성되었다고 가정 함).

그리고 항상 0의 트리의 루트이며,이 0으로 시작하여 다음 노드로 이동할 수 있는지 여부는 p [i]-a에 대해 결정됩니다.

이동할 수 있고 이동할 수 없는 경우 시도에 1을 추가한 다음 새 노드를 만든 다음 이 항목에서 가르칩니다.

동적 할당을 사용할 수 있는 전문가는 할당 후 그렇게 말할 수 있습니다.

시간 복잡도

문자열 길이가 시간 복잡화되면 문자열 길이가 mm이면 시간 복잡도가 O (m)O (m)입니다. 이유는 간단합니다. nn과 mm가 상대적으로 작으면 구현할 때 배열이 사용됩니다.현재 노드 위치가 i, j 문자인 경우 O (1)O (1)에서 트리 [i] [j]의 위치를 조회할 수 있습니다. 여기서 mm 숫자를 수행하면 O (m)O (m)에 시간이 걸릴 수 있지만 nn과 mm가 크면 메모리를 확보하는 데 시간을 낭비하더라도 std : : : : map으로 시도할 수 있습니다. 시간 n)O (mlogn)를 소비합니다.

트리

정의

자녀의 자녀가 부모 노드에 연결되면, 그것은 다시 자녀 노드에 연결된 여러 자녀 노드가 있는 데이터 구조의 재귀 형태이지만 일반적으로 트리로 인식되지 않습니다. 트리는 몇 가지 기본적이고 흥미로운 특성을 가지고 있지만 트리 구조에서 일부 노드를 취하면 이러한 생성된 연결되지 않은 트리의 수는 해당 노드에 연결된 가장자리 수와 동일합니다.

자식 노드에서 부모로 계속 올라가면 결국 부모없이 하나의 노드로 이어집니다. 이 노드는 루트 노드라고 불리며 루트 노드 주위에 줄 지어있는 그림은 트리의 구조와 유사하며 때로는 인테이트라고도하는 트리라고합니다.

뿌리가 없는 나무를 정의하지 않는 나무로 뿌리를 뽑자.

뿌리가 있는 나무에서는 다른 용어가 정의됩니다. 높이는 뿌리의 높이를 0으로 정의하고 아이의 높이는 원래 노드보다 큰 것으로 정의됩니다. 마지막으로 노드의 정의는 아이가 없는 노드입니다. 라우팅 트리에서 엔드 노드를 1도 노드로 정의합니다.

이진 트리

가장 간단한 형태의 나무는 부모 노드 아래에 두 명의 자녀 만 있으며, 두 명의 자녀는 왼쪽과 오른쪽 자녀로 나뉘며, 두 개의 포인트 포인터는 각각 하나의 값, 왼쪽 및 오른쪽을 가리키는 것입니다.

일반적으로 n-child를 가질 수있는 트리 구조에서, 원래의 자식 노드는 하나 이상의 각 자식에 하나의 노드를 추가하고 오른쪽에 형제 노드 (좌우, 우측)가 추가되어 2 진 트리 구조로 변환 될 수 있습니다. 따라서 모든 나무는 이진 트리 형식으로 재구성 될 수 있습니다 (같은 것이 사실입니다). 따라서 나무는 특별한 이유없이 이진 트리에서 구현됩니다.

이진 탐색 트리

이진 트리의한 유형인 노드의 왼쪽 분기는 노드의 값보다 작은 값만 가지고 있었고 오른쪽 분기는 큰 값으로만 구성되었습니다. 또한, 노드의 좌식 분기는 좌식 값보다 작은 값만 가지고 있으며, 좌식 분기는 좌식 값보다 큰 값만 가지고 있으며, 이진 탐색 트리의 어느 쪽이 이진 탐색 트리를 가지고 있는지에 관계없이 동일한 규칙으로 정렬된 우측 분기가 있습니다. 같은 방식으로 배열됩니다.

이러한 방식으로 구성되면 일부 값 n을 찾을 때 루트 노드에 비해 n이 작으면 루트 노드보다 큰 값으로 모인 오른쪽으로 항해할 필요가 없습니다. 마찬가지로, n이 루트 노드의 왼쪽 자식보다 크면 왼쪽 자식을 탐색할 필요가 없습니다. 즉, 트리 자체는 이진 탐색에 적합한 구성입니다. 값을 찾을뿐만 아니라 값을 삽입하거나 삭제할 때 동일한 과정을 거치기 때문에 이상적인 상황에서 검색 / 삽입 / 삭제는 모두 시간 복잡성 O (log N)를가집니다.

단점은 값이 삽입되거나 삭제되면 운이 좋다면 O (N)가 최악의 경우 시간이 걸립니다.예를 들어, 빈 이진 항법 트리에 1에서 100 순서로 삽입하면 첫 번째 루트 노드는 1보다 크고 3은 1보다 커서 1의 오른쪽 아이가 되어 1의 오른쪽, 2의 오른쪽입니다.이 방식으로 트리의 오른쪽 끝으로 계속 자랍니다. 50을 찾아서이 상태로, 결국에는 더 이상 선형 항법 또는 다른 것이 1에서 오른쪽으로 내려 가지 않고 나무가 원래대로 되었다고합니다. 어떤 경우에는 비켜가세요.

스레드 이진 트리

왼쪽 또는 오른쪽 자식 노드가 없는 노드의 링크를 중간 탐색에서 리드 노드 또는 후속 노드에 연결하는 이진 트리입니다. 현재 링크가 자식 노드인지 또는 선행 노드인지 또는 후속 노드인지 여부를 나타내는 플래그가 자식 노드에 대한 링크에 추가됩니다.반복 호출이나 스택을 사용하지 않고도 중위 검색을 구현할 수 있으며, 연속 검색 속도가 빨라집니다. 삽입 / 삭제시 링크를 다시 연결하는 프로세스가 필요하기 때문에 일반적인 이진 트리보다 구현이 더 복잡합니다.