單（雙向）連結清單的基本操作 C++

#include"iostream"

using namespace std;

//====================單連結清單===================================

//如果不提供“頭指針”，則整個連結清單都無法通路,連結清單的一個重要特點是插入、删除操作靈活友善.
//插入操作處理順序：中間節點的邏輯，後節點邏輯，前節點邏輯。按照這個順序處理可以完成任何連結清單的插入操作。
//删除操作的處理順序：前節點邏輯，後節點邏輯，中間節點邏輯。


/*單連結清單實際上是由節點（Node）組成的，一個連結清單擁有不定數量的節點。
而向外暴露的隻有一個頭節點（Head），我們對連結清單的所有操作，都是通過其頭節點(head)來進行的。
節點：資料+位址*/

struct ListNode
{
	int val;
	struct ListNode *next;
	ListNode(int x) :val(x), next(NULL){}
};

//頭指針與頭結點不同，頭結點即第一個結點，頭指針是指向第一個結點的指針。連結清單中可以沒有頭結點，但不能沒有頭指針。
/*1.初始化單連結清單(無頭結點)，頭指針為空*/
// void initList(Node **pNode)
// {
// 	*pNode = NULL;
// 	cout << "初始化成功！" << endl;
// }


/*2.建立單連結清單（頭插法）：生成的連結清單中結點的次序和輸入的順序相反
a.先讓新節點的next指向頭節點之後
b.然後讓表頭的next指向新節點*/
void CreatListHead(ListNode *pHead,int data)
{
	ListNode *p=new ListNode(-1);
	p->val = data;
	p->next = pHead->next;
	pHead->next = p;
}

/*2.建立單連結清單（尾插法）：在表的最後插入結點
a.将表尾終端結點的指針指向新結點
b.将目前的新結點定義為表尾終端結點 */
void CreatListTail(ListNode **Node, int data)
{
	if ((*Node)->next == NULL)
	{
		ListNode *p = new ListNode(-1);
		p->val = data;
		(*Node)->next = p;
		*Node = p;
		(*Node)->next = NULL;
	}
}

/*單連結清單的周遊，并傳回單連結清單長度*/
int printList(const ListNode *pHead)
{
	int len = 0;
	ListNode *p = pHead->next;
	if (p== NULL)
		cout << "連結清單為空！" << endl;
	else
	{
		while (p != NULL)
		{
			len++;
			cout << p->val << " ";
			p = p->next;
		}
		cout << endl;
	}
	return len;
}

/*删除單連結清單：
1.聲明一節點p和q；
2.将第一個結點指派給p；
3.循環：
a.将下一結點指派給q；b.釋放p；c.将q指派給p；
*/
bool ClearList(ListNode *pHead)
{
	ListNode *p, *q;
	p = pHead->next;
	while (p)
	{
		q = p->next;
		delete p;
		p = q;
	}
	pHead->next = NULL;
	return true;
}

/*查找單連結清單上指定節點的資料*/
bool GetElem(ListNode *pHead, int i, int &data)
{
	ListNode *p = pHead->next;
	int j = 0;
	while (p && j < i-1)
	{
		p = p->next;
		j++;
	}
	if (!p)
		return false;
	else
	{
		data = p->val;
		return true;
	}
}

/*單連結清單指定位置插入資料:
1.找到ai-1存儲位置p
2.生成一個資料域為x的新結點*s
3.令結點*p的指針域指向新結點
4.新結點的指針域指向結點ai。*/
bool ListInsert(ListNode *pHead, int i, int data)
{
	ListNode *p = pHead;
	int j = 0;
	while (p && j < i - 1)
	{
		p = p->next;
		j++;
	}
	if (!p || j>i - 1)
		return false;
	else
	{
		ListNode *tmpPtr = new ListNode(-1);
		tmpPtr->val = data;
		tmpPtr->next = p->next;
		p->next = tmpPtr;
		return true;
	}
}

/*删除單連結清單指定的某個結點:
1.找到ai-1的存儲位置p（因為在單連結清單中結點ai的存儲位址是在其直接前趨結點ai-1的指針域next中）
2.令p-＞next指向ai的直接後繼結點（即把ai從鍊上摘下）
3.釋放結點ai的空間，将其歸還給“存儲池”。*/
bool ListDelete(ListNode *pHead, int i)
{
	int j=1;
	ListNode *p, *q;
	p= pHead;
	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (!p || j>i)
		return false;
	else
	{
		q = p->next;
		p->next = q->next;
		delete q;
		return true;
	}
}
/*單連結清單逆序：*/
bool ListReverse(ListNode *PHead)
{
	ListNode *current, *pnext, *prev;
	current = PHead->next;
	pnext = current->next;
	current->next = NULL;
	while (pnext)
	{
		prev = pnext->next;
		pnext->next = current;
		current = pnext;
		pnext = prev;
	}
	PHead->next = current;

	return true;
}

/*判斷單連結清單中是否有環:
1.使用p、q兩個指針，p總是向前走，但q每次都從頭開始走，對于每個節點，看p走的步數是否和q一樣*/
bool HasLoop(ListNode *pHead)
{
	ListNode *cur1 = pHead;
	int pos1 = 0;
	while (cur1)
	{
		ListNode *cur2 = pHead;
		int pos2 = 0;
		pos1++;
		while (cur2)
		{
			pos2++;
			if (cur1 == cur2)
			{
				if (pos1 == pos2)
					break;
				else
					return true;
			}
			cur2 = cur2->next;
		}
		cur1 = cur1->next;
	}
	return false;
}

/*擷取單連結清單倒數第N個結點值:
建立兩個指針，第一個先走n步，然後第2個指針也開始走，兩個指針步伐（前進速度）一緻。當第一個結點走到連結清單末尾時，第二個節點的位置就是我們需要的倒數第n個節點的值。*/
bool GetNthNodeFromBack(ListNode *pHead, int n,int &data)
{
	int i = 1;
	ListNode *firstNode = pHead, *secNode = pHead;
	while (firstNode->next != NULL && i < n)
	{
		firstNode = firstNode->next;
		i++;
	}
	if (firstNode->next == NULL && i < n - 1)
	{
		cout << "n超對外連結表長度" << endl;
		return false;
	}
	while (firstNode->next != NULL)
	{
		secNode = secNode->next;
		firstNode = firstNode->next;
	}
	data = secNode->val;
	return true;
}


//=====================================================



//====================雙向循環連結清單=======================
/*雙向循環連結清單的結構：資料、next指針、prior指針
1.連結清單由頭指針head惟一确定的。
2.帶頭結點的雙連結清單的某些運算變得友善。
3.将頭結點和尾結點連結起來，為雙（向）循環連結清單。*/
struct NodeType2
{
	int val;
	NodeType2 *next, *prior;
	NodeType2(int x) :val(x), next(NULL), prior(NULL) {};
};

//建立雙向連結清單
void CreateListtype2(NodeType2 **Node, int data)
{
	NodeType2 *tmpPtr = (*Node)->next;
	NodeType2 *p = new NodeType2(data);
	(*Node)->next = p;
	p->prior = *Node;
	p->next = tmpPtr;

	*Node = p;
}

/*雙連結清單的前插操作*/
bool ListType2Insert1(NodeType2 *pHead, int i, int data)
{
	int j = 0;
	NodeType2 *p = pHead;
	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (!p && j < i - 1)
		return false;
	else
	{
		NodeType2 *tmpTpr = new NodeType2(data);
		tmpTpr->next = p;
		tmpTpr->prior = p->prior;
		p->prior->next = tmpTpr;
		p->prior = tmpTpr;
		return true;
	}


}

/*雙連結清單的後插操作*/
bool ListType2Insert2(NodeType2 *pHead, int i, int data)
{
	int j = 0;
	NodeType2 *p = pHead;
	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (!p && j < i - 1)
	{
		cout << "超對外連結表長度！" << endl;
		return false;
	}
	else
	{
		NodeType2 *tmpPtr = new NodeType2(data);
		tmpPtr->next = p->next;
		p->next->prior = tmpPtr;
		p->next = tmpPtr;
		tmpPtr->prior = p;
		return true;
	}
}

/*雙連結清單上删除結點*p*/
bool ListType2Delete(NodeType2 *pHead, int i)
{
	int j = 0;
	NodeType2 *p = pHead;
	while (p && j<i)
	{
		p = p->next;
		j++;
	}
	if (p && j < i - 1)
	{
		cout << "超對外連結表長度！" << endl;
		return false;
	}
	else
	{
		p->prior->next = p->next;
		p->next->prior = p->prior;
		delete p;
		return true;
	}
}

//=============================================


int main()
{
	//=========單連結清單==============
	//ListNode *L = new ListNode(-1);
	//int n;
	//ListNode* tmpPtr = L;
	//while (cin >> n)//ctrl+z結束
	//{
	//	//CreatListHead(L, n);
	//	CreatListTail(&tmpPtr, n);//為什麼傳指針不行 非得指針的指針
	//}
	//int len = printList(L);
	//int data = 0;
	// bool isGetElem = GetElem(L, 2, data);
	// bool isInsertElem = ListInsert(L, 2, 4);
	// bool isClear = ClearList(L);
	//bool isDelete = ListDelete(L, 1);
	//bool isReverse = ListReverse(L);

	//tmpPtr->next = L;
	//bool isloop=HasLoop(L);

	//bool IsGet = GetNthNodeFromBack(L, 2, data);
	//len = printList(L);


	//============雙連結清單==================
	NodeType2 *L = new NodeType2(-1);
	int n = 0;
	NodeType2 *tmpPtr = L;
	while (cin >> n)
	{
		CreateListtype2(&tmpPtr, n);
	}

	bool isInsert = ListType2Insert2(L, 2, 4);
	bool isDelete = ListType2Delete(L, 3);

	system("pause");
	return 0;
}