이 날은 아이디어 생각하고 수강신청 도와주려다가 밤을 새는 바람에....많이 졸아서 필기가 영 부족하다 ㅠㅠ..
그래서 대신 강사님의 소스 파일을 공유하고자 합니다.
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'알고리즘 > 자료구조/알고리즘' 카테고리의 다른 글
| [집중단기 마지막날] 자료구조 - 재귀호출, 정렬 (0) | 2014.02.14 |
|---|---|
| [집중단기 4일차] 자료구조 (0) | 2014.02.13 |
| [집중단기 3일차] 자료구조 - Stack, 비트연산, Dynamic Array (0) | 2014.02.12 |
| [집중단기 1일차] C언어 (0) | 2014.02.10 |
