메모리 구조 프로그램이 실행되기 위해서는 먼저 프로그램이 메모리에 로드(load)되어야 하는데, 프로그램에서 사용되는 변수들을 저장할 메모리도 필요하다. 따라서 OS는 프로그램의 실행을 위해 다양한 메모리 공간을 제공하고 있는데 대표적으로 프로그램이 OS로 부터 할당받는 메모리 공간은 다음과 같다. 코드(code) 영역 메모리의 코드영역은 프로그램의 코드가 저장되는 영역으로 CPU는 코드 영역에 저장된 명령어를 하나씩 가져가 처리한다. 데이터(data) 영역 메모리의 데이터영역은 프로그램의 전역변수와 정적(static)변수가 저장되는 영역이며, 프로그램의 시작과 함께 할당되며, 프로그램이 종료하면 소멸한다. 스택(stack)영역 메모리의 스택영역은 함수의 호출과 관계된는 지역변수와 매개변수가 저장되는 영..

C++ 코드의 주요 요소 #include int main(){ std::cout

- 일종의 리스트 - 단, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐 - LIFO( Last-In, First-Out ) - 삽입/삭제가 일어나는 쪽을 스택의 top이라고 부른다. - push : 스택에 새로운 원소를 삽입하는 연산 - pop : 스택의 top에 있는 원소를 스택에서 제거하고 반환 - peek : 스택 top의 원소를 제거하지 않고 반환 - empty : 스택이 비었는지 검사 - 입력 수식의 괄호가 올바른지 검사 예) [a+b*{c/(d-e)}] + (d/e) - 단순히 여는 괄호와 닫느 괄호의 개수 비교 만으로는 부족 - 스택을 이용하여 검사 - 여는 괄는 스택에 push - 닫는 괄호가 나오면 스택..

이제부터 이중연결리스트를 응용한 알고리즘을 살펴보겠습니다. 다음은 Music Library Program의 실행예입니다. 다음은 저장된 음악 프로그램 목록입니다. 아티스트와 음악 저장경로를 구분하기위해 #을 사용하였습니다. 다음은 Artist,Song,path간에 자료구조를 나타낸 그림입니다. 좀 더 자세히 살펴보면, Artist 노드안에 이중연결리스트로 구현된 SNode가 존재하고 하나의 SNode안에 Song노드가 존재하여 해당 Song의 정보를 나타내고 있습니다. 여기서 주의해야 할 점은 Song은 SNode안의 하나의 데이터일 뿐 연결리스트가 아닙니다. 이처럼 번거롭게 자료구조를 편성한 이유는 즉, 노드와 데이터를 분리하는 이유는 노래들에 대해서 다양한 접근경로를 제공하기 위해서입니다. 예를들어 ..

단방향 연결 리스트(single linked list)의 한계 - 어떤 노드의 앞에 새로운 노드를 삽입하기 어려움 - 삭제의 경우에 항상 삭제할 노드의 앞 노드가 필요 - 단방향의 순회만이 가능 이중 연결 리스트 - 각각의 노드가 다음(next)노드와 이전(previous)노드의 주소를 가지는 연결 리스트 - 양방향의 순회(traverse)가 가능. 각 노드에 하나의 문자열이 저장된다고 가정하자. #include #include struct node { char *data; struct node next; struct node prev; }; typedef struct node Node; Node *head; Node *tail; int size = 0; 노드를 삽입하는 경우를 알아봅시다. 이 과정은 순..

연결리스트를 활용하여 다항식의 문제를 푸는 계산기를 만들어봅시다. 이때, 계수는 정수이고 지수는 양의 정수라고 가정하겠습니다. ( 활용 예 ) - 연결리스트를 이용하여 하나의 다항식을 표현하는 구조체 Polynomial을 정의한다. - 다항식을 항들의 연결 리스트로 표현한다. - 항들을 차수에 대해서 내림차순으로 정렬하여 저장하며,동일 차수의 항을 2개 이상 가지지 않게 한다. 또한 계수가 0인 항이 존재하지 않게 한다. - 하나의 항은 계수와 지수에 의해 정의된다. 하나의 항을 표현하기 위해 구조체 Term을 정의한다. - 변수 x의 값이 주어질 때 다항식의 값을 계산하는 함수를 제공한다. 우리가 원하는 다항식의 자료구조 다항식 이름을 저장하고 , 다항식의 항의 개수, 각각의 항을 나타내는 구조체까지 ..

연결리스트에서 노드의 추가와 삭제에대해 알아보았으니 이제 연결리스트를 순회하는 방법에대해 생각해 봅시다. 당연하게도 어떤 노드가 어느 위치에 존재하는지 , 존재는 하는지 등 알아보기 위해서는 순회가 필요합니다. 위 함수는 특정 노드의 주소를 반환하는 함수입니다. 첫번째 노드부터 찾기 시작해 운이 좋지않으면 맨 마지막 노드까지 순회하는 방식입니다. 전에는 add_first, add_after 함수를 만들어 살펴보았는데 이제는 index에 추가하는 함수를 만들어 보았습니다. 여기서 중요한 점은 index가 0이냐 0이 아니냐의 차이인데 이는 추가하거나 삭제할 노드가 맨 앞에 있는지 그렇지 않은지를 판단하는 조건입니다. 자, 이제 index를 통한 제거를 알아봤으니 특정 데이터를 주고 그 데이터를 찾아 삭제하..

이제 연결리스트에서 노드의 삭제과정에 대해 알아보겠습니다. 노드 추가와 마찬가지로 삭제에도 2가지 경우가 있습니다. 첫번째는 맨 앞에 있는 노드를 삭제하는 경우이고, 두번째는 어떠한 노드의 다음 노드를 삭제한는 경우입니다. 첫 번째 노드를 삭제한다는것은 간단합니다. 첫 번째 노드를 가리키고 있는 head를 두번째 노드를 가리키도록 수정하면 됩니다.

이번 시간에는 새로운 노드를 추가하는 과정에 대해 알아보겠습니다. 추가할때는 2가지 경우의 수가 존재합니다. 맨 앞에 추가하거나, 어떤 노드 바로 뒤에 추가하는 경우가 있습니다. 위와 같이 새로운 노드를 맨 앞에 추가할 경우 첫번째 노드를 가리키는 포인터 head를 보겠습니다. 만약 head가 전역변수일 경우 위 코드와 같이 head = temp 처럼 포인터 변수간에 치환문을 사용하면 됩니다. ( 위 코드의 순서는 필수적으로 지켜져야 합니다. ) 하지만 만약 포인터 head변수가 전연변수가 아니라면 어떻게 될까요 ? 만약 add_frist 함수를 약간 수정해서 인자로 Node *head를 받는다고 생각해봅시다. 가볍게 생각하면 인자로 노드의 주소를 가리키는 head변수를 입..

연결리스트 개념과 기본동작 리스트 컴퓨터 프로그램은 대부분 리스트 - 기본적인 연산 : 삽입(insert),삭제(remove),검색(search)등 - 리스트를 구현하는 대표적인 두 가지 방법 : 배열, 연결 리스트 배열은 랜덤엑세스가 가능한 자료구조다 랜덤엑세스 ? 배열은 각 칸의 타입이 같고 즉, 크기가 동일하다. 예를 들어 배열의 5번재 칸은 배열의 시작 주소 + 4*(1칸의 크기) n번째 칸에 대한 접근의 차이가 없다. > 랜덤엑세스 몇번째 칸이든 상관 없다. >> 배열의 장점 배열의 단점 - 크기가 고정 - reallocation이 필요 = 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 연결리스트 - 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며, - 길이의 제한..