雙向循環連結清單的增删查減

文章目錄

• 1.連結清單結構體
• 2.連結清單頭的初始化
• 3.節點的建立
• 4.插入
• 5.查找
• 6.删除
• 7.尾插
• 8.頭插
• 9.尾删
• 10.頭删
• 11.列印
• 12.清空和銷毀

1.連結清單結構體

typedef int LTDataType;

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


ListNode* ListInit(ListNode *pphead);//初始化
ListNode* BuyListNode(LTDataType data);//建立節點
void ListInsert(ListNode *pos, LTDataType data);//在pos前面插入
ListNode* ListFind(ListNode *pphead, LTDataType data);//尋找節點
void ListErase(ListNode *pos);//删除
void ListPushBack(ListNode *pphead, LTDataType data);//尾插
void ListPushFront(ListNode *pphead, LTDataType data);//頭插
void ListPopBack(ListNode *pphead);//尾删
void ListPopFront(ListNode *pphead);//頭删
void ListPrint(ListNode *pphead);//列印
void ListClear(ListNode *pphead);//清空
void ListDestory(ListNode **pphead);//銷毀
           

2.連結清單頭的初始化

頭的初始化有兩種方式，要麼傳二級指針，要麼開辟好空間的節點傳回位址；

ListNode* ListInit(ListNode *pphead)//初始化
{
	/*assert(pphead);
	
	*pphead = (ListNode *)malloc(sizeof(ListNode));
	assert(*pphead);
	
	(*pphead)->prev = (*pphead)->next = *pphead;
	(*pphead)->data = 0;*/


	pphead = (ListNode *)malloc(sizeof(ListNode));
	assert(pphead);

	pphead->prev =pphead->next = pphead;
	pphead->data = 0;
	return pphead;
}
           

3.節點的建立

ListNode* BuyListNode(LTDataType data)//建立節點
{
	ListNode *node = (ListNode *)malloc(sizeof(ListNode));
	assert(node);

	node->next = node->prev = NULL;
	node->data = data;
	return node;
}
           

4.插入

void ListInsert(ListNode *pos,LTDataType data)//早Pos前面插入
 {
	 assert(pos);
	 ListNode *node = BuyListNode(data);
	 ListNode *prev = pos->prev;//pos前面的節點
	//和pos前面節點連結
	 prev->next = node;
	 node->prev = prev;
	 //和pos連結
	 node->next = pos;
	 pos->prev = node;
 }
           

5.查找

ListNode* ListFind(ListNode *pphead, LTDataType data)//尋找節點
 {
	 assert(pphead);

	 ListNode *cur = pphead->next;
	 
	 while (cur!=pphead)
	 {
		 if (cur->data == data)
			 return cur;
		 cur = cur->next;
	 }
	 return NULL;
 }
           

6.删除

void ListErase(ListNode *pos)//删除
 {
	 assert(pos);
	 //pos前後節點
	 ListNode *prev = pos->prev;
	 ListNode *next = pos->next;
	 //前後節點連結
	 prev->next = next;
	 next->prev = prev;

	 free(pos);
	 pos = NULL;//沒有多大意義，因為出了作用域就通路不到了
 }
           

7.尾插

尾插除了直接實作，還可以調用前面的插入函數；

雙向循環連結清單頭的前面就是尾；

void ListPushBack(ListNode *pphead,LTDataType data)//尾插
 {
	 assert(pphead);
	 //ListInsert(pphead, data);

	 ListNode *node = BuyListNode(data);
	 ListNode *tail = pphead->prev;//最後一個節點
	 //最後兩個節點連結
	 tail->next = node;
	 node->prev = tail;
	 //和頭連結
	 pphead->prev = node;
	 node->next = pphead; 
 }
           

8.頭插

同理，頭插也可以調用插入函數完成；

void ListPushFront(ListNode *pphead, LTDataType data)//頭插
 {
	 assert(pphead);
	 //ListInsert(pphead->next, data);

	 ListNode *node = BuyListNode(data);
	 ListNode *next = pphead->next;//未插入前的第一個節點
	 //插入的接點和後面的進行連結
	 node->next = next;
	 next->prev = node;
	 //頭連結
	 pphead->next = node;
	 node->prev = pphead;
 }
           

9.尾删

尾插也可以通過調用删除函數進行；

void ListPopBack(ListNode *pphead)//尾删
 {
	 assert(pphead);
	 assert(pphead->next != pphead);//頭不能删
	 //ListErase(pphead->prev);

	 ListNode *tail = pphead->prev;//尾
	 ListNode *tailPrev = tail->prev;

	 pphead->prev = tailPrev;
	 tailPrev->next = pphead;

	 free(tail);
 }
           

10.頭删

頭删同樣可以調用删除函數進行；

void ListPopFront(ListNode *pphead)//頭删
 {
	 assert(pphead);
	 assert(pphead->next != pphead);
	 //ListErase(pphead->next);

	 ListNode *head= pphead->next;
	 ListNode *next = head->next;

	 pphead->next = next;
	 next->prev = pphead;

	 free(head);

 }
           

11.列印

void ListPrint(ListNode *pphead)//列印
 {
	 assert(pphead);
	 ListNode *cur = pphead->next;
	 while (cur!=pphead)
	 {
		 printf("%d ", cur->data);
		 cur = cur->next;
	 }
	 printf("\n");
 }
           

12.清空和銷毀

清空保留頭結點，銷毀頭結點也要釋放，同時要置空；

void ListClear(ListNode *pphead)//清空
 {
	 assert(pphead);
	 ListNode *cur = pphead->next;
	 while (cur!=pphead)
	 {
		 ListNode *next = cur->next;
		 free(cur);
		 cur = next;
	 }
	 pphead->prev = pphead->next = pphead;;
 }

 void ListDestory(ListNode **pphead)//銷毀
 {
	 assert(pphead);
	 ListClear(*pphead);
	 free(*pphead);
	 *pphead = NULL;
 }