데이터 구조 복습 총화

데이터 구조 복습 총화
선형 표
A. 순서 표
데이터 구조 설계

typedef struct
{
    DATATYPE buf[MAX];
    int n;
}SEQLIST;

1. 요소 삽입 (seq)

seq->buf[seq->n] = data;

2. 위치 에 따라 삽입 (seq, post, data)

mov_n = seq->n + 1 - post + 1

for(i = seq->n; mov_n > 0; i --,mov_n --)
{
    seq->buf[i+1] = seq->buf[i]
}

seq->buf[post-1] = data;

3. 지정 한 요소 삭제 (seq, key)

for(i = 0,j = 0;i <= seq->n ;i ++)
{
    if(seq->buf[i]  != key)
        seq->buf[j++] = seq->buf[i];
}

seq->n = j - 1;

B. 링크
데이터 구조의 설계

typedef struct node
{
    DATATYPE data;
    struct node *next;
}LINKLIST;

1. 창설

//a.     (head)
//b.head->next = NULL;
//c.return head;

2. 헤드 삽입 법

struct node *temp;

temp = (struct node *)malloc(sizeof(struct node));
temp->data = data;

temp->next = head->next;
head->next = temp;

3. 꼬리 삽입 법 사상: 링크 의 끝 부분 까지 옮 겨 다 닌 다.

struct node *p = head;

while(p->next != NULL) p = p->next;
p->next = temp;
temp->next = NULL;

/ / 1 4 6 7 4. 순서대로 삽입

struct node *p = head;

while(p->next != NULL && p->next->data < data) p = p->next;
temp->next = p->next;
p->next = temp;

/ / 1, 2, 4, 8, 9, 5. 지정 한 요 소 를 삭제 합 니 다.

struct node *p = head;

while(p->next != NULL && p->next->data != data) p = p->next;

temp = p->next;
p->next = temp->next;
free(temp); 

6. 체인 테이블 역 설정

struct node *p = head;
struct node *q = p ->next;
struct node *current;

current = q->next;
q->next = NULL;

while(current)
{
    p = current->next;
    current->next = head->next;
    head->next = current;
    current = p;
} 

7. 링크 의 옮 겨 다 니 기

struct node * p = head->next;

while(p)
{
    printf("%d ",p->data);
    p = p->next;
}

C. 순서 창고
데이터 구조 설계

typedef struct
{
    DATATYPE buf[MAX];
    int top;//         
}STACK; 

1.

create_empty_stack()
{
    STACK *s;

    s = malloc();
    s->top = -1;
} 

2.

push_stack(STACK *s,DATATYPE data)
{
   // a.  
    //b.s->top ++;
    //s->buf[s->top] = data;
} 

3.
D. 체인 스 택
데이터 구조 설계

DATATYPE pop_stack(STACK *)
{
    //a.    
    data = s->buf[s->top];
    s->top --;

   // b.return data;
} 

1.

struct node
{
    DATATYPE data;
    struct node *next; };

typedef struct
{
    struct node *top;
    int n;
}STACK; 

2.

create_empty_stack()
STACK *s = (STACK *)malloc(sizeof(STACK));
s->top = NULL;
s->n = 0; 

결판 을 내리다

push_stack(STACK *s,DATATYPE data)
{
    struct node *temp;

    temp = malloc();
    temp->data = data;

    temp->next = s->top;
    s->top = temp;
    s->n ++;

    return 0;
} 

3.DATAYPE pop_stack(STACK *s)
{
    struct node *temp;
    DATATYPE data;
    temp = s->top;
    data = temp->data;
    s->top = temp->next;
    free(temp);
    s->n --;
    return data;
}
E. 대열
순환 대기 열 데이터 구조 설계
typedef struct
{
    DATATYPE buf[MAX];
    int front;
    int rear;
}QUEUE;
규정.
팀 비 움: q - > front = = q - > rear;
팀 만 료: (q - > rear + 1)% MAX = = q - > front;
1.create_queue
q = malloc();
q->front = q->rear = 0;
2. 입대
가득 판결 하 다
q->buf[q->rear] = data;
b.
q->rear = (q->rear + 1) % MAX;
3. 출전
판결 하 다
b.
data = q->buf[q->front];
q->front = (q->front + 1) % MAX;
return data;
체인 큐
데이터 구조 설계
struct node
{
    DATATYPE data;
    struct node *next;
}
typedef struct
{
    struct node *front;
    struct node *rear;
}QUEUE;
1.create_empty_queue()
분배 체인 테이블 의 머리
head = (struct node *)malloc(sizeof(struct node));
head->next = NULL;
b. 할당 대기 열의 헤더
q = (QUEUE *)malloc(sizeof(QUEUE));
q->front = q->rear = head;
return q;
2.EnterQueue()
temp = (struct node *)malloc(sizeof(struct node));
temp->data = data;
q->rear->next = temp;
q->rear = temp;
temp->next = NULL;
3.DeleteQueue()
판결 하 다
b.struct node *temp;
  temp = q->front;
  q->front = temp->next;
  free(temp);
  return q->front->data;
비 선형 표
A. 나무 (이 진 트 리)
데이터 구조 설계
typedef struct TreeNode
{
  DATATYPE data;
  struct TreeNode *lchild;
  struct TreeNode *rchild;
}BITREE;
1. 완전 이 진 트 리 만 들 기
BITREE *create_binary_tree(int n)
{
    BITREE *root;
    root = space_node(1);
    push_stack(s,root);
    while(!is_empty_stack(s))
    {
        tree = pop_stack(s);
        if(2 * tree->data <= n)
        {
            tree->lchild = space_node(2 * tree->data);
            push_stack(tree->lchild);
        }
        if(2 * tree->data + 1 <= n)
        {
            tree->rchild = space_node(2 * tree->data + 1);
            push_stack(tree->rchild);
        }
    }
    return root;
}
//n = 1
BITREE *_create_binary_tree(int n)
{
    BITREE *root;
    root = space_node(n);
    if(2 * root->data <= N)
        root->lchid = _create_bianry_tree(2 * root->data);
    if(2 * root->data + 1<= N)
        root->rchid = _create_bianry_tree(2 * root->data + 1);
    return root;
}
2. 이 진 트 리 옮 겨 다 니 기
a. 앞 순서 옮 겨 다 니 기
PreOrder(BITREE *tree)
{
    if(tree == NULL)
        return;
    printf("%d ",tree->data);
    PreOrder(tree->lchild);
    PreOrder(tree->rchild);
}
b. 차원 옮 겨 다 니 기
NoOder(BITREE *tree)
{
    q = create_empty_queue();
    EnterQueue(q,tree);
    while(!is_empty_queue(q))
    {
        tree = DeleteQueue(q);
        printf("%d",tree->data);
        if(tree->lchild != NULL)
        {
            EnterQueue(q,tree->lchild);
        }
        if(tree->rchild != NULL)
        {
            EnterQueue(q,tree->rchild);
        }
    }
}
B. 그림
1. 저장
인접 행렬
typedef struct
{
    vtype v[N];
    int matrix[N][N];
}Graph
b. 링크 테이블
typedef struct node
{
    vtype v;
    struct node *next;
}LINKGRAPH;
2. 옮 겨 다 니 기
깊이
DFS(Graph * G,int v)
{
    visited[v] = 1;
    printf("V%d",v);
    u = FirstAdj(G,v);
    while(u >= 0)
    {
        if(!visited[u])
            DFS(G,u);
        u = NextAdj(G,u,v);
    }
}
b. 넓이
BFS(Graph *G,int v)
{
    visited[v] = 1;
    EnterQueue(G,v);
    while(!is_empty_queue(q))
    {
        v = DelelteQueue(q);
        printf("V%d ",v);
        u = FirstAdj(G,v);
        while(u >= 0)
        {
            if(!visited[u])
            {
                visited[u] = 1;
                EnterQueue(q,u);
            }
            u = NextAdj(G,u,v);
        }
    }
}