说明
- 传送门：博客汇总帖
链表
链表的基本思维是，利用结构体，在堆空间开辟出一个又一个节点，通过next指针指向下一个节点，这样独立的节点通过next指针相互链接，形成链表
data为自定义的数据类型，next为指向下一个链表结点的指针，通过访问next，可以引导我们去访问链表的下一个结点。
单链表
1、节点数据类型设计
typedef unsigned int data_type;
typedef struct Node
{
data_type data;
struct Node *next;
/* data */
}linklist,*linkptr;
2、链表的初始化
书要是通过malloc函数在堆空间申请内存
/**
* @description: 创建（初始化）链表
* @param {*}
* @return {linkptr} 返回的是linkptr类型的指针
*/
linkptr link_create(void)
{
linkptr ptr;
ptr = (linkptr)malloc(sizeof(linklist));
if(NULL == ptr){
printf("malloc error");
return NULL;
}
ptr->next =NULL;
return ptr;
}
3、链表的插入
3.1头插法
每次都在list节点后面插入新的节点
/**
* @description: 头插法
* @param {linkptr} list 链表指针
* @param {int} value 插入的节点的数值
* @return {*}
*/
int link_head_insert(linkptr list,int value)
{
linkptr ptr;
if ((ptr = (linkptr)malloc(sizeof(linklist))) == NULL)
{
printf("malloc error\n");
return ERROR;
}
//在这里注意的是 将数据保存至ptr ，所以第一次插入的时候 第一个节点list->data 数值未知，
//这里与遍历有关
ptr->data = value;
ptr->next = list->next;
list->next = ptr;
return OK;
}
3.2 尾插法
在最后一个节点插入新的节点
/**
* @description: 尾部插入
* @param {linkptr} list 链表指针
* @param {int} value 数据
* @return {*}
*/
int link_end_insert(linkptr list,int value)
{
linkptr ptr; //保存数据节点
if ((ptr = (linkptr)malloc(sizeof(linklist))) == NULL)
{
printf("malloc error\n");
return ERROR;
/* code */
}
while (list->next)
{
list = list->next;
/* code */
}
ptr->data = value;
list->next = ptr;
ptr->next = NULL;
return OK;
}
4、链表的遍历
/**
* @description: 链表的遍历
* @param {linkptr} list
* @return {*}
*/
void link_show(linkptr list)
{
while (list->next)
{
printf("%d\n",list->next->data); //第一个节点是不包含数据的
list = list->next;
}
}
5、链表的查找
5.1、按照序号进行查找
/**
* @description: 按照序号进行查找,头结点不包含，第一个节点序号 0
* @param {linkptr} list：链表指针
* @param {int} i：序号
* @return {*} printf查找到的链表数据
*/
void link_get_serial_number(linkptr list,int i)
{
int j = -1; //j++(标号从0开始)
if(i<0) return ;
while ((list->next)&&j<i)
{
j++;
list = list->next;
/* code */
}
if (j == i)
{
printf("data = %d\n",list->data);
/* code */
}
else
{
return ;
/* code */
}
}
5.2、按照数值进行查找
/**
* @description: 按照数值进行查找，成功打印存在 失败打印不存在
* @param {linkptr} list
* @param {int} value
* @return {*}
*/
void link_get_value(linkptr list,int value)
{
list = list->next;
while (list->next && list->data != value)
{
list = list->next;
}
if (list->data == value)
{
printf("value = %d,在链表中存在\n",value);
/* code */
}
else
{
printf("value = %d,在链表中不存在\n",value);
/* code */
}
}
6、源码
/*
* @Author: Mr.Dragon
* @Date: 2021-08-30 22:28:46
* @LastEditTime: 2021-09-02 00:34:05
* @LastEditors: Mr.Dragon
* @Description: Fall_down:所念皆星河
*/
#include "stdio.h"
#include "stdlib.h"
typedef unsigned int data_type;
#define ERROR -1
#define OK 0
typedef struct Node
{
data_type data;
struct Node *next;
/* data */
}linklist,*linkptr;
/**
* @description: 创建（初始化）链表
* @param {*}
* @return {linkptr} 返回的是linkptr类型的指针
*/
linkptr link_create(void)
{
linkptr ptr;
ptr = (linkptr)malloc(sizeof(linklist));
if(NULL == ptr){
printf("malloc error");
return NULL;
}
ptr->next =NULL;
return ptr;
}
/**
* @description: 头插法
* @param {linkptr} list 链表指针
* @param {int} value 插入的节点的数值
* @return {*}
*/
int link_head_insert(linkptr list,int value)
{
linkptr ptr;
if ((ptr = (linkptr)malloc(sizeof(linklist))) == NULL)
{
printf("malloc error\n");
return ERROR;
}
ptr->data = value;
ptr->next = list->next;
list->next = ptr;
return OK;
}
/**
* @description: 链表的遍历
* @param {linkptr} list
* @return {*}
*/
void link_show(linkptr list)
{
while (list->next)
{
printf("%d\n",list->next->data); //第一个节点是不包含数据的
list = list->next;
}
}
/**
* @description: 尾部插入
* @param {linkptr} list 链表指针
* @param {int} value 数据
* @return {*}
*/
int link_end_insert(linkptr list,int value)
{
linkptr ptr; //保存数据节点
if ((ptr = (linkptr)malloc(sizeof(linklist))) == NULL)
{
printf("malloc error\n");
return ERROR;
/* code */
}
while (list->next)
{
list = list->next;
/* code */
}
ptr->data = value;
list->next = ptr;
ptr->next = NULL;
return OK;
}
/**
* @description: 按照序号进行查找,头结点不包含，第一个节点序号 0
* @param {linkptr} list：链表指针
* @param {int} i：序号
* @return {*} printf查找到的链表数据
*/
void link_get_serial_number(linkptr list,int i)
{
int j = -1; //j++(标号从0开始)
if(i<0) return ;
while ((list->next)&&j<i)
{
j++;
list = list->next;
/* code */
}
if (j == i)
{
printf("data = %d\n",list->data);
/* code */
}
else
{
return ;
/* code */
}
}
/**
* @description: 按照数值进行查找，成功打印存在 失败打印不存在
* @param {linkptr} list
* @param {int} value
* @return {*}
*/
void link_get_value(linkptr list,int value)
{
list = list->next;
while (list->next && list->data != value)
{
list = list->next;
}
if (list->data == value)
{
printf("value = %d,在链表中存在\n",value);
/* code */
}
else
{
printf("value = %d,在链表中不存在\n",value);
/* code */
}
}
int main(void)
{
#if 0 //使用头插法
linkptr link;
link = link_create();
link_head_insert(link,10);
link_head_insert(link,20);
link_head_insert(link,30);
link_show(link);
#endif
#if 1 //使用尾插法
linkptr link;
link = link_create();
link_end_insert(link,10);
link_end_insert(link,20);
link_end_insert(link,30);
link_show(link);
#endif
link_get_serial_number(link,2);
link_get_value(link,20);
free(link);
return 0;
}