数据结构(4)-线性表之双向链表

2020-04-07 本文已影响0人 xxxxxxxx_123

定义

在单向链表的元素中，添加一个指向前驱元素(也就是前一个元素)的指针域。元素中既有指向前驱元素的指针，又有指向后继元素的指针。这种形式的链表叫做双向链表。

其存储结构如下：

typedef int ElementType;

typedef struct DouNode{
    ElementType data;
    struct DouNode *next;
    struct DouNode *prior;
}DouNode;

typedef struct DouNode * linkList;

双向链表

初始化双向链表

TStatus InItDoubleLinkList(LinkList *dl) {
    (*dl) = (LinkList)malloc(sizeof(DouNode));
    if (*dl == NULL) {
        return T_ERROR;
    }
    (*dl)->data = -1;
    (*dl)->next = NULL;
    (*dl)->prior = NULL;
    return T_OK;
}

双向插入.png

插入双向链表的元素

双向链表由于存在两个指针域，所以插入的时候需要对其进行处理。

在第i个位置插入元素，大概步骤如下：

创建新结点q
遍历链表，找到需要插入的位置的前一个元素p
将新元素q的前驱指向p，后继指向p->next
将p->next的前驱指向新元素q
将p的后继指向新元素q

TStatus InsertElement(LinkList *dl, int i, ElementType e) {
    if (*dl == NULL) {
        return T_ERROR;
    }
    LinkList p = (*dl);
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    if (p == NULL || j > i) {
        return T_ERROR;
    }
    
    // 新插入的元素
    LinkList q = (LinkList)malloc(sizeof(DouNode));
    q->data = e;
    
    // q的指向
    q->next = p->next;
    q->prior = p;
    
    // q后继元素的指向
    if (p->next != NULL) {
        p->next->prior = q;
    }
    
    // p的指向
    p->next = q;
    
    return T_OK;
}

删除双向链表的元素

双向删除.png

删除第i个位置的元素，大概步骤如下：

遍历链表，找到想要删除的位置的前一个元素p
创建新结点q，将要删除的元素赋值给p
将p->next指向q->next，将q->next的前驱指向p
释放q

TStatus DeleteElement(LinkList *dl, int i, ElementType *e) {
    if (*dl == NULL) {
        return T_ERROR;
    }
    LinkList p = (*dl);
    int j = 1;
    // 1234
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    if (p == NULL || j > i) {
        return T_ERROR;
    }
    
    LinkList delQ = p->next;
    *e = delQ->data;
    p->next = delQ->next;
    if (delQ->next != NULL) {
        delQ->next->prior = p;
    }
    
    free(delQ);
    
    return T_OK;
}

也可以通过数据来删除具有相同的数据的元素，此处我们只考虑链表中最多只有一个元素数据为传入的数据。

TStatus DeleteElementWithData(LinkList *dl, ElementType e) {
    if (*dl == NULL) {
        return T_ERROR;
    }
    LinkList p = (*dl);
    
    while (p != NULL) {
        if (p->data == e) {
            break;
        }
        p = p->next;
    }
    
    if (p == NULL) {
        return T_ERROR;
    }
    // 要删除的前一个元素
    LinkList preQ = p->prior;
    preQ->next = p->next;
    if (p->next != NULL) {
        p->next->prior = preQ;
    }
    free(p);
    
    return T_OK;
}

获取元素

获取双向链表第i个位置的元素。

遍历链表找到第i个位置前一个位置的元素p
容错判断
返回p->next

TStatus GetElement(LinkList *dl, int i, ElementType *e) {
    if (*dl == NULL || i < 1) {
        return T_ERROR;
    }
    
    LinkList p = (*dl);
    int j = 1;
    
    while (p && j < i) {
        p = p->next;
        j += 1;
    }
    
    if (p->next == NULL && j > i) {
        return T_ERROR;
    }
    
    *e = p->next->data;
    
    return T_OK;
}

整表创建

采用尾插法整表创建双向链表:

初始化链表
遍历传入的数据，循环创建结点，加到链表的尾部

TStatus createDoubleLinkList(LinkList *dl, int arr[], int size) {
    *dl = (LinkList)malloc(sizeof(DouNode));
    if (*dl == NULL) {
        return T_ERROR;
    }
    (*dl)->data = -1;
    (*dl)->prior = NULL;
    (*dl)->next = NULL;
    
    LinkList r = (*dl);
    LinkList p;
    for (int i = 0; i < size; i++) {
        int e = arr[i];
        p = (LinkList)malloc(sizeof(DouNode));
        if (p == NULL) {
            return T_ERROR;
        }
        p->data = e;
        p->prior = r;
        p->next = NULL;
        r->next = p;
        r = p;
    }
    
    return T_OK;
}

双向循环链表

双向循环链表的概念其实和单向循环链表类似，也是将链表中最后一个结点的next针由空指针改为指向头指针指向的元素，不同的是我们还需要将头指针指向的元素的前驱指针prior指向最后一个结点，这样链表就形成了一个环。

双向循环.png

初始化双向循环链表

初始化双向循环链表的时候，需要将自己的next和prior都指向自己。

TStatus InItDoubleLinkList(LinkList *dl) {
    (*dl) = (LinkList)malloc(sizeof(DouNode));
    if (*dl == NULL) {
        return T_ERROR;
    }
    (*dl)->data = -1;
    (*dl)->next = (*dl);
    (*dl)->prior = (*dl);
    return T_OK;
}

双向循环链表删除元素

TStatus DeleteElement(LinkList *dl, int i, ElementType *e) {
    if (*dl == NULL) {
        return T_ERROR;
    }
    
    LinkList p = (*dl);
    int j = 1;
    
    // 找到需要删除的位置的前一个位置
    while (p && j < i && p->next != (*dl)) {
        p = p->next;
        j += 1;
    }
    
    if (p->next == NULL || j > i) {
        return T_ERROR;
    }
    
    LinkList delQ = p->next;
    *e = delQ->data;
    delQ->prior = p;
    p->next = delQ->next;
    free(delQ);
    
    return T_OK;
}

可以看出来，双向循环链表和双向链表的操作类似，只是多了循环的相关处理。

线性表总结

线性表是零个或者多个具有相同类型的数据元素的有限序列。

线性表的存储结构：

顺序存储结构
链式存储结构
- 单链表
- 静态链表
- 循环链表
- 双向链表