状态机系列学习笔记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. 一定要在最后进行