当前位置:   article > 正文

双向链表的实现--C 语言版,详细讲解+代码实现_双向链表建立c语言代码

双向链表建立c语言代码

双链表的实现–C 语言版,详细讲解+代码实现



前言

数据结构继续学习,这次进行,双链表的学习。


提示:以下是本篇文章正文内容,下面案例可供参考

一、双链表是什么

双链表是在单链表的基础上拓展出来的,单链表是一个结点中包含两部分,分别是数据和下一个结点的指针。
而双链表则是一个结点包含三个部分,分别是结点存储的数据,结点的下一个结点骶椎的指针,和结点的上一个结点的位置的指针。

二、使用步骤

1.定义结构体

双链表的结构体相比于单链表,实际上就是多了一个前一个结点的指针,其余并没有变化,还是数据和下一个结点的指针。

typedef struct Node
{
    int data;
    struct Node* pre;
    struct Node* next;
}Node;
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

2.双链表的初始化

所谓初始化就是定义一个头节点,将其中所容纳的数据定义为链表的长度,并作出两个空指针

//初始化
Node* init(){
    Node* node=(Node*)malloc(sizeof(Node));
    node->pre=NULL;
    node->next=NULL;
    node->data=0;
    return node;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

3.头插法

头插法,一如既往的将新数据插入到头节点后面。
步骤:
1. 初始化一个结点,并将数据赋值给结点的data
2. 将结点的next指针指向头节点的next的结点,并将pre指针指向头节点
3. 将头节点的next更正为当前结点的指针。
4. 将头节点中的数据+1,意为链表的长度+1

//头插法
void head_insert(Node* node,int data){
    Node* curnode = (Node*)malloc(sizeof(Node));
    curnode->data=data;
    curnode->pre = node;
    curnode->next = node->next;
    node->next=curnode;
    node->data++;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

4. 尾插法

尾插法总是比头插法难一点,双链表也不例外
尾插法就是将数据插入到链表的尾部,然后将链表的长度+1
步骤:
1. 初始化两个结点,一个结点作为当前结点用来存储新的数据,另一个结点用来循环
2. 对用来循环的结点进行循环,在循环中判断结点的next指针是否为空,为空说明当前结点已经到了单链表的尾部。
3. 此时,将数据赋予新的结点,并将循环的结点的next指向新的结点,同时新的结点的前置指针指向循环结点。
4. 链表的长度+1.

//尾插法
void tail_insert(Node* node,int data){
    Node* prenode = node->next;
    Node* curnode=(Node*)malloc(sizeof(Node));
    curnode->data = data;
    while(prenode){
        if(prenode->next==NULL){
            curnode->pre = prenode;
            curnode->next= NULL;
            prenode->next = curnode;
            node->data++;
            break;
        }
        prenode=prenode->next;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

5.删除某个结点

删除结点的步骤基本上和单链表没有区别,只是多了一个pre指针的指向。
1. 删除的过程中,首先初始化两个指针,指针1用来辅助,指针2用来循环和判断。
2. 对指针2进行循环,同时一直保持指针1在指针2的前一个结点,当指针2的data等于要删除的数据时,将指针1指向当前结点的next,并让指针2的next的pre指针指向指针1。(其中可以增加一个指针2的next是否为空的情况)
3. 当判定到指针2的next指针为空时,结束循环,说明链表中并不存在该数据
4. 链表的长度-1

//删除
void delete(Node* node , int data){
    Node* prenode = (Node*)malloc(sizeof(Node));
    Node* curnode = (Node*)malloc(sizeof(Node));
    prenode = node;
    curnode = node->next;
    while(curnode){
    if(curnode->data==data){
            prenode->next = curnode->next;
            curnode->next->pre = prenode;
            node->data--;
            break;
        }
        if(curnode->next==NULL){
            break;
        }
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

6. 遍历链表

双链表遍历就真的和单链表如出一辙了,感觉真的是一点变化都没有的那种。
步骤:
1. 和单链表一样,首先初始化一个结点用来遍历
2. 将首元结点赋给刚创建的结点,然后对利用该节点对链表进行循环输出,直到到达链表的尾部。

//遍历
void print(Node* node){
    Node* curnode = (Node*)malloc(sizeof(Node));
    curnode = node->next;
    while(curnode){
        printf("%d\n",curnode->data);
        curnode = curnode->next;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

总结

双链表和单链表也基本一样的了,就是多了一个结点的pre指针指向。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/892038
推荐阅读
相关标签
  

闽ICP备14008679号