C和指針讀書筆記（第十二章）

1. 單連結清單P235~245

1.1 單連結清單的結構

typedef struct NODE{
        STRUCT NODE *link;
        int value;
}Node;
//根指針隻是一個指針
//連結清單最後一個節點的指針字段的值為NULL
           

1.2 單連結清單的插入P244

int insert_list(Node **linkp, int new_value)
{
    Node *current;
    Node *New;

    //尋找正确的插入位置，方法是按序通路連結清單，知道達到其值大于或等于新插入值的節點
    while((current = *linkp) != NULL && current->value < new_value){
        linkp = &current->link;
    }

    //為新節點配置設定記憶體，并把新值存儲到新節點中，如果記憶體配置設定失敗函數傳回FALSE
    New = (Node *)malloc(sizeof(Node));
    if(New == NULL){
        return FALSE;
    }
    New->value = new_value;

    //把新節點插入到連結清單中，并傳回TRUE
    New->link = current;
    *linkp = New;
    return TRUE;
}
           

2. 雙連結清單

對if循環的代碼簡化

在函數中各個嵌套的if語句群存在相似代碼的時候，可以将語句提煉到if循環外

if(x == ){
    i = ;
    something;
    j = ;
}else{
    i = ;
    something else;
    j = ;
}
//修改後
i = ;
if(x == ){
    something;
}else{
    something else;
}
j = ;
           

雙連結清單插入結點的相關代碼P252

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

typedef struct NODE{
        struct NODE *fwd;
        struct NODE *bwd;
        int value;
}Node;

int dll_insert(Node *rootp, int value)
{
    Node *This;
    Node *next;
    Node *newnode;

    //檢視value是否已經存在于連結清單中，如果是就傳回
    //否則為新值建立一個新節點（"newnode"将指向它）
    //"this"将指向應該在新節點之前的那個節點
    //"next"将指向應該在新節點之後的那個節點
    for(This = rootp; (next = this->fwd) != NULL; this = next){
        if(next->value == value){
            return ;
        }
        if(next->value > value){
            break;
        }
    }

    //為新的節點申請空間
    newnode = (Node *)malloc(sizeof(Node));
    if(newnode == NULL){
        return -;
    }
    newnode->value = value;

    //把新節點添加到連結清單中
    newnode->fwd = next;
    this->value = value;

    if(this != rootp){
        newnode->bwd = this;
    }else{
        newnode->bwd = NULL;
    }

    if(next != NULL){
        next->bwd = newnode;
    }else{
        rootp->bwd = newnode;
    }
    return -;
}
           

3. 語句簡練是一種簡化程式的技巧，其方法是消除程式中備援的語句。如果一句if語句的“then”和“else”子句以相同序列的語句結尾，它們可以被一份單獨的出現于if語句之後的拷貝代替。相同序列的語句也可以從if語句的起始位置提煉出來，但是這種提煉不能改變if的測試結果。

2016.10.13