'자료구조' 태그의 글 목록 (2 Page)

트리(1)

C/C자료구조 : 2007. 11. 9. 09:55

트리 - 계층적 구조.

한개 이상의 노드로 이루어진 유한 집합

노드 - 트리의 구성요소중 하나

류트 - 부모노드

서브트리 - 자식노드

간선 - 루트와 서브트리를 연결한 선

조상노드 - 루트에서 임의의 노드까지의 경로

단말노드 - 자식이 없는 노드(leap node) != 비단말 노드

노드의 차수 - 어떤 노드가 가진 자식노드의 개수

트리의 차수 - 트리가 가진 노드의 차수 중 가장 큰 차수

레벨 - 트리의 각 층에 번호를 매기는 것

트리의 높이 - 트리가 가진 최대 레벨

포리스트 - 트리의 집합

이진트리

- 모든 노드가 2개의 서브 트리를 갖는 트리

- 서브트리는 서로 공집합일수 있다.

* 공집합 : 원소를 하나도 갖지 않는 집합, 공집합은 모든 집합의 부분집합이다.

- 최대 2개의 자식노드를 가지수 있다.

- 모든 노드의 차수가 2 이하이다.

- 공집합도 이진트리이다.

- 서브트리간에 순서가 존재한다.

- 왼쪽 서브트리와 오른쪽 서브트리는 서로 구별된다.

* 이진트리의 정의 : 공집합이거나, 루트와 왼쪽, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의한다.

이진 트리의 서브 트리들은 모두 이진트리여야 한다.

이진트리의 성질

- n개의 노드를 가진 이진트리는 n-1개의 간선을 갖는다.

- 높이가 h인 트리의 전체 노드의 개수는 (2^h) -1이 된다.

- 레벨당 최소 하나의 노드는 있어야 하기 때문에 높이(h)가 노드의 개수(n)를 넘을 수 없다.

1) 포화이진트리 : 각 레벨의 노드가 꽉 찬 상태

각 노드에 번호를 붙일 수 있다.

레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙인다.

2) 완전이진트리 : 마지막 레벨에서 노드가 꽉 차있지 않아도 되지만 중간에 빈곳이 있어선 안된다.

3) 기타이진트리 : 그 외

이진 트리의 표현

1) 배열 표현 : 배열의 0번지 요소는 사용되지 않는다. 저장공간의 낭비가 심할수 있다.

노드 i 의 부모 노드 인덱스 i/2

노드 i 의 왼쪽 자식노드 인덱스 2i

노드 i 의 오른쪽 자식노드 인덱스 2i+1

2) 링크 표현 : 노드가 구조체로 표현되고 각 노드가 포인터를 가지고 있어서 표인터를 이용해 노드끼리 연결.

* 링크법으로 생성된 이진 트리

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

typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;

void main()
{
TreeNode *n1, *n2, *n3;

n1 = (TreeNode *)malloc(sizeof(TreeNode));
n2 = (TreeNode *)malloc(sizeof(TreeNode));
n3 = (TreeNode *)malloc(sizeof(TreeNode));

n1->data = 10;
n1->left = n2;
n1->right = n3;

n2->data = 20;
n2->left = NULL;
n2->right = NULL;

n3->data = 30;
n3->left = NULL;
n3->right = NULL;
}

Posted by 청웨일

Trackback() : Comment ()

덱 deque

C/C자료구조 : 2007. 11. 9. 09:54

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

#define TRUE 1
#define FALSE 0

typedef int element;

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

typedef struct DequeType {
DlistNode *head;
DlistNode *tail;
} DequeType;

//오류처리
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}

//초기화
void init(DequeType *dq)
{
dq->head = dq->tail = NULL;
}

//생성
DlistNode *cnode(DlistNode *llink, element item, DlistNode *rlink)
{
DlistNode *node = (DlistNode *)malloc(sizeof(DlistNode));

if(node == NULL) error("메모리 할당 오류");
node->llink = llink;
node->data = item;
node->rlink = rlink;
return node;
}

//공백검출

int is_empty(DequeType *dq)
{
if(dq->head == NULL) return TRUE;
else return FALSE;
}

//삽입
void add_rear(DequeType *dq, element item) //전단 삽입
{
DlistNode *new_node = cnode(dq->tail, item, NULL);

if(is_empty(dq)) dq->head = new_node;
else
dq->tail->rlink = new_node;
dq->tail = new_node;
}

void add_front(DequeType *dq, element item) //후단 삽입
{
DlistNode *new_node = cnode(NULL, item, dq->head);

if(is_empty(dq)) dq->tail = new_node;
else
dq->head->llink = new_node;
dq->head = new_node;
}

//삭제

element del_front(DequeType *dq) //전단 삭제
{
element item;
DlistNode *removed_node;

if(is_empty(dq)) error("공백 덱에서 삭제");

else {
removed_node = dq->head;
item = removed_node->data;
dq->head = dq->head->rlink;
free(removed_node);

if(dq->head == NULL) dq->tail = NULL;
else dq->head->llink = NULL;
}
return item;
}

element del_rear(DequeType *dq) //후단 삭제
{
element item;
DlistNode *removed_node;

if(is_empty(dq)) error("공백 덱에서 삭제");

else {
removed_node = dq->tail;
item = removed_node->data;
dq->tail = dq->tail->llink;
free(removed_node);

if(dq->tail == NULL) dq->head = NULL;
else dq->tail->rlink = NULL;
}
return item;
}

//출력

void display(DequeType *dq)
{
DlistNode *p;
printf("(");

for(p=dq->head; p!=NULL; p=p->rlink) {
printf(" %d ", p->data);
}
printf(")\n");
}

//메인

void main()
{
DequeType deque;

init(&deque);

add_front(&deque, 10); //전위 삽입
add_front(&deque, 20); //전위 삽입
add_rear(&deque, 30); //후위 삽입

display(&deque);

del_front(&deque); //전위 삭제
del_rear(&deque); //후위 삭제

display(&deque);
}

Posted by 청웨일

Trackback() : Comment ()

연결리스트 큐

C/C자료구조 : 2007. 11. 9. 09:50

-배열로 구현된 큐에 비해 크기가 제한되지 않지만

코드가 더 복잡해지고 링크필드때문에 메모리 공간을 더 많이 사용한다.

- 기본적인 구조는 단순 연결 리스트에 2개의 포인터를 추가한 것과 같다.

- front - 연결리스트의 맨앞으로 삭제와 관련된다.

- rear - 연결리스트의 맨 뒤로 삽입과 관련된다.

- 공백의 경우 front와 rear는 NULL값.

- 큐의 각 요소는 (데이터+링크)로 이루어진 구조체로 정의된다.

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

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

typedef struct {
QueueNode *front, *rear; //큐노드를 가리킬 수 있는 front와 rear 포인터
} QueueType;

//에러처리

void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}

//초기화

void init(QueueType *q)
{
q->front = q->rear =0;
}

//공백상태 검출
int is_empty(QueueType *q)
{
return (q->front == NULL);
}
//포화상태 검출
int is_full(QueueType *q)
{
return 0;
}

//삽입함수
void enqueue(QueueType *q, element item)
{
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
if(temp == NULL) error("메모리를 할당 할 수 없습니다.");
else {
temp->item = item;
temp->link = NULL;
if(is_empty(q)) {
q->front = temp;
q->rear = temp;
}
else {
q->rear->link = temp;
q->rear = temp;
}
}
}

//삭제

element dequeue(QueueType *q)
{
QueueNode *temp = q->front; //아리송...
element item;

if(is_empty(q)) error("큐가 비어있습니다.");
else {
item = temp->item;
q->front = q->front->link;

if(q->front == NULL) q->rear = NULL;
free(temp);
return item;
}
}

//peek

element peek(QueueType *q)
{
element item;
if(is_empty(q)) error("큐가 비어있습니다.");
else {
item = q->front->item;
return item;
}
}

//main

void main()
{
QueueType q;

init(&q); //초기화

enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);

printf("dequeue() = %d\n", dequeue(&q));
printf("dequeue() = %d\n", dequeue(&q));
printf("dequeue() = %d\n", dequeue(&q));
}

Posted by 청웨일

Trackback() : Comment ()

스택 stack

C/C자료구조 : 2007. 11. 9. 09:42

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

#define MAX_STACK_SIZE 100

typedef int element;
element stack[MAX_STACK_SIZE];
int top = -1;

int is_empty()
{
return (top == -1);
}
int is_full()
{
return (top == (MAX_STACK_SIZE-1));
}

//삽입함수
void push(element item)
{
if(is_full()) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else stack[++top] = item;
}

//삭제함수
element pop()
{
if(is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top--];
}

//피크 함수
element peek()
{
if(is_empty()) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return stack[top];
}

void main()
{
push(1);
push(2);
push(3);
printf("%d\n", pop());
printf("%d\n", pop());
printf("%d\n", pop());
printf("\n");
printf("%d\n", is_empty());
}

Posted by 청웨일

Trackback() : Comment ()

단순 연결 리스트

C/C자료구조 : 2007. 11. 9. 09:42

* 동적 메모리 할당

new_node = (ListNode *)malloc(sizeof(ListNode));

new_node는 ListNode형식을 가리킬수 있는 포인터로서

ListNode의 size만큼의 공간을 malloc할당 받는다.

p.128_프로그램 4.12 전체 테스트 프로그램

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

typedef int element;

//구조체

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

//삽입함수

void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
if(*phead==NULL) {
new_node->link = NULL;
*phead = new_node;
}
else if(p==NULL) {
new_node->link = *phead;
*phead = new_node;
}
else {
new_node->link = p->link;
p->link = new_node;
}
}

//삭제함수

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");
}

//노드탐색

ListNode *search(ListNode *head, int x)
//찾을 리스트, 숫자
{
ListNode *p;
p=head;
while(p!=NULL) {
if(p->data == x) return p;
p=p->link;
}
return p;
}

//노드생성

ListNode *create_node(element data, ListNode *link)
{
ListNode *new_node;
new_node = (ListNode *)malloc(sizeof(ListNode));
if(new_node == NULL) printf("메모리 할당 에러");
new_node->data = data;
new_node->link = link;

return (new_node);
}

main()
{
ListNode *list1 = NULL, *list2 = NULL;
ListNode *p;

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(list1); //출력

remove_node(&list1, NULL, list1); //노드 삭제
display(list1); //출력

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