# 資料結構 HW2 筆記

> Write a C program to read 10 car plate number and its color. Sort and store the data in a Singly linked list in ascending way. Print out the data.

>使用C語言寫一個能紀錄十筆車牌號碼與車輛顏色的程式。輸入資料後依升序插入至鏈結串列中，最後印出所有節點之資料。

> 5/22 更新：
對不起，我少考慮了插入時新節點的車號等於串列第一個節點的情況，假如是參考我的程式的話，請將情況二的判斷式從 "小於" 改為 "小於等於"，筆記中皆已修正。

我想大家主要的問題在於節點插入的演算法，因此我僅對 **insert()** 函數做了額外說明，其餘部分請閱讀我寫的註解。

<details>
<summary>完整程式碼（含註解）</summary>

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

struct snode{
    int pla;            // 車牌號碼
    char st;            // 車輛顏色
    struct snode *nx;   // 指向下個節點的指標
};

// 宣告一個指標變數 opt 指向串列的第一個節點，因為串列為空所以指向NULL
// 建立 linked list 唯一需要的外部指標就只有這個指向第一個節點的 opt
// 老師建立的那一堆指標僅是作為節點處理時用到的索引而已
struct snode *opt = NULL;

void insert(int number, char color){
    
    // 分配空間給新節點，並宣告一個指標變數 newNode 指向這個新節點
    struct snode *newNode = (struct snode*)malloc(sizeof(struct snode));
    
    // 將資料填入新節點
    newNode->pla = number;
    newNode->st = color;
    
    // ！！開始插入！！
    // 情況一：串列為空
    if(opt == NULL){
        // 插在串列最前面
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    
    // 情況二：新節點小於或等於串列的第一個節點
    if(newNode->pla <= opt->pla){
        // 插在串列最前面（同情況一）
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    
    // 情況三：依序對串列中各節點比較大小，直到有節點大於新節點或已沒有節點可比較
    struct snode *current = opt, *prev;
    while(newNode->pla > current->pla){
        // current 會作為索引從第一個節點依序指向串列中各個節點進行比較
        // prev 負責記錄 current 的前一個節點
        prev = current;
        current = current->nx;
        // 若 current 等於 NULL 代表串列中的節點已經被比光了
        if(current == NULL) break;
    }
    // 跳出 while 迴圈時 current 指向的節點必大於新節點或等於 NULL
    // 將新節點插入於 current 與 prev 所指的兩個節點中間
    prev->nx = newNode;
    newNode->nx = current;
    return;
}

int main(){
    int number;
    char color;
    printf("請輸入10組車牌號碼與其顏色對應的字元:\n");
    for(int i=0; i<10; ++i){
        scanf("%d %c", &number, &color);
        insert(number, color);
    }
    // 宣告一個指標變數 current 作為索引
    // 讓它從第一個節點一路指到最後一個節點，便能印出所有節點的資料
    struct snode *current = opt;
    while(current != NULL){
        printf("車號: %4d, 顏色: %c\n", current->pla, current->st);
        current = current->nx;
    }
    return 0;
}

</details>
<br>
<details>
<summary>完整程式碼（無註解）</summary>

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

struct snode{
    int pla;
    char st;
    struct snode *nx;
};
struct snode *opt = NULL;

void insert(int number, char color){
    struct snode *newNode = (struct snode*)malloc(sizeof(struct snode));
    newNode->pla = number;
    newNode->st = color;
    if(opt == NULL){
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    if(newNode->pla <= opt->pla){
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    struct snode *current = opt, *prev;
    while(newNode->pla > current->pla){
        prev = current;
        current = current->nx;
        if(current == NULL) break;
    }
    prev->nx = newNode;
    newNode->nx = current;
    return;
}

int main(){
    int number;
    char color;
    printf("請輸入10組車牌號碼與其顏色對應的字元:\n");
    for(int i=0; i<10; ++i){
        scanf("%d %c", &number, &color);
        insert(number, color);
    }
    struct snode *current = opt;
    while(current != NULL){
        printf("車號: %4d, 顏色: %c\n", current->pla, current->st);
        current = current->nx;
    }
    return 0;
}

</details>
<br>
<details>
<summary>翁教授的程式碼</summary>

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

struct snode{
    int pla;
    char st;
    struct snode *nx;
};
struct snode *opt = 0, *pt, *p1, *p2;

int insert(int x, char y){
    struct snode *pp;
    pp = (struct snode*)malloc(sizeof(struct snode));
    pp->pla = x;
    pp->st = y;
    if (opt == 0){// initial
        opt = pp;
        pp->nx = 0;
        printf(" init\n");
    }else{// non-initial
        p1 = opt;
        p2 = p1;
        while(p1 != 0){
            if(x > p1->pla){// next
                p2 = p1;// 跟上
                p1 = p1->nx;// 向前一步
                printf(" next ");
            }else{
                if(p2 == p1){
                    pp->nx = opt;
                    opt = pp;
                    printf(" ih\n");
                }else{// insert in the middle or end
                    pp->nx = p2->nx;
                    p2->nx = pp;
                    printf(" im\n");
                }
                break;
            }
        }
        if(p1 == 0){// insert in the end
            pp->nx = p2->nx;
            p2->nx = pp;
            printf(" ie\n");
        }
    }
}

int main(){
    int i, p, s;
    printf("Insert 5 plates and colors\n");
    for(i=0; i<5; i++){
        scanf("%d %c", &p, &s);
        printf("%d %c ", p, s);
        insert(p, s);
    }
    printf("\nThe sorted list is:\n");
    p1 = opt;
    while(p1 != 0){
        printf("%d %c\n", p1->pla, p1->st);
        p1 = p1->nx;
    }
}

</details>

> 要注意，除了結構、結構內與串列首指標的變數名稱，其餘變數我並未與教授的命名統一。

<details>
<summary>inesert() 函數測試程式</summary>

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

struct snode{
    int pla;
    char st;
    struct snode *nx;
} *opt = NULL, testArray[20];

// -----------------------------------
// 替換掉此處的 insert() 來檢測你寫的函數功能是否正常
// 每次執行會自動輸入 20 筆資料，也請不必擔心輸出的排版
void insert(int number, char color){
    struct snode *newNode = (struct snode*)malloc(sizeof(struct snode));
    newNode->pla = number;
    newNode->st = color;
    if(opt == NULL || newNode->pla <= opt->pla){
        newNode->nx = opt;
        opt = newNode;
    }
    else{
        struct snode *current = opt, *prev;
        while(current != NULL && newNode->pla > current->pla){
            prev = current;
            current = current->nx;
        }
        prev->nx = newNode;
        newNode->nx = current;
    }
}
// -----------------------------------

void mkData(int quantity){
    int number;
    char color;
    srand(time(NULL));
    for(int i = 0; i < quantity; ++i){
        number = rand() % 9000 + 1000;
        color = rand() % 26 + 65;
        testArray[i].pla = number;
        testArray[i].st = color;
    }
}

int main(){
    int number, count = 0;
    char color;
    mkData(20);
    printf("Raw input: \n");
    for(int i=0; i<20; ++i){
        number = testArray[i].pla;
        color = testArray[i].st;
        printf("%4d %c ", number, color);
        insert(number, color);
        if(++count%5 == 0) printf("\n");
    }
    printf("\nData of the list: \n");
    struct snode *current = opt;
    for(; current != NULL; current = current->nx)
        printf("plaNum: %4d, color: %c\n", current->pla, current->st);
    return 0;
}

</details>

> 這個程式每次執行會自動輸入 20 筆隨機資料，用你打的 insert() 函數取代我寫的部分來檢測功能是否正常。

## **insert() 函數：**

void insert(int number, char color){
    
    // 分配空間給新節點，並宣告一個指標變數 newNode 指向這個新節點
    struct snode *newNode = (struct snode*)malloc(sizeof(struct snode));
    
    // 將資料填入新節點
    newNode->pla = number;
    newNode->st = color;
    
    // ！！開始插入！！
    // 情況一：串列為空
    if(opt == NULL){
        // 插在串列最前面
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    
    // 情況二：新節點小於或等於串列的第一個節點
    if(newNode->pla <= opt->pla){
        // 插在串列最前面（同情況一）
        newNode->nx = opt;
        opt = newNode;
        return;
    }
    
    // 情況三：依序對串列中各節點比較大小，直到有節點大於新節點或已沒有節點可比較
    struct snode *current = opt, *prev;
    while(newNode->pla > current->pla){
        // current 會作為索引從第一個節點依序指向串列中各個節點進行比較
        // prev 負責記錄 current 的前一個節點
        prev = current;
        current = current->nx;
        // 若 current 等於 NULL 代表串列中的節點已經被比光了
        if(current == NULL) break;
    }
    // 跳出 while 迴圈時 current 指向的節點必大於新節點或等於 NULL
    // 將新節點插入於 current 與 prev 所指的兩個節點中間
    prev->nx = newNode;
    newNode->nx = current;
    return;
}

<br>

**我們將插入節點分為三種情況：**

### **1. 串列為空（串列中沒有任何節點）**
* 插入方法：將新節點插入在最前面（作為串列的首個節點）。

if(opt == NULL){
    // 插在串列最前面
    newNode->next = opt;
    opt = newNode;
    return;
}
// 程式執行至 return 便會跳出副程式回到主程式
// 善加利用 return 可以簡化多層 if...else 的複雜邏輯

### **2. 新節點小於或等於串列的第一個節點**
* 插入方法：將新節點插入在最前面（同情況一）。

if(newNode->pla <= opt->pla){
    // 插在串列最前面
    newNode->nx = opt;
    opt = newNode;
    return;
}

### **3. 若非前兩點之情況，依序對串列中各節點比較大小，直到有節點大於新節點或串列已沒有節點可比較**

* 插入方法：將新節點插入於該節點前一個位置。

（若新節點大於串列中所有節點，則插在 NULL 的前一個位置，也就是最尾端。）

struct snode *current = opt, *prev;
while(newNode->pla > current->pla){
    // current 會作為索引從第一個節點依序指向串列中各個節點進行比較
    // prev 負責記錄 current 的前一個節點
    // 如 current 指向節點五，prev 就是指向節點四
    prev = current;
    current = current->nx;
    // 若 current 等於 NULL 代表串列中的節點已經被比光了
    if(current == NULL) break;
}
// 跳出 while 迴圈時 current 指向的節點必大於新節點或等於 NULL
// 將新節點插入於 current 與 prev 所指的兩個節點中間
prev->nx = newNode;
newNode->nx = current;
return;

> 當 currrent == NULL 時 prev 必指向最後一個節點，
> 此時插入在 current 與 prev 所指的兩個節點中間等同於插在最尾端。