C++求数组的全排列之字典序法

概述C++求数组的全排列之字典序法

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

字典序法说明：
字典序列算法是一种非递归算法。而它正是STL中Next_permutation的实现算法。
它的整体思想是让排列成为可递推的数列，也就是说从前一状态的排列，可以推出一种新的状态，直到最终状态。比如说，最初状态是12345，最终状态是54321。
1.最初状态为12345，从最后面向前面比较，因为5>4,所以从4后面的序列中找出一个比4大，但是比在4后面的序列中最小的数，因为只有5，所有将4和5调换位置，结果为12354.
2.将原来4后面的序列进行倒置，因为现在只有1个4，倒置后还是12354.
3.已12354为基础，继续上面的步骤进行 *** 作，下一序列的生成步骤如下：
12354(5>3) -> 12354(4,5序列中最小但是比3大的是4) -> 12453(调换4和3) -> 12435（将5,3倒置）

#include <stdio.h>#include <ctype.h>#include <malloc.h> static voID swapNum(int i,int j,int* intArray,int num);static int getSmallestButGreatThanIndex(int* intArray,int num,int i);static voID invertIntArray(int i,int num);static voID prtIntArray(int* intArray,int num); int main(int argc,char* argv[]){    int num = 0;    int* intArray = NulL;    int i = 0;    int j = 0;         //检查参数，必须是2个    if(argc != 2){        printf("there must be one parameter!\n");        goto FINALLY;    }         //检查参数，参数必须是数字    char* ptr = argv[1];    while(*ptr != ''){        if(isdigit(*(ptr++)) == 0){            printf("please input a numble!\n");            goto FINALLY;        }    }         //将参数转换成int型    num = atoi(argv[1]);    intArray = (int*)malloc(sizeof(int) * num);    //初始化数组:1,2,3,4,5,6......    for(i=0; i<num; i++){        intArray[i] = i+1;    }         //打印下原始数组    printIntArray(intArray,num);    //从数组最后面往前比较    for(i=num-1,j=num-2; i>=1 && j>=0; i--,j--){        //如果右边数的比左边数的大        if(intArray[i] > intArray[j]){            //将左边的数与右边数组中最小但是比左边的数大的数交换            swapNum(i,j,intArray,num);            //将左边数右边的数组序列倒置            invertIntArray(i,num);            //将整个数组打印            printIntArray(intArray,num);            //继续从数组的最后面往前面比较            i = num;            j = num - 1;        }    }     FINALLY:    if(intArray != NulL){        free(intArray);        intArray = NulL;        }    return 0;} static voID swapNum(int i,int num){    int swAPI = getSmallestButGreatThanIndex(intArray,num,i);    int temp = intArray[j];    intArray[j] = intArray[swAPI];    intArray[swAPI] = temp;} static int getSmallestButGreatThanIndex(int* intArray,int i){    int m = 0;    int swAPI = 0;    int smallest = num + 1;    for(m = i; m<num; m++){        if(intArray[m] > intArray[j] && intArray[m] < smallest){            swAPI = m;            smallest = intArray[m];        }    }    return swAPI;} static voID invertIntArray(int i,int num){    int m;    int n;    int temp;    for(m=i,n=num-1; (m-n)<0; m++,n--){        temp = intArray[m];        intArray[m] = intArray[n];        intArray[n] = temp;    }} static voID printIntArray(int* intArray,int num){    int i;    for(i=0; i<num; i++){        printf("%d ",intArray[i]);    }    printf("\n");} 

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C++求数组的全排列之字典序法全部内容，希望文章能够帮你解决C++求数组的全排列之字典序法所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。