C++ 单向链表 —— 初始化、插入、返回第一个节点、删除、查找、长度、打印、反转(逆序)

单向链表的概念：

如果“一个节点”将指向“另一个节点的指针”作为数据成员，那么多个这样的节点可以连起来，只用一个变量就能够访问整个节点序列，我们称之为链表。如果序列中的节点只包含指向后继节点的链接，该链表就称之为单向链表。

01 声明：

#ifndef LINKLIST_H
#define LINKLIST_H
#include <iostream>
using namespace std;

/************************/
/*  13_01.h 文件
/************************/

typedef struct LINKNODE  //节点的定义
{
	int info;  //存储信息
	struct LINKNODE * next; 
}LinkNode;


class LinkList  //链表的定义
{
private:
	LinkNode *head;
	int size;

public:
	LinkList();  //构造函数
	~LinkList();  //析构函数(销毁链表)
	void *init();  //链表初始化
	void Insert(LinkList *list,  int pos, int data);  //插入
	void first(LinkList *list);  //返回第一个节点
	void del(LinkList *list, int pos);  //删除
	int Find(LinkList *list, int data);  //查找
	int length(LinkList *list);  //长度
	void print(LinkList *list);  //打印
	void rotate(LinkList *list);  //反转(逆序)

	int InsertPrint();  //打印节点插入的提示信息
	int DelPrint();  //打印节点删除的提示信息
	int FourteenPrint();  //打印14节点查找的提示信息
	int FiftyPrint();  //打印50节点查找的提示信息
	int RotatePrint();  //打印链表逆序的提示信息
};

#endif
           

02 功能：

#include "13_01.h"

LinkList::LinkList() {}  //构造函数


LinkList::~LinkList()  //析构函数(销毁链表)
{
	LinkNode *P = head;
	while (head)
	{
		P = head;
		head = head->next;
		delete(P);
	}
}


void *LinkList::init()  //链表初始化
{
	LinkList *list = (LinkList*)malloc(sizeof(LinkList));  //申请链表内存
	list->size = 0;
	list->head = (LinkNode*)malloc(sizeof(LinkNode));  //申请节点内存
	list->head->info = NULL;
	list->head->next = NULL;
	
	return list;
}


void LinkList::Insert(LinkList *list, int pos, int data)  //插入(pos是位置)
{
	if (list == NULL)
	{
		return;
	}

	if (data == NULL)
	{
		return;
	}

	if (pos < 0 || pos > list->size)  //pos位置越界的时候，把节点从尾部插入
	{
		pos = list->size;  //例如：size = 5，当输入位置 pos = 9 的时候，插入的位置仍是 5
	}

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

	LinkNode *pCurrent = list->head;
	for (int i = 0; i < pos; i++)  //根据pos找出插入节点的位置 ( i 是数位置，i 根据pos数值对应next指针)
	{
		pCurrent = pCurrent->next;  //移动节点
	}

	NewNode->next = pCurrent->next;  //新节点插入链表
	pCurrent->next = NewNode;  //将NewNode本身的地址赋给pCurrent指向的下一个地址
	list->size++;  //链表的长度增加
}


void LinkList::first(LinkList *list)  //返回第一个节点
{
	cout << "节点第一：" << list->head->next->info << endl << endl;
	return;
}


void LinkList::del(LinkList *list, int pos)  //删除(pos是位置)
{
	if (list == NULL)
	{
		return;
	}

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

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

	LinkNode *pDel = pCurrent->next;
	pCurrent->next = pDel->next;  //删除节点后，把后面的节点接上去

	delete(pDel);  

	list->size--;
}


int LinkList::Find(LinkList *list, int data)  //查找
{
	if (list == NULL)
	{
		return -1;
	}

	if (data == NULL)
	{
		return -1;
	}

	LinkNode *pCurrent = list->head->next;  //遍历查找从头指针开始
	int i = 0;
	while (pCurrent != NULL)  //遍历查找
	{
		if (pCurrent->info == data)
		{
			break;
		}
		i++;
		pCurrent = pCurrent->next;
	}

	if (i < list->size)
	{
		cout << "查找成功！节点的位置是“ " << i << " ” " << endl << endl;
	}
	else
	{
		cout << "查找失败！节点不存在。" << endl << endl;
	}

	return i;
}


int LinkList::length(LinkList *list)  //长度
{
	cout << "链表长度：" << list->size << endl << endl;
	return -1;
}


void LinkList::print(LinkList *list)  //打印
{
	if (list == NULL)
	{
		return;
	}

	LinkNode * pCurrent = list->head->next;
	cout << "链表打印：";
	while (pCurrent != NULL)
	{
		cout << pCurrent->info << " ";
		pCurrent = pCurrent->next;
	}
	cout << endl << endl;  //换行
}


void LinkList::rotate(LinkList *list)  //反转(逆序)
{
	LinkNode *head = NULL, *pCurrent, *pNext, *pPrev;
	pPrev = (LinkNode*)malloc(sizeof(LinkList));
	if (pPrev == NULL)
	{
		return;
	}

	pPrev->next = list->head->next;
	pCurrent = list->head->next;
	while (pCurrent->next)
	{
		pNext = pCurrent->next;
		pCurrent->next = pNext->next;
		pNext->next = pPrev->next;
		pPrev->next = pNext;
	}

	while (pPrev->next != NULL)
	{
		cout << pPrev->next->info << " ";
		pPrev = pPrev->next;
	}
	cout << endl << endl;

	return;
}


int LinkList::InsertPrint()  //打印节点插入的提示信息
{
	cout << "节点插入：" << "11 12 13 14 15 16" << endl << endl;
	return 0;
}

int LinkList::DelPrint()  //打印节点删除的提示信息
{
	cout << "节点删除：16" << endl << endl;
	return 0;
}

int LinkList::FourteenPrint()  //打印14节点查找的提示信息
{
	cout << "节点查找：“ 14 ”" << endl << endl;
	return 0;
}

int LinkList::FiftyPrint()  //打印50节点查找的提示信息
{
	cout << "节点查找：“ 50 ”" << endl << endl;
	return 0;
}

int LinkList::RotatePrint()  //打印链表逆序的提示信息
{
	cout << "链表反转：";
	return 0;
}
           

03 执行：

#include "13_01.h"
#include <iostream>
using namespace std;

/********************************************************************************************************/
/*  单向链表  ——  初始化、插入、返回第一个节点、删除、查找、长度、打印、反转(逆序)
/*******************************************************************************************************/

int main(void)
{
	LinkList L;  //实例化
	LinkList *list = (LinkList*)L.init();

	L.InsertPrint();  //打印节点插入的提示信息
	L.Insert(list, 0, 11);  //根据0、1、2、3、4、5的位置插入节点
	L.Insert(list, 1, 12);
	L.Insert(list, 2, 13);
	L.Insert(list, 3, 14);
	L.Insert(list, 4, 15);
	L.Insert(list, 5, 16);

	L.first(list);  //返回第一个节点
	L.DelPrint();  //打印节点删除的提示信息
	L.del(list, 5);  //删除位置为“ 5 ”的节点“ 16 ”
	L.FourteenPrint();  //打印14节点查找的提示信息
	L.Find(list, 14);  //查找（成功）
	L.FiftyPrint();  //打印50节点查找的提示信息
	L.Find(list, 50);  //查找（失败）
	L.length(list);  //长度
	L.print(list);  //打印
	L.RotatePrint();  //打印链表逆序的提示信息
	L.rotate(list);  //反转（逆序）

	system("pause");  //调试时，黑窗口不会闪退，一直保持
	return 0;
}
           

运行结果：