使用循环链表完成约瑟夫环问题
1.c
#include "1.h"
//创建循环链表
NodePtr list_create()
{//在堆区申请一个头结点NodePtr L = (NodePtr)malloc(sizeof(Node));if (NULL == L){printf("创建失败\n");return NULL;}//初始化L->len = 0;L->next = L; //头结点指针域指向自己printf("创建成功\n");return L;
}
//链表判空
int list_empty(NodePtr L)
{return L->next == L;
}
//链表申请空间封装节点
NodePtr apply_node(datatype e)
{//堆区申请一个节点的空间NodePtr p = (NodePtr)malloc(sizeof(Node));if (NULL == p){printf("申请失败\n");return NULL;}//给节点赋值p->data = e;p->next = NULL;return p;
}
//按位置进行查找
NodePtr list_search_pos(NodePtr L, int pos)
{//判断逻辑if (NULL == L || pos < 0 || pos > L->len){printf("查找失败\n");return NULL;}//查找逻辑NodePtr q = L;for (int i = 0; i < pos; i++){q = q->next;}return q;
}
//链表尾插
int list_insert_tail(NodePtr L, datatype e)
{//判断逻辑if (NULL == L){printf("插入失败\n");return -1;}//找到最后一个节点NodePtr q = list_search_pos(L, L->len);//封装节点NodePtr p = apply_node(e);if (NULL == p){return -1;}//插入逻辑p->next = q->next;q->next = p;//表的变化L->len++;printf("插入成功\n");return 0;
}
//链表遍历
int list_show(NodePtr L)
{//判断逻辑if (NULL == L || list_empty(L)){printf("遍历失败\n");return -1;}//遍历逻辑NodePtr q = L->next;while (q != L){printf("%d\t", q->data);q = q->next; //继续访问下一个}printf("\n");
}
//链表的头删
int list_delete_head(NodePtr L)
{//判断逻辑if (NULL == L || list_empty(L)){printf("删除失败\n");return -1;}//头删逻辑NodePtr p = L->next; //标记L->next = p->next; //孤立free(p); //删除p = NULL;//表长变化L->len--;printf("删除成功\n");return 0;
}
//链表销毁
void list_destroy(NodePtr L)
{//判断逻辑if (NULL == L){printf("释放失败\n");return;}//删除节点while (!list_empty(L)){list_delete_head(L);}//释放头结点free(L);L = NULL;printf("销毁成功\n");
}
void create(NodePtr L, datatype n)
{for (int i = 1; i <= n; i++){list_insert_tail(L, i);}
}
// 约瑟夫环问题求解
void josephus(NodePtr L, int m)
{NodePtr p = L->next; // 从第一个节点开始while (p->len > 1){for (int i = 1; i < m - 1; i++){p = p->next;}list_delete_head(p);}printf("最后活着的是: %d\n", p->data);
}
2.c
#include "1.h"
int main()
{NodePtr L = list_create();if (NULL == L){return -1;}int n, m;printf("请输入总人数n和报数间隔m");printf("例如(m=2,从一号开始则三号死)");scanf("%d %d", &n,&m);create(L, n);list_show(L);josephus(L, m);//调用释放函数list_destroy(L);L = NULL;return 0;
}
1.h
#ifndef LINKLIST_H
#define LINKLIST_H
#include <myhead.h>
//定义数据类型
typedef int datatype;//定义结点类型
typedef struct Node
{union{int len; //头结点数据域datatype data; //普通结点数据域};struct Node *next; //指针域
} Node, *NodePtr;
//创建循环链表
NodePtr list_create();
//链表判空
int list_empty(NodePtr L);
//链表申请空间封装节点
NodePtr apply_node(datatype e);
//按位置进行查找
NodePtr list_search_pos(NodePtr L, int pos);
//链表尾插
int list_insert_tail(NodePtr L, datatype e);
//链表遍历
int list_show(NodePtr L);
//链表的头删
int list_delete_head(NodePtr L);
//链表销毁
void list_destroy(NodePtr L);
void create(NodePtr L, datatype n);
// 约瑟夫环问题求解
void josephus(NodePtr L, int m);
#endif
使用栈,完成进制转换
输入:一个整数,进制数
输出:该数的对应的进制数
1.c
#include"1.h"
int main() {int number, base;printf("请输入一个整数和进制数(用空格隔开):");scanf("%d %d", &number, &base);printf("转换后的进制数为:");convertToBase(number, base);return 0;
}
2.c
#include"1.h"
void push(Stack *stack, int value)
{if (stack->top == MAX_SIZE - 1){printf("栈已满,无法插入新元素");return;}stack->data[++stack->top] = value;
}int pop(Stack *stack)
{if (stack->top == -1){printf("栈为空,无法弹出元素");return -1;}return stack->data[stack->top--];
}void convertToBase(int number, int base)
{Stack stack;stack.top = -1;while (number > 0){push(&stack, number % base);number /= base;}while (stack.top != -1){int digit = pop(&stack);if (digit < 10){printf("%d", digit);}else{printf("%c", 'A' + digit - 10);}}printf("\n");
}
1.h
#ifndef SEQSTACK_H
#define SEQSTACK_H
#include<myhead.h>
#define MAX_SIZE 100
typedef struct {int data[MAX_SIZE];int top;
} Stack;
void push(Stack *stack, int value);
int pop(Stack *stack);
void convertToBase(int number, int base);#endif