C언어 구조체 및 공용체 주요예제7 (이중 연결 리스트에서 특정 문자 삭제)

내용 출처 : YES C (정보공학연구소 /생능출판사)

이중 연결 리스트(doubly linked list) 에서 특정 문자 삭제하는 예제

// 이중 연결 리스트 예제

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

#define MAXLINE 100

typedef char DATA;

struct ELEMENT {
	DATA d;
	ELEMENT *prev;
	ELEMENT *next;
};

typedef ELEMENT* LINK;

void concatenate(LINK a, LINK b);
int count_it(LINK head);
void delete_list(LINK head);
LINK string_to_list(LINK p, char s[]);
void wrt_list(LINK hp);
void wrt_rev_list(LINK tp);
void find_and_delete(LINK head, DATA x);

LINK hp = NULL;
LINK tp = NULL;

int main()
{
	char line[MAXLINE], x;
	LINK p;

	while (1) {
		printf("type in a line of text : ");
		assert(fgets(line, MAXLINE, stdin) != NULL);
		
		if (*line == '\n') {
			break;
		}

		p = string_to_list(NULL, line);

		if (hp == NULL) {
			hp = p;
		}
		else {
			concatenate(hp, p);
		}

		printf("\n forward list : "); wrt_list(hp);
		printf("\n reverse list : "); wrt_rev_list(tp);
		printf("\n");
	}

	printf("삭제할 문자를 입력하세요 : "); scanf_s("%c", &x, sizeof(char));
	find_and_delete(hp, x);

	printf("%c 문자를 삭제하였습니다. \n",x );

	printf("\n forward list : "); wrt_list(hp);
	printf("\n reverse list : "); wrt_rev_list(tp);
	printf("\n");

	delete_list(hp);
}


//concatenate list a and b with a as head.
void concatenate(LINK a, LINK b)
{
	assert(a != NULL);

	if (a->next == NULL) {
		a->next = b;
		b->prev = a;	//데이터를 연결할 때 반대로도 연결함.
	}
	else {
		concatenate(a->next, b);
	}
}


//count a list iteratively.
int count_it(LINK head)
{
	int cnt = 0;

	for (; head != NULL; head->next) {
		cnt++;
	}

	return cnt;
}

//recursive deletion of a list
void delete_list(LINK head)
{
	if (head != NULL) {
		delete_list(head->next);
		free(head);
		//재귀호출을 이용해서 맨 마지막 노드부터 지워온다.
	}
}

//데이터를 찾아서 지우는 함수
void find_and_delete(LINK head, DATA x)
{
	LINK p;
	while (1) {
		p = head;

		if (p == NULL) {
			break;
		}

		if (p->d == x) {	//삭제할 데이터를 찾은 경우
			if (p->prev != NULL && p->next == NULL) {
				//찾은 데이터가 가장 마지막 데이터인 경우
				p->prev->next = NULL;
				tp = p->prev;
				//tp를 삭제된 데이터 이전 데이터로 바꿈
			}
			else if (p->prev == NULL && p->next != NULL) {
				//찾은 데이터가 가장 첫번째 데이터인 경우
				p->next->prev = NULL;
				hp = p->next;
				//hp를 삭제된 데이터 다음 데이터로 바꿈
			}
			else {
				//그외(찾은 데이터가 가운데에 있는 경우)
				p->next->prev = p->prev;
				p->prev->next = p->next;
			}
			head = p->next;

			free(p);
		}
		else {
			head = p->next;
		}
	}
}

//재귀호출을 이용해서 리스트를 만든다.
LINK string_to_list(LINK p, char s[])
{
	DATA d;
	LINK head;

	if (s[0] == '\0')
	{
		return NULL;
	}
	else {
		head = (LINK)malloc(sizeof(ELEMENT));

		if (s[0] == '\n') {
			d = ' ';
			tp = head;
		}
		else {
			d = s[0];
		}

		head->d = d;

		if (p == NULL) {
			head->prev = NULL;
		}
		else {
			head->prev = p;
		}
		head->next = string_to_list(head, s + 1);

		return head;
	}
}

//hp를 이용해서 처음부터 순서대로 출력
void wrt_list(LINK hp)
{
	LINK p;

	for (p = hp; p != NULL; p = p->next) {
		putchar(p->d);
	}
}

//tp를 이용해서 마지막부터 역순으로 출력
void wrt_rev_list(LINK tp)
{
	LINK p;
	for (p = tp; p != NULL; p = p->prev) {
		putchar(p->d);
	}

}