主题:比较静态表和动态表:二叉顺序树的 ASL(Average Search Length)和时间复杂度 O(f(n))
Binary Search 二分查找(折半查找)
适用:顺序表
效率:O(log2(n))
算法示例:http://www.cnblogs.com/xwdreamer/archive/2012/05/07/2487246.html
程序实例:http://www.cnblogs.com/yu-chao/archive/2012/03/23/2413686.html
代码:
1 /*
2
3 目的:掌握折半查找、二叉查找树的插入与查找算法
4
5 要求:针对输入文件 dict.txt (其中每一行为一个英文单词),网络地址:http://202.113.29.10/class/ds12/dict.txt
6
7 1、请尝试编写折半查找算法,对每个单词进行查找,统计平均的比较次数;
8
9 2、请尝试随机排列其中的单词,如果你不知道怎么做,请看这里,如果你不会做,可以直接用这个dictr.txt;
10
11 3、对该随机单词序列,依次使用二叉排序树的插入算法插入建立二叉排序树,然后统计每个单词的平均查找长
12
13 */
14 #include<iostream>
15 #include<fstream>
16 #include<string>
17 #include<vector>
18 #include<time.h>
19 #include<iomanip>
20 using namespace std;
21 typedef vector<string>::size_type index;
22
23 class Static_Search_Table
24 {
25 private:
26 vector<string> dict;
27 index sum;
28 public:
29 Static_Search_Table();
30 ~Static_Search_Table();
31 long Bi_Search(int &pos,const string key);
32 string Element(int pos);
33 void Performance_Analysis();
34 void Traverse();
35 };
36 Static_Search_Table::Static_Search_Table()
37 {
38 fstream read_dict("d:\\mydir\\dict.txt",ios::in);
39 if(read_dict.fail())
40 {cerr<<"open failed!"<<endl;exit(1);}
41 string temp;
42 dict.push_back("xxx dict");
43 while(read_dict>>temp)
44 dict.push_back(temp);
45 sum=dict.size()-1;
46 cout<<"the whole number of word is:"<<sum<<endl;
47 read_dict.close();
48 }
49 Static_Search_Table::~Static_Search_Table()
50 {
51 cout<<"mission completed!"<<endl;
52 system("pause");
53 }
54 /*
55 二分查找又称折半查找,
56 优点:比较次数少,查找速度快,平均性能好
57 缺点:要求待查表为有序表,且插入删除困难
58 方法:
59 1.确定待查记录区间
60 2.缩小范围
61 环境:
62 dict.txt是字典顺序,按string类的比较操作符是增序排列
63 停止条件:
64 1.查找成功
65 2.待查区间长度为0且查找失败
66 */
67 long Static_Search_Table::Bi_Search(int &pos,const string key)
68 {
69 int beg,end,mid;
70 long num;
71 beg=1;end=sum;num=0;
72 while(beg<=end)
73 {
74 mid=(beg+end)/2;
75 if(dict[mid]==key)
76 {pos=mid;++num;end-=sum;}
77 else
78 if(dict[mid]<key)
79 {end=mid-1;++num;}
80 else
81 {beg=mid+1;++num;}
82 }
83 return num;
84 }
85 string Static_Search_Table::Element(int pos)
86 {
87 return dict[pos];
88 };
89 /*
90 性能分析模块:performance analysis
91 查找性能用ASL(Average Search Length)衡量:ASL越小,性能越好
92 */
93 void Static_Search_Table::Performance_Analysis()
94 {
95 int temp,j=0;
96 long SSL=0;
97 double ASL;
98 for(index i=1;i<dict.size();++i)
99 SSL+=Bi_Search(temp,dict[i]);
100 ASL=double(SSL)/double(sum);
101 cout<<"ASL:"<<ASL<<endl;
102 }
103 void Static_Search_Table::Traverse()
104 {
105 fstream traverse("d:\\mydir\\Traverse.txt",ios::out|ios::trunc);
106 if(traverse.fail())
107 {cerr<<"open failed!"<<endl;exit(1);}
108 for(index i=1;i<sum;++i)
109 traverse<<dict[i]<<endl;
110 traverse.close();
111 }
112
113 int main()
114 {
115 clock_t start,finish,duration;
116 Static_Search_Table SST;
117 start=clock();
118 SST.Performance_Analysis();
119 finish=clock();
120 cout<<"the precise time is:"<<finish-start<<endl;
121 duration=(finish-start)/CLOCKS_PER_SEC;
122 cout<<"the whole time is:"<<duration<<"s"<<endl;
123 system("pause");
124 return 0;
125 }
DisOrdered Dictionary 乱序字典生成:
置换:http://en.wikipedia.org/wiki/Random_permutation
随机数生成:http://www.cnblogs.com/longdouhzt/archive/2011/10/15/2213756.html
高效不重复随机数的生成:http://www.cppblog.com/sleepwom/archive/2010/01/13/105570.html
不重复随机数快速生成原理:有1—n总共n个正整数,利用随机置换生成排列。
循环从最后一个元素到第二个元素,记为 i 。
每次从0—(i-1)个元素中随机选取一个元素,与 i 做置换。
可用数学方法证明使用上述步骤生成的是一个随机序列
1 #include<iostream>
2 #include<fstream>
3 #include<vector>
4 #include<string>
5 #include<ctime>
6 using namespace std;
7
8 class DisOrdered
9 {
10 private:
11 vector<int> v;
12 vector<string> dict;
13 int sum;
14 public:
15 DisOrdered();
16 ~DisOrdered();
17 void Swap(int i,int j);
18 void Replacement();
19 };
20 DisOrdered::DisOrdered()
21 {
22 fstream read_dict("d:\\mydir\\dict.txt",ios::in);
23 if(read_dict.fail())
24 {cerr<<"open failed!"<<endl;exit(1);}
25 string temp;
26 while(read_dict>>temp)
27 dict.push_back(temp);
28 sum=dict.size();
29 read_dict.close();
30 for(int i=0;i<sum;++i)
31 v.push_back(i);
32 cout<<"init successfully!"<<endl;
33 }
34 DisOrdered::~DisOrdered()
35 {
36 cout<<"exit successfully!"<<endl;
37 }
38 void DisOrdered::Swap(int i,int j)
39 {
40 int temp;
41 temp=v[j];v[j]=v[i];v[i]=temp;
42 };
43 void DisOrdered::Replacement()
44 {
45 int i,j;
46 fstream write_dict_random("d:\\mydir\\dict_random.txt",ios::out|ios::trunc);
47 if(write_dict_random.fail())
48 {cerr<<"open failed!"<<endl;exit(1);}
49 srand((unsigned)time(0));
50 time_t beg,end,dur;
51 beg=clock();
52 for(i=sum-1;i>1;--i)
53 {
54 j=rand()%i;
55 Swap(i,j);
56 }
57 end=clock();
58 dur=end-beg;
59 cout<<"duration:"<<double(dur)/double(CLOCKS_PER_SEC)<<endl;
60 for(i=0;i<sum;++i)
61 write_dict_random<<dict[v[i]]<<endl;
62 write_dict_random.close();
63 }
64 int main()
65 {
66 DisOrdered DOdict;
67 DOdict.Replacement();
68 system("pause");
69 return 0;
70 }
Binary Sort Tree 二叉排序树(红黑树)
STL容器:sets container 和 multisets container 。
root:第一个输入的元素
left_child:小于双亲节点
right_child:大于双亲节点
关于sets:http://apps.hi.baidu.com/share/detail/18593242
http://www.cplusplus.com/reference/stl/set/
书目:《c++标准程序库:自修教程与参考手册》 华中科技大学出版社 侯捷/孟岩 6.5 sets 和 multisets Page:175-191
代码:
1 /*
2
3 本来想在这里尝试用sets容器构造二叉树
4
5 STL参考书上sets是以“红黑树”(即二叉排序树)方式实现,相对简单很多
6
7 但是考虑到要计算AVL,只好重编一个二叉排序树
8
9 */
10 #include<iostream>
11 #include<fstream>
12 #include<string>
13 #include<iomanip>
14 using namespace std;
15
16 typedef struct Binary_Tree_Node
17 {
18 string data;
19 Binary_Tree_Node *left_child,*right_child;
20 }BTN;
21
22 class Binary_Sort_Tree
23 {
24 private:
25 BTN root;
26 int sum;
27 public:
28 Binary_Sort_Tree();
29 ~Binary_Sort_Tree();
30 long Match(const string s);
31 void Performance_Analysis();
32 void Insert(const string s);
33 void Destroy(BTN *&p);
34 };
35 Binary_Sort_Tree::Binary_Sort_Tree()
36 {
37 fstream read_dictr("d:\\mydir\\dictr.txt",ios::in);
38 if(read_dictr.fail())
39 {cerr<<"init open failed!"<<endl;exit(1);}
40 string temp;
41 read_dictr>>root.data;
42 root.left_child=root.right_child=NULL;
43 while(read_dictr>>temp)
44 {
45 BTN *x=&root;
46 while(x!=NULL)
47 {
48 if(temp<x->data)
49 if(x->left_child!=NULL)
50 x=x->left_child;
51 else
52 {
53 x->left_child=new BTN;
54 x=x->left_child;
55 x->data=temp;
56 x->left_child=x->right_child=NULL;
57 x=NULL;
58 }
59 else
60 if(x->right_child!=NULL)
61 x=x->right_child;
62 else
63 {
64 x->right_child=new BTN;
65 x=x->right_child;
66 x->data=temp;
67 x->left_child=x->right_child=NULL;
68 x=NULL;
69 }
70 }
71 }
72 read_dictr.close();
73 }
74 long Binary_Sort_Tree::Match(const string s)
75 {
76 bool b=true;
77 long num=0;
78 BTN *x=&root;
79 while(b)
80 {
81 if(x->data==s)
82 {++num;b=false;}
83 if(x->data>s)
84 {x=x->left_child;++num;}
85 else
86 {x=x->right_child;++num;}
87 }
88 return num;
89 }
90 void Binary_Sort_Tree::Performance_Analysis()
91 {
92 fstream test("d:\\mydir\\dictr.txt",ios::in);
93 if(test.fail())
94 {cerr<<"open failed!"<<endl;exit(1);}
95 long sum=0,SSL=0;
96 double ASL;
97 string temp;
98 while(test>>temp)
99 {SSL+=Match(temp);++sum;}
100 ASL=double(SSL)/double(sum);
101 cout<<"sum:"<<sum<<endl;
102 cout<<"SSL:"<<SSL<<endl;
103 cout<<"ASL:"<<ASL<<endl;
104 test.close();
105 }
106 void Binary_Sort_Tree::Insert(const string s)
107 {
108 BTN *x=&root;
109 while(x!=NULL)
110 {
111 if(x->data==s)
112 {cerr<<"string:"<<s<<" has existed!"<<endl;return;}
113 if(s<x->data)
114 x=x->left_child;
115 else
116 x=x->right_child;
117 }
118 x=new BTN;
119 x->data=s;
120 x->left_child=x->right_child=NULL;
121 cout<<"insert successfully!"<<endl;
122 }
123 void Binary_Sort_Tree::Destroy(BTN *&p)
124 {
125 if(p)
126 {
127 Destroy(p->left_child);
128 Destroy(p->right_child);
129 delete p;
130 p=NULL;
131 }
132 }
133 Binary_Sort_Tree::~Binary_Sort_Tree()
134 {
135 BTN *x=&root;
136 Destroy(x->left_child);
137 Destroy(x->right_child);
138 }
139 int main()
140 {
141 clock_t start,finish,duration;
142 Binary_Sort_Tree BST;
143 start=clock();
144 BST.Performance_Analysis();
145 finish=clock();
146 cout<<"the precise time is:"<<finish-start<<endl;
147 duration=(finish-start)/CLOCKS_PER_SEC;
148 cout<<"the whole time is:"<<duration<<"s"<<endl;
149 system("pause");
150 return 0;
151 }
效率比较:
静态表查找速度:
ASL:16.4998
时间:1111ms
动态表查找速度:
ASL:21.3702
时间:1937ms
静态表查找速度较快
原文链接: https://www.cnblogs.com/kopanswer/archive/2012/06/06/2537503.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/52157
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!