输入
计算逆序值
稳定排序
代码:
#include <stdio.h>#include <string.h>
typedef struct
{
char arr[51]
int v
}ARR
int main()
{
ARR list[100]
ARR t
int n,l,i,j,k
scanf("%d%d", &l, &n)
for(i = 0 i < n i ++)
{
scanf("%s", list[i].arr)
list[i].v = 0
for(j = 0 j < l - 1 j ++)
{
for(k = j + 1 k < l k ++)
if(list[i].arr[k] < list[i].arr[j])
list[i].v ++
}
}
for (i = 0 i < n i++)
{
for (j = n - 1 j > i j--)
{
if (list[j].v < list[j-1].v)
{
memcpy(&t, &list[j-1], sizeof t)
memcpy(&list[j-1], &list[j], sizeof t)
memcpy(&list[j], &t, sizeof t)
}
}
}
for(i = 0 i < n i ++)
printf("%s\n", list[i].arr)
return 0
}
供参考
是否有问题? 有问题请追问 没问题请采纳
没用C写,用python写的,道理都一样。
def generate(n): //n为长度for i in range(4**n):
a=[0 for i in range(n)] //a为长度为n的一个序列
num = i
z = 0
while(num!=0):
a[z]=num%4
z = z+1
num = int(num/4)
for j in a:
if j==0:
print('A',end="")
elif j==1:
print('T',end="")
elif j==2:
print('G',end="")
else:
print('C',end="")
print()
原理就是四进制转换。
当调用函数generate(2),产生结果AA,TA,GA,CA,AT,TT,GT,CT,AG,TG,GG,CG,AC,TC,GC,CC
后缀数组或者后缀树如果你不知道这两个是什么东西,建议先去搜点资料来看看。。。除了这两个东西我没想到什么比较好的方法
用比较直观的后缀树为例,假设树中某一节点u对应的字符串为s,深度为d,以u为根的子树包含了k个叶子节点,那么在原先的字符串里面,就找到了一个长度为d的字符串s恰好出现了k次
后缀树建立可以用Ukkonen算法,建立以后把整棵树遍历一下就可以了
整个过程都是比较直观的,就是编码太麻烦
而且你要求用c语言,粗略估计大概300行以上
或者你用线性的算法生成一个后缀数组,然后比较相邻两个后缀的lcp,找出最大的那个就是了
后缀数组的线性时间构造貌似也是个比较复杂的东西
总之代码较长,内容比较专业,不建议你在这里问
最好自己去找找相关资料