c语言-链表1

10 链表

一、链表是什么？

                --  数据的一种存储方式         -- 链式存储

（1）线性存储         -- 地址连续         -- 自动开辟，自动释放         -- 默认是线性存储

（2）链式存储         -- 地址不连续         -- 手动开辟，手动释放

二、链式存储所使用的常用函数

1、malloc

函数功能：开辟内存空间

函数头文件：#include<stdlib.h>

函数原型：void *malloc(size_t size);

函数参数：size -- 要开辟的空间大小

函数返回值：void *         -- 开辟的空间的地址         -- 任意类型    -- 方便强转成你需要的类型

注：因为返回值是任意类型，所以一定不要忘记强转！！！

2、perror

函数功能：打印某个函数的执行结果（错误信息）

函数头文件：#include<stdio.h>

函数原型：void perror(const char *s);

函数参数：

                s -- 字符串，函数名

        //因为参数是个字符串类型，所以函数名作为参数时，要用""引起来。

函数返回值：无

3、memset

函数功能：初始化内存空间

函数头文件：#include<string.h>

函数原型：void *memset(void *s,int c,size_t n);

函数参数：
        s         -- 要初始化的空间地址
        c         -- 初始化的内容 -- 一般初始化为0
        n         -- 要初始化的空间大小

函数返回值：不用

4、bzero

函数功能：初始化内存空间为0

函数头文件：#include<strings.h>

函数原型：void bzero(void *s,size_t n);

函数参数：
        s         -- 要初始化的空间地址
        n         -- 要初始化的空间大小

函数返回值：无

4、free

函数功能：释放内存空间 --地址依然存在，但是不能够使用

函数头文件：#include<stdlib.h>

函数原型：void free(void *ptr);

函数参数：
                ptr -- 要释放的空间地址

函数返回值：无

三、链表的存储形式

1、链表是由多个节点组成的

2、节点的组成：

（1）保存数据                 -- 数据域

（2）保存下一个节点的地址                 -- 指针域

地址：默认都是首地址

四、链表操作

        tip: 在vscode中，按住ctrl的同时点击鼠标，就会产生超链接，进到其函数定义处或者是.h文件里。

                ctrl+F，有查询和替换的功能

1、创建节点

#include "create.h"struct node *create()
{struct node *p = (struct node *)malloc(sizeof(struct node));  //要强转if(p == NULL){perror("malloc");   //参数是字符串，所以函数名要用""引起来return NULL;}memset(&p->pnext,0,sizeof(p->data));//将数据初始化为0，因为不能把指针初始化为0，所以指针和数据分开初始化p->pnext = NULL;printf("创建成功!\n");return p;
} 

2、新增链表

#include "add.h"struct node *ADD(struct node *phead)
{struct node *pnew = create();printf("请输入你想增加的数据：\n");scanf("%d",&pnew->data);struct node *ptemp = phead;while(ptemp->pnext != NULL){ptemp = ptemp->pnext;}ptemp->pnext = pnew;printf("添加成功！\n");
}

3、删除链表、修改、查询

（1）删除

        注：这里要ptemp代表的是要删除数据的上一个节点，如果ptemp是要删除的节点的话，则找不到上一个节点的数据。因为是单链表。

#include "del.h"void DEL(struct node *phead)
{if(phead->pnext == NULL){printf("链表为空！\n");return;}int n;printf("请输入你想删除的数据:\n");scanf("%d",&n);struct node *ptemp = phead;while(ptemp->pnext !=NULL){if(ptemp->pnext->data == n){struct node *pdel = ptemp->pnext;ptemp->pnext = ptemp->pnext->pnext;free(pdel);printf("删除成功！\n");return;}ptemp = ptemp->pnext;}printf("查无数据！\n");
}

(2)修改

#include "update.h"void UPDATE(struct node *phead)
{if(phead->pnext == NULL){printf("链表为空！\n");return;}int n;printf("请输入你想更新的数据:\n");scanf("%d",&n);struct node *ptemp = phead;while(ptemp->pnext !=NULL){if(ptemp->pnext->data == n){printf("请输入您要修改的新数据：\n");scanf("%d",&ptemp->pnext->data);printf("更新成功！\n");return;}ptemp = ptemp->pnext;}printf("查无数据！\n");
}

（3）查询

#include "find.h"void FIND(struct node *phead)
{if(phead->pnext == NULL){printf("链表为空！\n");return;}int n;printf("请输入你想查询的数据:\n");scanf("%d",&n);struct node *ptemp = phead;while(ptemp->pnext !=NULL){if(ptemp->pnext->data == n){printf("%d\n",ptemp->pnext->data);printf("查询成功！\n");return;}ptemp = ptemp->pnext;}printf("查无数据！\n");
}

4、遍历链表

         注：ptemp这里是第一个有效节点，因为phead头节点没有数据域，所以不是有效节点

#include "query.h"void QUERY(struct node *phead)
{if(phead->pnext == NULL){printf("链表为空！\n");return;}struct node *ptemp = phead->pnext;printf("链表存放的数据为：\n");while(ptemp!=NULL){printf("%d\n",ptemp->data);ptemp = ptemp->pnext;}
}

 5、节点排序

五、循环链表

 

六、双向链表