约瑟夫环.cpp

数据结构学习用到的一些程序！！里面有二叉树相关的几个

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 15
struct list
{
	int num;
	int mima;
	struct list *next;
};
typedef struct list node;
typedef node *link;


int data[2][max];


void print_list(link head,int n)   //把输入的数据打印出来！用以对照！
{
	int count=0;
	link pointer;
	pointer=head;
	printf("输入的数据是:");
	while(count<n)
	{
		printf("[%d,%d]",pointer->num,pointer->mima);
	    pointer=pointer->next;
		count++;
	}
	printf("\n");
}


link create_list(link head,int n)    //建立环！
{
	link newnode;
	link pointer;
	int i;
	head=(link)malloc(sizeof(node));
	if(head==NULL)
		printf("内存分配失败");
	else
	{
		printf("请输入第一个结点的标志数和密码！\n");
		scanf("%d%d",&data[0][0],&data[1][0]);
		head->num=data[0][0];
		head->mima=data[1][0];
		head->next=NULL;
		pointer=head;
		for(i=1;i<n;i++)
		{
            printf("请输入第%d结点的标志数和密码！",i+1);
			printf("\n");
            scanf("%d%d",&data[0][i],&data[1][i]);
			newnode=(link)malloc(sizeof(node));
			newnode->num=data[0][i];
			newnode->mima=data[1][i];
			newnode->next=NULL;
			pointer->next=newnode;
			pointer=newnode;
		}
		pointer->next=head;
	}
	return head;
}


void select(link head,int p,int n) //按照要求把结点筛选并打印出来！
{   
	link pointer;
	link back;
	link recorder;
	int counter=1;
	pointer=head;
	for (int i=0;i<n-1;i++)
		pointer=pointer->next;
	back=pointer;
	pointer=head;
	while(pointer->next!=pointer) //当不是最后一个数，即它的下一个元素不是本身！
	{
		if(counter!=p)    
		{
			back=pointer;
			pointer=pointer->next;
		    counter++;
		}
		else
		{
			recorder=pointer;        //当与密码序号一样时，打印出来，然后销毁。
			pointer=pointer->next;
			back->next=pointer;
			printf("[%d,%d]",recorder->num,recorder->mima);
			p=recorder->mima;
			free(recorder);
			counter=1;
		}
	}
	printf("\n最后的数据是");
	printf("[%d,%d]\n",pointer->num,pointer->mima);
}

void main()
{   
	int n;    //结点总数！
	int p;   //初始密码！
	printf("请输入结点总数和初始密码！\n");
	scanf("%d%d",&n,&p);
	link head=(link)malloc(sizeof(node));
	head=create_list(head,n);
	printf("表已建立\n");
	print_list(head,n);
	printf("依次淘汰的数据为");
	select(head,p,n);
}