C语言：循环双链表的创建，插入，删除

电玩女神 2022-08-03 11:51 222阅读 0赞

/*
    	双向循环链表的创建，插入，删除
    */
    
    # include <stdio.h>
    # include <malloc.h>
    
    //节点类型
    typedef struct node
    {
    	int data;
    	struct node * pNext;
    	struct node * pPrior;
    }NODE, *PNODE;
    
    PNODE creat_list();  //建立链表
    void traverse(PNODE pHead);  //遍历链表
    void insert(PNODE pHead, int pos, int val);  //在链表的第pos位置插入元素val
    int Length(PNODE pHead);  //求链表的长度
    void getEle(PNODE pHead, int pos);  //获取第pos位置的前驱、后继元素
    void dele(PNODE pHead, int pos);  //删除第pos位置的元素
    
    int main(void)
    {
    	PNODE pHead = creat_list();  //创建循环双链表
    	traverse(pHead);
    
    	//在第pos节点前插入新节点
    	printf("在第1个节点前插入4：");
    	insert(pHead, 1, 4);
    	traverse(pHead);
    
    	//获取pos位置的前驱、后继
    	getEle(pHead, 2);
    
    	getEle(pHead, 3);
    
    	//删除第pos位置的元素
    	printf("删除第4个节点：");
    	dele(pHead, 4);
    	traverse(pHead);
    
    	return 0;
    }
    
    //创建循环双链表
    PNODE creat_list()
    {
    	int len;
    	int val;
    	int i;
    	PNODE pHead = (PNODE)malloc(sizeof(NODE));  //创建头结点
    	pHead->pNext = pHead;
    	pHead->pPrior = pHead;
    
    	PNODE pTail = pHead;
    	PNODE pNew;
    
    	printf("链表节点个数为 len = ");
    	scanf("%d", &len);
    
    	for(i = 0; i < len; i++)
    	{
    		printf("输入第%d个节点的值：", i+1);
    		scanf("%d", &val);
    
    		pNew = (PNODE)malloc(sizeof(NODE));
    		pNew->data = val;
    		pNew->pPrior = pTail;
    		pNew->pNext = pHead;
    
    		pTail->pNext = pNew;
    		pTail = pNew;
    	}
    
    	return pHead;
    
    }
    
    //遍历链表
    void traverse(PNODE pHead)
    {
    	PNODE p = pHead->pNext;
    
    	while(p != pHead)
    	{
    		printf("%d ", p->data);
    		p = p->pNext;
    	}
    	printf("\n");
    }
    
    //在第pos位置前插入元素val
    void insert(PNODE pHead, int pos, int val)
    {
    	PNODE p = pHead->pNext;   //p指向首节点
    
    	PNODE pNew = (PNODE)malloc(sizeof(NODE));
    	pNew->data = val;
    
    	int len = Length(pHead);
    
    	int count = 0;  //计数器
    
    	if(1 == pos)  //新节点插在首节点前
    	{
    		pNew->pNext = p;
    		p->pPrior = pNew;
    
    		pNew->pPrior = pHead;
    		pHead->pNext = pNew;
    	}
    	
    	//获取第pos-1个节点的指针p,新节点插在p后面
    	else if(pos > 1 && pos <= len + 1) 
    	{
    		while(p != pHead)
    		{
    			count ++;
    			if(count == pos - 1)
    			{
    				pNew->pNext = p->pNext;
    				p->pNext->pPrior = pNew;
    
    				p->pNext = pNew;
    				pNew->pPrior = p;
    				break;
    			}
    			p = p->pNext;
    		}
    	}
    	else
    	{
    		printf("插入位置错误");
    		return;
    	}
    }
    
    //求链表的长度
    int Length(PNODE pHead)
    {
    	int len = 0;
    	PNODE p = pHead->pNext; //p指向首节点
    	while(p != pHead)
    	{
    		len ++;
    		p = p->pNext;
    	}
    	
    	return len;
    }
    
    //获取第pos个节点的前驱，后继
    void getEle(PNODE pHead, int pos)
    {
    	PNODE p = pHead->pNext;
    	int count = 0;
    
    	while(p != pHead)
    	{
    		count ++;
    		if(count == pos)  //获取第pos节点的指针
    		{
    			if(p->pPrior == pHead)
    			{
    				printf("第%d个节点的前驱数头结点\n", pos);
    			}
    			else
    			{
    				printf("第%d个节点的前驱是：%d\n", pos, p->pPrior->data);
    			}
    
    			if(p->pNext == pHead)
    			{
    				printf("第%d个节点的后继数头结点\n", pos);
    			}
    			else
    			{
    				printf("第%d个节点的后继是：%d\n", pos, p->pNext->data);
    			}		
    		}
    
    		p = p->pNext;
    	}
    
    }
    
    //删除第pos节点
    void dele(PNODE pHead, int pos)
    {
    	PNODE p = pHead->pNext;
    	int count = 0;
    	int len = Length(pHead);
    
    	if(1 == pos)  //删除首节点
    	{
    		pHead->pNext = p->pNext;
    		p->pNext->pPrior = pHead;
    	}
    	else if(pos > 1 && pos < len + 1)
    	{
    		while(p != pHead)
    		{
    			count ++;
    			if(count == pos - 1)  //获取第pos-1节点的指针p
    			{
    				p->pNext = p->pNext->pNext;
    				p->pNext->pNext->pPrior = p;
    				break;
    			}
    			p = p->pNext;
    		}
    	}
    	else
    	{
    		printf("删除位置错误");
    		return ;
    
    	}
    }

![Center][]

[Center]: /images/20220731/ecda06f95ea94c11ac5374e0ad8d2e1f.png