C언어 구조체 및 공용체 주요예제2 (선형 연결 리스트)

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

선형 연결 리스트 예제

//linear linked list example

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

#define MAXLINE 100

typedef char DATA;	// will use char in examples

struct linked_list {
	DATA			d;
	linked_list*	next;
};

typedef linked_list ELEMENT;
typedef ELEMENT*	LINK;

void concatenate(LINK a, LINK b);
int count(LINK head);
int count_it(LINK head);
LINK string_to_list(char s[]);
void delete_list(LINK head);
void wrt_list(LINK hp);
void print_list(LINK head);

int main()
{
	char line[MAXLINE];
	LINK hp = NULL;			//hp = head pointer
	LINK p;

	printf("This program will do the following repeatedly and then delete the linked list before exiting : \n");
	printf("\n");
	printf("\t1. cereate a linked list from a line of text \n");
	printf("\t2. concatinate the list to what we already have \n");
	printf("\t3. print the data in the linked list\n");

	while (1) {
		printf("\n Type in a line of text : ");
		assert(fgets(line, MAXLINE, stdin) != NULL);

		if (*line == '\n') {
			break;
		}

		p = string_to_list(line);
		
		if (hp == NULL) {
			hp = p;
		}
		else {
			concatenate(hp, p);
		}
		putchar('\n');
		wrt_list(hp);
		putchar('\n');
	}
	delete_list(hp);
	printf("\n bye! \n\n");

	return 0;
}

//concatenate list a and b with as head.
//리스트의 마지막에 b를 연결시키는 함수
void concatenate(LINK a, LINK b)
{
	assert(a != NULL); // a가 NULL이면 프로그램을 종료시킨다.

	if (a->next == NULL) {
		a->next = b;
	}
	else {
		concatenate(a->next, b);
	}
}

//count a list recursively.
//재귀 호출을 이용해서 리스트에 연결된 ELEMENT들의 개수를 세는 함수
int count(LINK head)
{
	if (head == NULL) {
		return 0;
	}
	else {
		return (1 + count(head->next));
	}
}

//count a list iteratively.
//반복문을 이용해서 리스트에 연결된 ELEMENT들의 개수를 세는 함수
int count_it(LINK head)
{
	int cnt = 0;

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

	return cnt;
}

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

	if (s[0] == '\0') { //base case
		return NULL;
	}
	else {
		head = (LINK)malloc(sizeof(ELEMENT));
		d = (s[0] == '\n') ? ' ' : s[0];
		head->d = d;
		head->next = string_to_list(s + 1);
		return head;
	}

}

//recursive deletion of a list
//재귀를 이용해서 리스트를 삭제한다.
void delete_list(LINK head) {
	if (head != NULL) {
		delete_list(head->next);
		free(head);
	}
}

//write data in list iteratively.
//리스트에 데이터를 쓰는 함수.
void wrt_list(LINK hp)
{
	LINK	p;
	for (p = hp; p != NULL; p = p->next) {
		putchar(p->d);
	}
}

//print a list recursively.
//재귀호출을 이용해서 리스트의 내용을 출력
void print_list(LINK head)
{
	if (head == NULL) {
		printf("NULL");
	}
	else {
		printf("%c -> ", head->d);
		print_list(head->next);
	}
}