Question

（C语言）用静态链表求解约瑟夫问题。

Answer 1

#include "stdio.h"
// #include "conio.h"
#include "stdlib.h"
#define MAX 100
typedef struct nodes
{
int data;
nodes* next;
}Lnode; /*静态链表节点结构体定义 */

// typedef struct list
// {
// Lnode node[MAX];
// int head;
// }List,*PList;

void InitList(Lnode* pHead,int n)/*n为节点数 */
{
pHead->data = 0;
Lnode* pPre = pHead;
for(int i=1; i<n; ++i)
{
Lnode *pTemp = (Lnode*)malloc(sizeof(Lnode));
pTemp->data = i;
pPre->next = pTemp;
pPre = pTemp;

if (i == n-1)
{
pTemp ->next = pHead;
}
}
}

void Searchnode(Lnode *pHead, int n)/*m为报数，n为节点数,start为初始报数序号*/
{
Lnode* pNext = pHead;
Lnode* pPreNode = NULL;
while (1)
{
for(int i=0; i< n; ++i)
{
pPreNode = pNext;
pNext = pNext->next;
}

printf("delete: %d\n",pNext->data);
if (pPreNode->next == pNext->next)
{
break;
}

pPreNode->next = pNext->next;
free((void *)pNext);
pNext = pPreNode->next;
}
}

void main()
{
int i;
int n=10,start=1;

Lnode* pHeadNode = (Lnode*)malloc(sizeof(Lnode));
InitList(pHeadNode, n);

Lnode* pNext = pHeadNode;
for (i=0;i<10; ++i)
{
printf("%d\n", pNext->data);
pNext = pNext->next;
}

printf("请输入一个数\n");
scanf("%d", &n);
n %= 10;
Searchnode(pHeadNode, n);
getchar();
// printf("Hello, world\n");
}

追问

静态链表是为了在那些没有指针类型的高级语言中继续使用链式结构而设计的，静态链表的指针是结点的数组下标。先定义一个结构体记录：
typedef struct {
DataType data; /*元素*/
int next; /*相对指针*/
}SNode;
再定义一个静态链表：
#define maxsize 100
typedef struct {
SNode sp[maxsize];
int SL; /*静态链表头指针*/
}StList,*PSList;
如果按这个做怎么实现？

追答

数组和指针还不是一样的东西，换一下就可以啦。照样做咯。例如int a[100]; 可以给首地址给指针int *p = a;

追问

你给的程序不就是单循环链表么？

追答

嗯。用数组查和用指针查你觉得差别大么，数组是按指标，指针是从头开始一个个读，按这个程序，你用数组的话把那些NEXT操作都按指标加1就差不多了吧