《数据结构与算法实验题 2》由会员分享,可在线阅读,更多相关《数据结构与算法实验题 2(25页珍藏版)》请在金锄头文库上搜索。
1、数据结构与算法实验题 2.3大家一起来报数 实验任务 编号为 1 - n 的 n 个人按顺时针方向围坐一圈,从第一个人开始按顺时针方向自 1 开 始报数,报到 m 时停止,在报到 m 的那个人的左右的两个人出列,从他在顺时针方向下 一 个人开始重新从 1 报数,如此下去。如果还在游戏的人数少于 3 个,则游戏终止。在一行 内输出最后留下来的人编号 数据输入 输入第一行为 T ,代表接下去有 T 组测试, 0 left=leftList; leftList-right=mainList; mainList=leftList; mainList-left=headList; headList-ri
2、ght=mainList; return headList; void searchList(List mainList,int n,int m) while(n2) int mTemp=(m%n); while(mTemp-) mainList=mainList-left; List p,q; p=mainList-right; q=mainList-left; mainList-right=p-right; p-right-left=mainList; mainList-left=q-left; q-left-right=mainList; free(p); free(q); n-=2;
3、if(n=1) printf(“%dn“,mainList-n); else printf(“%d %dn“,(mainList-n)(mainList-left-n)?(mainList-left-n):(mainList-n), (mainList-n)left-n)?(mainList-left-n):(mainList-n); int main() int m,n; int num; scanf(“%d“, while(num-) scanf(“%d%d“, List list; list=creatList(n); searchList(list-right,n,m); 数据结构与算
4、法实验题 3.3价值问题 实验任务 小明最近在好或者坏的天气如何影响人们的心情,他发现,在给定的一段日子里,人的价值 可以通过一段时间内最坏的那天的心情等级 (可以有多天) 乘上这段时间心情等级的总和得 到(心情等级越小,心情越坏) ,于是他想请你帮忙计算一下给定 N 天里面,在连续一段 时间里他可能的价值最高。 数据输入 第一行为总天数 N(1b?len:b; if(ua.sign=1 if(s) if(!ua.sign) ua.value=a;ua.sign=1; if(!ub.sign) ub.value=b;ub.sign=1; connect(a,b); for(i=1;ib?len
5、:b; suma=sumb=1; input+; for(int i=0;ih=dp; if(t-son0-h=-1) DFS(t-son0,dp,endDp,endNode); if(t-son1 if(t-son2 dp-=1; void findNum(tree tree end=endNode; for(h=endDp;hendDp/2;h-) for(int i=0;isoni-h=h) end=endNode; endNode=endNode-soni; break; if(endDp%2!=0) printf(“%d %dn“,endNode-nn?endNode-n:end-n
6、,endNode-nend-n?endNode-n:e nd-n); else printf(“%dn“,endNode-n); int main() int num,m,n; int i,j; int dp,endDp; tree endNode; scanf(“%d“, tree t=(tree)malloc(n*sizeof(TreeNode); for(i=0;i1 i=i/2; int main() int n; int sum=0; int i,j; scanf(“%d“, int *a=(int*)malloc(n+1)*sizeof(int); for(i=1;i0;i-) M
7、ax_Heapify(a,i,n); int sign=0; int count; while(n1) int a1,a2; a1=getMin(a,n); if(sign=0) a2=getMin(a,n); else a2=count; sign=0; count=a1+a2; int a3=a1; if(counta3) insertItem(a,a1+a2,n); else sign=1; sum+=count; printf(“%dn“,sum); /* 7 1 2 3 4 5 6 7 */ 算法与数据结构题 实验题 9.1三瓣雪花 实验任务 在观念中,雪花总是六瓣的。 然后在一处无
8、人问津的小岛上总是下着三瓣的雪。 每瓣雪花都有重量。重量在 1 到 1000 之间。 两片雪花如果每瓣重量一一对应,便是相同。(可以转和翻转) 你处在上帝的视角看雪,计算有多少不同的雪花。 数据输入 第一行为一整数 N。代表雪花数量。(1a0*1000*1000+t-a1*1000+t-a2)%10001; if(Thash=NULL) Thash=t; return 0; table pre,temp=Thash; while(temp!=NULL) if(temp-a0=t-a0 pre=temp; temp=temp-next; if(pre-next=temp)pre-next=t;
9、/temp=t; return 0; int main() int sum=0; int n; int i; scanf(“%d“, for(i=0;inext=NULL; scanf(“%d %d %d“, sort(t-a); if(!isEqual(t) sum+; printf(“%dn“,sum); return 0; /* 4 1 2 3 2 3 1 3 1 2 1 1 1 */ 算法与数据结构题 实验题 10.4文件名统计 实验任务 摩根手里有不超过 10000 个文件,他每天都会使用某些文件,并记录这个文件名,文 件名为小写英文字母。现在他一共记录了 n 个文件名,他想知道每个
10、文件被使用的概率是 多少。 数据输入 第一行输入一个整数 n(0son*s-a=NULL) tire temp=(tire)malloc(sizeof(TireTree); for(i=0;isoni=NULL; temp-count=0; p-son*s-a=temp; p=p-son*s-a; else p=p-son*s-a; s+; p-count+; strcpy(p-c,ch); void printMessage(tire t,int n) for(int i=0;isoni!=NULL) if(t-soni-count) printf(“%s %.4lfn“,t-soni-c,
11、(double)t-soni-count/n); /else printMessage(t-soni,n); / int main() int n; int i,j; char ch30; tire t=(tire)malloc(sizeof(TireTree); for(i=0;isoni=NULL; t-count=0; scanf(“%d“, for(i=0;i1;i-) temp(sum1,sumi); n-; Max_Heapify(sum,1,n); summ+1=-1; int count=0; for(i=1;i把边反向-dj*/ int N,M,P,result=-1,fla
12、g=0; int dist10012; int a10011001; int prev1001=0; link newnode(int x) link p=(link)malloc(sizeof(NODE); p-e=x; p-next=0; return p; link first=0; void insert(int x) if(first) link p=newnode(x); link q=first-next; p-next=q; first-next=p; else first=newnode(x); int delmin(void) int x; link p=first,q=p
13、-next,t=p,r=t; if(first-next=0) x=first-e; first=0; return x; while(q) if(distq-eflageflag)t=p;r=q; p=q; q=q-next; if(t=r)first=r-next; else t-next=r-next; x=r-e; return x; void dj(void) int i,j; for(i=1;i=N;i+) distiflag=aPi; if(distiflag!=-1) previ=P; insert(i); distPflag=0; while(first) i=delmin(
14、); for(j=1;jdistiflag+aij) distjflag=distiflag+aij; if(!prevj)insert(j); prevj=i; void djb(void) int i,j; for(i=1;i=N;i+) distiflag=aiP; if(distiflag!=-1) previ=P; insert(i); distPflag=0; while(first) i=delmin(); for(j=1;jdistiflag+aji) distjflag=distiflag+aji; if(!prevj)insert(j); prevj=i; int main(void) int x,y,z,i,j; scanf(“%d%d%d“, memset(a,-1,sizeof(a); for(i=1;iz)axy= z; dj(); flag+; memset(prev,0,sizeof(prev); first=0; djb(); for(i=1;iresult printf(“%d“,result); return 0;