狀态機系列學習筆記02

雙向連結清單

雙向連結清單（又叫雙連結清單）的每個結點中包括兩個指針域，分别指向該結點的前一個結點和後一個結點。

雙向連結清單存儲結構可表示為：

typedef struct node
{
    DATATYPE info;
    //prior用來存儲目前結點相鄰的前一個結點的位址
    //next用來存儲目前結點相鄰的後一個結點的位址
    struct node *prior, *next;
}DINKLIST;           

其中DATATYPE表示結點資料域的類型，它可以是整型、字元型等類型。

對指向雙向連結清單任一結點的指針p，有下面的關系：

p->next->prior=p->prior->next=d

上述語句表示目前結點後面的結點的前一結點是自身，目前結點前面的結點的後面的結點也是自身。

雙向連結清單有三種基本運算：查找、插入和删除

（1） 對雙向連結清單的查找操作。

對雙向連結清單的查找操作要從表頭結點往後依次比較各結點資料域的值，若正是該特定值，則傳回指向結點的指針，否則繼續往後查，直到表尾。

（2） 對雙向連結清單的删除操作。

删除雙向連結清單中結點的基本步驟為：

1. 從連結清單中找到要删除的結點，用指針p指向該結點。
2. 使指針p指向的結點（要删除的結點）的前面的結點指針域指向它後面的結點，即是p指向的結點的next的值賦給p指向的結點的prior成員指向的結點的next成員。
3. 使指針p指向的結點（要删除的結點）的後面的結點指針域指向它前面的結點，即是p指向的結點的prior的值賦給p指向的結點的next成員指向的結點的prior成員。

上面步驟用代碼的形式表示如下。

……//從連結清單中找到要删除的結點，用指針p指向該結點

p->prior->next=p->next;

p->next->prior=p->prior;

（3） 對雙向連結清單的插入操作。

向雙向連結清單中插入新結點，根據其插入的位置，可分為兩種情況。一種是插入到某個結點之後，基本步驟為：

1. 使用malloc函數、calloc函數或realloc函數配置設定記憶體空間，建立一個新結點，用一個指針p0指向這個新結點。
2. 在連結清單中，确定新結點應被插入到哪個結點的後面，用指針p1指向該結點。
3. 使指針p0指向的結點指向p1指向的結點後面的結點，即将指針p1指向的結點的next成員值賦給p0指向的結點的next成員。
4. 使p0指向的結點（新結點）指向p1指向的結點，即将指針p1的值賦給p0指向的結點的prior成員。
5. 使p1指向的結點的下一個結點指向p0指向的結點，即将指針p0的值賦給指針p1指向的結點的下一個結點的prior成員。
6. 使p1指向的結點指向p0指向的結點，即将指針p0的值賦給指針p1指向的結點的next成員。

p0=(struct st *)malloc(sizeof(struct st));

/*找到p0指向的新結點要插入到哪個結點的後面，用指針p1指向該結點*/

……

p0->next=p1->next;

p0->prior=p1;

p1->next->prior=p0;

p1->next=p0;

前面3. 4. 5. 的順序可以互換，但6. 一定要在最後進行。

另一種是将新結點插入到某個結點之前，基本步驟如下：

2. 在連結清單中，确定新結點應被插入到哪個結點的之前，用指針p2指向該結點。
3. 使p0指向的結點指向p2指向的結點，即将指針p2的值賦給p0指向的結點的next成員。
4. 使p0指向的結點指向p2指向的結點的前面的結點，即将指針p2指向的結點的prior值賦給指針p0指向的結點的prior成員。
5. 使p2指向的結點的前面的結點指向指針p0指向的結點，即将指針p0的值賦給p2指向的結點的prior成員指向的結點next成員。
6. 使p2指向的結點指向p0指向的結點，即将指針p0的值賦給指針p2指向的結點的prior成員。

上面的步驟用代碼的形式表示如下。

p0=(struct st *)malloc(sizeof(struct st));

/*找到p0指向的新結點要插入到哪個結點的後面，用指針p1指向該結點*/

……

p0->next=p2;

p0->prior=p2->prior;

p2->prior->next=p0;

p2->prior=p0;

前面的3. 4. 5. 可以互換，但6. 一定要在最後進行