数据结构与算法----双向链表

cmusketeer 2018-10-06 原文

PS：前面已经说过线性表的两种表现形式，一种是顺序，另一种是链式，链式的一种普通表现形式就是加入一个指针，前一个的指针指向后一个结点的地址，那么还有一种形式就是双向链表，里面又加上了一个指针变量，让前指针变量指向直接前驱，后指针变量指向直接后继。

/**
 * 创建结构体
 * */
typedef struct DoubleLink {
    int data;
    struct DoubleLink *prior;
    struct DoubleLink *next;
} DoubleLink, *DoubleLinkL;

创建双向链表并初始化

注：这里我们是只创建了一个空的链表，内部无数据，所以首结点的两个指针变量要为NULL。

/**
 * 初始化
 * */
DoubleLinkL initLink() {
    DoubleLinkL L = (DoubleLinkL) malloc(sizeof(DoubleLink));
    L->next = NULL;
    L->prior = NULL;
    return L;
}

开始插入数据

在插入数据之前我们要考虑一个事情就是，链表中有数据和无数据的插入是否一样，也就是说指针改变是否一致，在左右都有值的时候平时要改变4条线，那么如果只有首结点的话移动几条呢。

其实可以说是移动3条，但画图的话就看到两条。

如图：

：：|：：

首先当只要一个首结点或者在最后一个结点插入的情况下，如第一个图，

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

当前后都有结点的时候，如第二个图

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

整体插入代码就是

int insertLink(DoubleLinkL &L, int pos, int e) {
    DoubleLinkL p = L;
    int i = 0;
    while (p && i < pos-1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos-1) {
        printf("插入失败，下标问题\n");
        return -1;
    }
    DoubleLinkL s = (DoubleLinkL) malloc(sizeof(DoubleLink));
    s->data = e;
    if (p->next == NULL) {
        s->next = p->next;
        s->prior = p;
        p->next = s;
    } else {
        s->next = p->next;
        s->prior = p;
        p->next = s;
        s->next->prior = s;
    }
    return 0;
}

删除图解

对于删除比较简单，在前后都有结点的情况下，如图一，如果本来只要一个结点，前面是首结点的情况下，直接把首结点的next指向NULL即可。（本人画图不怎么样不要在意）

p->next->next->prior=p;//一定要写在该位置。
p->next=p->next->next;

如果首结点后只有一个结点

p->next=NULL;

删除全部代码

int deleteLink(DoubleLinkL &L,int pos,int e){
    DoubleLinkL p = L;
    int i = 0;
    while (p && i < pos-1) {
        p = p->next;
        i++;
    }
    if (!p || i > pos-1) {
        printf("插入失败，下标问题\n");
        return -1;
    }
    if(p->next==NULL){
        p->next=NULL;
    }else{
        p->next->next->prior=p;//一定要写在该位置。
        p->next=p->next->next;
    }
    return 0;
 }

修改和查找

这个修改和查找是比较简单的，直接找到知道该结点修改就完事了，干就对了。

 int getElem(DoubleLinkL L,int pos){
     DoubleLinkL p = L;
     int i = 0;
     while (p && i < pos) {
         p = p->next;
         i++;
     }
     if (!p || i > pos) {
         printf("查找失败，下标问题\n");
         return -1;
     }
     printf("查找的数据：%d\n",p->data);
     return 0;
 }
 int updataLink(DoubleLinkL &L,int pos,int e){
     DoubleLinkL p = L;
     int i = 0;
     while (p && i < pos) {
         p = p->next;
         i++;
     }
     if (!p || i > pos) {
         printf("修改失败，下标问题\n");
         return -1;
     }
     p->data=e;
     return 0;
 }