线性表-双向链表与双向循环链表

双向链表

双向链表示意图如下：

非空的双向链表.jpg

数据结构定义

typedef struct Node {
    struct Node *next;
    struct Node *pre;
    ElemType data;
}Node;

typedef Node * LinkList;

创建双向链表

Status CreateList(LinkList * list) {
    *list = (LinkList)malloc(sizeof(Node));
    if (NULL == list) {
        return ERROR;
    }
    (*list)->pre = NULL;
    (*list)->next = NULL;
    (*list)->data = -1;
    
    LinkList p = *list;
    for (int i = 0; i < 10; i++) {
        LinkList tmp = (LinkList)malloc(sizeof(Node));
        tmp->data = i;
        p->next = tmp;
        tmp->pre = p;
        p = tmp;
    }
    return OK;
}

双向链表插入元素

Status InsertList(LinkList *list, int i, ElemType data) {
    if (i < 1) {
        return ERROR;
    }
    
    LinkList node = (LinkList)malloc(sizeof(Node));
    node->data = data;
    node->pre = NULL;
    node->next = NULL;
    
    LinkList tmp = *list;
    for (int j = 1; j < i && tmp; j++) {
        tmp = tmp->next;
    }
    
    if (NULL == tmp) {
        return ERROR;
    }
    
    if (NULL == tmp->next) {
        tmp->next = node;
        node->pre = tmp;
    } else {
        node->next = tmp->next;
        tmp->next->pre = node;
        node->pre = tmp;
        tmp->next = node;
    }
    return OK;
}

双向链表删除元素

Status Delete(LinkList *list, int i, ElemType *e) {
    if (i < 1 || NULL == list) {
        return ERROR;
    }
    
    LinkList p = *list;
    for (int j = 1; j < i && p; j++) {
        p = p->next;
    }
    
    if (NULL == p) {
        return ERROR;
    }
    
    LinkList deletNode = p->next;
    *e = deletNode->data;
    
    p->next = deletNode->next;
    if (p->next) {
        p->next->pre = p;
    }
    free(deletNode);
    return OK;
}

双向链表打印元素

void PrintList(LinkList list) {
    LinkList p = list->next;
    if (NULL == p) {
        printf("链表为空\n");
        return;
    }
    printf("链表数据为：\n");
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
}

双向链表删除指定元素

Status LinkListDeletVAL(LinkList *list, int data) {
    LinkList p = *list;
    while (p) {
        if (p->data == data) {
            p->pre->next = p->next;
            if (p->next != NULL) {
                p->next->pre = p->pre;
            }
            free(p);
           
        }
        p = p->next;
    }
    return OK;
}

双向循环链表

双向循环链表示意图如下：

空的双向循环链表.jpg 非空双向循环链表.jpg

数据结构定义（同上）

typedef struct Node {
    struct Node *next;
    struct Node *pre;
    ElemType data;
}Node;

typedef Node * LinkList;

双向循环链表创建元素

Status CreateList(LinkList * list) {
    *list = (LinkList)malloc(sizeof(Node));
    if (NULL == list) {
        return ERROR;
    }
    (*list)->pre = *list;
    (*list)->next = *list;
    (*list)->data = -1;
    
    LinkList p = *list;
    for (int i = 0; i < 10; i++) {
        LinkList tmp = (LinkList)malloc(sizeof(Node));
        tmp->data = i;
        
        p->next = tmp;
        tmp->pre = p;
        tmp->next = *list;
        (*list)->pre = tmp;
        p = tmp;
    }
    return OK;
}

双向循环链表插入元素

Status InsertList(LinkList *list, int i, ElemType data) {
    if (i < 1) {
        return ERROR;
    }
    
    LinkList node = (LinkList)malloc(sizeof(Node));
    node->data = data;
    node->pre = NULL;
    node->next = NULL;
    
    LinkList tmp = *list;
    for (int j = 1; j < i && tmp; j++) {
        tmp = tmp->next;
    }
    node->next = tmp->next;
    tmp->next->pre = node;
    node->pre = tmp;
    tmp->next = node;
    return OK;
}

双向循环链表删除结点

Status Delete(LinkList *list, int i, ElemType *e) {
    if (i < 1 || NULL == list) {
        return ERROR;
    }
    
    LinkList p = *list;
    for (int j = 1; j < i && p; j++) {
        p = p->next;
    }
    
    LinkList deletNode = p->next;
    *e = deletNode->data;
    
    p->next = deletNode->next;
    p->next->pre = p;
    free(deletNode);
    return OK;
}

双向循环链表与双向链表的基本算法实现，差异很小~