【C++】单链表的创建、插入、删除

1.前言

最近没啥心情搞机器人，一直在仿真，输了呀。索性搞搞C++算法。虽然大二的时候学过数据结构，但是上的太水了。。。不过基本概念还是很清楚，所以就简单的用程序实现一下吧，顺便学习了：

struct结构体

还有指针的应用

2.代码实现

首先定义结构体Node，来为每个结点定义，我理解的结构体为一种新的数据类型，相当于int、double这种，只不过该数据类型里面又有很多小的数据，不知道这样理解对不对……还需要加强基础的学习啊

struct Node
{
	int data;
	struct Node *next;  //该指针指向下一个结构体，next为一个结点的指针，和header效果一样
};

2.1.单链表的创建

Node *CreateLinkedList(int a[], int number)   //相当于将Node当成一个新的数据类型，因为要返回的是一个指针，所以定义为Node *
{
	Node *header_node;  
	Node *current_node;   //定义两个结构体指针

	header_node = new Node;  //为header开辟新空间
	current_node = header_node;  //当前工作指针指向头节点

	for(int i = 0; i < number; i++)
	{
		Node *templt = new Node;  //为临时结点开辟新空间
		templt->data = a[i];
		templt->next = nullptr;
		current_node->next = templt;
		current_node = templt;
	}
	
	return header_node;
};

因为我们的结点定义的是一个指针，所以对结构体中的变量使用时要使用->，而不是“.”。因为结构体相当于是一种数据类型，且返回值是一个指向结构体的指针，所以定义函数时用的是 Node *，和int *类似哦。

2.2.其他函数

搞懂了2.1后，其他的函数编写就很简单明了了，具体原理就不赘述了。

#include <iostream>
using namespace std;

#define MAXSIZE 10

struct Node
{
	int data;
	struct Node *next;  //该指针指向下一个结构体，next为一个结点的指针，和header效果一样
};

Node *CreateLinkedList(int a[], int number);
int LengthOfList(Node *header_node);
void ShowList(Node *header_node);
Node *DeleteNode(Node *header_node, int pos);
Node *AddNode(Node *header_node, int pos, int add_number);

Node *CreateLinkedList(int a[], int number)   //相当于将Node当成一个新的数据类型，因为要返回的是一个指针，所以定义为Node *
{
	Node *header_node;  
	Node *current_node;   //定义两个结构体指针

	header_node = new Node;  //为header开辟新空间
	current_node = header_node;  //当前工作指针指向头节点

	for(int i = 0; i < number; i++)
	{
		Node *templt = new Node;  //为临时结点开辟新空间
		templt->data = a[i];
		templt->next = nullptr;
		current_node->next = templt;
		current_node = templt;
	}
	
	return header_node;
};

int LengthOfList(Node *header_node)
{
	Node *cur = header_node;
	if(header_node->next == nullptr)
	{
		cout << "该表无数据" << endl;
		return 0;
	}
	else
	{
		int length = 0;
		while(cur->next != nullptr)
		{
			length++;
			cur = cur->next;
		}
		return length;
	}
}

void ShowList(Node *header_node)
{
	Node *cur = header_node;
	for(int i = 0; i < LengthOfList(header_node); i++)
	{
		cout << cur->next->data << endl;
		cur = cur->next;
	}
}

Node *DeleteNode(Node *header_node, int pos)  //删除头结点后第pos个结点，pos大于0
{
	int length = LengthOfList(header_node);
	if(pos <= 0 || length == 0)
	{
		cout << "删除错误" << endl;
	}
	else
	{
		cout << "删除头结点后第" << pos << "个结点：" << endl;
		Node *cur = header_node;  //定义当前指针
		Node *pre = cur;  //定义上一个位置的指针
		for(int i = 0; i < pos; i++)  //移动当前指针到要删除的位置
		{
			pre = cur;
			cur = cur->next;
		}
		if(pos == length)
			pre->next = nullptr;
		else
			pre->next = cur->next;
	}
	return header_node;
}

Node *AddNode(Node *header_node, int pos, int add_number)  //在头结点后第pos个结点后面插入新结点，pos>=0
{
	int length = LengthOfList(header_node);
	if(pos < 0 || pos > length || length == 0)
	{
		cout << "插入错误" << endl;
	}	
	else
	{
		cout << "在头结点后第" << pos << "个结点的后面插入元素：" << endl;
		Node *cur = header_node;  //定义当前指针
		Node *new_node = new Node;  //为新加入的结点开辟空间
		new_node->data = add_number;
		for(int i = 0; i < pos; i++)
		{
			cur = cur->next;
		}		
		if(pos == length)
		{
			cur->next = new_node;
			new_node->next = nullptr;
		}
		else
		{
			new_node->next = cur->next;
			cur->next = new_node;
		}
	}
	return header_node;
}

2.3.使用

#include <iostream>
#include "linked_list.hpp"
using namespace std;

int main()
{
	int a[] = {1, 2, 3, 4};
	Node *my_header = CreateLinkedList(a, 4);
	ShowList(my_header);  //my_header已经是一个*Node，所以不用加*
	int length = LengthOfList(my_header);
	cout << "该表长" << length << endl;
	my_header = DeleteNode(my_header, 1);
	ShowList(my_header);
	my_header = AddNode(my_header, 1, 100);
	ShowList(my_header);
}

3.结果

编写makefile：

linkedlist: main.o
	g++ -o linkedlist main.o
main.o: main.cpp linked_list.hpp
	g++ -c main.cpp
clean:
	rm -f *.o

使用make命令后使用:

./linkedlist