Algorithm | 달콤 쌉싸래한 인생

Archive for the ‘ Algorithm ’ Category

[제5장]연결 리스트

-단일 연결 리스트

각 항목들이 하나의 포인터로 연결된 가장 단순한 연결 리스트다. 리스트의 첫 항목부터 마지막 항목까지 순회할 수 있다.

-이중 연결 리스트

각 항복들이 두 개의 포인터로 연결된 연결 리스트다. 양 방향으로 순회할 수 있다.

-원형 리스트

마지막 항목의 포인터가 NULL 대신에 첫 항목을 가리키는 연결 리스트다. 리스트를 원형으로 순회할 수 있다.

- 최악 분석

대부분의 알고리즘들을 비교하는 방법이다. 다른 방법으로는 평균과 최상의 경우를 생각할 수 있으나 보통 최악 분석이 몇 가지 장점을 제공한다.

- O-표기법

알고리즘의 성능을 표현하기 위해 가장 흔히 사용되는 표기법이다. O-표기법은 함수의 계수 범위 내의 상위 한계를 표현하는데 사용된다.

- 계산 복잡도

알고리즘이 다루는 자료의 크기에 따라 필요한 자원(일반적으로 시간)의 증가율이다. O-표기법은 알고리즘의 복잡도를 정형적으로 표현하는 방법이다.

포인터의 기본

포인터를 이해하는 최상의 방법 중 하나인 다이어그램을 포함한다. 또 다른 포인터 사용의 기본적 측면은 매달린 포인터를 피하는 방법을 배우는 것이다.

기억장소 할당

메모리 공간을 확보하는 과정이다. 포인터를 사용하면 실제로 메모리에 자유자재로 접근할 수 있으므로 포인터를 기억장소 할당과 연관지어서 이해하는 것이 특히 중요하다.

집합체와 포인터 계산

C에서 집합체는 구조체와 배열이다. 포인터 연산은 포인터로 수행되는 계산 규칙들을 정의한다. 구조체의 포인터는 자료구조를 만들 때 중요하다. C에서 배열과 포인터는 같은 방식으로 포인터 연산을 사용한다.

함수의 매개변수로서의 포인터

C에서 참조 호출 매개변수 전달을 흉내내는 수단이다. C에서 포인터를 배열과 큰 구조체를 전달하는 효율적인 수단으로 사용하는 것도 일반적이다.

포인터의 포인터

자료 대신에 다른 포인터를 가리키는 포인터이다. 포인터의 포인터는 특히 함수의 매개변수로 흔히 사용된다.

일반 포인터와 캐스트

C의 형 시스템을 무시하고 회피하는 메커니즘이다. 일반 포인터는 당장에는 자료형으ㅔ 개의치 않고 자료를 가리킬 수 있게 한다. 캐스트(casts)는 임시로 변수의 형을 바꿀 수 있게 한다.

함수 포인터

자료를 가리키는 대신 실행 가능한 코드 또는 실행 가능한 코드를 호출하는 데 필요한 정보 블록을 가리키는 포인터이다. 함수를 마치 자료 조각처럼 저장하고 다루는데 사용된다.