[집중단기 2일차] 자료구조 - 포인터

이 날은 아이디어 생각하고 수강신청 도와주려다가 밤을 새는 바람에....많이 졸아서 필기가 영 부족하다 ㅠㅠ..

그래서 대신 강사님의 소스 파일을 공유하고자 합니다.

---

1일차에 이어서 동일하게 프로젝트를 생성합니다.

프로젝트명 : 20140211

1일차 복습하고 시작합니다.

파일명 : 1.c

파일명 : 2.c

// void 포인터
#include <stdio.h>

void swap(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}

void swap(int *a, int *b) {
	short t = *a;
	*a = *b;
	*b = t;
}

void swap(int *a, int *b) {
	char t = *a;
	*a = *b;
	*b = t;
}

void main() {
	int a = 30, b = 1000;
	swap(&a, &b);
	printf("a = %d, b = %d\n", a, b);
}

c언어에서는 동일한 이름의 함수이름들을 전부 swap이 _swap으로 바뀐다.

그래서 swap_xx함수 이름을 바꿔준다. -> swap_int

a

// void 포인터
#include <stdio.h>

void swap_int(int *a, int *b) {
	int t = *a;
	*a = *b;
	*b = t;
}

void main() {
	int a = 30, b = 1000;
	swap(&a, &b);
	printf("a = %d, b = %d\n", a, b);
}

전처리 기능은 문자열을 단순히 치환만 하기 때문에 .....

// void 포인터
#include <stdio.h>

#define SWAP(x,y,T) do { 
T t = a; 
a - b; 
b= t; 
} while(0)

void main() {
	int a = 30, b = 1000;
	//swap(&a, &b);
	SWAP(a, b, int);
	printf("a = %d, b = %d\n", a, b);
}

하나의 함수를 여러 타입을 핸들링하고 싶은 것의 문제이다..!

함수가 어떤 타입이 되든지 간에 모두 SWAP을 하려면 중간에 있는 임시 변수를 char로 한 바이트를 주고

아래 소스 코드는 타임에 의존적이지 않는 generic swap을 만든것이다.

#include <stdio.h>

/*#define SWAP(x,y,T) do { 
T t = a; 
a - b; 
b= t; 
} while(0) */
void swap(void *a, char *b, int size) {
	char t;
	char *aa = (char*)a;
	char (bb = (char*)b;
	int i;

	for(i=0;i




파일명 : 3.c














파일명  : 4.c

알아둡시다!!

구조체와 포인터

구조체 포인터 연산자: (*)., / ->

// 자기 참조 구조체 : 자기 자신의 타입에 대한 포인터

파일명 : 5.c

메모리를 보통 노드라고 한다.

리스트 자료구조 : 데이터를 저장하기 위한 메모리 -> 노드(node)

본인의 마지막 노드를 터미널이라고 한다. 종료 노드와 시작 노드를 구분하기 위해서 마지막 노드에 null을 넣어 놓는다.

끝을 tail이라고 한다.

리스트 자료구조 구현 방법은 여러개 있다.

파일명 : 6.c

한 방향으로 연결된 노드의 경우!

만약 3000개가 연결되었다.. 근데 찾고자하는게 마지막에 있다면??? 최악이지 않은가...

그래서 배울게 바로!! reverse() - PPT 13p : 기존의 display()는 head부터 시작한다. 따라서 tail부터 시작하는 reverse용 display를 따로 만들어야 된다.

void reverse(NODE *head, NODE *tail){
	NODE *prev = head;
	NODE *curr = head->next;
	NODE *next;

	while(cur != tail) {
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}

	curr->next = prev;
}

a

문제점이 있다면, 어떤게 reverse로 보고 어떤것을 reverse_display로 봐야 할지 모른다. 근데 별 쓸모없는 기능이다.

그리고 이 함수는 역방향(reverse)에 대한 순방향 복원이 안된다. 오버헤드가 크다!!

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

typedef struct __NODE
{
	int data;
	struct __NODE *next;
	struct __NODE *prev;	//double linked list!
} NODE;

void init_list(NODE *head)
{
	head->next = head;
	head->prev = head;
}

//PPT 17p
void insert_front(NODE *head, NODE *node)
{
	node->next = head->next;
	head->next = node;

	node->prev = node->next->prev;
	node->next->prev = node;
}

void insert_end(NODE *head, NODE *node)
{
	NODE *cur = head;

	while(cur->next != head)
		cur = cur->next;

	node->next = cur->next;
	cur->next = node;
}

void reverse(NODE *head)
{
	NODE *prev = head;
	NODE *curr = head->next;
	NODE *next;

	while(curr != head)
	{
		next = curr->next;
		curr->next = prev;
		prev = curr;
		curr = next;
	}

	curr->next = prev;
}

void display(NODE *head)
{
	NODE *node;

	system("cls");
	printf("\n[head]->");
	for(node = head->next; node != head; node = node->next)
		printf("[%d]->", node->data);
	printf("[head]");
	getchar();
}



void main()
{
	int i;

	NODE head;

	NODE arr[5];

	init_list(&head);

	display(&head);
	for(i = 0; i < 5; i++)
	{
		arr[i].data = i+1;
		//insert_front(&head, &arr[i]);
		insert_end(&head, &arr[i]);
		display(&head);
	}

	reverse(&head);
	display(&head);

	reverse(&head);
	display(&head);
}

// 역방향에 대한 순방향 복원이 안된다!

양방향 노드를 이용하면 라이브러리의 최고 동력을 살릴 수 있지만, 메모리는 2배 희생이 필요하다.

이 양방향 노드를 더블 링크라고 한다.

---

1.c

2.c

3.c

4.c

5.c

6.c