summ의 블로그

양방향 연결 리스트 양방향 연결 리스트 그전까지와는 다르게 노드들은 동시에 양쪽으로 연결되어 있다. 따라서 연결 리스트 정의는 다음과 같다. typedef struct _node { Data data; struct _node*next; struct _node*prev; } Node; 양방향 연결 리스트의 구현 void LInsert(List*plist, Data data) { Node*newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = plist->head; newNode->prev = NULL; plist->head = newNode; (plist->numOfData)++; } 데이터 조회 LPrevious(List*..

원형 연결 리스트 계속해서 연결 리스트에 관해 알아보자. 원형 연결 리스트 단순 연결 리스트의 마지막 노드 tail은 NULL 을 가리킨다. 그러나 원형 연결 리스트는 마지막 노드는 첫번째 노드를 가리킨다. 그래서 원형을 띄고 있기에 원형 연결 리스트인 것이다. 새 노드의 추가 사실 노드들이 원형으로 연결되어 있기에, 머리와 꼬리의 구분이 명확하지 않으며 우리는 꼬리를 가리키는 포인터 변수만 존재해도 꼬리에 노드를 추가할 수 있다. plist->head = plist->tail->next; 이제 원형 연결 리스트에서 새로운 노드를 추가하는 방법은 다음과 같다. LInsert // 꼬리에 삽입 LInsertFront // 머리에 삽입 더미노드가 존재하지 않기에 당연히 첫 노드와 두번째 이후의 노드의 추가 ..

정렬 연결 리스트에서의 정렬 연결 리스트에서 정렬 기준의 설정과 관련된 부분은 다음과 같다. 정렬 ADT void SetSortRule(List * plist, int (*comp) (LData d1, LData d2)); void SetSortRule(List * plist, int (*comp) (LData d1, LData d2)) { plist->comp=comp; } SetSortRule 함수는 리스트의 멤버 comp를 초기화하며, SInsert 함수에서 comp에 등록된 정렬의 기준을 근거로 데이터를 정렬하여 저장한다. while(pred->next != NULL && plist->comp(data, pred->next->data) != 0) { pred = pred->next; } 반복문을 ..

정렬 기능 | 더미노드 정렬 기능 ADT void SetSortRule(List * plist, int(*comp)(LData d1, LData d2)); 정렬 기준이 되는 함수를 등록 더미 노드 더미노드란? 유효한 데이터 값을 갖지 않는 노드, head가 가리키는 노드 더미노드를 추가하는 이유: 보다 간결한 코드를 위해서 연결 리스트에서 첫번째 노드와 그 이후의 노드의 추가 및 삭제 방법이 다르다. 그러나 더미 노드를 추가한다면, 노드 번호와 상관없이 동일한 과정을 거친다. 연결 리스트 - 삽입 - 참조 포인터 변수의 이동 - 삭제

연결 리스트 지난 포스팅에 이어 연결 리스트에 관해 알아보려 한다. 우선 메모리 할당에 관해 알아보자. 메모리의 동적 할당 malloc() 함수 : 메모리를 동적으로 할당하여 반환 free() 함수 : 동적으로 받은 메모리 공간을 해제 연결 리스트 앞서 말했듯이 배열은 길이가 초기에 정해져 있어야 한다. 이러한 단점을 보완하기 위해 연결 리스트를 사용한다. 연결 리스트는 동적 할당된 메모리들을 순차적으로 연결하는 것이다. 따라서 첫 (메모리) 노드 head 부분의 주소값만 알고 있다면, 메모리들은 순차적으로 연결되어 있기에 나머지의 주소값을 몰라도 접근이 가능하다. 연결을 어떻게 시키는지 순차접근을 어떻게 하는지 에 관해 공부하는 것이다. 구조체 정의 typedef struct _node{ int dat..

추상 자료형 | 리스트 자료구조 추상 자료형 ADT 추상 자료형이란? Abstract Data Type 약자 ADT 라고 부르며, 어떠한 행위나 사물에서 구체적인 기능의 완성 과정을 언급하지 않고, 순수하게 기능만을 나열한 것이다. 리스트 다른 언어를 공부할 때 배웠던 리스트의 자료구조에 관해 알아보자 리스트는 구현 방법에 따라 두 가지 형태로 나뉜다. 1. 순차 리스트 : 배열을 기반으로 구현, 배열의 길이 초기에 구현 2. 연결 리스트 : 메모리의 동적 할당을 기반으로 구현 헤더파일 #include "ArrayList.h" 리스트 자료구조의 ADT void ListInit(List * plist); // 초기화할 리스트의 주소 값을 인자로 전달 // 리스트 생성 후 제일 먼저 호출되어야 하는 함수 v..

recursive 재귀함수 나무위키에 따르면 재귀함수 (recursion) 는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 일단 무언가를 설명할 때 자기를 포함한 것이라고 이해하면 편하다. 즉, 재귀함수는 함수 내에서 자기 자신을 다시 호출하여 복사본을 만든 후 복사본을 실행하는 함수이다. void recursive(void) { printf("recursive call"); recursive(); }​ 재귀함수를 사용할 때 탈출조건을 정립하지 않으면 계속해서 재귀함수가 실행된다. 따라서 함수가 실행을 멈추게 되는 탈출 조건의 정립이 필요하다. 재귀함수의 활용으로 팩토리얼 계산, 피보나치 수열, ..

이진 탐색 알고리즘을 수행하기 전 한 가지 조건은 "배열에 저장된 데이터는 정렬이 되어있어야 한다." 이다. 이진 탐색 알고리즘은 배열을 반으로 줄여나가면서 내가 찾고자 하는 값의 위치를 알아내기 때문이다. 단계별로 소개해보면, 1. 배열 인덱스의 시작과 끝을 더한다. 2. 1의 결과값을 2로 나눈다. 3. 2의 결과값이 인덱스가 되며, 저장된 값이 내가 원하는 값인지 확인한다. 4-1. 맞음 4-2. 아니라면 3에서의 저장된 인덱스 값과 내가 원하는 값의 대소를 비교한다. 5. 인덱스를 기준으로 4의 결과에 의해 탐색의 범위를 제한할 수 있다. 6. 다시 1으로 돌아가 제한된 인덱스의 시작과 끝을 더한다. 7. 결과값을 2로 나눈다. (정수부분만 취함 8. 인덱스에 저장된 값이 내가 원하는 값인지 확인..

탐색 알고리즘에서 가장 먼저 접하게 되는 알고리즘이다. 이름에서부터 알 수 있듯이 내가 찾고자 하는 값을 차례대로 찾아 나서는 것이다. 코드로 보자면 다음과 같다. 앞서 말한대로 좋은 알고리즘을 위해서는 시간이 단축되어야 하며, 순차 탐색 알고리즘의 시간 단축을 위해서는 위의 코드에서 볼 수 있듯이 == 비교 연산자의 횟수가 적어야 한다. 이 알고리즘은 배열의 길이가 길면 연산 횟수가 많아져 시간이 오래 걸리는 단점이 있다.

자료구조를 배워야 하는 이유 위키백과에서 보면, 자료구조(資料構造, data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 데이터의 표현 및 저장방법을 뜻하는 자료구조를 파악하고 있다면 효율적인 알고리즘을 사용이 가능하다. 이는 적은 메모리의 사용과 처리 속도의 향상으로 이어진다. 자료구조의 구분 크게 4가지 구조 선형구조, 비선형구조, 파일구조, 단순구조로 나뉜다. 선형구조 | 리스트 / 스택 / 큐 비선형구조 | 트리 / 그래프 파일..