C语言单链表增删改查

r囧r小猫 2022-02-14 01:21 260阅读 0赞

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

作为有强大功能的链表，对他的操作当然有许多，比如：链表的修改，删除，插入，查询等等。

1.链表的创建

typedef struct Node
    {
    	int data;     //数据域
    	struct LNode * next; //指向下一个节点的指针
    }LinkList;

2.链表的初始化

void InitList(LinkList *&L)
    {
    	L = (LinkList *)malloc(sizeof(LinkList));
    	L->next = NULL;
    }

3.链表的插入

这里介绍的是头插法

void ListInsert(LinkList *&L, LinkList *p)
    {
    	LinkList *q;
    	q = L;
    	p->next = q->next;
    	q->next=p;
    }

将节点p插入到链表L中，只需要让p指向头结点指向的位置，在另头结点指向p，就可以吧p插入到链表中。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NnczcyMw_size_16_color_FFFFFF_t_70][]

4.链表中某个节点的删除

void Delete(LinkList *&L, int e)
    {
    	LinkList *p = L->next;
    	LinkList *q;//q用来记录上一个节点
    	while (p->next != NULL)
    	{
    		if (p->data == e)//如果成立，则让上一个节点指向下一个节点，跳过该节点，即达到删除的目的
    		{
    			q->next = p->next;
    		}
    		q = p;
    		p = p->next;
    	}
    	free(p);//删除后一定要记得释放空间，不然造成内存崩溃
    }

用图来表示，即就是跳过该节点，直接指向下一个节点，再释放掉该节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NnczcyMw_size_16_color_FFFFFF_t_70 1][]

5.遍历链表

LinkList *q = L->next;
    	while (q != NULL)
    	{
    		printf("%d ", q->data);
    	}

这样就可对链表进行遍历，输出所有节点的数据域的值。

**完整代码：**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct LNode
    {
    	int data;     //数据域
    	struct LNode * next; //指向下一个节点的指针
    }LinkList;
    void InitList(LinkList *&L)
    {
    	L = (LinkList *)malloc(sizeof(LinkList));
    	L->next = NULL;
    }
    void ListInsert(LinkList *&L, LinkList *p)
    {
    	LinkList *q;
    	q = L;
    	p->next = q->next;
    	q->next = p;
    }
    void Delete(LinkList *&L, int e)
    {
    	LinkList *p = L->next;
    	LinkList *q=L;//q用来记录上一个节点
    	if (p == NULL)
    	{
    		printf("目前无节点\n");
    		exit(0);
    	}
    	while (p != NULL)
    	{
    		if (p->data == e)//如果成立，则让上一个节点指向下一个节点，跳过该节点，即达到删除的目的
    		{
    			q->next = p->next;	
    			printf("删除成功\n");
    			free(p);//删除后一定要记得释放空间，不然造成内存崩溃
    			break;
    		}
    		q = p;
    		p = p->next;
    	}
    
    }
    void ADD(LinkList *&L)//增加
    {
    	int a, num;
    	printf("请输入你要增加的数据:\n");
    	scanf("%d", &num);
    	LinkList *p = (LinkList *)malloc(sizeof(LinkList));
    	p->data = num;
    	ListInsert(L, p);
    }
    void dele(LinkList *&L)//删除
    {
    	int n;
    	printf("请输入你要删除的数据:\n");
    	scanf("%d", &n);
    	Delete(L, n);
    }
    void change(LinkList *&L)//修改
    {
    	int i,j;
    	printf("请输入你要修改的节点数据:\n");
    	scanf("%d", &i);
    	LinkList *q = L->next;
    	while (q != NULL)
    	{
    		if (q->data == i)
    		{
    			printf("请输入你要修改后的数据:\n");
    			scanf("%d", &j);
    			q->data = j;
    			printf("修改成功\n");
    		}
    		q = q->next;
    	}
    }
    void Prin(LinkList *&L)//打印链表
    {
    	LinkList *q = L->next;
    	while (q != NULL)
    	{
    		printf("%d ", q->data);
    		q = q->next;
    	}
    	printf("\n");
    }
    int main()
    {
    	LinkList *L;
    	InitList(L);
    	int a;
    	
    	while (1)
    	{
    		printf("请输入你要进行的操作:\n1.增加数据\n2.删除数据\n3.修改数据\n4.打印链表\n");
    		scanf("%d", &a);
    		switch (a)
    		{
    		case 1:ADD(L); break;
    		case 2:dele(L); break;
    		case 3:change(L); break;
    		case 4:Prin(L); break;
    		default:printf("输入不合法\n");
    		}
    
    	}
    	system("pause");
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NnczcyMw_size_16_color_FFFFFF_t_70]: /images/20220214/7c478cf2692e453f812f10376a2f89c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0NnczcyMw_size_16_color_FFFFFF_t_70 1]: /images/20220214/eb9749866afa45568f61692aa0784462.png