单链表
基本概念
- 顺序表:顺序存储的线性表。
- 链式表:链式存储的线性表,简称链表。
既然顺序存储中的数据因为挤在一起而导致需要成片移动,那很容易想到的解决方案是将数据离散地存储在不同内存块中,然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表,就是所
谓的链表。
顺序表和链表在内存在的基本样态如下图所示:
链表的分类
根据链表中各个节点之间使用指针的个数,以及首尾节点是否相连,可以将链表细分为如下种类:
- 单向链表
- 单向循环链表
- 双向循环链表
这些不同链表的操作都是差不多的,只是指针数目的异同。以最简单的单向链表为例,其基本示意图
如下所示:
上图中,所有的节点均保存一个指针,指向其逻辑上相邻的下一个节点(末尾节点指向空)。另外注
意到,整条链表用一个所谓的头指针 head 来指向,由 head 开始可以找到链表中的任意一个节点。
head 通常被称为头指针。
链表的基本操作,一般包括:
- 节点设计
- 初始化空链表
- 增删节点
- 链表遍历
- 销毁链表
下面着重针对这几项常见操作,讲解单向链表的处理。
单链表节点设计
单向链表的节点非常简单,节点中除了要保存用户数据之外(这里以整型数据为例),只需要增加一
个指向本类节点的指针即可,如下所示:
typedef int DATA;
typedef struct Node
{
DATA data; // 存储数据---数据域
struct Node *next; // 存储下一个节点的地址---指针域
} NODE;
单链表初始化
首先,空链表有两种常见的形式。一种是带所谓的头结点的,一种是不带头结点的。所谓的头结点是
不存放有效数据的节点,仅仅用来方便操作,如下:
而不带头结点的空链表如下所示:
注意:
- 头指针 head 是必须的,是链表的入口
- 头节点是可选的,为了方便某些操作
由于头结点是不存放有效数据的,因此如果空链表中带有头结点,那么头指针 head 将永远不变,这会给以后的链表操作带来些许便捷。
下面以带头结点的链表为例,展示单向链表的初始化的示例代码:
int slist_create(NODE** head,DATA data)
{
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
{
return -1;
}
p -> data = data;
p -> next = NULL;
*head = p;
return 0;
}
单链表增删节点
相对于顺序表需要整片移动数据,链表增删节点只需要修改几个相关指针的指向,动作非常快速。与顺序表类似,可以对一条链表中的任意节点进行增删操作,示例代码是:
int slist_addHead(NODE **head, DATA data)
{
NODE *p = (NODE *)malloc(sizeof(NODE));
if (!p)
{
return -1;
}
p->data = data;
p->next = *head;
*head = p;
return 0;
}
int slist_addTail(NODE **head, DATA data)
{
NODE *pNew = (NODE *)malloc(sizeof(NODE));
if (!pNew)
{
return -1;
}
pNew->data = data;
pNew->next = NULL;
NODE *p = *head, *q = NULL;
if (!p)
{
*head = pNew;
return 0;
}
while (p)
{
q = p;
p = p->next;
}
q->next = pNew;
return 0;
}
int slist_insert(NODE **head, DATA pos, DATA data)
{
NODE *pNew = (NODE *)malloc(sizeof(NODE));
if (!pNew)
return -1;
pNew->data = data;
pNew->next = NULL;
NODE *p = *head, *q = NULL;
if (!p)
{
*head = pNew;
return 0;
}
if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0)
{
pNew->next = *head;
*head = pNew;
return 0;
}
while (p)
{
if (memcmp(&(p->data), &pos, sizeof(DATA)) == 0)
{
pNew->next = p;
q->next = pNew;
return 0;
}
q = p;
p = p->next;
}
q->next = pNew;
return 0;
}
int slist_update(const NODE *head, DATA old, DATA newdata)
{
NODE *p = NULL;
if (!(p = slist_find(head, old)))
return -1;
p->data = newdata;
return 0;
}
int slist_delete(NODE **head, DATA data)
{
NODE *p = *head, *q = NULL;
if (!p)
return -1;
if (memcmp(&(p->data), &data, sizeof(DATA)) == 0)
{
*head = p->next;
free(p);
return 0;
}
while (p)
{
if (memcmp(&(p->data), &data, sizeof(DATA)) == 0)
{
q->next = p->next;
free(p);
return 0;
}
q = p;
p = p->next;
}
return -1;
}
注意:
删除链表的节点并不意味着释放其内存,而是将其剔除出链表
单链表的遍历
遍历的意思就是逐个访问每一个节点,对于线性表而言,由于路径唯一的选择就是从头走到尾。因此相当而言比较简单。
下面是单向链表的遍历示例代码,假设遍历每个节点并将其整数数据输出:
NODE* slist_find(const NODE* head,DATA data)
{
const NODE* p = head;
while(p)
{
if(memcmp(&(p -> data),&data,sizeof(DATA)) == 0)
{
return (NODE*)p;
}
p = p -> next;
}
return NULL;
}
void slist_showAll(const NODE* head)
{
const NODE* p = head;
while(p)
{
printf("%d ",p -> data);
p = p -> next;
}
printf("\n");
}
单链表的销毁
由于链表中的各个节点被离散地分布在各个随机的内存空间,因此销毁链表必须遍历每一个节点,释放每一个节点。
注意:
销毁链表时,遍历节点要注意不能弄丢相邻节点的指针
void slist_destroy(NODE** head)
{
NODE* p = *head, *q = NULL;
while(p)
{
q = p;
p = p -> next;
free(q);
}
*head = NULL;
}
完整代码
- singList.h
#ifndef __SEQLIST_H
#define __SEQLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
// 定义顺序表的结构体
typedef struct
{
int capacity;// 顺序表的容量(顺序表本质上是数组)
int last; // 末元素的下标
int *data; // 数据,其实是一个存放多个int的容器
} seqList;
// 创建顺序表(顺序表的初始化)
seqList *initList(int cap);
// 向顺序表的表头插入一个新数据
bool insert(seqList *list,int data);
// 判断顺序表是否满了
bool isFull(seqList *list);
// 遍历顺序表中的元素
void show(seqList *list);
// 将顺序表中指定的某个元素删除
bool removeNode(seqList *list,int data);
// 销毁顺序表
void destroy(seqList *s);
#endif
slist.c
#include "slist.h"
/*
@function: int slist_create(NODE** head,DATA data);
@berif: 创建单项链表
@argument: head: 指向头指针变量的地址,用来接收首节点地址
data: 存储在节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_create(NODE **head, DATA data)
{
// 申请内存
NODE *p = (NODE *)malloc(sizeof(NODE));
// 校验
if (!p)
{
return -1;
}
// 赋值操作
p->data = data;
p->next = NULL;
*head = p;
return 0;
}
/*
@function: int slist_addHead(NODE** head,DATA data);
@berif: 向链表头部插入一个节点数据(头插法)
@argument: head: 指向头指针变量的地址,用来接收首节点地址
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_addHead(NODE **head, DATA data)
{
// 创建一个新节点(申请内存)
NODE *p = (NODE *)malloc(sizeof(NODE));
// 校验
if (!p)
{
return -1;
}
// 给节点添加新数据(创建节点的目的是存储数据)
p->data = data;
// 新节点指向原本的head节点
p->next = *head;
// 我们要让p作为我们新的head
*head = p;
return 0;
}
/*
@function: int slist_addTail(NODE** head,DATA data);
@berif: 向链表尾部插入一个节点数据(尾插法)
@argument: head: 指向头指针变量的地址,用来接收首节点地址
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_addTail(NODE **head, DATA data)
{
// 创建一个新节点(申请内存)
NODE *pNew = (NODE *)malloc(sizeof(NODE));
// 校验
if (!pNew)
{
return -1;
}
// 赋值操作
pNew->data = data; // 存数据
pNew->next = NULL; // 因为是最后一个节点,所有没有指向
// 获取尾部节点,默认head头结点就是尾结点,p用来保存真实的尾结点
NODE *p = *head, *q = NULL;
if (!p)
{
// 如果说头节点不存在,我们直接将新节点作为头结点,一般不会发生
*head = pNew;
return 0;
}
// 通过一个循环,找尾结点
while (p)
{
// 为什么要定义q,因为p是在变化的
q = p;
p = p->next;// 指针向下指
}
// 让原本的尾结点指向新插入的的节点,此时新插入的节点变成了尾结点
q->next = pNew;
return 0;
}
/*
@function: int slist_insert(NODE** head,DATA pos ,DATA data);
@berif: 向链表节点值为pos的位置插入一个节点数据data
@argument: head: 指向头指针变量的地址
pos: 插入节点位置的节点数据
data: 存储在新节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_insert(NODE** head,DATA pos,DATA data)
{
// 创建一个新节点,并申请内存
NODE *pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
{
perror("内存申请失败!");
return -1;
}
// 给新节点赋初值
pNew->data = data;
pNew->next = NULL;
// 声明变量,p是pos对应位置的节点,默认是头结点,q是pos对应节点的上一个节点
NODE *p = *head,*q = NULL;
// 第一种情况:头结点不存在
if(!p)
{
// 新节点pNew作为头结点
*head = pNew;
return 0;
}
// 第二种情况:只有头结点
if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0)
{
// 头插法
// 新节点的next指向head节点
pNew->next = *head;
// 改变指向,将pNew作为新的头结点
*head = pNew;
return 0;
}
// 第三种情况:既有头结点,也有普通节点
while (p)
{
// 找pos对应位置的节点
if(memcmp(&(p->data),&pos,sizeof(DATA)) == 0)
{
// pNew在p前
pNew->next = p;
// pNew在q后
q->next = pNew;
return 0;
}
q = p;// q在p的前一位,一前(q)一后(p)
p = p ->next;
}
// 尾插法
q->next = pNew;
return 0;
}
/*
@function: NODE* slist_find(const NODE* head,DATA data);
@berif: 查找链表数据data
@argument: head: 指向头指针变量
data: 待查找的数据
@return : 成功返回节点的地址
失败返回NULL
*/
NODE* slist_find(const NODE *head,DATA data)
{
// 创建一个变量,用来接收链表
const NODE* p = head;
while(p)
{
if(memcmp(&(p->data),&data,sizeof(DATA))==0)
{
return (NODE*)p;
}
// 移动节点
p = p->next;
}
return NULL;
}
/*
@function: int slist_update(const NODE* head,DATA old_data,DATA new_data);
@berif: 更新链表数据old_data 为 new_data
@argument: head: 指向头指针变量
old_data: 待更新的节点数据
new_data: 更新后的节点数据
@return : 成功返回 0
失败返回 -1
*/
int slist_update(const NODE* head,DATA old_data,DATA new_data)
{
NODE* p = NULL;
if(!(p = slist_find(head,old_data)))
{
return -1;
}
p->data = new_data;
return 0;
}
/*
@function: void slist_showAll(const NODE* head);
@berif: 遍历链表数据
@argument: head: 指向头指针变量
@return : 无
*/
void slist_showAll(const NODE* head)
{
// 创建一个变量用来接收链表
const NODE* p = head;
// 遍历链表
while (p)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
/*
@function: int slist_delete(NODE** head,DATA data);
@berif: 删除链表中节点值为data的节点
@argument: head: 指向头指针变量的地址
data: 删除节点中的数据
@return : 成功返回 0
失败返回 -1
*/
int slist_delete(NODE** head,DATA data)
{
// 指针尾随
NODE *p = *head,*q = NULL;
// 第一种情况:头结点不存在(链表本身不存在),无法操作
if(!p)
{
return -1;
}
// 第二种情况:只有一个节点
if(memcmp(&(p->data),&data,sizeof(DATA)) == 0)
{
*head = p -> next;
free(p);
return 0;
}
// 第三种情况:有多个节点
while (p)
{
if(memcmp(&(p->data),&data,sizeof(DATA)) == 0)
{
q->next = p->next;// p的上一个节点的next指向p的下一个节点
// 这个回收不会影响到链表的删除
free(p);
return 0;
}
q = p;
p = p->next;// p->next代表的是p的下一个节点,将p的下一个节点赋值给p,相当于p移动了一位
}
return -1;
}
/*
@function: void slist_destroy(NODE** head);
@berif: 回收链表
@argument: head: 指向头指针变量的地址
@return : 无
*/
void slist_destroy(NODE** head)
{
// 指针尾随
NODE *p = *head,*q = NULL;
while(p)
{
q = p;// 12
p = p->next;// 13
// 回收前一个节点
free(q);
}
*head = NULL;
}
链表优缺点
链式存储中,所有节点的存储位置是随机的,他们之间的逻辑关系用指针来确定,跟物理存储位置无
关,因此从上述示例代码可以很清楚看到,增删数据都非常迅速,不需要移动任何数据。另外,又由
于位置与逻辑关系无关,因此也无法直接访问某一个指定的节点,只能从头到尾按遍历的方式一个个
找到想要的节点。简单讲,链式存储的优缺点跟顺序存储几乎是相对的。
总结其特点如下:
-
优点
-
插入、删除时只需要调整几个指针,无需移动任何数据
-
当数据节点数量较多时,无需一整片较大的连续内存空间,可以灵活利用离散的内存
-
当数据节点数量变化剧烈时,内存的释放和分配灵活,速度快
-
-
缺点
-
在节点中,需要多余的指针来记录节点之间的关联。
-
所有数据都是随机存储的,不支持立即访问任意一个随机数据。
-
循环单向链表
所谓的循环,指得是将链表末尾节点循环地指向链表表头。比如,单向链表变成循环链表的示意图如下所示:
循环链表的操作跟普通链表操作基本上是一致的,只要针对循环特性稍作修改即可
标签:NODE,head,return,链表,数据结构,data,节点 From: https://blog.csdn.net/qixi_ao/article/details/141612920