- 일종의 리스트 - 단, 데이터의 삽입과 삭제가 한쪽 끝에서만 이루어짐 - 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이 필요 = 리스트의 중간에 원소를 삽입하거나 삭제할 경우 다수의 데이터를 옮겨야 연결리스트 - 다른 데이터의 이동없이 중간에 삽입이나 삭제가 가능하며, - 길이의 제한..

바로 전 전화번호부 알고리즘 version 4.0을 떠올려 봅시다. 위 그림과 같이 4개의 field를 가지는 struct person을 정의한 후 Person type의 directory 배열을 만들어 사용하였습니다. 이 배열의 각 칸이 구조체인 구조입니다. 예를 들어 특정 칸의 특정 멤버정보를 가져올려면 directory[2].number = ~ 이런식으로 표기 하였습니다. 하지만 일반적으로 c프로그래밍에서 이런식의 구조체 배열을 사용하는 것은 일반적인 스타일이 아닙니다. (효율적이지 않습니다.) 예를 들어 version 4.0의 status() 함수에서 print_person함수를 호출하는 과정을 위 그림에서 살펴봅시다. c언어에서 함수를 호출할때 값에 의한 호출 (call by value) 방식을..

동장방식 : 이름과 번호 뿐아니라 email과 소속그룹까지 추가해보자 >> 구조체 이용 , 만약 번호,email,group이 없다면 빈칸으로 둔다. 또한 이름이 하나 이상의 단어로 구성될 수 있으며 단어사이에 여러 개의 공백이 있을 경우 한칸의 공백으로 저장한다. 생각해야할 점 2가지 ! 1. 구조체를 어떻게 사용할 것인가 ? typedef struct person { char *name; char *number; char *email; char *group; } Person; Person directory[CAPACITY]; // Person type의 배열 directory를 선언. person struct를 Person으로 재선언. 2. 빈칸을 어떻게 처리 할 것인가? int compose_name..