练习友元函数，有元类，快排和全排列问题

写了一小段代码：

练习一下友元类和友元函数的声明和使用；
练习一下最简单的快排算法；
练习一下递归的方法处理全排列问题。

代码：

  1 #include <stdlib.h>
  2 #include <string>
  3 
  4 class Something;
  5 
  6 // 友元函数可以提前在类外定义，也可以不这么做
  7 int get_data(Something& sth);
  8 
  9 class Otherthing;
 10 class Something
 11 {
 12 private:
 13     int data;
 14 
 15     // 友元类定义的位置在private,public,protected都可以
 16     // 友元类实现的位置在类内和类外都可以
 17     friend Otherthing;
 18 
 19     // 友元函数定义的位置在private,public,protected都可以
 20     // 友元函数实现的位置在类内和类外都可以
 21     // 即使在类内定义，也是全局可访问
 22     friend int get_data(Something& sth)
 23     {
 24         return sth.data;
 25     }
 26 public:
 27     void set_data(int v)
 28     {
 29         data = v;
 30     }
 31 };
 32 
 33 class Otherthing
 34 {
 35 public:
 36     int get_data(Something& sth)
 37     {
 38         return sth.data;
 39     }
 40 };
 41 
 42 // 交换
 43 void swap(int* p, int* q)
 44 {
 45     if(p == q)
 46         return;
 47     int tmp = *p;
 48     *p = *q;
 49     *q = tmp;
 50 }
 51 
 52 // 打印
 53 void print_array(int* begin, int* end)
 54 {
 55     while(begin < end)
 56         printf("%d ", *begin++);
 57     printf("
");
 58 }
 59 
 60 // 快排
 61 void quick_sort(int* begin, int* end)
 62 {
 63     if(end - begin <= 1)
 64         return;
 65 
 66     // 定义两个迭代器
 67     int* p = begin+1, * q = end-1;
 68 
 69     // 采用最常规的，选第一个元素作为中枢点的方法
 70     while(p < q)
 71     {
 72         while(p < q && *p <= *begin)    // 后移p
 73             p++;
 74         while(p < q && *q > *begin)        // 前移q
 75             q--;
 76         swap(p, q);                        // 交换p,q
 77     }
 78 
 79     // 比较中枢位置的元素和第一个元素，若逆序，则交换
 80     if(*p < *begin)
 81         swap(p, begin);
 82 
 83     // 递归调用
 84     quick_sort(begin, p);
 85     quick_sort(p, end);
 86 }
 87 
 88 void full_permutation(const char* str, char* aux, int* num, int cur, const int n)
 89 {
 90     if(n == cur)
 91     {
 92         printf("%s
", aux);
 93     }
 94     for(int i = 0; i < n; i++)
 95     {
 96         if(0 == num[i])            // 如果第i个字符还没有被用过
 97         {
 98             num[i] = 1;            // 标志设为1，表示该字符不能在 “后面的递归中” 再次被使用
 99             aux[cur] = str[i];    // 在cur位置使用第i个字符
100             full_permutation(str, aux, num, cur+1, n);
101             num[i] = 0;            // 清空标志，使该字符在 “迭代之后的递归中” 可以被使用
102         }
103     }
104 }
105 
106 void full_permutation_aux(const char* str)
107 {
108     int n = strlen(str);
109     char* aux = new char[n+1];
110     memset(aux, 0, (n+1)*sizeof(char));
111     int* num = new int[n];
112     memset(num, 0, n*sizeof(int));
113     full_permutation(str, aux, num, 0, n);
114 }
115 
116 int _tmain(int argc, _TCHAR* argv[])
117 {
118     // 练习友元函数和有元类
119     Something sth;
120     sth.set_data(10);
121     printf("%d
", get_data(sth));
122     Otherthing oth;
123     printf("%d
", oth.get_data(sth));
124 
125     // 练习快排
126     int array[] = {6, 12, 45, 12, 78, 3, 9, 1, 89, 12, 34, 8, 18, 15};
127     int len = sizeof(array)/sizeof(int);
128     int* begin = array;
129     int* end = array + len;
130     quick_sort(begin, end);    
131     print_array(begin, end);
132 
133     // 练习全排列
134     const char* str = "ABCD";
135     full_permutation_aux(str);
136 
137     system("pause");
138     return 0;
139 }

输出结果：

10
10
1 3 6 8 9 12 12 12 15 18 34 45 78 89
ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA
请按任意键继续. . .