首页  /  数据结构教程  /  双向链表二  /  

双向链表二

点击打开在线编译器,边学边练

1.   双向链表的插入操作

如图所示:

41.png

对于每一次的双向链表的插入操作,我们首先需要创建一个独立的结点并通过malloc操作开辟相应的空间,其次我们选中这个新创建的独立节点,将其的pre指针指向所需插入位置的前一个结点,同时,其所需插入的前一个结点的next指针修改指向为该新的结点,同理,该新的结点的next指针将会指向一个原本的下一个结点,而修改下一个结点的pre指针为指向新结点自身,这样的一个操作我们称之为双向链表的插入操作。

其代码可以表示为:

//插入数据
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;
}


2.   双向链表的删除操作

如图:

42.png


删除操作的过程是:选择需要删除的结点,选中这个结点的前一个结点,将前一个结点的next指针指向自己的下一个结点,同时,选中该节点的下一个结点,将下一个结点的pre指针修改指向为自己的上一个结点,这样产生的效果就是在进行遍历的时候直接将这一个结点给跳过了。

在这样的指针修改操作之后,我们释放删除结点,归还空间给内存,这样的操作我们称之为双链表的删除操作。

其代码可以表示为:

//删除元素
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;
}


3   双向链表的遍历

如同单链表的遍历一样,利用next指针逐步向后进行索引即可,注意判断这里,我们既可以用while(list)的操作直接判断是否链表为空,也可以使用while(list->next)的操作判断该链表是否为空,其下一节点为空和本结点是否为空的判断条件是一样的效果,当然了,善用双向链表的pre指针进行有效的遍历也是值得去尝试的。

其简单的代码可以表示为:

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


4.   题目

双向链表的单独训练数据并不是很多,在网上的资料相比单链表也是偏少,不过我们在熟悉原理之后可以同单链表的题目,可以尝试使用双链表进行做题,如下题:

1676题    1585题  


5.   本题目案例代码

#include<stdio.h>
#include<stdlib.h>
typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line;
//分别表示该结点的前驱(pre),后继(next),以及当前数据(data)

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

//创建双链表
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;
}

int main(){
    line *head=NULL;
    printf("创建双链表操作\n"); 
    head=initLine(head);
    printLine(head);
//////////create line////////////
	printf("插入操作\n"); 
    head=insertLine(head,40,2);     //为了简化直接写参数了
    printLine(head);
//////////insert Line////////////
	printf("删除操作\n"); 
    head=deleteLine(head,2);       //为了简化直接写参数了
    printLine(head);
//////////delete Line////////////  
    return 0;
}

 



上一课:双向链表一 下一课:循环链表一
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记