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;
}
           

運作結果：