数据结构之带头结点的单链表
一、单链表的概念
二、结构体声明：
三、函数
1.购买节点
2.释放节点
3.单链表的初始化
4.判空函数
5.获取单链表有效值个数
6.按数据查询（返回含有此数据节点的前驱）
7.按数据查询（返回含有当前数据的节点）
8.按pos位置查节点的前驱
9.按pos位置查节点
10.按照节点插入数据
11.头插法
12.尾插法
13.按pos位置插入
14.删除ptr指针后续节点
15.删除第一个节点
16.删除最后一个节点
17.删除数据域和val相等的元素
18.删除数据域和val相等的所有元素
19.清空链表
20.销毁链表
四.完整代码
一、单链表的概念单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：数据域(数据元素的映象) + 指针域(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。单链表逻辑上相邻，物理上不一定相邻
typedef int ELEM_TYPE;
//有效数据节点结构体设计：
typedef struct ListNode
{
ElemType data;//数据域
struct ListNode* next;//指针域
}ListNode,*LinkList;
三、函数
1.购买节点
从堆区申请一个节点大小的内存，并将申请好内存的地址返回。代码如下：
//购买节点
ListNode* Buynode()
{
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
if (s == NULL) exit(1);
memset(s, 0, sizeof(ListNode));//将节点内数据全部填充为0
return s;//返回申请成功的节点地址
}
2.释放节点
每次删除节点之后都需要用 free()来释放，否则会造成严重的内存泄漏代码如下：
//释放节点
void Freenode(ListNode*p)
{
free(p);
p = NULL;//防止野指针
}
3.单链表的初始化
将头节点的数据域浪费掉，头节点的指针域2指为NULL，等待插入数据。
单链表设计头节点的目的：
防止单链表是空的而设的。当链表为空的时候，带头结点的头指针就指向头结点，如果当链表为空的时候，头结点的指针域的数值为NULL。
为了方便单链表的特殊操作，插入在表头或者删除第一个结点。这样就保持了单链表操作的统一性。
单链表加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理统一，方便了单链表的操作，也减少了程序的复杂性和出现bug的机会。
代码实现：
//初始化 //对头结点进行初始化
ListNode* InitList()
{
ListNode* s = Buynode();//申请一个头节点
s->next = NULL;//将头节点的next域置为空
return s;
}
4.判空函数
判断一个单链表是否是空链，只需要判断头节点的指针域是否为NULL
（如果不是一个空链，那么必定存在一个有效值节点，只要存在有效值节点，那么头结点的指针域必不可能指向空，而是指向第一个有效值节点）代码如下：
//判空
bool IsEmpty(LinkList head)
{
assert(head != NULL);
return head->next == NULL;
}
5.获取单链表有效值个数
用for循环遍历单链表，使用一个变量充当计数器，每次循环+1，当 p->next == NULL 的时候，返回计数器的值。代码如下：
//获取单链表有效值个数
int GetSize(LinkList head)
{
assert(head != NULL);
int size = 0;//计数器
LinkList p = head->next;//从头结点的下一个开始
while (p != NULL)
{
size++;
p = p->next;
}
return size;
}
6.按数据查询（返回含有此数据节点的前驱）
通过两个指针 prev 和 p 进行遍历，prev从头节点开始，p从 头节点的next域开始，两个指针同步前进同步停止。当 p->data == val（传进来的值）时，循环结束返回 prev的值否则当p ==NULL 时说明将链表遍历完成都没有找到。返回NULL；
当要查询 3 的时候，返回的是 2 的地址，此时prev->next->data == 3
代码如下：
ListNode* FindValue_Prev(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* prev = head;//head
ListNode* p = head->next;//head->next
while (p != NULL && p->data != val)//循环结束条件
{
prev = p;//先将prev向后走一步
p = p->next;//然后p向后走一步
}
if (p == NULL)//当p ==NULL 说明没有找到 返回NULL
{
prev = NULL;
}
return prev;
}
7.按数据查询（返回含有当前数据的节点）
通过调用查找前驱的函数找到它的前驱，那么前驱的后继就是当前查询的节点。如果p 是NULL 的话，说明没有找到代码如下：
ListNode* FindValue(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* p = FindPos_Prev(head, val);//调用查找前驱的函数
if (p != NULL)
{
p = p->next;
}
return p;
}
8.按pos位置查节点的前驱
通过两个指针 prev 和 p 和一个计数器 i 进行遍历，prev从头节点开始，p从 头节点的next域开始，两个指针同步前进同步停止。但是在循环之前需要判断 pos位置是否合法。当pos<1 时 返回NULL
当 p == NULL 的时候说明没有找到退出循环返回 NULL当 i==pos 时 说明找到了这个数据的节点，此时返回prev
代码如下：
ListNode* FindPos_Prev(LinkList head, int pos)
{
assert(head != NULL);
int i = 1;
ListNode* prev = head;
ListNode* p = head->next;
if (pos < 1)
{
return NULL;
}
while (p != NULL && i < pos)
{
prev = p;
p = p->next;
i = i + 1;
}
if (p == NULL)
{
prev = NULL;
}
return prev;
}
9.按pos位置查节点
通过调用查找前驱的函数找到它的前驱，那么前驱的后继就是当前查询的节点。如果p 是NULL 的话，说明没有找到代码如下：
ListNode* FindPos(LinkList head, int pos)
{
assert(head != NULL);
ListNode* p = FindPos_Prev(head,pos);
if (p != NULL)
{
p = p->next;
}
return p;
}
10.按照节点插入数据
我们认为，形参中传入进来的节点地址就是存在的（通过其他函数嵌套使用，并不可单独使用）直接插入即可。
首先通过 **Buynode（）**函数申请一个节点，保存val值然后把ptr->next赋值给s->next 此时s和ptr都指向 300 这个地址然后将 s 的地址赋值给 ptr->next ，完成插入
代码如下：
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val)
{
assert(head != NULL);
if (NULL == ptr)
{
return false;
}
ListNode* s = Buynode();
s->data = val;
s->next = ptr->next;
ptr->next = s;
return true;
}
11.头插法
首先通过 **Buynode（）**函数申请一个节点，保存val值然后把头节点指向的next的地址赋值给 s->next
最后 把s 的地址赋值给头节点的next域
代码如下：
void Push_Front(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* s = Buynode();
s->data = val;
s->next = head->next;
head->next = s;
}
12.尾插法
先使用一个p指针遍历链表到 p->next == NULL 说明此时p指针所指向的节点就是尾节点使用**Buynode（）**申请一个节点，将val值赋值给s 并且将s->next置为空
最后将 s 的地址赋值给 p->next ，完成尾插
代码如下：
void Push_Back(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* p = head;
ListNode* s = Buynode();
while (p->next != NULL)
{
p = p->next;
}
//退出循环后p指向尾节点
s->data = val;
s->next = p->next;
p->next = s;
}
13.按pos位置插入
首先判断pos的合法性，如果pos<1则退出然后用while循环判断链表是否结束以及 计数链表的位置此时while循环有两种情况结束
当 s->next == NULL 时，说明 s指向的链表的尾部，此处退出循环，判断pos和i的关系如果pos>i 说明pos位置远远大于链表有效长度，无法插入。
当 i>pos 退出循环时，说明已经找到了pos位置，并且s->next就是待插入位置，此时调用**Insert_Next（）**函数，传入s的地址，完成插入
代码如下：
bool InsertPos(LinkList head, int pos, ElemType val)
{
assert(head != NULL);
if (pos < 1)
{
return false;
}//判断p的合法性
ListNode* s = head;
int i = 1;//计数链表位置
while (s->next != NULL && i < pos)
{
s = s->next;
i++;
}
if (pos > i)
{
return false;
}
return Insert_Next(head, s, val);
14.删除ptr指针后续节点
我们认为，形参中传入进来的节点地址就是存在的（通过其他函数嵌套使用，并不可单独使用）直接删除即可。首先 用一个指针保存ptr ->next 的值（也就是待删除结点的地址）
然后将 p->next 的值赋值给 ptr->next
最后使用 Freenode（）函数释放p节点
完成删除
代码如下：
bool Earse_Next(LinkList head, ListNode* ptr)
{
assert(head != NULL);
if (ptr == NULL||ptr->next==NULL)//判断ptr和ptr->next是一个有效值
{
return false;
}
ListNode* p = ptr->next;
ptr->next = p->next;
Freenode(p);//释放节点
return true;
}
15.删除第一个节点
直接调用 **Earse_Next（）**函数，传入头节点头节点的后续节点就是第一个节点。代码如下：
void Pop_Front(LinkList head)
{
assert(head != NULL);
Earse_Next(head, head);
}
16.删除最后一个节点
通过两个指针 pre和 p分别指向头节点和头节点的下一个节点使用while循环找到 最后一个节点的前驱然后调用 **Earse_Next（）**函数，完成删除代码如下：
void Pop_Back(LinkList head)
{
assert(head != NULL);
ListNode* pre = head;
ListNode* p = head->next;
while (p != NULL && p->next != NULL)
{
pre = p;
p = p->next;
}
Earse_Next(head, pre);
}
17.删除数据域和val相等的元素
通过 **FindPos_Prev（）函数查到val数据的节点地址然后通过Earse_Next（）**函数，完成删除代码如下：
bool Remove(LinkList head, ElemType val)
{
assert(head != NULL);
return Earse_Next(head, FindPos_Prev(head, val));
}
18.删除数据域和val相等的所有元素
通过while循环 不断调用**FindValue_Prev（）函数返回地址然后通过通过Earse_Next（）函数，完成删除一个数据直到FindValue_Prev（）**函数返回地址为NULL的时候，说明链表里没有这个数据退出循环，完成删除。代码如下：
void Remove_ALL(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* s = NULL;
while ((s = FindValue_Prev(head, val)) != NULL)
{
Earse_Next(head, s);
}
}
19.清空链表
不断调用头删函数，直到除了头节点以外没有任何节点（判空函数）代码如下：
void ClearList(LinkList head)
{
assert(head != NULL);
while (!IsEmpty(head))
{
Pop_Front(head);
}
}
20.销毁链表
清空链表并且释放头节点代码如下：
void DestroyList(LinkList head)
{
assert(head != NULL);
ClearList(head);
Freenode(head);
}
四.完整代码
1. My_LinkList.h
#ifndef MY_LINKLIST_S#define MY_LINKLIST_Stypedef int ElemType;typedef struct ListNode{<!-- -->ElemType data;//数据元素struct ListNode* next;//指针域}ListNode,*LinkList;//初始化函数 headListNode* InitList();//清空链表void ClearList(LinkList head);//销毁链表void DestroyList(LinkList head);//判空函数 bool IsEmpty(LinkList head);//返回数据节点的个数int GetSize(LinkList head);//传入头节点打印函数void PrintList(LinkList head);//按数据查询返回含有此数据节点的前驱ListNode* FindValue_Prev(LinkList head, ElemType val);//按数据查询 返回含有当前数据的节点ListNode* FindValue(LinkList head, ElemType val);//按pos位置查节点ListNode* FindPos(LinkList head, int pos);//按pos位置查节点的前驱ListNode* FindPos_Prev(LinkList head, int pos);//按节点插入bool Insert_Next(LinkList head, ListNode* ptr, ElemType val);//从头插入void Push_Front(LinkList head, ElemType val);//尾插法void Push_Back(LinkList head, ElemType val);//按pos位置插入bool InsertPos(LinkList head, int pos, ElemType val);//删除ptr指针后续节点bool Earse_Next(LinkList head, ListNode* ptr);//删除第一个节点void Pop_Front(LinkList head);//删除最后一个节点void Pop_Back(LinkList head);//删除数据域和val相等的元素bool Remove(LinkList head, ElemType val);//删除数据域和val相等的所有元素void Remove_ALL(LinkList head, ElemType val);#ifndef MY_LINKLIST_S
#define MY_LINKLIST_S
typedef int ElemType;
typedef struct ListNode
{
ElemType data;//数据元素
struct ListNode* next;//指针域
}ListNode,*LinkList;
//初始化函数 head
ListNode* InitList();
//清空链表
void ClearList(LinkList head);
//销毁链表
void DestroyList(LinkList head);
//判空函数
bool IsEmpty(LinkList head);
//返回数据节点的个数
int GetSize(LinkList head);
//传入头节点打印函数
void PrintList(LinkList head);
//按数据查询返回含有此数据节点的前驱
ListNode* FindValue_Prev(LinkList head, ElemType val);
//按数据查询 返回含有当前数据的节点
ListNode* FindValue(LinkList head, ElemType val);
//按pos位置查节点
ListNode* FindPos(LinkList head, int pos);
//按pos位置查节点的前驱
ListNode* FindPos_Prev(LinkList head, int pos);
//按节点插入
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val);
//从头插入
void Push_Front(LinkList head, ElemType val);
//尾插法
void Push_Back(LinkList head, ElemType val);
//按pos位置插入
bool InsertPos(LinkList head, int pos, ElemType val);
//删除ptr指针后续节点
bool Earse_Next(LinkList head, ListNode* ptr);
//删除第一个节点
void Pop_Front(LinkList head);
//删除最后一个节点
void Pop_Back(LinkList head);
//删除数据域和val相等的元素
bool Remove(LinkList head, ElemType val);
//删除数据域和val相等的所有元素
void Remove_ALL(LinkList head, ElemType val);
2. My_LinkList.cpp
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include"My_LinkList.h"
ListNode* Buynode()//购买节点
{
ListNode* s = (ListNode*)malloc(sizeof(ListNode));
if (s == NULL) exit(1);
memset(s, 0, sizeof(ListNode));//将节点内数据全部填充为0
return s;//返回申请成功的节点地址
}
void Freenode(ListNode*p)
{
free(p);
p = NULL;//防止野指针
}
bool IsEmpty(LinkList head)
{
assert(head != NULL);
return head->next == NULL;
}
int GetSize(LinkList head)
{
assert(head != NULL);
int size = 0;
LinkList p = head->next;
while (p != NULL)
{
size++;
p = p->next;
}
return size;
}
ListNode* InitList()
{
ListNode* s = Buynode();
s->next = NULL;
return s;
}
void PrintList(LinkList head)
{
assert(head != NULL);
ListNode* p = head->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
ListNode* FindValue(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* p = FindPos_Prev(head, val);
if (p != NULL)
{
p = p->next;
}
return p;
}
ListNode* FindValue_Prev(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* prev = head;//head
ListNode* p = head->next;//head->next
while (p != NULL && p->data != val)
{
prev = p;
p = p->next;
}
if (p == NULL)
{
prev = NULL;
}
return prev;
}
ListNode* FindPos(LinkList head, int pos)
{
assert(head != NULL);
ListNode* p = FindPos_Prev(head,pos);
if (p != NULL)
{
p = p->next;
}
return p;
}
ListNode* FindPos_Prev(LinkList head, int pos)
{
assert(head != NULL);
int i = 1;
ListNode* pre = head;
ListNode* p = head->next;
if (pos < 1)
{
return NULL;
}
while (p != NULL && i < pos)
{
pre = p;
p = p->next;
i = i + 1;
}
if (p == NULL)
{
pre = NULL;
}
return pre;
}
bool Insert_Next(LinkList head, ListNode* ptr, ElemType val)
{
assert(head != NULL);
if (NULL == ptr)
{
return false;
}
ListNode* s = Buynode();
s->data = val;
s->next = ptr->next;
ptr->next = s;
return true;
}
void Push_Front(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* s = Buynode();
s->data = val;
s->next = head->next;
head->next = s;
}
void Push_Back(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* p = head;
ListNode* s = Buynode();
while (p->next != NULL)
{
p = p->next;
}
s->data = val;
s->next = p->next;
p->next = s;
}
bool InsertPos(LinkList head, int pos, ElemType val)
{
assert(head != NULL);
if (pos < 1)
{
return false;
}
ListNode* s = head;
int i = 1;
while (s->next != NULL && i < pos)
{
s = s->next;
i++;
}
if (pos > i)
{
return false;
}
return Insert_Next(head, s, val);
/*
p->data = val;
p->next = s->next;
s->next = p;
*/
}
bool Earse_Next(LinkList head, ListNode* ptr)
{
assert(head != NULL);
if (ptr == NULL||ptr->next==NULL)
{
return false;
}
ListNode* p = ptr->next;
ptr->next = p->next;
Freenode(p);
return true;
}
void Pop_Front(LinkList head)
{
assert(head != NULL);
Earse_Next(head, head);
}
void Pop_Back(LinkList head)
{
assert(head != NULL);
ListNode* pre = head;
ListNode* p = head->next;
while (p != NULL && p->next != NULL)
{
pre = p;
p = p->next;
}
Earse_Next(head, pre);
}
bool Remove(LinkList head, ElemType val)
{
assert(head != NULL);
return Earse_Next(head, FindPos_Prev(head, val));
/*
ListNode* pre = head;
ListNode* p = head->next;
while (p != NULL && p->data != val)
{
pre = p;
p = p->next;
}
if (p != NULL)
{
Earse_Next(head, pre);
}
*/
}
void Remove_ALL(LinkList head, ElemType val)
{
assert(head != NULL);
ListNode* s = NULL;
while ((s = FindValue_Prev(head, val)) != NULL)
{
Earse_Next(head, s);
}
}
void ClearList(LinkList head)
{
assert(head != NULL);
while (!IsEmpty(head))
{
Pop_Front(head);
}
}
void DestroyList(LinkList head)
{
assert(head != NULL);
ClearList(head);
Freenode(head);
}
到此这篇关于数据结构之带头结点的单链表的文章就介绍到这了,更多相关带头结点的单链表内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！
