第二章上机及作业题第二章上机题用三种存储结构（顺序表，链表，静态链表）求解josuphu问题！1：顺序表#include<stdio.h>#define max 100typedef struct{int data[max];int length;}stack,*pstack;pstack Creat() /*顺序表初始化*/{pstack p;p=(pstack)malloc(sizeof(stack));if(p)p->length=0;return p;}void Creatstack(pstack p) /*创建一个顺序表*/{int i,l,x;printf("please stack's length:\n");scanf("%d",&l);p->length=l;printf("please enter a stack:\n");for(i=0;i<l;i++){scanf("%d",&x);p->data[i]=x;}}Deletes(pstack p,int x) /*删除指定位置的元素*/{int i;for(i=x;i<=p->length;i++){p->data[i]=p->data[i+1];}p->length--;}int josephus(pstack p) /*约瑟夫循环*/{int s1,i,s,m,w;printf("please enter start adress:\n");scanf("%d",&s);printf("please enter how long to out eachother:\n");scanf("%d",&m);if(!p->length){printf("empty!\n");return 0;}s1=s-1;printf("please answer:\n");for(i=p->length;i>0;i--){s1=(s1+m-1)%i;w=p->data[s1];printf("%4d",w);Deletes(p,s1);}return 1;}int main() /*主函数*/ {pstack Q;Q=Creat();Creatstack(Q);josephus(Q);getch();}2：链表解决#include<stdio.h>typedef struct node /*定义一个链表结构体*/ {int data;struct node *next;}list,*List;void Putlist(List L) /*输入一个链表*/{int x,i,length;List s;L=NULL;printf("please enter the length:\n");scanf("%d",&length);printf("please enter the list:\n");for(i=0;i<length;i++){s=(List)malloc(sizeof(list));scanf("%d",&x);s->data=x;s->next=L;L=s;}s->next=L;}void Dislist(List L) /*输出链表*/{List p=L->next;printf("%d",L->data);while(p!=L){printf("%3d",p->data);p=p->next;}printf("\n");}int josephs(List L) /*约瑟夫循环的计算*/ {int s,m,count;List p,pre;printf("start in:\n");scanf("%d",&s);printf("how often:\n");scanf("%d",&m);if(!L){printf("the list is empty!\n");return 0;}p=L;for(count=1;count<s;count++){p=p->next;}printf("put the answer:\n");while(p!=p->next){for(count=1;count<m;count++) {pre=p;p=p->next;}printf("%2d",p->data);pre->next=p->next;free(p);p=pre->next;}printf(" %d",p->data);free(p);return 1;}void main(){int x,i,length;List L,s,r;s=L=(List)malloc(sizeof(list)); printf("please enter the length:\n"); scanf("%d",&length);printf("please enter the list:\n"); scanf("%d",&x);L->data=x;for(i=0;i<length-1;i++){r=(List)malloc(sizeof(list)); scanf("%d",&x);r->data=x;s->next=r;s=s->next;}s->next=L;josephs(L);getch();}3：静态链表#include<stdio.h>#define MAXSIZE 100struct node{int number;int next;}string[MAXSIZE];int josephus(void) /*约瑟夫循环*/ {int total;int out;int start;int i,j=1;int flag=0;int current,front;printf("The total number is:");scanf("%d",&total);printf("The out number is:");scanf("%d",&out);printf("The starting number is:");scanf("%d",&start);if(out==1) return total;for(i=0;i<total;i++){string[i].number=i+1;string[i].next=i+1;}string[i-1].next=0;front=total-1;current=0;for(i=1;i<start;i++){front=string[front].next;current =string[current].next;}while(flag<total){if(j%out==0){string[front].next=string[current].next;current=string[front].next;j=1;flag++;}else{j++;front=string[front].next;current =string[current].next;}}return(string[current].number);}void main(){int t;t=josephus();printf("The last one is %d",t);getch();}第二章作业：1．已知递增有序的两个单链表A，B分别存储了一个集合。
