一.字典序基础
字典序(dictionary order),又称 字母序(alphabetical order),原意是表示英文单词在字典中的先后顺序,在计算机领域中扩展成两个任意字符串的大小关系。
英文中的 字母表(Alphabet) 按照如下的顺序排列:
ABCDEFG HIJKLMN OPQRST UVWXYZ
abcdefg hijklmn opqrst uvwxyz
在字典中,单词是按照首字母在字母表中的顺序进行排列的,比如 alpha 在 beta 之前。而第一个字母相同时,会去比较两个单词的第二个字母在字母表中的顺序,比如 account 在 advanced 之前,以此类推。下列单词就是按照字典序进行排列的:
as
aster
astrolabe
astronomy
astrophysics
at
ataman
attack
baa
在计算机领域中,这个字典序就不仅仅用来比较英文单词了,而是比较任意字符串。对于两个字符串,大小关系取决于两个字符串从左到右第一个不同字符的 ASCII 值的大小关系。比如ah1x
小于ahb
,而Z5
小于a3
。下列字符串就是按照字典序进行排列的:
$
*(&%%#
,.23
234q
A2.532
ZZRWA23
\235
a/34
a423
h2ab`.
在绝大多数语言中,都提供了比较两个字符串大小的方法,比较的实际上就是两个字符串的字典序。例如在 C++ 语言 中:
cout << ("ah1x" < "ahb") << endl;
就会输出true
,而在 Java 语言 中:
System.out.println(“ah1x”.compareTo(“ahb”));
会输出 -49−49,这个数是两个字符串第一个不一样的位置的两个字符的 ASCII 值之差,如果小于零则说明第一个字符串小于第二个字符串。
除此之外,大多数语言也都有对应的字符串比较方法,而背后的核心都是字符串的字典序。理解并掌握这个重要的概念,对今后计算机专业课程的学习和程序开发
二.字典序算法相关
1.字典序全排列问题
示例:1 2 3
的全排列如下:
1 2 3 | 1 3 2 | 2 1 3 | 2 3 1 | 3 1 2 | 3 2 1
- 我们这里是通过字典序法找出来的。
那么什么是字典序法呢?
从上面的全排列也可以看出来了,从左往右依次增大,对这就是字典序法。可是如何用算法来实现字典序法全排列呢?
我们再来看一段文字描述:(用字典序法找124653
的下一个排列)
- 如果当前排列是
124653
,找它的下一个排列的方法是,从这个序列中从右至左找第一个左邻小于右邻的数 - 如果找不到,则所有排列求解完成,如果找得到则说明排列未完成
- 本例中将找到
46
,计4
所在的位置为i
,找到后不能直接将46
位置互换,而又要从右到左到第一个比4
大的数 - 本例找到的数是
5
,其位置计为j
,将i
与j
所在元素交换125643
- 然后将
i+1
至最后一个元素从小到大排序得到125346
,这就是124653
的下一个排列
下图是用字典序法找1 2 3
的全排列(全过程):
1、 递归版本
算法简述
简单地说:就是第一个数分别以后面的数进行交换
E.g:E = (a , b , c),则 prem(E)= a.perm(b,c)+ b.perm(a,c)+ c.perm(a,b)
然后a.perm(b,c)= ab.perm(c)+ ac.perm(b)= abc + acb.依次递归进行
Foo(const char *str)
{
Perm( str , 0 , strlen( str ) – 1 );
}
//需要三个参数,k表示当前的数,m表示数的个数
Perm( char *pszStr , int k , int m )
{
if (k == m)
{
static int s_i = 1;
cout<<” 第 ”<<s_i ++<<” 个排列 ”<<pszStr<<endl;
}
else
{
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
Swap(pszStr + k, pszStr + i);
Perm(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
去掉重复符号的全排列:在交换之前可以先判断两个符号是否相同,不相同才交换,这个时候需要一个判断符号是否相同的函数。
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
for (int i = nBegin; i < nEnd; i++)
if (pszStr[i] == pszStr[nEnd])
return false;
return true;
}
Perm(char *pszStr, int k, int m)
{
if (k == m)
{
Static int s_i = 1;
cout<<” 第 ”<<s_i ++<<” 个排列 ”<<pszStr<<endl;
}
else
{
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
if (IsSwap(pszStr, k, i)) //添加的判断语句,判断是否相等
{
Swap(pszStr + k, pszStr + i);
Perm(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
}
2.非递归版本
算法简述
要考虑全排列的非递归实现,先来考虑如何计算字符串的下一个排列。如”1234″的下一个排列就是”1243″。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。
如何计算字符串的下一个排列了?来考虑”926520″这个字符串,我们从后向前找第一双相邻的递增数字,”20″、”52″都是非递增的,”26 “即满足要求,称前一个数字2为替换数,替换数的下标称为替换点,再从后面找一个比替换数大的最小数(这个数必然存在),0、2都不行,5可以,将5和2交换得到”956220″,然后再将替换点后的字符串”6220″颠倒即得到”950226″。
如果达到这个数的最大,比如1234-à4321,这个时候就结束整个循环。
如果输入是一个非最小数,如1324,则将它转换为最小数,如1234,再进行排序。排序算法用快排,可以自己写一个,如果快排不会的话,就先看会再来接着看,或者自己想一个靠谱的算法,也可以直接用VC库中的qsort(s , n , sizeof(s[0]) , cmp);各参数是什么意思就自己在下面多花点时间吧。
Prem( char *s ) //全排列函数
{
char *pEnd = s + strlen(s) - 1;
char *p = pEnd; //p代表替换点
//q代表替换点的下一个数 ,pMax 代表替换点后比替换点大的最小数
char *q = new char,*pMax = new char; //注意初始化!!!
while (p != s) //p == s 就结束循环
{
q = p;
p--;
if (*p < *q)
{
pMax = FindMaxForOne(p,pEnd); //找与替换点交换的点
Swap(p,pMax); //交换
Reverse(q,pEnd); //将替换点后所有数进行反转
Print(s); //输出
p = pEnd; //将替换点置最后一个点,开始下一轮循环
}
if (s == p) break; //结束条件
}
}
char* FindMaxForOne(char *p,char *q)
{
char *p1 = p;
char *p2 = q;
while (*p2 <= *p1) p2--;
return p2;
}
二、字典序排序
例1:
exp:
6125431
按照字典序,下一个数是哪个?
- 寻找最后一对递增数AB(25)
- 之后的最小但大于A的数与A调换(2&3)=>6135421
- 之后的数反排(即从小到大排列)=>6131245
例2:
字典序排序
字符
#include<algorithm>
#include<cstring>
#include<cstdio>
#define M 100000
#define len 22
using namespace std;
char str[M][len];
int cmp1(const void *a,const void*b){
char *s1=(char *)a;
char *s2=(char *)b;
return strcmp(s1,s2);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%s",str[i]);
qsort(str,n,sizeof(char)*len,cmp1);
for()
return 0;
}
字符串
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#define M 100000
#define len 22
using namespace std;
string str[1005];
int cmp(string a,string b)
{
return a.compare(b)<0;
}
int main()
{
int n;
scanf("%d", &n);
for (int i=0; i<n; i++)
cin>>str[i];
sort(str, str+n, cmp);
return 0;
}
结构体:
#include<algorithm>
#include<cstring>
#include<cstdio>
#define M 100000
#define len 22
using namespace std;
struct Word{
char str[len];
}word[M];
int cmp(Word a,Word b)
{
return strcmp(a.str, b.str)>0;
}
int main()
{
int n;
scanf("%d", &n);
for (int i=0; i<n; i++)
scanf("%s", word[i].str);
sort(word, word+n, cmp);
return 0;
}
今天的文章字典序_字典序最小是什么意思[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:http://bianchenghao.cn/77273.html