数据结构之带头双向循环链表（源代码）

布满荆棘的人生 2023-07-02 13:29 79阅读 0赞

## List.h ##

//带头双向循环链表
    
    #ifndef __LIST_H__
    #define __LIST_H__
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<malloc.h>
    
    typedef int LTDataType;
    typedef struct ListNode
    { 
    	LTDataType _data;
    	struct ListNode* _next;   //后继
    	struct ListNode* _prev;   //前驱
    }ListNode;
    
    typedef struct List
    { 
    	ListNode* _head;
    }List;
    
    void ListNodeInit(List* plist);
    void ListNodeDestory(List* plist);
    void ListNodePrint(List* plist);
    
    void ListNodePushBack(List* plist, LTDataType x);
    void ListNodePopBack(List* plist);
    void ListNodePushFront(List* plist, LTDataType x);
    void ListNodePopFront(List* plist);
    
    ListNode* ListFind(List* plist, LTDataType x);
    //在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x);
    //删除pos位置的节点
    void ListErase(ListNode* pos);
    void ListRemove(List* plist, LTDataType x);
    
    void ReverseList(List* plist);
    int ListSize(List* plist);
    int ListEmpty(List* plist);
    
    #endif //__LIST_H__

## List.c ##

#include"List.h"
    
    //构造新节点
    ListNode* BuyListNode(LTDataType x)
    { 
    	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    	assert(newnode);
    	newnode->_data = x;
    	newnode->_next = NULL;
    	newnode->_prev = NULL;
    	return newnode;
    }
    
    //初始化链表
    void ListNodeInit(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* head = BuyListNode(0);
    	head->_next = head;
    	head->_prev = head;
    	plist->_head = head;
    }
    
    //尾插
    void ListNodePushBack(List* plist, LTDataType x)
    { 
    	assert(plist != NULL);
    	ListNode* newnode = BuyListNode(x);
    	ListNode* head = plist->_head;
    	ListNode* tail = head->_prev;
    	newnode->_prev = tail;
    	tail->_next = newnode;
    	newnode->_next = head;
    	head->_prev = newnode;
    }
    
    //尾删
    void ListNodePopBack(List* plist)
    { 
    	assert(plist != NULL && plist->_head->_next != plist->_head);
    	ListNode* head = plist->_head;
    	ListNode* tail = head->_prev;
    	ListNode* tailprev = tail->_prev;
    	free(tail);
    	tail = NULL;
    	tailprev->_next = head;
    	head->_prev = tailprev;
    }
    
    //头插
    void ListNodePushFront(List* plist, LTDataType x)
    { 
    	assert(plist != NULL);
    	ListNode* newnode = BuyListNode(x);
    	ListNode* head = plist->_head;
    	ListNode* next = plist->_head->_next;
    	head->_next = newnode;
    	newnode->_prev = head;
    	newnode->_next = next;
    	next->_prev = newnode;
    }
    
    //头删
    void ListNodePopFront(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* head = plist->_head;
    	ListNode* next = plist->_head->_next;
    	ListNode* nextnext = plist->_head->_next->_next;
    	free(next);
    	next = NULL;
    	head->_next = nextnext;
    	nextnext->_prev = head;
    }
    
    //查找结点
    ListNode* ListFind(List* plist, LTDataType x)
    { 
    	assert(plist != NULL);
    	ListNode* cur = plist->_head->_next;
    	while (cur != plist->_head)
    	{ 
    		if (cur->_data == x)
    		{ 
    			return cur;
    		}
    		else
    		{ 
    			cur = cur->_next;
    		}
    	}
    	return NULL;
    }
    
    //在pos的前面进行插入
    void ListInsert(ListNode* pos, LTDataType x)
    { 
    	assert(pos != NULL);
    	ListNode* newnode = BuyListNode(x);
    	ListNode* prev = pos->_prev;
    	newnode->_prev = prev;
    	prev->_next = newnode;
    	newnode->_next = pos;
    	pos->_prev = newnode;
    }
    
    //删除pos位置的节点
    void ListErase(ListNode* pos)
    { 
    	assert(pos != NULL);
    	ListNode* prev = pos->_prev;
    	ListNode* next = pos->_next;
    	free(pos);
    	pos = NULL;
    	prev->_next = next;
    	next->_prev = prev;
    }
    
    //删除节点
    void ListRemove(List* plist, LTDataType x)
    { 
    	assert(plist != NULL);
    	ListNode* cur = plist->_head->_next;
    	ListNode* prev = NULL;
    	ListNode* next = NULL;
    	while (cur != plist->_head)
    	{ 
    		if (cur->_data == x)
    		{ 
    			prev = cur->_prev;
    			next = cur->_next;
    			free(cur);
    			prev->_next = next;
    			next->_prev = prev;
    			cur = next;
    		}
    		else
    		{ 
    			cur = cur->_next;
    		}
    	}
    }
    
    //反转链表
    void ReverseList(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* begin = plist->_head->_next;
    	ListNode* end = plist->_head->_prev;
    	while (begin != end && begin->_next != end)
    	{ 
    		LTDataType tmp = begin->_data;
    		begin->_data = end->_data;
    		end->_data = tmp;
    		begin = begin->_next;
    		end = end->_prev;
    	}
    }
    
    //链表长度
    int ListSize(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* cur = plist->_head->_next;
    	int count = 0;
    	while (cur != plist->_head)
    	{ 
    		count++;
    		cur = cur->_next;
    	}
    	return count;
    }
    
    //空返回0，非空返回1
    int ListEmpty(List* plist)
    { 
    	assert(plist != NULL);
    	return (plist->_head->_next == plist->_head ? 0 : 1);
    }
    
    //销毁链表
    void ListNodeDestory(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* cur = plist->_head->_next;
    	while (cur != plist->_head)
    	{ 
    		ListNode* next = cur->_next;
    		free(cur);
    		cur = next;
    	}
    	free(plist->_head);
    	plist->_head = NULL;
    }
    
    //打印链表
    void ListNodePrint(List* plist)
    { 
    	assert(plist != NULL);
    	ListNode* cur = plist->_head->_next;
    	printf("<-head->");
    	while (cur != plist->_head)
    	{ 
    		printf("<-%d->", cur->_data);
    		cur = cur->_next;
    	}
    	printf("\n");
    }