C 单链表 实现约瑟夫环
2024-08-28 22:16:26
list.h
#ifndef _List_H
#define _List_H
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
//定义一个空链表
List MakeEmpty();
//判断链表是否为空,0为空,1为非空
int IsEmpty( List L );
//int IsLast( Position P, List L );
//查找数据X在链表L中的位置,若不存在返回NULL
Position Find( ElementType X,List L );
//从链表中删除数据为X的结点
void Delete( ElementType X,List L);
// 从链表中删除P结点
void Delete_two( Position P );
//查找数据X在链表L中的直接前驱结点
Position FindPrevious( ElementType X, List L );
void Insert( ElementType X, Position P );
void DeleteList( List L );
//Position Header( List L);
//Position First( List L );
//Position Advice( Position P);
//ElementType Retrieve( Position P);
#endif /*_List_H*/
/*Place in the Implementation file */
struct Node
{
ElementType Element;
Position Next;
};
list.c
#include "list.h"
#include <stdlib.h>
/*make a empty list,Head pointer to it's head*/
List MakeEmpty()
{
PtrToNode L;
L=(struct Node*)malloc(sizeof(struct Node));
L->Next = L;
return L;
}
/*Return true if L is empty*/
int IsEmpty( List L )
{
if( L->Next == L )
return 1;
else
return 0;
}
/*Return true if P is the last position in list L*/
/*int IsLast( Position P, List L )
{
return P->Next==NULL;
}*/
/*Return Position of X in L;NULL if not found*/
Position Find( ElementType X,List L )
{
Position P;
P=L->Next;
while(P != L && P->Element != X)
P=P->Next;
if( P == L )
return NULL;
else
return P;
}
/*Delete first occurrence of X from a list*/
/*Assume use of a header node*/
void Delete( ElementType X, List L )
{
Position P, TmpCell;
P = FindPrevious( X, L );
if( P != NULL )
{
TmpCell = P->Next;
P->Next = TmpCell->Next;
free( TmpCell );
}
}
/* If X is not found, then Next field of returned */
/* Position id NULL*/
/*Assumes a header */
Position FindPrevious( ElementType X, List L )
{
Position P;
P = L;
while( P->Next != L && P->Next->Element != X )
P = P->Next;
if( P->Next == L )
return NULL;
else
return P;
}
void Delete_two( Position P)
{
Position preP, TmpCell;
preP = FindPrevious( P->Element , P );
if( preP != NULL )
{
TmpCell = preP->Next;
preP->Next = TmpCell->Next;
free( TmpCell );
}
}
/* Insert (after legal position P) */
/* Header implementtation assumed */
/* Parameter L is unused in this implementation */
void Insert( ElementType X, Position P )
{
Position TmpCell;
TmpCell = ( Position )malloc( sizeof ( struct Node ) );
if( TmpCell == NULL)
{
//printf( "Out of space!!!" );
}
TmpCell->Element = X;
TmpCell->Next = P->Next;
P->Next = TmpCell;
}
/* Correct DeleteList algorithm*/
void DeleteList( List L )
{
Position P, Tmp;
P = L->Next;
L->Next = NULL;
while( P != NULL)
{
Tmp = P->Next;
free(P);
P=Tmp;
}
}
Joseph.c
#include <stdio.h>
#include "list.h"
void main()
{
//定义链表L
List L;
L=MakeEmpty();
Position P;
//输入人数n和m
int n ,m = 4 , tamp;
//获取人数n
printf("请输入人的个数n:\n");
scanf("%d",&n);
if( n == 0 )
{
printf("请输入人数n\n");
return;
}
else
{
int i;
for( i = 0 ; i<n ; i++ )
{
if(i == 0 )
{
Insert( i+1 , L );
P = L->Next;
}
else
{
Insert( i+1 , P );
P = P->Next;
}
}
}
//获取m
printf("请输入m:\n");
scanf("%d",&m);
tamp = 1;
P = L->Next;
while( !IsEmpty( L ) )
{
if( tamp == m )
{
printf("%d",P->Element);
tamp = 0;
Delete( P->Element , L );
}
else
{
tamp++;
P = P->Next;
if( P == L )
P = P->Next;
}
}
printf("\n");
}
Github:https://github.com/Wave-Maker/DataStructs
最新文章
- quartz定时+log4net日志+exchangeservice发邮件
- 基于webpack的前端工程化开发解决方案探索(一):动态生成HTML(转)
- 2015年可用的TRACKER服务器大全
- CircleLayout
- Spring Filter components in auto scanning
- 编译Android4.3内核源代码
- telnet查看memcached运行参数说明
- Android Studio常用插件续
- Java程序员快速入门Go语言
- 此文本文件包含的数据无法放置在一个工作表中 gb2312
- Creating your own header file in C
- CSS 实现流布局以及多列混合布局
- PHP中常用操作文件的方法
- 在Unix系统中,主存索引节点和辅存索引节点从内容上比较有什么不同,为什么要设置主存索引节点?
- C# 当前 .NET SDK 不支持将 .NET Core 2.1 设置为目标。请将 .NET Core 2.0 或更低版本设置为目标,或使用支持 .NET Core 2.1 的 .NET SDK 版本。
- 并发编程(二)—— CountDownLatch、CyclicBarrier和Semaphore
- ORB-SLAM2的安装和运行流程
- Github提交本地代码
- 2017-10-5-Python
- C#高级编程9 第18章 部署