자료구조 연결 리스트 함수들 정리

자료구조에서 리스트는 매우 중요한 자리에 있는 것 같다.

Singly linked List를 응용하면, Doubly linked List나 tree 또는 graph 등을 구현할 때도 도움이 될 수 있기 때문이다.

 

아래는 Singly linked List의 예제이며, 아직 구현되지 않은 부분도 있다.

 

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

// #define newFunc

typedef struct Node {
    char data[128];
    struct Node *next;
} Node;



Node* swap(Node* ptr1, Node* ptr2) { 
    Node* tmp = ptr2->next; 
    ptr2->next = ptr1; 
    ptr1->next = tmp; 
    return ptr2; 
} 
  
int bubbleSort(Node** head) { 

    Node** h; 
    int i, j, swapped; 
    
    int cnt = 0;
    for(Node **p = head; *p; p = &(*p)->next) { //count number of nodes
        count++;
    }

    for (i = 0; i <= count; i++) { 
  
        h = head; 
        swapped = 0; 
  
        for (j = 0; j < count - i - 1; j++) { 
  
            Node* p1 = *h; 
            Node* p2 = p1->next; 
  
            if ( strcmp(p1->data, p2->data) > 0 ) {
  
                *h = swap(p1, p2); 
                swapped = 1; 
            } 
  
            h = &(*h)->next; 
        } 
  
        if (swapped == 0) 
            break; 
    } 
} 

Node *selection_sort(Node* head) {
    
    Node* temp = head; 
    Node* min; 
    Node* p;
    
    char tmp_str[128];
  
    while( temp ) { /* Traverse the List */
        min = temp; 
        p = temp->next; 
        
        while( p ) { /* Traverse the unsorted sublist */
            if ( strcmp(min->data, p->data) > 0 )
                min = p; 
  
            p = p->next; 
        } 
        
        strcpy(tmp_str, temp->data); /* Swap Data */
        strcpy(temp->data, min->data); 
        strcpy(min->data, tmp_str); 
        
        temp = temp->next; 
    }
    
    return head;
} 

Node *append(Node *head, char num[ ]) {    Node *p, *tmp;
    
    Node *n=(Node *)malloc(sizeof(Node));

    if( n == NULL) {
        printf("Error creating a new node.\n");
        exit(0);
    }

    strcpy(n->data, num);
    
    if(head==NULL) { n->next=head; head = n; return head;}
    
    for(p=head; p!=NULL; p=p->next)
        tmp=p;
        
    p=tmp;
    n->next=p->next;
    p->next=n;
    
    return head;
}

Node *push(Node *head, char *myword) {

Node *stone=(Node *) malloc(sizeof(Node));
strcpy(stone->data, myword);

stone->next=head;
head = stone;

return head;
}

#ifdef newFunc   // 아직 정리되지 못한 부분

Node *insertN(Node *head, int LOC, int num) {
   Node *p; int i; //Nodc *tmp;
   
   Node *n=(Node *)malloc(sizeof(Node));
   n->data=num;
   
   if(head==NULL || LOC==1) { n->next=head; head = n; return head; }
   
   for(p=head, i=1; p!=NULL && i<LOC-1; p=p->next, i++)
       ; //tmp=p;
       
   n->next=p->next;
   p->next=n;
   
   return head;
}

Node *deleteN(Node *head, int LOC) { int i;
   Node *p, *tmp;
   
   if(LOC==1) { tmp=head; head = head->next; free(tmp); return head; }
   
   for(p=head, i=1; p!=NULL && i < LOC; p=p->next, i++)
       tmp=p;
       
   tmp->next=p->next;
   free(p);
   
   return head;
}
#endif

Node *reverse(Node *head) { Node *p, *head2 = NULL;
   
   Node *tmp, *stone;
   
   for(p=head; p!=NULL; p=tmp) {
       tmp  =p->next;
       stone=p;
       
       stone->next=head2;
       head2=stone;
   }
   
   return head2;
}


Node *clear(Node *head) { Node *p, *tmp;

   for(p=head;p!=NULL;p=tmp) {
       tmp=p->next;
       free(p);
   }

   return (head = NULL);
}


Node *search(Node *head, char *find ) { Node *p; Node *sav;

   for( p = head ; p != NULL ; p = p->next) {
       if(strcmp(find, p->data) == 0 )  return p;
       sav = p;
   }

   return NULL;      
}

int print(Node *head ) { Node *p;

   for( p = head ; p != NULL ; p = p->next) {
       puts(p->data);
   }

   return 0;      
}

int main() {  Node *head = NULL;

    head = push(head, "cars");
    head = push(head, "trains");
    head = push(head, "airplanes");
    head = push(head, "ships");

    head = append(head, "hello");
    head = append(head, "tigers");
    head = append(head, "lions");
    head = append(head, "eagles");

    head = append(head, "flowers");
    head = append(head, "trees");
    print(head);

    //head = selection_sort(head);
    bubbleSort(&head);

    puts("\n***** after sort *****");
    print(head);

    head = reverse(head);
    puts("\n***** after reverse *****");
    print(head);
    
    head = clear(head);

    return 0;
}

 

실행 결과는 아래의 그림과 같다.