环形链表

约定不等于承诺〃 2022-09-24 05:23 173阅读 0赞

环形链表.h

#include<stdio.h>
    #include<stdlib.h>
    
    struct info
    {
    	int data;
    	struct info *pNext;
    };
    
    typedef struct info node, *PNODE;
    
    PNODE addBack(PNODE phead, int data);	//尾部插入
    PNODE addFront(PNODE phead, int data);	//头部插入
    PNODE findFirst(PNODE phead, int data);	//检索数据
    PNODE deleteFirst(PNODE phead, int data);	//删除数据
    
    PNODE deleteNode(PNODE phead, int data,PNODE *ptemp);	//删除数据
    
    PNODE insertNode(PNODE phead, int finddata, int data);	//插入数据
    int getNum(PNODE phead);	//返回链表的个数
    void showAll(PNODE phead);	//显显示全部

环形链表.c

#include"环形链表.h"
    
    PNODE addBack(PNODE phead, int data)	//尾部插入
    {
    	node *pnew = malloc(sizeof(struct info));	//分配内存
    	pnew->data = data;
    
    	if (phead == NULL)
    	{
    		phead = pnew;
    		phead->pNext = pnew;
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead) //循环到尾部
    		{
    			p = p->pNext;
    		}
    		p->pNext = pnew;
    		pnew->pNext = phead; //头尾相连
    		
    	}
    
    	return phead;
    }
    PNODE addFront(PNODE phead, int data)	//头部插入
    {
    	node *pnew = malloc(sizeof(struct info));	//分配内存
    	pnew->data = data;
    
    	if (phead == NULL)
    	{
    		phead = pnew;
    		phead->pNext = pnew;
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead) //循环到尾部
    		{
    			p = p->pNext;
    		}
    		p->pNext = pnew;
    		pnew->pNext = phead; //头尾相连
    		phead = pnew;
    	}
    
    	return phead;
    }
    void showAll(PNODE phead)	//显显示全部
    {
    	if (phead == NULL)
    	{
    		printf("链表为空！\n");
    		return;
    	}
    	else if (phead->pNext == phead)
    	{
    		printf("%d %p %p\n", phead->data, phead, phead->pNext);	//只有一个节点
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			printf("%d %p %p\n", p->data, p, p->pNext);	
    			p = p->pNext;
    		}
    		printf("%d %p %p\n", p->data, p, p->pNext);	//最后一个节点。
    	}
    }
    
    PNODE findFirst(PNODE phead, int data)	//检索数据
    {
    	if (phead == NULL)
    	{
    		return	NULL;
    	}
    	else if (phead->pNext == phead) //如果头节点是要查询的数据
    	{
    		return phead;
    	}
    	else
    	{
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			if (p->data == data)
    			{
    				return p; //如果找到返回。
    			}
    			else
    			{
    				p = p->pNext;	//找不到继续前进
    			}
    		}
    		if (p->data == data)
    			return p;
    		return NULL;
    	}
    }
    PNODE deleteFirst(PNODE phead, int data)	//删除数据
    {
    	//先判断要删除的数据是否存在。
    	PNODE p = findFirst(phead, data);
    	if (p == NULL)
    	{
    		printf("没有检索到数据！\n");
    		return phead;
    	}
    	//删除需要使用双指针
    	PNODE p1, p2;
    	p1 = phead;
    	p2 = NULL;
    	//上面的判断要使用，否则最后一个不好判断
    	while (p1->pNext != phead)
    	{
    		if (p1->data == data)
    		{
    			break;
    		}
    		else
    		{
    			p2 = p1;
    			p1 = p1->pNext;//循环下个节点
    		}
    	}
    
    	if (p1 != phead)
    	{
    		p2->pNext = p1->pNext;
    		free(p1);
    		p1 = NULL;
    	}
    	else
    	{
    		node *p = phead;
    		while (p->pNext != phead)
    		{
    			p = p->pNext;
    		}
    
    		phead = phead->pNext;	//改变头节点
    		free(p1);	//释放p1
    		p->pNext = phead;
    
    	}
    
    	//
    	//	if (p1->pNext == phead)
    	//	{
    	//		if (p1->data == data)
    	//		{
    	//			printf("删除的数据是:%d %p\n", p1->data, p1);
    	//			free(p1);
    	//			phead = NULL;
    	//			return phead;
    	//		}
    	//	}
    	//	else
    	//	{		
    	//		while (p1->pNext != phead)
    	//			{
    	//				if (p1->data == data)
    	//				{
    	//					break;//找到后跳出循环
    	//				}
    	//				else
    	//				{
    	//					p2 = p1;
    	//					p1 = p1->pNext;
    	//				}
    	//			}
    	//		/* 这儿最后一个数据没有访问到，所以先要用查询，查询一遍 */
    	//	}
    	//	if (p1 == phead)	//如果是第一个
    	//	{
    	//		PNODE p = phead;
    	//		while (p->pNext != phead)
    	//		{
    	//			p = p->pNext;	//循环到尾部
    	//		}			
    	//		phead = phead->pNext;
    	//		p->pNext = phead;
    	//		printf("删除的数据是:%d %p\n", p1->data, p1);
    	//		free(p1);
    	//		p1 = NULL;
    	//	}
    	//	else
    	//	{
    	//		p2->pNext = p1->pNext;
    	//		printf("删除的数据是:%d %p\n", p1->data, p1);
    	//		free(p1);
    	//	}
    		return phead;
    	
    }
    
    
    PNODE deleteNode(PNODE phead, int data, PNODE *ptemp)
    {
    	//先判断要删除的数据是否存在。
    	PNODE p = findFirst(phead, data);
    	if (p == NULL)
    	{
    		printf("没有检索到数据！\n");
    		return phead;
    	}
    	//删除需要使用双指针
    	PNODE p1, p2;
    	p1 = phead;
    	p2 = NULL;
    	//上面的判断要使用，否则最后一个不好判断
    	while (p1->pNext != phead)
    	{
    		if (p1->data == data)
    		{
    			break;
    		}
    		else
    		{
    			p2 = p1;
    			p1 = p1->pNext;//循环下个节点
    		}
    	}
    
    	if (p1 != phead)
    	{
    		p2->pNext = p1->pNext;
    
    		*ptemp = p1->pNext;	//指向下个节点
    		
    		free(p1);
    		p1 = NULL;
    	}
    	else
    	{
    		node *p = phead;
    		while (p->pNext != phead)
    		{
    			p = p->pNext;
    		}
    
    		phead = phead->pNext;	//改变头节点
    
    		*ptemp = p1->pNext;	//指向下个节点
    
    		free(p1);	//释放p1
    		p1 = NULL;
    		p->pNext = phead;
    
    	}
    	return phead;
    
    }
    
    PNODE insertNode(PNODE phead, int finddata, int data)	//插入数据
    {
    	PNODE pnew = malloc(sizeof(node));
    	pnew->data = data;
    
    	PNODE p = findFirst(phead, finddata);
    	if (p == NULL)
    	{
    		printf("没有找到要插入数据的标记！\n");
    	
    	}
    	else
    	{
    		PNODE p1, p2;
    		p1 = phead;
    		p2 = NULL;
    		while (p1->pNext != phead)
    		{
    			if (p1->data == finddata)
    			{
    				break;
    			}
    			else
    			{
    				p2 = p1;
    				p1 = p1->pNext;
    			}
    		}
    		if (p1 == phead)
    		{
    			
    			PNODE p = phead;
    			while (p->pNext != phead)
    			{
    				p = p->pNext;
    			}
    			//插在前面
    			p->pNext = pnew;
    			pnew->pNext = phead;
    			phead = pnew;
    
    			//插在后面
    		/*	pnew->pNext = phead->pNext;
    			phead->pNext = pnew;*/
    		}
    		else
    		{
    			//插在前面
    			p2->pNext = pnew;
    			pnew->pNext = p1;
    			//插在后面
    			/*pnew->pNext = p1->pNext;
    			p1->pNext = pnew;*/
    		}
    	}
    
    	return phead;
    }
    
    int getNum(PNODE phead)	//返回链表的个数
    {
    	if (phead == NULL)
    	{
    		return 0;
    	}
    	else if (phead->pNext == phead)
    	{
    		return 1;
    	}
    	else
    	{
    		int sum = 0;
    		PNODE p = phead;
    		while (p->pNext != phead)
    		{
    			sum++;
    			p = p->pNext;
    		}
    		sum++;
    		return sum;
    	}
    }

main.c

#include"环形链表.h"
    
    /* 环形链表的演示 */
    void main1()
    {
    	PNODE phead	= NULL;
    	for (int i = 0; i < 10; i++)
    	{
    		phead = addBack(phead, i);
    		//phead = addFront(phead, i);
    	}
    
    	//phead = addBack(phead, 88);
    
    	showAll(phead);
    	printf("\n\n");
    	PNODE p = findFirst(phead, 0);
    	p->data = 88;
    	showAll(phead);
    
    	phead = deleteFirst(phead, 88);
    	printf("\n\n");
    	showAll(phead);
    
    	printf("\n环形链表共有：%d 个\n", getNum(phead));
    
    	phead = insertNode(phead, 1, 99);
    	printf("\n\n");
    	showAll(phead);
    
    
    	printf("\n环形链表共有：%d 个\n", getNum(phead));
    
    
    
    	system("pause");
    }
    
    /* 约瑟夫环： 有m个人围成一圈，开始报数，报道n，退出，问最后剩下的是几号。下面是以数到 5 时出局 然后继续数 */
    void main()
    {
    	PNODE phead = NULL;
    	for (int i = 0; i < 10; i++)
    	{
    		phead = addBack(phead, i);
    		//phead = addFront(phead, i);
    	}
    
    	showAll(phead);
    
    	PNODE p = phead;
    	while (getNum(phead) != 1)
    	{
    		for (int i = 0; i < 4; i++)
    		{
    			p = p->pNext; 
    		}
    		//删除后需要让 p 指向下个节点，所以这儿使用了 &p.
    		phead = deleteNode(phead, p->data, &p);
    		
    		printf("\n\n");
    		showAll(phead);
    	}
    
    
    	system("pause");
    }