请问如何加一个双循环链表实现敢死队问题，以下是用单循环链表，顺序存储，循环队列实现
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
//顺序表
#define MAXSIZE 100
#define LISTINCCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct KList //定义数据结构体类型
{
ElemType *elem;//储存空间基址
int length ; //当前长度
int listsize;//当前分配的存储容量（以sizeof(ElemType)为单位）
}SqList;
int InitList(SqList &L)//创建线性表函数
{
L.elem=(ElemType *)malloc(MAXSIZE *sizeof(ElemType));//动态分配一个大小为MAXSIZE的数组空间
if(!L.elem)
{
printf("存储分配失败");
return ERROR;
}
else
{
L.length=0;//空表长度为0
L.listsize=MAXSIZE;
return OK;//初始存储容量
}
}
int ListInsert_Sq(SqList &L)//线性表再分配函数
{
//SqList L;
int *newbase;
newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCCREMENT)*sizeof(ElemType));
//为顺序表增加一个大小为存储LISTNCCREMENT 个数据元素的空间
if(!newbase)
{
printf("存储分配失败");
return ERROR;
}
else
{
L.elem=newbase;//新基址
L.listsize+=LISTINCCREMENT;
//增加存储容量
return OK;
}
}
//循环单链表
typedef struct node
{
int data;
struct node *next ;
}LNode;//定义结点类型
LNode *CREAT(int n)//创建循环单链表（n个敢死队队员）
{
LNode *s,*q,*T;
int i;
if(n!=0)
{
T=q=(LNode *)malloc(sizeof(LNode));//生成第一个结点
q->data=1;//使其data值为1
for(i=2;i<=n;i++)
{
s=(LNode*)malloc(sizeof(LNode));//自动生成结点
q->next=s;
q->next->data=i;//赋值
q=q->next;
}
q->next=T;
}
return T;//返回头结点，形成循环链表
}
DELETE (LNode *T)//链表的删除
{
LNode *a;
int i;
while(T->next!=T)
{
for(i=1;i<4;i++)//查找要删除节点的前一个结点
{
T=T->next;
}
a=T->next;
T->next=a->next;//删除数据
free(a);
T=T->next ;
}
printf("\n");
return (T->data );
}
//循环队列
#define QueueSize 1000//假定预分配的队列空间最多为1000个元素
//typedef int DataType;//假定队列元素的数据类型为字符
typedef struct{
int data[QueueSize];
int front;//头指针
int rear;//尾指针
int count; //计数器，记录队中元素总数
}SqQueue;
// 循环队列初始化
void InitQueue(SqQueue *Q)
{//构造空队列Q
Q->front=Q->rear=0;
Q->count=0; //计数器置0
}
// 判队列空
int IsEmpty(SqQueue *Q)
{
return Q->front==Q->rear;
}
//判队列满
int IsFull(SqQueue *Q)
{
return Q->rear==QueueSize-1+Q->front;
}
//进队列
void EnQueue(SqQueue *Q,int x)
{
if (IsFull(Q))
{
printf("队列上溢"); //上溢,退出运行
exit(0);
}
Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize; //循环意义下将尾指针加1
Q->count ++; //队列数加1
}
//出队列
int DeQueue(SqQueue *Q)
{
int temp;
if(IsEmpty(Q))
{
printf("队列为空"); //队列空,退出运行
exit(0);
}
temp=Q->data[Q->front];
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1
Q->count--; //队列数减1
return temp;
}
int main()
{
SqList L;
int s,i,count=0;//声明变量
LNode *p;
int z ,y,e=1,c=1;
int num;
int opt;
while(c)
{
printf("\n————敢死队问题————\n");
printf("1.顺序表\n");
printf("2.循环单链表\n");
printf("3.循环队列\n");
printf("4.退出\n");
printf("请选择使用的存储结构：（1~4）\n\n");
scanf("%d",&opt);
if(opt >4||opt <1)
{
printf("输入有误请重新输入\n");
continue;
}
switch(opt)
{
case 1:
printf("您使用的是顺序表存储结构\n\n");
while(e)
{
printf("请输入敢死队的人数：\n");
scanf("%d",&num);
if(num<1)
{
printf("输入有误请重新输入\n");
continue;
}
InitList(L);
while(num>L.listsize)//当顺序表当前分配的存储空间大小不足时进行再分配
ListInsert_Sq(L);
for(i=0;i<num;i++) L.elem[i]=i+1;//为队员赋值
s=num;
i=0;
while(s>1)//当所剩敢死队员总数为1时，总循环结束
{
for(i=0;i<num;i++)
if(L.elem[i]!=0)
{
count++;
if(count==5)//报数循环
{
L.elem[i]=0;//表示队员出列
count =0;//计数器清零
s--;//敢死队员数-1
}
}
}
for(i=0;i<num;i++)//输出从一开始最后剩余队员的位置为 L.elem[i]
if(L.elem[i]!=0)
if((num-L.elem[i]+2)%num==0)
printf("从第%d号开始计数能让排长最后一个留下。\n",num);
else
printf("从第%d号开始计数能让排长最后一个留下。\n",(num-L.elem[i]+2)%num);
break;
}
break;
case 2:
e=1;
printf("您使用的是循环单链表存储结构\n");
while(e)
{
printf("请输入敢死队的人数:\n");
scanf("%d",&num);
if(num<1)
{
printf("输入有误重新输入\n");
continue;
}
else
{
p=CREAT(num);
y=DELETE(p);//计算从根结点出发剩下的y
z=num-y+2;//计算从谁出发剩下根结点，公式1+num-y+1
if(z%num==0)
printf("从第%d号开始计数能让排长最后一个留下。\n",z);
else
printf("从第%d号开始计数能让排长最后一个留下。\n",(num-y+2)%num);
}
break;
}
break;
case 3:
e=1;
printf("您使用的是循环队列存储结构\n\n");
int start,count,j;
SqQueue s;
while(e)
{
printf("请输入敢死队的人数 :\n");
scanf("%d",&num);
if(num<1)
{
printf("输入有误请重新输入\n");
continue;
}
for(start=1;start<=num;start++)//start为测试起点
{
InitQueue(&s);
for(i=1;i<=num;i++)
{
EnQueue(&s,i);
}//初始化
for(i=1;i<start;i++)
{
j=DeQueue(&s);
EnQueue(&s,j);
}//将队头元素放到队尾，这样循环后start就会在队头
count=1;
while(count<num)
{
for(i=1;i<5;i++)
{
j=DeQueue(&s);
EnQueue(&s,j);
}//4个放到队尾
j=DeQueue(&s);//删除队头
count++;
}
if(s.data[s.front]==1)
break;
}
printf("从第%d号开始计数能让排长最后一个留下。\n",start);
break;
}
break;
case 4:
exit(0);
}
}
}
