티스토리 뷰

c언어

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

열혈허슬러 상추님 2019.07.01 12:10
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
댓글
댓글쓰기 폼
네이버 이웃추가
«   2019/10   »
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    
글 보관함