数据结构习题

数据结构与算法实验题2.3 大家一起来报数Ⅱ ★实验任务

编号为 1 - n 的 n 个人按顺时针方向围坐一圈，从第一个人开始按顺时针方向自 1 开 始报数，报到 m 时停止，在报到 m 的那个人的左右的两个人出列，从他在顺时针方向下一

个人开始重新从 1 报数，如此下去。如果还在游戏的人数少于 3 个，则游戏终止。在一行 内输出最后留下来的人编号 ★数据输入

输入第一行为 T ，代表接下去有 T 组测试， 0 < T < =10 接下去 T行，每行两个数代表 n 和m，0 < n，m < =1000 ★数据输出

对于每个输入，在一行内输出最后留下来的人编号，如果有两个人留下来，则用空格隔 开，并按从小到大排序。 输入示例 输出示例 3 1 2 3 1 4 2 1 1 2 4

#include #include

typedef struct LinkedList* List; struct LinkedList { List right; List left; int n; };

List creatList(int peopleNum) { List mainList; List leftList; List headList; headList=mainList=leftList=NULL; for(int i=1;i<=peopleNum;i++) { leftList=(List)malloc(sizeof(LinkedList)); leftList->n=i; if(mainList==NULL){ mainList=headList=leftList; } else {

mainList->left=leftList; leftList->right=mainList; mainList=leftList; } } mainList->left=headList; headList->right=mainList; return headList; }

void searchList(List mainList,int n,int m) { while(n>2) { 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; } if(n==1) printf(\ else

printf(\ (mainList->n)<(mainList->left->n)?(mainList->left->n):(mainList->n)); }

int main() { int m,n; int num; scanf(\ while(num--){ scanf(\ List list;

list=creatList(n); searchList(list->right,n,m); } }

数据结构与算法实验题3.3 价值问题 ★实验任务

小明最近在好或者坏的天气如何影响人们的心情，他发现，在给定的一段日子里，人的价值 可以通过一段时间内最坏的那天的心情等级（可以有多天）乘上这段时间心情等级的总和得 到（心情等级越小，心情越坏），于是他想请你帮忙计算一下给定 N 天里面，在连续一段 时间里他可能的价值最高。 ★数据输入

第一行为总天数 N（1<=N<=100000）。

第二行为 N 个正整数，为小明每天的心情等级（1<=a[i]<=100000）。 ★数据输出

输出小明在连续一段时间内可能的最高价值 W。 输入示例 输出示例 6

3 1 6 4 5 2 60

#include

int main() { int n; int i,j,k; int a[100001]={0}; int sum[100001]={0}; scanf(\ for(i=1;i<=n;i++) { scanf(\ sum[i]=sum[i-1]+a[i]; } __int64 max=0; for(i=1;i<=n;i++) { __int64 min=a[i]; if(min!=a[i-1]){ int signS=i-1; int signE=i; for(k=i;k>=0;k--) { if(a[k]

{ signS=k; break; } } for(j=i;j<=n+1;j++) { if(a[j]temp?max:temp; } } printf(\}

算法与 数据结构题 实验题 12.4 道路 ★ 实验任务

某省调查城镇交通状况，得到现有城镇道路统计表，现给出每条道路连接的城 镇编号，问当前的道路设计方案是否合理。

合理的方案为任意两个城镇之间可以相互到达，有且只有一条通路。 ★ 数据输入

输入 a b(1<=a,b<=10,000)，表示城镇 a 和城镇 b 连通。输入包含多组数据，每 组数据以 0 0 结束。 整个文件以-1 -1 结尾 ★ 数据输出

如果方案合法，输出\否则输出\。 输入示例 输出示例 6 8 5 3 5 2 6 4 5 6 0 0 8 1 7 3 6 2 8 9 7 5 7 4 7 8 7 6 0 0

3 8 6 8 6 4 5 3 5 6 5 2 0 0

1 2 3 4 0 0 -1 -1 Yes Yes No No

#include

#include #define MAX 10002 typedef struct Union* U; struct Union{ int value; int sign; }; U u; int v=0; int len=0;

int findValue(int n){ return u[n].value; }

void connect(int a,int b){ int va=findValue(a); int vb=findValue(b); if(va==vb) return; for(int i=0;i<=len;i++){ if(u[i].value==vb){ v=va; u[i].value=va; } } }

int main(){ while(1){ int a,b; int i,j; int s=1; u=(U)malloc(MAX*sizeof(Union)); for(i=0;ia?len:a; len=len>b?len:b; if(u[a].sign==1&&u[b].sign==1){ if(u[a].value==u[b].value) s=0; }