C/C++ : 과제3 (Double Linked List)

날짜 : 190521

주제 : 더블 링크드 리스트 구현

설명 : 싱글과 다르게 더블은 노드 구조체 안에 앞에 있는 노드와 뒤에 있는 노드를 모두 저장하고 있다. 따라서 노드를 뒤에서부터 순회할 수 있다.

 

#include <iostream>

using namespace std;

#define NAME_SIZE 32

/* 링크드 리스트 : 자료구조의 한 종류. 자료구조란 데이터를 저장하는 방법
링크드 리스트는 데이터 목록을 연결시켜서 접근할 수 있는 구조를 제공

특징 : 선형구조... 즉 배열처럼 특정요소에 바로 접근 불가. 무조건 앞에서부터 차례대로 들어가야한다.
노드를 추가할때 노드를 생성하고 마지막 노드에 연결. 따라서 개수의 제한이 없음.


노드 : 데이터를 저장하기 위한 공간
노드의 특징 : 다음노드에 연결가능(주소를 저장)
*/

/*
정렬 기능 추가... 기준은 학번 또는 평균
*/

enum MAIN_MENU
{
	MM_NONE,
	MM_INSERT,
	MM_DELETE,
	MM_SEARCH,
	MM_PRINT,
	MM_SORT,
	MM_EXIT
};

enum PRINT_MENU
{
	PM_NONE,
	PM_FORWARDS,
	PM_BACKWARDS,
	PM_BACK
};

enum SORT_MENU
{
	SM_NONE,
	SM_NUMBER,
	SM_AVERAGE,
	SM_BACK
};

// 학생 정보 구조체
typedef struct _tagStudent
{
	char	name[NAME_SIZE];
	int		number;
	int		kor;
	int		eng;
	int		math;
	int		total;
	float	average;
}STUDENT, *PSTUDENT;

// 노드 구조체
typedef struct _tagNode
{
	STUDENT studentData;
	_tagNode* nextNode;
	_tagNode* prevNode;
}NODE, *PNODE;

// 리스트 구조체
typedef struct _tagList
{
	PNODE	begin;
	PNODE	end;
	int		currentSize;
	int		studentNumberStandard;
}LIST, *PLIST;

void InitList(PLIST list)
{
	// 포인터 초기화 방식
	list->begin = NULL;
	list->end = NULL;
	list->currentSize = 0;
}

int InputInt()
{
	int input;
	cin >> input;

	if (cin.fail())
	{
		cin.clear();
		cin.ignore(1024, '\n');
		return INT_MAX;
	}

	return input;
}

int PrintMenu()
{
	system("cls");
	cout << "1. 학생 추가" << endl;
	cout << "2. 학생 삭제" << endl;
	cout << "3. 학생 탐색" << endl;
	cout << "4. 학생 출력" << endl;
	cout << "5. 학생 정렬" << endl;
	cout << "6. 종료" << endl << endl;

	cout << "메뉴를 선택하세요 : " << endl;

	int input = InputInt();

	if (input <= MM_NONE || input > MM_EXIT)
	{
		return MM_NONE;
	}

	return input;
}

void InputString(char* string, int size)
{
	cin.clear();
	cin.ignore(1024, '\n');

	cin.getline(string, size - 1);
}

void Insert(PLIST list)
{
	system("cls");
	cout << "========== 1. 학생 추가 ==========" << endl;

	STUDENT student = {};

	cout << "이름 : ";
	InputString(student.name, NAME_SIZE);

	cout << "국어 점수 : ";
	student.kor = InputInt();

	cout << "영어 점수 : ";
	student.eng = InputInt();

	cout << "수학 점수 : ";
	student.math = InputInt();

	student.total = student.kor + student.eng + student.math;
	student.average = student.total / 3.f;

	++list->studentNumberStandard;
	++list->currentSize;
	student.number = list->studentNumberStandard;


	// 추가할 리스트 노드를 생성
	PNODE	node = new NODE;

	// 마지막에 추가되는 노드이기 때문에 그 뒤에 노드는 없음
	node->nextNode = NULL;

	// 입력받은 데이터를 노드에 저장
	node->studentData = student;

	// 헤드노드가 비어있으면 새로 생성된 노드가 헤드노드
	if (list->begin == NULL)
	{
		list->begin = node;
		node->prevNode = NULL;
	}
	else
	{
		node->prevNode = list->end;
		list->end->nextNode = node;
	}

	// 새로 생성된 노드가 마지막 노드
	list->end = node;
}

//void InsertFront(PLIST list)


void ClearList(PLIST list)
{
	PNODE	node = list->begin;

	while (node != NULL)
	{
		// 다음 노드 저장
		PNODE	next = node->nextNode;

		// 현재 노드 삭제
		delete node;

		// 이제 다음 노드로
		node = next;
	}

	// 마지막으로 모두 초기화
	list->begin = NULL;
	list->end = NULL;
	list->currentSize = 0;
}

const void PrintStudentData(const PSTUDENT student)
{
	cout << "이름 : " << student->name << "\t학번 : " << student->number << endl;
	cout << "국어 점수 : " << student->kor << "\t영어 점수 : " << student->eng << endl;
	cout << "수학 점수 : " << student->math << endl;
	cout << "총 점 : " << student->total << "\t평 균 : " << student->average << endl << endl;
}

const void PrintListBackwards(const PLIST list)
{
	PNODE	node = list->end;

	while (node != NULL)
	{
		PrintStudentData(&node->studentData);
		node = node->prevNode;
	}

	cout << "총 학생 수 : " << list->currentSize << endl;
}

const void PrintListForwards(const PLIST list)
{
	PNODE	node = list->begin;

	while (node != NULL)
	{
		PrintStudentData(&node->studentData);
		node = node->nextNode;
	}

	cout << "총 학생 수 : " << list->currentSize << endl;
}

const void PrintList(const PLIST list)
{
	while (true)
	{
		system("cls");
		cout << "========== 4. 학생 정보 출력 ==========" << endl;
		cout << "1. 정방향 출력" << endl;
		cout << "2. 역방향 출력" << endl;
		cout << "3. 뒤로 가기" << endl;
		int menu = InputInt();

		switch (menu)
		{
		case PM_FORWARDS:
			PrintListForwards(list);
			break;
		case PM_BACKWARDS:
			PrintListBackwards(list);
			break;
		case PM_BACK:
			return;
			break;
		}

		system("pause");
	}
	
}

void SearchByName(PLIST list)
{
	cout << "탐색할 이름을 입력하세요 : ";
	char searchName[NAME_SIZE] = {};
	InputString(searchName, NAME_SIZE);

	PNODE	node = list->begin;

	while (node != NULL)
	{
		if (strcmp(node->studentData.name, searchName) == 0)
		{
			PrintStudentData(&node->studentData);
			system("pause");

			return;
		}

		node = node->nextNode;
	}

	cout << "ERROR : 일치하는 학생을 찾지 못했습니다." << endl;
	system("pause");
}

void SearchByNumber(PLIST list)
{
	cout << "탐색할 학번을 입력하세요 : ";
	int		searchNumber;
	searchNumber = InputInt();

	PNODE	node = list->begin;

	while (node != NULL)
	{
		if (node->studentData.number == searchNumber)
		{
			PrintStudentData(&node->studentData);
			system("pause");

			return;
		}

		node = node->nextNode;
	}

	cout << "ERROR : 일치하는 학생을 찾지 못했습니다." << endl;
	system("pause");
}

void Search(PLIST list)
{
	while (true)
	{
		system("cls");
		cout << "========== 3. 학생 탐색 ==========" << endl;

		cout << "1. 이름 검색" << endl;
		cout << "2. 학번 검색" << endl;
		cout << "3. 뒤로가기" << endl << endl;

		cout << "메뉴를 선택하세요 : ";

		int menu = InputInt();

		switch (menu)
		{
		case 1:
			SearchByName(list);
			break;
		case 2:
			SearchByNumber(list);
			break;
		case 3:
			break;
		}

		break;
	}
}

void Delete(PLIST list)
{
	system("cls");
	cout << "========== 4. 학생 삭제 ==========" << endl;

	cout << "삭제할 이름을 입력하세요 : ";
	char searchName[NAME_SIZE] = {};
	InputString(searchName, NAME_SIZE);

	PNODE	currNode = list->begin;

	while (currNode != NULL)
	{
		if (strcmp(currNode->studentData.name, searchName) == 0)
		{
			cout << currNode->studentData.name << " 학생이 삭제되었습니다." << endl;
			PNODE	nextNode = currNode->nextNode;
			PNODE	prevNode = currNode->prevNode;

			// 만약 이전 노드가 NULL이라면
			// 즉 시작 노드라면
			if (prevNode == NULL)
			{
				delete currNode;
				list->begin = nextNode;

				// 다음 노드가 헤드 노드가 된다.
				nextNode->prevNode = NULL;

				if (nextNode == NULL)
				{
					list->end = NULL;
				}
			}

			// 만약 이전 노드가 NULL이 아니라면 이전노드의 다음을 다음 노드와 연결
			else
			{
				delete currNode;
				
				// 다음 노드가 존재한다면
				if (nextNode != NULL)
				{
					nextNode->prevNode = prevNode;
					prevNode->nextNode = nextNode;
				}
				else
				{
					list->end = prevNode;
					prevNode->nextNode = NULL;
				}
			}

			--list->currentSize;
			system("pause");
			return;
		}

		// 해당 학생이 아니라면 현재 노드가 이전 노드가 된다.
		currNode = currNode->nextNode;
	}

	cout << "삭제할 학생을 찾을 수 없습니다." << endl;
	system("pause");
}

void Sort(PLIST list)
{
	system("cls");
	cout << "========== 5. 정렬하기 ==========" << endl;
	cout << "1. 학점 기준" << endl;
	cout << "2. 평균 기준" << endl;
	cout << "메뉴를 선택하세요. ";

	int menu = InputInt();

	if (menu <= SM_NONE || menu > SM_AVERAGE)
	{
		cout << "잘못 선택하였습니다." << endl;
		system("pause");
		return;
	}

	
	int i = 0;

	while (i <= list->currentSize)
	{
		PNODE	firstNode = list->begin;
		PNODE	secondNode = firstNode->nextNode;
		while (secondNode != NULL)
		{
			bool	swap = false;

			switch (menu)
			{
			case SM_NUMBER:
				if ((firstNode->studentData.number) > (secondNode->studentData.number))
				{
					swap = true;
				}

				break;
			case SM_AVERAGE:
				if ((firstNode->studentData.average) > (secondNode->studentData.average))
				{
					swap = true;
				}
				break;
			}

			if (swap == true)
			{
				PNODE	firstPrev = firstNode->prevNode;
				PNODE	firstNext = firstNode->nextNode;

				PNODE	secondPrev = secondNode->prevNode;
				PNODE	secondNext = secondNode->nextNode;


				// begin 설정
				if (firstNode == list->begin)
				{
					list->begin = secondNode;
				}

				PNODE	tempNode = firstNode;
				firstNode = secondNode;
				secondNode = tempNode;

				// 앞앞 노드
				if(firstPrev != NULL)
				{
					firstPrev->nextNode = firstNode;
				}

				// 뒤뒤 노드
				if (secondNext != NULL)
				{
					secondNext->prevNode = secondNode;
				}

				// 2번째 노드
				secondNode->nextNode = secondNext;
				secondNode->prevNode = firstNode;			

				// 1번째 노드
				firstNode->prevNode = firstPrev;
				firstNode->nextNode = secondNode;

				// end 설정
				if (firstNext == list->end)
				{
					list->end = secondNode;
				}

				firstNode = secondNode;
				secondNode = firstNode->nextNode;
			}
			else
			{
				firstNode = secondNode;
				secondNode = firstNode->nextNode;
			}
		}
		++i;
	}
	cout << "========= 정렬 되었습니다. =========" << endl;
	PrintListForwards(list);

	system("pause");
}

int main()
{
	LIST	list = {};

	InitList(&list);

	while (true)
	{
		int menu = PrintMenu();

		if (menu == MM_EXIT)
		{
			break;
		}

		switch (menu)
		{
		case MM_INSERT:
			Insert(&list);
			break;
		case MM_DELETE:
			Delete(&list);
			break;
		case MM_SEARCH:
			Search(&list);
			break;
		case MM_PRINT:
			PrintList(&list);
			break;
		case MM_SORT:
			Sort(&list);
			break;
		case MM_EXIT:
			break;
		}
	}

	ClearList(&list);

	return 0;
}