【C++知識點】連結清單（整理）

1. 連結清單的建立
2. 連結清單的周遊
3. 連結清單節點的添加
4. 連結清單節點的删除

連結清單的建立

SNode* pNewNode = new SNode();   //建立新節點
	cout << "請輸入ID和名字" << endl;
	cin >> pNewNode->nID >> pNewNode->strName;
	pTailNode->pNext = pNewNode;   //把建立的節點接到尾部（接）
	pTailNode = pNewNode;    //将節點換為新的尾部（換）
           

//從第一節開始跟随(老師版)
	Snake* pPreNode = pHead;
	for (Snake* pCurNode = pHead->pNext; pCurNode; pCurNode = pCurNode->pNext)
	{
		pCurNode->backup();
		pCurNode->nSnakeRow = pPreNode->nSnakeRowBk;
		pCurNode->nSnakeCol = pPreNode->nSnakeColBk;
		pPreNode = pPreNode->pNext;  //pPreNode = pCurNode;
	}
           

Snake* pPreNode = pHead;  //建立前一個指針從頭開始
	Snake* pCurNode = pHead->pNext;  //建立目前指針指向 前一個指針的 下一個節點
	while (pCurNode)  //如果目前指針存在：最後一個指針
	{
		pCurNode->backup();  //先備份目前坐标：用于給後面的使用
		//跟随
		pCurNode->nSnakeRow = pPreNode->nSnakeRowBk;  //把前一節的備份坐标給目前節點
		pCurNode->nSnakeCol = pPreNode->nSnakeColBk;

		//指針往後移
		pPreNode = pPreNode->pNext;
		pCurNode = pCurNode->pNext;
	}
           

連結清單的周遊

//建立一個指針用于周遊輸出
	SNode* pCurNode = g_pHead;
	while (pCurNode){
		//輸出目前節點的資料
		cout << "ID = " << pCurNode->nID << "," << "Name = " << pCurNode->strName << endl;
		//将目前節點設定為下一個節點
		pCurNode = pCurNode->pNext;
	}
           

//老師版
	bool DrawSnake = false;
	for (Snake* pDrawNode = pHead; pDrawNode; pDrawNode = pDrawNode->pNext)
	{
		if (pDrawNode->nSnakeRow == i && pDrawNode->nSnakeCol == j)
		{
			DrawSnake = true;
			break;
		}
	}
           

//自己版
	bool DrawSnake = false;
	Snake* pDrawNode = pHead;
	while (pDrawNode)
	{
		if (pDrawNode->nSnakeRow == i && pDrawNode->nSnakeCol == j)
		{
			DrawSnake = true;
			break;
		}
		pDrawNode = pDrawNode->pNext;
	}
           

連結清單節點的插入删除

// 2021.3.22(連結清單插入删除).cpp : 定義控制台應用程式的入口點。
//

#include "stdafx.h"
#include <windows.h>
#include <iostream>
#include <string>

using namespace std;

struct SNode
{
	SNode(){
		nID = 0;
		pNext = nullptr;
	}
	int nID;
	string strName;
	SNode* pNext;
};

//定義頭結點
SNode* g_pHead = nullptr; //new SNode();

void createList(int nCount);  //建立連結清單
void showList();  //列印連結清單
void addNode(int nIndex);   //添加節點
void deleteNode(int nIndex);  //删除節點

int _tmain(int argc, _TCHAR* argv[])
{
	//在main中調用函數實作相應功能
	createList(3);  //長度為5
	showList();
	addNode(0);  //從0插入節點
	showList();
	deleteNode(0);
	showList();
	system("pause");
	return 0;
}


//其他函數寫在main函數之外
void createList(int nCount){
	if (nCount <= 0) 
	{
		return;   //傳回調用處，并結束目前函數
	}

	g_pHead = new SNode();  //建立頭結點并輸入資料
	cout << "請輸入ID和名字" << endl;
	cin >> g_pHead->nID >> g_pHead->strName;
	
	SNode* pTailNode = g_pHead;    //建立尾指針（第一個節點既是頭也是尾）

	int i = 0;
	while (i < (nCount - 1))
	{
		SNode* pNewNode = new SNode();   //建立新節點
		cout << "請輸入ID和名字" << endl;
		cin >> pNewNode->nID >> pNewNode->strName;
		pTailNode->pNext = pNewNode;   //接到尾部
		pTailNode = pNewNode;
		i++;
	}
}

void showList()
{
	cout << "-----------------------列印連結清單------------------------" << endl;

	//建立一個指針用于周遊輸出
	SNode* pCurNode = g_pHead;
	while (pCurNode){
		//輸出目前節點的資料
		cout << "ID = " << pCurNode->nID << "," << "Name = " << pCurNode->strName << endl;
		//将目前節點設定為下一個節點
		pCurNode = pCurNode->pNext;
	}
}

//通過索引搜尋節點★★★
SNode* getNodeByIndex(int nIndex)
{
	int i = 0;
	SNode* pCurNode = g_pHead;
	while (pCurNode)
	{
		pCurNode = pCurNode->pNext;
		i++;
		if (i == nIndex)
		{
			return pCurNode;
		}
	}
	return nullptr;
}

void addNode(int nIndex)
{
	//建立一個新節點并輸入資料
	SNode* pNewNode = new SNode();
	cout << "請輸入ID和名字" << endl;
	cin >> pNewNode->nID >> pNewNode->strName;

	if (nIndex <= 0)  //在連結清單頭插入資料
	{
		pNewNode->pNext = g_pHead;    //把頭結點的位址賦給新節點的pNext
		g_pHead = pNewNode;       //新節點變成頭結點
		return;     //結束函數
	}

	SNode* pCurNode = getNodeByIndex(nIndex - 1);   //先通過index搜尋節點的插入位置
	pNewNode->pNext = pCurNode->pNext;   //把搜尋到的節點的pNext設為待插入節點的pNext
	pCurNode->pNext = pNewNode;    //再讓搜尋到的節點的pNext等于新節點
}

void deleteNode(int nIndex)
{
	//删除第一個
	SNode* pNewNode = new SNode; //建立臨時變量存放頭結點
	if (nIndex <= 0)
	{
		pNewNode = g_pHead;  //把頭結點存起來，用于後面釋放
		g_pHead = g_pHead->pNext; //把第二個節點設為新的頭結點

		if (pNewNode)
		{
			delete pNewNode;
			pNewNode = nullptr;
		}
		return;
	}


	//删除第nIndex個
	SNode* pPreNode = getNodeByIndex(nIndex -1);
	SNode* pCurNode = pPreNode->pNext;
	pPreNode->pNext = pCurNode->pNext;
	if (pCurNode)
	{
		//删除操作
		delete pCurNode;
		pCurNode = nullptr;
	}

	//删除最後一個
	if (!pCurNode)
	{
		return;
	}
}