双向链表和双向循环链表

双向链表

线性表-双向链表的结点结构：

双向链表结点结构.png

带头结点的双向链表：

非空的双向链表-带头结点.png

1.双向链表初始化

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

//1 双向链表初始化
Status creatLinkList(LinkList *L){
    
    (*L) = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;//这3行是初始化头结点，头结点可以不赋值，因为始终不会打印头结点
    
    LinkList p = *L;
    for (int i = 0; i < 10; i++) {
        //1.创建新结点temp
        LinkList temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) return ERROR;
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        //2.为temp建立一个双向链表关系
        p->next = temp;
        temp->prior = p;
        p = p->next;
    }
    
    
    return  OK;
}

2.遍历双向链表

void display(LinkList L) {
    LinkList temp = L->next;
    if (temp == NULL) {
        printf("打印的双向链表为空!\n\n");
        return ;
    }
    printf("双向链表内容:  ");
    while (temp) {
        printf("%d   ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

2.双向链表插入

Status ListInsert(LinkList *L, int i, ElemType data) {
    
    //1.插入位置不合法，为0或为负数
    if (i < 1) return ERROR;
    
    //2.新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    //3.将p指向头结点
    LinkList p = *L;
    
    //4.找到插入的位置i直接的结点
    for (int j = 1; j < i && p; j++) {
        p = p->next;
    }
    
    //5.如果插入的位置超过链表本身的长度
    if (p == NULL) {
        return ERROR;
    }
    
    //6.判断插入位置是否为链表尾部
    if (p -> next == NULL) {
        p->next =temp;
        temp->prior = p;
    }else {
        temp->next = p->next;
        p->next->prior = temp;
        p->next = temp;
        temp->prior = p;
    }

    return OK;
}

4.删除双向链表指定位置上的结点

Status ListDelete(LinkList *L, int i, ElemType *e) {
    int k = 1;
    LinkList p = (*L);
    
    //1.判断双向链表是否为空，如果为空则返回ERROR;
    if (*L == NULL) {
        return ERROR;
    }
    
    //2.将指针p移动到i的位置
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>i,或者p == NULL 则返回ERROR
    while (k > i || p == NULL) {
        return ERROR;
    }
    
    //4.创建临时指针delTemp 指向要删除的结点，并将要删除的结点的data 赋值给*e，带回到main函数
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5.p->next 等于要删除的结点的下一个结点
    p->next = delTemp->next;
    
    //6.如果要删除结点的下一个结点不为空，则将要删除的下一个结点的前驱指向p
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    //7.删除delTemp结点
    free(delTemp);

    return OK;
}

5.删除双向链表指定的元素

Status LinkListDeleteVAL(LinkList *L, int data) {
    
    LinkList p = *L;//1.创建临时结点指向首结点
    //2.遍历双向链表
    while (p) {
        //3.判断当前结点的数据域和data是否相等，若相等则删除该结点
        if (p->data == data) {
            //4.修改被删除点的前驱结点的后继指针 = 删除结点的后继指针
            p->prior->next = p->next;
            if (p->next != NULL) {//5.判断是否为尾结点，若不是尾结点
                p->next->prior = p->prior;//则删除结点的后继结点的前驱结点 = 删除结点的前驱结点
            }
            free(p);//6.删除delTemp结点
            break;
        }
        p = p->next;//7.若数据域不相等则执行循环操作
    }
    return OK;
}
//6.在双向链表中查找元素
int selectElem(LinkList L,ElemType elem) {
    LinkList p = L->next;
    
    int i = 1;
    while (p) {
        
        if (p->data == elem) {
            return i;
        }
        i++;
        p = p->next;
    }

    return -1;
}

7.在双向链表中更新结点

Status replaceLinkList(LinkList *L,int index, ElemType newElem) {
    LinkList p = (*L)->next;
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    p->data = newElem;
    return OK;
}

双向链表main函数

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 双向链表!\n");
    Status iStatus = 0;
    LinkList L;
    int temp,item,e;
    iStatus = creatLinkList(&L);
    display(L);
    
    printf("请输入插入的位置 元素\n");
    scanf("%d %d",&temp,&item);
    iStatus = ListInsert(&L, temp, item);
    printf("插入数据，打印链表：\n");
    display(L);
    
    printf("请输入删除的位置\n");
    scanf("%d",&temp);
    iStatus = ListDelete(&L, temp, &e);
    printf("删除元素: 删除位置为%d,data = %d\n",temp,e);
    printf("删除操作之后的,双向链表:\n");
    display(L);
    
    printf("请输入你要删除的内容\n");
    scanf("%d",&item);
    iStatus = LinkListDeleteVAL(&L, item);
    printf("删除指定data域等于%d的结点,双向链表:\n",item);
    printf("删除操作之后的,双向链表:\n");
    display(L);

    
    printf("请输入你要查找的内容\n");
    scanf("%d",&item);
    ElemType index = selectElem(L, item);
    printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",item,index);

    printf("请输入你要更新的结点以及内容\n");
    scanf("%d %d",&temp,&item);
    iStatus = replaceLinkList(&L, temp, item);
    printf("更新结点数据后的双向链表:\n");
    display(L);
    
    
    return 0;
}

双向循环链表

线性表-双向循环链表的结点结构：

双向循环链表结点结构.png

空的双向循环链表：

[图片上传中...(非空的双向循环链表.png-fdaca-1588350609674-0)]
非空的双向循环链表：
非空的双向循环链表.png

1 双向循环链表初始化

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

//1 双向循环链表初始化
Status  creatLinkList(LinkList *L){

    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) {
        return ERROR;
    }

    (*L)->next = (*L);
    (*L)->prior = (*L);

    
    //新增数据
    Node *p,*temp = NULL;
    p = *L;
    
    for (int i = 0; i < 10; i++) {
        temp = (LinkList)malloc(sizeof(Node));
        temp->data = i;
        temp->prior = p;
        p->next = temp;
        p = temp;
    }
    
    p->next = (*L);
    (*L)->prior = temp;
    
    return OK;
}

2.遍历双向循环链表

Status Display(LinkList L) {
    if (L == NULL) {
        printf("打印的双向循环链表为空!\n\n");
        return ERROR;
    }
    printf("双向循环链表内容:  ");

    
    LinkList p = L->next;
    while (p != L) {
        printf("%d    ",p->data);
        p = p->next;
    }
    printf("\n");
    
    return OK;
}

3.双向循环链表插入元素

Status LinkListInsert(LinkList *L, int index, ElemType e){
    
    //1.创建指针p,指向双向链表头
    LinkList p = (*L);
    int i = 1;
    //2.双向循环链表为空,则返回error
    if (*L == NULL) {
        return ERROR;
    }
    //3.找到插入前一个位置上的结点p
    while (i < index && p->next != *L) {
        p = p->next;
        i++;
    }
    //4.如果i>index 则返回error
    if (i > index) {
        return ERROR;
    }
    //5.创建新结点temp
    LinkList temp = (LinkList)malloc(sizeof(Node));
    //6.temp 结点为空,则返回error
    if (temp == NULL) {
        return ERROR;
    }
    //7.将生成的新结点temp数据域赋值e.
    temp->data = e;
    //8.将结点temp 的前驱结点为p;
    temp->prior = p;
    //9.temp的后继结点指向p->next;
    temp->next = p->next;
    //10.p的后继结点为新结点temp;
    p->next = temp;
    //如果temp 结点不是最后一个结点
    if (*L != temp->next) {
        temp->next->prior = temp;
    }else {
        (*L)->prior = temp;
    }
    
    return OK;
}

4.双向循环链表删除结点

Status  LinkListDelete(LinkList *L,int index,ElemType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;
    
    if (*L == NULL) {
        return ERROR;
    }
    //情况1：如果删除到只剩下首元结点了,则直接将*L置空;
    if (temp->next == *L) {
        free(*L);
        (*L) == NULL;
        return OK;
    }
    //情况2：如果删除到剩下不止首元结点，还有其他结点
    //1.找到要删除的结点
    while (i < index) {
        temp = temp->next;
        i++;
    }
    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    //3.修改被删除结点的前驱结点的后继指针
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针
    temp->next->prior = temp->prior;
    //5.释放结点temp
    free(temp);
    
    return OK;
}

双向循环链表main函数

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, 双向循环链表!\n");
    
    LinkList L;
    Status iStatus;
    ElemType temp,item;
    
    iStatus = creatLinkList(&L);
    printf("双向循环链表初始化是否成功(1->YES)/ (0->NO):  %d\n\n",iStatus);
    Display(L);
    
    printf("输入要插入的位置和数据用空格隔开：");
    scanf("%d %d",&temp,&item);
    iStatus = LinkListInsert(&L,temp,item);
    Display(L);
    
    printf("输入要删除位置：");
    scanf("%d",&temp);
    iStatus = LinkListDelete(&L, temp, &item);
    printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);
    Display(L);
    
    
    return 0;
}

Demo:双向链表和双向循环链表