数据结构-链表实现（单链表，双链表，类实现）

桃扇骨 2022-05-28 12:54 312阅读 0赞

## 1.单链表 ##

1）单的意思就是说只有一个方向，所以**只能往一个方向增加节点**。

2）也因为单（身）所以处理起来很寂寞，注意几点吧：

A）创建和遍历需要一个**头节点（不含数据）**，和**一个尾节点**。

B）**删除和插入都要在前一节点**（比如要删除第二个节点，需要在第一个节点操作，又如在第三个节点前插入一个节点，得在第二个节点操作），所以后面类实现的成员函数一般都是找目标的前一节点。

### 类实现（创建，析构，删除，插入，输出） ###

####  ####

###  ###

/*by szu_crayon 2018/3/7*/
    #include<iostream>
    using namespace std;
    class MyList
    {
    private:
    	struct Node{
    		int Data;
    		Node* Next;
    	};
    	Node* Head;  //头节点
    	Node* Tail;  //尾节点
    public:
    	MyList()    //创建头节点
    	{
    		Head = new Node;
    		Head->Data = NULL; Head->Next = NULL;
    		Tail = Head;
    	}
    	~MyList()    //释放链表空间
    	{
    		Node* Temp;
    		while (Head)
    		{
    			Temp = Head;
    			Head = Head->Next;
    			delete Temp;
    		}
    	}
    	void AddNode(int num)      //从尾部增加节点
    	{
    		Node *NewNode = new Node;
    		NewNode->Data = num; NewNode->Next = NULL;    //增加节点的时候新节点后面没有元素所以next指向空
    		Tail->Next = NewNode; Tail = NewNode;      //Tail连接新节点，然后新节点作为新的尾节点
    	}
    	int ListSize()           //返回链表元素个数
    	{
    		int cnt = 0;
    		Node* Temp = Head;
    		while (Temp->Next != NULL)
    		{
    			Temp = Temp->Next;
    			cnt++;
    		}
    		return cnt;
    	}
    	Node* FindNode(int Index)         //返回所查找下标的前一个节点
    	{
    		Node* Temp = Head;
    		int cnt = 0;
    		while (Temp->Next != NULL)
    		{
    			cnt++;
    			if (cnt == Index)
    				return Temp;
    			Temp = Temp->Next;
    		}
    		return NULL;     //no find
    	}
    	Node* FindNum(int num)     //返回查找数字所在节点的前一节点
    	{
    		Node* Temp = Head;
    		while (Temp->Next != NULL)
    		{
    			if (Temp->Next->Data == num)
    				return Temp;
    			Temp = Temp->Next;
    		}
    		return NULL;     //no find
    	}
    	int DeleteNode(Node* FindedNode)    //删除指定位置的节点
    	{
    		if (FindedNode)
    		{
    			Node* Temp = FindedNode->Next;
    			FindedNode->Next = Temp->Next;
    			delete Temp;
    			return 1;
    		}
    		return 0;
    	} 
    	void InsertNode(int Index,int num)          //指定位置插入一个数据为num的节点
    	{
    		if (Index - 1 == ListSize())    //如果指定位置刚好比链表元素多1，那么相当于在尾部增加节点
    		{
    			AddNode(num);
    			PrintList();
    		}
    		else
    		{
    			Node *FindedNode = FindNode(Index);    //FIndedNode为插入位置的前一位
    			if (FindedNode)
    			{
    				Node *NewNode = new Node;
    				NewNode->Data = num; NewNode->Next = FindedNode->Next;
    				FindedNode->Next = NewNode;
    				PrintList();
    			}
    			else
    				cout << "error" << endl;
    		}
    	}
    	void PrintList()     //输出链表
    	{
    		int cnt = 1;
    		Node *Temp = Head->Next;
    		while (Temp)
    		{
    			if (cnt == 1)
    				cout << Temp->Data;
    			else
    				cout << " " << Temp->Data;
    			cnt++;
    			Temp = Temp->Next;
    		}
    		//cout<<" " << endl;
    		cout << endl;
    	}
    };

## 2.双向链表 ##

1）在单向链表的基础上拥有前驱指针（指向前一个节点）。

2）友好，因为有指向前一节点的指针，说明**插入删除只需查找当前需要插入或者删除的节点**！

3）还能**逆序输出**，**两端插入**！

4）因为**我懒**，所以功能实现没有前插和后插，其实可以把头节点删了换成一个头指针（就是指向有数据的第一个节点），这样就能实现前插后插，交给你们啦~

5）一个彩蛋，数据结构和STL相关，比如list就是以双链表为基础，所以下篇blog介绍List。

### 类实现（创建，析构，删除，插入，输出） ###

#include<iostream>
    using namespace std;
    struct Node
    {
    	int Data;
    	Node* Prior;
    	Node* Next;
    };
    class Double_direct_List
    {
    private:
    	
    	Node * Head;
    	Node * Tail;
    	int List_Size;
    public:
    	Double_direct_List();      //创建
    	void AddNode(int Elem);     //尾插节点
    	Node* Find_Elem(int Being_Find_Elem);   //查找含有指定数据的节点
    	Node* Find_Index_Node(int Index);      //查找Index位置的节点
    	int Delete_Node(Node* Finded_Node);     //删除节点
    	int Insert_Node(int insert_index,int insert_Elem);    //插入含有数据insert_elem的节点
    	int Get_ListSize();             //返回链表元素个数
    	void Head_To_Tail_OutPut();   //顺序输出
    	void Tail_To_Head_OutPut();   //逆序输出
    };
    Double_direct_List::Double_direct_List() :List_Size(0)
    {
    	Head = new Node;
    	Head->Next = NULL; Head->Prior = NULL;
    	Tail = Head;
    }
    void Double_direct_List::AddNode(int Elem)
    {
    	Node* NewNode = new Node;
    	NewNode->Data = Elem;
    	NewNode->Next = NULL;
    	NewNode->Prior = Tail;    //比单向链表多了这一步，就是前驱指针要指向前一节点
    	Tail->Next = NewNode;
    	Tail = NewNode;
    	List_Size++;
    }
    Node* Double_direct_List::Find_Elem(int Being_Find_Elem)
    {
    	Node* Index = Head->Next;
    	while (Index)
    	{
    		if (Index->Data == Being_Find_Elem)
    			return Index;
    		Index = Index->Next;
    	}
    	return NULL;
    }
    Node* Double_direct_List::Find_Index_Node(int Index)
    {
    	Node* TempIndex = Head->Next;
    	int cnt = 0;
    	while (TempIndex)
    	{
    		if (++cnt == Index)
    			return TempIndex;
    		TempIndex = TempIndex->Next;
    	}
    	return NULL;
    }
    int Double_direct_List::Delete_Node(Node* Finded_Node)
    {
    	if (Finded_Node == NULL)
    		return 0;
    	Node* Prior_Node = Finded_Node->Prior;
    	Node* Next_Node = Finded_Node->Next;
    	Prior_Node->Next = Next_Node;
    	if(Next_Node)
    		Next_Node->Prior = Prior_Node;
    	List_Size--;
    	delete Finded_Node;
    	return 1;
    }
    int Double_direct_List::Insert_Node(int insert_index, int insert_Elem)
    {
    	if (insert_index == List_Size+1)
    		AddNode(insert_Elem);
    	else
    	{
    		Node* Finded_Node = Find_Index_Node(insert_index);
    		if (Finded_Node == NULL)
    			return 0;
    		else
    		{
    			Node* Prior_Node = Finded_Node->Prior;
    			Node* NewNode = new Node;
    			NewNode->Data = insert_Elem;
    			Prior_Node->Next = NewNode;
    			Finded_Node->Prior = NewNode;
    			NewNode->Next = Finded_Node;
    			NewNode->Prior = Prior_Node;
    			List_Size++;
    		}
    	}
    	return 1;
    }
    int Double_direct_List::Get_ListSize()
    {
    	return List_Size;
    }
    void Double_direct_List::Head_To_Tail_OutPut()
    {
    	int i=0;
    	Node* TempHead = Head->Next;
    	while (TempHead)
    	{
    		if (++i == 1)
    			cout << TempHead->Data;
    		else
    			cout << " " << TempHead->Data;
    		TempHead = TempHead->Next;
    	}
    	cout << endl;
    }
    void Double_direct_List::Tail_To_Head_OutPut()
    {
    	Node* TempTail = Tail;
    	while (TempTail->Prior)
    	{
    		cout << TempTail->Data << " ";
    		TempTail = TempTail->Prior;
    	}
    	cout << endl;
    }

## 3.具体题目 ##

**(小傲娇放在最后没人看！)一道题：约瑟夫环（单链表实现），看完双链表可以用双链表实现下，附上题目及我代码的链接：[点击打开链接][Link 1]**

#### 1.单链表的删除 ####

1.问题描述

给出初始数据，实现单链表的定义、创建、查找和删除。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针。

单链表的创建：依次为输入的数据分配结点，并按序链接起来。

单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。

单链表的删除：给出位置i，删除第i个结点(1<=i<=L)。

要求定义删除函数：int DeleteList(Node \*H,int i) //删除第i个结点成功，返回1；第i个结点不存在，删除不成功，返回0。其中Node是链表结点结构体名，H是链表头指针。

每个样本分2行：

第一行：第一个数字n表示样本数目，其后跟n个样本

第二行：删除测试次数m 后跟m个删除位置

##### 输出 #####

第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。

第二行至第m+1行：若删除指定位置的数据成功，输出链表中元素个数和单链表中的全部数据；若删除不成功，输出error。

##### 样例输入 #####

5 2 4 3 5 7

3 0 2 4

##### 样例输出 #####

5 2 4 3 5 7

error

4 2 3 5 7

3 2 3 5

##### 应用上述类实现代码 #####

###### 单链表实现 ######

int main()
    {
    	int n, num;
    	int t, Index;
    	MyList OneList;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> num;
    		OneList.AddNode(num);
    	}
    	cout << OneList.ListSize();
    	OneList.PrintList();
    	cin >> t;
    	while (t--)
    	{
    		cin >> Index;
    		if (OneList.DeleteNode(OneList.FindNode(Index)) )
    		{
    			cout << OneList.ListSize();
    			OneList.PrintList();
    		}
    		else
    			cout << "error" << endl;
    	}
    	return 0;
    }

###### 双向链表实现 ######

int main()
    {
    	int size, deltime, delnum, num;
    	Double_direct_List MyList;
    	cin >> size;
    	for (int i = 1; i <= size; i++)
    	{
    		cin >> num;
    		MyList.AddNode(num);
    	}
    	cout << MyList.Get_ListSize();
    	MyList.Head_To_Tail_OutPut();
    	cin >> deltime;
    	while(deltime--)
    	{
    		cin >> delnum;
    		if (MyList.Delete_Node(MyList.Find_Index_Node(delnum) ) )
    		{
    			cout << MyList.Get_ListSize();
    			MyList.Head_To_Tail_OutPut();
    		}
    		else
    			cout << "error" << endl;
    	}
    	return 0;
    }

#### 2.单链表查找 ####

1.问题描述

给出初始数据，实现单链表的定义、创建、查找。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针。

单链表的创建：依次为输入的数据分配结点，并按序链接起来。

单链表结点个数L(也称单链表表长L)：从头至尾遍历单链表，对结点进行计数。

单链表的查找：给出位置i,若第i个结点存在(1<=i<=L)，返回结点地址；否则，返回NULL。

要求查找子函数定义为：Node \*Find(Node \*H,int i)

//若i的值在1...单链表长L之间，返回第i个结点的地址；否则返回空指针NULL。其中Node为链表结点结构体名，H为链表头指针。

##### 输入 #####

每个样本分2行：

第一行：第一个数字n表示样本数目，其后跟n个样本。

第二行：查找测试次数m 后跟m个待查找的位置。

##### 输出 #####

第一行：单链表创建后，输出链表中元素个数和单链表中的全部数据。

第二行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error。

##### 样例输入 #####

6 1 2 3 4 5 64 0 2 10 6

##### 样例输出 #####

6 1 2 3 4 5 6

error

##### 应用上述类实现代码 #####

###### 单向链表实现 ######

int main()
    {
    	MyList OneList;
    	int n, num;
    	int t, Index;
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> num;
    		OneList.AddNode(num);
    	}
    	cout << OneList.ListSize();
    	OneList.PrintList();
    	cin >> t;
    	while (t--)
    	{
    		cin >> Index;
    		if (OneList.FindNode(Index))
    			cout << OneList.FindNode(Index)->Next->Data<< endl;
    		else
    			cout << "error" << endl;
    	}
    	return 0;
    }

###### 双向链表实现 ######

int main()
    {
    	int size, TxTtime, testindex, num;
    	Double_direct_List MyList;
    	cin >> size;
    	for (int i = 1; i <= size; i++)
    	{
    		cin >> num;
    		MyList.AddNode(num);
    	}
    	cout << MyList.Get_ListSize()<<" ";
    	MyList.Head_To_Tail_OutPut();
    	cin >> TxTtime;
    	while (TxTtime--)
    	{
    		cin >> testindex;
    		Node* FindedNode = MyList.Find_Index_Node(testindex);
    		if (FindedNode)
    			cout << FindedNode->Data << endl;
    		else
    			cout << "error" << endl;
    	}
    	return 0;
    }

#### 3.单链表插入 ####

1.问题描述

单链表初始为空，给定插入位置和数据，插入结点实现单链表的创建。假设单链表中的结点计数从1开始。

2.算法

单链表结点的存储结构包含两部分：数据、下一结点指针

单链表的查找：给出位置i，若第i个结点存在(1<=i<=表中结点数L)，返回结点地址；否则，返回NULL。

单链表的插入：给出位置i和数据e，在单链表第i(1<=i<=L+1)个结点位置插入新结点，数据为e。

##### 输入 #####

测试次数n

每行一组测试数据,格式如下：

位置i 数据e

##### 输出 #####

对每组测试数据，调用插入函数在位置i插入数据e，若插入成功，输出当前链表中的数据；若插入不成功，输出error。

##### 样例输入 #####

80 10

1 10

2 20

3 30

1 40

6 60

5 50

9 100

##### 样例输出 #####

error

10 20

10 20 30

40 10 20 30

error

40 10 20 30 50

error

##### 应用上述类实现代码 #####

###### 单向链表实现 ######

int main()
    {
    	MyList OneList;
    	int t, Index, num;
    	cin >> t;
    	while (t--)
    	{
    		cin >> Index >> num;
    		OneList.InsertNode(Index, num);
    	}
    	return 0;
    }

###### 双向链表实现 ######

int main()
    {
    	Double_direct_List MyList;
    	int insert_time, insert_data, insert_index;
    	cin >> insert_time;
    	while (insert_time--)
    	{
    		cin >> insert_index >> insert_data;
    		if (MyList.Insert_Node(insert_index, insert_data))
    		{
    			MyList.Head_To_Tail_OutPut();
    			MyList.Tail_To_Head_OutPut();
    		}
    		else
    			cout << "error" << endl;
    	}
    	
    	return 0;
    }

还有一道题：约瑟夫环，看完双链表可以用双链表实现下，附上题目及我代码的链接：[点击打开链接][Link 1]

感觉没有注释是不是和没缩减对齐一样是渣男~

[Link 1]: https://blog.csdn.net/SZU_Crayon/article/details/79819258