link list-資料的依值插入

typedef struct node {
   int val;
   struct node *next;
}node;

node *head = NULL;
// insert value "val" into link list
void insert_value(int val)
{
   node *prev, *rush;
   // create node for that insertor
   node *data = (node*) malloc(sizeof(node));
   // put the value in that node
   data->val = val;

   prev = rush = head;
   // find out the correct position for val
   while (rush != NULL && val > rush->val) {
      prev = rush;
      rush = rush->next;
   }

   // link it next to the bigger value
   data->next = rush;
   // if there is no element in link list
   // or val is the smallest
   if (rush == head)
      head = data;
   else
      prev->next = data;

}

// show link list elements
void show_list(void)
{
   node *rush = head;
   printf("\nThe result is:\n");
   while (rush != NULL) {
      printf("%d ", rush->val);
      rush = rush->next;
   }
   puts("");


}
int main()
{
   int n;
   printf("Enter values:\n");
   while(scanf("%d", &n) != EOF) {
      printf("%d ", n);
      insert_value(n);
   }
   show_list();
   return 0;

}

關於include的部分請依自己的compiler把該include的東西放進去。

依值插入顧名思義就是依據值的大小而插入適當的位置，因此不管目前插入的值是什麼，整個list都會是由小排到大(又或是由大排到小)。

所以這個function邏輯是
1. 找到相等又或是比插入值還大的node
2. 把插入值的node next 接在1.前面
3. 把比插入值還小的node接在插入值前面，如果是NULL node又或是插入值是最小的，那麼插入值它就會是head

因此指標prev和rush就是在step 1中為了找出比插入值還小的prev的node，以及該接在插入值後面的rush

   while (rush != NULL && val > rush->val) {
      prev = rush;
      rush = rush->next;
   }

在這個while迴圈中，不斷的比較插入值和現有在list中node的大小。當現有的node還不到尾端的時候，且目前還沒找到該插入的位置的時候，在list中的node就會往後移，直到rush這個指標比插入值還大或相等，那麼理所當然的prev就是比插入值還小。

從while迴圈跳出來會有兩種情形 ａ.list是空的 ｂ.list非空的且有找到插入值該有的位置，因此以ｂ.來說，我們依循以上function的邏輯2. 我們就會把插入值的next往後接rush：

   // link it next to the bigger value
   data->next = rush;

但如果是情形ａ呢？這也沒問題，因為即使是空的，我們一開始initialize head是NULL的，而link list的尾端總是NULL的，所以目前的rush也會是NULL的。所以把插入值的尾端這樣接是不會有問題的。

所以邏輯3.：

   if (rush == head)
      head = data;
   else
      prev->next = data;

就會和描述一模一樣，如果插入值該放第一個又或是這個list是空的，那麼沒有一個node該接他前面，所以head就會assign給他。如果不是的話，那麼前面那個prev就會是比她還小的值，應當接在插入值的前方。