单向循环链表——插入、删除、实现约瑟夫环、排序

2024年2月3日
1.请编程实现单向循环链表的头插，头删、尾插、尾删

自定义头文件：

#ifndef __head_h__
#define __head_h__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
typedef struct Node
{
	datatype data;
	struct Node *next;
}*Linklist;
Linklist create();
Linklist insert_head(Linklist head,datatype element);
Linklist insert_rear(Linklist head,datatype element);
void output(Linklist head);
Linklist delete_head(Linklist head);
Linklist delete_rear(Linklist head);

#endif

主函数：

#include"head.h"
int main(int argc, const char *argv[])
{
	datatype element;
	int num;
	Linklist head=NULL;
	printf("please enter num:");
	scanf("%d",&num);
	for(int i=0;i<num;i++)
	{
		printf("please enter %d element:",i+1);
		scanf("%d",&element);
		//head=insert_head(head,element);
		head=insert_rear(head,element);
	}
	output(head);
	puts("");
	head=delete_head(head);
	output(head);
	puts("");
	head=delete_rear(head);
	output(head);
	return 0;
}

自定义函数:

#include"head.h"
/*
 * function:    创建新节点
 * @param [ in] 
 * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
 * @return      
 */
Linklist create()
{
	Linklist s=(Linklist)malloc(sizeof(struct Node));
	if(s==NULL)
		return NULL;
	s->data=0;
	s->next=s;
	return s;
}
/*
 * function:   头插
 * @param [ in] 头　插入的值
 * @param [out] 头
 * @return      
 */
Linklist insert_head(Linklist head,datatype element)
{
	Linklist s=create();
	s->data=element;
	if(head==NULL)
	{
		head=s;
	}
	else
	{
		Linklist p=head;
		while(p->next!=head)
			p=p->next;
		s->next=head;
		head=s;
		p->next=head;
	}
	return head;
}
/*
 * function:    尾插　
 * @param [ in] 头　插入值
 * @param [out] 头
 * @return      
 */
Linklist insert_rear(Linklist head,datatype element)
{
	Linklist s=create();
	s->data=element;
	if(head==NULL)
	{
		head=s;
		return head;
	}
	Linklist p=head;
	while(p->next!=head)
	{
		p=p->next;
	}
	p->next=s;
	s->next=head;
	return head;
}
/*
 * function:    遍历输出
 * @param [ in] 头
 * @param [out] 
 * @return      
 */
void output(Linklist head)
{
	if(head==NULL)
	{
		puts("empty");
		return;
	}
	Linklist p=head;
	do
	{
		printf("%-5d",p->data);
		p=p->next;
	}while(p!=head);
}
/*
 * function:    头删
 * @param [ in] 头
 * @param [out] 头
 * @return      
 */
Linklist delete_head(Linklist head)
{
	if(head==NULL)
		return head;
	Linklist del=head;
	Linklist p=head;
	while(p->next!=head)
		p=p->next;
	p->next=head->next;
	head=head->next;
	free(del);
	return head;
}
/*
 * function:    尾删
 * @param [ in] 头
 * @param [out] 头
 * @return      
 */
Linklist delete_rear(Linklist head)
{
	if(head==NULL)
		return NULL;
	if(head->next==head)
	{
		free(head);
		head=NULL;
		return head;
	}
	Linklist p=head;
	while(p->next->next!=head)
	{
		p=p->next;
	}
	Linklist del=p->next;
	free(del);
	del=NULL;
	p->next=head;
	return head;
}

尾插、头删、尾删

头插、头删、尾删

⒉请编程实现单向循环链表约瑟夫环
约瑟夫环:用循环链表编程实现约瑟夫问题
n个人围成一圈，从某人开始报数1,2, .; m，数到m的人出圈，然后从出圈的下一个人(m+1)开始重复此过程，直到全部人出圈，于是得到一个出圈人员的新序列
如当n=8，m=4时，若从第一个位置数起，则所得到的新的序列为4,8,5,2,1,3,7,6。

头文件：

#ifndef __head_h__
#define __head_h__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
typedef struct Node
{
	datatype data;
	struct Node *next;
}*Linklist;
Linklist create();
Linklist insert_rear(Linklist head,datatype element);
void output(Linklist head);
Linklist joseph(Linklist head,int n,int m);

#endif

主函数：

#include"head.h"
int main(int argc, const char *argv[])
{
	datatype element;
	int num;
	Linklist head=NULL;
	printf("please enter num:");
	scanf("%d",&num);
	for(int i=0;i<num;i++)
	{
		printf("please enter %d element:",i+1);
		scanf("%d",&element);
		head=insert_rear(head,element);
	}
	output(head);
	puts("");
	int m;
	printf("please enter m:");
	scanf("%d",&m);
	head=joseph(head,num,m);
	return 0;
}

自定义函数：

/*
 * function:    创建新节点
 * @param [ in] 
 * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
 * @return      
 */
Linklist create()
{
	Linklist s=(Linklist)malloc(sizeof(struct Node));
	if(s==NULL)
		return NULL;
	s->data=0;
	s->next=s;
	return s;
}
/*
 * function:    尾插　
 * @param [ in] 头　插入值
 * @param [out] 头
 * @return      
 */
Linklist insert_rear(Linklist head,datatype element)
{
	Linklist s=create();
	s->data=element;
	if(head==NULL)
	{
		head=s;
		return head;
	}
	Linklist p=head;
	while(p->next!=head)
	{
		p=p->next;
	}
	p->next=s;
	s->next=head;
	return head;
}
/*
 * function:    遍历输出
 * @param [ in] 头
 * @param [out] 
 * @return      
 */
void output(Linklist head)
{
	if(head==NULL)
	{
		puts("empty");
		return;
	}
	Linklist p=head;
	do
	{
		printf("%-5d",p->data);
		p=p->next;
	}while(p!=head);
}
Linklist joseph(Linklist head,int n,int m)
{
	if(NULL==head)
		return head;
	Linklist p=head;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m-2;j++)
		{
			p=p->next;
		}
		printf("%-5d",p->next->data);
		Linklist del=p->next;
		p->next=del->next;
		free(del);
		del=NULL;
		p=p->next;
	}
}

3.请编程实现单向循环链表的排序

头文件：

#ifndef __head_h__
#define __head_h__
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int datatype;
typedef struct Node
{
	datatype data;
	struct Node *next;
}*Linklist;
Linklist create();
Linklist insert_rear(Linklist head,datatype element);
void output(Linklist head);
void bubble(Linklist head,int num);
void simple(Linklist head);

#endif

主函数：

#include"head.h"
int main(int argc, const char *argv[])
{
	datatype element;
	int num;
	Linklist head=NULL;
	printf("please enter num:");
	scanf("%d",&num);
	for(int i=0;i<num;i++)
	{
		printf("please enter %d element:",i+1);
		scanf("%d",&element);
		head=insert_rear(head,element);
	}
	output(head);
	puts("");
	//bubble(head,num);
	simple(head);
	output(head);
	return 0;
}

自定义函数：

#include"head.h"
/*
 * function:    创建新节点
 * @param [ in] 
 * @param [out] 成功返回首地址，失败返回ＮＵＬＬ
 * @return      
 */
Linklist create()
{
	Linklist s=(Linklist)malloc(sizeof(struct Node));
	if(s==NULL)
		return NULL;
	s->data=0;
	s->next=s;
	return s;
}
/*
 * function:    尾插　
 * @param [ in] 头　插入值
 * @param [out] 头
 * @return      
 */
Linklist insert_rear(Linklist head,datatype element)
{
	Linklist s=create();
	s->data=element;
	if(head==NULL)
	{
		head=s;
		return head;
	}
	Linklist p=head;
	while(p->next!=head)
	{
		p=p->next;
	}
	p->next=s;
	s->next=head;
	return head;
}
/*
 * function:    遍历输出
 * @param [ in] 头
 * @param [out] 
 * @return      
 */
void output(Linklist head)
{
	if(head==NULL)
	{
		puts("empty");
		return;
	}
	Linklist p=head;
	do
	{
		printf("%-5d",p->data);
		p=p->next;
	}while(p!=head);
}
void bubble(Linklist head,int num)
{
	if(NULL==head)
		return;	
	for(int i=1;i<num;i++)
	{
		Linklist p=head;
		for(int j=0;j<num-i;j++)
		{
			if(p->data>p->next->data)
			{
				datatype t=p->data;
				p->data=p->next->data;
				p->next->data=t;
			}
			p=p->next;
		}
	}
}
/*
 * function:    简单选择排序
 * @param [ in] 头
 * @param [out] 
 * @return      
 */
void simple(Linklist head)
{
	if(NULL==head)
		return;
	for(Linklist i=head;i->next!=head;i=i->next)
	{
		Linklist min=i;
		for(Linklist j=i->next;j!=head;j=j->next)
		{
			if(min->data>j->data)
				min=j;
		}
		if(min!=i)
		{
			datatype t=i->data;
			i->data=min->data;
			min->data=t;
		}
	}
}

冒泡排序：

简单选择排序：