Dev Journey

1. 스택의 정의와 추상 데이터 타입(ADT)

 - 상자 더미처럼 쌓이는 자료구조

 - LIFO : 후입선출, 스택의 중간에서 데이터를 삭제할 수 없다

 - 객체 : n개의 element 타입의 요소들의 순서 있는 모임

 - 연산 :

• create()
• is_empty(s)
• is_full(s)
• push(s, e)
• pop(s)
• peek(s)

 - 가장 전형적인 예제로 함수 호출에서 복귀주소를 기억하는데 스택을 사용

 - 사용자가 접근할 수 없고 운영 체제만 사용하는 스택이 있는데 함수가 호출될 때마다 활성화 레코드가 만들어지며 여기에 함수로부터 복귀 후에 실행될 명령어의 주소인 프로그램 카운터 값이 기록된다.

2. 배열로 구현한 스택

 - top값은 마지막 입력 위치로 스택이 비어있을 때 top = -1

 - 구조체로 스택구현

typedef struct {
	element stack[MAX_STACK_SIZE];
	int top;
} StackType;

3. 연결리스트로 구현한 스택

typedef int element;	
typedef struct StackNode { 
	element item;
	struct StackNode *link;
} StackNode;

typedef struct {
	StackNode *top;
} LinkedStackType;

4. 스택을 이용한 괄호 검사와 수식의 계산

 1) 괄호 검사는 여는 괄호는 push하고 닫히는 괄호를 만날 때마다 스택에서 pop하여 비교

 2) 수식을 표기하는 방법에는 중위(infix), 후위(postfix), 전위(prefix)

  - 컴파일러는 주로 후위 표기법을 사용한다. 후위표기는 우선순위가 반영되어 있음.

  - 후위 계산 알고리즘 : 피연산자는 push 연산자나오면 second <- pop(); first <- pop();

  - 중위 -> 후위 변환 : 여는 괄호는 스택에 쌓고 닫는 괄호 나오면 여는 괄호 만날때까지 pop(), 연산자 간에 우선순위 따져서 (top에 있는 연산자보다 같거나 낮은 놈이 들어오면 pop()) 출력하면 됨

5. 미로 탐색

 - 알고리즘 : 스택의 역할은 현재 위치에서 갈 수 있는 위치들을 매번 쌓아놓는 통

스택 S와 출구의 위치, 현재 생쥐의 위치를 초기화

while (현재의 위치가 출구가 아니면)
do 현재위치를 방문한 것으로 표기
  if (현재위치의 상하좌우 위치가 아직 방문되지 않았고, 갈수 있으면
    then 그 위치들을 스택 S에 push
  if (is_empty(s))
    then 실패
  else 스택에서 하나의 위치를 꺼내어 현재위치로 만든다

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년

• ADT가 제공하는 연산을 사용하는 것보다 연결 리스트의 포인터를 이용한 연산이 효율적인 경우도 있다

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

#define FALSE 0
#define TRUE 1

typedef int element;
typedef struct ListNode { 
	element data;
	struct ListNode *link;   	
} ListNode;
typedef struct {
	ListNode *head;     // 헤드 포인터
	int length;		// 노드의 개수
} ListType;

// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드 
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node) 
{
	if( *phead == NULL ){	// 공백리스트인 경우
		new_node->link = NULL; 
		*phead = new_node; 
	}
	else if( p == NULL ){ // p가 NULL이면 첫번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else {			 // p 다음에 삽입
		new_node->link = p->link; 
		p->link = new_node; 
	}
}
// phead : 헤드 포인터에 대한 포인터 
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드 
void remove_node(ListNode **phead, ListNode *p, ListNode *removed) 
{
	if( p == NULL ) 
		*phead = (*phead)->link; 
	else 
		p->link = removed->link; 
	free(removed);		
}
// 리스트를 초기화한다.
void init(ListType *list)
{
	if( list == NULL ) return;
	list->length = 0;
	list->head = NULL;
}
// 리스트안에서 pos 위치의 노드를 반환한다.
ListNode *get_node_at(ListType *list, int pos)
{
	int i;
	ListNode *tmp_node = list->head;
	if( pos < 0 ) return NULL;
	for (i=0; i<pos; i++)
		tmp_node = tmp_node->link;
	return tmp_node;
}
// 리스트의 항목의 개수를 반환한다.
int get_length(ListType *list)
{
	return list->length;
}
//
void error(char *message)
{
	fprintf(stderr,"%s\n",message);
	exit(1);
}
// 주어진 위치에 데이터를 삽입한다.
void add(ListType *list, int position, element data) 
{
 ListNode *p;
 if ((position >= 0) && (position <= list->length)){
   ListNode *node= (ListNode *)malloc(sizeof(ListNode)); 
   if( node == NULL ) error("메모리 할당에러");
   node->data = data;
   p = get_node_at(list, position-1);
   insert_node(&(list->head), p, node); 
   list->length++;
 }
} 
// 리스트의 끝에 데이터를 삽입한다.
void add_last(ListType *list, element data)
{
	add(list, get_length(list), data);
}  
// 리스트의 끝에 데이터를 삽입한다.
void add_first(ListType *list, element data)
{
	add(list, 0, data);
}  
//
int is_empty(ListType *list)
{
	if( list->head == NULL ) return 1;
	else return 0;
}

// 주어진 위치의 데이터를 삭제한다.
void delete_node(ListType *list, int pos)
{
	if (!is_empty(list) && (pos >= 0) && (pos < list->length)){
	 ListNode *p = get_node_at(list, pos - 1);
	 ListNode *removed = get_node_at(list, pos);
	 remove_node(&(list->head),p, removed);
	 list->length--;
	}
}
//
element get_entry(ListType *list, int pos)
{
	ListNode *p;
	if( pos >= list->length ) error("위치 오류");
	p = get_node_at(list, pos);
	return p->data;
}
//
void clear(ListType *list)
{
	int i;
	for(i=0;i<list->length;i++)
		delete_node(list, i);
}
// 버퍼의 내용을 출력한다. 
void display(ListType *list)
{
	int i;
	ListNode *node=list->head;
	printf("( ");
	for(i=0;i<list->length;i++){
		printf("%d ",node->data);
		node = node->link;
	}
	printf(" )\n");
}
// 데이터 값이 s인 노드를 찾는다.
int is_in_list(ListType *list, element item) 
{ 
	ListNode *p; 
	p = list->head; 	// 헤드 포인터에서부터 시작한다.
	while( (p != NULL) ){
		// 노드의 데이터가 item이면
		if( p->data == item ) 
			break;
		p = p->link; 
	}
	if( p == NULL) return FALSE;
	else return TRUE; 
}
//
int main()
{
	ListType list1;

	init(&list1);
	add(&list1, 0, 20);
	add_last(&list1, 30);
	add_first(&list1, 10);
	add_last(&list1, 40);

	// list1 = (10, 20, 30, 40)
	display(&list1);

	// list1 = (10, 20, 30)
	delete(&list1, 3);
	display(&list1);

	// list1 = (20, 30)
	delete(&list1, 0);
	display(&list1);

	printf("%s\n", is_in_list(&list1, 20)==TRUE ? "성공": "실패");
	printf("%d\n", get_entry(&list1, 0));

	return 0;
}

※ 출처 - 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년

• 헤더 노드가 head와 tail 포인터를 동시에 가지고 있다

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

typedef struct ListNode {
	int coef;
	int expon;
	struct ListNode *link;
} ListNode;

typedef struct ListHeader {
	int length;
	ListNode *head;
	ListNode *tail;
} ListHeader;

// 초기화 함수
void init(ListHeader *plist)
{
	plist->length = 0;
	plist->head = plist->tail = NULL;
}

// plist는 연결 리스트의 헤더를 가리키는 포인터, coef는 계수, expon는 지수
void insert_node_last(ListHeader *plist, int coef, int expon)
{
	ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
	if( temp == NULL ){
		fprintf(stderr,"메모리 할당 에러\n");
		exit(1);
	}
	temp->coef=coef;
	temp->expon=expon;
	temp->link=NULL;
	if( plist->tail == NULL ){
		plist->head = plist->tail = temp;
	}
	else {
		plist->tail->link = temp;
		plist->tail = temp;
	}
	plist->length++;
}
//
void poly_add(ListHeader *plist1, ListHeader *plist2, ListHeader *plist3 )
{
 ListNode *a = plist1->head;
 ListNode *b = plist2->head;
 int sum;
 while(a && b){
   if( a->expon == b->expon ){
	sum = a->coef + b-> coef;
    if( sum != 0 ) insert_node_last(plist3, sum, a->expon);
	a=a->link; b=b->link; 
   }
   else if( a->expon > b->expon ){
    insert_node_last(plist3, a->coef, a->expon);
	a=a->link;
   }
   else {
	insert_node_last(plist3, b->coef, b->expon);
	b=b->link; 
   }
 }
  // a나 b중의 하나가 먼저 끝나게 되면 남아있는 항들을 모두 
  // 결과 다항식으로 복사
 for( ; a != NULL; a=a->link) 
   insert_node_last(plist3, a->coef, a->expon);
 for( ; b != NULL; b=b->link) 
   insert_node_last(plist3, b->coef, b->expon);
}
//
void poly_print(ListHeader *plist)
{
	ListNode *p=plist->head;
	for(;p;p=p->link){
		printf("%d %d\n", p->coef, p->expon);
	}
}
//
int main()
{
	ListHeader list1, list2, list3;
		
	init(&list1);
	init(&list2);
	init(&list3);


	// 다항식 1을 생성 
	insert_node_last(&list1, 3,12);
	insert_node_last(&list1, 2,8);
	insert_node_last(&list1, 1,0);

	// 다항식 2를 생성 
	insert_node_last(&list2, 8,12);
	insert_node_last(&list2, -3,10);
	insert_node_last(&list2, 10,6);

	// 다항식 3 = 다항식 1 + 다항식 2
	poly_add(&list1, &list2, &list3);
	poly_print(&list3);

	return 0;
}

※ 출처 - 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년

• 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다.
• 단점은 공간을 많이 차지하고 코드가 복잡해진다는 것이다.
• 그럼에도 불구하고 장점이 많기 때문에 널리 쓰인다.
• 헤드 노드(head node)라는 특별한 노드를 추가하는 경우가 많다.
• 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드이다.

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

typedef int element;
typedef struct DlistNode {
	element data;
	struct DlistNode *llink;
	struct DlistNode *rlink;
} DlistNode;

// 이중 연결 리스트를 초기화
void init(DlistNode *phead)
{
	phead->llink = phead;
	phead->rlink = phead;
}

// 이중 연결 리스트의 노드를 출력
void display(DlistNode *phead)
{
	DlistNode *p;
	for (p = phead->rlink; p != phead; p = p->rlink) {
		printf("<--- | %x | %d | %x | ---->\n", p->llink, p->data, p->rlink);
	}
	printf("\n");
}
// 노드 new_node를 노드 before의 오른쪽에 삽입한다.
void dinsert_node(DlistNode *before, DlistNode *new_node)
{
	new_node->llink = before;
	new_node->rlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node;
}
// 노드 removed를 삭제한다.
void dremove_node(DlistNode *phead_node, DlistNode *removed)
{
	if (removed == phead_node) return;
	removed->llink->rlink = removed->rlink;
	removed->rlink->llink = removed->llink;
	free(removed);
}
// 이중 연결 리스트 테스트 프로그램
void main()
{
	DlistNode head_node;
	DlistNode *p[10];
	int i;

	init(&head_node);
	for (i = 0; i<5; i++) {
		p[i] = (DlistNode *)malloc(sizeof(DlistNode));
		p[i]->data = i;
		// 헤드 노드의 오른쪽에 삽입
		dinsert_node(&head_node, p[i]);
	}
	dremove_node(&head_node, p[4]);
	display(&head_node);
}

※ 출처 - 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년

1. 리스트 추상 데이터 타입

 - 리스트(list) 또는 선형 리스트(linear list)는 자료를 정리하는 방법 중의 하나이다.

 - 항목들 간에 순서가 있다.

 - 리스트 ADT

  객체 : n개의 element형으로 구성된 순서 있는 컬렉션

[ 연산 ]

•  add_last(list, item) : 맨 끝에 요소를 추가한다.
•  add_first(list, item) : 맨 앞에 요소를 추가한다.
•  add(list, pos, item) : pos 위치에 요소를 추가한다.
•  delete(list, pos) : pos 위치의 요소를 제거한다.
•  clear(list) : 리스트의 모든 요소를 제거한다.
•  replace(list, pos, item) : pos 위치의 요소를 item으로 바꾼다.
•  is_in_list(list, item) : item이 리스트 안에 있는지를 검사한다.
•  get_entry(list, pos) : pos 위치의 요소를 반환한다.
•  get_length(list) : 리스트의 길이를 구한다.
•  is_empty(list)
•  is_full(list)
•  display(list)

2. 배열로 구현된 리스트

 - 삽입과 삭제 시에 상당한 오버헤드가 따른다.

#define MAX_LIST_SIZE 100 // 배열의 최대크기

typedef int element;
typedef struct {
	int list[MAX_LIST_SIZE];	  // 배열 정의
	int length;		  // 현재 배열에 저장된 자료들의 개수
} ArrayListType;

// 오류 처리 함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// 리스트 초기화
void init(ArrayListType *L)
{
	L->length = 0;
}
// 리스트가 비어 있으면 1을 반환
// 그렇지 않으면 0을 반환
int is_empty(ArrayListType *L)
{
	return L->length == 0;
}
// 리스트가 가득 차 있으면 1을 반환
// 그렇지 많으면 1을 반환
int is_full(ArrayListType *L)
{
	return L->length == MAX_LIST_SIZE;
}
// 리스트 출력
void display(ArrayListType *L)
{
	int i;
	for (i = 0; i<L->length; i++)
		printf("%d\n", L->list[i]);
}
// position: 삽입하고자 하는 위치
// item: 삽입하고자 하는 자료
void add(ArrayListType *L, int position, element item)
{
	if (!is_full(L) && (position >= 0) &&
		(position <= L->length)) {
		int i;
		for (i = (L->length - 1); i >= position; i--)
			L->list[i + 1] = L->list[i];
		L->list[position] = item;
		L->length++;
	}
}
// position: 삭제하고자 하는 위치
// 반환값: 삭제되는 자료
// position: 삭제하고자 하는 위치
// 반환값: 삭제되는 자료
element del(ArrayListType *L, int position)
{
	int i;
	element item;

	if (position < 0 || position >= L->length)
		error("위치 오류");
	item = L->list[position];
	for (i = position; i<(L->length - 1); i++)
		L->list[i] = L->list[i + 1];
	L->length--;
	return item;
}
//
void main()
{
	ArrayListType list1;
	ArrayListType *plist;

	// ListType를 정적으로 생성하고 ListType를 가리키는
	// 포인터를 함수의 파라미터로 전달한다.
	init(&list1);
	add(&list1, 0, 10);
	add(&list1, 0, 20);
	add(&list1, 0, 30);
	display(&list1);

	// ListType를 동적으로 생성하고 ListType를 가리키는 
	// 포인터를 함수의 파라미터로 전달한다.
	plist = (ArrayListType *)malloc(sizeof(ArrayListType));
	init(plist);
	add(plist, 0, 10);
	add(plist, 0, 20);
	add(plist, 0, 30);
	display(plist);
	free(plist);
}

3. 연결 리스트

 - 배열의 단점은 크기가 고정된다는 것이다. 그리고 삽입/삭제 시 기존의 데이터들을 이동하여야 한다.

 - 연결된 표현(linked representation)은 다른 여러 가지의 동적 자료구조, 즉 스택, 큐, 트리, 그래프등을 구현하는 데 널리 쓰인다.

 1) 단순 연결 리스트(Singly linked list)

  - 첫 번째 노드를 가리키는 하나의 포인터만 있으면 충분한다.

  - 보통 이 포인터는 헤드 포인터(head pointer)라고 불린다.

  (1) 삽입 연산

   - head가 NULL인 경우 : head값을 변경

   - p(선행노드 포인터)가 NULL인 경우 : 리스트의 맨 앞에 삽입

   - head와 p가 NULL이 아닌 경우 : p 뒤에 삽입

// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드 
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
	if (*phead == NULL) {	// 공백리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) { // p가 NULL이면 첫번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else {			 // p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}

  (2) 삭제 연산

   - p가 NULL인 경우 : 첫 번째 노드를 삭제

   - p가 NULL이 아닌 경우

// phead : 헤드 포인터에 대한 포인터 
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드 
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}

  (3) 그 외 몇 가지 함수

   - concat, reverse

ListNode *concat(ListNode *head1, ListNode *head2)
{
	ListNode *p;
	if( head1 == NULL ) return head2;
	else if( head2 == NULL ) return head1;
	else {
		p = head1;
		while( p->link != NULL )
			p = p->link;
		p->link = head2;
		return head1;
	}
}

ListNode *reverse(ListNode *head)
{
   // 순회 포인터로 p, q, r을 사용
   ListNode *p, *q, *r;
   p = head;         // p는 역순으로 만들 리스트
   q = NULL;         // q는 역순으로 만들 노드
   while (p != NULL){
       r = q;          // r은 역순으로 된 리스트.    r은 q, q는 p를 차례로 따라간다.
       q = p;
       p = p->link;
       q->link =r;      // q의 링크 방향을 바꾼다.
    }
    return q; 	// q는 역순으로 된 리스트의 헤드 포인터
}

[ 전체 테스트 프로그램 ]

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

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

// phead: 리스트의 헤드 포인터의 포인터
// p : 선행 노드
// new_node : 삽입될 노드 
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
	if (*phead == NULL) {	// 공백리스트인 경우
		new_node->link = NULL;
		*phead = new_node;
	}
	else if (p == NULL) { // p가 NULL이면 첫번째 노드로 삽입
		new_node->link = *phead;
		*phead = new_node;
	}
	else {			 // p 다음에 삽입
		new_node->link = p->link;
		p->link = new_node;
	}
}
// phead : 헤드 포인터에 대한 포인터 
// p: 삭제될 노드의 선행 노드
// removed: 삭제될 노드 
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
	if (p == NULL)
		*phead = (*phead)->link;
	else
		p->link = removed->link;
	free(removed);
}
void display(ListNode *head)
{
	ListNode *p = head;
	while (p != NULL) {
		printf("%d->", p->data);
		p = p->link;
	}
	printf("\n");
}
void display_recur(ListNode *head)
{
	ListNode *p = head;
	if (p != NULL) {
		printf("%d->", p->data);
		display_recur(p->link);
	}
}
ListNode *search(ListNode *head, int x)
{
	ListNode *p;
	p = head;
	while (p != NULL) {
		if (p->data == x) return p;  // 탐색 성공
		p = p->link;
	}
	return p;  // 탐색 실패일 경우 NULL 반환
}
// 으로 변경
ListNode *concat(ListNode *head1, ListNode *head2)
{
	ListNode *p;
	if (head1 == NULL) return head2;
	else if (head2 == NULL) return head1;
	else {
		p = head1;
		while (p->link != NULL)
			p = p->link;
		p->link = head2;
		return head1;
	}
}
// 로 변환
ListNode *reverse(ListNode *head)
{
	// 순회 포인터로 p, q, r을 사용
	ListNode *p, *q, *r;
	p = head;         // p는 역순으로 만들 리스트
	q = NULL;         // q는 역순으로 만들 노드
	while (p != NULL) {
		r = q;          // r은 역순으로 된 리스트.    r은 q, q는 p를 차례로 따라간다.
		q = p;
		p = p->link;
		q->link = r;      // q의 링크 방향을 바꾼다.
	}
	return q; 	// q는 역순으로 된 리스트의 헤드 포인터
}

// 노드를 동적으로 생성하는 프로그램
ListNode *create_node(element data, ListNode *link)
{
	ListNode *new_node;
	new_node = (ListNode *)malloc(sizeof(ListNode));
	if (new_node == NULL) {
		fprintf(stderr, "메모리 할당 에러\n");
		exit(1);
	}
	new_node->data = data;
	new_node->link = link;
	return new_node;
}
// 테스트 프로그램
void main()
{
	ListNode *list1 = NULL, *list2 = NULL;
	ListNode *p;

	// list1 = 30->20->10
	insert_node(&list1, NULL, create_node(10, NULL));
	insert_node(&list1, NULL, create_node(20, NULL));
	insert_node(&list1, NULL, create_node(30, NULL));
	display_recur(list1);

	// list1 = 20->10
	remove_node(&list1, NULL, list1);
	display(list1);

	// list2 = 80->70->60 
	insert_node(&list2, NULL, create_node(60, NULL));
	insert_node(&list2, NULL, create_node(70, NULL));
	insert_node(&list2, NULL, create_node(80, NULL));
	display(list2);

	// list1 = list1 + list2
	list1 = concat(list1, list2);
	display(list1);

	// list1을 역순으로 
	list1 = reverse(list1);
	display(list1);

	// list1에서 20 탐색
	p = search(list1, 20);
	printf("탐색성공: %d\n", p->data);

}

※ 출처 - 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년