【数据结构】——双向链表

速通回忆

如果你之前学过链表，可以直接看我下面的这个项目，实现了下面专题中所有内容；

如果你是个新手，建议先不要看下面这个项目，先好好看一下下面每一个部分的代码思路，并尝试自己去写一下

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

/* 学生数据结构体 */
typedef struct{
    char name[20];
    int age;
}stu_demo;

/* 创建双向链表 */
typedef struct stu_l{
    stu_demo stu;
    struct stu_l *pre;
    struct stu_l *next;
}stu_line,*LinkList;

/* 初始化双向链表 */
LinkList LinkListInit(stu_demo demo){
    /* 创建新的节点动态分配存储空间 */
    LinkList temp = (LinkList)malloc(sizeof(stu_line));
    /* 赋值 */
    temp->pre = NULL;
    temp->next = NULL;
    strcpy(temp->stu.name, demo.name);
    temp->stu.age = demo.age;

    return temp;
}

/* 双链表的头插法，将头节点下一位换位新插入的节点 */
/* 双链表的头插法，返回新的头节点 */
LinkList LinkLListCreateH(LinkList l){
    /* 动态分配新节点的空间 */
    LinkList n = (LinkList)malloc(sizeof(stu_line));
    /* 读取要输入的学生信息 */
    printf("头插法\n");
    printf("输入添加的学生姓名：");
    scanf("%s", n->stu.name);
    printf("输入学生年龄：");
    scanf("%d", &n->stu.age);
    /* 将新节点插入到链表中 */
    n->next = l;
    if (l != NULL) {
        l->pre = n;
    }
    n->pre = NULL;
    /* 返回新的头节点 */
    return n;
}

/* 双链表的尾插法，将最后一个节点换为新插入的节点 */
void LinkLListCreateL(LinkList l){
    /* 动态分配节点空间 */
    LinkList n = (LinkList)malloc(sizeof(stu_line));
    LinkList point = l;
    /* 读取要存入的学生信息 */
    printf("尾插法\n");
    n->next = NULL;
    printf("输入添加的学生姓名：");
    scanf("%s",n->stu.name);
    printf("输入学生年龄：");
    scanf("%d",&n->stu.age);
    /* 链表指针指向链表的最后一个节点 */
    while(point->next != NULL)  
        point = point->next;
    /* 将节点放到链表的最后一个位置 */
    point->next = n;
    n->pre = point;
}

/* 遍历显示双链表的所有节点数据 */
void LinkListShow(LinkList l){
    LinkList point = l;
    printf("|\t姓名\t|\t年龄\t|\n");
    while(point!=NULL){
        printf("|\t%s\t|\t%d\t|\n",point->stu.name,point->stu.age);
        point = point->next;
    }
}

/* 遍历显示双链表的所有节点数据 */
void LinkListInser(LinkList l, char *stu_name){
    /* 动态分配节点空间 */
    LinkList n = (LinkList)malloc(sizeof(stu_line));
    LinkList point = l;
    /* 读取要存入的学生信息 */
    n->next = NULL;
    printf("输入添加的学生姓名：");
    scanf("%s",n->stu.name);
    printf("输入学生年龄：");
    scanf("%d",&n->stu.age);
    /* 遍历找到与name名字相符的节点位置 */
    while(point != NULL){
        if(strcmp(point->stu.name, stu_name) == 0){
            n->next = point->next;
            point->next = n;
            point->next->pre = n;
            n->pre = point;
            return ;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

void LinkListReplace(LinkList l, char *stu_name){
    LinkList point = l;
    /* 遍历找到与name名字相符的节点位置 */
    while(point != NULL){
        if(strcmp(point->stu.name, stu_name) == 0){
            printf("请输入对%s同学,修改后的年龄:",stu_name);
            scanf("%d",&point->stu.age);
            return ;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

void LinkListDelete(LinkList l, char *stu_name){
    LinkList point = l;
    LinkList temp = (LinkList)malloc(sizeof(stu_line));
    /* 遍历找到与name名字相符的节点位置 */
    while(point != NULL){
        if(strcmp(point->stu.name, stu_name) == 0){
            temp = point;
            point->pre->next = point->next;
            point->next->pre = point->pre;
            free(temp);
            return ;
        }
        point = point->next;
    }
    printf("查询无结果\n");
}

int main(){
    /* 获取双向链表的第一个学生信息（双向链表第一个节点的数据段不为空） */
    stu_demo demo;
    printf("请输入学生姓名：");
    scanf("%s",demo.name);
    printf("请输入学生年龄：");
    scanf("%d",&demo.age);
    /* 初始化双向链表 */
    LinkList stu_data = LinkListInit(demo);
    /* 添加数据到双向链表 */
    stu_data = LinkLListCreateH(stu_data);
    LinkLListCreateL(stu_data);
    /* 遍历输出节点 */
    LinkListShow(stu_data);
    /* 在某个节点后插入一个节点 */
    LinkListInser(stu_data, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu_data);
    /* 遍历替换到与名字相同的节点的信息 */
    LinkListReplace(stu_data, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu_data);
    /* 遍历删除节点 */
    LinkListDelete(stu_data, "liu");
    /* 遍历输出节点 */
    LinkListShow(stu_data);
    free(stu_data);
    return 0;
}

双向链表的概念

双向链表的存在是为了解决单链表的缺点，让链表更加优秀。
单链表是结点中只有一个指向其后继的指针，具有单向性，当需要搜索大量数据时候，就必须要多次进行从头开始的遍历了，这样不是很便利

对此在单链表的基础上，产生了双向链表的概念，即： 在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表

一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链

双向链表的结点设计

pre代表的是前驱指针，它永远指向当前结点的前一个结点
注意，如果当前结点是头结点，则pre指针为空

next代表的是后继指针，它永远指向当前结点的下一个结点
注意，如果当前结点是尾结点，则next指针为空

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)

双链表的创建

双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的

//创建双链表
line* initLine(line * head){
    int number,pos=1,input_data;
    //三个变量分别代表结点数量，当前位置，输入的数据
    printf("请输入创建结点的大小\n");
    scanf("%d",&number);
    if(number<1){return NULL;} //输入非法直接结束
    //////头结点创建///////
    head=(line*)malloc(sizeof(line));
    head->pre=NULL;
    head->next=NULL;
    printf("输入第%d个数据\n",pos++);
    scanf("%d",&input_data);
    head->data=input_data;
  
    line * list=head;
    while (pos<=number) {
        line * body=(line*)malloc(sizeof(line));
        body->pre=NULL;
        body->next=NULL;
        printf("输入第%d个数据\n",pos++);
        scanf("%d",&input_data);
        body->data=input_data;
        
        list->next=body;
        body->pre=list;
        list=list->next;
    }
    return head;
}

双向链表的插入操作

//插入数据
line * insertLine(line * head,int data,int add){
    //三个参数分别为：进行此操作的双链表，插入的数据，插入的位置
    //新建数据域为data的结点
    line * temp=(line*)malloc(sizeof(line));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;
    //插入到链表头，要特殊考虑
    if (add==1) {
        temp->next=head;
        head->pre=temp;
        head=temp;
    }else{
        line * body=head;
        //找到要插入位置的前一个结点
        for (int i=1; i<add-1; i++) {
            body=body->next;
        }
        //判断条件为真，说明插入位置为链表尾
        if (body->next==NULL) {
            body->next=temp;
            temp->pre=body;
        }else{
            body->next->pre=temp;
            temp->next=body->next;
            body->next=temp;
            temp->pre=body;
        }
    }
    return head;
}

双向链表的删除操作

//删除元素
line * deleteLine(line * head,int data){
    //输入的参数分别为进行此操作的双链表，需要删除的数据
    line * list=head;
    //遍历链表
    while (list) {
        //判断是否与此元素相等
        //删除该点方法为将该结点前一结点的next指向该节点后一结点
        //同时将该结点的后一结点的pre指向该节点的前一结点
        if (list->data==data) {
            list->pre->next=list->next;
            list->next->pre=list->pre;
            free(list);
            printf("--删除成功--\n");
            return head;
        }
        list=list->next;
    }
    printf("Error:没有找到该元素，没有产生删除\n");
    return head;
}

双向链表的遍历

利用next指针逐步向后进行索引即可，注意判断这里，我们既可以用while(list)的操作直接判断是否链表为空，也可以使用while(list->next)的操作判断该链表是否为空

//遍历双链表,同时打印元素数据
void printLine(line *head){
    line *list = head;
    int pos=1;
    while(list){
        printf("第%d个数据是:%d\n",pos++,list->data);
        list=list->next;
    }
}