smwt[2].self = &smwt[2];
smwt[2].tag = 3;
smwt[3].sorted_order_str =smwt[3].normal_order_str= "823";
smwt[3].self = &smwt[3];
smwt[3].tag = 4;
smwt[4].sorted_order_str =smwt[4].normal_order_str= "123";
smwt[4].self = &smwt[4];
smwt[4].tag = 5;
smwt[5].sorted_order_str =smwt[5].normal_order_str= "423";
smwt[5].self = &smwt[5];
smwt[5].tag = 6;
smwt[6].sorted_order_str =smwt[6].normal_order_str= "123";
smwt[6].self = &smwt[6];
smwt[6].tag = 7;
smwt[7].sorted_order_str =smwt[7].normal_order_str= "723";
smwt[7].self = &smwt[7];
smwt[7].tag = 8;
smwt[8].sorted_order_str = smwt[8].normal_order_str="523";
smwt[8].self = &smwt[8];
smwt[8].tag = 9;
smwt[9].sorted_order_str =smwt[9].normal_order_str= "823";
smwt[9].self = &smwt[9];
smwt[9].tag = 10;
sort(smwt, 10, cmp_node, swap_node);
//下面使用了最恶心的输出，经典###
for (i = 0; i< 10; i++) {
printf("###:%s tag:%d\n", smwt[i].normal_order_str, smwt[i].tag);
}
for (i = 0; i< 10; i++) {
printf("@@@:%s tag:%d\n", smwt[i].sorted_order_str, smwt[i].tag);
}
for (i = 0; i< 10; i++) {
if (smwt[i].tag != 0){
printf("@@@&&:%s\n", smwt[i].normal_order_str);
}
}
return 0;
}
下面的一种方法使用了标准的二叉树插入，注意，插入仅仅是为了删除重复元素，实际上，各种语言各种库的标准Map实现很多也是使用了树，比如java.util中的TreeMap就是使用了红黑树。下面直接给出代码，基于排序二叉树的代码：
//
// main.c
// test-xcode
//
// Created by ya zhao on 11-12-17.
// Copyright 2011年 __MyCompanyName__. All rights reserved.
//
#include
#include
#include
struct string_node {
char *string;
int tag; //标示是否被删除
};
//标准排序二叉树
struct string_tree {
struct string_node *strn;
struct string_tree* left,*right;
};
struct string_tree *add_node(struct string_tree *, struct string_node *str, int (*cmp)(struct string_node *, struct string_node *));
int normalcmp(struct string_node *, struct string_node *);
//简单的字符串比较
int normalcmp(struct string_node *n1, struct string_node *n2)
{
return strcmp (n1->string,n2->string);
}
int main(int argc, char **argv)
{
int j = 0;
for (j = 0; j < 1; j++) {
struct string_tree *root;
struct string_node str[9] = {{"123",1},{"456",1},{"234",1},{"123",1},{"347",1},{"129",1},{"888",1}, {"568",1}, {"456",1}};
root = NULL;
int i = 0;
while (i<9) {
root = add_node(root, &str[i], normalcmp);
i ++;
}
i=0;
while (i<9){
if (str[i].tag) {
printf("&&&:%s\n", str[i].string);
}
i++;
}
}
return 0;
}
struct string_tree *add_node(struct string_tree *p, struct string_node *new, int (*cmp)(struct string_node *n1, struct string_node *n2))
{
int cmp_ret;
if (p == NULL) {
p = (struct string_tree *)calloc(1, sizeof(struct string_tree));
p->strn = (struct string_node*)calloc(1, sizeof(struct string_node));
memcpy(p->strn, new, sizeof(struct string_node));
p->left = p->right = NULL;
} else if ((cmp_ret = cmp(new, p->strn)) == 0) {
new->tag =0;
} else if (cmp_ret < 0) {
p->left = add_node(p->left, new, cmp);
} else {
p->right = add_node(p->right, new, cmp);
}
return p;
}
经过测试，自己实现的上述算法效率还可以，当然这里不该去比较效率，留下个思路即可，在没有库可用的情况下，也可以自己实现它。在现实中，特别是在软件工程中，还是使用现成的map比较好
摘自 黎明