link list-reverse

// reverse a link list
void reverse_link_list(void)
{
   // we need 3 pointers to keep going
   node *rush, *prev, *now;

   // initialize
   rush = head;
   now = NULL;

   // loop from head to final
   while (rush != NULL) {
      // prev now rush
      prev = now;
      now = rush;
      rush = rush->next;
      // prev<-now rush
      now->next =prev;
   }
   // assign head to now
   head = now;
}

反轉一個link list我們會需要三個指標。因為如果照以前一樣只用兩個指標來做的話：

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

我們會永遠沒辦法往下一個node前進，因為現有的now的next已經往前接了，而該往後的node會因此斷了音訊。所以我們需要一個pointer來保存下一個node的位置。因此rush是用來保存下一個node的位置，而now是現有的node，prev則是前一個node。由於我們要反轉一個link list，所以now的next應當接在prev上。

我們初始化指標使得：　now(NULL) rush(head)

這樣在進入迴圈做這件事情的時候：

      prev = now;
      now = rush;
      rush = rush->next;
      // prev<-now rush
      now->next =prev;

就會讓前頭長成這樣 prev(NULL)<-now(head) rush(next)

這樣子我們就把目前的head接給NULL，也因為我們要反轉的關係，head將來就會成為最後一個節點，而我們知道最後一個節點的next是NULL，因此這樣做是沒問題的，這也是支所以我們把now initialize為NULL的初衷。

與使用兩個指標的方式不同的是，由於我們有保存下一個指標的位址rush，所以我們要往下一個節點邁進的時候，只需要把rush assign給now。然後rush就可以往下一個節點邁進。

接著最後再把head assign給目前的now(而不是rush!因為經過迴圈之後rush已經是NULL了)：

   head = now

大功告成!

link list-清除link list

// free all nodes in the link list
void free_all_nodes(void)
{
   node *rush, *prev;
   // if there is no existing element, jump out
   if (head == NULL) {
      printf("No existing element!\n");
      exit(1);
   }
   // initialize rush as head
   rush = head;
   // free all elements
   while (rush != NULL) {
      prev = rush;
      rush = rush->next;
      free(prev);
   }
}

當我們allocate一個link list的時候，記憶體會騰出空間出來。當然C的程式的default會在程式結束之後把記憶體清空。但是如果你有程式是巨量資料，那麼這list要清空騰出記憶體是無可避免的。

因此要清空一個list的記憶體的方式就是從頭慢慢的一個一個開始清。他不像是一般array使用free就可以清除一整筆資料。由於目前的link list是單向的，所以清除順序勢必是要從head開始清除。

所以首先我們需要先判斷link list裡面究竟有沒有existing的node再來決定要不要清除。因為如果沒有的話便會清除到NULL指標。當然也許程式可能是容許的，但是如果可以養成程式能夠自我預警，那麼日後出現任何問題都能夠容易debug，也能夠有點像是封裝概念一般省去一堆debug的時間。

   if (head == NULL) {
      printf("No existing element!\n");
      exit(1);
   }

這邊就是偵測目前是否有現存資料在內，如果沒有那麼就印出訊息跳出去。當然如果你整支程式還是要繼續執行的話就把exit(1)改成return即可。

接著initialize rush為head之後開始迴圈一個一個開始free掉每個node：

   rush = head;
   // free all elements
   while (rush != NULL) {
      prev = rush;
      rush = rush->next;
      free(prev);
   }

while迴圈就偵測目前是否有到尾了，如果還沒到尾就繼續free掉現有值。直到迴圈結束這支程式也做了該做的事情了。

link list-刪除某值之資料

// delete a node of data val in a link list
void delete_specified_data(int val)
{
   node *rush, *prev;
   rush = head;
   // search for data val
   while (rush != NULL && val != rush->val) {
      prev = rush;
      rush = rush->next;
   }
   // if there is no result
   if (rush == NULL) {
      printf("Data no found!\n");
      exit(1);
   }
   // if that result is the first node,
   // then head will be the next node
   else if (rush == head)
      head = rush->next;
   // else, pull out the node
   else
      prev->next = rush->next;
   free(rush);

}

這個是只刪除某一個值，但是只刪除一個而已，因此如果一個數列23 54 54 34 65 12 在這邊如果刪除54的話，只會刪除第一個54。 所以概念上就是從link list之中從頭開始找，找到符合值為val的就把它刪除，刪除方式就是把他前面的node的next接它後面。接著再free掉它。

   rush = head;
   // search for data val
   while (rush != NULL && val != rush->val) {
      prev = rush;
      rush = rush->next;
   }

首先把探索用的指標rush initialize為head，接著迴圈內就開始找第一個符合我們要找的值的node為止。這時候rush有幾種情形
1. 第一個node就找到了
2. 沒有找到
3. 找到了，但不是1.的情形

while內的條件最好是該有正確的boundary判斷，因此rush != NULL，因為筆者的參考書沒有這一段，所以特別標明這一點。如果這個link list沒有找到我們要找的資料的話，那麼最後rush會跑到NULL上，接著會讀取不存在的記憶體rush = rush->next，這樣是有問題的。

所以當我們找到的是第１.的情形的時候，他會和第三個有所不同。因為第三個情形的處理方式就是該把(我們找到的node)前面那個的next給接到(我們找到的node)的後一個。但如果是第一個情形不會有前面那個node，這時候prev是沒有Initialize的所以一樣會讀取到沒有allocate的記憶體上。

   else if (rush == head)
      head = rush->next;
   // else, pull out the node
   else
      prev->next = rush->next;

所以第一個else if就是判斷第一個情形，這時候因為我們要移掉的是第一個node，處理方式就是重新指定head為後一個node就行了。而第三種情形的處理方式就是把前面那個node往後接給後面那一個node。

至於第二個情形

   if (rush == NULL) {
      printf("Data no found!\n");
      exit(1);
   }

就該把沒找到的訊息印出來並且直接跳出去。筆者的參考書一樣沒這一段，雖然本身無關緊要。因為如果沒有找到的話，那麼我們最後要free()的時候便會free掉什麼都沒有的NULL，這本身是沒什麼問題的。但寫程式概念還是要清楚，畢竟free是用在有memory allocate的情形的。萬一某個部分沒有寫好，比如我們的while如果沒有判斷rush != NULL，這時候會發生什麼事情也不曉得。即使free掉NULL沒什麼要緊的，但寫給自己看也讓自己提醒自己該注意的地方是什麼才是重要的。

link-list 資料插尾插頭

// insert val in head of a link list
void insert_in_head(int val)
{
   // create a node for val
   node *data = (node *) malloc(sizeof(node));
   data->val = val;
   // link head next to data
   data->next = head;
   // new head = data
   head = data;
}

node *tail = NULL;
// insert val in tail of a link list
void insert_in_tail(int val)
{
   // create a node for val
   node *data = (node *) malloc(sizeof(node));
   data->val = val;
   // link NULL to data
   data->next = NULL;

   // if there is no existing node
   if (head == NULL)
      // then this node is head and also tail
      head = tail = data;
   else {
      // otherwise, this node is new tail
      tail->next = data;
      tail = data;
   }
}

資料的插頭，就是把一筆資料直接放入到link list的頭端，如果沒有資料那麼這筆資料就會是新的頭。如果有資料的話那麼目前的頭就會被接在這筆新資料之後。

   data->next = head;
   // new head = data
   head = data;

在create一個node之後我們便把目前的頭接在這筆新資料之後，然後新的頭就會是這筆新資料。在此，即使是沒有任何資料的狀態也不會有問題，因為沒有任何資料的狀況之下，我們早在一開始便把head initialize成為NULL了，因此這時候這筆新資料往後接的，便會是NULL，這也是正常該有的狀況。

而資料的插尾，就是把這筆資料直接放到最尾端。我們可以直接一個一個從頭去search next指標直到尾端去找尾端然後把這筆資料往後接上，但這太耗費工夫，尤其如果是巨量資料之下的話會更明顯。因此我們直接create一個指標tail，指向這個list的最後一個node，我們一開始initialize為NULL：

node *tail = NULL;

接著這個程式create memory並放入資料給這筆新資料之後，首先就將這筆新資料的尾端接為NULL：

   data->next = NULL;

然後我們先判定目前是不是現有資料，原因在於如果不管三七二十一不判定有沒有資料而直接把tail往後接給這筆資料的話，會有問題，因為我們並沒有配給tail一個記憶體空間，所以它的next是不存在的，因為即使是指標，還是需要記憶體空間的。所以如果沒有任何資料在list之內，我們直接把tail和head assign給這筆新資料：

   if (head == NULL)
      // then this node is head and also tail
      head = tail = data;

當然我們也可以用tail == NULL來判斷也是一樣的結果。邏輯上來講，如果沒有任何資料存在，那麼這筆新資料就會是這個link list的頭兼尾，這邊程式的邏輯就會把這段話給烙印上去。

接著如果現有資料的話，我們就把tail往後接這筆資料，接著才把tail assign給這筆資料，這邊順序要對，如果我們先把tail assign給這筆新資料在把tail往後接給這筆資料的話，結果會是這筆資料是孤立的，沒有任何資料接它，並且它的next會是接它自己。

      tail->next = data;
      tail = data;

於是接頭接尾便能夠很簡單的用幾行就可以完成。

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就會是比她還小的值，應當接在插入值的前方。

陣列-sparse matrix的轉置

void trans_spm(spm *orig, spm *trans)
{
   // sofar is the index for trans
   int col, i, sofar = 1;
   // initialize matrix info
   int TotalCol = trans[0].row = orig[0].col;
   trans[0].col = orig[0].row;
   int TotalElements = trans[0].val = orig[0].val;

   // loop with column index
   for (col = 0; col < TotalCol; col++)
      // search all over the elements
      // for the same column
      for (i = 1; i <= TotalElements; ++i)
         if (orig[i].col == col) {
            // add the same column elements to trans
            trans[sofar].row = col;
            trans[sofar].col = orig[i].row;
            trans[sofar].val = orig[i].val;
            sofar++;
         }
}

sparse matrix的轉置矩陣，其做法的原理很簡單，首先的資料部分row 和column數目對調就是轉置的結果，總element數目不變。接著再以column為主，從原先的矩陣依照(column, row)的順序把每一個element抽出來放到轉置矩陣去。

因此首先有dummy index：

   int col, i, sofar = 1;

col是給column用的index，為了loop in column。而i則是跑全部的element。sofar則是記錄目前在轉置矩陣上的index。
接著把矩陣資料排好給轉置矩陣後，就開始依據(column, row)的順序把element從原矩陣中抽出。

  for (col = 0; col < TotalCol; col++)

因為我們要排的是轉置的矩陣，因此原先的矩陣排列方式是(row, column)，那麼現在的轉置矩陣就會是原矩陣的相反(column, row)。首先的迴圈就run over all column的index去依據column大小的順序去排列轉置矩陣。

      for (i = 1; i <= TotalElements; ++i)
         if (orig[i].col == col) {
            // add the same column elements to trans
            trans[sofar].row = col;
            trans[sofar].col = orig[i].row;
            trans[sofar].val = orig[i].val;
            sofar++;
         }

我們便每次都從第一個element開始排列順序，我們每一次一個column都會從頭從原矩陣的每個element找起，找的目標就是當下的column，比如我們開始排列第0個column，那麼我們便從原矩陣找column為0的。而原矩陣的row和column早就已經排列過了，因此我們就按照element的順序去找起即可，而不需要考慮row的順序。當我們找到當下的column的時候，便把這個element assign給轉置矩陣，當然row和column是要對調的，而值是相同的。因此按照這樣的邏輯下去這個轉置矩陣變這樣完成。

陣列-sparse matrix的加法

// add sparse matrix c = a + b
void add_spm(spm *c, spm *a, spm *b)
{
   int ia = 1; // index for a
   int ib = 1; // index for b
   int ic = 1; // index for c

   // while both index are not yet reach the end
   while (ia <= a[0].val && ib <= b[0].val)
      // if a position > b position, then assign b to c
      if (a[ia].row > b[ib].row ||
          a[ia].row == b[ib].row && a[ia].col > b[ib].col)
         c[ic++] = b[ib++];
      // if a position < b position, then assign a to c
      else if (a[ia].row < b[ib].row ||
               a[ia].row == b[ib].row && a[ia].col < b[ib].col)
         c[ic++] = a[ia++];
      // if a position = b position, c = a+c
      else {
         // we only save non-zero elements
         int sum = a[ia].val + b[ib].val;
         if (sum != 0) {
            c[ic].row = a[ia].row;
            c[ic].col = a[ia].col;
            c[ic].val = sum;
            ic++;
         }
         ia++;
         ib++;
      }
   /* end while */

   // assign the rest elements a OR b to c
   while (ia <= a[0].val)
      c[ic++] = a[ia++];
   while (ib <= b[0].val)
      c[ic++] = b[ib++];
   // assgin the matrix info to c
   c[0].row = a[0].row;
   c[0].col = a[0].col;
   c[0].val = ic - 1;
}

加法其實很簡單，有overlap的elements就是直接加，沒有overlap的部分就是看row和column的位置，先判斷row在判斷column，row/column數字少的就直接遞給c。接著如果其中一方a或b已經把它自己的element都遞給c的時候，那麼另外一方就直接把剩餘的element都遞給c，因為已經不會有overlap的部分了。

  while (ia <= a[0].val && ib <= b[0].val)

首先這個迴圈，當a以及b皆有element要加的時候就會持續的做以下的加法。

      if (a[ia].row > b[ib].row ||
          a[ia].row == b[ib].row && a[ia].col > b[ib].col)
         c[ic++] = b[ib++];

在while迴圈仍有效的前提之下，開始判斷有沒有overlap的element。這邊就判定不是overlap，並且a的目前index的位置是在b之後的，所以我們就直接把b的element assign給c，並且各自的index往下一個element前進，而接著的else if則是相同的邏輯，只是是判定b的index在a之後。

      else {
         // we only save non-zero elements
         int sum = a[ia].val + b[ib].val;
         if (sum != 0) {
            c[ic].row = a[ia].row;
            c[ic].col = a[ia].col;
            c[ic].val = sum;
            ic++;
         }

接著最後則是a和b是overlap的element，把他們的值加上去之後assign給c，把c的index往後移之後

         ia++;
         ib++;

馬上把a和b的index都往後移，最後最外面的while迴圈跑完之後，有三種情形：1.(a沒有剩下了，b還有) 2.(b沒有剩下了，a還有) 3.(都沒有剩下了) 但不論是怎樣的情形，我們都會跑：

   while (ia <= a[0].val)
      c[ic++] = a[ia++];
   while (ib <= b[0].val)
      c[ic++] = b[ib++];

因為即使是情形1. a沒有剩下的element，我們跑while(ia <= a[0].val)它不會有element要執行，因此這邊是不會跑迴圈的，只會跑下面那個b，而情形2和情形3亦然是如此。最後我們再把這矩陣的資料assign給c就完成了。