基本知識點

注：數據結構系列將持續(xù)更新，歡迎交流討論…

1. 有頭鏈表和單項鏈表差不多是一種線性結構，只是比單項鏈表多一個不存儲數據的、用來操作鏈表的頭節(jié)點；
2. 優(yōu)點：作數據的刪除、插入簡單；缺點：數據查找慢
3. 組成：數據域、頭節(jié)點、尾結點、后繼節(jié)點的一個指針域；
4. 有頭鏈表，后繼指針指向下一個結點；
5. 學數據結構的建議：學習每種結構的時候，首先得清除它的結構，所以自己首先要清楚大概的結構，自己畫一畫；文中我會展示出部分圖片以供參考。

基本結構

注：這三張圖分別是有頭鏈表的初始狀態(tài)（只有頭節(jié)點和尾結點）、基本模型、插入時后進行的操作

一般實現步驟

1. 構建數據模型；（以什么方式實現鏈表，結構體、類等）
2. 初始化頭節(jié)點，尾結點；
3. 初始化結點參數/創(chuàng)建結點；
4. 用頭結點或尾結點來操作鏈接每個結點，讓這些結點成為一個邏輯上相連接的鏈表；
5. 注意點：指針的先后指向要捋清楚，誰先指，誰后指；
6. 建議：學編程就是學的一種思維，有的問題可以不必深究；

List.h文件代碼

#pragma once
//數據域數據，包含一個學號，三門成績
typedef struct DATA
{
	int number;
	int score[3];
	DATA* next;
}Data, * p_Data;

class System
{
public:
	System();
	~System();
	p_Data initData();
	p_Data createData(int number, int score_1, int score_2, int score_3);
	void insertHData(p_Data data);
	void insertTData(p_Data data);
	bool deleteData(int delNum);
	bool changeData(int oldNum,int newNum);
	bool searchData(int seaNum);

	void printData();

	int Size();

protected:
	p_Data m_head;
	p_Data m_tail;
	int m_curSize;
};

List.cpp文件

#include "List.h"
#include <iostream>

using namespace std;

System::System()
{
//初始化兩個結點
	this->m_head = this->initData();
	this->m_tail = this->initData();
	m_head->next = m_tail;

	this->m_curSize = 0;
}

System::~System()
{
	//cout << "析構了..." << endl;
	if (m_head != nullptr)
	{
		delete m_head;
		m_head = nullptr;
	}
	if (m_tail != nullptr)
	{
		delete m_tail;
		m_tail = nullptr;
	}
	this->m_curSize = 0;
		
}

p_Data System::initData()
{
	p_Data data = new Data;
	data->next = nullptr;
	data->number = 0;
	for (int i = 0; i < 3; i++)
	{
		data->score[i] = 0;
	}

	return data;
}

p_Data System::createData(int number, int score_1, int score_2, int score_3)
{
	p_Data newData = initData();
	newData->number = number;
	newData->score[0] = score_1;
	newData->score[1] = score_2;
	newData->score[2] = score_3;

	return newData;
}

void System::insertHData(p_Data data)
{
//看上面的過程圖，插入結點的next先指，頭節(jié)點的next在指向插入結點
	data->next = this->m_head->next;
	m_head->next = data;

	this->m_curSize++;
}

void System::insertTData(p_Data data)
{
//保證pLight指向尾結點的左側結點
	p_Data pMove = m_head;
	p_Data pLight = m_head;
	while (pMove != m_tail)
	{
		pLight = pMove;
		pMove = pMove->next;
	}
	data->next = pLight->next;
	pLight->next = data;

	this->m_curSize++;
}

bool System::deleteData(int delNum)
{
	p_Data pMove = m_head->next;
	p_Data pLight = m_head;
	/*for (int i = 0; i < this->m_curSize; i++)
	{
		if (pMove->number == delNum)
		{
			pLight->next = pMove->next;

			return true;
		}
		pLight = pMove;
		pMove = pMove->next;
	}*/
	while (pMove != m_tail)
	{
		if (pMove->number == delNum)
		{
			pLight->next = pMove->next;
			delete pMove;
			pMove = nullptr;
			m_curSize--;
			return true;
		}
		pLight = pMove;
		pMove = pMove->next;
	}

	return false;
}

bool System::changeData(int oldNum,int newNum)
{
	p_Data pMove = m_head->next;
	while (pMove != m_tail)
	{
		if (pMove->number == oldNum)
		{
			pMove->number = newNum;
			return true;
		}
		pMove = pMove->next;
	}

	return false;
}

bool System::searchData(int seaNum)
{
	p_Data pMove = m_head->next;
	while (pMove != m_tail)
	{
		if (pMove->number == seaNum)
		{
			return true;
		}
		pMove = pMove->next;
	}

	return false;
}

void System::printData()
{
	p_Data pMove = this->m_head;
	while (pMove->next != m_tail)
	{
		pMove = pMove->next;
		cout << pMove->number << "\t";
		for (int i = 0; i < 3; i++)
		{
			cout << pMove->score[i] << "\t";
		}
		cout << endl;
	}
}

int System::Size()
{
	return this->m_curSize;
}

Main.cpp測試代碼

#include <iostream>
#include "List.h"

using namespace std;

int main()
{
	System sys;
	p_Data data_1 = sys.createData(192, 89, 90, 89);
	p_Data data_2 = sys.createData(193, 79, 79, 79);
	p_Data data_3 = sys.createData(194, 90, 99, 85);
	p_Data data_4 = sys.createData(195, 85, 85, 85);
	sys.insertHData(data_1);
	sys.insertHData(data_2);
	sys.insertTData(data_3);
	sys.insertTData(data_4);
	cout << "鏈表含有 " << sys.Size() << " 個數據..." << endl;
	sys.printData();
	cout << endl;
	sys.deleteData(195);
	sys.printData();
	cout << endl;
	sys.changeData(192, 198);
	sys.printData();
	if (sys.searchData(192))
	{
		cout << "含有該數據..." << endl;
	}
	else
	{
		cout << "沒有該數據..." << endl;
	}

	return 0;
}

尾插法指針的移動

結語

這些內容是我平時的所學知識的理解，數據結構的內容將持續(xù)更新，如文中有誤還請不吝賜教；歡迎評論區(qū)留言或私信討論。