Language/C18 [자료구조] 스택(Stack) 1. 스택의 개념 스택(Stack)의 구조란 쌓인 접시에 가장 먼저 놓은 것은 제일 아래 있는 접시다. 그러나 사용하려고 접시를 집는다면 제일 위에 있는 접시부터 사용하게 된다. 이처럼 들어온 순서와 정반대로 서비스를 받는 것이 스택의 개념이다. 2. 스택의 특징 데이터의 삽입과 삭제가 한곳에서 이루어지는 방식(Last In First Out = LIFO) - Top : 가장 최근에 삽입된 자료 - Bottom : 스택의 밑바닥 - 삽입 : Push - 삭제 : Pop 다중 스택 - 하나의 기억공간에 여러 개의 스택으로 운영하는 형태로 overflow의 발생방지를 위해 사용 스택의 응용 - 서브루틴호출, 순환 프로그램, 인터럽트 처리, 수식표기, 0-주소, 컴파일러 등 3. 스택의 구조 3 C top 2.. 2020. 6. 22. [자료구조] 이중 연결 리스트(Doubly linked list) 1. 이중 연결 리스트 특징 양쪽 방향으로 순회할 수 있도록 노드를 연결한 리스트 2. 이중 연결 리스트 구조 두 개의 링크 필드와 한 개의 데이터 필드로 구성 llink(Left link) 필드 : 왼쪽 노드와 연결하는 포인터 rlink(Right link) 필드 : 오른쪽 노드와 연결하는 포인터 1) C언어 구조체 - C언어 구조체로 본 이중 연결 리스트의 기본구조 struct Dnode{ struct Dnode *llink; int data; struct Dnode *rlink; }; 2) 이중 연결리스트의 구조 head llink Data rlink llink Data rlink llink Data rlink → NULL 10 → ← 20 → ← 30 NULL node1 node2 node3 3).. 2020. 6. 22. [자료구조] 원형 연결 리스트(Circular linked list) 1. 원형 연결 리스트(Circular linked list) 단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트 단순 연결 리스트의 마지막 노드의 링크 필드에 첫 번째 노드의 주소를 저장하여 구성 링크를 따라 계속 순회하면서 이전 노드에 접근 가능 2. 원형 연결 리스트 구조 head Datd Link Datd Link Datd Link → 10 → 20 → 30 ↓ curr ↑ ← node1 node2 node3 원형 연결리스트 구조를 보게 되면 head와 curr은 첫 번째 노드를 가리킨다. 각 노드는 뒤에 있는 노드를 가리킨다. 단순 연결리스트에서 마지막 노드에는 NULL이 들어가지만, 원형 연결리스트에서 마지막 노드의 Link는 .. 2020. 6. 22. [자료구조] 연결리스트 PART.2 1. 연결리스트로 나타낸 구조에서 삭제하기(중간노드) 연결리스트 PART.1에서 삽입으로 실습했던 구조를 가지고 삭제 실습한다. Data Link Data Link Data Link Data Link Data Link -> 10 -> 20 -> 30 -> 40 NULL head node1 node2 node3 node4 이 구조에서 node3을 삭제한다. 1) 순서 삭제할 노드의 앞 노드(선행자)를 찾는다. 앞 노드의 링크 필드에 사제할 노드의 링크 필드 값을 저장한다. 2. C언어 실습 1) 노드 생성 위 구조의 노드를 생성한다. #include #include typedef struct NODE { int data; struct NODE *link; } NODE; int main() { NODE *h.. 2020. 6. 21. [자료구조] 연결리스트 PART.1 1. 연결 자료구조(Linked Data Structure) 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 각 원소에 저장된 다음 원소의 주소에 의해 순서가 연결되는 방식 물리적인 순서를 맞추기 위한 오버헤드가 발생하지 않음 여러 개의 작은 공간을 연결하여 하나의 전체 자료구조를 표현 크기 변경이 유연하고 더 효율적으로 메모리 사용 리스트를 연결 자료구조로 표현한 구조 연결하는 방식에 따라 단순 연결 리스트와 원형 연결 리스트, 이중 연결 리스트, 이중 원형 연결 리스트가 있음 2. 연결 리스트의 구성 1) 노드 연결 자료구조에서 하나의 원소를 표현하기 위한 단위 구조 (1) 노드의 구조 노드의 구조 데이터 필드 링크 필드 2) 데이터 필드(data field) 원소의 값을 저장 저장할 .. 2020. 6. 19. [자료구조] 선형리스트 1. 선형리스트의 개념 1) 리스트 자료의 목록 배열 2) 선형리스트 순서 리스트(Ordered List) 자료 간에 순서를 갖는 리스트 (1) 선형리스트 예 - 요일 일 월 화 수 목 금 토 - 요리 분야 (순서가 없지만, 선형리스트 일부분이다.) 한정식 중식 일식 분식 양식 3) 리스트의 표현 방식 리스트 이름 = (원소1, 원소2, 원소n) 선형 리스트에서 원소를 나열한 순서는 원소들의 순서가 됨 4) 선형 리스트의 저장 원소들의 논리적 순서와 같은 순서로 메모리에 저장 5) 선형 리스트에서의 원소 삽입 선형리스트 중간에 원소가 삽입되면 그 이후의 원소들은 한 자리씩 자리를 뒤로 이동하여 물리적 순서를 논리적 순서와 일치시킨다. (1) 원소 삽입 방법 원소를 삽입할 빈자리 만든다. - 삽입할 자리 .. 2020. 6. 19. [자료구조] 개념 PART.2 자료의 표현 - 포인터 자료 포인터(pointer)의 개념 - C언어에서 가장 큰 특징을 포인터라고 말하는 사람들이 많다. 그만큼 포인터는 C언어의 대표적인 특징이자 C언어를 강력하게 만드는 존재다. 포인터로 인해 메모리 접근이 가능하므로 저급 언어의 특징을 갖게 하는 존재이며 때로는 잘못된 포인터의 연결로 오류를 만드는 C언어의 최대 약점이 될 수도 있는 존재다. 그래서 자바에서는 포인터를 제외하고 포인터와 비슷한 참조형을 만들었다. - 일반적인 변수들은 각자 선언된 자료형의 상숫값을 그 변수의 기억되는 값으로 저장하게 되지만 포인터 또는 포인터 변수는 메모리의 주솟값을 가지는 변수를 말한다. 주 메모리는 주소라는 개념으로 프로그램에서 접근하게 되는데 이 주솟값을 포인터 변수가 가지게 되는 것이다. 포.. 2020. 6. 18. [자료구조] 개념 PART.1 자료구조의 개념 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법 신중히 선택한 자료구조는 더 효율적인 알고리즘을 사용할 수 있게 한다. 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 자료구조의 필요성 컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 해서 자료구조에 대한 개념과 활용 능력이 있어야 한다. 형태에 따른 자료구조의 분류 자료구조 단순구조 정수 실수 문자 문자열 선형구조 리스트 연결리스트 스택 큐 데큐 선형구조 - 연결리스트 단일 이중 원형 비선형구조 트리 그래프 비선형구조 -.. 2020. 6. 18. 이전 1 2 다음