高效实现Josephus算法

作者佚名技术来源程序设计浏览发布时间 2012-06-29

t Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List CreateList (ElementType X);
void DisposeList(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
void Remove(Position P, List * L);
void Insert(ElementType X, List L, Position P);
void DeleteList(List L);
Position NextPosition(Position P);
Position PreviousPosition (Position P);
ElementType Retrieve(Position P);
#endif // DLINKEDLIST_H_INCLUDED
　　
fatal.h
#ifndef FATAL_H_INCLUDED
#define FATAL_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
#define Error(Str)　　　　　　　　FatalError(Str)
#define FatalError(Str)　　 fprintf(stderr, "%s\n", Str), exit(1)
#endif // FATAL_H_INCLUDED
　　
dlist.c
#include "dlinkedlist.h"
#include "fatal.h"
struct Node
{
　　　　ElementType Element;
　　　　Position Next;
　　　　 Position Prev;
};
List CreateList(ElementType X)
{
　　　　 List L;
　　　　L = malloc(sizeof(struct Node));
　　　　if(L == NULL)
　　　　　　　　FatalError("Out of space!!!");
　　　　L- >Next = L->Prev = L;
　　　　L->Element = X;
　　　　return L;
}
void DisposeList(List L)
{
　　　　if(L->Next != L)
　　　　　　　　DeleteList(L);
　　　　free(L);
}
/* Return true if L is empty */
int IsEmpty(List L)
{
　　　　return L == NULL;
}
/* Return true if P is the last position in list L */
/* Parameter L is unused in this implementation */
int IsLast(Position P, List L)
{
　　　　return P == L;
}
/* Return Position of X in L; NULL if not found */
Position Find(ElementType X, List L)
{
　　　　if (L->Element == X)
　　　　　　　　return L;
　　　　Position P;
　　　　P = L->Next;
　　　　while(P != L && P- >Element != X)
　　　　　　　　P = P->Next;
　　　　if (P == L) //not found
　　　　　　　　P = NULL;
　　　　return P;
}
/* Delete from a list */
/* Cell pointed to by P->Next is wiped out */
/* Assume that the position is legal */
void Delete(ElementType X, List L)
{
　　　　Position P;
　　　　P = Find(X, L);
　　　　if (P != NULL)
　　　　　　　　Remove(P, &L);
}
void Remove (Position P, List * L)
{
　　　　if(P == *L)
　　　　{
　　　　　　　　if ((*L)->Next == *L)
　　　　　　　　{
　　　　　　　　　　　　free(*L);
　　　　　　　　　　　　*L = NULL;
　　　　　　　　　　　　return;
　　　　　　　　}
　　　　　　　　*L = (*L)->Next;
　　　　}
　　　　P->Prev->Next = P->Next;
　　　　P->Next ->Prev = P->Prev;
　　　　free(P);
}
/* Insert (after legal position P) */
/* Tailer implementation assumed */
/* Parameter L is unused in this implementation */
void Insert(ElementType X, List L, Position P)
{
　　　　Position TmpCell;
　　　　TmpCell = malloc(sizeof (struct Node));
　　　　if(TmpCell == NULL)
　　　　　　　　FatalError ("Out of space!!!");
　　　　TmpCell->Element = X;
　　　　TmpCell->Next = P->Next;
　　　　P->Next->Prev = Tmp

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!

分享到：更多

你可能对下面的文章感兴趣

上一篇: C++的可移植性和跨平台开发[2]：语法下一篇: 遍历多维数组（Traverse Multidimensioned Arrays）

关于高效实现Josephus算法的所有评论

随机推荐