[자료구조] 연결 리스트 (Linked List) 응용 - 특정 위치에 데이터 삽입과 삭제, 선행 노드의 포인터 이용

특정 위치에 새로운 데이터(노드)를 삽입하고, 삭제할 수 있는 연결 리스트 프로그램이다.

 

 

data.txt

20074241 마바사 50 90 95
20074242 가나다 80 95 85
20074243 라마바 70 60 95
20074244 사아자 50 30 65


add_last() 함수를 이용

 

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

#define TRUE 1
#define FALSE 0

typedef struct element {
	int nId;
	char* name;
	int nKor, nEng, nMath, nSum;
	double dAvg;
}element;

typedef struct ListNode{
	element data;
	struct ListNode* link;
}ListNode;

typedef struct ListType{
	ListNode* head; // 리스트의 헤드포인터
	int length;		// 노드의 개수
}ListType;

// 초기화(ListType의 head와 length를 초기화)
void init(ListType* list) {
	if (list == NULL) return;
	list->length = 0;
	list->head = NULL;
}

int is_empty(ListType* list) {
	if (list->head == NULL) return TRUE;
	else return FALSE;
}

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

// insert_node : 실제로 새로운 노드를 삽입하는 함수 (선행 노드 p가 가리키는 링크에 new_node 의 링크를 연결)
void insert_node(ListNode** phead, ListNode* p, ListNode* new_node) {
	// phead: 헤드 포인터
	// p : 선행 노드
	// new_node : 신규 노드

	if (*phead == NULL) {	// empty list
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) {	// 선행 노드가 없는 경우(첫번째에 삽입하게 되는 경우)
		new_node->link = *phead;
		*phead = new_node;
	}
	else { // p 노드 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}

// 리스트를 삽입할 위치의 노드의 주소를 얻는 함수
ListNode* get_node_at(ListType* list, int pos) {
	int i;
	ListNode* tmp_node = list->head;

	if (pos < 0) return NULL; // 첫번째 위치에 삽입하도록 pos값이 0 미만이 전달된경우
	for (i = 0;i < pos;i++)
		tmp_node = tmp_node->link;

	return tmp_node; // pos 위치의 노드 주소값 반환
}

// pos 위치에 data를 추가
void add(ListType *list, int position, element data) {
	ListNode* p;

	// pos의 숫자가 new_node 를 삽입하기 위한 유효한 위치인지 먼저 검사해보기
	if (position >= 0 && position <= list->length) {
		ListNode* node = (ListNode*)malloc(sizeof(ListNode));
		
		if (node == NULL) {
			printf("memory allocation failure\n");
			return;
		}
		node->data = data;

		p = get_node_at(list, position - 1); // 선행 노드의 주소를 주소를
		insert_node(&(list->head), p, node); // 해당 포인터 p 위치에 new node를 삽입
		list->length++;
	}
}

// add_first : 리스트의 첫번째 노드 삽입
void add_first(ListType* list, element data) {
	// 새로 추가하는 노드가 기존의 첫번째 노드를 가리키도록 
	add(list, 0, data); // list->head 다음에 추가
}
// add_last: 리스트의 끝에 순서대로 삽입하는 함수
void add_last(ListType* list, element data) {
	add(list, get_length(list), data); // 리스트의 맨 뒤(get_length())에 추가하도록 함수 호출
}

// 연결리스트 출력
void display(ListType* list) {
	int i;
	ListNode* node = list->head;

	printf("|========|======|====|====|====|====|======|\n");
	printf("|  학번  | 이름 |국어|영어|수학|총점| 평균 |\n");
	printf("|========|======|====|====|====|====|======|\n");


	// ListType 구조체의 head 포인터가 가리키는 ListNode 구조체의 data의 멤버 변수들 출력
	// 노드의 개수만큼 반복하기
	for (i = 0;i < list->length;i++) {
		printf("|%d|%s|%4d|%4d|%4d|%4d|%6.2lf|\n",
			node->data.nId, node->data.name, node->data.nKor, node->data.nEng,
			node->data.nMath, node->data.nSum, node->data.dAvg);

		node = node->link; // 다음 노드로 이동
	}
	printf("|========|======|====|====|====|====|======|\n\n");
}

// 최고 점수를 갖고 있는 노드 출력
void list_max(ListType* list) {
	int i;
	ListNode* node = list->head;
	ListNode* max_node=list->head; // 최고 점수를 갖고 있는 노드를 저장할 임시 포인터에 첫번째 노드 주소를 담아둔다.
	node = node->link; // 다음 노드와 비교하기 위해 2번째 노드를 다시 대입

	// (노드의 개수-1)만큼 차례대로 반복하며, dAvg 평균을 비교하여 더 높은 노드를 max_node에 대입. 반복하여 갱신한다
	for (i = 0;i < list->length-1;i++) {
		if (node->data.dAvg > max_node->data.dAvg)
			max_node = node;
		node = node->link; // 다음 노드로 이동
	}
	
	// 최고 점수를 갖고 있는 max_node 의 데이터들을 출력
	printf("|========|======|====|====|====|====|======|\n");
	printf("|  학번  | 이름 |국어|영어|수학|총점| 평균 |\n");
	printf("|========|======|====|====|====|====|======|\n");
	
	printf("|%d|%s|%4d|%4d|%4d|%4d|%6.2lf|\n",
		max_node->data.nId, max_node->data.name, max_node->data.nKor, max_node->data.nEng,
		max_node->data.nMath, max_node->data.nSum, max_node->data.dAvg);

	printf("|========|======|====|====|====|====|======|\n\n");
}

// 삭제할 노드의 메모리 공간 해제
void remove_node(ListNode** phead, ListNode* p, ListNode* removed) {
	// phead: 헤드 포인터
	// p : 삭제할 노드의 선행 노드
	// removed : 삭제할 노드

	if (p == NULL) {
		ListNode* pf;
		pf = *phead;
		*phead = (*phead)->link;
		free(pf->data.name); // 동적으로 할당받은 name에 대한 메모리 해제
		free(pf); // 전체 pf 노드에 대한 메모리 해제
	}
	else
		p->link = removed->link;

	// printf("%d 학번의 데이터 삭제\n", removed->data.nId);

	free(removed);
}

// 특정 위치의 노드 삭제
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, cnt = list->length;

	for (i = 0;i < cnt;i++)
		delete_node(list, 0); // 위치를 지정해 준 노드의 메모리를 해제(첫번째 인덱스의 노드 삭제)

	// 뒤에서부터 삭제할 수 있는 함수도 구현하기
}

int main() {
	FILE* fp;
	element input;
	ListType list;
	char buf[100];

	fp = fopen("data.txt", "rt");
	if (fp == NULL) {
		printf("file not found \n");
		return 0;
	}
	init(&list);

	// 파일 읽어서 연결리스트에 저장
	while (!feof(fp)) {
		// element tmp 구조체의 변수들에 임시로 읽어 저장
		fscanf(fp, "%d%s%d%d%d", &input.nId, buf, &input.nKor, &input.nEng, &input.nMath);
		input.nSum = input.nKor + input.nEng + input.nMath;
		input.dAvg = input.nSum / 3.0;
		input.name = (char*)malloc(strlen(buf) * sizeof(char) + 1); // char형 포인터에 실제 메모리를 할당해줌
		strcpy(input.name, buf);

		add_last(&list, input);
	}

	//printf("리스트 추가 후 출력 \n");
	display(&list); // 연결 리스트 출력

	// 최고 점수 검색

	// 값이 가장 큰 노드를 찾아 출력하는 list_max()
	printf("최고 점수는 ? \n");
	list_max(&list); 

	printf("\n리스트 삭제\n\n");
	clear(&list);

	printf("삭제된 후 리스트 출력 \n");
	display(&list);
}

 

 

 

add_first() 함수를 이용

 while (!feof(fp)) { // element tmp 구조체의 변수들에 임시로 읽어 저장
 	fscanf(fp, "%d%s%d%d%d", &input.nId, buf, &input.nKor, &input.nEng, &input.nMath);
    
   	 ...
    
   	add_first(&list, input);
}