链表-题

╰半夏微凉° 2022-09-26 13:57 134阅读 0赞

#pragma once
    #include <assert.h>
    #include <malloc.h>
    typedef int DataType;
    typedef struct SListNode
    {
    	DataType data;
    	struct SListNode* next;
    }SListNode;
    
    void PushBack(SListNode* & pHead, DataType x);
    void PopBack(SListNode* & pHead);
    void PushFront(SListNode* & pHead, DataType x);
    void PopFront(SListNode* & pHead);
    SListNode* Find(SListNode* pHead, DataType x);
    void Insert(SListNode* pos, DataType x);
    void Erase(SListNode* pos);
    void DestoryList(SListNode*& pHead);
    
    void DestoryList(SListNode*& pHead)
    {
    	SListNode* cur=pHead;
    	while(cur)
    	{
    		SListNode* tmp=cur;
    		cur=cur->next;
    		free(tmp);
    	}
    	pHead=NULL;
    }
    SListNode* _BuyNode(DataType x)
    {
    	SListNode* tmp=(SListNode*)malloc(sizeof(SListNode));
    	tmp->data=x;
    	tmp->next=NULL;
    	return tmp;
    }
    void PrintSlist(SListNode* pHead)
    {
    	SListNode* cur=pHead;
    	while(cur)
    	{
    		printf("%d->",cur->data);
    		cur=cur->next;
    	}
    	printf("NULL\n");
    }
    
    void PushBack(SListNode* &pHead,DataType x)
    {
    	//两种情况，1.空；2.不为空
    	if(pHead==NULL)
    	{
    		pHead=_BuyNode(x);
    	}
    	else
    	{
    		SListNode* tail=pHead;
    		while(tail->next!=NULL)
    		{
    			tail=tail->next;
    		}
    		tail->next=_BuyNode(x);
    	}
    }
    void PopBack(SListNode* &pHead)
    {
    	//1.空；2.一个结点；3.多个结点；
    	if(pHead==NULL)
    	{
    		return;
    	}
    	else if(pHead->next==NULL)
    	{
    		free(pHead);
    		pHead=NULL;
    	}
    	else
    	{
    		SListNode* tail=pHead;
    		SListNode* prev=NULL;
    		while(tail->next)
    		{
    			prev=tail;
    			tail=tail->next;
    		}
    		free(tail);
    		prev->next=NULL;
    	}
    }
    void PushFront(SListNode* &pHead,DataType x)
    {
    	//1.空2.不空
    	if(pHead==NULL)
    	{
    		pHead=_BuyNode(x);
    	}
    	else
    	{
    		SListNode* tmp=_BuyNode(x);
    		tmp->next=pHead;
    		pHead=tmp;
    	}
    }
    void PopFront(SListNode* &pHead)
    {
    	//1.空；2.一个结点；3.多个结点；
    	if(pHead==NULL)
    	{
    		return;
    	}
    	else if(pHead->next==NULL)
    	{
    		free(pHead);
    		pHead=NULL;
    	}
    	else
    	{
    		SListNode* tmp=pHead;
    		pHead=pHead->next;
    		free(tmp);
    	}
    }
    SListNode* Find(SListNode* pHead,DataType x)
    {
    	SListNode* cur=pHead;
    	while(cur)
    	{
    		if(cur->data==x)
    		{
    			return cur;
    		}
    		cur=cur->next;
    	}
    	return NULL;
    }
    void Insert(SListNode* pos,DataType x)
    {
    	assert(pos);
    	SListNode* tmp=_BuyNode(x);
    	tmp->next=pos->next;
    	pos->next=tmp;
    }
    void Erase(SListNode* &pHead,SListNode* pos)
    {
    	assert(pos);
    	assert(pHead);
    	if(pHead==pos)
    	{
    		pHead=pHead->next;
    		free(pos);
    		return;
    	}
    	SListNode* prev=pHead;
    	while(prev)
    	{
    		if(prev->next==pos)
    		{
    			prev->next=pos->next;
    			free(pos);
    			break;
    		}
    		prev=prev->next;
    	}
    }
    
    //求一个单链表中结点个数
    int size(SListNode* &pHead)
    {
    	int count=0;
    	if(pHead==NULL)
    	{
    		return 0;
    	}
    	else
    	{
    		SListNode *cur=pHead;
    		while(cur)
    		{
    			count++;
    			cur=cur->next;
    		}
    		return count;
    	}
    }
    //删除一个无头单链表的非尾结点
    void DelNonTailNode(SListNode* pos)
    {
    	assert(pos);
    	assert(pos->next);
    	SListNode* del=pos->next;
    	SListNode* next=del->next;
    	pos->data=del->data;
    	pos->next=next;
    	free(del);
    }
    //在无头单链表的一个非头结点前插入一个结点
    void InsertFrontNode(SListNode* pos,DataType x)
    {
    	assert(pos);
    	SListNode* tmp=_BuyNode(pos->data);
    	tmp->next=pos->next;
    	pos->next=tmp;
    	pos->data=x;
    }
    //逆置单链表
    SListNode* Reserve(SListNode* pHead)
    {
    	SListNode* cur=pHead;
    	SListNode* newHead=NULL;
    	while(cur)
    	{
    		SListNode* tmp=cur;
    		cur=cur->next;
    		tmp->next=newHead;
    		newHead=tmp;
    	}
    	return newHead;
    }
    //单链表排序
    void BubbleSort(SListNode* pHead)
    {
    	assert(pHead);
    	SListNode* begin=pHead;
    	SListNode* end=NULL;
    	while(pHead->next!=end)
    	{
    		while(begin->next!=end)
    		{
    			if(begin->data<begin->next->data)
    			{
    				int tmp=begin->data;
    				begin->data=begin->next->data;
    				begin->next->data=tmp;
    			}
    			begin=begin->next;
    		}
    		end=begin;
    		begin=pHead;
    	}
    }
    void SelectSort(SListNode* pHead)
    {
    	assert(pHead);
    	SListNode* begin=pHead;
    	SListNode* end=pHead;
    	while(begin->next!=NULL)
    	{
    		SListNode* tmp=begin;
    		end=begin->next;
    		while(end)
    		{
    			if(tmp->data>end->data)
    			{
    				tmp=end;
    			}
    			end=end->next;
    		}
    		if(tmp!=begin)
    		{
    			int x=tmp->data;
    			tmp->data=begin->data;
    			begin->data=x;
    		}
    		begin=begin->next;
    	}
    }
    //合并两个有序链表，合并后仍然有序
    SListNode* MergeList(SListNode* p1,SListNode* p2)
    {
    	SListNode* newHead=NULL;//新链表的头结点
    	SListNode* end=newHead;//新链表的当前结点
    	if(!p1)
    	{
    		return p2;
    	}
    	if(!p2)
    	{
    		return p1;
    	}
    	if(p1->data<p2->data)
    	{
    		newHead=p1;
    		p1=p1->next;
    	}
    	else
    	{
    		newHead=p2;
    		p2=p2->next;
    	}
    	end=newHead;
    	while(p1&&p2)
    	{
    		if(p1->data>p2->data)
    		{
    			end->next=p2;
    			end=p2;
    			p2=p2->next;
    		}
    		else
    		{
    			end->next=p1;
    			end=p1;
    			p1=p1->next;
    		}
    	}
    	if(!p1)
    	{
    		end->next=p2;
    	}
    	if(!p2)
    	{
    		end->next=p1;
    	}
    	return newHead;
    }
    //查找单链表的中间结点，要求只能遍历一次链表
    SListNode* FindMidNode(SListNode* pHead)
    {
    	SListNode* fast=pHead;
    	SListNode* slow=pHead;
    	while(fast&&fast->next)
    	{
    		slow=slow->next;
    		fast=fast->next->next;
    	}
    	return slow;
    }
    //查找单链表的倒数第k个结点
    SListNode* FindKNode(SListNode* pHead,int k)
    {
    	SListNode* fast=pHead;
    	SListNode* slow=pHead;
    	while(fast && k--)
    	{
    		fast=fast->next;
    	}
    	if(k>0)
    	{
    		return NULL;
    	}
    	while(fast)
    	{
    		slow=slow->next;
    		fast=fast->next;
    	}
    	return slow;
    }
    SListNode* JosephCycle(SListNode* pHead,int m)
    {
    	SListNode* cur=pHead;
    	if(cur==NULL)
    	{
    		return NULL;
    	}
    	while(1)
    	{
    		//只剩一个结点
    		if(cur==cur->next)
    		{
    			return cur;
    		}
    		int x=m;
    		while(--x)
    		{
    			cur=cur->next;
    		}
    		SListNode* del=cur->next;
    		cur->data=del->data;
    		cur->next=del->next;
    		free(del);
    	}
    }
    //判断单链表是否带环
    int IsCycle(SListNode* pHead)
    {
    	assert(pHead);
    	SListNode *fast=pHead;
    	SListNode *slow=pHead;
    	while(fast&&fast->next)
    	{
    		fast=fast->next->next;
    		slow=slow->next;
    		if(fast==slow)
    		{
    			return 1;
    		}
    	}
    	return 0;
    }
    //找带环单链表的环入口
    SListNode* FindEntry(SListNode* pHead)
    {
    	assert(pHead);
    	SListNode* fast=pHead;
    	SListNode* slow=pHead;
    	while(fast&&fast->next)
    	{
    		fast=fast->next;
    		slow=slow->next;
    		if(fast==slow)
    		{
    			break;
    		}
    	}
    	fast=pHead;
    	while(fast!=slow)
    	{
    		fast=fast->next;
    		slow=slow->next;
    	}
    	return fast;
    }
    //求带环单链表的环长
    int LengthCycle(SListNode* pHead)
    {
    	assert(pHead);
    	SListNode* fast=pHead;
    	SListNode* slow=pHead;
    	while(fast&&fast->next)
    	{
    		fast=fast->next->next;
    		slow=slow->next;
    		if(fast==slow)
    		{
    			break;
    		}
    	}
    	int count=0;
    	do
    	{
    		slow=slow->next;
    		count++;
    	}while(fast!=slow);
    	return count;
    }