2015年黑龙江省数据理论纲要
1、题目中要求矩阵两行元素的平均值按递增顺序排序，由于每行元素个数相等，按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和，放入一维数组中，然后选择一种排序方法，对该数组进行排序，注意在排序时若有元素移动，则与之相应的行中各元素也必须做相应变动。
void Translation（float *matrix，int n）
//本算法对n×n的矩阵matrix，通过行变换，使其各行元素的平均值按递增排列。 {int i,j,k,l；
float sum，min； //sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i<n; i++)
{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.
for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.
*(p+i)=sum; //将一行元素之和存入一维数组.
}//for i
for(i=0; i<n-1; i++) //用选择法对数组p进行排序
{min=*(p+i); k=i; //初始设第i行元素之和最小.
for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号. if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和) {pk=matrix+n*k; //pk指向第k行第1个元素.
pi=matrix+n*i; //pi指向第i行第1个元素.
for(j=0;j<n;j++) //交换两行中对应元素.
{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}
sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.
}//if
}//for i
free(p); //释放p数组.
}// Translation
[算法分析] 算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).
2、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
(1) (3分)给出适用于计数排序的数据表定义;
(2) (7分)使用Pascal或C语言编写实现计数排序的算法；
(3) (4分)对于有n个记录的表，关键码比较次数是多少?
(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法，模拟此过程。
2015年黑龙江省数据理论纲要
#include<stdlib.h>
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/ { p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点，并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n<1) printf("n<0");
else
2015年黑龙江省数据理论纲要
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/ head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(linklist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*
jose(head,s,m); /*
}
}
生成循环链表*/ 调用函数*/