C언어 10강 | Structures and list processing | 제일 중요함 ***

매우 중요함

linear linked list

stack

queue

binary tree

structures and list processing

self referential structures

자기 자신을 가리키는 포인터 변수를 멤버로 갖는 구조체

struct list {
	int data;
    struct list *next;
};

struct list a, b, c;
a.data = 1;
b.data = 2;
c.data = 3;

a.next = &b;
b.next = &c;
c.next = NULL;

printf("%d\n%d\n", a.next->data, a.next->next->data);

 

 

linear linked lists

배열은 배열인데, struct가 일렬로 연결된 리스트(꼬리잡기)

 

#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();
}

example : store n e w

** 주의 **

포인터 변수에 대해서는 (만약에 구조체를 포인터로 접근하였다면) 무조건 malloc(sizeof(type)) 해줘야한다는 것 기억하기

(#include <stdlib.h>까지~!)

#include <stdio.h>

struct cha {
    char character;
    struct cha *next;
};
typedef struct cha cha;

int main(void){
    cha a, b, c;
    a.character = 'n';
    b.character = 'e';
    c.character = 'w';
	
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    cha *tmp = &a;

    while ((tmp)!=NULL){
        printf("%c\n", tmp->character);
        tmp = tmp->next;
    }
}

 

linear list operations

 

list creation using iteration

("abcde" string을 linked list로 변환하는 함수)

LINK s_to_l(char s[]){
    LINK head = NULL, tail;
    int i;

    if (s[0]!='\0'){
        head = malloc(sizeof(ELEMENT));
        head->d=s[0];
        tail=head;
        for (i=1;s[i]!='\0';++i){
            tail->next=malloc(sizeof(ELEMENT));
            tail = tail->next;
            tail->d=s[i];
        }
        tail->next=NULL;
    }
    return head;
}

 

list creation using recursion

LINK string_to_list(char s[]){
    LINK head;
    if (s[0]=='\0'){
        return NULL;
    }
    else {
        head = malloc(sizeof(ELEMENT));
        head->d = s[0];
        head->next=string_to_list(s+1);
        return head;
    }
}

 

counting the elements

int count_it(LINK head){
    int cnt = 0;
    for (;head!=NULL;head=head->next){
        ++cnt;
    }
    return cnt;
}

 

- recursive version - 

int count(LINK head){
    if (head==NULL){
        return 0;
    }
    else {
        return (1+count(head->next));
    }
}

 

concatenate list a and b with a as head

void concatenate(LINK a, LINK b){
    assert(a!=NULL);
    if (a->next == NULL){
        a->next = b;
    }
    else {
        concatenate(a->next, b);
        
    }
}

 

insertion

recursive functions for list processing

insert an element

void insert(LINK p1, LINK p2, LINK q){
    assert(p1->next==p2);
    p1->next=q;
    q->next=p2;
}

 

delete an element

delete a list

void delete(LINK p){
    p->next = p->next->next;
}
void delete_list(LINK head){
    if (head!=NULL){
        delete_list(head->next);
        free(head);
    }
}

 

stacks

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

void push (int);
int pop ();
void print_s ();

typedef struct node{
    int data;
    struct node* next;
}stack;


stack *top = NULL;

int
main (){

  printf("-------- PUSH --------\n");
  push(1);
  push(2);
  push(3);
  push(4);
  push(5);

  print_s();

  printf("-------- POP --------\n");
  pop();
  pop();

  print_s();

}

void
push (int data){

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

    if(new_node == NULL){
        printf("stack is full!");
        exit(1);
    }

    new_node -> data = data;
    new_node -> next = top;
    top = new_node;
}

int
pop (){
    stack *del;
    int value;

    if(top == NULL){
        printf("stack is empty!");
        exit(1);
    }

    value = top -> data;
    del = top;
    top = top -> next;
    free(del);

    return value;
}

void
print_s (){
    stack *i ;
    stack *count = top;

    i = count;

    while(i != NULL){
        if(i->next == NULL)
            printf("%d\n",i->data);
        else
            printf("%d --> ",i->data);

        i = count -> next;
        count = count -> next;
    }
}

stack.h

#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);

 

stack operations

initialize

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

push

void push(data d, stack *stk){
    elem *p;
    p=malloc(sizeof(elem));
    p->d=d;
    p->next=stk->top;
    stk->top=p;
    stk->cnt++;
}

pop

data pop(stack *stk){
    data d1;
    elem *p;
    d1=stk->top->d;
    p=stk->top;
    stk->top=stk->top->next;
    stk->cnt--;
    free(p);
    return d1;
}

top

data top(stack *stk){
    return stk->top->d;
}

empty / full

boolean empty(const stack *stk){
    return ((boolean)(stk->cnt==EMPTY));
}

boolean full(const stack *stk){
    return ((boolean)(stk->cnt==FULL));
}

main

#include "stack.h"
int main(void){
    char str[] = "My name is Jonna Kelly!";
    int i;
    stack s;
    initialize(&s);
    printf("In the string:%s\n", str);
    for (i=0;str[i]!='\0';++i){
        if (!full(&s)){
            push(str[i], &s);
        }
    }
    printf("From the stack : ");
    while (!empty(&s)){
        putchar(pop(&s));
    }
    putchar('\n');
    return 0;
}

 

 

polish notation and stack evaluation

polish notation

연산자를 피연산자 뒤에 쓰는 연산 표기법

수식을 계산할 때 수식을 앞에서부터 읽으면서 스택에 저장하면 된다. 

우선순위가 분명하다. 

 

(17+5)*2-20을 stack을 이용한 polish notation으로 계산하면, 

17 5 + 2 * 20 -로 표기할 수 있다. 

#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

선입선출

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

void add (int); int delete(); void Print();

typedef struct node{
    int data;
    struct node *next;
}queue;

queue *rear = NULL;
queue *front = NULL;

int
main () {
    printf("----- ADD -----\n");
    add(1);
    add(2);
    add(3);
    add(4);
    add(5);

    Print();

    printf("----- DELETE -----\n");

    delete();
    delete();
    delete();

    Print();

}

void
add (int data) {
    queue *new_node = (queue*)malloc(sizeof(queue));

    new_node -> data = data;
    new_node -> next = NULL;

    if(rear == NULL && front == NULL){
         front = new_node;
         rear = new_node;
         return;
    }

    rear -> next = new_node;
    rear = new_node;

};

int
delete (){
    int re;
    queue * del = (queue*)malloc(sizeof(queue));

    if(front == NULL && rear == NULL){
        printf("queue is empty!!\n");
        exit(1);
    }
    del = front;
    front = front -> next;
    re = del ->data;
    free(del);

    return re;
}

void Print() {
    queue * temp = front;
    while(temp != NULL){
        if( temp == rear){
            printf("%d",temp->data);
        }
        else{
            printf("%d --> ", temp->data);
        }
        temp = temp ->next;
    }
        printf("\n");


}

스택은 push pop

큐는 FIFO

 

세부 함수로는

3페이지 분량이다

 

#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

/*
 * C Program to Implement Binary Tree using Linked List
 */
#include <stdio.h>
#include <malloc.h>
 
struct node {
    struct node * left;
    char data;
    struct node * right;
};
 
struct node *constructTree( int );
void inorder(struct node *);
 
char array[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' };
int leftcount[ ] = {  1,   3,   5,   -1,   9,  -1,  -1,   -1,   -1,  -1 };
int rightcount[ ] = {  2,   4,   6,   -1,  -1,  -1,  -1,   -1,   -1,  -1 };
 
void main() {
    struct node *root;
    root = constructTree( 0 );
    printf("In-order Traversal: \n");
    inorder(root);
}
 
struct node * constructTree( int index ) {
    struct node *temp = NULL;
    if (index != -1) {
        temp = (struct node *)malloc( sizeof ( struct node ) );
        temp->left = constructTree( leftcount[index] );
        temp->data = array[index];
        temp->right = constructTree( rightcount[index] );
    }
    return temp;
}
 
void inorder( struct node *root ) {
    if (root != NULL) {
        inorder(root->left);
        printf("%c\t", root->data);
        inorder(root->right);
    }
}

이진 트리

parent에서 child으로 뻗어나가는 구조

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

root, leaf, left / right subtree, parent, child

 

create a linked binary tree

binary tree traversal

inordertraversal

preorder traversal

postorder traversal

#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;
}