主题:[原创]自己写的双向静态循环链表( ANIS C )
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef int ElemType;
typedef struct node
{
ElemType data;
int prior;
int next;
} SLinkList;
SLinkList space[MAXSIZE];
void InitSpace( SLinkList* space );
int Malloc_SL( SLinkList* space );
void Free_SL( SLinkList* space, int k );
bool InitList_SL( SLinkList* space, int S );
int ListLength_SL( SLinkList* space, int S );
bool GetElem_SL( SLinkList* space, int S, int i, ElemType* e );
bool ListInsert_SL( SLinkList* space, int S, int i, ElemType e );
bool ListDelete_SL( SLinkList* space, int S, int i, ElemType* e );
void output( SLinkList space[] );
int main( void )
{
int josh;
int i, n, m, s, j;
ElemType tmp;
scanf( "%d%d%d", &n, &m, &s );
InitSpace( space );
josh = Malloc_SL( space ); /*用约瑟夫环做试验,n要小于等于MAXSIZE - 2*/
InitList_SL( space, josh );
for ( i = 1; i <= n; ++i )
{
ListInsert_SL( space, josh, 0, i );
}
for ( i = 0, j = s - 1; i < n; ++i )
{
j = ( j + m - 1 ) % ( n - i ) + 1;
ListDelete_SL( space, josh, j--, &tmp );
printf( "%d\n", tmp );
}
Free_SL( josh );
system( "pause" );
return 0;
}
void InitSpace( SLinkList* space )
{
int i;
for ( i = 0; i < MAXSIZE - 1; ++i )
space[i].next = i + 1;
space[MAXSIZE - 1].next = 0;
}
int Malloc_SL( SLinkList* space )
{
int i = space[0].next;
if ( i )
space[0].next = space[i].next;
return i;
}
void Free_SL( SLinkList* space, int k )
{
space[k].next = space[0].next;
space[0].next = k;
}
bool InitList_SL( SLinkList* space, int S )
{
if ( S <= 0 )
return false;
space[S].next = S;
space[S].prior = S;
return true;
}
int ListLength_SL( SLinkList* space, int S )
{
int i = 0;
int j = S;
while ( space[j].next != S )
{
j = space[j].next;
++i;
}
return i;
}
bool GetElem_SL( SLinkList* space, int S, int i, ElemType* e )
{
int p = space[S].next;
int j = 1;
while ( p != S && j < i )
{
p = space[p].next;
++j;
}
if ( p == S || j > i ) /*限制i在1到length之间*/
return false;
*e = space[p].data;
return true;
}
bool ListInsert_SL( SLinkList* space, int S, int i, ElemType e )
{
int p = S;
int j = 0;
if ( i < 0 ) /*i可以是任意正整数,在0插入就是在头节点和最后一个节点之间插入*/
{
return false;
}
while ( j < i )
{
p = space[p].next;
++j;
}
j = Malloc_SL( space );
if ( !j )
return false;
space[j].data = e;
space[j].prior = space[p].prior;
space[j].next = p;
space[space[p].prior].next = j;
space[p].prior = j;
return true;
}
bool ListDelete_SL( SLinkList* space, int S, int i, ElemType* e )
{
int p = space[S].next;
int j = 1;
while ( p != S && j < i )
{
p = space[p].next;
++j;
}
if ( p == S || j > i ) /*限制i在1到length之间*/
return false;
space[space[p].prior].next = space[p].next;
space[space[p].next].prior = space[p].prior;
if ( e )
{
*e = space[p].data;
}
Free_SL( space, p );
return true;
}
void output( SLinkList space[] )
{
int i = 0;
do
{
printf( "%2d %2d %2d\n", i, space[i].data, space[i].next );
}
while ( ++i < MAXSIZE );
}
#include<stdlib.h>
#define MAXSIZE 20
typedef int ElemType;
typedef struct node
{
ElemType data;
int prior;
int next;
} SLinkList;
SLinkList space[MAXSIZE];
void InitSpace( SLinkList* space );
int Malloc_SL( SLinkList* space );
void Free_SL( SLinkList* space, int k );
bool InitList_SL( SLinkList* space, int S );
int ListLength_SL( SLinkList* space, int S );
bool GetElem_SL( SLinkList* space, int S, int i, ElemType* e );
bool ListInsert_SL( SLinkList* space, int S, int i, ElemType e );
bool ListDelete_SL( SLinkList* space, int S, int i, ElemType* e );
void output( SLinkList space[] );
int main( void )
{
int josh;
int i, n, m, s, j;
ElemType tmp;
scanf( "%d%d%d", &n, &m, &s );
InitSpace( space );
josh = Malloc_SL( space ); /*用约瑟夫环做试验,n要小于等于MAXSIZE - 2*/
InitList_SL( space, josh );
for ( i = 1; i <= n; ++i )
{
ListInsert_SL( space, josh, 0, i );
}
for ( i = 0, j = s - 1; i < n; ++i )
{
j = ( j + m - 1 ) % ( n - i ) + 1;
ListDelete_SL( space, josh, j--, &tmp );
printf( "%d\n", tmp );
}
Free_SL( josh );
system( "pause" );
return 0;
}
void InitSpace( SLinkList* space )
{
int i;
for ( i = 0; i < MAXSIZE - 1; ++i )
space[i].next = i + 1;
space[MAXSIZE - 1].next = 0;
}
int Malloc_SL( SLinkList* space )
{
int i = space[0].next;
if ( i )
space[0].next = space[i].next;
return i;
}
void Free_SL( SLinkList* space, int k )
{
space[k].next = space[0].next;
space[0].next = k;
}
bool InitList_SL( SLinkList* space, int S )
{
if ( S <= 0 )
return false;
space[S].next = S;
space[S].prior = S;
return true;
}
int ListLength_SL( SLinkList* space, int S )
{
int i = 0;
int j = S;
while ( space[j].next != S )
{
j = space[j].next;
++i;
}
return i;
}
bool GetElem_SL( SLinkList* space, int S, int i, ElemType* e )
{
int p = space[S].next;
int j = 1;
while ( p != S && j < i )
{
p = space[p].next;
++j;
}
if ( p == S || j > i ) /*限制i在1到length之间*/
return false;
*e = space[p].data;
return true;
}
bool ListInsert_SL( SLinkList* space, int S, int i, ElemType e )
{
int p = S;
int j = 0;
if ( i < 0 ) /*i可以是任意正整数,在0插入就是在头节点和最后一个节点之间插入*/
{
return false;
}
while ( j < i )
{
p = space[p].next;
++j;
}
j = Malloc_SL( space );
if ( !j )
return false;
space[j].data = e;
space[j].prior = space[p].prior;
space[j].next = p;
space[space[p].prior].next = j;
space[p].prior = j;
return true;
}
bool ListDelete_SL( SLinkList* space, int S, int i, ElemType* e )
{
int p = space[S].next;
int j = 1;
while ( p != S && j < i )
{
p = space[p].next;
++j;
}
if ( p == S || j > i ) /*限制i在1到length之间*/
return false;
space[space[p].prior].next = space[p].next;
space[space[p].next].prior = space[p].prior;
if ( e )
{
*e = space[p].data;
}
Free_SL( space, p );
return true;
}
void output( SLinkList space[] )
{
int i = 0;
do
{
printf( "%2d %2d %2d\n", i, space[i].data, space[i].next );
}
while ( ++i < MAXSIZE );
}