[자료구조] 이중 연결 리스트(Doubly Linked List)를 이용한 학생 성적 관리 프로그램 - 이중 연결리스트 초기화, 출력, 검색, 정렬, 메모리 해제

 

 

data.txt

2 이대호 80 75 90 75
1 박찬호 80 100 75 60
3 박세리 100 50 100 45

 

 

소스코드 :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 학생의 데이터를 담는 구조체를 새로운 타입 element로 정의
typedef struct student {
	int num;
	char name[20]; // 이름은 4글자까지 가능
	int kor, math, eng, com;
}element;

// 이중 연결리스트의 자기참조구조체 구현
typedef struct DListNode {
	struct DListNode* llink;
	element data;
	struct DListNode* rlink;
}DListNode;

// 함수 원형
void init(DListNode* phead); // 처음에 노드를 초기화
DListNode* dinsert_node(DListNode* before, DListNode* new_node); // 새로운 노드를 before 노드 다음에 삽입
void search(DListNode* head, element data); // 학생 번호에 입력 받아 노드 탐색 후 출력
void sort_dinsert(DListNode* head); // 이중 연결리스트를 정렬
void display(DListNode* phead);// 연결 리스트 전체 출력
void free_node(DListNode* phead); // 동적 할당된 메모리 반환

int main() {
	FILE* fp;
	DListNode* head = (DListNode*)malloc(sizeof(DListNode)); // 헤드 노드 생성(데이터 필드는 empty)
	DListNode* tmp; // 임시로 데이터를 입력받는 노드
	element dat; // 데이터 임시로 입력 받는 구조체
	int flag; // 입력받는 메뉴

	// 연결 리스트 초기화
	init(head);

	// 파일 열기
	fp = fopen("data.txt", "rt");
	if (fp == NULL) {
		printf("File not found\n");
		return 0;
	}

	// 파일로부터 데이터 입력 받아 tmp 노드에 저장후 노드 삽입
	while (!feof(fp)) {
		fscanf(fp, "%d %s %d %d %d %d",
			&dat.num, dat.name, &dat.kor, &dat.math, &dat.eng, &dat.com);
		printf("%6d %10s %6d %6d %6d %6d\n",
			dat.num, dat.name, dat.kor, dat.math, dat.eng, dat.com);
		tmp = (DListNode*)malloc(sizeof(DListNode)); // create_node 함수 구현 대신 파일 내에서 생성
		tmp->data = dat;

		dinsert_node(head, tmp); // head에 새로 만든 tmp를 insert
	}

	// 메뉴 선택하여 조건에 맞게 함수 호출 
	while (1) {
		printf("\n종료(0) 학생 데이터 입력(1) 학생 검색(2) 목록 보기(3)\n");
		printf("메뉴 입력 : ");
		scanf("%d", &flag);

		switch (flag)
		{
		case 0: // 0인 경우 종료
			exit(1);
			break;

		case 1: // 데이터 입력 받아 새로운 노드 추가 후 삽입
			tmp = (DListNode*)malloc(sizeof(DListNode));

			printf("추가할 학생 번호: "); scanf("%d", &dat.num);
			printf("이름 : "); scanf("%s", dat.name);
			printf("국어 : "); scanf("%d", &dat.kor);
			printf("수학 : "); scanf("%d", &dat.math);
			printf("영어 : "); scanf("%d", &dat.eng);
			printf("컴퓨터 : "); scanf("%d", &dat.com);

			tmp->data = dat; // 새로운 노드의 데이터 필드에 입력 받은 dat구조체를 대입
			dinsert_node(head, tmp); // 노드 맨 앞에 삽입
			break;

		case 2: // 학생 번호 입력 받아 리스트에서 탐색 후 출력
			printf("검색할 학생 번호 : ");
			scanf("%d", &dat.num);
			search(head, dat); // 학생 번호 찾아 출력
			break;

		case 3: // 리스트를 정렬하여 출력
			printf("\n<정렬된 목록 보기>\n\n");
			sort_dinsert(head); // 목록을 학생 번호 순대로 정렬
			display(head); // 출력
			break;

		default:break;
		}

	}
	free_node(head);
	fclose(fp);
}

void init(DListNode* phead) {
	//printf("[Init Doubly List]\n");
	phead->llink = phead;
	phead->rlink = phead;
}

DListNode* dinsert_node(DListNode* before, DListNode* new_node) {
	//before -> aaa     => before -> new_node -> aaa

	// new_node의 링크 필드 먼저 생성
	new_node->llink = before;
	new_node->rlink = before->rlink;

	before->rlink->llink = new_node; // aaa의 llink에는 new_node 주소를 저장
	before->rlink = new_node; // before의 rlink에는 new_node 주소를 저장

	//printf("\n\n new_node 성공적\n\n");
}

void search(DListNode* head, element data) {
	DListNode* p;

	for (p = head->rlink;p != head;p = p->rlink) {
		if (p->data.num == data.num) {
			printf("%6d %10s %6d %6d %6d %6d\n",
				p->data.num, p->data.name, p->data.kor, p->data.math, p->data.eng, p->data.com);
			return;
		}
	}
	printf("%d 번 학생의 번호 검색 실패\n\n", data.num);
}

void sort_dinsert(DListNode* head) {
	DListNode* p, * q;
	element tmp;

	// 오른쪽으로 이동하여 작은 값 찾으며 정렬
	for (p = head->rlink;p->rlink != head;p = p->rlink) {
		for (q = p->rlink;q != head;q = q->rlink) {
			if (q->data.num < p->data.num) // q의 total이 p의 total보다 크면
			{
				// q와 p의 swap
				tmp = p->data;
				p->data = q->data; // q와 p의 자리 바꿔줌
				q->data = tmp;
			}
		}
	}
}

void display(DListNode* phead) {
	printf("=====================================================\n");
	printf("|번 호|  이 름  |  언어  |  수리  |  영어  | 컴퓨터 |\n");
	printf("=====================================================\n");

	for (DListNode* p = phead->rlink;p != phead;p = p->rlink) {
		printf("|%3d  |  %5s |  %4d  |  %4d  | %4d  | %5d   |\n",
			p->data.num, p->data.name, p->data.kor, p->data.math, p->data.eng, p->data.com);
	}
	printf("=====================================================\n");
}

void free_node(DListNode* phead) {
	DListNode* p = phead->rlink, * next;
	while (p != phead) {
		next = p;
		free(p);
		p = p->rlink;
	}
}

 

 

결과:

 

 

 

 

 

 

// 학생의 데이터를 담는 구조체를 새로운 타입 element로 정의
typedef struct student {
	int num;
	char name[20]; // 이름은 4글자까지 가능
	int kor, math, eng, com;
}element;

// 이중 연결리스트의 자기참조구조체 구현
typedef struct DListNode {
	struct DListNode* llink;
	element data;
	struct DListNode* rlink;
}DListNode;

 

리스트, 데이터 구조체 구현

이중 연결리스트 DListNode는 양쪽으로 링크 필드가 존재한다.

왼쪽, 오른쪽 각각의 노드를 가리키는 llink, rlink 구조체 포인터 그리고 데이터 필드에 저장될 data를 멤버 변수를 포함한다.

element 구조체는 학생의 정보들을 담는 구조체이다.

 

 

	while (!feof(fp)) {
		fscanf(fp, "%d %s %d %d %d %d",
			&dat.num, dat.name, &dat.kor, &dat.math, &dat.eng, &dat.com);
		printf("%6d %10s %6d %6d %6d %6d\n",
			dat.num, dat.name, dat.kor, dat.math, dat.eng, dat.com);
		tmp = (DListNode*)malloc(sizeof(DListNode)); // create_node 함수 구현 대신 파일 내에서 생성
		tmp->data = dat;

		dinsert_node(head, tmp); // head에 새로 만든 tmp를 insert
	}

 

파일로부터 데이터 입력 받아 연결 리스트에 삽입

 

선언된 dat 구조체의 멤버 변수에 각각 파일로부터 입력 받는 데이터를 저장한다.

한 묶음의 데이터들이 입력되고 난 뒤, tmp 구조체 포인터에 DlistNode 의 크기만큼 동적 메모리를 할당하여 이중 연결리스트의 노드를 생성하여 대입한다.

데이터들을 임시로 저장해놓은 dat를 tmp의 데이터 필드에 그대로 대입한다. (구조체는 대입이 가능하기 때문)

헤드 포인터와 tmp 포인터를 인자로 전달하여 dinsert_node 함수를 호출하고 tmp를 리스트에 삽입한다.

 

 

	// 메뉴 선택하여 조건에 맞게 함수 호출 
	while (1) {
		printf("\n종료(0) 학생 데이터 입력(1) 학생 검색(2) 목록 보기(3)\n");
		printf("메뉴 입력 : ");
		scanf("%d", &flag);

		switch (flag)
		{
		case 0: // 0인 경우 종료
			exit(1);
			break;

		case 1: // 데이터 입력 받아 새로운 노드 추가 후 삽입
			tmp = (DListNode*)malloc(sizeof(DListNode));

			printf("추가할 학생 번호: "); scanf("%d", &dat.num);
			printf("이름 : "); scanf("%s", dat.name);
			printf("국어 : "); scanf("%d", &dat.kor);
			printf("수학 : "); scanf("%d", &dat.math);
			printf("영어 : "); scanf("%d", &dat.eng);
			printf("컴퓨터 : "); scanf("%d", &dat.com);

			tmp->data = dat; // 새로운 노드의 데이터 필드에 입력 받은 dat구조체를 대입
			dinsert_node(head, tmp); // 노드 맨 앞에 삽입
			break;

		case 2: // 학생 번호 입력 받아 리스트에서 탐색 후 출력
			printf("검색할 학생 번호 : ");
			scanf("%d", &dat.num);
			search(head, dat); // 학생 번호 찾아 출력
			break;

		case 3: // 리스트를 정렬하여 출력
			printf("\n<정렬된 목록 보기>\n\n");
			sort_dinsert(head); // 목록을 학생 번호 순대로 정렬
			display(head); // 출력
			break;

		default:break;
		}

 

main 함수의 함수 호출 부분

 

사용자에게 입력 받는 정수에 따라 조건에 맞게 각 함수가 실행된다.

1: 학생 데이터 입력 - 사용자에게 데이터를 입력 받아 생성된 노드를 삽입

2: 학생 검색 - 입력 받는 학생 번호로 리스트에서 탐색하여 있는 경우 학생 정보를 출력 => '문자열' 탐색으로 구현해보기

3: 목록 보기 - 정렬되지 않은 리스트를 학생 번호에 맞게 정렬하여 출력

 

 

void init(DListNode* phead) {
	//printf("[Init Doubly List]\n");
	phead->llink = phead;
	phead->rlink = phead;
}

 

1. void init(DListNode* phead);

리스트를 생성하여 초기화하는 함수이다.

 

처음에 phead 헤드포인터를 생성하고 난 후에, 양쪽의 링크 필드에는 자기 자신을 가리키도록

phead 포인터값을 그대로 대입하도록 한다.

 

 

DListNode* dinsert_node(DListNode* before, DListNode* new_node) {
	//before -> aaa     => before -> new_node -> aaa

	// new_node의 링크 필드 먼저 생성
	new_node->llink = before;
	new_node->rlink = before->rlink;

	before->rlink->llink = new_node; // aaa의 llink에는 new_node 주소를 저장
	before->rlink = new_node; // before의 rlink에는 new_node 주소를 저장

	//printf("\n\n new_node 성공적\n\n");
}

 

2. DListNode* dinsert_node(DlistNode* before, DListNode* new_node);

새로 생성된 new_node를 리스트에 삽입하는 함수이다.

 

새로운 노드를 삽입하기 위해서는 추가하고자 하는 위치를 알아야 한다.

추가하고자 하는 위치의 이전 노드와 생성될 노드를 매개 변수로 전달받는다.

 

가장 먼저 데이터 필드가 채워져 있는 new_node에 대하여 노드의 양쪽의 링크 필드를 먼저 초기화 해준다.

llink에는 이전 노드의 주소인 before의 값이, rlink에는 before이 기존에 가리키던 오른쪽 노드의 주솟값을 대입한다.

 

다음은 before의 링크 필드를 변경하는 작업이다.

before이 기존에 가리키던 오른쪽 노드의 왼쪽 노드의 주소인 rlink->llink에 new_node를 대입한다.

rrlink에는 new_node를 대입한다.

 

 

 

void search(DListNode* head, element data) {
	DListNode* p;

	for (p = head->rlink;p != head;p = p->rlink) {
		if (p->data.num == data.num) {
			printf("%6d %10s %6d %6d %6d %6d\n",
				p->data.num, p->data.name, p->data.kor,
             				   p->data.math, p->data.eng, p->data.com);
			return;
		}
	}
	printf("%d 번 학생의 번호 검색 실패\n\n", data.num);
}

 

3. void search(DListNode* head, element data);

검색하고자 하는 data를 리스트에서 탐색하여, 발견되면 해당 노드에 저장된 값을 출력하는 함수이다.

 

main 함수에서 사용자로부터 입력 받은 int형 변수를 포함하는 data구조체를 두번째 매개 변수로, 리스트의 주소를 첫번째 매개변수로 전달 받게 된다. -> data에서 char 문자 배열 멤버를 입력 받기

각 노드에 접근하며, 데이터 구조체의 num 멤버 변수의 값이 입력받은 값과 동일하다면 해당 노드의 데이터 필드의 데이터를 모두 출력하도록 한다.

 

 

 

void sort_dinsert(DListNode* head) {
	DListNode* p, * q;
	element tmp;

	// 버블 정렬
	for (p = head->rlink;p->rlink != head;p = p->rlink) {
		for (q = p->rlink;q != head;q = q->rlink) {
			if (q->data.num < p->data.num) // q의 total이 p의 total보다 크면
			{
				// q와 p의 swap
				tmp = p->data;
				p->data = q->data; 
				q->data = tmp;
			}
		}
	}
}

 

3. void sort_dinsert(DListNode* head);

리스트를 학생 번호에 따라 오름차순으로 정렬하는 함수이다.

 

버블 정렬 알고리즘으로 구현되었다.

 

 

void display(DListNode* phead) {
	printf("=====================================================\n");
	printf("|번 호|  이 름  |  언어  |  수리  |  영어  | 컴퓨터 |\n");
	printf("=====================================================\n");

	for (DListNode* p = phead->rlink;p != phead;p = p->rlink) {
		printf("|%3d  |  %5s |  %4d  |  %4d  | %4d  | %5d   |\n",
			p->data.num, p->data.name, p->data.kor, p->data.math,
            		p->data.eng, p->data.com);
	}
	printf("=====================================================\n");
}

 

4. void display(DListNode* phead);

출력 함수

 

void free_node(DListNode* phead) {
	DListNode* p = phead->rlink, * next;
	while (p != phead) {
		next = p;
		free(p);
		p = p->rlink;
	}
}

 

5. void free_node(DListNode* phead);

각 노드에 접근하며 동적 할당한 메모리를 해제하는 함수