[자료구조] 연결 리스트 - 동적 할당, 파일 입출력, 메타 구조체(metastructure), 노드 생성, 추가, 삽입, 삭제, 정렬, 탐색, 최대 최소

 

 

 

 

내가 작성한 코드:

(짝수번째 인덱스의 데이터 삭제 구현 실패)

 

 

// data.txt 파일에 있는 숫자들을 읽어 연결리스트에 저장하고 출력, 탐색, 최대 최소 출력

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

typedef int element;
typedef struct nArr {
	element data;
	struct nArr* link;
}nArr;

int main() {
	FILE* fp;
	nArr* list = NULL, * p, * prev=NULL, * next, *tmp=NULL;
	int getNum;
	int isEven = 0;
	element max, min;

	// 파일 열어 데이터 개수 저장
	// 파일을 열어 파일의 끝이 아닐 때까지 계속 새로운 노드 생성하여 리스트에 삽입
	fp = fopen("data.txt", "rt");
	if (fp == NULL) {
		printf("File not found\n");
		return 0;
	}
	while (!feof(fp)) {
		p = (nArr*)malloc(sizeof(nArr));
		fscanf(fp, "%d", &p->data);
		if (list == NULL) {
			p->link = NULL;
			list = p;
		}
		else {
			p->link = NULL;
			prev->link = p;
		}
		prev = p;
		p = p->link;
	}

	// 연결 리스트 출력
	p = list;
	printf(" < ");
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->link;
	}
	printf(" > \n\n");

	// 사용자로부터 입력 받은 숫자가 리스트에 몇 개 있는지 출력
	while (1) {
		printf("값을 입력하세요<0:종료> : ");
		scanf("%d", &getNum);
		if (getNum == 0)break;

		int nCount = 0;
		p = list;
		while (p != NULL) {
			if (p->data == getNum) nCount++;
			p = p->link;
		}
		printf("%d는 리스트에 %d개 있습니다.\n\n", getNum, nCount);
	}
	
	// 최대값과 최소값 찾기
	p = list;
	max = p->data, min = p->data;
	while (p != NULL) {
		if (p->data > max) max = p->data;
		if (p->data < min)min = p->data;
		p = p->link;
	}
	printf("최대값은 %d\n최소값은 %d\n\n", max, min);

	// 연결리스트 해제
	p = list;
	while (p != NULL) {
		next = p;
		free(p);
		p = p->link;
	}

	fclose(fp);
	return 0;
}

 

 

 

 

 

 

 

 

 

---

 

 

정답 코드:

(입력값 탐색, 최대 최소 출력, 짝수번째 인덱스 노드 삭제 구현 전)

 

// data.txt 파일에 있는 숫자들을 읽어 연결리스트에 저장하고 출력, 탐색, 최대 최소 출력

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

#define TRUE 1
#define FALSE 0

typedef int element; // 실제 데이터
typedef struct ListNode // 각 노드의 구조
{
	element data;
	struct ListNode* link;
}ListNode;

typedef struct // 메타 구조체(ListNode의 속성에 대한 구조체)
{
	ListNode* head; // 연결리스트의 헤드포인터
	int length; // 리스트 노드의 개수
}ListType;


void init(ListType* list);
int get_length(ListType* list);
ListNode* get_node_at(ListType* list, int pos);
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node);
void add(ListType* list, int position, element data);
void add_first(ListType* list, element data);
void add_last(ListType* list, element data);
void display(ListType* list);
int is_empty(ListType* list);
void remove_node(ListNode** phead, ListNode* p, ListNode* removed);
void delete_node(ListType* list, int pos);
void clear(ListType* list);


int main() {
	FILE* fp;
	ListType list;
	int nTemp;
	int getNum;
	int isEven = 0;
	element max, min;

	init(&list);

	// 파일 열어 데이터 개수 저장
	// 파일을 열어 파일의 끝이 아닐 때까지 계속 새로운 노드 생성하여 리스트에 삽입
	fp = fopen("data.txt", "rt");
	if (fp == NULL) {
		printf("File not found\n");
		return 0;
	}
	while (!feof(fp)) {
		fscanf(fp, "%d", &nTemp);
		add_last(&list, nTemp); // 구조체 변수이기 때문에 주소값을 전달하여 함수 호출
	}

	fclose(fp);

	display(&list);
	clear(&list);

	return 0;
}

void init(ListType* list) {
	if (list == NULL)
		return;

	// head와 length 초기화
	list->length = 0;
	list->head = NULL; // head 포인터가 가리키는 값이 없다는 뜻
}

int get_length(ListType* list) {
	return list->length;
}

ListNode* get_node_at(ListType* list, int pos) {
	int i;
	ListNode* tmp_node = list->head; // 리스트의 헤드 포인터 스캔함

	if (pos < 0) return NULL; // position 은 0부터 가능

	// 특정 position에 있는 노드를 찾아 리턴
	for(i = 0;i < pos;i++)
		tmp_node = tmp_node->link;

	return tmp_node;
}

/*
phead: 리스트의 헤드 포인터 (phead에 대한 포인터)
p: 선행 노드
new_node: 삽입될 노드
*/
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if (*phead == NULL) // empty list
	{
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) // p가 NULL이면 첫번째 노드
	{
		new_node->link = *phead;
		*phead = new_node;
	}
	else // p 다음에 new_node 삽입
	{
		new_node->link = p->link;
		p->link = new_node;
	}
}

// position 위치에 새로운 데이터를 추가
void add(ListType* list, int position, element data) {
	ListNode* p;

	// position의 lower range와 upper range를 체크하여 노드를 추가 가능한지 여부 판단
	if (position >= 0 && position <= list->length) {
		ListNode* node = (ListNode*)malloc(sizeof(ListNode));
		if (node == NULL) {
			printf("fail to allocate memory\n");
			exit(0);
		}
		node->data = data;

		p = get_node_at(list, position - 1); // position 위치의 노드 앞의 노드를 가져옴
		insert_node(&(list->head), p, node); // 이전 p노드의 link에 position위치의 새로운 노드를 삽입
		list->length++;
	}

}

// 리스트의 처음에 삽입
void add_first(ListType* list, element data) {
	add(list, 0, data);
}
 
// 리스트의 마지막에 삽입
void add_last(ListType* list, element data) {
	add(list, get_length(list), data); //
}

void display(ListType* list) {
	int i;
	ListNode* node = list->head;
	for (int i = 0;i < list->length;i++) {
		printf("%d\t", node->data);
		node = node->link;
	}
	printf("\n");
}

void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}

int is_empty(ListType* list) {
	return list->length; // 비어있다면 null 값 리턴
}
// pos 위치에 있는 노드 삭제
void delete_node(ListType* list, int pos) {
	if (!is_empty(list) && (pos >= 0 && pos < list->length)) {
		ListNode* p = get_node_at(list, pos - 1); // 선행 노드
		remove_node(&(list->head), p, (p != NULL) ? p->link : NULL); // 선행 노드를 다음 노드와 연결하도록
		list->length--;
	}
}

void clear(ListType* list) {
	int i;
	ListNode* node = list->head;
	for (int i = 0;i < list->length;i++) {
		delete_node(list, i); // i위치에 있는 노드 삭제
	}
}

 

---

[각 부분 이해해보기]

 

함수 원형

 

void init(ListType* list);
int get_length(ListType* list);
ListNode* get_node_at(ListType* list, int pos);
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node);
void add(ListType* list, int position, element data);
void add_first(ListType* list, element data);
void add_last(ListType* list, element data);
void display(ListType* list);
int is_empty(ListType* list);
void remove_node(ListNode** phead, ListNode* p, ListNode* removed);
void delete_node(ListType* list, int pos);
void get_maxmin(ListType* list); // 추가 구현
void search(ListType* list, element target); // 추가 구현
void clear(ListType* list);

 

typedef int element; // 실제 데이터
typedef struct ListNode // 각 노드의 구조
{
	element data;
	struct ListNode* link;
}ListNode;

typedef struct // 메타 구조체(ListNode의 속성에 대한 구조체)
{
	ListNode* head; // 연결리스트의 헤드포인터
	int length; // 리스트 노드의 개수
}ListType;

 

1. 메타 구조체 구현

 

ListNode는 기존의 자기참조 구조체와 생김새가 동일하다.

int형 data 변수를 데이터 필드로, link 구조체 포인터를 링크 필드로 포함하고 있다.

추가로 연결 리스트와 해당 리스트의 길이를 멤버로 포함하고 있는 ListType이라는 메타 구조체가 구현되었다.

 

 

ListType list; // ListType 구조체 변수 list 선언

void init(ListType* list) {
	if (list == NULL)
		return;

	// head와 length 초기화
	list->length = 0;
	list->head = NULL; // head 포인터가 가리키는 값이 없다는 뜻
}

int get_length(ListType* list) {
	return list->length;
}

 

2. void init(ListType *list); int get_length(ListType *list); 

 

우선 연결리스트와 리스트의 길이를 멤버로 포함하고 있는 ListType 구조체의 변수 list를 선언하였다.

main함수에서는 변수의 주소를 인수로 전달하여 init과 get_length를 호출하게 된다.

 

init 함수에서는 생성된 메타 구조체 변수의 초기 작업을 수행한다.

length 멤버에는 0을 대입, 아직 리스트가 생성되지 않았으므로 head 포인터에는 NULL값을 대입한다.

 

 

ListNode* get_node_at(ListType* list, int pos) {
	int i;
	ListNode* tmp_node = list->head; // 리스트의 헤드 포인터 스캔함

	if (pos < 0) return NULL; // position 은 0부터 가능

	// 특정 position에 있는 노드를 찾아 리턴
	for(i = 0;i < pos;i++)
		tmp_node = tmp_node->link;

	return tmp_node;
}

 

3. ListNode* get_node_at(ListType *list, int pos);

특정 pos에 위치한 노드를 반환한다.

 

리스트의 처음부터 노드를 하나씩 접근하며 pos 위치까지 이 과정을 반복한다.

pos위치에 있는 node를 반환한다.

 

 

 

/*
phead: 리스트의 헤드 포인터 (phead에 대한 포인터)
p: 선행 노드
new_node: 삽입될 노드
*/
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	if (*phead == NULL) // empty list
	{
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) // p가 NULL이면 첫번째 노드
	{
		new_node->link = *phead;
		*phead = new_node;
	}
	else // p 다음에 new_node 삽입
	{
		new_node->link = p->link;
		p->link = new_node;
	}
}

 

4. void insert_node(ListNode **phead, ListNode *p, ListNode *new_node);

생성된 노드를 리스트에 삽입하는 함수이다.

 

헤드 포인터가 비어있다면, new_node를 헤드 포인터에 대입한다.

추가하려는 노드의 앞에 위치한 노드를 의미하는 p가 NULL값인 경우에에는, new_node를 다시 phead에 대입한다.

위의 경우에 해당되지 않는다면, new_node를 p의 다음 위치에 삽입한다.

 

 

 

// position 위치에 새로운 데이터를 추가
void add(ListType* list, int position, element data) {
	ListNode* p;

	// position의 lower range와 upper range를 체크하여 노드를 추가 가능한지 여부 판단
	if (position >= 0 && position <= list->length) {
		ListNode* node = (ListNode*)malloc(sizeof(ListNode));
		if (node == NULL) {
			printf("fail to allocate memory\n");
			exit(0);
		}
		node->data = data;

		p = get_node_at(list, position - 1); // position 위치의 노드 앞의 노드를 가져옴
		insert_node(&(list->head), p, node); // 이전 p노드의 link에 position위치의 새로운 노드를 삽입
		list->length++;
	}
}

// 리스트의 처음에 삽입
void add_first(ListType* list, element data) {
	add(list, 0, data);
}
 
// 리스트의 마지막에 삽입
void add_last(ListType* list, element data) {
	add(list, get_length(list), data); //
}

 

5. void add(ListType *list, int position, element data);

생성한 data를 리스트의 position 위치에 삽입하는 함수이다.

 

두번째 매개 변수로 전달 받은 position이 0보다 크고, 리스트의 현재 깅ㄹ이보다 작거나 같은 경우에 해당 코드 블럭을 싱핸한다.

새로운 노드를 위한 메모리 공간을 동적 할당 받고, 데이터 필드에 세번째 매개변수로 전달 받은 data를 대입한다.

 

 

6. 연결리스트 전체 출력

void display(ListType* list) {
	int i;
	ListNode* node = list->head;
	for (int i = 0;i < list->length;i++) {
		printf("%d\t", node->data);
		node = node->link;
	}
	printf("\n");
}

 

7. 특정한 노드에 해당하는 메모리 해제

void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}

 

8. 연결리스트의 특정한 위치에 있는 노드 삭제

int is_empty(ListType* list) {
	return list->length; // 비어있다면 null 값 리턴
}

// pos 위치에 있는 노드 삭제
void delete_node(ListType* list, int pos) {
	if (!is_empty(list) && (pos >= 0 && pos < list->length)) {
		ListNode* p = get_node_at(list, pos - 1); // 선행 노드
		remove_node(&(list->head), p, (p != NULL) ? p->link : NULL); // 선행 노드를 다음 노드와 연결하도록
		list->length--;
	}
}

 

9. 전체 리스트의 메모리 해제

void clear(ListType* list) {
	int i;
	ListNode* node = list->head;
	for (int i = 0;i < list->length;i++) {
		delete_node(list, i); // i위치에 있는 노드 삭제
	}
}

 

 

 

+ 추가 구현

 

10. 최대 최소 출력

// main 함수에서의 호출
		get_maxmin(&list); // 최대 최소


// 최대 최소 출력
void get_maxmin(ListType* list) {
	ListNode* p = list->head;

	element max = p->data, min = p->data;
	while (p != NULL) {
		if (p->data > max) max = p->data;
		if (p->data < min)min = p->data;
		p = p->link;
	}
	printf("\n최대값 : %d\n최소값 : %d\n", max, min);
}

 

11. 입력 값 리스트에서 탐색

 

// main함수에서의 호출
	while (1) {
		printf("\n값을 입력하세요<0:종료> : ");
		scanf("%d", &getNum);
		if (getNum == 0)break;
		search(&list, getNum);
	}
    

// 입력 받은 값이 리스트에 몇 개 있는지 찾기
void search(ListType* list, element target) {
	ListNode* p = list->head;
	int cnt = 0;

	while (p != NULL) {
		if (target == p->data) cnt++;
		p = p->link;
	}
	printf("%d는 리스트에 %d개 있습니다.\n", target, cnt);
}