한다 공부

앞에서의 스택, 큐, 연결리스트는 선형 자료구조였다. 선형 자료구조란 자료들이 선형으로 나열되어있는 구조이다. 트리는 자료가 계층적인 구조로 이루어져있다. 예를 들면 가족의 가계도, 컴퓨터의 디렉토리 구조 등이 있다. 그래프와 트리의 차이점은, 사이클이 존재하면 그래프이고 사이클이 없고 상하관계가 존재하면 트리이다. -트리의 용어 루트 : 가장 높은 곳에 존재하는 노드 서브트리 : 루트가 아닌 나머지 노드들 간선 : 노드들을 연결하는 연결선 = edge 관계 : 부모, 자식, 형제, 조상, 자손 관계가 존재 (개념은 인간 관계랑 같음!) 단말노드 : 자식이 없는 노드 비단말노드 : 단말노드의 반대 차수 : 한 노드가 가지고 있는 자식 노드의 개수 레벨 : 트리의 각 층에 번호를 매긴 것 (루트는 레벨 1..

연결리스트로 큐와 스택을 구현해보자 [스택] 간단히 말하자면 연결리스트의 맨 앞에 삽입하고 맨 뒤만 삭제하면 된다. insert_first, delete_first !! 단순연결리스트에서도 구현했었다~ #include #include typedef int element; typedef struct StackNode { element data; struct StackNode* link; }StackNode; //top은 정수가 아니고 노드를 가리키는 포인터이다 typedef struct { StackNode* top; }LinkedStackType; void init(LinkedStackType* s) { s->top = NULL; } //insert_first! void push(LinkedStackTy..

[원형연결리스트] 단순연결리스트에 한계가 있음을 깨달았다 ... 원형연결리스트를 이용해 삽입 삭제를 더 편리하게 해보자! 단순연결리스트에서는 마지막 노드가 NULL을 가리켰지만 원형연결리스트에서는 마지막 노드가 첫 번째 노드를 가리킨다. 원형연결리스트를 이용하면 맨 뒤에 노드를 삽입하는 것이 용이해진다! 헤드 포인터가 마지막 노드를 가키리도록 구성하자. 헤드 포인터를 첫 번째 노드를 가키리도록 하면 마지막 노드를 접근하기 위해 모든 노드들을 다 거쳐가야하고, 비효율적으로 동작하기 때문에 헤드 포인터가 마지막 노드를 가리켜야한다 ㅠ ㅠ print_list(list) insert_first(list, data) insert_last(list, data) 를 이용해서 원형연결리스트를 구현해보자 #include..

연결리스트를 복습해보자 연결된 리스트 형태의 자료구조를 연결리스트라고 한다 (단순) 연결리스트는 자기 참조 구조체를 쓸 것이며, lisert 함수를 생성해 연결리스트에 데이터를 추가할 것이며 delete함수를 생성해 연결리스트의 데이터를 삭제할 것이다. print_list함수를 따로 생성해 연결리스트에 있는 데이터를 순서대로 출력하기도 할 것이다. . . 외에 여러 연산이 있지만 추후 필요하면 기술하기로 하겠다 배열과 연결리스트의 장/단점 으로는 무엇이 있을까? 배열은 구현이 간단하고 노드를 찾는 검색 속도가 빠르다. 인덱스를 이용해 해당 위치로 바로 이동할 수 있기 때문이다. 하지만 동적으로 크기를 변경하는게 힘들다. +배열의 경우 중간 데이터를 삭제할 때, 해당 데이터 뒤에 있는 데이터를 앞으로 한칸..

방가방가 안녕들 하신가요. 오늘은 큐에 대해 복습을 하려고 합니다. 큐란? 선입선출 (FIFO: first in first out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조를 의미한다. 쉽게 말하면 선착순이다. 추상 자료형의로 정의하면.. create(max_size) >> 최대 크기가 max_size인 비어있는 큐 생성 init(q) >> 큐 초기화 is_empty(q) >> 큐의 사이즈가 0이면 return true, 아니면 return false is_full(q) >> 큐의 사이즈가 max_size와 같으면 return true, 아니면 return false enqueue(q,e) >> is_full 검사를 하고 자리가 있다면 q의 끝에 e를 추가 dequeue(q) >> is_emp..

첫번째 공부할 자료구조는 스택! 스택이란? LIFO(Last in First out)으로, 데이터의 삽입과 삭제가 후입선출인 자료구조를 말한다. 가장 나중에 들어온 데이터가 가장 먼저 나가게 되고 가장 먼저 들어온 데이터는 가장 나중에 나가게 된다... 추상 자료형으로 정의하면 . . creat(size) >> 최대 크기가 size만큼인 비어있는 스택 생성 is_full(s) >> 스택의 원소수 == size면 true (stack is full), 아니면 false is_empty(s) >> 스택의 원소수 == 0 이면 true, 아니면 false push(s, item) >> is_full(s) 이 false면 맨 위 (top)에 item 추가 pop(s) >> is_empty(s) 가 flase면 ..