本文共 3133 字，大约阅读时间需要 10 分钟。

双链表技术指南

结点类型定义

在单链表的基础上，双链表的结点内增加了一个指针域，用于指向前一个结点。这种结构使得双链表能够在常规单链表的基础上实现前向和逆向遍历。

双链表初始化

初始化一个带头结点的双链表。以下代码示例展示了如何初始化一个双链表：

#include 
   
    using namespace std;typedef struct DNode {    int data;    struct DNode *prior, *next;} *DLinkList;void InitDLinkList(DLinkList &L) {    L = (DNode *)malloc(sizeof(DNode));    if (L == NULL) {        cout << "内存分配失败！" << endl;        return;    }    L->prior = NULL;    L->next = NULL;}int main() {    DLinkList L;    InitDLinkList(L);    return 0;}
   

创建双链表

创建一个长度为10的双链表。以下代码示例使用尾插法建立双链表：

#include 
   
    using namespace std;typedef struct DNode {    int data;    struct DNode *prior, *next;} *DLinkList;void createDLinkList(DLinkList &L) {    DNode *r = L; // 指向最后一个节点    for (int i = 0; i < 10; i++) {        DNode *p = (DNode *)malloc(sizeof(DNode));        p->data = i + 1;        p->next = r->next;        p->prior = r;        r->next = p;        r = p;    }}int main() {    DLinkList L;    InitDLinkList(L);    createDLinkList(L);    DNode *p = L->next;    while (p) {        cout << p->data << " ";        p = p->next;    }    return 0;}
   

查找指定节点

找到第i个节点，并打印输出data域，默认头节点编号为0。以下代码示例实现了查找功能：

#include 
   
    using namespace std;typedef struct DNode {    int data;    struct DNode *prior, *next;} *DLinkList;DNode *getElem(DLinkList L, int i) {    DNode *p = L;    int j = 0;    if (i < 0) {        return NULL;    }    while (p != NULL && j < i) {        p = p->next;        j++;    }    return p;}int main() {    DLinkList L;    InitDLinkList(L);    createDLinkList(L);    DNode *q = getElem(L, 7);    if (q == NULL) {        cout << "查找失败，请检查编号输入是否有误！";    } else {        cout << q->data;    }    return 0;}
   

插入节点

在第i个节点后插入一个新节点，并插入遍历之后的链表。以下代码示例实现了插入功能：

#include 
   
    using namespace std;typedef struct DNode {    int data;    struct DNode *prior, *next;} *DLinkList;void inDLinkList(DLinkList &L, int i, int val) {    DNode *p = getElem(L, i);    if (p == NULL) {        cout << "插入失败，请检查编号是否有误！";        return;    }    DNode *q = (DNode *)malloc(sizeof(DNode));    q->data = val;    if (p->next == NULL) {        q->next = p->next;        q->prior = p;        p->next = q;    } else {        q->next = p->next;        q->prior = p;        p->next->prior = q;        p->next = q;    }}int main() {    DLinkList L;    InitDLinkList(L);    createDLinkList(L);    inDLinkList(L, 7, 11);    DNode *p = L->next;    while (p) {        cout << p->data << " ";        p = p->next;    }    return 0;}
   

删除节点

删除第i(i>0)个结点，并打印链表。以下代码示例实现了删除功能：

#include 
   
    using namespace std;typedef struct DNode {    int data;    struct DNode *prior, *next;} *DLinkList;void deDLinkList(DLinkList &L, int i) {    DNode *p = getElem(L, i);    if (p == NULL || i == 0) {        cout << "删除失败，请检查编号！";        return;    } else if (p->next == NULL) {        p->prior->next = NULL;        free(p);    } else {        p->prior->next = p->next;        p->next->prior = p->prior;        free(p);    }}int main() {    DLinkList L;    InitDLinkList(L);    createDLinkList(L);    deDLinkList(L, 2);    DNode *p = L->next;    while (p) {        cout << p->data << " ";        p = p->next;    }    return 0;}
   

转载地址：http://oumq.baihongyu.com/