当前位置：网站首页>C语言n番战--链表（九）

C语言n番战--链表（九）

2022-07-23 04:51:00 【阿杰在线送代码】

嵌入式之路，贵在日常点滴

                                                                ---阿杰在线送代码

目录

一、对比链表与数组 

同样是存放一串数据，链表与数组的区别在哪里？

链表方便增删

二、链表的创建之静态创建：最简单的创建 

链表的动态遍历：统计节点个数与查找节点 

三、插入节点与删除节点

从指定节点的后方插入新节点

在指定节点前方插入新节点

删除指定节点 

四、链表的创建之动态创建

头插法创建链表

尾插法创建链表 

一、对比链表与数组 

同样是存放一串数据，链表与数组的区别在哪里？

在这里插入图片描述

数组是申请连续的地址存放数据，在增加或删除某一元素不方便。

而链表可以很好地解决这个问题。

链表方便增删

大致思路：

  • 增加节点

在这里插入图片描述 

  • 删除节点 

在这里插入图片描述 

二、链表的创建之静态创建：最简单的创建 

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
                    //t1.next是一个结构体指针，访问里面的data自然要用->
        printf("%d %d %d\n",t1.data,t1.next->data,t1.next->next->data);
        return 0;
}

链表的动态遍历：统计节点个数与查找节点 

#include "stdio.h"

struct Test
{
	int data;
	struct Test *next;
};

//遍历链表，把节点数据打印出来
void printLink(struct Test *head)
{
	int i;
	struct Test *p = head;
	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
}

//统计链表节点个数
void getNodeNum(struct Test *head)
{
	int cnt = 0;
	struct Test *p = head;
	while(p != NULL)
	{
        cnt++;
        p = p->next;
    }
    printf("链表节点的个数是:%d\n",cnt);
}

//找节点
void findNode(struct Test *head,int data)
{
	struct Test *p = head;
    
	while(p != NULL)
	{
        if(p->data == data)
		{
            printf("找到了\n");
            return;//直接退出子函数，返回main函数
        }
        p = p->next;
    }
    printf("没找到\n");
}

int main()
{
	struct Test t1 = {1,NULL};
	struct Test t2 = {2,NULL};
	struct Test t3 = {3,NULL};
	
	t1.next = &t2;//t1的指针指向了t2的地址
	t2.next = &t3;
	
	printLink(&t1);
    getNodeNum(&t1);
    findNode(&t1,2);
	
	return 0;
}

结果：

1 2 3 链表节点的个数是:3

找到了 

要重点理解的是：p = p->next
指针p指向了下一个结构体的地址，p->next中存放的正是下一个链表节点的地址。
p本身是一个结构体指针，所以用->访问成员next. 

三、插入节点与删除节点

从指定节点的后方插入新节点

思路：
（1）找到指定节点
（2）把指定节点的的next指向new节点的地址
（3）new节点的next指向下一个节点

靠，真拗口，看图！

在这里插入图片描述 

举例：要从链表1 2 3 4 中，在 2 后插入 5 。 

#include "stdio.h"

struct Test
{
	int data;
	struct Test *next;
};

void addBehind(struct Test *head,int data,struct Test *new)
{
	struct Test *p = head;
	
	while(p != NULL)
	{
		if(p->data == data)
		{
			new->next = p->next;
			p->next = new;
			return;
		}
		p = p->next;
	}
}

void printLink(struct Test *head)
{
	struct Test *p = head;
	
	while(p != NULL)
	{
		printf("%d ",p->data);
		p = p->next;
	}
	putchar('\n');
}

int main()
{
	struct Test t1 = {1,NULL};
	struct Test t2 = {2,NULL};
	struct Test t3 = {3,NULL};
	struct Test t4 = {4,NULL};
	
	t1.next = &t2;//t1的指针指向了t2的地址
	t2.next = &t3;
	t3.next = &t4;
	
	struct Test new = {5,NULL};
	addBehind(&t1,2,&new);
	
	printLink(&t1);
	
	return 0;
}

运行结果： 

1 2 5 3 4 

思考一下，为什么上面要传入结构体new的地址？

像下图一样修改，传入的是结构体变量new，然后p->next再指向new的地址不就行啦？还不是一样把地址串了起来。

void addBehind(struct Test *head,int data,struct Test new)
{
        struct Test *p = head;
        while(p != NULL){
                if(data == p->data)
                {
                        new.next = p->next;
                        p->next = &new;
                        return;
                }
                p = p->next;
        }
}

addBehind(&t1,2,new);

结果是：段错误 

Segmentation fault 

为啥？

因为上述中new只是子函数的一个形式参数罢了，地址空间是临时分配，当函数调用结束空间回收，你让一个指针p->next指向这里，必然导致段错误！

在指定节点前方插入新节点

第一种情况：不是1之前插入，链表头未发生改变

在这里插入图片描述第二种情况：是在1之前插入，链表头发生改变 

在这里插入图片描述举个栗子：（1）要从链表1 2 3 4 中，在 3 前插入 5 。

#include "stdio.h"

struct Test
{
	int data;
	struct Test *next;
};

struct Test *addInfront(struct Test *head,int data,struct Test *new)
{
        struct Test *p = head;
		
        if(data == head->data)
		{
            new->next = head;
            head = new;
            return head;
        }
        while(p->next != NULL)
		{
            if(data == p->next->data)
			{
                new->next = p->next;
                p->next = new;
                return head;
            }
			p = p->next;//让链表遍历起来
        }
}

void printLink(struct Test *head)
{
        struct Test *p = head;
		
        while(p != NULL)
		{
            printf("%d ",p->data);
            p = p->next;
        }
        putchar('\n');
}

int main()
{
	struct Test t1 = {1,NULL};
	struct Test t2 = {2,NULL};
	struct Test t3 = {3,NULL};
	struct Test t4 = {4,NULL};
	
	t1.next = &t2;//t1的指针指向了t2的地址
	t2.next = &t3;
	t3.next = &t4;
	
	struct Test new = {5,NULL};	
	struct Test *head = &t1;

    head = addInfront(head,1,&new);
    printLink(head);
	
	return 0;
}

结果：

1 2 5 3 4 

删除指定节点 

在这里插入图片描述 

当删除的是头节点时，还要注意新头的替换！

举例：删除 1 2 3 4中的 1

#include <stdio.h>

struct Test
{
        int data;
        struct Test *next;
};

struct Test *deNode(struct Test *head,int data)
{
        struct Test *p = head;
        if(data == head->data)
        {
                head = head->next;
                return head;
        }

        while(p->next != NULL)
        {
                if(data == p->next->data)
                {
                        p->next = p->next->next;
                        return head;
                }
                p = p->next;
        }
}

void printLink(struct Test *head)
{
        int i;
        struct Test *p = head;
        while(p != NULL)
        {
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

int main()
{
        struct Test t1 ={1,NULL};
        struct Test t2 ={2,NULL};
        struct Test t3 ={3,NULL};
        struct Test t4 ={4,NULL};

        t1.next = &t2;//t1的指针指向了t2的地址
        t2.next = &t3;
        t3.next = &t4;

        struct Test *head = &t1;

        head = deNode(head,1);

        printLink(head);

        return 0;
}

结果：

2 3 4

删除 1 2 3 4中的4，结果：

1 2 3

四、链表的创建之动态创建

头插法创建链表

头一直是在变化的

在这里插入图片描述 

关键步骤：

new->next = head;//new直接指向原来的链表头
head = new;//赋予新的链表头 

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

typedef struct test
{
        int data;
        struct test *next;
}test,*ptest;

void printLink(ptest head)
{
        ptest p = head;
		
        while(p != NULL)
		{
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

ptest insertHead(ptest head,ptest new)
{
        if(head == NULL)
		{
                head = new;
        }
		else
		{
                new->next = head;
                head = new;
        }
        return head;
}

ptest creatLink(ptest head)
{
        ptest new;
        while(1)
		{
                new = (ptest)malloc(sizeof(test));
                printf("请输入新的节点,输入999结束输入\n");
                scanf("%d",&new->data);
                if(new->data == 0)
				{
                        free(new);
                        //new = NULL;
						printf("0 quit\n");
                        return head;
                }
                head = insertHead(head,new);
        }
}

int main()
{
		ptest head = NULL;
		head = creatLink(head);       
        printLink(head);
		
        return 0;
}

结果：

请输入新的节点,输入999结束输入

3

请输入新的节点,输入999结束输入

4

请输入新的节点,输入999结束输入

5

请输入新的节点,输入999结束输入

6

请输入新的节点,输入999结束输入

999

6 5 4 3

尾插法创建链表 

在这里插入图片描述 

关键步骤：

（1）去到链表的尾部

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

（2）在尾部添加new

p->next = new;

实际例子：

运用尾插法创建链表，直接输入数据自动串成链表，想要结束时，输入数据999.

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

typedef struct test
{
        int data;
        struct test *next;
}test,*ptest;

void printLink(ptest head)
{
        int i;
        ptest p = head;
        while(p != NULL){
                printf("%d ",p->data);
                p = p->next;
        }
        putchar('\n');
}

ptest insertTail(ptest head,ptest new)
{
        ptest p = head;
        if(p == NULL){
                head = new;
                return head;//没有此句段错误
        }
        while(p->next != NULL){
                p = p->next;
        }
        p->next = new;

        return head;
}

ptest creatLink(ptest head)
{
        ptest new;
        while(1){
                new = (ptest)malloc(sizeof(test));
                printf("请输入新的节点,输入999结束输入\n");
                scanf("%d",&new->data);
                if(new->data == 999){
                        free(new);
                        new = NULL;
                        return head;
                }
                head = insertTail(head,new);
        }
}

int main()
{
        ptest head = NULL;
        head = creatLink(head);
        printLink(head);
        return 0;
}

结果：

请输入新的节点,输入999结束输入

3

请输入新的节点,输入999结束输入

4

请输入新的节点,输入999结束输入

5

请输入新的节点,输入999结束输入

999

3 4 5

思考：当上面的inserTail函数更改为如下，会发生什么？ 

ptest insertTail(ptest head,ptest new)
{
        ptest p = head;
        if(head == NULL){
                head = new;
        }else{
                p->next = new;
        }
        return head;
}

结果：可以发现无论怎样输入链表都只有第一个和最后一个数据 

请输入新的节点,输入999结束输入

3

请输入新的节点,输入999结束输入

4

请输入新的节点,输入999结束输入

5

请输入新的节点,输入999结束输入

999

3  5

那是因为：使用尾插法，链表头一直未改变。然而在每一次的循环中，p->next都指向new，即为每次头都指向new。到最后链表中自然只有头和最新的new啦。 

原网站

版权声明
本文为[阿杰在线送代码]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_50546241/article/details/125909651

边栏推荐

猜你喜欢

随机推荐