연결 리스트 응용 - 리스트 뒤집기

연결 리스트 응용

- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.

저의 정리가 옳지 않다면 피드백 부탁드립니다.

---

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

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

//head에 삽입
node* insert_head(node *head, int value)
{
	node *p = (node*)malloc(sizeof(node));
	p->data = value;
	p->link = head;
	head = p;
	return head;
}

//삽입
node* insert(node **list, int num)
{
	node *p = (node*)malloc(sizeof(node));
	p->data = num;
	p->link = NULL;
	node* pos = *list;

	if (*list == NULL) {
		*list = p;
	}

	else if (p->data >= (*list)->data)
	{
		p->link = *list;
		*list = p;
	}
	else {
		while (1)
		{
			if (pos->link == NULL) {
				pos->link = p;
				break;
			}
			else if (p->data > pos->link->data) {
				p->link = pos->link;
				pos->link = p;
				break;
			}
			pos = pos->link;
		}
	}
}

//head노드 삭제
node* delete_head(node* head)
{
	node *removed;
	if (head == NULL)
		return NULL;
	removed = head;
	head = removed->link;
	free(removed);
	return head;
}

//삭제
node* delete(node *head, int key) {
	node* list = head; 
	if (head->data == key) {
		head = head->link; 
		return; 
	} else {
		while (list->link != NULL) 
		{ if (list->link->data == key) {
			list->link = list->link->link; 
			return; 
		} 
		list = list->link; 
		} 
	} 
}

//검색
node* search(node* head, element num)
{
	node* p = head;

	while (p != NULL) {
		if (p->data == num) {
			return p;
		}
		p = p->link;
	}
	return NULL
}

//연결 리스트 뒤집기
node* reverse(node* head)
{
	node* p, * q, * r;

	p = head;
	q = NULL;
	while (p != NULL)
	{
		r = q;
		q = p;
		p = p->link;
		q->link = r;
	}
	return q;
}

//출력
void print_list(node* head)
{
	node* p = head;
	while (p != NULL) {
		printf("%d ", p->data);
		p = p->link;
	}
	printf("\n");
}

int main(void)
{
	node* head = NULL;
	node* rhead = NULL;

	while (1)
	{
		int answer;
		int input = NULL;
		int* tmp = NULL;
		printf("1: 추가, 2: 삭제, 3: 출력, 4: 역순 출력, 5: 종료\n");
		scanf_s("%d", &answer);

		switch (answer) {
			case 1:
				//추가
				printf("입력 : ");
				scanf_s("%d", &input);
				if (head == NULL) { 
					insert(&head, input);
					printf("성공.\n");
				}
				else {
					if (search(head, input) == NULL) {
						insert(&head, input);
						printf("성공.\n");
					}
					else {
						printf("실패. \n"); 
					}
				}
				break;
			case 2:
				//삭제
				printf("삭제 : ");
				scanf_s("%d", &input);
				if (head == NULL)
					printf("리스트 비어있음.\n");
				else if (head->data == input) //첫번째 노드일 경우
					head = head->link;
				else
					delete(head, input); //그 외
				break;
			
			case 3:
				printf("출력 : ");
				if (head == NULL)
					printf("리스트 비어있음. \n");
				print_list(head);
				printf("끝\n");
				break;

			case 4:
				printf("역순 출력 : ");
				if (head == NULL)
					printf("리스트 비어있음.\n");
				rhead = reverse(head); //리스트 뒤집기
				print_list(rhead); //출력
				head = reverse(rhead); //다시 뒤집어서 원상 복구
				printf("끝\n");
				break;

			case 5:
				exit(1);

			default :
				continue;
		}
	}

	return 0;
}