Sorting Using Link List With Bubble Sort

一般我們用陣列做bubble sort時，使用兩個變數指向陣列的某個位置，即兩個array index的變數，而使用link list時，則改用struct node指標。

int i, j v.s. struct node*

link list和陣列都是呈現「一串有序資料」的方法，於是可以做出的功能應該是相近的，在撰寫Bubble Sort之前，歸納下列三個所需的功能，並找出兩者的作法：

• 掃描過整串資料
• 陣列

for(i=0 ; i<len ; i++)  arr[i]...

• link list

now = top;
while(now){
 now->data... ;
 now = now->next;
}

• 交換資料(swap)
• 陣列

int t;
t = a[i];
a[i] = a[j];
a[j] = t;

• link list：直接個別交換structure中的elements或是交換node指標
• 指向某項資料與判斷
• 陣列：用int變數當作儲存特定位置的index
• link list：用struct node指標當作儲存特定位置的方法

[範例]

有一份檔案grades.txt，存有一串資料，格式是[名字 分數]，例如：

Heron 99

Apple 89

Nobody 100

我們將這串資料讀到link list之後排序，再把結果印出到sorted_grades.txt。

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

// structure defination
struct node{
 char name[100];
 int grade;
 struct node *next;
};

// a node pointer pointing to the top of linklist
struct node *top;

int main(void){

 // initialize file pointers fin, fout
 FILE *fin = fopen("grades.txt" ,"r");
 FILE *fout = fopen("sorted_grades.txt","w");

 // malloc top node
 top = (struct node *)malloc(sizeof(struct node));

 // define "now" node pointer, and pointer to top
 struct node *now;
 now = top;
 now->next = NULL;

 // define some variables to store new data temporarily
 char new_name[100];
 int new_grade;

 // scan in the data from file and build into linklist
 while(fscanf(fin, "%s%d", new_name, &new_grade)!=EOF){

  // copy the temporary data to linklist node
  strcpy(now->name, new_name);
  now->grade = new_grade;

  // create a new node "new" and store the new data
  struct node *new;
  new = (struct node *)malloc(sizeof(struct node));
  new->next = NULL;

  // let "now->next" point to new
  now->next = new;
  // let "now" point to now->next
  now = now->next;

 }


 // sorting here, using bubble sort

 // define last node pointer "last" pointing to last node
 struct node *last = now; // last node is empty
 
 // while the last pointer doesn't come the top one
 while(last != top){

  now = top;

  // while now pointer doesn't come to the end
  while(now->next != last){

   // if the grade in now is greater than the grade in now->next
   // then swap
   if(now->grade > now->next->grade){

    // swap grade
    int t;
    t = now->grade;
    now->grade = now->next->grade;
    now->next->grade = t;

    // swap name
    char tN[100];
    strcpy(tN, now->name);
    strcpy(now->name, now->next->name);
    strcpy(now->next->name, tN);

   }


   // if now is about to the last
   // then let last point to the previous node
   // something like, "last--", if we use array index
   if(now->next->next == last){
    last = now;
    break;
   }

   // let now point to the next one,
   // things like, "now++", if we use array index
   now = now->next;
  }
 }


 // print out the whole link list
 now = top;
 while(now->next){
  //printf("%s\t%d\n", now->name, now->grade);
  fprintf(fout, "%s\t%d\n", now->name, now->grade);
  now = now->next;
 }
 
 // end
 return 0;
}