基本知識點(diǎn)

注：數(shù)據(jù)結(jié)構(gòu)系列將持續(xù)更新，歡迎交流討論…

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

基本結(jié)構(gòu)

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

一般實(shí)現(xiàn)步驟

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

List.h文件代碼

#pragma once
//數(shù)據(jù)域數(shù)據(jù)，包含一個(gè)學(xué)號，三門成績
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()
{
//初始化兩個(gè)結(jié)點(diǎn)
	this->m_head = this->initData();
	this->m_tail = this->initData();
	m_head->next = m_tail;

	this->m_curSize = 0;
}

System::~System()
{
	//cout << "析構(gòu)了..." << 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)
{
//看上面的過程圖，插入結(jié)點(diǎn)的next先指，頭節(jié)點(diǎn)的next在指向插入結(jié)點(diǎn)
	data->next = this->m_head->next;
	m_head->next = data;

	this->m_curSize++;
}

void System::insertTData(p_Data data)
{
//保證pLight指向尾結(jié)點(diǎn)的左側(cè)結(jié)點(diǎn)
	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() << " 個(gè)數(shù)據(jù)..." << endl;
	sys.printData();
	cout << endl;
	sys.deleteData(195);
	sys.printData();
	cout << endl;
	sys.changeData(192, 198);
	sys.printData();
	if (sys.searchData(192))
	{
		cout << "含有該數(shù)據(jù)..." << endl;
	}
	else
	{
		cout << "沒有該數(shù)據(jù)..." << endl;
	}

	return 0;
}

尾插法指針的移動(dòng)

結(jié)語

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