目录
  • 一、单链表的概念
  • 二、结构体声明：
  • 三、函数
    • 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);
}
    声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。