1202作业

思维导图

作业

1> 使用单向循环链表完成约瑟夫环问题

#include <myhead.h>
typedef int datatype;;
typedef struct Node
{union{int len;datatype data;};struct Node *next;
}Node,*Node_ptr;//判空函数
int list_empty(Node_ptr L)
{if(NULL==L){printf("链表不合法\n");return -1;}return L->next==L?1:0;
}//尾插函数
int list_insert_tail(Node_ptr L,Node_ptr p)
{if(NULL==L){printf("尾插失败\n");return -1;}Node_ptr q = L;while(q->next != L)//找到最后一个节点{q = q->next;}q->next = p;p->next = L;L->len++;//printf("插入成功\n");return 0;}//创建节点封装数据函数
Node_ptr list_node_apply(datatype e)
{Node_ptr p = (Node_ptr)malloc(sizeof(Node));if(NULL==p){printf("申请失败\n");return NULL;}p->data = e;p->next = NULL;//printf("封装成功\n");return p;
}//创建循环链表函数
Node_ptr list_creat()
{Node_ptr L = (Node_ptr)malloc(sizeof(Node));//申请空间if(NULL==L){printf("申请失败\n");return NULL;}
//去除头结点
Node_ptr list_head_delete(Node_ptr L)
{if(NULL==L){printf("去头失败\n");return NULL;}if(list_empty(L)){free(L);return NULL;}Node_ptr q = L->next;while(q->next != L){q = q->next;}q->next = L->next;free(L);L=NULL;printf("去头成功\n");return q->next;
}L->len=0;L->next = L;//头指针指向自己printf("创建循环链表成功\n");return L;
}//遍历函数
void list_show(Node_ptr L)
{if(NULL==L || list_empty(L)){printf("遍历失败\n");return ;}Node_ptr q = L->next;printf("该链表信息如下：\n");while(q!= L){printf("%d\t",q->data);q = q->next;}putchar(10);
}//按幸运数字循环，去除节点
int list_delete_luck(Node_ptr L,Node_ptr H,int luck)
{if(list_empty(L)){return -1;}Node_ptr q = L->next;Node_ptr r = L;int i=1;while(L->len!=0){if(i==luck){Node_ptr p = q;r->next = q->next;L->len--;list_insert_tail(H,p);i = 1;q = r->next;}else{r = q;q = q->next;i++;}if(q==L){q = L->next;}}return 0;
}/*****************************主函数***********************************/
int main(int argc, const char *argv[])
{//创建循环链表Node_ptr L = list_creat();if(NULL==L){printf("链表不合法\n");return -1;}//将封装好的数据尾插到循环链表中int num=0;printf("请输入想要多少个数据存入约瑟夫环中：");scanf("%d",&num);for(int i=1;i<=num;i++){Node_ptr p = list_node_apply(i);//封装好的数据if(NULL==p){printf("申请失败\n");return -1;}list_insert_tail(L,p);//尾插到链表中}//调用遍历函数list_show(L);//创建另一新的链表Node_ptr H = list_creat();if(NULL==H){printf("申请失败\n");return -1;}//输入幸运数字，将去除的节点给新的链表int luck = 0;printf("请输入幸运数字：");scanf("%d",&luck);list_delete_luck(L,H,luck);list_show(H);return 0;
}