C/C++ : 강의 44화~46화 (Single Linked List)

날짜 : 190520

주제 : 싱글 링크드 리스트로 학생관리 프로그램 만들기

설명 : 노드를 구조체로 만들고 그 구조체 안에 다음 구조체의 주소를 저장할 변수를 선언한다. 그 후 노드와 노드를 연결하는 것이 링크드 리스트이다. 장점은 노드의 최대 개수 같은 것들이 정해져 있지 않아서 마음대로 노드를 추가/제거할 수 있다. 따라서 고정크기인 배열의 단점을 보완할 수 있다. 단점은 연속된 메모리 공간이 아니기 때문에 추가하고 지울 경우 '메모리 단편화'가 발생할 수 있다.

 

#include <iostream>

using namespace std;

#define NAME_SIZE 32



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

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


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

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

// 학생 정보 구조체
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;
}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 << 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;
	}
	else
	{
		list->end->nextNode = node;
	}

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

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 PrintList(const PLIST list)
{
	system("cls");
	cout << "========== 4. 학생 정보 출력 ==========" << endl;

	PNODE	node = list->begin;

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

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

	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;
	PNODE	prevNode = NULL;

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

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

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

			// 만약 이전 노드가 NULL이 아니라면 이전노드의 다음을 다음 노드와 연결
			else
			{
				cout << currNode->studentData.name << " 학생이 삭제되었습니다." << endl;
				delete currNode;
				prevNode->nextNode = nextNode;

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

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

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

	cout << "삭제할 학생을 찾을 수 없습니다." << endl;
	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;
		}
	}

	ClearList(&list);

	return 0;
}
/* 숙제 : 더블 링크드 리스트로 학생관리 프로그램 만들기 */