-
2017.05.11
[C] 스택(Stack)
스택(Stack) - 제일 먼저 입력된 데이터가 맨 아래에 쌓이고 가장 최근에 입력된 데이터가 가장 위에 쌓이는 구조. (후입 선출(LIFO: Last-In-First-Out) - 스택에서 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고, 반대쪽인 바닥 부분을 스택 하단(stack bottom)이라고 함. - 스택에 저장되는 것을 요소(element)라고 함. - 스택에 요소가 하나도 없을 때 스택을 공백 스택(empty stack)이라고 함. - 삽입 연산을 push 연산이라고 하고, 삭제 연산은 pop 연산이라고 함. - is_empty 연산과 is_full 연산은 스택이 공백 상태에 있는지와 포화 상태에 있는지를 검사함. - create 연산은 스택을 생성함. - peek 연산은 ..
-
2017.05.06
[C] 이중 연결 리스트(Doubly Linked List)
이중 연결 리스트(Doubly Linked List) - 응용 프로그램에서의 특정 노드에서 양방향으로 자유롭게 움직일 수 있는 리스트 구조. - 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트. - 링크가 양방향이므로 양방향으로 검색이 가능해짐. - 공간을 많이 차지하고 코드가 복잡해진다는 단점이 있음. - 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용됨. - 헤드 노드(head node)라는 특별한 노드를 추가하는 경우가 많음. - 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 의미함. cf) 헤드 포인터 : 리스트의 첫 번째 노드를 가리키는 포인터 - 헤드 노드가 존재하면 삽입, 삭제 알고리즘이 간편해짐. - 이중 연결 리스트에서의 ..
-
2017.05.02
[C] 원형 연결 리스트(Circular Linked List)
원형 연결 리스트(Circular Linked List) - 리스트의 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트. -> 마지막 노드의 링크 필드가 NULL이 아닌 첫 번째 노드 주소가 되는 리스트. - 한 노드에서 다른 모든 노드로의 접근이 가능하다는 장점이 있음. - 노드이 삽입과 삭제가 단순 연결 리스트보다는 용이해짐. - 삭제나 삽입 시에는 항상 선행 노드의 포인터가 필요함. - 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적일 수 있음. 코드 // 원형 연결 리스트 (Circular Linked List) #include #include typedef int element; typedef struct ListNode { element data; struct ListNo..
-
2017.04.17
[C] 단순 연결 리스트(Singly Linked List)
단순 연결 리스트(Singly Linked List) - 단순 연결 리스트는 노드들이 하나의 링크 필드를 가지며 이 링크 필드를 이용하여 모든 노드들이 연결되어 있음. - 마지막 노드의 링크 필드 값은 NULL. - 첫 번째 노드를 가리키는 포인터(헤드 포인터) 값만 알고 있으면 연결 리스트 안의 모든 노드에 접근이 가능함. -> 하나의 단순 연결 리스트는 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분함. - 헤드 포인터(head pointer) : 첫 번째 노드를 가리키는 포인터 코드 #include typedef int element; typedef struct ListNode { element data; struct ListNode *link; } ListNode; void error(cha..
