[C和指針]第三部分，指針第三部分

[C和指針]第三部分，指針第三部分

第八章     結構和聯合... 1
第九章     動態內存分配... 9
第十章     使用結構和指針（鏈表實現）... 14

第八章     結構和聯合

在C中，使用結構可以把不同類型的值存儲在一起。數組是通過下標訪問，因為數組的元素長度相同，但是結構並不是這樣，每個結構成員都有自己的名字，它們是通過名字來訪問的。
 
結構變量屬於標量類型，並不是指針類型，和其他任何標題一樣，當結構名在表達式中作為右值使用時，它表示存儲在結構中的值。當它作為左值使用時，它表示結構存儲的內存位置。但是，當數組名在表達式中作為右值使用時，它的值是一個指向數組第一個元素的指針，由於它的值是一個常量指針，所以數組名不能作為左值使用。可以聲明指向結構的指針與結構數組。
 
struct 標識 { 成員列表}  變量列表 ;
 
struct {
    inta;
    charb;
    floatc;
} x;
struct {
    inta;
    charb;
    floatc;
} y[10], *z;
注意，上面是兩種截然不同的類型，所以不能這樣：z = &x
 
struct SIMPLE {
    inta;
    charb;
    floatc;
};
該聲明並沒有提供變量列表，所以它並未創建任何變量，下面才開始創建變量。
struct SIMPLE x;
struct SIMPLE y[10], *z;
但現在與上前面的聲明不同的是 x y z 都是同一種類型的結構變量了，所以z = &x可以
 
typedefstruct {
    inta;
    charb;
    floatc;
} Simple;
Simple現在是一個類型名而不是一個結構標簽，所以後續的聲明可以是下面這樣：
Simple x;
Simple y[10], *z;
 
結構可以嵌套其他結構：
    struct COMPLEX {
       struct SIMPLE sa[10];
       struct SIMPLE *sp;
    } comp, *cp = ∁
 
結構的訪問
    typedefstruct EX {
       inta;
       charb[3];
       struct EX2 {
           inta;
           shortb[2]
       } c;
       struct EX *d;
    } EX;
    EX x = { 10, "Hi", { 5, { -1, 25 } }, 0 };
    EX *px = &x;
    EX y;
    x.d = &y;
    printf("%d", x.a);//10//結構體變量的訪問方式
    printf("%d", (*px).a);//10//結構體指針的訪問方式
    printf("%d", px->a);//10//此種為上面結構指針的簡化訪問方式
    printf("%d", *px->c.b);//-1//混合使用
    printf("%d", px->d->c.b[1]);//30656
    px->d->c.b[1]=11;
    printf("%d", px->d->c.b[1]);//11 
 
  結構的自引用
    struct SELF_REF1 {
inta;
       struct SELF_REF1 b;//非法
    };
----
    struct SELF_REF2 {
       inta;
struct SELF_REF2 *b;//合法
    };
    printf("%d", sizeof(a.a));//4
    printf("%d", sizeof(a.b));//4
第一個聲明會嘗試遞歸下去，但最終結構的長度不能確定下來而編譯時出錯誤；但第二個是一個指針，其在編譯時能夠確定結構體的長度，一般鏈表和樹都是用這種技巧實現。
 
在32位機上，一個指針通常占4個字節，而不管它指向什麼類型的變量，因為指針是用來存儲存儲地址的：
    char *p = NULL;
    printf("%d", sizeof(p));//4
    printf("%d", sizeof (char *));//4
 
書上說下面是非法的（原因就是類型名直到聲明的末尾才定義，在結構聲明的內部它尚定義），但實際上編譯可以通過：
    typedefstruct {
       inta;
       struct SELF_REF3 *b;//合法
    } SELF_REF3;
    SELF_REF3 a = { 3, NULL };
    printf("%d", a.a);//3
 
相互引用的結構
有時需要聲明一些相互之間存在依賴的結構，先被引用的結構需要使用不完整聲明（如下面的struct B;），來聲明一個作為結構標簽的標識符，然後我們可以把這個標簽與用在結構指針的聲明中（如下面的struct B *partner;）：
    struct B;
    struct A {
       inta;
       struct B *partner;
    };
    struct B {
       struct A partner;
    };
經實際測試，struct B;可以注釋掉，編譯時都不會出錯，甚至將後面的B結構的定義一起去掉都沒有問題，這也進一肯說聲明結構體指針時不需要知道它所指向的結構體的具體類型，甚至不需要定義都可以；
 
結構體的初始化
結構體的初始化類似於或多維數組的初始化：
    struct A {
       inta;
       shortb[10];
       Simplec;
    } x = { 10, { 1, 2 }, { 25, 'x', 1.9 } };
 
 
結構的地址與第一個成員的地址是相同的：
    struct A {
       inta;
       shortb[10];
    } x;
    printf("%p\n", &x);//0022FF38
    printf("%p\n", &x.a);//0022FF38
    printf("%p\n", &x);//0022FF38
    printf("%p\n", &x.a);//0022FF38
   
結構的存儲分配
上面章節中（“結構的訪問”），顯示的是結構的邏輯存儲結構（圖中分配的空間好像不連續），那結構在內存中是如何實際存儲的呢？上面那張圖並不完整，實際上編譯器會按照成員列表的順序（聲明的順序）一個接一個地給每個成員分配內存，只有當存儲成員時需要滿足正確的邊界要求時，成員之間才可能出現用於填充的額外內存空間（被浪費掉了的），如下面圖中的灰色地帶：
#include<stddef.h>
       typedefstruct ALIGN {
       chara;
       intb;
       charc;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,a));//0
    printf("%d", offsetof(struct ALIGN,b));//4
    printf("%d", offsetof(struct ALIGN,c));//8
    printf("%d", sizeof (struct ALIGN));//12 
如果編譯器有成員對齊這一要求時，會按照最長類型來分配每一個成員，如上面的a成員，在整型類型長度為4字節的機器上，由於a是一個字符型，雖然本身只需一個字節，但也為a分配了4個字節，這將浪費3個字節的空間，c也是一樣，此時需要總共12個字節的空間。如果將短的類型放在一起，這將會節約空間（此時只需要8個字節的空間）：
    typedefstruct ALIGN {
       intb;
       chara;
       char c;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,b));//0
    printf("%d", offsetof(struct ALIGN,a));//4
    printf("%d", offsetof(struct ALIGN,c));//5
    printf("%d", sizeof (struct ALIGN));//8 
下面與上面也是一樣節約空間：
    typedefstruct ALIGN {
       chara;
       char c;
       int b;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,a));//0
    printf("%d", offsetof(struct ALIGN,c));//1
    printf("%d", offsetof(struct ALIGN,b));//4
    printf("%d", sizeof (struct ALIGN));//8
 
最後看看下面這個程序：
    typedefstruct ALIGN {
       chara;
       charc;
       chard;
       shorte;
       charf;
       charj;
       intb;
    }ALIGN;
    printf("%d", offsetof(struct ALIGN,a));//0
    printf("%d", offsetof(struct ALIGN,c));//1
    printf("%d", offsetof(struct ALIGN,d));//2
    printf("%d", offsetof(struct ALIGN,e));//4
    printf("%d", offsetof(struct ALIGN,f));//6
    printf("%d", offsetof(struct ALIGN,j));//7
    printf("%d", offsetof(struct ALIGN,b));//8
    printf("%d", sizeof (struct ALIGN));//12 
 
  sizeof操作符能夠得出一個結構體的整體長度，包括因邊界對齊而路過的那些字節，如果想得到每個成員偏離結構首的字節數，則可以使用offsetof宏。
 
降序排列結構成員的聲明可以最大限度地減少結構存儲中浪費的內存空間。sizeof返回的值包含了結構中浪費的內存空間。
 
參數結構體
把結構體作為參數傳遞給一個函數是合法的，但這種做法效率低，因為在傳遞過程中需要復制整個結構體。
 
void print(registerstruct Trans const * const trans);
在許多的機器中，你可以把參數聲明為寄存器變量，從而進一步提高指針傳遞方案的效率，這對於需要多次訪問的變量有很大的效率提升。
 
位段
用signed或unsigned整數地聲明位段是個好主意，如果只是聲明為int類型，它究竟被解釋為有符號數還是無符號數是由編譯器決定的。
 
位段的聲明與結構類似，但它的成員是一個或多個位的字段，這些不同長度的字段實際上存儲於一個或多個整型變量中。
 
位段的成員必須聲明為int、signed int、或unsigned int類型。其次，在成員名的後面是一個冒號和一個整數，這個整數指定該位段所占用的位的數目。
 
    struct CHAR {
       unsignedch :7;
       unsignedfont :6;
       unsignedsize :19;
    };
    struct CHAR ch1;
該程序可以處理128個不同的字符值、64種不同的字段、524288種字體大小。成員size位段過於龐大，無法容納於一個短整型中，但其他的位段成員又比一個字符還短，所以這裡能夠利用存儲ch和font所剩余的位來用在size位段上，這樣就可以使用一個32位的整數來存儲整個內容了。上面程序在16位機上是非法的，因為最長的位段定義成了19，而最長也只可能為16，但在32位機上，這個聲明將根據下面兩種可能的方法創建ch1： 
位段的好處：它能夠把長度不同的類型數據包裝在一起，節省存儲空間。另一個好處是，可以很方便地訪問一個整型值的部分內容。下面是一個軟盤控制器寄存器，每位的結構如下： 
在一個從右向左分配位段的機器上，下面的這個聲明允許程序方便地對這個寄存器的不同位段進行訪問：
    struct DISK_REGISTER_FORMAT {
       unsignedcommand :5;
       unsignedsector :5;
       unsignedtrack :9;
       unsignederror_code :8;
       unsignedhead_loaded :1;
       unsignedwrite_protect :1;
       unsigneddisk_spinning :1;
       unsignederror_occurred :1;
       unsignedready :1;
    };
假如寄存器是在內存地址 0xc0200142 ，我們可以聲明下面的指針常量：
#define DISK_REGISTER ((struct DISK_REGISTER_FORMAT*)0xc0200142)
下面開始訪問：
    /*
     * 告訴控制器從哪個扇區哪個磁道開始讀取
     */
    DISK_REGISTER->sector = new_sector;
    DISK_REGISTER->track = new_track;
    DISK_REGISTER->command = READ;
    /*
     * 等待，直到操作完成（ready變量變成真）
     */
    while (!DISK_REGISTER->ready);
    /*
     * 檢查錯誤
     */
    if(DISK_REGISTER->error_code){
      
    }
使用位段只是基於方便的目的，任何可以用位段實現的任務都可以使用移位和屏蔽來實現。下面的代碼功能和前面的賦值功能是一樣：
#define DISK_REGISTER ((unsignedint *)0xc0200142)
    *DISK_REGISTER &= 0xfffffc1f;//將sector字段清零
    *DISK_REGISTER |= (new_sector & 0x1f) << 5;//賦值
在源代碼中，用位段表示這個處理過程更簡單一些，但在目標中，這兩種方法並不存在任何區別，無論是否使用位段，相同的移位和屏蔽都是必需的。位段提供的唯一優點是簡化了源代碼，但需要與位段的移植性較弱這個缺點進行權衡。
 
注重可移植性的程序應該避免使用位段，位段在不同的系統中可能有不同的結果：
1、  int位段被當作有符號數還是無符號數。
2、  位段中字段的位最大數目。許多編譯器把位段成員的位數限制在一個整型的長度之內，所以能夠運行於32位整數的機器上的位段聲明可能在16位整數的機器上無法運行，如unsignederror_code :32;  肯定是不能移植了。
3、  位段中的成員在內存中是從左向右分配的還是從右向左分配的。
 
聯合
聯合的所有成員引用的是內存中的相同位置，當你想在不同的時刻把不同的東西存儲於一個位置時，就以使用聯合。通過訪問不同類型的聯合成員時，內存中相同的位組合可以被解釋為不同的東西。
 
union u_tag {
    inti;
    floatf;
    char *s;
} u;
int main(int argc, char * argv[]) {
    printf("%d\n", u.i);//0
    u.i=1;
    printf("%d\n", u.i);//1
    printf("%f\n", u.f);//0.000000
    u.f=1.1;
    printf("%f\n", u.f);//1.100000
    //打印的還是最後一次存儲的內容
    printf("%f\n", u.i);//1.100000
    //float轉換成int
    printf("%d\n", u.i);//1066192077
    return 0;
}
 
聯合與結構可以相互嵌套。
 
實際上，聯合就是一個結構，它的所有成員相對於基地址的偏移量都為0，此結構空間要大到足夠容納最“寬”的成員。
 
在一個成員長度不同的聯合裡，分配給聯合的內存數量取決於它的最長成員的長度。如果成員的長度相關懸殊，會浪費很多的空間，在這種情況下，最好的方法是在聯合中存儲指向不同成員的指針而不是直接存儲成員本身，因為所有指針的長度都是相同的，這樣就解決了內存浪費的問題了。
 
聯合會默認使用第一個成員類型的值進行初始化。
 
聯合初始化必須是聯合第1個成員的類型，而且它必須位於一對花括號裡：
    union {
       charc;
       inta;
       floatb;
    } x={'a'};
    printf("%c\n",x.c);//a
    printf("%d\n",x.a);//97

第九章     動態內存分配

當你聲明數組時，你必須用一個編譯時常量指定數組的長度，但是，數組的長度常常在運行時才知道，所以我們通常采用的方法是聲明一個較大的數組，它可以容納可能出現的最多元素。
 
malloc從內存池中提取一塊合適的內存，並向程序返回一個指向這塊內存的指針。分配與釋放的函數原型如下：
void *malloc(size_t size);
void free(void *pointer);
size_t是一個無符號類型，定義於stdlib.h中，該參數指定了需要分配的內存字節數。
 
malloc所分配的是一塊連續的內存。malloc實際分配的內存有可能比你請求的稍微多一點，這是由編譯器定義的。
 
如果操作系統無法向malloc提供更多的內存，malloc就返回一個NULL指針。
 
malloc是不知道你所請求的內存是用來存儲整數、浮點數、結構還是數組的，所以它返回的是一個類型為void*的指針，而這個類型的指針可以轉換為其他任何類型的指針，在某些老式的編譯器中，可能要求你在轉換時使用強制類型轉換。
 
另外還有兩個內存分配函數，原型如下：
void *calloc(size_t num_elements, size_t element_size);
void realloc(void *ptr, size_t new_size);
calloc與malloc之間的主要區別是前者在返回指向內存的指針之前把內存初始化為0，另一個區別是它們請求內存數量的方式不同，calloc的參數包括所需要元素的數量和每個元素的字節數，根據這些值，它能夠計算出總共需要分配的內存。
 
realloc函數用於修改一個碑已經分配的內存塊的大小，可以使用一塊內存擴大或縮小。擴大時原先的內容依然保留，新增加的內存添加到原先內存塊的後面，新內存並未以任何方法進行初始化。縮小時，該內存塊尾的部分內存被拿掉，剩余部分內存的原先內容依然保留。如果原先的內存無法改變大小，realloc將分配另一塊正確大小的內存，並把原先那塊內存的內容復制到新的塊上。因此，在使用realloc之後，你主不能再使用指向舊內存的指針，而是應該改用realloc所返回的新的指針。
 
    int i, *pi, *pi2;
    //這塊內存將被當作25個整型元素的數組，
    //因為pi是一個指向整型的指針
    pi = malloc(25 * sizeof(int));
    if (pi == NULL) {
       printf("Out of memory!\n");
       exit(1);
    }
    pi2 = pi;
    for (i = 0; i < 25; i++) {
       *pi2++ = 0;
       //或者使用下標，當作數組來使用 pi[i]=*(pi + i)
       //pi[i]=0;
    }
 
常見的動態內存錯誤：對NULL指針進行解引用操作、對分配的內存進行操作時越過邊界、釋放並非動態分配的內存、試圖釋放一塊動態分配的內存的一部分、一塊動態內存被釋放之後被繼續使用。
 
使用MALLOC自定義宏來避免上面這些錯誤，下面程序由三部分組成：一個是定義接口alloc的頭文件alloc.h，第二個是接口，第三個是使用接口：
/*
* 定義一個不易發生錯誤的內存分配器接口
*/
#include<stdlib.h>
#define malloc 不要直接調用malloc!
#define MALLOC(num,type) (type*)alloc((num) * sizeof(type))
externvoid * alloc(size_t size);//接口
                                                                 ——alloc.h
/*
* 實現
*/
#include<stdio.h>
#include"alloc.h"
#undef malloc
void * alloc(size_t size) {
    void * new_mem;
    //請求所需的內存，並檢查確實分配成功
    new_mem = malloc(size);
    if (new_mem == NULL) {
       printf("Out of memory!\n");
       exit(1);
    }
    return new_mem;
}
                                                                 ——alloc.c
#include"alloc.h"
/*
* 使用
*/
void function() {
    int * new_memeory;
    //獲取一串整型數的空間
    new_memeory = MALLOC(25,int);
}
                                                                 ——a_client.c
 
 
free的參數必須要麼是NULL，要麼是一個先前從malloc、calloc或realloc返回的值，向free傳遞一個NULL參數不會產生任何效果。free試圖釋放一塊動態分配內存的一部分也有可能引起問題：
pi = malloc(25 * sizeof(int));
//下面會引發問題
free(pi +5);
釋放一內存的一部分是不允許的，動態分配的內存必須整塊一起釋放。但是，realloc函數可以縮小一塊動態分配的內存，有效地釋放它尾部的內存。
 
不能訪問已經被free函數釋放了的內存。
 
分配內存但在使用完畢後不釋放將引起內存洩漏
 
動態分配實例
動態分配最常見的一個應用就是為那些長度在運行時才知道的數組分配內存空間。下面是讀取一列整數，並排序：
/*
** 讀取、排序和打印一列整數.
*/
#include<stdlib.h>
#include<stdio.h>
 
/*
** 該函數由 qsort 用於比較整型值
*/
int compare_integers(voidconst *a, voidconst *b) {
    registerintconst *pa = a;
    registerintconst *pb = b;
 
    return *pa > *pb ? 1 : *pa < *pb ? -1 : 0;
}
 
int main() {
    int *array;
    int n_values;
    int i;
 
    /*
     ** 觀察共有多少個值.
     */
    printf("How many values are there? ");
    if (scanf("%d", &n_values) != 1 || n_values <= 0) {
       printf("Illegal number of values.\n");
       exit(EXIT_FAILURE);
    }
 
    /*
     ** 分配內存，用於存儲這些值.
     */
    array = malloc(n_values * sizeof(int));
    if (array == NULL) {
       printf("Can't get memory for that many values.\n");
       exit(EXIT_FAILURE);
    }
 
    /*
     ** 讀取這些值.
     */
    for (i = 0; i < n_values; i += 1) {
       printf("? ");
       if (scanf("%d", array + i) != 1) {
           printf("Error reading value #%d\n", i);
           exit(EXIT_FAILURE);
       }
    }
 
    /*
     ** 調用庫函數進行排序.
     */
    qsort(array, n_values, sizeof(int), compare_integers);
 
    /*
     ** 輸出.
     */
    for (i = 0; i < n_values; i += 1)
       printf("%d\n", array[i]);
 
    /*
     ** 釋放內存並且退出.
     */
    free(array);
    return EXIT_SUCCESS;
}
 
動態復制字符串：
/*
** 用動態分配內存制作一個字符串的一份拷貝。注意：
** 調用程序應該負責檢查這塊內存是否成功分配!這樣
** 做允許調用程序以任何它所希望的方式對錯誤作出反應
*/
#include<stdlib.h>
#include<string.h>
 
char *strdup(charconst *string) {
    char *new_string;
    /*
     ** 請求足夠長度的內存，用於存儲字符串和它的結尾NUL字節.
     */
    new_string = malloc(strlen(string) + 1);
    /*
     ** 如果我們得到內存，就復制字符串.
     */
    if (new_string != NULL)
       strcpy(new_string, string);
    return new_string;
}
該程序將輸入的字符串存儲到緩沖區，每次讀取一行。調用此函數時才可以確定字符串的長度，然後就分配內存用於存儲字符串，最後字符串被復制到新內存，這樣緩沖區又可以用於讀取下一個輸入行。這個函數非常方便，也非常有用，盡管標准沒有提及，但許多環境都把它作為函數庫的一部分。
 
有些C編譯器提供了一個稱為alloca的函數，它與malloc函數不現是在於它在棧上分配內存，而malloc是在堆上分配內存。在棧上分配內存的主要優點是當分配內存的返回時，這塊內存會被自動釋放，這是由棧的工作方式決定的，它可以保證不會出現內存洩漏，但這種方式存在缺點，由於函數返回時被分配的內存將消失，所以它不能用於存儲那些回傳給調用程序的數據。
 

第十章     使用結構和指針（鏈表實現）

單鏈表
/*
** 單鏈表的插入，鏈表為升序
*/
#include<stdlib.h>
#include<stdio.h>
typedefstruct NODE {
    struct NODE *link;
    intvalue;
} Node;
 
#define    FALSE  0
#define TRUE  1
 
/*
* 如果節點插在最前面，則需要使用根指針的值，
* 所以這裡使用了二級指針將根指針的地址也傳遞
* 過去，這樣便於修改根指針的指向
*/
int sll_insert(Node **rootp, int new_value) {
    /*
     * 前驅節點，會成為新節點的前驅節點，也可能為NULL
     */
    Node *previous;
    /*
     * next節點，即第一個大於或等於新節點的節點，最後會
     * 成會新節點的後繼節點，可能為NULL
     */
    Node *next;
    Node *new;//新節點
    previous = NULL;//剛開始時前驅節點指針指向NULL
//初始化後繼節點，剛開始時與根節點一樣指向第一個節點
    next = *rootp;
 
    /*
     ** 如果沒有到達鏈尾，且沒有找到一個大於或等於新節點
     ** 的節點時，繼續往下找
     */
    while (next != NULL && next->value < new_value) {
       previous = next;
       next = next->link;
    }
 
    //動態創建新的節點
    new = (Node *) malloc(sizeof(Node));
    if (new == NULL)
       return FALSE;
    new->value = new_value;
 
    //設定next域，讓next節點成為新節點的下一節點
    new->link = next;
   
    //如果需要在最前面插入時
    if (previous == NULL)
       //此時需要修改根節點的指向，讓它指向新的節點
       *rootp = new;
    else//如果插入是在鏈表的中間或者末尾時
       previous->link = new;
    return TRUE;
}
int main(int argc, char **argv) {
    Node *root = NULL;
    Node **rootp = &root;
    sll_insert(rootp, 2);
    sll_insert(rootp, 5);
    sll_insert(rootp, 3);
    sll_insert(rootp, 0);
    sll_insert(rootp, 1);
    sll_insert(rootp, 4);
    while (root != NULL) {
       printf("%d", root->value);//012345
       root = root->link;
    }
} 

單鏈表的優化插入操作
看上去，把一個節點插入到鏈表的起始位置必須作為一種特殊情況進行處理，因為此時插入新節點需要修改的是指針是根指針，而對於其他任何節點，修改的是前一個節點（previous）的link字段，這兩個看上去不同的操作實際上是一樣的。
消除這種特殊情況的關鍵在於：我們必須認識到，鏈表中的每個節點都有一個指向它的指針。對於第1個節點，這個指針是根指針；對於其他節點，這個指針是前一節點的link字段，相同點是每個節點都有一個指針指向它，至於該指針是不是位於一個節點內部則不重要，我們完全可以將root與節點內部的link指針同等看待，root即可看成某個節點的link字段。

讓我們再次觀察這個鏈表，弄清這個概念，這是第1個節點和指向它的指針：

如果新值插入到第1個節點之前，這個指針就必須進行修改。下面是第2個節點和指向它的指針：

如果新值需要插入到第2個節點之前，那麼前一節點的link指針必須進行修改。

現在我們只需要擁有一個指向插入位置的下一節點的指針（next），以及一個“指向next節點的link字段”的指針（linkp），除此外，我們就不再需要一個用來保存指向插入位置的前一節點的指針（previous），下面是賦值語句（next = *linkp）執行後的各變量情況：

當移動到下一個節點時，我們保存一個“指向next節點的link字段的”指針（linkp），而不是保存一個指向前一個節點的指針（previous）：

注，這裡的linkp並不指向節點本身，與上面實現不現的是，它是指向節點內部的link字段，這是簡化插入操作的關鍵所在，這可以將root指針與節點內的link指針字段同等看待，我們可以用一種和修改節點的link字段完全一樣的方式來修改root變量。插入函數的原型與上面的實現還是一樣，只是將rootp的名稱改成了linkp，因為這裡的實現是讓rootp可以指向其他任何節點內部的link字段，所以就形象的稱為linkp，而不僅僅是根指針了。我們再也不需要previous指針了，因為我們的linkp指針可以負責尋找到需要修改的link字段，下面是實現：
result = sll_insert(&root, 12);
int sll_insert(registerNode **linkp, int new_value) {
    registerNode *next;
    registerNode *new;
 
    next = *linkp;//剛開始時next與root同指向第一個節點
    //如果沒有到達鏈尾且next節點的值小於或等於新節點值時繼續
    while (next != NULL && next->value < new_value) {
       /*
        * 這裡與上面的實現是不一樣的，這裡保存的是節點內link字段的
        * 地址，而不像上面那樣保存的是節點本身，這是簡化的關鍵所在
        */
       linkp = &next->link;
       next = *linkp;
    }
 
    new = (Node *) malloc(sizeof(Node));
    if (new == NULL)
       return FALSE;
    new->value = new_value;
 
    //這個與上面的實現還是一樣，讓當前節點成為新節點的下一節點
    new->link = next;
    /*
     * 即使在空鏈表時，可以將root根指針與節點中的link字段同等看待
     * 鏈表為空時，修改的就是root的指向，否則修改的就是其他節點的
     * link指向
     */
    *linkp = new;
    return TRUE;
}
節點的刪除與查找也可以使用上面這種簡化的操作來實現。
 
 
雙鏈表（非循環） 
雙鏈表的根節點允許我們可以從鏈表的任何一端（第一個節點還是最後一個節點）開始遍歷鏈表。根節點的fwd字段指向鏈表的第1個節點，根節點的bwd字段指向鏈表最後一個節點（如果只有一個節點，則這兩個都指向第一個節點）。如果鏈表為空，這兩個字段都為NULL。鏈表第1個節點的bwd字段和最後一個節點的fwd字段都為NULL。並將根節點與其他節點等同看待，只是value沒有值而已。
 
1、  如果鏈表為空，則新增節點的fwd與bwd字段都為NULL。
2、  如果新增節點位於起始位置，則新增節點的bwd字段為NULL，新節點的fwd字段指向下一節點（next指向的節點），下一節點（next指向的節點）的bwd字段指向這個新的節點。
3、  如果新增節點位於結束位置，則新增節點的fwd字段為NULL，新節點的bwd字段指向前一節點（previous指向的節點），前一節點（previous指向的節點）的fwd字段指向這個新的節點。
4、  如果新增節點位於鏈表中間，則新增節點的fwd字段為下一節點（next指向的節點），新節點的bwd指向前一節點（previous指向的節點），下一節點（next指向的節點）的bwd指向新節點，前一節點（previous指向的節點）的fwd也指向新節點。
 
/*
** 把一個值插入到一個雙鏈表，rootp是一個指向根節點的指針，
** value是欲插入的新值
** 返回值：如果欲插值已存在於鏈表中，函數返回0；如果內存不
** 足，返回-1；如果插入成功，函數返回1。
*/
#include<stdlib.h>
#include<stdio.h>
 
typedefstruct NODE {
    struct NODE *fwd;
    struct NODE *bwd;
    intvalue;
} Node;
 
int dll_insert(Node *rootp, int value) {
    Node *previous;//指向待插入位置的前一節點，
    Node *next;//指向待插入位置的後一節點，
    Node *new;//指向新的節點
 
    previous = rootp;//初始化時指向根節點
    //previous不能為NULL，rootp不能傳遞為NULL
    next = previous->fwd;//初始化時指向第一個節點或NULL
    /*
     * 如果沒有達到鏈尾，且新的值比next值大時繼續向後找
     */
    while (next != NULL && next->value < value) {
       //查看value是否已經存在於鏈表中，如果是就返回
       if (next->value == value) {
           return 0;
       }
       previous = next;
       next = previous->fwd;
    }
 
    new = (Node *) malloc(sizeof(Node));
    if (new == NULL) {
       return -1;
    }
    new->value = value;
 
    if (rootp->fwd == NULL && rootp->bwd == NULL) {//如果鏈表為空
       new->fwd = NULL;
       rootp->fwd = new;
       new->bwd = NULL;
       rootp->bwd = new;
    } elseif (previous == rootp) {//如果插入位置為鏈表首時
       new->fwd = next;
       rootp->fwd = new;
       new->bwd = NULL;
       next->bwd = new;
    } elseif (next == NULL) {//如果插入位置為鏈表尾時
       new->fwd = NULL;
       previous->fwd = new;
       new->bwd = previous;
       rootp->bwd = new;
    } else {
       //如果插入位置為鏈表中間時
       new->fwd = next;
       previous->fwd = new;
       new->bwd = previous;
       next->bwd = new;
    }
    return 1;
}
 
int main(int argc, char **argv) {
    //  Node root = { NULL, NULL, 0 };
 
    /*
     * 為了節省空間，root的值成員是多余的，
     * 可以使用動態分配出來
     *
     * 如果不是動態分配出來的，則可以使用如
     * 下結構來實現：
     * struct DLL_NODE;
     * struct DLL_POINTERS{//根節點結構
     *      struct DLL_NODE * fwd;
     *      struct DLL_NODE * bwd;
     * };
     * struct DLL_NODE{//節點
     *      struct DLL_POINTERS pointers;
     *      int value;
     * };
     *
     */
    Node* root2 = malloc(sizeof(Node) - sizeof(int));
    root2->bwd = NULL;
    root2->fwd = NULL;
    dll_insert(root2, 2);
    dll_insert(root2, 5);
    dll_insert(root2, 3);
    dll_insert(root2, 0);
    dll_insert(root2, 1);
    dll_insert(root2, 4);
    //從前向後遍歷
    Node* tmp = root2->fwd;
    while (tmp != NULL) {
       printf("%d", tmp->value);//012345
       tmp = tmp->fwd;
    }
    //從後向前遍歷
    tmp = root2->bwd;
    while (tmp != NULL) {
       printf("%d", tmp->value);//543210
       tmp = tmp->bwd;
    }
}