연습 문제 #1 | 간단한 알고리즘(bubble sort, selection sort, merge sort), 간단한 자료구조(queue, linked list, stack, binary tree)

bubble sort

int bubbleSort(int a[], int n){
    for (int i =0;i<n;i++){
        for (int j = i;j<n;j++){
            if (a[i]>a[j]){
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
    for (int i=0;i<n;i++){
        printf("%d\n", a[i]);
    }
    return 0;
}

selection sort

int selectionSort(int a[], int n){

    for (int i=0;i<n;i++){
        int tmp = a[i];
        for (int j=i;j<n;j++){
            if (a[j]<a[i]){
                tmp = a[j];
            }
        }
        a[i] = tmp;
    }

    for (int i=0;i<n;i++){
        printf("%d\n", a[i]);
    }
    return 0;
}

merge sort

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

void merge(int a[], int b[], int c[], int m, int n);
void mergeSort(int key[], int n);
void wrt(int key[], int sz);

void merge(int a[], int b[], int c[], int m, int n){
    int i=0, j=0, k=0;
    while (i<m&&j<n){
        if (a[i]<b[j]){
            c[k++]=a[i++];
        }
        else{
            c[k++]=b[j++];
        }
    }
    while (i<m) c[k++]=a[i++];
    while (j<n) c[k++]=b[j++];
}

void mergeSort(int key[], int n){
    int j, k, m, *w;
    for (m=1;m<n;m*=2);
    if (n<m) exit(1);
    w=calloc(n, sizeof(int));
    assert(w!=NULL);
    for (k=1;k<n;k*=2){
        for (j=0;j<n-k;j+=2*k){
            merge(key+j, key+j+k, w+j, k, k);
        }
        for (j=0;j<n;++j) key[j] = w[j];
    }
    free(w);
}

void main(void){
    int sz;
    int key[] = {4,3,1,67,55,8,0,4,-5,37, 7,42,9,1,-1};
    sz=sizeof(key)/sizeof(int);
    printf("\nBefore : ");
    wrt(key, sz);
    mergeSort(key, sz);
    printf("\nAfter");
    wrt(key, sz);
}

void wrt(int key[], int sz){
    for (int i=0;i<sz;i++){
        printf("%d ", *(key+i));
    }
    printf("\n");
}

linear linked lists

- struct

- print

- insert

- delete

- empty

- count

- concat 

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

struct node {
   int data;
   int key;
   struct node *next;
};

struct node *head = NULL;
struct node *current = NULL;

//display the list
void printList() {
   struct node *ptr = head;
   printf("\n[ ");
	
   //start from the beginning
   while(ptr != NULL) {
      printf("(%d,%d) ",ptr->key,ptr->data);
      ptr = ptr->next;
   }
	
   printf(" ]");
}

//insert link at the first location
void insertFirst(int key, int data) {
   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
	
   link->key = key;
   link->data = data;
	
   //point it to old first node
   link->next = head;
	
   //point first to new first node
   head = link;
}

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //mark next to first link as first 
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

//is list empty
bool isEmpty() {
   return head == NULL;
}

int length() {
   int length = 0;
   struct node *current;
	
   for(current = head; current != NULL; current = current->next) {
      length++;
   }
	
   return length;
}

//find a link with given key
struct node* find(int key) {

   //start from the first link
   struct node* current = head;

   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {
	
      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {
         //go to next link
         current = current->next;
      }
   }      
	
   //if data found, return the current Link
   return current;
}

//delete a link with given key
struct node* delete(int key) {

   //start from the first link
   struct node* current = head;
   struct node* previous = NULL;
	
   //if list is empty
   if(head == NULL) {
      return NULL;
   }

   //navigate through list
   while(current->key != key) {

      //if it is last node
      if(current->next == NULL) {
         return NULL;
      } else {
         //store reference to current link
         previous = current;
         //move to next link
         current = current->next;
      }
   }

   //found a match, update the link
   if(current == head) {
      //change first to point to next link
      head = head->next;
   } else {
      //bypass the current link
      previous->next = current->next;
   }    
	
   return current;
}

void sort() {

   int i, j, k, tempKey, tempData;
   struct node *current;
   struct node *next;
	
   int size = length();
   k = size ;
	
   for ( i = 0 ; i < size - 1 ; i++, k-- ) {
      current = head;
      next = head->next;
		
      for ( j = 1 ; j < k ; j++ ) {   

         if ( current->data > next->data ) {
            tempData = current->data;
            current->data = next->data;
            next->data = tempData;

            tempKey = current->key;
            current->key = next->key;
            next->key = tempKey;
         }
			
         current = current->next;
         next = next->next;
      }
   }   
}

void reverse(struct node** head_ref) {
   struct node* prev   = NULL;
   struct node* current = *head_ref;
   struct node* next;
	
   while (current != NULL) {
      next  = current->next;
      current->next = prev;   
      prev = current;
      current = next;
   }
	
   *head_ref = prev;
}

void main() {
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56); 

   printf("Original List: "); 
	
   //print list
   printList();

   while(!isEmpty()) {            
      struct node *temp = deleteFirst();
      printf("\nDeleted value:");
      printf("(%d,%d) ",temp->key,temp->data);
   }  
	
   printf("\nList after deleting all items: ");
   printList();
   insertFirst(1,10);
   insertFirst(2,20);
   insertFirst(3,30);
   insertFirst(4,1);
   insertFirst(5,40);
   insertFirst(6,56);
   
   printf("\nRestored List: ");
   printList();
   printf("\n");  

   struct node *foundLink = find(4);
	
   if(foundLink != NULL) {
      printf("Element found: ");
      printf("(%d,%d) ",foundLink->key,foundLink->data);
      printf("\n");  
   } else {
      printf("Element not found.");
   }

   delete(4);
   printf("List after deleting an item: ");
   printList();
   printf("\n");
   foundLink = find(4);
	
   if(foundLink != NULL) {
      printf("Element found: ");
      printf("(%d,%d) ",foundLink->key,foundLink->data);
      printf("\n");
   } else {
      printf("Element not found.");
   }
	
   printf("\n");
   sort();
	
   printf("List after sorting the data: ");
   printList();
	
   reverse(&head);
   printf("\nList after reversing the data: ");
   printList();
}

stack

- struct

- init

- push

- pop

- print

- empty

- full

#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define FULL 10000

typedef char data;
typedef enum {false, true} boolean;
struct elem{
    data d;
    struct elem *next;
};
typedef struct elem elem;
struct stack {
    int cnt;
    elem *top;
};
typedef struct stack stack;

void initialize(stack *stk);
void push(data d, stack *stk);
data pop(stack *stk);
data top(stack *stk);
boolean empty(const stack *stk);
boolean full(const stack *stk);

polish notation and stack evaluation

- evaluate

- fill

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define FULL 10000

struct data {
    int data;
    enum {operator, value} kind;
    union {
        char op;
        int val;
    } u;
}; typedef struct data data;

struct elm {
    data d;
    struct elm *next;
}; typedef struct elm elm;

typedef enum {false, true} boolean;

struct stack {
    int cnt;
    elm *top;
}; typedef struct stack stack;

void initialize(stack *stk);
void push(data d, stack *stk);
data pop(stack *stk);
boolean empty(const stack *stk);
boolean full(const stack *stk);

int evaluate(stack *polish);
void fill(stack *stk, const char *str);

int main(void){
    char s[] = "17, 5, +, 2, *, 20, -";
    stack polish;
    fill(&polish, s);
    printf("%d\n", evaluate(&polish));
    return 0;
}

void initialize(stack *stk){
    stk->cnt = 0;
    stk->top=NULL;
}

void push(data d, stack *stk){
    elm *t = (elm*)malloc(sizeof(elm));
    t->d = d;
    t->next = stk->top;

    stk->top = t;
    stk->cnt++;
}

data pop(stack *stk){
    elm *t = (elm*)malloc(sizeof(elm));
    t = stk->top;
    data top = stk->top->d;
    stk->top=stk->top->next;
    stk->cnt--;
    free(t);
    return top;
}

boolean empty(const stack *stk){
    return (stk->cnt==EMPTY) ? true : false; 
}
boolean full(const stack *stk){
    return (stk->cnt==FULL) ? true : false; 
}

int evaluate(stack *polish){
    data d, d1, d2;
    stack eval;
    initialize(&eval);

    while (!empty(polish)){
        d = pop(polish);
        switch(d.kind){
            case value: push(d, &eval); break;
            case operator:
                d2 = pop(&eval);
                d1 = pop(&eval);
                switch(d.u.op){
                    case '+': 
                        d.u.val=d1.u.val+d2.u.val;
                        break;
                    case '-':
                        d.u.val = d1.u.val-d2.u.val;
                        break;
                    case '*':
                        d.u.val = d1.u.val*d2.u.val;
                }
                d.kind = value;
                push(d, &eval);
        }
        
    }
    d = pop(&eval);
    return d.u.val;
}

void fill(stack *stk, const char *str){
    const char *p = str;
    boolean b1, b2;
    data d;
    stack tmp;
    char c1, c2;

    initialize(stk);
    initialize(&tmp);

    while (*p!='\0'){
        while (isspace(*p)||*p==',') ++p;
        b1=(boolean)((c1=*p)=='+'||c1=='-'||c1=='*');
        b2=(boolean)((c2=*(p+1))==','||c2=='\0');
        if (b1&&b2){
            d.kind = operator;
            d.u.op = c1;
        }
        else {
            d.kind = value;
            sscanf(p, "%d", &d.u.val);
        }
        if (!full(&tmp)) push(d, &tmp);
        while (*p!=','&&*p!='\0') ++p;
    }

    while (!empty(&tmp)){
        d = pop(&tmp);
        if (!full(stk)) push(d, stk);
    }

}

 

queue

- init

- enqueue

- dequeue

- empty

- full

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define EMPTY 0
#define FULL 10000
typedef unsigned int data;
typedef enum {false, true} boolean;

struct elem {
    data d;
    struct elem *next;
}; typedef struct elem elem;

struct queue {
    int cnt;
    elem *front;
    elem *rear;
}; typedef struct queue queue;

void initialize(queue *q);
void enqueue(data d, queue *q);
data dequeue(queue *q);
data front(const queue *q);
boolean empty(const queue *q);
boolean full(const queue *q);

int main(void){

    queue q;
    initialize(&q);
    data d;
    d = 1;
    enqueue(1, &q);
    enqueue(2, &q);
    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));
    return 0;
}

void initialize(queue *q){
    q->cnt = 0;
    q->front = NULL;
    q->rear = NULL;
}
void enqueue(data d, queue *q){
    elem *new = malloc(sizeof(elem));
    new->d = d;
    new->next = NULL;

    if (empty(q)==true){
        q->front = new;
        q->rear = new;
    }
    else {
    q->rear->next = new;
    q->rear = new;
    }
    q->cnt++;
}

data dequeue(queue *q){
    elem *new = (elem*)malloc(sizeof(elem));
    new = q->front;
    data d = new->d;
    q->front = q->front->next;
    free(new);
    return d;
}
data front(const queue *q){
    return q->front->d;
}
boolean empty(const queue *q){
    return ((q->cnt==EMPTY)?true:false);
}
boolean full(const queue *q){
    return ((q->cnt==FULL)?true:false);
}

 

binary tree

- struct

- init

- create

- inorder / preorder / postorder

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

typedef char DATA;

struct node {
    DATA d;
    struct node *left;
    struct node *right;
};

typedef struct node NODE;
typedef NODE *BTREE;

BTREE init_node(DATA d1, BTREE p1, BTREE p2){
    BTREE t;
    t=malloc(sizeof(NODE));
    t->d=d1;
    t->left=p1;
    t->right=p2;
    return t;
}

BTREE create_t(DATA a[], int i, int size){
    if (i>=size){
        return NULL;
    }
    else {
        return (init_node(a[i], create_t(a, 2*i+1, size), create_t(a, 2*i+2, size)));
    
    }
}

void inorder(BTREE root){
    if (root!=NULL){
        inorder(root->left);
        printf("%c\n", root->d);
        inorder(root->right);
    }
}

void preorder(BTREE root){
    if (root!=NULL){
        printf("%c\n", root->d);
        preorder(root->left);
        preorder(root->right);
    }
}

void postorder(BTREE root){
    if (root!=NULL){
        postorder(root->left);
        postorder(root->right);
        printf("%c\n", root->d);
    }
}

int main(void){
    BTREE bt;
    bt = init_node(1, bt, bt);
    DATA a[] = {'a','b','c','d','e','f','g'};
    bt = create_t(a,1,7);

    inorder(bt);
    printf("\n\n");
    preorder(bt);
    printf("\n\n");
    postorder(bt);
    printf("\n\n");        
    return 0;
}