数据结构的题 有没有大佬
课程设计
1
约瑟夫（Joseph）问题的一种描述是：设编号为1，2，…，n的n（n>0）个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始时任选一个整数作为报数上限值m，从一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。要求设计一个程序模拟此过程，求出出列顺序。 （2） 设计要求 设计一个程序，以人机交互方式执行，用户指定约瑟夫环游戏的总人数n和初始的报数上限m，然后输入每个人所持有的密码key。模拟约瑟夫环，从头开始报数，直到所有的人出列。系统按照出列顺序给出编号。 （3） 数据结构 本设计利用带头结点的单循环链表作为模拟约瑟夫环游戏的存储结构。
-
#include <iostream> using namespace std; #define OK 1 typedef int ElemType; typedef struct LNode{ ElemType data,num; struct LNode *next; }LNode,*Linklist; int CreateLinklist(Linklist &L,int n){ int temp = 0; cout<<"please enter data:"<<endl; cin>>L->data; L->num=1; temp++; Linklist p = L; for(int i=1;i<n;i++){ Linklist s = new LNode; cin>>s->data; s->num = temp; p->next = s; p = s; } p->next = L; return OK; } int DeleteLinklist(Linklist & L, Linklist & x, int & m){ Linklist temp; for(int i = 0; i < m - 1; i++){ x = x -> next; } m = x -> next -> data; cout << x -> next -> num<<" "; temp = x ->next; x -> next = x -> next -> next; delete temp; return OK; } void DisplayLinklist(Linklist L){ Linklist p = L; for(int i = 0; p -> next != L;i++){ cout << p -> data <<" "; p = p -> next; } cout << p -> data <<" " <<endl; } int main(){ Linklist L =new LNode; Linklist p =new LNode; int n,m; cout<<"Please enter m"<<endl; cin>>m; cout<<"Please enter n"<<endl; cin>>n; CreateLinklist(L,n); DeleteLinklist(L,p,m); DisplayLinklist(L); return OK; } -
#include <iostream> using namespace std; struct monkey { int num; monkey *next; }; int joseph(int sum, int cycle) { int i; monkey *p_old, *p_new, *head=NULL; head = new monkey; //此处创建一个循环链表(create a circular chained table) head->num = 1; p_old = head; for(i=2; i<=sum; i++) { p_new = new monkey; p_new->num = i; p_old->next = p_new; p_old = p_new; } p_new->next = head; p_old = head; i = 1; //循环删除元素直到只剩下最后一个元素(delete elements circularly until the last element left) while(1) { p_new = p_old->next; i++; if(p_new == p_old) break; if((i % cycle) == 0) { p_old->next = p_new->next; p_new->next = NULL; delete p_new; i = 0; } else { p_old = p_new; } } return p_new->num; } int main(void) { int n,m; cin>>n>>m; cout<<joseph(n,m)<<endl; return 0; }
发表回复