이중연결리스트 가장 단순한 이중연결리스트는 다음과 같다. 모든 노드에 대해 진전 노드로 가는 연결을 충가한 것이 이중 연결이다. 이렇게 되면 정렬된 연결리스트의 삽입 삭제에 있어서 이전 노드로 되돌아가기가 쉬워진다. 위의 내용을 코드로 구현하자면 다음과 같다. 만약 연결 리스트에서 삽입 작업이 주로 리스트 끝에서 일어난다면 테일 포인터를 하나 더 두면 된다. 새로운 노드를 삽입하려면 현재의 테일이 가리키는 노드의 Next가 새 노드를 가리키게 한 후 원래 테일을 이동시켜 새 노드를 가리키게 한다. 이를 구현한 내용은 다음 링크를 통해 확인 한다. 2022.04.22 - [C++/자료구조] - 연결 리스트를 이용한 스택 구현 스택에서는 Tail이 Top이 된다.

2022.04.23 - [C++/자료구조] - 큐(Queue) 1. 배열을 이용한 큐의 구현 int[10]만큼의 공간이 있다고 하자. Enqueue(7) 위의 코드를 실행시키면 Rear++에 7이 들어간 것을 알 수 있다. Dequeue() 위의 코드를 실행시키면 Front에 1이 사라진 것을 알 수 있다. 만약 큐가 비었다면 Front와 Rear의 값을 -1로 초기화해준다. 다음은 위의 내용을 코드로 구현한 내용이다. #include using namespace std; #define DEFAULT_CAPACITY 10 //디폴트 capacity는 10으로 한다. class Queue { public: Queue(); //기본 생성자 Queue(int capacity); //객체의 capacity는 객..

2022.04.29 - [C++/자료구조] - 배열을 이용한 큐 구현 위의 글에서 원형큐를 참고한다. 큐가 가득 찬 경우 만약 다음과 같이 큐가 가득 찬 경우 capacity를 capacity*capacity만큼 늘린다. 다음은 이를 구현한 내용이다. 멤버 함수 생성자 : 기본 capacity는 10으로 한다. 소멸자 Enqueue(element) : element요소를 rear쪽에 넣는다. Dequeue() : element요소를 front쪽부터 삭제한다. IsFull() : 큐가 가득찼다면 true를 반환한다. Extend() : 큐를 확장한다. CopyArray(array, old_array) : array에 old_array를 복사한다. ArrayClear(array) : array를 0으로 초기..

아래의 코드는 정상적으로 작동된다. #include using namespace std; int main(void) { int *ptr = new int[3](); //힙 공간에 동적으로 int형 배열을 할당한다. for(int i = 0; i

2022.04.22 - [C++/자료구조] - 배열을 이용한 스택 구현 스터디에서 스택에서의 배열을 확장할 수 있다는 이야기를 듣게 되었다. 그를 구현해 보았다. 아래 코드의 멤버 함수와 멤버 변수는 다음과 같다. Stack Class의 멤버 함수 디폴트 생성자 : 기본 capacity는 10이고 top은 -1이다. 생성자(int capacity) : capacity의 값은 입력 받은 대로 설정하고, top은 -1이다. 소멸자 : 스택을 비우고 스택에 할당된 공간을 해제한다. Push(int element) : 스택에 요소를 push한다. 그 후 스택이 꽉찼다면 Extend()함수를 실행한다. Pop() : 스택의 요소를 pop한다. 만약 스택이 비어있다면 -1을 리턴한다. Top() : 스택의 top ..

아래 그림에서 원으로 표시한 것을 노드(Node)라고 한다. 직접 갈 수 있는 노드를 인접 노드(Adjacent Node)라고 한다. 예를 들어 A의 인접 노드는 G, B다. 그리고 각 노드를 잇는 선을 간선이라고 한다. A에서 I로 갈 수 있을까? 소모적 탐색 A에서 출발하여 갈 수 있는 모든 곳을 가 본 후, 가는 길이 없다면 길이 없다는 결론을 내리고, 만약 있다면 더 이상 다른 길을 찾지 말고, 길이 있다는 결론을 내린다. 소모적 탐색에는 깊이우선 탐색과 너비우선 탐색이 있다.