[c언어] 자료구조, sort 등

190617(6일차-end) - 자료구조, sort

 

교육을 받으면서 노트필기 했던 내용을 날것 그대로 업로드합니다.

 

cf. link(http://soen.kr/)

---

 

자료구조 list

 

1.list - 싱글, 서큘러, 더블, 커널-DL

1-1. sort(버블, 선택, insert->indirect insert->shell, Qsort merge, 직접기수(버킷)

2.stack - compiler

3.queue - deque

4.tree - DL, array(heap:priority Q)

4-4. (tree sort, BST(70%) , )

5. graph(최소비용, 최단거리 -> A-star:PQ)

(DFS, BFS)

 

 

---

#퀵소트를 사용해서 정렬하기

#include <stdio.h>

#include <stdlib.h>

 

void printInt(int* arr, int size);

void printDbl(double* arr, int size);

void printstr(double(*arr)[10], int size);

 

int comp_i(const void* a, const void* b) {

    return (*(int*)a - *(int*)b);

}

 

//라이브러리 제공하는 qsort를 위한 comp_d 함수 완성

int comp_d(const void* a, const void* b) {

    if ((*(double*)a - *(double*)b) == 0)

        return 0;

    else if ((*(double*)a - *(double*)b) > 0)

        return 1;

    else

        return -1;

 

}

 

//라이브러리 제공하는 qsort를 위한 comp_s 함수 완성

int comp_s(const void* a, const void* b) {

    return strcmp((char*)a, (char*)b);

 

 

}

 

 

 

 

int main(void) {

    int arri[] = { 3,4,1,5,2,8,9,6,10,7 };

    double arrd[] = { 3.2, 5.6, 4.3, 8.7, 2.3, 4.5, 2.1, 2.3, 4.6, 4.5 };

    char arrs[][7] = { 개인정보 보호를위해 실명 문자열 목록 삭제 };

    qsort(arri, sizeof(arri) / sizeof(arri[0]), sizeof(int), comp_i);

    printInt(arri, sizeof(arri) / sizeof(arri[0]));

 

    qsort(arrd, sizeof(arrd) / sizeof(arrd[0]), sizeof(double), comp_d);

    printDbl(arrd, sizeof(arrd) / sizeof(arrd[0]));

 

    //라이브러리 qsort를 이용하여 2차원배열에 있는 문자열을 정렬합시다.

 

    qsort(arrs, sizeof(arrs) / sizeof(arrs[0]), sizeof(arrs[0]), comp_s);

    printstr(arrs, sizeof(arrs) / sizeof(arrs[0]));

 

    return 0;

}

void printInt(int* arr, int size) {

    int dx = 0;

    for (dx = 0; dx < size; ++dx) {

        printf("%d ", arr[dx]);

    }

    printf("\n");

}

 

void printDbl(double* arr, int size) {

    int dx = 0;

    for (dx = 0; dx < size; ++dx) {

        printf("%.1f ", arr[dx]);

    }

    printf("\n");

}

 

void printstr(char(*arr)[7], int size) {

    int dx = 0;

    for (dx = 0; dx < size; ++dx) {

        printf("%s ", arr[dx]);

    }

    printf("\n");

}

 

---

#퀵소트를 사용해서 구조체배열을 정렬하기.

#include<stdio.h>

#include<string.h>

#pragma warning (disable:4996)

typedef struct _sales

{

    char itemname[20];

    int unitprice;

    int count;

    int amount;

}Sales;

int prd_item(const void *a, const void *b)

{

    return strcmp(((Sales*)a)->itemname, ((Sales*)b)->itemname);

//    return strcmp(((Sales*)a)->itemname, ((Sales*)b)->itemname);

}

main()

{

    Sales prd[5] = {

     { "ccc", 10,90,900 },

    { "aaa", 20,80,1600 },

    { "ddd", 30,70,2100 },

    { "eee", 40,60,2400 },

    { "bbb", 50,50,2500 }

    };

    int dx;

 

    qsort(prd, 5, sizeof(prd[0]), prd_item);

 

 

    for (dx = 0; dx < 5; dx++)

        printf("%s %d %d %d\n", prd[dx].itemname,

            prd[dx].unitprice, prd[dx].count, prd[dx].amount);

 

 

}

 

 

---

 

 

#include <stdio.h>

#include <stdlib.h>

 

 

 

#pragma warning (disable:4996)

 

//다음 구조체포인터 배열을 라이브러리 qsort를 상용하여 name의 오름차순으로 정렬하시오

typedef struct _node node;

struct _node {

    char name[10];

    struct _node *next;

};

//int gg = 0;

int cmp_node(const void *a, const void *b)

{

    printf("[%s] [%s] = %d\n", (*(node**)a)->name, (*(node**)b)->name, strcmp((*(node**)a)->name, (*(node**)b)->name));

    return strcmp((*(node**)a)->name, (*(node**)b)->name);

// return strcmp((*(node**)a)->name, (*(node**)b)->name);

}

node *p, *q;

main()

{

    node *k[4];

 

    p = (node*)malloc(sizeof(node));

    strcpy(p->name, "ccc");

    p->next = NULL;

    q = (node*)malloc(sizeof(node));

    strcpy(q->name, "aaa");

    q->next = NULL;

 

 

    k[0] = p;

    k[1] = q;

    k[2] = (node*)malloc(sizeof(node));

    strcpy(k[2]->name, "bbb");

    qsort(k, 3, sizeof(node*), cmp_node);

 

    puts("\n-----");

    printf("%s\n", k[0]->name);

    printf("%s\n", k[1]->name);

    printf("%s\n", k[2]->name);

 

}

 

---

 

- stack

- LIFO

- 후위 표기법을 사용한 계산.

• 연산자 우선순위가 현재 보다 높은 연산자 삽입시 그냥 삽입.
• ex) 342*+ 가 스택에 있을 경우.
• 3,4,2
• 3,8
• 11 (최종값)
• ex) (7+8)*2
• 왼쪽 괄호는 무조건 스택에 삽입함.
• 오른쪽 괄호가 나오면 왼쪽괄호가 나올 때 까지 계산함.
• 78+2*
• 스택을 사용하는 예

1. 컴파일러가 중위를 후위로 바꾼다.
   - 왼쪽 괄호는 무조건 push
   - 피연산자는 출력(콘솔,배열에 출력)
   - 연산자는 스택에 push(센놈은 밀고 들어간다.(크거나 같은 놈은 빼고들어감))
2. 후위를 계산식 으로
   - 피연산자는 스택에 push
   - 연산자를 만나면 첫번째 pop한것이 오른쪽
                     두번째 pop한것이 왼쪽에 두고 계산한다 (첫번째 +|-|/|* 두번째)

 

#define STACK_SIZE 5

int stack[STACK_SIZE];

int top;

 

void init_stack(void) {

    top = -1; // 값 넣을시 하나 증가후 넣어야하게 설계해보자.

}

void push(int data) {

    if (top >= STACK_SIZE - 1) {

        puts("stack overflow");

        return;

    }

    stack[++top] = data;

}

int pop() {

    if (top == -1) {

        puts("stack empty");

        return -1;

    }

    return stack[top--];

}

 

//main()

main() {

    init_stack();

    push(3);

    push(4);

    push(1);

    push(5);

    printf("%d\n", pop());

    printf("%d\n", pop());

    printf("%d\n", pop());

    printf("%d\n", pop());

}

 

 

- queue

- 스택과 유사.

- 버퍼링으로 많이 쓰인다.

- FIFO