Roopretelcham

수식계산을 위해 고려해야할 두가지

1. 소괄호 먼저 연산

2. 연산자 우선순위를 근거로 연산 

수식 표기법

중위 표기법 (infix notation)    ex) 5 + 2 / 7

: 수식내에 연산 순서 정보 없음. 소괄호와 연산자 우선 순위를 정의하여 연산 순서 명시. 일반적인 수식은 바로 infix

전위 표기법 (prefix notation)    ex) +5 / 2 7

후위 표기법 (postfix notation)    ex) 5 2 7 / +

: 전위와 후위는 수식내에 연산순서의 정보가 담겨있다. 따라서 소괄호가 필요없고 연산 우선순위를 결정할 필요가 없다.

중위 표기법은 우리가 이해하기는 쉽다. 하지만 연산자 우선 순위를 조절하기 위해 소괄호가 필요하다.

따라서, 수식의 값을 구하기 쉽고 괄호없이 표현이 정확한 후위 표기법을 사용한다. 

stack을 이용한 중위 -> 후위 수식 변환 과정

 수식을 이루는 왼쪽 문자부터 하나씩 처리

1. 피 연산자는 오른쪽(변환된 수식이 위치할 자리)으로 이동

2. 연산자는 쟁반(stack)으로 이동

3. stack에 기존 연산자가 있을 때는?

stack에 위치한 연산자 우선 순위가 높으면

-> stack에 위치한 연산자를 꺼내 오른쪽으로 이동, 새 연산자를 stack으로 이동

stack에 위치한 연산자 우선 순위가 낮으면

-> stack에 위치한 연산자 위에 새 연산자 쌓음

서로의 연산자 우선 순위가 같다면

-> stack에 위치한 연산자 우선 순위가 높다고 가정하여 오른쪽으로 옮기고, 새 연산자를 stack으로 이동

 둘 이상의 연산자가 쌓여있을 때에도 1:1로 계속 비교하여 진행해야 한다.

4. 마지막으로 위와 같이 쟁반(stack)의 데이터 차례대로 꺼내 옮김

중위 -> 후위 수식 변환 과정 : 소괄호 고려

) 연산자를 만나면 stack의 data를 ( 연산자 만날때까지 오른쪽으로 옮긴다. 그리고 괄호는 사라진다.

위의 그림에서도 이 같은 과정을 거친 후,  / 연산자를 stack으로 4를 오른쪽으로 옮기고 마지막으로 stack의 데이터( / )를 꺼내 옮긴다.

-> 1 2 3 * + 4 /

중위 -> 후위 수식 변환 프로그램 구현

위의 과정을 코드로 옮기면 다음과 같다.

일단 stack의 정의와 연결리스트 초기화는 이전 포스팅 참조 (http://smart2016.tistory.com/113)

 중위 표기법 수식을 배열에 담아 함수 인자로 전달, 호출된 함수의 인자 MExp에는 변환된 수식이 담기도록 한다.

아래 함수는 연산자의 우선 순위 정보를 반환하는 함수로 ConvToRPN의 helper function이다.

( 는 ) 연산자가 등장할 때까지 stack에 남아있어야 하기 때문에 우선순위가 가장 낮다 ( 1 )

 ) 연산자는 stack으로 가지 않기 때문에 return 값 정의 없음

두 연산자 우선순위 비교결과를 반환하는 함수 - ConvToRPN의 실질적인 helper function

op1이 우선순위가 높다면 1 반환, op2가 높다면 -1 반환, 같다면 0 을 반환하도록 정의

후위 표기법의 수식 계산

1. 피연산자는 stack으로 옮김

2. 연산자를 만나면 stack에서 두개의 피연산자를 꺼내 계산

3. 계산결과를 다시 stack에 넣음

stack을 이용한 계산기

//stack을 이용한 계산기

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

#define STACKSIZE 100

int stack[STACKSIZE];
int top;

////////////////////////////////////////////////////////////////////////// 스택 초기화
void init_stack(void)
{
	top = -1;
}

////////////////////////////////////////////////////////////////////////// push
int push(int t)
{
	if (top >= STACKSIZE - 1)
	{
		printf("\n   Stack overflow.");
		exit(1);
	}
	stack[++top] = t;
	return t;
}

////////////////////////////////////////////////////////////////////////// pop
int pop(void)
{
	if (top < 0)
	{
		printf("\n   Stack underflow.");
		exit(1);
	}
	return stack[top--];
}

////////////////////////////////////////////////////////////////////////// 스택 top의 값 구한다.
int get_stack_top(void)
{
	return (top < 0) ? -1 : stack[top];
}

////////////////////////////////////////////////////////////////////////// 스택이 비어있는지 확인
int is_stack_empry(void)
{
	return (top < 0);
}

////////////////////////////////////////////////////////////////////////// 연산자 확인
// 이후 확장시 변경
int is_operator(int k)
{
	return (k == '+' || k == '-' || k == '*' || k == '/');
}

////////////////////////////////////////////////////////////////////////// 피연산사 확인
int is_operand(int src)
{
	return (src >= '0' && src <= '9');
}

////////////////////////////////////////////////////////////////////////// 후위 표기법 적합성 확인
int is_legal(char *s)
{
	int f = 0;
	while (*s)
	{
		while (*s == ' ') // remove space
			s++;
		if (is_operator(*s))
			f--; // 연산자이면 감소
		else
		{
			f++; // 피연산자이면 증가
			while (*s != ' ')
				s++;
		}
		if (f < 1) break; // f가 1보다 적으면 언더플로
		s++;
	}
	return (f == 1); // 피연산자의 수 - 연산자의 수 = 1;
}

////////////////////////////////////////////////////////////////////////// 연산자의 우선순위를 수치로 변환
int precedence(int op)
{
	if (op == '(') return 0;
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/') return 2;
	else return 3;
}

////////////////////////////////////////////////////////////////////////// 중위표기법을 후위표기법으로 변환
// dst : 후위표기법으로 변환한 식 저장, src : 중위 표기법이 저장된 인자
void postfix(char *dst, char *src)
{
	//   char c;
	init_stack(); // 스택 초기화
	while (*src) // 중위 표기법이 남아있는 동안
	{
		if (*src == '(') // '('를 만나면 스택에 푸시
		{
			push(*src);
			src++;
		}
		else if (*src == ')') // ')'를 만나면 '('가 나올 때까지 팝
		{
			while (get_stack_top() != '(')
			{
				*dst++ = pop();
				*dst++ = ' ';
			}
			pop(); // '('는 버린다.
			src++;
		}
		else if (is_operator(*src)) // 연산자
		{
			while (!is_stack_empry() && precedence(get_stack_top()) >= precedence(*src))
			{ // 자신보다 높은 우선순위의 연산자는 스택에서 팝
				*dst++ = pop();
				*dst++ = ' ';
			}
			push(*src); // 자신을 push
			src++;
		}
		else if (is_operand(*src))
		{
			do {
				*dst++ = *src++;
			} while (is_operand(*src));
			*dst++ = ' ';
		}
		else src++;
		// 설정한 문자 외의 값들은 무시한다. 공백, 오타 등.
	}
	while (!is_stack_empry())
	{ // 스택에 남은 연산자를 모두 팝
		*dst++ = pop();
		*dst++ = ' ';
	}
	dst--; // ' '제거
	*dst = 0;
}

int calc(char *p)
{ // 후위표기법 수식을 연산
	int i;
	init_stack();
	while (*p)
	{
		if (is_operand(*p))
		{
			i = 0;
			do {
				i = i * 10 + *p - '0';
				p++;
			} while (*p >= '0' && *p <= '9');
			push(i); // 피연산자는 스택에 푸시.
		}
		else if (*p == '+')
		{ // 연산자가 팝 두 번해서 계산하여 그 결과를 푸시
			push(pop() + pop());
			p++;
		}
		else if (*p == '*')
		{
			push(pop() * pop());
			p++;
		}
		// '-'와 '/'는 교환 법칙이 성립하지 않는다. push(pop() - pop())에서 어느 pop이 먼저인지 컴파일러에 따라 다르다.
		else if (*p == '-')
		{
			i = pop();
			push(pop() - i);
			p++;
		}
		else if (*p == '/')
		{
			i = pop();
			push(pop() / i);
			p++;
		}
		else p++;
	}
	return pop(); // 연산 결과
}

int main()
{
	int r;
	char exp[256];
	char argv[] = { 0 };
	char postExp1[50] = { 0 };
		
	printf("수식 입력: ");
	fgets(postExp1, sizeof(postExp1), stdin);
	postExp1[strlen(postExp1) - 1] = 0;
	
	postfix(exp, postExp1); // 후위표기법으로 바꿈
	printf("\nPostfix : %s", exp);

	if (!is_legal(exp)) // 수식이 적법한가 점검
	{
		printf("\n Expression is not legal!");
		exit(1);
	}
	r = calc(exp); // 연산
	printf("\nAnswer : %d \n", r);
	
	return 0;
}

stack 개념

밑이 막힌 긴 통에 비유

: 먼저 들어간(Push) 것이 아래에 있게 되고 나중에 들어간 것이 위에 있게 된다. 따라서 제일 나중에 들어간 것이 제일 먼저 나온다(POP). 

이 때문에 stack을 LIFO(Last In Firsto Out) 구조라고 한다.

위의 그림과 같이 stack에 값을 집어넣는 것을 Push, 값을 빼내는 것을 Pop이라고 한다.

자료구조에서의 Stack

배열로 구현

stack이 완전히 빈 경우는 top Index가 -1의 값을 가진다. 

stack의 바닥은 배열의 index 0이 된다. 마지막에 저장된 데이터 위치가 top이 된다.

push 연산은 아래와 같이 정리된다.

 - push : Top을 위로 한칸 올리고, Top이 가리키는 위치에 데이터 저장

pop 연산은 아래와 같이 정리된다.

- pop : Top이 가리키는 데이터 반환 후, Top 위치를 한칸 내림

pop 연산시에는 stack이 텅 비어있는 경우를 가정해야 한다. 텅 빈 stack을 pop하면 Stack Underflow가 일어나게 된다.

마지막으로 stack에 저장된 값을 출력하는 함수를 정의한다.

위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.

Output :

 -> Initialize stack.

push 1, 2, 3

===== Stack에 저장된 값 =====

3 2 1

pop 3

===== Stack에 저장된 값 =====

2 1

push 4, 5

 -> Stack Overflow.

===== Stack에 저장된 값 =====

4 2 1

 -> Initialize stack.

 -> Stack is Empty.

pop

 -> Stack underflow.

stack 구조에 맞게 push와 pop이 진행되고 overflow와 underflow가 일어나는 모습도 볼 수 있다.

연결리스트를 이용한 stack

연결리스트 초기화

push 함수

head->next가 stack의 상단이 된다.

pop 함수

pop의 과정은 다음과 같다. delN가 가리키는 노드의 data를 ret에 저장해두었다 노드의 해제와 함께 return한다.

stack이 비어있을 때는 underflow 에러를 띄우고 -1을 return하도록 한다.

clear_stack 함수

배열을 이용한 stack은 top을 -1로 초기화해줬지만 연결리스트는 모든 노드를 메모리에서 해제할 필요가 있다.

dN과 d가 처음 head->next를 가리키게 된다.

dN이 다음 노드로 이동하고 d가 가리키는 노드가 해제된다. 이 과정을 dN이 tail을 가리킬 때까지 반복하게 된다.

그리고 head->next가 tail을 가리키면서 초기화 형태로 돌아가게 된다.

마지막으로 stack의 데이터들을 보여주기 위한 함수이다.

위 함수를 토대로 main함수를 정의하고 출력결과를 살펴 본다.

Output :

 push 1, 2, 3, 4, 5

 스택의 데이터 :

5 4 3 2 1

pop

 스택의 데이터 :

4 3 2 1

push 6, 7, 8

 스택의 데이터 :

8 7 6 4 3 2 1

 스택 비움

 -> Stack is Empty.

pop

 -> Stack underflow.

stack의 개념에는 peek이라고 해서 맨 위의 개체를 반환하되 제거는 하지 않는 것도 있지만 따로 함수로 구현하진 않았다.

그리고 배열의 경우에도 동적할당을 사용해볼 수 있으나 연결리스트에 비해 큰 이점이 없으므로 필요에 따라 선택하는게 좋을 듯 하다.

단순 연결리스트에 파일 입출력을 응용

구조체 정의

연결 리스트의 초기화

데이터 입력받음

노드의 삽입

연결리스트를 파일로 저장

*t가 tail을 가리킬 때까지 (추가할 필요가 노드가 없게 될때까지) 각 노드를 추가한다.

파일을 읽어들여 연결리스트로 구성

malloc() 함수는 메모리를 할당후 초기화하지 않기 때문에 출력된 파일을 메모장으로 열어보면 데이터를 알아보기 힘들게 된다.

하지만 문자열의 끝은 NULL로 구분하게 되므로 콘솔환경의 파일 입출력시에는 아무 문제없다.

만약 식별하기 쉬운 파일 데이터를 원하면, calloc함수를 통해 동적할당하면 된다. (calloc함수는 모든 비트를 0으로 초기화)

calloc

#include <stdlib.h>

void * calloc(size_t elt_count, size_t elt_size);

malloc 함수와의 차이점은 elt_count x elt_size 크기만큼의 바이트를 동적할당한다는 것이다.

그리고 malloc 함수는 쓰레기값으로 초기화되는것과 달리 calloc는 모든 비트를 0으로 초기화한다.

도서관리 프로그램에 구현된 파일 입출력 기능

종료 메뉴 선택시 save_File() 함수 호출 후, 프로그램을 종료한다.

BOOK.DBF 파일의 내용

프로그램 재실행 후 출력 모습 

저장된 파일을 토대로 연결리스트를 구성하면서 처음 입력된 자료가 처음 출력되게 된다.

main함수에서는 연결리스트 초기화 후, 파일을 읽어들여 연결리스트로 재구성한다.

이진 트리 구현의 예

BinaryTree.h

BinaryTree.c

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)

{

if(main->left != NULL)

free(main->left);

main->left = sub;

}

위의 함수에서 왼쪽 서브트리가 하나의 노드라면 문제없지만,

그렇지 않다면 나머지 노드는 잃어버리게 되고 메모리 누수로 이어진다.

둘 이상의 노드로 이루어진 서브트리를 완전히 삭제하려면

서브 트리를 구성하는 모든 노드를 대상으로 free함수를 호출해야 한다.

BinaryTreeMain.c

Output :

2

4

이진 트리의 순회(Traversal)

이진 트리의 순회 방법은 재귀적(recursive)이다.

루트 노드를 방문하는 시점에 따라 세 가지 순회 방법으로 나뉜다.

서브 트리가 존재하는 이진 트리의 중위 순회

// 이진 트리 전체를 중위 순회하는 함수

void InorderTraverse(BTreeNode * bt)

{

if(bt == NULL)    // bt가 NULL이면 재귀 탈출! 

return;

InorderTraverse(bt->left); 

printf("%d \n", bt->data); 

InorderTraverse(bt->right); 

}

재귀함수와 관련된 코드를 이해할 떄는 단순히 거슬러가는것이 아니라,

복사본을 만들고 호출하고 호출된 순서의 역순으로 반환이 이뤄진다고 이해하면 쉽다.

BinaryTreeTraverseMain.c

Output :

4

2

1

3

함수 포인터의 활용

typedef void VisitFuncPtr(BTData data);    // (*VisitFuncPtr)로 대신 가능

action이 가리키는 함수를 통해 방문 진행

action(bt->data);    // 노드의 방문

VisitFuncPtr 형을 기준으로 정의된 함수

void ShowIntData(int data)

{

printf("%d ", data);

}

BinaryTreeTraversalAdded.7z

output :

1 2 4 5 3 6

4 2 5 1 3 6

4 5 2 6 3 1

Tree는 단순한 데이터의 저장이 아닌 "데이터의 표현을 위한 도구"이다.

자료구조를 공부하는데 있어서 시야를 넓게 가지고 깊게 사고하려는 노력이 필요하다. 좁은 시야에서 다 이해했다고 착각은 금물

이진 트리의 조건

: 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어짐 (empty set도 node로 간주)

나뉘어진 두 서브 트리도 모두 이진트리

이러한 특성에서 그 구조가 재귀적임을 보인다.

Tree의 level과 높이

각 노드의 깊이(depth)는 루트 노드에서 자신까지 가는 경로의 길이이다. 

트리의 특정 깊이를 가지는 노드의 집합을 레벨(level)이라 부르기도 한다. 루트 노드의 깊이는 0이다.

트리의 높이(height)는 루트 노드에서 가장 깊이 있는 노드까지 가는 경로의 길이이다. 루트 노드만 있는 트리의 높이는 0이다.

full binary tree(정 이진 트리)

leaf node(자식이 없는 노드)가 아닌 모든 노드가 2개의 자식을 가진 트리이다.

complete binary tree(완전 이진 트리)

위에서 아래로 왼쪽에서 오른쪽으로 채워진 트리를 말한다.

끝 부분(마지막 레벨)을 제외하고 모든 노드가 채워진(마지막 레벨을 제외하고는 모든 노드가 자식노드를 2개를 가진) 이진 트리. 

마지막 레벨의 노드들은 왼쪽으로 채워져 있다. 마지막 레벨이 다 채워질 수도 있다.

perfect binary tree(포화 이진 트리)

모든 단말 노드의 깊이가 같은 정 이진 트리이다.

동시에 complete binary tree이기도 하다. (모든 레벨에 노드가 꽉 차야하므로, 역은 성립하지 않음)

이진 트리 구현의 두가지 방법

배열 기반, 이진 트리

위에서 아래, 왼쪽에서 오른쪽으로 노드에 번호를 부여

양방향 연결리스트 기반, 이진트리

실제 구현

하나의 노드는 그 자체로 이진 트리 (entry set도 node이다)

따라서 노드를 표현한 구조체는 실제로 이진 트리를 표현한 구조체가 된다.

// 노드를 표현한 구조체

typedef struct _bTreeNode

{

BTData data;

struct _bTreeNode * left;

struct _bTreeNode * right;

}BtreeNode;

이진 트리의 모든 노드는 직/간접적으로 연결되어 있으며

루트 노드의 주소 값만 기억하면 이진 트리 전체를 가리키는 것과 다름 없다.

이진 트리 자료구조의 ADT (헤더파일에 선언되는 함수들)

BTreeNode * MakeBTreeNode(void); // 노드 생성

BTData GetData(BTreeNode * bt); // 노드에 저장된 데이터 반환

void SetData(BtreeNode * bt, BTData data); // 노드에 데이터 저장

노드에는 함수를 통한 접근이 좋다.

하나의 노드도 이진 트리란 사실을 인지. 

BTreeNode * GetLeftSubTree(BTreeNode * bt); // 왼쪽 서브 트리 주소값 반환

BTreeNode * GetRightSubTree(BTreeNode * bt); // 오른쪽 서브 트리 주소값 반환

 D의 주소값이 곧 왼쪽 서브트리의 주소값이 된다.

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub); // main의 왼쪽 서브트리로 sub 연결

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub); // main의 오른쪽 서브트리로 sub 연결

위의 함수는 노드 뿐만 아니라 트리를 대상으로도 적용되는 함수들이다.

이진트리를 생성하는 main함수 예

int main(void)

{

BTreeNode * ndA = MakeBTreeNode();

BTreeNode * ndB = MakeBTreeNode();

BTreeNode * ndC = MakeBTreeNode();    // 노드 A, B, B 생성

SetData(ndA, 1);

SetData(ndB, 2);

SetData(ndB, 3);

MakeLeftSubTree(bt1, bt2);    // 노드A의 왼쪽 자식 노드로 노드 B 연결

MakeRightSubTree(bt1, bt3);  // 노드A의 오른쪽 자식 노드로 노드 C 연결

( ... )

}

Doubly Linked List (양방향 연결리스트)

typedef struct _node

{

Data data;

struct _node * next;

struct _node * prev;    // 이전 노드를 가리키는 멤버가 추가됨

} Node;

양방향 연결리스트의 LNext

왼쪽 노드의 주소값을 얻을 수 있기 때문에,

단순 연결리스트와 달리 before를 유지할 필요 없음

int LPrevious(List * plist, Data * pdata);

첫번째 노드 추가

newMode->next = NULL;

-> newMode->next = plist->head;

첫번째 노드를 추가할 때 plist->head는 NULL이기 때문에 위의 바뀐 문장으로 두가지 역할을 할 수 있다. 

두번째 노드의 추가는 다음과 같이 이뤄진다.

void LInsert(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

newNode->next = plist->head;        // (1) 새 노드의 next가 이전 노드에 연결

if(plist->head != NULL)                    // NULL이 아니기 때문에

plist->head->prev = newNode; // (2) 이전 node의 prev가 새 노드에 연결

(...생략)

}

void LInsert(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

(...생략)

newNode->prev = NULL;    // (1)

plist->head = newNode;    // (2)

(plist->numOfData)++;

}

데이터 조회

LFirst, LNext는 사실상 차이가 없으며

LPrevious함수는 prev를 통해 이전 노드의 위치를 쉽게 가리킬 수 있다는 점에서 차이가 있다.

int LPrevious(List * plist, Data * pdata)

{

if(plist->cur->prev == NULL)

return FALSE;

plist->cur = plist->cur->prev;

*pdata = plist->cur->data;

return TRUE;

}

원형 연결 리스트의 활용 예제

: 직원 정보 등록 프로그램 (원형 연결리스트 기반)

- 직원 정보 등록 가능

직원 정보는 사번과 이름으로 구성

- 직원 정보를 담을 구조체 정의

구조체를 기반으로 네명의 직원정보를 원형 연결리스트에 저장 (임의 결정, 입력받지 않고 미리 결정해도 됨)

직원 사번은 int형 변수에 담음

원형 연결리스트에는 구조체 변수의 주소 값을 저장

- 직원은 순서대로 돌아가며 당직근무

등록순서대로 당직근무

(A,B,C순 직원등록시 당직근무도 A-B-C-A-B...)

- 직원 이름과 숫자를 이용해 당직자 확인

직원의 이름과 숫자를 인자로 전달받는 함수 정의

- 이 함수는 다음과 같은 직원의 정보 반환

예를 들어 '이수정'과 숫자 7이 전달되면 이수정의 당직근무 7일후

누가 당직근무를 하는지에 대한 정보 반환

Circular Linked List

 모든 노드가 원의 형태를 이루며 연결되어 있기 때문에,

사실상 머리와 꼬리의 구분이 없다.

다만 저장 순서를 근거로한 머리나 꼬리의 개념을 둘 뿐이다.

머리와 꼬리를 가리키는 포인터 변수를 두지않고

하나의 포인터 변수를 가지고 머리 또는 꼬리에 노드를 추가할 수 있게 한다.

꼬리를 가리키는 변수 : tail

머리를 가리키는 변수 : tail->next

변경하거나 추가할 함수

LNext

원형 연결리스트를 계속해서 순환하는 형태로 변경!

(이전 함수 그대로 써도 되지만 원형 연결리스트 특성을 반영)

앞과 뒤에 삽입이 가능한 두개의 함수 정의

LinsertFront, LInsert

void LInsert(List * plist, Data data); // 노드를 꼬리에 추가

void LInsertFront(List * plist, Data data); // 노드를 머리에 추가 

원형 연결리스트의 초기화 함수

void ListInit(List * plsit) // 모든 멤버를 NULL과 0으로 초기화

{

plist->tail = NULL;

plist ->cur = NULL;

plist->befor = NULL;

plist->numOfData = 0;

}

원형 연결리스트의 구현 : 첫번째 Node 추가

첫 번째 노드는 그 자체로 머리이자 꼬리이기 때문에 노드를 뒤에 추가하든 앞에 추가하든 결과가 동일

// LInsert와 LInsertFront의 공통 부분

void LInser~(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

if(plist->tail == NULL) 

{

plist->tail = newNode;           // ①

 newNode->next = newNode;  // ②

}

else

{

// 두번째 이후의 노드는 차이가 있음

}

원형 연결리스트의 구현 : 두번째 이후 Node 머리에 추가

void LInsertFront(List * plist, Data data)

{

Node * newNode = (Node*)malloc(sizeof(Node));

newNode->data = data;

if(plist->tail == NULL) 

{

plist->tail = newNode;

newNode->next = newNode;

}

else

{

newNode->next = plist->tail->next;    // (1)

plist->tail->next = newNode;             // (2)

}

(plist->numOfData)++;

}

원형 연결 리스트 구현 : 머리와 꼬리에 추가하는 과정 비교

tail이 가리키는 것이 꼬리Node, 

꼬리Node가 가리키는 것이 head

데이터의 순서는 동일, tail이 누구를 가리키냐만 차이

void LInsert(List * plist, Data data)

{

(... 생략)

   else 

{

newNode->next = plist->tail->next;

plist->tail->next = newNode;

      plist->tail = newNode;  //  LInsertFront 함수에는 없는 문장이며, 이것이 유일한 차이이다.

}

원형 연결 리스트 구현 : 조회 LFirst

int LFirst(List * plist, Data * pdata)

{

if(plist->tail == NULL)    // 저장된 노드가 없다면

return FALSE;

plist->before = plist->tail;        

plist->cur = plist->tail->next;   

*pdata = plist->cur->data;

return TRUE;

}

조회 LNext

int LNext(List * plist, Data * pdata)

{

if(plist->tail == NULL)    // 저장된 노드가 없다면

return FALSE;

plist->before = plist->cur;

plist->cur = plist->cur->next;

*pdata = plist->cur->data;

return TRUE;

}

원형 연결 리스트 구현 : Node 삭제

핵심적인 부분은 앞서 dummy Node 기반 연결 리스트의 삭제와 다르지 않다.

하지만 다음의 두가지 예외 경우가 있다.

만약 삭제할 노드를 tail이 가리키는데, 그 노드가 마지막 노드라면 tail의 위치 조정이 필요하다.

tail이 가리키는 노드가 머리이자 꼬리인 경우엔 tail에 NULL을 저장한다.

Data LRemove(List * plist)

{

Node * rpos = plist->cur;

Data rdata = rpos->data;

if(rpos == plist->tail)    // 삭제 대상을 tail이 가리킨다면

{

if(plist->tail == plist->tail->next)    // 그리고 마지막 남은 노드라면

plist->tail = NULL;

else

plist->tail = plist->before;

}

plist->before->next = plist->cur->next;

plist->cur = plist->before;

free(rpos);

(plist->numOfData)--;

return rdata;

}

원형 연결리스트 구현 예제

CLinkedList.h

CLinkedList.c

CLinkedListMain.c

Output :

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

1 3 5

정렬 기능 추가된 연결 리스트의 ADT

추가되는 함수

void SetSortRule(List * plist, int (*comp)(LData d1, Ldata d2)  

int (*comp)(LData d1, Ldata d2)  

반환형이 int인 LData형 인자를 두개 전달받는, 함수의 주소값 전달

(typedef LData int)

다음과 같이 정의된 함수의 주소값이 SetSortRule 함수의 두번째 인자가 됨

int WhoIsPrecede(LData d1, LData d2)

{

if(d1 < d2)

return 0; // d1이 head에 가까우면 0 반환

else

return 1; // d2가 head에 가까우면 1 반환

}

리스트라는 자료구조를 바꾸지 않으면서

정렬의 기준을 지정(약속)하는 함수를 정의

DLinkedList.h

연결리스트의 정렬삽입 구현

SetSortRule 함수 : 정렬 기준이 되는 함수 

LinkedList의 멤버 comp : SetSortRule 함수를 통해 전달된 함수 정보 저장

SInsert : comp에 등록된 정렬기준을 근거로 데이터 저장

-> SetSortRule 함수가 호출되면서 정렬 기준이 리스트의 멤버 comp에 등록되면,

Sinsert 함수내에서 comp에 등록된 정렬기준을 근거로 데이터를 정렬해 저장한다.

SInsert 함수

pred(predicate)가 첫번째 노드가 아닌 더미노드를 가리키는 이유

: 노드가 한쪽 방향으로만 연결되있어서 pred가 가리키는 노드의 오른쪽에만

새 노드를 추가할 수 있기 때문이다.

Sinsert함수의 while문 조건의 의미

조건 1.

pred->next != NULL // 연결리스트의 끝에 도달했음을 의미

조건 2.

plist->comp(data, pred->next->data) != 0

// 첫번째 인자인 data가 앞서면 0을 반환해서 숫자의 대소를 비교해나감. (오름차순 기준)

newNode -> data = data;

정렬의 기준을 설정하기 위한 함수

int WhoIsPrecede(int d1, int d2) // 오름차순 정의

{

if (d1 < d2)

return 0;    // d1이 정렬 순서상 앞선다.

else

return 1;    // d2가 정렬 순서상 앞서거나 같다.

}

comp에 등록된 함수가 반환하는 값의 종류와 의미를 결정

main함수에서 SetSortRule(&list, WhoIsPrecede);    // 정렬의 기준 등록

DLinkedList.c

연결리스트 (Linked List)

연결리스트의 구현을 이해하기 위해서는,

malloc 함수와 free함수 기반의 메모리 동적할당에 대한 완전한 이해가 필요

배열은 index를 이용해 순차 접근이 가능한 자료구조

배열은 기본적으로 정적이다. (길이의 변경 불가능)

#include <stdio.h>

int main(void)
{
	int arr[10];
	int readCount = 0;
	int readData;
	int i;

	while (1)
	{
		printf("자연수 입력 (0이하 값 입력시 종료): ");
		scanf("%d", &readData);
		if (readData < 1)
			break;

		arr[readCount++] = readData;
	}

	for (i = 0; i<readCount; i++)
		printf("%d  ", arr[i]);

	return 0;
}

위의 예제에서 0 이하의 값을 입력하지 않고, 

계속해서 할당된 배열의 길이를 넘어서는 입력을 할 시 디버그 에러가 나게 된다.

이를 해결하기 위해선 메모리의 동적할당을 이용해야 한다.

* head : 첫번째 node를 가리키기 위함

* tail : head와 달리 필요없을 수도 있음

* cur : (current) 순차접근을 위한 것

새 노드를 연결리스트 머리에 추가하는 경우는, * tail이 불필요하지만 저장된 순서가 역순이 된다.

꼬리에 추가하는 경우는 저장된 순서가 유지되지만 * tail이 필요

노드의 꼬리에 추가하는 연결리스트

정렬 기능 추가된 연결 리스트의 ADT

추가되는 함수

void SetSortRule(List * plist, int (*comp)(LData d1, Ldata d2)  

int (*comp)(LData d1, Ldata d2)  

반환형이 int인 LData형 인자를 두개 전달받는, 함수의 주소값 전달

(typedef LData int)

다음과 같이 정의된 함수의 주소값이 SetSortRule 함수의 두번째 인자가 됨

int WhoIsPrecede(LData d1, LData d2)

{

if(d1 < d2)

return 0; // d1이 head에 가까우면 0 반환

else

return 1; // d2가 head에 가까우면 1 반환

}

리스트라는 자료구조를 바꾸지 않으면서

정렬의 기준을 지정(약속)하는 함수를 정의

더미 노드 기반, 연결리스트

앞선 예제에서 첫번째 노드는 * head가 가리킨다는 점에서

다른 노드들과 차이가 있었다.

때문에 노드추가, 삭제, 조회하는 방법에 있어 일관성이 없다는 단점이 있었다.

(첫번째 노드와 두번째 이후 노드에 차이가 있다)

이를 해결하기위해 Dummy Node를 추가한다.

처음 추가되는 노드가 구조상 두번째 노드가 되며,

노드 추가, 삭제 및 조회의 과정이 일관된 형태로 구성된다.

LinkedRead.c

#ifndef __POINT_H__
#define __POINT_H__

typedef struct _point
{
	int xpos;
	int ypos;
} Point;

// Point 변수의 xpos, ypos 값 저장
void SetPointPos(Point * ppos, int xpos, int ypos);

// Point 변수의 xpos, ypos 정보 출력 
void ShowPointPos(Point * ppos);

// 두 Point 변수의 비교
int PointComp(Point * pos1, Point * pos2); 

#endif

Point.c (PointComp 함수의 반환값은 임의로 지정)

#include <stdio.h>
#include "Point.h"

void SetPointPos(Point * ppos, int xpos, int ypos)	// 값 저장
{
	ppos->xpos = xpos;
	ppos->ypos = ypos;
}

void ShowPointPos(Point * ppos)
{
	printf("[%d %d]", ppos->xpos, ppos->ypos);
}

int PointComp(Point * pos1, Point * pos2)
{
	//	xpos가 서로 같으면 1, ypos가 서로 같으면 2, 모두 같으면 0, 모두 다르면 -1 반환
	if (pos1->xpos == pos2->xpos)
		return 1;
	else if (pos1->ypos == pos2->ypos)
		return 2;
	else if (pos1->xpos == pos2->xpos && pos1->ypos == pos2->ypos)
		return 0;
	else
		return -1;
}