## Friday, January 6, 2012

### Sorting Using Link List With Bubble Sort

int i, j v.s. struct node*

• 掃描過整串資料
• 陣列
`for(i=0 ; i<len ; i++)  arr[i]...`
```now = top;
while(now){
now->data... ;
now = now->next;
}```
• 交換資料(swap)
• 陣列
```int t;
t = a[i];
a[i] = a[j];
a[j] = t;```

• 指向某項資料與判斷
• 陣列：用int變數當作儲存特定位置的index
[範例]

Heron 99
Apple 89
Nobody 100

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

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

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

int main(void){

// initialize file pointers fin, fout

// 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];

// scan in the data from file and build into linklist

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

// 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

int 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){