C++零基礎精通資料結構之帶頭雙向迴圈連結串列

// 建立連結串列（連結串列初始化）
ListNode* ListCreate();
//建立節點
ListNode* BuyListNode(ListNode* pHead);
// 雙向連結串列銷燬
void ListDestory(ListNode* pHead);
// 雙向連結串列列印
void ListPrint(ListNode* pHead);
// 雙向連結串列尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 雙向連結串列尾刪
void ListPopBack(ListNode* pHead);
// 雙向連結串列頭插
void ListPushFront(ListNode* pHead, LTDataType x);
// 雙向連結串列頭刪
void ListPopFront(ListNode* pHead);
// 雙向連結串列查詢
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 雙向連結串列在pos的前面進行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向連結串列刪除pos位置的節點
void ListErase(ListNode* pos);

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 建立連結串列（初始化）
ListNode* ListCreate()
{
	//開闢哨兵衛頭結點
	ListNode* plist = (ListNode*)malloc(sizeof(ListNode));
	if (plist == NULL)//失敗列印錯誤資訊並結束程序
	{
		perror("ListCreat fail:");
		exit(-1);
	}
	plist->next = plist;
	plist->prev = plist;
	return plist;
}

//建立節點
ListNode* BuyListNode(LTDataType x)
{
	//建立節點
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)//失敗列印錯誤資訊並結束程序
	{
		perror("creatnode fail:");
		exit(-1);
	}
	newnode->data = x;
	//初始化結點
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

// 雙向連結串列銷燬
void ListDestory(ListNode* pHead)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	ListNode* cur = pHead;
	pHead->prev->next = NULL;
	while (cur!=NULL)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	return;
}

// 雙向連結串列列印
void ListPrint(ListNode* pHead)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//建立定址指標
	ListNode* cur = pHead->next;
	//迴圈遍歷連結串列
	while (cur != pHead)
	{
		//列印資料
		printf("%d->", cur->data);
		//找到下一個節點
		cur = cur->next;
	}printf("NULLn");
	return;
}

// 雙向連結串列尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//建立節點
	ListNode* newnode = BuyListNode(x);
	//找到尾節點
	ListNode* tail=pHead->prev;
	tail->next = newnode;
	newnode->prev = tail;
 
	pHead->prev = newnode;
	newnode->next = pHead;
}

// 雙向連結串列尾刪
void ListPopBack(ListNode* pHead)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//只剩哨兵衛頭結點的情況
	if (pHead->prev == pHead)
		return;
	//記錄尾節點及其前一節點
	ListNode* tail = pHead->prev;
	ListNode* tailprev = tail->prev;
	//釋放尾節點
	free(tail);
	//構建尾節點前一節點與哨兵衛頭結點的關係
	tailprev->next = pHead;
	pHead->prev = tailprev;
	return;
}

// 雙向連結串列頭插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//建立節點
	ListNode* newnode = BuyListNode(x);
	//記錄哨兵衛頭結點的下一節點
	ListNode* next = pHead->next;
	//構建各節點之間的關係
	pHead->next = newnode;
	newnode->prev = pHead;
 
	newnode->next = next;
	next->prev = newnode;
	return;
}

// 雙向連結串列頭刪
void ListPopFront(ListNode* pHead)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//只剩哨兵衛頭結點的情況
	if (pHead->next == pHead)
		return;
	//記錄哨兵衛頭結點下一節點及其的下一節點
	ListNode* next = pHead->next;
	ListNode* nextNext = next->next;
	//釋放節點
	free(next);
	pHead->next = nextNext;
	nextNext->prev = pHead;
	return;
}

// 雙向連結串列查詢
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	//斷言傳入指標不為NULL
	assert(pHead);
	//建立定址指標
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		//比較資料
		if (cur->data == x)
			return cur;
		//找到下一個節點
		cur = cur->next;
	}
	//沒找到則返回NULL
	return NULL;
}

void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
	return;
}