数据结构题，必做和选做

来人，dd，周三前交，有偿有偿，机不可失失不再来，啊啊，三十个字好难凑，快来帮帮忙

冒泡排序：

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct _data
{
    ElemType data;
    struct _data* next;
}LinkNode, * LinkList;
 
 
//显示链表
void showList(LinkList head)
{
    LinkList p = head->next;
    while (p)
    {
       cout << p->data<<" ";
        p = p->next;
    }
    cout << endl;
}
 
//冒泡排序
void bubble_sort(LinkNode* L)
{
    LinkNode* p, * tail, * q;
    int tms = 1;
    tail = NULL;
    while ((L->next->next) != tail)
    {
        p = L;
        q = L->next;
        while (q->next != tail)
        {
            if (q->data > q->next->data) //升序排列
            {
                p->next = q->next;
                q->next = q->next->next;
                p->next->next = q;
                q = p->next;
               
            }
            q = q->next;
            p = p->next;
        }
        cout << "第" << tms << "遍排序结果：";
        tms++;
        showList(L); //显示链表
        tail = q;
    }
 
}
 
 
int main()
{
    ElemType a[] = { 9,8,7,6,5,4,3,2,1,0 };
    LinkList head, p, t, maxnode, prenode;
    int len = sizeof(a) / sizeof(int); //得到数组的大小
    int i;
 
    head = (LinkList)malloc(sizeof(LinkNode)); //创建头节点
    head->next = 0;
    p = head;
 
    //用数组元素构建链表
    for (i = 0; i < len; i++)
    {
        t = (LinkList)malloc(sizeof(LinkNode));
        t->next = 0;
        t->data = a[i];
        //节点插入链表
        p->next = t;
        p = t;
    }
   
    //链表排序
    bubble_sort(head);
 
    //遍历排序后的链表
    cout << "最终结果：";
    showList(head);
    return 0;
}
 

链表逆序：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct link_node 
{
    datatype info;
    struct link_node* next;
}node,*linklist;
linklist createList()
{
    datatype x;
    linklist L;
    char ch;
    L = (linklist)malloc(sizeof(node));
    if (L == NULL)
    {
        printf("error");
        return 0;
    }
    linklist n,p;
    p = L;
    printf("请输入整数系列：\n"); //输入系列并以回车结束
    while(1)
    {
        scanf_s("%d",&x,1);
        n = (linklist)malloc(sizeof(node));
        n->info = x;
        n->next = NULL;
        p->next = n;
        p = n;
        if( (ch=getchar()) == '\n') break;
    }
    return L;
}
void print(linklist head)
{
    linklist p;
    p = head->next;
    while(p)
    {
        printf("%d ",p->info);
        p = p->next;
    }
    printf("\n");
}
//翻转
linklist reverse(linklist head)
{
    linklist p,t,k;
    p = head->next;
    t = p->next;
    p->next = NULL;
    while(t)
    {
        k = t->next;
        head->next = t;
        t->next = p;
        p = t;
        t = k;
    }
    return head;
}
//释放内存
void release(linklist head)
{
    linklist p;
    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}
 
int main()
{
    linklist head = createList();
    print(head);
    head = reverse(head);
    printf("逆序后：");
    print(head);
    release(head);
    return 0;
}
 

约瑟夫环：

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef struct _data
{
    int flag; //标记
    int index;  //序号
    int pwd;

    struct _data* next;
}Stdata;

//创建链表
Stdata* CreateList(int n);
//报数出队
void CountOff(int n, int w, int s, Stdata* out);

int main()
{
    int n, w, s;
    Stdata* head = 0, * p, * t=0;
    srand((unsigned int)time(0));
    scanf("%d", &n);  //读取N，一共有N个人
    scanf("%d %d", &w, &s); //读入w和s，w是开始位置，报s的退出
    
    
    head = CreateList(n);

    CountOff(n, w, s, head);

    //释放空间
    while (head)
    {
        p = head->next;
        free(head);
        head = p;
    }
    head = 0;
    return 0;
}

Stdata* CreateList(int n)
{
    Stdata* head = 0, * p, * t = 0;
    int i;
    for (i = 0; i < n; i++)
    {
        p = (Stdata*)malloc(sizeof(Stdata));
        p->flag = 0;
        p->index = i + 1;
        p->pwd = 1 + rand() % 10; //生成1到10的正数作为密码
        p->next = 0;
        if (head == 0)
        {
            head = p;
            t = head;
        }
        else
        {
            t->next = p;
            t = p;
        }
    }
    t->next = head; //最后一个节点指向头节点
    return head;
}


void CountOff(int n, int w, int s, Stdata* head)
{
    int i = 1, t = n, k = 0;//t表示剩余人数
    Stdata* out = head;

    //找到第w个位置
    while (i < w)
    {
        out = out->next;
        i++;
    }


    //开始出队
    while (t != 0)
    {
        if (out->flag == 0)
        {
            k++;
            if (k % s == 0)
            {
                k = 0;
                out->flag = 1;
                printf("%d ", out->index);
                s = out->pwd; //将出队任意的密码作为新的s
                t--;
            }
        }
        out = out->next;
    }
}