字符串按规则排序算法
/blog/1723707
写这个东西源自于公司组织的一次编程道场，最后的总结就是，尽量使用既有的库，将问题转化为既有库算法能解决的问题，可读性第一，效率第二。老大们说的话总是让人觉得醍醐灌顶，不要自己实现一个功能为了去榨取那么一点点性能，最终还不一定能榨出来！不知道有没有什么特别的原因，最后几位老大展示出的代码竟然一模一样，虽然语言不同，那就像直接的翻译一般，难道编程有其道，而老大们均掌握了“道”？
我也想出了那种“标准的做法”，只是我根本不会用什么库，也根本不了解库，虽然有了伪代码，然而在将其转化为C代码的时候，遇到了无法突破的障碍，因为我根本不知道map或者vector之类的，更别提STL了，我除了知道点C++的一点语法之外，其它的什么都不知道…有时候，我认为我根本不是一个程序员，而是一个网管。
字符串长度排序我没有什么技巧可炫，也没有库使用的知识可以利用，只好从零开始用标准C来实现了，虽然效率不一定很高，可读性方面也可能只有我自己能看懂，然而不管怎么说，实现了，而且所有
的时间复杂度是可控的，因为整个代码没有掉进任何的库实现的算法黑洞，比如如果你不知道你所使用的sort是怎么实现的，那么它的时间复杂度就是不可控的。
问题是这样的：按照下列规则排序字符串数组
1.F一定出现在最前面；
2.L一定出现在最后面；
3.B一定要在A前面；
4.所有相同的字符串必须放在一起。
实际上再抽象一点就是，输入字符串是无序的，但是要确保输出是有序的。正常的思路就是将字符串的规则键转化为一个数字，然后进行数字排序，然而要处理字符串和索引的关系，这个如果不使用库里面的ADT还真麻烦，于是换一种思路，在扫描字符串的过程中就将其各归其位，各归其位的含义就是根据规则的优先级顺序到自己的位置，那么二叉树是一个理想的选择。
现在最关键的就是写一个getprio函数以及一个compare函数，而这个是很好办的。getprio函数的逻辑决定了最终的排序结果，这个函数可以做的很复杂，也可以很简单，比如为了能实现不感兴趣的字符串按照自然顺序输出，并且相同的排在一起这样的需求，可以为getprio函数保存一个容器，保存所有已经匹配到的不感兴趣的字符串的prio值。
以下是全部的代码：
Cpp代码
1.#include <stdio.h>
2.#include <stdlib.h>
3.#define MAX 32
4.
5.//一个字符串链表，保存相同的prio的字符串
6.struct string_list {
7.char *str;
8.struct string_list *next;
9.};
10.//一个字符串包装，携带了一个prio
11.struct string_wrap {
12.char *string;
13.int prio;
14.};
15.//最终决定字符串位置的二叉树
16.struct string_node {
17.struct string_list *string;
18.struct string_list *last;
19.int prio;
20.struct string_node *left;
21.struct string_node *right;
22.};
23.//声明要使用的函数
24.struct string_node *add_node(struct string_node *, struct string_wrap *str, int (*cmp)(struct string_wrap *, struct string_node *));
25.void print_result(struct string_node *);
26.//比较函数，比较优先级
27.int normalcmp(struct string_wrap *n1, struct string_node *n2)
28.{
29.return n1->prio - n2->prio;
30.}
31.//getprio函数，根据规则返回优先级
32.int getprio(char *s, int thread)
33.{
34.static int prio = 1;
35.if (!strcmp(s, "F"))
36.return 0;
37.if (!strcmp(s, "L"))
38.return 100;
39.if (!strcmp(s, "B"))
40.return 50;
41.if (!strcmp(s, "A"))
42.return 51;
43.//如果希望不想关的字符串按照输入顺序输出，则放开下面的注释
44.//如果只是return prio++，那么字符串将按照原始顺序输出
45.//return prio++;
46.//返回自然顺序，和上面注释的意义一样
47.return thread;
48.}
49.
50.int main(int argc, char **argv)
51.{
52.struct string_node *root;
53.int thread = 0;
54.char string[MAX];
55.char *str[40] = {"L","F","A","dsfsfsg","L","B","A", "ss", "A"};
56.
57.root = NULL;
58.int i = 0;
59.while (str[i]) {
60.int prio = getprio(str[i], ++thread);
61.struct string_wrap sw = {str[i], prio};
62.root = add_node(root, &sw, normalcmp);
63.i ++;
64.}
65.print_result(root);
66.return 0;
67.}
68.//标准的二叉树插入
69.struct string_node *add_node(struct string_node *p, struct string_wrap *new, int (*cmp)(struct string_wrap *n1, struct string_node *n2))
70.{
71.int cmp_ret;
72.
73.if (p == NULL) {
74.p = (struct string_node *)malloc(sizeof(struct string_node));
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论