Лекция 13 - Едносвързан Списък и Сортиране

А клас - сортиране

#include <stdio.h>

int main() {
  int arr[] = {3,2,6,1,5,4};
  for(int i=0; i < 6; i++) {
    printf("i=%d arr[i]=%d\n", i, arr[i]);

    for(int j=i+1; j < 6; j++) {
      printf("\tj=%d arr[j]=%d\n", j, arr[j]);
      printf("\t\t%d > %d ? %d\n", arr[i], arr[j], arr[i] > arr[j]);

      if(arr[i] > arr[j]) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
      }
    }
  }

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

  return 0;
}

А клас

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

struct node_t {
  int val;
  struct node_t* next;
};

struct list_t {
  //struct node_t* first;
  struct node_t* head;
  int size;
};

// For readability
void
insert(struct list_t* list, int val)
{
  //struct node_t new_node = {val, NULL};
  struct node_t* new_node = malloc(sizeof(struct node_t));
  new_node->val = val;
  new_node->next = NULL;

  struct node_t* curr = list->head;
  if(curr == NULL) {
    list->head = new_node;
    list->size = 1;
    return;
  }

  while(curr->next != NULL) {
    curr = curr->next;
  }

  curr->next = new_node;
  list->size++;
}

void print_list(struct list_t* list) {
  struct node_t* curr = list->head;

  /*while(curr != NULL) {
    printf("%d\n", curr->val);
    curr = curr->next;
  }*/

 for(int i=0; i < list->size; i++) {
 printf("%p %d\n", curr, curr->val);
    curr = curr->next;
  }
  printf("== Reached the end! ==\n");
}

void remove_by_index(struct list_t* list, int index) {
  if(index > list->size - 1) {
 printf("== Invalid index! ==\n");  
   return;
  }

  if(index == 0) {
struct node_t* to_remove=list->head;
    list->head = to_remove->next;
    free(to_remove);
    list->size--;
    return;
  }

  struct node_t* curr = list->head;
  for(int i=0; i < index - 1; i++) {
    curr = curr->next;
  }
//  curr->next = curr->next->next;
struct node_t* to_remove=curr->next;
  curr->next = to_remove->next;
  free(to_remove);
  list->size--;
}

struct node_t* get(struct list_t* list, int val) {
  int count = 0;
  struct node_t* node = list->head;
  while(count < list->size) {
    if(node->val == val) {
      return node;
    }
    node = node->next;
    count++;
  }
  return NULL;
}

void remove_by_value(struct list_t* list, int val) {
  struct node_t* curr = list->head;

  while(curr->next != NULL) {
    if(curr->next->val == val) {
struct node_t* to_remove=curr->next;
      curr->next = to_remove->next;
      free(to_remove);
      list->size--;
    }
    curr = curr->next;
  }
}

void sort(struct list_t* list) {
  struct node_t* curr = list->head;
  while(curr->next != NULL) {
  struct node_t* inner = curr->next;
    while(inner != NULL) {
      if(curr->val > inner->val) {
        int tmp = curr->val;
        curr->val = inner->val;
        inner->val = tmp;
      }
      inner = inner->next;
    }
    curr = curr->next;
  }
}

int main() {
  struct list_t list1 = {NULL, 0};
  /*struct node_t n1 = {15, NULL};

  list1.head = &n1;
  list1.size++;

  struct node_t n2 = {25, NULL};
  list1.head -> next = &n2;
  list1.size++;

  struct node_t n3 = {35, NULL};
  list1.head -> next -> next = &n3;
  list1.size++;*/
  insert(&list1, 25);
  insert(&list1, 15);
  insert(&list1, 45);
  insert(&list1, 35);
  insert(&list1, 35);

  print_list(&list1);

/*struct node_t* found=get(&list1,65);
  printf("%p\n", found);
  found=get(&list1,35);
  printf("%p\n", found);*/

  sort(&list1);
  print_list(&list1);

  //remove_by_index(&list1, 2);
  //remove_by_value(&list1, 35);
  //print_list(&list1);

  //remove_by_index(&list1, 0);
  //print_list(&list1);

  //remove_by_index(&list1, 6);
  //print_list(&list1);
  return 0;
}

Б клас

В клас

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

struct node_t {
    int value;
    struct node_t* next;
};

struct node_t* init(int value) {
    struct node_t* new_node = malloc(sizeof(struct node_t));
    new_node -> next = NULL;
    new_node -> value = value;

    return new_node;
}

void insert(struct node_t* node, int value) {
    struct node_t* new_node = init(value);
    node -> next = new_node;
}

void print(struct node_t* head) {
    struct node_t* curr = head;

    while(curr != NULL) {
        printf("[%p] %d (%p)\n", curr, curr -> value, curr -> next);
        curr = curr -> next;
    }
}

void insert_middle(struct node_t* prev, int value) {
    struct node_t* new_node = init(value);
    new_node -> next = prev -> next;
    prev -> next = new_node;
}

void remove_middle(struct node_t* prev) {
    struct node_t* middle = prev -> next;
    struct node_t* next = middle -> next;

    middle -> next = NULL;
    prev -> next = next;

    free(middle);
}

struct node_t* sort(struct node_t* head) {
  if(head == NULL) return head;
  if(head -> next == NULL) return head;

  struct node_t* first = head;
  struct node_t* first_prev = NULL;
  while(first -> next != NULL) {
    printf("first: [%p] %d (%p)\n", first, first -> value, first -> next);

    struct node_t* second = first -> next;
    struct node_t* second_prev = first;
    while(second != NULL) {
      printf("\tsecond: [%p] %d (%p)\n", second, second -> value, second -> next);
      printf("\t\t%d > %d ? %d\n", first -> value, second -> value, first -> value > second -> value);

      if(first -> value > second -> value) {
        struct node_t* second_next = second -> next;   
        struct node_t* first_next = first -> next;

        // Just a print block
        if(first_prev!=NULL) {
          printf("\t\t\tfirst_prev:  [%p] %d (%p)\n", first_prev, first_prev -> value, first_prev -> next);
        } else {
          printf("\t\t\tfirst_prev:  %p\n", NULL);
        }
        printf("\t\t\tfirst:       [%p] %d (%p)\n", first, first -> value, first -> next);
        printf("\t\t\tfirst_next:  [%p] %d (%p)\n", first_next, first_next -> value, first_next -> next);
        printf("\t\t\tsecond_prev: [%p] %d (%p)\n", second_prev, second_prev -> value, second_prev -> next);
        printf("\t\t\tsecond:      [%p] %d (%p)\n", second, second -> value, second -> next);
        if(second_next != NULL) {
          printf("\t\t\tsecond_next: [%p] %d (%p)\n", second_next, second_next -> value, second_next -> next);
        } else {
          printf("\t\t\tsecond_next: %p\n", NULL);
        }
        // Just a print block

        first -> next = second_next;
        if(first != second_prev) {
          // Elements have another element between them.
          second_prev -> next = first;
          second -> next = first_next;
        } else {
          // Elements are adjacent.
          second -> next = first;
        }

        if(first_prev) first_prev -> next = second;
        // When swapping the first element point head to the new first.
        if(head == first) head = second;

        first = second;
        second = first -> next;
      }

      second_prev = second;
      second = second -> next;
    }

    first_prev = first;
    first = first -> next;
  }
  return head;
}

int main() {
    struct node_t* n1 = init(15);
    //struct node_t* n2 = malloc(sizeof(struct node_t));
    //	struct node_t* n3 = malloc(sizeof(struct node_t));

    //	n1->value = 15;
    //n2->value = 25;
    //	n3->value = 35;

    //n1->next = n2;
    //	n2->next = n3;
    insert(n1, 45);
    insert(n1->next, 5);


    insert_middle(n1, 35);
    insert_middle(n1, 35);
    insert_middle(n1, 95);
    insert_middle(n1, 55);

    //	printf("%d %d %d\n", n1->value, n2->value, n3->value);
    //	printf("%p %p %p\n", n1->next, n2->next, n3->next);

    //printf("%d %d %d\n", n1->value, n1->next->value, n1->next->next->value);
    //printf("%p %p %p\n", n1->next, n1->next->next, n1->next->next->next);

    print(n1);
    printf("Sort the list:\n");    
    n1 = sort(n1);
    printf("Sorted:\n");
    print(n1);

    free(n1->next->next);
    free(n1->next);
    free(n1);

    return 0;
}