3-1 연결리스트를 통한 영단어 끝말잇기

이번 문제는

연결리스트(linked list)를 통한 영단어 끝말잇기를 구현하는 문제입니다.

 

list의 STL을 사용하고 싶지만, 2학년 1학기 과정에서는 STL을 사용을 못하게 했습니다...

 

그리고 이번 3차 과제부터는 메모리 누수가 날 경우에 감점까지 있다는 점을 유의해야 합니다.

 

다시 본론으로 돌아와서 영단어 끝말잇기를 구현해야 할 때 아래와 같이 주의해야 할 점이 있습니다.

Is it a word that has not been entered before?
전에 그 단어가 나온 적이 있었나?

Is the word that starts with the last letter of previous entered word (case insensitive)?
전에 통과한 단어의 끝으로 시작하나?

 문제 풀이 방법

1. 연결리스트 구현하기

 

먼저 문자열을 구조체 노드로 나타냈습니다.

struct Node
{
	char arr[100] = { 0, };
	Node* p_next;
};

이 노드의 다음 노드를 가리킬 구조체형 변수 p_next와 문자열을 담아둘 char형 변수를 선언했습니다.

이번에 구현할 연결리스트는 singly linked list로 단일 연결리스트입니다.

이 singly linked list는 쉽게 설명하자면 왼쪽에서부터 오른쪽으로밖에 가지 못하고, 왼쪽으로 가지 못하는 구조입니다.

이러한 연결 리스트를 class로 구현을 할 것인데, 크게 다섯가지 요소로 나눴습니다.

 

1. 단어 추가하기=> 연결리스트 노드 삽입

먼저 연결 리스트의 앞인 head와 뒤인 tail을 이용했습니다.

먼저 head가 NULL인 경우(아무 노드도 없는 경우(초기 과정)) head를 그 노드에 메모리 생성을 하고, tail이 head와 같게 했습니다.

mp_head = new Node;
mp_tail = mp_head;

그리고 비어있지 않은 경우에는 초기 과정에서 했던 tail의 next를 메모리 생성을 해주고, 기존에 tail은 tail의 next를 가리키게 했습니다.

mp_tail->p_next = new Node;
mp_tail = mp_tail->p_next;

이렇게 메모리 생성을 해주고 나서 입력받은 문자열을

strcpy_s(mp_tail->arr, a_arr);
mp_tail->p_next = NULL;

이런 식으로 노드에 넣어주었습니다.

2. Is it a word that has not been entered before? 전에 그 단어가 나온 적이 있었나? => 연결 리스트 탐색

이 과정은 연결 리스트의 구조를 알면 쉽게 구현할 수 있었습니다.

저는 어떤 식으로 구현을 했냐면, 연결 리스트에 head를 가리킬 노드를 하나 만든 후, 대소문자를 무시하고 입력받은 문자열과 같은지 탐색을 했습니다. 이때 탐색은 head를 가리키고 있는 노드가 NULL이 나올 때까지, 매번 다음 노드를 가리키면서 입력받은 문자열이 그 노드의 문자열과 같을 때까지, 탐색을 하게 했습니다.

		Node* p = mp_head;

		while (NULL != p)
		{
			
			if (_stricmp(p->arr, search) != 0)
			{
				p = p->p_next;
			
			}
			else
			{//±‚¡∏ø° πÆ¿⁄ø≠¿Ã ¿÷æ˙¥¯∞ÊøÏ
				cout << "Already Exists" << endl;
				while (NULL != p)
				{
					p = p->p_next;
				}
				return 1;
			}
		}

기존에 있었던 문자열 같은 경우 1을 반환하고 이미 존재한다! 를 출력해줍니다.

3. Is the word that starts with the last letter of previous entered word (case insensitive)?
전에 통과한 단어의 끝으로 시작하나? => 별도의 방법
이것을 해결하기 위해 저는 야매인 듯 아닌듯한 방법으로 진행했습니다.
전에 입력받은 문자열의 strlen()-1과 현재 입력받은 문자열의 첫 번째 알파벳을 비교(대소문자 생각)를 했습니다.

arr[0] == pre_arr[strlen(pre_arr) - 1] || arr[0] == pre_arr[strlen(pre_arr) - 1] - 32 || arr[0] == pre_arr[strlen(pre_arr) - 1] + 32 ||

arr이 현재 입력받은 문자열이고 pre_arr이 전에 입력받은 문자열입니다. 이런 식으로 진행하면 되겠죠?

 

4. 입력할 때마다 보이는 입력했던 단어들 => 연결 리스트 출력

이것도 연결리스트 탐색과 비슷합니다. head를 가리킬 노드형 변수를 선언하고, 그 변수를 매번 next를 가리키게 하면서 그 노드의 문자열을 출력하게 하는 구조입니다.

		Node* p = mp_head;

		while (NULL != p)
		{
			cout << p->arr << "-> ";
			p = p->p_next;
		}
		cout << endl;

위와 같은 구조를 가집니다.

5. "exit"을 입력받은 경우 => 소멸자에서 메모리 해제

메모리 해제인 경우 이거를 작성하는 때는 2학년이 끝났을 때인데, 이 코드를 작성했던 시간은 2학년 1학기여서 그런지 메모리 해제를 하는 부분은 smooth하지 못합니다.

이 당시 저는 지울 노드의 다음 노드를 가리키는 변수를 만들고 지울노드를 지우고 그 지운 노드가 다음노드를 가르키는 변수를 가리키게 하는 방식을 head가 NULL이 될 때까지 시도했던 것 같습니다.

		if (mp_head != NULL)
		{
			Node* p = mp_head, * p_save_next;

			while (NULL != p)
			{
				p_save_next = p->p_next;
				delete p;
				p = p_save_next;
			}
			mp_head = mp_tail = NULL;
		}

위 코드들을 종합하면

#define _CRTDBG_MAP_ALLOC
#include<iostream>
using namespace std;

struct Node
{
	char arr[100] = { 0, };
	Node* p_next;
};//≥ε ±∏¡∂√º

class NumList//numlist classº±æ
{
private:
	Node* mp_head, * mp_tail;

public:
	NumList()//ª˝º∫¿⁄
	{
		mp_head = mp_tail = NULL;
	}

	~NumList()//º“∏Í¿⁄
	{
		DeleteAllObject();
	}

	void Addstr(char* a_arr)
	{//≥εÂ√fl∞°«œ±‚
		if (NULL != mp_head)
		{
			mp_tail->p_next = new Node;
			mp_tail = mp_tail->p_next;
		}
		else
		{
			mp_head = new Node;
			mp_tail = mp_head;
		}
		strcpy_s(mp_tail->arr, a_arr);
		mp_tail->p_next = NULL;
	}


	void DisplaystrList()
	{//≥εÂ∫∏ø©¡÷±‚
		Node* p = mp_head;

		while (NULL != p)
		{
			cout << p->arr << "-> ";
			p = p->p_next;
		}
		cout << endl;
	}

	void DeleteAllObject()
	{//∏fi∏∏Æ«ÿ¡¶
		if (mp_head != NULL)
		{
			Node* p = mp_head, * p_save_next;

			while (NULL != p)
			{
				p_save_next = p->p_next;
				delete p;
				p = p_save_next;
			}
			mp_head = mp_tail = NULL;
		}
	}

	int SearchList(char* search)
	{//πÆ¿⁄ø≠¿Ã ±‚¡∏ø° ¿÷æ˙¥¬¡ˆ ≈Ωªˆ
		Node* p = mp_head;

		while (NULL != p)
		{
			
			if (_stricmp(p->arr, search) != 0)
			{
				p = p->p_next;
			
			}
			else
			{//±‚¡∏ø° πÆ¿⁄ø≠¿Ã ¿÷æ˙¥¯∞ÊøÏ
				cout << "Already Exists" << endl;
				while (NULL != p)
				{
					p = p->p_next;
				}
				return 1;
			}
		}
	}

	void CheckList(char* arr)
	{//exit¿ª πfi¿∏∏È ¡æ∑·
		if (_stricmp(arr, "exit") == 0) {
			DeleteAllObject();
			exit(0);
		}
	}
};

int main()
{
	NumList nums;
	char arr[100];
	char pre_arr[100] = { 0, };
	int count = 0;
	int result=0;
	for (int count = 0; ; count++)
	{
		cout << "CMD(Word/exit)>> ";
		cin >> arr;
		nums.CheckList(arr);
		result = nums.SearchList(arr);
			if (arr[0] == pre_arr[strlen(pre_arr) - 1] || arr[0] == pre_arr[strlen(pre_arr) - 1] - 32 || arr[0] == pre_arr[strlen(pre_arr) - 1] + 32 || count == 0)
			{
				if (result !=1)
				{
					nums.Addstr(arr);
					nums.DisplaystrList();
					strcpy_s(pre_arr, arr);
				}
				else if(result==1)
				{
					nums.DisplaystrList();
				}
			}
			
			else {
				cout << "Not Chained" << endl;
				nums.DisplaystrList();
			}
			
	}

	return 0;
}

가 되는데, 이 코드를 입력하고 실행하면 아래와 같은 결과화면이 나옵니다.

왼쪽 위 : 끝말로 이어지지 않는 경우, 오른쪽 위 : 잘 이어지는 경우, 왼쪽 아래 : 이미 존재하는 단어

메모리 해제가 잘 되었는지 찾아보려고 했지만 3차 과제의 7번에서 60% 이상의 copy률이 보여서 0점을 맞아 찾아볼 수가 없었습니다.(이것만 아니었다면,,,) ㅜㅜ

다행히 2학년 2학기 때 linux에서 c++을 돌리면서 valgrind로 메모리 누수를 잘 찾을 수 있었는데 valgrind를 쓰는 과정도 곧 포스팅하겠습니다.

 

#이 문제의 출처는 kw대학교 컴퓨터 정보공학부 2021년 1학기 객체지향 프로그래밍 과제 문제입니다.