第六次课程

队列的链表实现

#include "bits/stdc++.h"
using namespace std;
// 队列的节点
struct Node
{
    int data;//数据域
    struct Node* next;//指针域
};
// 队首队尾指针
struct Queue
{
    struct Node* front;//队头指针
    struct Node* rear;//队尾指针
    int size;//队列长度
};

void QueueInit(struct Queue* queue)//初始化队列
{
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

int QueueEmpty(struct Queue* queue)//判断队列为空
{
    return (queue->size == 0);//队列长度为空 返回1
}

void QueuePush(struct Queue* queue, const int data)//入队
{
    struct Node* node;
    node = (struct Node*)malloc(sizeof(struct Node));//为节点分配空间
    assert(node != NULL);//断言节点不为空 可进行后续程序
    node->data = data;
    node->next = NULL;
    if(QueueEmpty(queue))//如果队列为空
    {
        queue->front = node;
        queue->rear = node;
    }
    else
    {
        queue->rear->next = node;
        queue->rear = node;
    }
    ++queue->size;//队列长度++
}

int QueuePop(struct Queue* queue, int* data)//出队
{
    if (QueueEmpty(queue))//队列中没有数据 程序退出
    {
        return 0;
    }
    struct Node* tmp = queue->front;//创建临时节点
    *data = queue->front->data;
    queue->front = queue->front->next;
    free(tmp);
    --queue->size;
    return 1;
}
void QueueDestroy(struct Queue* queue)//销毁队列
{
    struct Node* tmp;
    while(queue->front)
    {
        tmp = queue->front;
        queue->front = queue->front->next;
        free(tmp);
    }
    queue->front=queue->rear=NULL;
}
void GetLength(struct Queue *queue)//获取队列长度
{
    int data= queue->size;
    printf("队列长度为:%d",data);
    printf("n");
}
void GetHead(struct Queue *queue)//获取队头元素
{
    int data=queue->front->data;
    printf("队头元素是%d:",data);
    cout<front)
    {
        tmp=queue->front;
        data=tmp->data;
        printf("%d ",data);
        queue->front=queue->front->next;
    }
    printf("n");
}
void menu(struct Queue* Q)
{
    int choice,data;
    cout<<"1.***入队     2.***出队"<>choice;
    switch (choice){
        case 1:cout<<"输入数据:";cin>>data;QueuePush(Q,data);break;
        case 2:QueuePop(Q,&data);cout<<"出队的元素是:"< 
约瑟夫环的链表实现
 
#include "bits/stdc++.h"
using namespace std;
typedef struct Node{
    int num;
    struct Node *next;
}JoseNode,*pNode;
void JoseInit(pNode &p)//初始化约瑟夫环
{
    p=new JoseNode ;//分配空间
    p->next=p;//建立链表循环
}
void Jose_Insert(pNode &p,int n)//约瑟夫环的插入
{
    pNode tmp=p;//临时节点 始终指向头节点
    for(int i=1;i<=n;i++)
    {
        if(i==1) tmp->num=i;//为头节点录入第一个数据
        else
        {
            //创建新节点 并用尾插法
            JoseNode *newNode=new JoseNode ;
            newNode->num=i;
            tmp->next=newNode;
            newNode->next=p;//新节点的指针域指向头节点 建立循环
            tmp=newNode;//临时节点向后移一位
        }
    }
}
void Jose_Delete(pNode &p,int k,int n)//k是密码
{
    pNode tmp;
    cout<<"出环顺序为:";
    while (n!=0)//当环内人数不为0时 程序执行
    {
        for(int i=1;inext;
        }
        tmp=p->next;//所求位置节点
        p->next=tmp->next;//让所求位置的前一个节点指针 指向所求位置的后一个节点
        cout<num<<"->";
        free(tmp);//释放节点
        p=tmp->next;//将新节点向后移一个位置
        n--;
    }
}
int main()
{
    pNode p;
    int n,k;//n是人数 k是密码
    JoseInit(p);//初始化
    cout<<"输入人数和密码:";
    cin>>n>>k;
    Jose_Insert(p,n);//约瑟夫环插入
    Jose_Delete(p,k,n);//约瑟夫环的输出
}

 
约瑟夫环的数组实现
 
#include "bits/stdc++.h"
using namespace std;
int Joseph[100]={0};
int main()
{
    int n,m;//n是人数 m是密码
    int i=0,k=0,j=0;//i是数组下标标识位置 k是标记符标记数到了几 j是出局的人数
    cin>>n>>m;
    while(j!=n)
    {
        i++;//下标从1开始
        if(i>n) i=1;//如果超出下标n 重新从下标1开始
        if(Joseph[i]==0)
        {
            k++;
            if(k==m)//当数到m时 输出当前位置下标
            {
                j++;
                cout<";
                k=0;//重新初始化k 从0继续开始
            }
        }
    }
}
 
约瑟夫环的递归实现
 
#include "bits/stdc++.h"
using namespace std;
//ysf(n,k,i)=ysf(n-1,k,i-1) i!=1 ysf(n,k,i)=(n+k-1)%n i=1;
int ysf(int n,int k,int i)//n为总人数 报数为k 第i个人出队的编号
{
    if(i==1)
        return (n+k-1)%n;
    else
        return (ysf(n-1,k,i-1)+k)%n;
}
int main()
{
    int n,m;
    cout<<"输入人数和密码:";
    cin>>n>>m;
    cout<<"出环顺序:";
    for(int i=1;i<=n;i++)
        cout<";
    return 0;
}
 
约瑟夫环递推法实现
 
#include "bits/stdc++.h"
using namespace std;
int cir(int n,int m)
{
    int p=0;
    for(int i=2;i<=n;i++)
    {
        p=(p+m)%i;//每次循环向前移动m个位置
    }
    return p+1;
}
int main()
{
    int n,k;
    cout<<"输入人数和密码";
    cin>>n>>k;
    cout<<"出环顺序:";
    cout<