Friday, January 6, 2012

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