字典序

一.字典序基础

字典序（dictionary order），又称 字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成两个任意字符串的大小关系。

英文中的 字母表（Alphabet） 按照如下的顺序排列：

ABCDEFG HIJKLMN OPQRST UVWXYZ

abcdefg hijklmn opqrst uvwxyz

在字典中，单词是按照首字母在字母表中的顺序进行排列的，比如 alpha 在 beta 之前。而第一个字母相同时，会去比较两个单词的第二个字母在字母表中的顺序，比如 account 在 advanced 之前，以此类推。下列单词就是按照字典序进行排列的：

aster

astrolabe

astronomy

astrophysics

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

我们这里是通过字典序法找出来的。

那么什么是字典序法呢？

从上面的全排列也可以看出来了，从左往右依次增大，对这就是字典序法。可是如何用算法来实现字典序法全排列呢？

我们再来看一段文字描述：（用字典序法找的下一个排列）

如果当前排列是，找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数
如果找不到，则所有排列求解完成，如果找得到则说明排列未完成
本例中将找到46，计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数
本例找到的数是5，其位置计为j，将i与j所在元素交换
然后将i+1至最后一个元素从小到大排序得到，这就是的下一个排列

下图是用字典序法找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<<” 第 ”<

去掉重复符号的全排列：在交换之前可以先判断两个符号是否相同，不相同才交换，这个时候需要一个判断符号是否相同的函数。

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<<” 第 ”<

2.非递归版本

算法简述

要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如"1234"的下一个排列就是"1243"。只要对字符串反复求出下一个排列，全排列的也就迎刃而解了。

如何计算字符串的下一个排列了？来考虑""这个字符串，我们从后向前找第一双相邻的递增数字，"20"、"52"都是非递增的，"26 "即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到""，然后再将替换点后的字符串"6220"颠倒即得到""。

如果达到这个数的最大，比如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：

寻找最后一对递增数AB（25）
之后的最小但大于A的数与A调换（2&3）=>
之后的数反排（即从小到大排列）=>

例2：

字典序排序

字符

#include 
  
    #include 
   
     #include 
    
      #define M #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

字符串

#include 
  
    #include 
   
     #include 
    
      #include 
     
       #define M #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 
      
        >str[i]; sort(str, str+n, cmp); return 0; }

结构体：

#include 
  
    #include 
   
     #include 
    
      #define M #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

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199974.html原文链接：https://javaforall.net