• C++数据结构X篇_04_单向链表框架搭建、实现和测试(链表的定义，常用操作的实现等)

    接上篇C++数据结构X篇_03_线性表的顺序存储和动态数组案例（基本概念；操作要点；顺序存储算法；动态数组案例实现），本篇将会开始介绍线性表的链式存储。
    参考博文：最详细的C++单向链表实现，文中采用C++的class去实现单向链表，这与本文采用struct的形式是类似的，先看参考博文，再看此文（后期将其整理至本篇“C++实现代码及解析”部分），本文为了与学习视频一致，仍采用struct的形式介绍单向链表。

    单向链表框架搭建、实现和测试

    1 基本概念

    1.1 链式存储定义

    为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要存储指示其直接后继的信息。
    在这里插入图片描述

    1.2 单向链表

    链表是数据结构中常见的一种数据存储形式，其在物理存储单元上是非连续的存储结构，即其数据存储的空间并非连续的内存空间。这种存储方式的优点是可以动态分配内存空间，不会造成内存的浪费和溢出，同时链表对于执行插入、删除等操作十分简便，不需要移动大量元素，但是其相对于连续空间存储的数据相比，遍历速度较慢。

    1.2.1单向链表概念

    在这里插入图片描述
    链表由多个node(节点)组成，每个节点中由数据域与指针域组成，数据域data中存储需要存储的数据，指针域next为一个指针，其指向下一个node的地址。
    当多个node前后链接在一起时就形成了lis(链表)：
    在这里插入图片描述
    list中每个node通过指针next前后相联系，但要注意list中最后一个node由于没有后续的node,因此其next指正是指向NULL的。

    1.2.2 链表插入

    在这里插入图片描述
    对于一个链表list若想把Node n插入Node 0与Node 1之间，只需要将Node 0的next指针指向Node n的地址，再把Node n的next指针指向Node 1的地址即可。

    1.2.3 链表删除

    在这里插入图片描述
    若想删除节点Node 2，只需要将其前一节点Node 1的next指针指向其后一节点Node 3的地址，再将Node 2的内存空间delete掉即可。

    2 C实现代码

    以下是在VS IDE中已经有一个项目的情况下如何增加一个新的项目“ListTest2”
    在这里插入图片描述
    与上篇一致，此部分将会按照搭建，实现，测试进行介绍

    2.1 单向链表框架搭建（.h文件）

    #pragma once
#ifndef LINKLIST_H
#define LINKLIST_H

//list是由节点组成，先定义一个链表节点
typedef struct LINKNODE
{
	void* data;  //无类型指针，指向任何类型数据
	struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef struct LINKLIST 
{
	LinkNode* head;
	//无需容量，链表是来一个节点就申请一个内存，据需申请内存
	int size;
}LinkList;

//打印回调函数指针，返回是void
typedef void(*PRINTLINKNODE)(void*);

//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list,int pos,void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list,int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list,void* data);
//打印链表节点
//用户可能传入任何数据类型，但是传进后都会转成void*
//我们无法知道用户传入的是什么类型,不确定的时候让用户去做
//给函数，遍历的时候将void*数据类型传给函数，让用户打印
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//返回第一个节点
void* Front_LinkList(LinkList* list);
//释放链表内存
void FreeSpace_LinkList(LinkList* list);

#endif

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43

    2.2 单向链表框架实现（.cpp文件）

    #include "LinkList.h"
#include
#pragma once

//初始化链表
LinkList * Init_LinkList()
{
	LinkList * list = (LinkList*)malloc(sizeof(LinkList));
	list->size = 0;
	//头结点 不保存数据信息 为了实现链表下少考虑几种情况
	//比如在插入时少考虑是否插入头部
	list->head = (LinkNode *)malloc(sizeof(LinkNode));
	list->head->data = NULL;
	list->head->next = NULL;

	return list;
}
//指定位置插入
void Insert_LinkList(LinkList * list, int pos, void * data)
{
	if (list==NULL)
	{
		return;
	}
	if (data == NULL)
	{
		return;
	}
	//友好的处理，pos越界，默认插入到尾部
	if (pos< 0 || pos>list->size)
	{
		pos = list->size;
	}

	//创建新的节点
	LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
	newnode->data = data;
	newnode->next = NULL;

	//找节点
	//辅助指针变量
	LinkNode* pCurrent = list->head;
	for (int i=0;i<pos;i++)
	{
		pCurrent = pCurrent->next;
	}

//新节点入链表：newnode的next指向第pos-1的next也就是原先第pos个node，然后再让第pos-1的next指向newnode
//list实际第0个是head;head->next与newnode->next一致,即newnode的next指向head的next;
newnode->next = pCurrent->next; 
//head的next又指向newnode
pCurrent->next = newnode;

	list->size++;

}
//删除指定位置的值
void RemoveByPos_LinkList(LinkList * list, int pos)
{
	if (list == NULL)
	{
		return;
	}

	if (pos< 0 || pos>= list->size)
	{
		return;
	}

	//查找删除节点的前一个节点
	LinkNode* pCurrent = list->head;
	for (int i = 0; i < pos; i++)
	{
		pCurrent = pCurrent->next;
	}

	//缓存删除的节点
	LinkNode* pDel = pCurrent->next;
	pCurrent->next = pDel->next;

	//释放删除节点的内存
	free(pDel);

	list->size--;
}
//获得链表的长度
int Size_LinkList(LinkList * list)
{
	return list->size;
}
//查找
int Find_LinkList(LinkList * list, void * data)
{
	if (list == NULL)
	{
		return 0;
	}
	if (data == NULL)
	{
		return 0;
	}
	//遍历查找 head不保存有效数据 list->head->next指向第一个有效数据
	LinkNode* pCurrent = list->head->next;
	int i = 0;
	while (pCurrent!=NULL)
	{
		if (pCurrent->data == data)
		{
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}

	return i;
}
//打印链表节点
void Print_LinkList(LinkList * list, PRINTLINKNODE print)
{
	if (list == NULL)
	{
		return;
	}

	//辅助指针变量
	LinkNode* pCurrent = list->head->next;
	while (pCurrent != NULL)
	{
		print(pCurrent->data);
		pCurrent = pCurrent->next;
	}

}
//返回第一个节点
void * Front_LinkList(LinkList * list)
{
	return list->head->next->data;
}
//释放链表内存
void FreeSpace_LinkList(LinkList * list)
{
	if (list == NULL)
	{
		return;
	}

	//每一个节点都需要手动释放
	//辅助指针变量
	LinkNode* pCurrent = list->head;
	//不能找到一个节点就进行释放，需要先缓存下一个节点，然后删除当前节点
		while (pCurrent != NULL)
		{
         //缓存下一个节点
			LinkNode* pNext = pCurrent->next;

			free(pCurrent);

			pCurrent = pNext;
		}

		//释放链表内存
		list->size = 0;
		free(list);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164

    2.3 单向链表测试（客户测试）

    

#include 
#include "LinkList.h"

//自定义数据类型
typedef struct PERSON {
	char name[64];
	int age;
	int score;
} Person;

//打印函数
void MyPrint(void* data) {
	Person* p = (Person*)data;
	printf("Name:%s Age:%d Score:%d\n",p->name,p->age,p->score);
}

int main()
{
    //创建链表
	LinkList* list = Init_LinkList();

	//创建数据
	Person p1 = {"aaa",18,100};
	Person p2 = { "bbb",19,99 };
	Person p3 = { "ccc",20,101 };
	Person p4 = { "ddd",17,97 };
	Person p5 = { "eee",16,59 };

	//数据插入链表
	Insert_LinkList(list,0,&p1);
	Insert_LinkList(list, 0, &p2);
	Insert_LinkList(list, 0, &p3);
	Insert_LinkList(list, 0, &p4);
	Insert_LinkList(list, 0, &p5);

	//打印 打印顺序为p5 p4 p3...
	Print_LinkList(list,MyPrint);

	//删除3 也就是从p5往前从0数到3，即为p2
	RemoveByPos_LinkList(list, 3);

	//增加分隔符之后进行打印
	printf("---------------------\n");
	Print_LinkList(list, MyPrint);

	//返回第一个节点
	printf("---------查找结果------------\n");
	 Person* ret= (Person*)Front_LinkList(list);
	 printf("Name:%s Age:%d Score:%d\n", ret->name, ret->age, ret->score);

	//销毁链表
	FreeSpace_LinkList(list);

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    测试结果：
    在这里插入图片描述

    1. 参考视频地址：单向链表框架搭建单向链表框架实现，单向链表测试

    2. 上述源代码见：博文C++数据结构X篇-04-单向链表框架搭建、实现和测试(链表的定义，常用操作的实现等)的配套资源

    3. 最详细的C++单向链表实现的代码如下：

    
#include 
using namespace std;

class node 
{
public:
	int data; //存储数据
	node* next; //指向下一个node的地址
};

class list 
{
public:
	node* head; //指向链表首位node
	int size;   //链表中的node的个数
};

//链表初始化
list* list_init()
{
	list* L = new list; //创建一个链表L
	L->size = 0; //初始node个数设置为0
	L->head = new node; //创建链表中的第一个node
	L->head->data = NULL; //将第一个node中存储的data设为空
	L->head->next = NULL; //将第一个node中存储的next指针设为空
	return L;
}

//链表的数据插入
void list_insert(list* L,int pos,int data)
{
	//如果数据为空，则从头插入
	if (L == NULL)
	{
		pos = 0;
	}

	//创建新节点并把数据放入
	node* new_node = new node;
	new_node->data = data;
	new_node->next = NULL;

	//寻找pos-1号的位置
	node* pos_node = L->head; //0号node
	for (int i = 0; i < pos; i++)
	{
		//将下一个node的地址赋给pos_node地址，相当于地址在不断向后移动
		pos_node = pos_node->next; //获得pos-1号node(pos_node)
	}

	//新节点入链表
	new_node->next = pos_node->next; //将new_node的next指向第pos号的node地址
	pos_node->next = new_node; //pos-1的node指向new_node

	L->size++;

}

//链表的数据删除
void list_remove_pos(list* L,int pos)
{
	//判断链表是否为空
	if (L == NULL)
	{
		return;
	}
	
	//找到需要删除的前一个节点
	node* pos_node = L->head;
	for (int i = 0; i < pos; i++)
	{
		pos_node = pos_node->next;
	}

	//删除pos的节点
	pos_node->next = pos_node->next->next;
	L->size--;
}

//打印链表
void list_print(list* L)
{
	if (L == NULL)
	{
		cout << "链表中没有数据" << endl;
	}

	//遍历打印
	node* pcurrent = L->head->next;
	while(pcurrent !=NULL)
	{
		cout << pcurrent->data << endl;
		pcurrent = pcurrent->next;
	}
	cout << endl;
}
int main()
{
    //创建链表
	list* L = list_init();
	//插入数据
	for (int i=0;i<10;i++)
	{
		list_insert(L, i, i);
	}
	cout << "插入0-9的链表为：" << endl;
	list_print(L);

	//删除指定位置
	list_remove_pos(L, 5);
	cout << "删除第5号node后的地址为：" << endl;
	list_print(L);
	system("pause");
	return 0;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117

    3 C++实现代码及解析

    3.1 节点node的定义

    class node
{
public:
	int data;    //存储数据
	node *next;  //指向下一个node的地址
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    我们采用C++中的类去定义Node，当然你也可以用struct结构体去定义。

    3.2 链表list的定义

    class list
{
public:
	node *head;  //指向链表首位node
	int  size;   //链表中node的个数
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    此处定义的list包含两部分，链表的第一个node（head）与链表中数据数量（size）。为什么我们只包含链表中第一个node呢？难道链表不应该包含所有的node嘛？这里就体现出node的特殊性了，因为对于一个链表我们只要获得其中任意一个node，该node到链表最后的node我们都可以通过每个node中的next指针逐个访问到。因此此处链表的类，我们不需要存储每个node，只需要获得链表第一个node即可，其它node我们都可以逐个访问得到。

    3.3 链表初始化

    链表list与节点node的类我们都创建好了，怎样把两者联系起来呢？或者说我们怎样得到一个可用的链表呢？

    list* list_init()
{
	list *L=new list;  //创建一个链表L
	L->size=0;         //初始node个数设置为0
	L->head=new node;  //创建链表中第一个node
	L->head->data=	NULL; //将第一个node中存储的data设为空
	L->head->next=  NULL; //将第一个node中存储的next指针设为空
	return L;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    此处我们写了一个返回list指针的函数。

        目前为止我们已经完成了list与node类的创建并可以通过函数list_init()获得一个可用的链表，下面我们将对这个链表进行插入删除工作。

    • 1

    3.4 链表的数据插入

    void list_insert(list *L,int pos, int data)
{
	//如果数据为空则从头插入
	if (L==NULL)
	{
		pos=0;
	}
	//创建新节点并把数据放入
	node *new_node=new node;  
	new_node->data=data;
	new_node->next=NULL;
	//寻找pos-1号的位置
	node *pos_node=L->head;
	for (int i = 0; i < pos; i++)
	{
		pos_node=pos_node->next;
	}
	//新节点入链表
	new_node->next=pos_node->next;
	pos_node->next=new_node;
 
	L->size++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    该函数的作用是在链表L中第pos的位置插入一个存放data的node。

    第一眼看见这个代码是不是头皮发麻？别急我们把代码拆分，慢慢分析。

    1、我们最开始定义并获得的链表 L为NULL里面并不包含任何数据，因此我们在插入数据时需要进行判断，如果这个链表里一开始不包含任何数据，那我们将插入的位置设为头部即pos=0。

    	if (L==NULL)
	{
		pos=0;
	}

    • 1
    • 2
    • 3
    • 4

    2、在确保链表本身含有数据，可以正常插入data的时候，我们需要将这个data“包装”成链表能识别的节点new_node，此时还不知道插入位置后面的node是啥，因此需要将new_node->next设为NULL。

    	node *new_node=new node;  
	new_node->data=data;
	new_node->next=NULL;

    • 1
    • 2
    • 3

    3、我们还要寻找new_node插入位置原本的node，这里我们可以通过遍历从list中第0号的node遍历到第pos-1号的node，获得pos-1号的node（pos_node）。

    	node *pos_node=L->head;  //0号node
	for (int i = 0; i < pos; i++)
	{
		pos_node=pos_node->next;
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    4、找到list中第pos-1号的node后，我们需要将new_node的next指向第pos号的node地址，同时将pos-1号的node指向new_node的地址即可，最后别忘了list中数据个数size加1。

    	new_node->next=pos_node->next; //new_node指向pos号的node
	pos_node->next=new_node;       //pos-1号的node指向new_node
	L->size++;

    • 1
    • 2
    • 3

    3.5 链表的数据删除

    void list_remove_pos(list *L,int pos)
{
	//判断链表是否为空
	if (L ==NULL)
	{
		return;
	}
	//找到需要删除的前一个节点
	node *pos_node=L->head;
	for (int i = 0; i < pos; i++)
	{
		pos_node=pos_node->next;
	}
	//删除pos的节点
    pos_node->next=pos->next->next;
	L->size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    同样我们先将代码拆分分析。

    1、首先我们还是要判断链表L是否为空，毕竟为空的话如何进行删除工作呢？

    	//判断链表是否为空
	if (L ==NULL)
	{
		return;
	}

    • 1
    • 2
    • 3
    • 4
    • 5

    2、与数据插入相同，对于删除pos号的node我们同样选择先找到pos-1号的node，我们可以通过node(pos-1)->next=node(pos)来获得pos号的node。

    	//找到需要删除的前一个节点
	node *pos_node=L->head;
	for (int i = 0; i < pos; i++)
	{
		pos_node=pos_node->next;
	}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3、这是我们只需要将pos-1号的node指向pos+1号的node即可，最后别忘记链表L的size减1。

    	//删除pos的节点
	pos_node->next=pos->next->next;
	L->size--;

    • 1
    • 2
    • 3

    至此我们已经完成链表的插入、删除的功能了，最后附上链表L的打印函数，方便后面实验展示。

    （注意：打印过程是跳过头节点head的）

    //打印链表
void list_print(list *L)
{
	if (L->size==0)
	{
		cout<<"链表中没有数据"<<endl;
		return;
	}
	//遍历打印
	node *pcurrent=L->head->next;
	while (pcurrent != NULL)
	{
		cout<<pcurrent->data<<"\t";
		pcurrent=pcurrent->next;
	}
	cout<<endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    3.6 测试

    int main()
{
	//创建链表
	list *L=list_init();
	//插入数据
	for (int i = 0; i < 10; i++)
	{
		list_insert(L,i,i);
	}
	cout<<"插入0-9的链表为："<<endl;
	list_print(L);
	//删除指定位置
	list_remove_pos(L,5);
	cout<<"删除第5号node后的地址为："<<endl;
	list_print(L);
	system("pause");
	return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    结果为：
    在这里插入图片描述

  • 相关阅读:
    GIS工具maptalks开发手册(一)——hello world初始化
    【图像配准】基于SURF特征实现印刷体汉字配准附matlab代码
    基于springboot服饰电商平台的设计与开发-计算机毕业设计源码+LW文档
    WebSocket在node端和客户端的使用
    MCU的环形FIFO
    C# 给Word每一页设置不同文字水印
    大学生个人博客网页设计模板 学生个人博客网页成品 简单个人网站作品下载 静态HTML CSS个人网页作业源代码
    漆包线行业你了解多少？
    AgileConfig-1.7.0 发布，支持 SSO
    利用Python给女朋友跨年放个烟花
  • 原文地址：https://blog.csdn.net/Dasis/article/details/128087781