[数据结构与算法]双向链表的C语言实现

1?? 用结构体定义一个节点

• ?? 双向链表的结构体：

struct node
{
	int data;
	struct node *prev;//指向上一个节点
	struct node *next;//指向下一个节点
};

2?? 建立一个双向链表

• 双向链表结构
  
• 类似单链表的头插法，我们创建一个节点插在链表头节点前面成为新的头结点：

struct node *insertHead(struct node *head)
{
	struct node *new = (struct node *)malloc(sizeof(struct node));//为新节点开辟空间并初始化数据
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    if (head == NULL){ //若头节点为空，新节点即为头结点
        return new; //返回新节点的地址
    }else{
        head->prev = new;
        new->next = head;
        return new;//返回新节点的地址
    }
}

• 当然我们也可以在链表的尾部添加节点，返回头指针

struct node *insertTail(struct node *head)
{
    struct node *end = head; //添加一个指向尾部的指针end
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    if (head == NULL)
    {               //若头节点为空，创建第一个节点
        return new; //返回头指针
    }

    while (end->next != NULL)
    { //end一直走到最后一个节点
        end = end->next;
    }

    end->next = new; //让最后一个节点的指针指向新节点
    new->prev = end;
    return head;
}

3??双向链表的遍历

• 因为链表是双向的，所以我们可以从头和尾两个方向遍历
• 从头节点开始遍历：

void printLinkH(struct node *head)
{
    if (head == NULL){
        printf("The list is empty.\n");
        return;
    }
    while (head != NULL){ //不是空就往下走
    	printf("%d\n", head->data);
        head = head->next;
    }
    putchar('\n');
}

• 因为我们的创建函数返回的是头节点地址，所以我们写一个得到尾节点地址的函数

struct node *getTail(struct node *head)
{
    while (head->next != NULL)
    { //head一直走到最后一个节点
        head = head->next;
    }
    return head;
}

• 从尾节点的遍历跟从头结点一样，只不过把next换成了prev

void printLinkT(struct node *tail)
{
    if (tail == NULL)
    {
        printf("The list is empty.\n");
        return;
    }
    while (tail != NULL) //不是空就往下走
    {
        printf("%d\n", tail->data);
        tail = tail->prev;
    }
    putchar('\n');
}

• 下面放代码验证：

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *prev; //指向上一个节点
    struct node *next; //指向下一个节点
};
struct node *insertHead(struct node *head)
{
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    if (head == NULL)
    {               //若头节点为空，新节点为头节点
        return new; 
    }
    else
    {
        head->prev = new;
        new->next = head;
        return new;
    }
}

struct node *insertTail(struct node *head)
{
    struct node *end = head; //添加一个指向尾部的指针end
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    if (head == NULL)
    {               //若头节点为空，新节点为头节点
        return new; 
    }

    while (end->next != NULL)
    { //end一直走到最后一个节点
        end = end->next;
    }

    end->next = new; //让最后一个节点的指针指向新节点
    new->prev = end;//新节点的前一个指针指向end指向的节点
    return head;
}
struct node *getTail(struct node *head)
{
    while (head->next != NULL)
    { //head一直走到最后一个节点
        head = head->next;
    }
    return head;
}

void printLinkH(struct node *head)
{
    if (head == NULL)
    {
        printf("The list is empty.\n");
        return;
    }
    while (head != NULL) //不是空就往下走
    {
        printf("%d\n", head->data);
        head = head->next;
    }
    putchar('\n');
}

void printLinkL(struct node *tail)
{
    if (tail == NULL)
    {
        printf("The list is empty.\n");
        return;
    }
    while (tail != NULL) //不是空就往前走
    {
        printf("%d\n", tail->data);
        tail = tail->prev;
    }
    putchar('\n');
}

int main()
{
    int i = 0;
    struct node *head1 = NULL;
    struct node *head2 = NULL;
    struct node *tail = NULL;

    for (i = 0; i < 5; i++)//头插法创建5个节点的双向链表link1
    {
        head1 = insertHead(head1);//从头结点遍历
    }
    printLinkH(head1);

    for (i = 0; i < 5; i++)//尾插法创建5个节点的双向链表link2
    {
        head2 = insertTail(head2);
    }
    tail = getTail(head2);//得到link2的尾节点地址
    printLinkH(head2);//从头结点遍历
    printLinkL(tail);//从尾结点遍历

    return 0;
}

• 示意图

• 终端显示：

input your new node data:1
input your new node data:2
input your new node data:3
input your new node data:4
input your new node data:5
5
4
3
2
1

input your new node data:11
input your new node data:22
input your new node data:33
input your new node data:44
input your new node data:55
11
22
33
44
55

55
44
33
22
11

4??删除第n个节点

• 这里的方法很灵活，我的做法是用一个指针p遍历到第n个节点的后一个结点，然后把目标节点（p->prev）的prev赋值给p下节点的prev，把p的地址赋值给上上个节点的next，最后释放（free）掉目标节点就成了。
  

struct node *delNode(struct node *head, int num)
{
    struct node *p = head;
    if (num == 1){	//头结点的情况
        head = head->next;//把第二个节点的地址给头指针
        free(p);//释放原来的头结点
        return head;//返回新的头指针
    }

    while (num--){
        if (p->next == NULL){  //尾节点也特殊照顾
            struct node *temp = p;//把最后一个节点地址给中间变量
            p->prev->next = NULL;//把倒数第二个节点的next设为NULL
            free(temp);//释放最后一个节点结点
            return head;//为了兼容头结点的情况返回头指针
        }

        p = p->next;
    }
    p->prev->prev->next = p;//把p的地址赋值给上上个节点的next
    struct node *temp = p->prev;//目标节点的地址给中间变量
    p->prev = p->prev->prev;//把目标节点地址给p的prev
    free(temp);//释放目标节点，完成删除

    return head;//为了兼容头结点的情况返回头指针
}

• 代码验证：

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *prev; //指向上一个节点
    struct node *next; //指向下一个节点
};

struct node *insertTail(struct node *head)//尾插法插入一个节点
{
    struct node *end = head;
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data));

    if (head == NULL)
    {               
        return new; 
    }

    while (end->next != NULL)
    { 
        end = end->next;
    }

    end->next = new; 
    new->prev = end;
    return head;
}

void printLinkH(struct node *head)//从头指针遍历链表
{
    if (head == NULL)
    {
        printf("The list is empty.\n");
        return;
    }
    while (head != NULL) //不是空就往下走
    {
        printf("%d\n", head->data);
        head = head->next;
    }
    putchar('\n');
}

struct node *delNode(struct node *head, int num)//删除第n个节点
{
    struct node *p = head;
    if (num == 1){
        head = head->next;
        free(p);
        return head;
    }

    while (num--)
    {
        if (p->next == NULL){
            struct node *temp = p;
            p->prev->next = NULL;
            free(temp);
            return head;
        }

        p = p->next;
    }

    
    p->prev->prev->next = p;
    struct node *temp = p->prev;
    p->prev = p->prev->prev;
    free(temp);

    return head;
}

struct node *creatLink(struct node *head)//尾插法创建链表
{
    int num;
    printf("input node num:");//键入你想创建的节点数
    scanf("%d", &num);
    putchar('\n');
    while (num--){

        head = insertTail(head);
    }
    return head;
}

int main()
{
    int n;
    struct node *head = NULL;

    head = creatLink(head);//创建链表封装了一个函数
    printLinkH(head);//打印链表

    printf("input del num:");//键入你想删除的节点数
    scanf("%d", &n);

    head = delNode(head, n);
    putchar('\n');

    printLinkH(head);//打印链表

    return 0;
}

• 终端显示：

input node num:6

input your new node data:1
input your new node data:2
input your new node data:3
input your new node data:4
input your new node data:5
input your new node data:6
1
2
3
4
5
6

input del num:4

1
2
3
5
6

5??在第n个节点后插入一个节点

• 创建一个新节点new，用一个指针p遍历到第n个节点的后一个节点，把new结点的地址给第n个节点（p->prev）的next，并让newt的prev指向n节点；把p的地址给new的next，最后再把new结点的地址给第p的prev就完成了
  
• 函数如下：

int insertnode(struct node *p, int num)
{
    struct node *new = (struct node *)malloc(sizeof(struct node));
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    while (num--){
        if (p->next == NULL){ //走到最后一个节点的处理
			p->next = new;
            new->prev = p;
            new->next = NULL;
			return 0;
        }

        p = p->next;//p指针往下走
    }

    p->prev->next = new;
    new->prev = p->prev;
    new->next = p;
    p->prev = new;
}

• 代码验证：

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *prev; //指向上一个节点
    struct node *next; //指向下一个节点
};

struct node *insertTail(struct node *head)//尾插法插入一个节点
{
    struct node *end = head;
    struct node *new = (struct node *)malloc(sizeof(struct node));
    new->prev = NULL;
    new->next = NULL;
    printf("input your new node data:");
    scanf("%d", &(new->data));

    if (head == NULL)
    {               
        return new; 
    }

    while (end->next != NULL)
    { 
        end = end->next;
    }

    end->next = new; 
    new->prev = end;
    return head;
}

void printLinkH(struct node *head)//从头指针遍历链表
{
    if (head == NULL)
    {
        printf("The list is empty.\n");
        return;
    }
    while (head != NULL) //不是空就往下走
    {
        printf("%d\n", head->data);
        head = head->next;
    }
    putchar('\n');
}

int insertnode(struct node *p, int num)//在n节点后插入节点
{
    struct node *new = (struct node *)malloc(sizeof(struct node));
    printf("input your new node data:");
    scanf("%d", &(new->data)); //往新节点里键入数据

    while (num--){
        if (p->next == NULL){ //走到最后一个节点的处理
			p->next = new;
            new->prev = p;
            new->next = NULL;
			return 0;
        }

        p = p->next;//p指针往下走
    }

    p->prev->next = new;
    new->prev = p->prev;
    new->next = p;
    p->prev = new;
}

struct node *creatLink(struct node *head)//尾插法创建链表
{
    int num;
    printf("input node num:");//键入你想创建的节点数
    scanf("%d", &num);
    putchar('\n');
    while (num--){

        head = insertTail(head);
    }
    return head;
}

int main()
{
    int n;
    struct node *head = NULL;

    head = creatLink(head);//创建链表封装了一个函数
    printLinkH(head);//打印链表

    printf("input del num:");//键入你想删除的节点数
    scanf("%d", &n);

    insertnode(head, n);
    putchar('\n');

    printLinkH(head);//打印链表

    return 0;
}

• 终端：

input node num:5

input your new node data:5
input your new node data:6
input your new node data:7
input your new node data:8
input your new node data:9
5
6
7
8
9

input insert num:3
input your new node data:666

5
6
7
666
8
9