Programming Study/자료구조 썸네일형 리스트형 리스트 - 이중 연결 리스트(Doubly Linked List)와 이중 연결 원형 리스트(Doubly Circular Linked List) 이중 연결 리스트 - 리스트의 각 노드가 전위 방향과 후위 방향에 대한 2개의 링크 필드 llink와 rlink로 연결된 리스트 장점 1. 리스트 검색 시 매번 첫 번째 노드로부터 검색을 시작할 필요가 없다. 2. 삽입 및 삭제 연산이나 기타 연산 등에서 선행 노드에 대한 추가적인 파라미터 전달이 필요 없게 된다. 이중 연결 리스트를 구조체로 정의 typedef struct node_type *node_ptr; typedef struct node_type { node_ptr llink; int data; node_ptr rlink; }; node_ptr list_ptr; 이중 연결 리스트의 첫 번째나 마지막 노드가 아닌 임의의 노드에 대해서 다음과 같은 관계가 성립. ptr = ptr->llink->rl.. 더보기 리스트 - 원형 연결 리스트(Circular Linked List) 단순 연결리스트의 노드 검색의 문제점을 해결하자! 원형 연결 리스트! 단순 연결 리스트는 항상 마지막 노드의 링크 필드가 NULL값을 갖는다. 이러한 리스트에서는 각 노드를 검색하기 위해서 항상 리스트의 첫 노드부터 검색이 수행되어야 하는 문제점이 있다. 이러한 문제점은 원형 연결 리스트에 의해 해결 될 수 있다. 원형연결리스트의 장점 - 어떠한 위치의 노드로부터도 리스트 전체 노드에 대한 검색이 가능하게 되는 것. 더보기 리스트 - 단순 연결 리스트(Simply Linked List) 단순 연결 리스트 - 하나의 링크 필드에 의해 각 노드들이 순차적으로 연결된 연결리스트 화살표로 표시된 각 노드의 링크 필드는 실제 다음 노드에 대한 메모리 주소 값을 갖는 포인터. 마지막 노드의 링크 필드는 더 이상의 연결된 노드가 없음을 의미하기 위해 NULL값으로. 첫번째 노드를 가리키는 포인터 변수인 list_ptr이 이 리스트에 대한 이름으로서 사용. 단순 연결 리스트의 생성 ① malloc()함수를 이용하여 하나의 노드에 대한 메모리를 할당한다. ② 리스트의 이름을 나타내는 포인터 변수가 생성된 노드를 가리키게 한다. ③ 생성된 노드의 링키 필드의 값을 NULL로 설정한다. ④ 생성된 노드의 데이터 필드를 해당 값으로 설정한다. 연결리스트에서의 노드 구조체 정의 typedef struct no.. 더보기 리스트(List) 배열을 사용한 리스트의 문제점 1. 고정된 크기에 따른 메모리 사용의 비효율성 2. 각 원소의 인접한 메모리 사용에 따른 삽입 및 삭제 연산의 비효율성 문제 3. 정해진 리스트의 크기를 동적으로 증가시킬 수 없다는 점 위에서 언급한 배열이 갖는 문제점들은 연결 리스트(Linked List)에 의해 해결 될 수 있다. 연결리스트에서 각 원소들은 배열에서와는 다르게 메모리 상에서 서로 인접해 있거나 일정한 거리만큼 떨어져 있을 필요가 없다. 또, 연결 리스트에서는 각 원소의 물리적 순서는 의미가 없다. 연결리스트에서 각원소는 반드시 값(Value, data)과 다음 원소에 해당하는 위치를 가리키는 링크(link)의 쌍으로 표현된다. 이렇게 하나의 원소를 표현하기 위한 단위를 노드(node)라고 한다. 노드는.. 더보기 큐(Queue) 큐의 정의 - 선형리스트에서 한쪽에서는 삽입연산이 반대쪽에서는 삭제 연산이 이루어지도록 한 것. - 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 성질을 갖는다. - rear : 큐에서 데이터의 삽입이 이루어지는 쪽, 가장 최근에 삽입된 데이터의 위치를 가리킴. - front : 큐에서 데이터의 삭제가 이루어지는 쪽, 가장 최근에 삭제된 데이터의 위치를 가리킴. 큐의 기본 연산 큐의 생성 #define QUEUE_SIZE 100 typedef struct { char *item1[20] int item2; ··············· }Element; Element queue[QUEUE_SIZE]; int rear = -1; // 최초 생선된 큐는 공백.. 더보기 스택(stack) 스택의 정의 - 선형 리스트에서 데이터의 삽입과 삭제를 한 방향에서 이루어지도록 한 것. 스택의 기본연산 스택의 생성 #define STACK_SIZE 100 typedef struct { char *item1[20] int item2; ······· }Element; Element stack[STACK_SIZE]; int top = -1 //스택을 공백 상태로 초기화시키기 위해서 top의 값을 -1로 설정 스택의 포화/공백 상태 검사 함수 bool IsFull(int top) { if(top >= STACK_SIZE-1) return true; //포화상태 else return false; } bool IsEmpty(int top) { if(top == 1) return true; //공백 스택 상태 .. 더보기 자료구조의 구분 더보기 이전 1 다음
