`
webcenterol
  • 浏览: 906776 次
文章分类
社区版块
存档分类
最新评论

《数据结构与算法分析C++描述》 搜索二叉树的C++实现

 
阅读更多

《数据结构与算法分析C++描述》 搜索二叉树的C++实现

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

《数据结构与算法分析c++描述》 Mark Allen Weiss 人民邮电大学出版 中文版第93-100面,搜索二叉树

需要说明一点的是,此搜索二叉树并没有平衡算法,所以可能会导致有可能出现O(M logN)的最坏情况。

并且几乎所有代码都用递归实现,所以效率并不是太高,并且当N足够大的时候,很多操作都可能导致栈溢出。但是因为对于树的操作用递归描述起来理解上还是比循环好的多,并且以后可以用平衡算法,所以这里都用递归了。

搜索二叉树的实现:

1
2 #ifndef __BINARY_SEARCH_TREE_H__
3 #define __BINARY_SEARCH_TREE_H__
4
5 templatetypename
T>
6 classCBinarySearchTree
7 {
8 public:
9 CBinarySearchTree():mpRoot(NULL) { }
10 CBinarySearchTree(constCBinarySearchTree& aOrig)
11 {
12 mpRoot = Clone(aOrig.mpRoot);
13 }
14 ~CBinarySearchTree()
15 {
16 MakeEmpty();
17 }
18
19 ////////////////////////////////////////////
20 // const member function
21 ////////////////////////////////////////////
22 constT* FindMin() const;
23 constT* FindMax() const;
24
25 boolContains( constT& aElement) const;
26 boolIsEmpty() const
27 {
28 return(mpRoot != NULL) ? true: false;
29 }
30
31 // I don't know how to print it in a good format
32 //void PrintTree() const;
33
34 ////////////////////////////////////////////
35 // non-const member function
36 ////////////////////////////////////////////
37 voidMakeEmpty();
38 voidInsert( constT& aElement);
39 voidRemove( constT& aElement);
40
41 constCBinarySearchTree& operator=(constCBinarySearchTree& aOrig);
42
43 private:
44 structCBinaryNode
45 {
46 CBinaryNode(constT& aElement, CBinaryNode* apLeft, CBinaryNode* apRight)
47 : mElement(aElement),mpLeft(apLeft),mpRight(apRight) {}
48
49 T mElement;
50 CBinaryNode *mpLeft;
51 CBinaryNode *mpRight;
52 };
53
54 // Root Node
55 CBinaryNode *mpRoot;
56
57 ////////////////////////////////////////////
58 // private member function to call recursively
59 ////////////////////////////////////////////
60
61 // I don't like to use reference to pointer
62 // so I used pointer to pointer instead
63 voidInsert(constT& aElement, CBinaryNode** appNode) const;
64 voidRemove(constT& aElement, CBinaryNode** appNode) const;
65
66 CBinaryNode* FindMin(CBinaryNode* apNode) const;
67 CBinaryNode* FindMax(CBinaryNode* apNode) const;
68 boolContains(constT& aElement, CBinaryNode * apNode) const;
69 voidMakeEmpty(CBinaryNode** apNode);
70 //void PrintTree(CBinaryNode* apNode) const;
71 CBinaryNode* Clone(CBinaryNode* apNode) const;
72
73 };
74
75
76 templatetypenameT>
77 boolCBinarySearchTree<t>::Contains(<span style="color:seagreen"><strong>const</strong></span>T&amp; aElement) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">78 </span>{<br><span style="color:#804040">79 </span><span style="color:#804040"><strong>return</strong></span>Contains(aElement, mpRoot);<br><span style="color:#804040">80 </span>}<br><span style="color:#804040">81 </span><br><span style="color:#804040">82 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">83 </span><span style="color:seagreen"><strong>bool</strong></span>CBinarySearchTree<t>::Contains(<span style="color:seagreen"><strong>const</strong></span>T &amp;aElement, CBinaryNode *apNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">84 </span>{<br><span style="color:#804040">85 </span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>== apNode )<br><span style="color:#804040">86 </span>{<br><span style="color:#804040">87 </span><span style="color:#804040"><strong>return</strong></span><span style="color:fuchsia">false</span>;<br><span style="color:#804040">88 </span>}<br><span style="color:#804040">89 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( aElement mElement )<br><span style="color:#804040">90 </span>{<br><span style="color:#804040">91 </span><span style="color:#804040"><strong>return</strong></span>Contains(aElement, apNode-&gt;mpLeft);<br><span style="color:#804040">92 </span>}<br><span style="color:#804040">93 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( aElement &gt; apNode-&gt;mElement )<br><span style="color:#804040">94 </span>{<br><span style="color:#804040">95 </span><span style="color:#804040"><strong>return</strong></span>Contains(aElement, apNode-&gt;mpRight);<br><span style="color:#804040">96 </span>}<br><span style="color:#804040">97 </span><span style="color:#804040"><strong>else</strong></span><br><span style="color:#804040">98 </span>{<br><span style="color:#804040">99 </span><span style="color:#804040"><strong>return</strong></span><span style="color:fuchsia">true</span>;<span style="color:blue">// Find it</span><br><span style="color:#804040">100 </span>}<br><span style="color:#804040">101 </span>}<br><span style="color:#804040">102 </span><br><span style="color:#804040">103 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">104 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::Insert(<span style="color:seagreen"><strong>const</strong></span>T &amp;aElement)<br><span style="color:#804040">105 </span>{<br><span style="color:#804040">106 </span>Insert(aElement, &amp;mpRoot);<br><span style="color:#804040">107 </span>}<br><span style="color:#804040">108 </span><br><span style="color:#804040">109 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">110 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::Insert(<span style="color:seagreen"><strong>const</strong></span>T&amp; aElement, CBinaryNode** appNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">111 </span>{<br><span style="color:#804040">112 </span>CBinaryNode *lpNode = *appNode;<br><span style="color:#804040">113 </span><span style="color:#804040"><strong>if</strong></span>(<span style="color:fuchsia">NULL</span>== lpNode)<br><span style="color:#804040">114 </span>{<br><span style="color:#804040">115 </span>*appNode = <span style="color:#804040"><strong>new</strong></span>CBinaryNode(aElement, <span style="color:fuchsia">NULL</span>, <span style="color:fuchsia">NULL</span>);<br><span style="color:#804040">116 </span>}<br><span style="color:#804040">117 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( aElement mElement )<br><span style="color:#804040">118 </span>{<br><span style="color:#804040">119 </span>Insert(aElement, &amp;(lpNode-&gt;mpLeft) );<br><span style="color:#804040">120 </span>}<br><span style="color:#804040">121 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( aElement &gt; lpNode-&gt;mElement)<br><span style="color:#804040">122 </span>{<br><span style="color:#804040">123 </span>Insert(aElement, &amp;(lpNode-&gt;mpRight) );<br><span style="color:#804040">124 </span>}<br><span style="color:#804040">125 </span><br><span style="color:#804040">126 </span><span style="color:blue">// had not deal with duplicate</span><br><span style="color:#804040">127 </span>}<br><span style="color:#804040">128 </span><br><span style="color:#804040">129 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">130 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::Remove(<span style="color:seagreen"><strong>const</strong></span>T &amp;aElement)<br><span style="color:#804040">131 </span>{<br><span style="color:#804040">132 </span>Remove(aElement, &amp;mpRoot);<br><span style="color:#804040">133 </span>}<br><span style="color:#804040">134 </span><br><span style="color:#804040">135 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">136 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::Remove(<span style="color:seagreen"><strong>const</strong></span>T &amp;aElement, CBinaryNode** appNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">137 </span>{<br><span style="color:#804040">138 </span>CBinaryNode* lpNode = *appNode;<br><span style="color:#804040">139 </span><span style="color:#804040"><strong>if</strong></span>(<span style="color:fuchsia">NULL</span>== lpNode)<br><span style="color:#804040">140 </span>{<br><span style="color:#804040">141 </span><span style="color:#804040"><strong>return</strong></span>; <span style="color:blue">// Item removing is not exist</span><br><span style="color:#804040">142 </span>}<br><span style="color:#804040">143 </span><br><span style="color:#804040">144 </span><span style="color:#804040"><strong>if</strong></span>( aElement mElement )<br><span style="color:#804040">145 </span>{<br><span style="color:#804040">146 </span>Remove(aElement, &amp;(lpNode-&gt;mpLeft) );<br><span style="color:#804040">147 </span>}<br><span style="color:#804040">148 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( aElement &gt; lpNode-&gt;mElement )<br><span style="color:#804040">149 </span>{<br><span style="color:#804040">150 </span>Remove(aElement, &amp;(lpNode-&gt;mpRight) );<br><span style="color:#804040">151 </span>}<br><span style="color:#804040">152 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>!= lpNode-&gt;mpLeft &amp;&amp; <span style="color:fuchsia">NULL</span>!= lpNode-&gt;mpRight) <span style="color:blue">// Two children</span><br><span style="color:#804040">153 </span>{<br><span style="color:#804040">154 </span>lpNode-&gt;mElement = FindMin(lpNode-&gt;mpRight)-&gt;mElement;<br><span style="color:#804040">155 </span>Remove( lpNode-&gt;mElement, &amp;(lpNode-&gt;mpRight) );<br><span style="color:#804040">156 </span>}<br><span style="color:#804040">157 </span><span style="color:#804040"><strong>else</strong></span><br><span style="color:#804040">158 </span>{<br><span style="color:#804040">159 </span>CBinaryNode *lpOldNode = lpNode;<br><span style="color:#804040">160 </span><span style="color:blue">// Even if lpNode equal NULL, this is still the right behavior we need</span><br><span style="color:#804040">161 </span><span style="color:blue">// Yeah,When lpNode have no children,we make lpNode equal NULL</span><br><span style="color:#804040">162 </span>*appNode = (lpNode-&gt;mpLeft != <span style="color:fuchsia">NULL</span>) ? lpNode-&gt;mpLeft : lpNode-&gt;mpRight;<br><span style="color:#804040">163 </span><span style="color:#804040"><strong>delete</strong></span>lpOldNode;<br><span style="color:#804040">164 </span>}<br><span style="color:#804040">165 </span>}<br><span style="color:#804040">166 </span><br><span style="color:#804040">167 </span><br><span style="color:#804040">168 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">169 </span><span style="color:seagreen"><strong>const</strong></span>T* CBinarySearchTree<t>::FindMin() <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">170 </span>{<br><span style="color:#804040">171 </span>CBinaryNode* lpNode = FindMin(mpRoot);<br><span style="color:#804040">172 </span><span style="color:#804040"><strong>return</strong></span>(lpNode != <span style="color:fuchsia">NULL</span>) ? &amp;(lpNode-&gt;mElement) : <span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">173 </span>}<br><span style="color:#804040">174 </span><br><span style="color:#804040">175 </span><br><span style="color:#804040">176 </span><span style="color:blue">// damn it! So redundant words to fit to C++ syntax</span><br><span style="color:#804040">177 </span><span style="color:blue">// the only way to fix this problom is compositing defines and declares</span><br><span style="color:#804040">178 </span><span style="color:blue">// I even doubt that are there programmers could write it right </span><br><span style="color:#804040">179 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">180 </span><span style="color:seagreen"><strong>typename</strong></span>CBinarySearchTree<t>::CBinaryNode * CBinarySearchTree<t>::FindMin(CBinaryNode* apNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">181 </span>{<br><span style="color:#804040">182 </span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>== apNode)<br><span style="color:#804040">183 </span>{<br><span style="color:#804040">184 </span><span style="color:#804040"><strong>return</strong></span><span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">185 </span>}<br><span style="color:#804040">186 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>== apNode-&gt;mpLeft)<br><span style="color:#804040">187 </span>{<br><span style="color:#804040">188 </span><span style="color:blue">// Find it</span><br><span style="color:#804040">189 </span><span style="color:#804040"><strong>return</strong></span>apNode;<br><span style="color:#804040">190 </span>}<br><span style="color:#804040">191 </span><span style="color:#804040"><strong>else</strong></span><br><span style="color:#804040">192 </span>{<br><span style="color:#804040">193 </span><span style="color:#804040"><strong>return</strong></span>FindMin(apNode-&gt;mpLeft);<br><span style="color:#804040">194 </span>}<br><span style="color:#804040">195 </span>}<br><span style="color:#804040">196 </span><br><span style="color:#804040">197 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">198 </span><span style="color:seagreen"><strong>const</strong></span>T* CBinarySearchTree<t>::FindMax() <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">199 </span>{<br><span style="color:#804040">200 </span>CBinaryNode* lpNode = FindMax(mpRoot);<br><span style="color:#804040">201 </span><span style="color:#804040"><strong>return</strong></span>(lpNode != <span style="color:fuchsia">NULL</span>) ? &amp;(lpNode-&gt;mElement) : <span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">202 </span>}<br><span style="color:#804040">203 </span><br><span style="color:#804040">204 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">205 </span><span style="color:seagreen"><strong>typename</strong></span>CBinarySearchTree<t>::CBinaryNode * CBinarySearchTree<t>::FindMax(CBinaryNode* apNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">206 </span>{<br><span style="color:#804040">207 </span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>== apNode)<br><span style="color:#804040">208 </span>{<br><span style="color:#804040">209 </span><span style="color:#804040"><strong>return</strong></span><span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">210 </span>}<br><span style="color:#804040">211 </span><span style="color:#804040"><strong>else</strong></span><span style="color:#804040"><strong>if</strong></span>( <span style="color:fuchsia">NULL</span>== apNode-&gt;mpRight)<br><span style="color:#804040">212 </span>{<br><span style="color:#804040">213 </span><span style="color:blue">// Find it</span><br><span style="color:#804040">214 </span><span style="color:#804040"><strong>return</strong></span>apNode;<br><span style="color:#804040">215 </span>}<br><span style="color:#804040">216 </span><span style="color:#804040"><strong>else</strong></span><br><span style="color:#804040">217 </span>{<br><span style="color:#804040">218 </span><span style="color:#804040"><strong>return</strong></span>FindMax(apNode-&gt;mpRight);<br><span style="color:#804040">219 </span>}<br><span style="color:#804040">220 </span>}<br><span style="color:#804040">221 </span><br><span style="color:#804040">222 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">223 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::MakeEmpty()<br><span style="color:#804040">224 </span>{<br><span style="color:#804040">225 </span>MakeEmpty(&amp;mpRoot);<br><span style="color:#804040">226 </span>}<br><span style="color:#804040">227 </span><br><span style="color:#804040">228 </span><br><span style="color:#804040">229 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">230 </span><span style="color:seagreen"><strong>void</strong></span>CBinarySearchTree<t>::MakeEmpty(CBinaryNode** appNode)<br><span style="color:#804040">231 </span>{<br><span style="color:#804040">232 </span>CBinaryNode* lpNode = *appNode;<br><span style="color:#804040">233 </span><span style="color:#804040"><strong>if</strong></span>( lpNode != <span style="color:fuchsia">NULL</span>)<br><span style="color:#804040">234 </span>{<br><span style="color:#804040">235 </span>MakeEmpty( &amp;(lpNode-&gt;mpLeft) );<br><span style="color:#804040">236 </span>MakeEmpty( &amp;(lpNode-&gt;mpRight) );<br><span style="color:#804040">237 </span><span style="color:#804040"><strong>delete</strong></span>lpNode;<br><span style="color:#804040">238 </span>}<br><span style="color:#804040">239 </span><br><span style="color:#804040">240 </span>*appNode = <span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">241 </span>}<br><span style="color:#804040">242 </span><br><span style="color:#804040">243 </span><span style="color:blue">// how long the syntax is...............</span><br><span style="color:#804040">244 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">245 </span><span style="color:seagreen"><strong>const</strong></span>CBinarySearchTree<t>&amp; CBinarySearchTree<t>::<span style="color:#804040"><strong>operator</strong></span>=(<span style="color:seagreen"><strong>const</strong></span>CBinarySearchTree<t> &amp;aOrig)<br><span style="color:#804040">246 </span>{<br><span style="color:#804040">247 </span><span style="color:#804040"><strong>if</strong></span>(&amp;aOrig == <span style="color:#804040"><strong>this</strong></span>)<br><span style="color:#804040">248 </span>{<br><span style="color:#804040">249 </span><span style="color:#804040"><strong>return</strong></span>*<span style="color:#804040"><strong>this</strong></span>;<br><span style="color:#804040">250 </span>}<br><span style="color:#804040">251 </span><br><span style="color:#804040">252 </span>MakeEmpty();<br><span style="color:#804040">253 </span>mpRoot = Clone(aOrig.mpRoot);<br><span style="color:#804040">254 </span><br><span style="color:#804040">255 </span><span style="color:#804040"><strong>return</strong></span>*<span style="color:#804040"><strong>this</strong></span>;<br><span style="color:#804040">256 </span><br><span style="color:#804040">257 </span>}<br><span style="color:#804040">258 </span><br><span style="color:#804040">259 </span><span style="color:blue">// when you use nest class and template both,you will find out how long the C++ syntax is.....</span><br><span style="color:#804040">260 </span><span style="color:blue">// I use it once,I ask why couldn't we have a short once again.</span><br><span style="color:#804040">261 </span><span style="color:seagreen"><strong>template</strong></span><strong>typename</strong>T&gt;<br><span style="color:#804040">262 </span><span style="color:seagreen"><strong>typename</strong></span>CBinarySearchTree<t>::CBinaryNode* CBinarySearchTree<t>::Clone(CBinaryNode *apNode) <span style="color:seagreen"><strong>const</strong></span><br><span style="color:#804040">263 </span>{<br><span style="color:#804040">264 </span><span style="color:#804040"><strong>if</strong></span>(<span style="color:fuchsia">NULL</span>== apNode)<br><span style="color:#804040">265 </span>{<br><span style="color:#804040">266 </span><span style="color:#804040"><strong>return</strong></span><span style="color:fuchsia">NULL</span>;<br><span style="color:#804040">267 </span>}<br><span style="color:#804040">268 </span><br><span style="color:#804040">269 </span><span style="color:blue">// abuse recursion</span><br><span style="color:#804040">270 </span><span style="color:#804040"><strong>return</strong></span><span style="color:#804040"><strong>new</strong></span>CBinaryNode(apNode-&gt;mElement, Clone(apNode-&gt;mpLeft), Clone(apNode-&gt;mpRight));<br><span style="color:#804040">271 </span>}<br><span style="color:#804040">272 </span><br><span style="color:#804040">273 </span><br><span style="color:#804040">274 </span><br><span style="color:#804040">275 </span><br><span style="color:#804040">276 </span><span style="color:#a020f0">#endif</span><span style="color:blue">// __BINARY_SEARCH_TREE_H__ </span></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t></t>

测试代码:

1 #include <iostream></iostream>
2 #include "BinarySearchTree.h"
3 usingnamespacestd;
4
5 int_tmain(intargc, _TCHAR* argv[])
6 {
7 CBinarySearchTreeint
> loTree;
8
9 loTree.Insert(10);
10 loTree.Insert(20);
11 loTree.Insert(30);
12 loTree.Insert(40);
13 cout "Min: "" Max: "" IsContains(20)"20) 14 loTree.Remove(40);
15 cout "Min: "" Max: "" IsContains(20)"20) 16 loTree.Remove(30);
17 loTree.Remove(20);
18 loTree.Remove(10);
19
20
21 loTree.Insert(40);
22 cout "Min: "" Max: "" IsContains(20)"20) 23 loTree.Insert(30);
24 loTree.Insert(20);
25 loTree.Insert(10);
26 cout "Min: "" Max: "" IsContains(20)"20) 27 loTree.Remove(40);
28 loTree.Remove(30);
29 loTree.Remove(20);
30 loTree.Remove(10);
31
32 loTree.Insert(30);
33 loTree.Insert(40);
34 cout "Min: "" Max: "" IsContains(20)"20) 35 loTree.Insert(10);
36 loTree.Insert(20);
37 cout "Min: "" Max: "" IsContains(20)"20) 38 CBinarySearchTreeint> loTree2 = loTree;
39 cout "Min: "" Max: "" IsContains(20)"20) 40
41 loTree.MakeEmpty();
42
43
44
45 system("pause");
46 return0;
47 }
48

write by 九天雁翎(JTianLing) -- blog.csdn.net/vagrxie

分享到:
评论

相关推荐

    数据结构与算法:C++描述

    本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    5.1 数据对象和数据结构 5.2 线性表数据结构 5.2.1 抽象数据类型linearList 5.2.2 抽象类linearList 5.3 数组描述 5.3.1 描述 5.3.2 变长一维数组 5.3.3 类arrayList 5.3.4 C++迭代器 5.3.5 arrayList的一个迭代器 ...

    C++数据结构知识点与经典算法整理

    四、算法分析与设计 102 1.常用的算法设计方法: 102 1.1 迭代法: 102 1.2 穷举搜索法: 103 1.3 递推法: 104 1.4 递归法 106 1.5 贪婪法 111 1.6 分治法 113 1.7 动态规划法 115 1.8 回溯法 119 1.9 分支定界法...

    数据结构算法与应用(C++语言描述).rar

    第二部分 数据结构 第3章 数据描述 75 3.1 引言 75 3.2 线性表 76 3.3 公式化描述 77 3.3.1 基本概念 77 3.3.2 异常类NoMem 79 3.3.3 操作 79 3.3.4 评价 83 3.4 链表描述 86 3.4.1 类ChainNode 和Chain 86 3.4.2 ...

    数据结构与算法课件C++

    通过本课程的学习,大部分学生的编程能力将跃上一个新的台阶,为后续的专业基础课和专业课程(算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等)打下坚实的基础。  2. 能够...

    数据结构算法与应用-C++语言描述

    本书在简要回顾了基本的C++ 程序设计概念的基础上,全面系统地介绍了队列、堆栈、树、图等基本数据结构,以及贪婪算法、分而治之算法、分枝定界算法等多种算法设计方法,为数据结构与算法的继续学习和研究奠定了一...

    基础数据结构和算法(C、C++、Java各一套)

    基础的数据结构和算法C、C++、Java实现,有线性表、链表、队列、二叉树、图、查找、排序等等,全是最标准的实现,可以用来学习也可以直接使用。用来学习的话,里边有每种算法一步一步实现的图片,更加清晰。

    数据结构与算法综合资料库

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    数据结构与算法分析

     本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书的内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找...

    C++数据结构与算法

     1.9 数据结构与面向对象编程  1.10 案例分析:随机访问文件  1.11 习题  1.12 编程练习  参考书目 第2章 复杂度分析  2.1 计算复杂度以及渐近复杂度  2.2 大O表示法  2.3 大O表示法的性质  2.4 Ω表示法与...

    C++数据结构与算法_第4版_Adam Drozdek_2014.part1.rar

    这本《C++数据结构与算法(第4版)》全面系统地介绍了数据结构,并以C++语言实现相关的算法。 主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈、队列、...

    数据结构与算法:语言描述(中英文)

    本章结尾处介绍了衡量书中讨论的数据结构与算法性能的方法。 第2章提供了数组构造方法的回顾,并连同示例说明了Array类的特征。Array类把许多与数组相关的函数(UBound函数、LBound函数等等)封装到单独一个包中。...

    谭浩强C语言程序设计,C++程序设计,严蔚敏数据结构,高一凡数据结构算法分析与实现.rar

    4.3 数据输入输出的概念及在 C 语言中的实现 54 4.4 字符数据的输入输出 54 4.4.1 putchar 函数(字符输出函数) 54 4.4.2 getchar函数(键盘输入函数) 55 4.5 格式输入与输出 55 4.5.1 printf 函数(格式输出函数...

    数据结构与算法综合资料库.CHM

    数据结构与算法综合资料库.CHM 介绍 何谓数据结构 算法综合知识 用递归中序遍历二叉树 BRESENHAM高效画线算法 C++的沉迷与爱恋 C++复习题一 C++复习题 二 DES加密算法破解方法 DES算法及其应用误区 N皇后问题 采用...

    C++数据结构与算法_第4版_Adam Drozdek_2014.part2.rar

    这本《C++数据结构与算法(第4版)》全面系统地介绍了数据结构,并以C++语言实现相关的算法。 主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈、队列、...

    C++数据结构与算法_第4版_Adam Drozdek_2014.part3.rar

    这本《C++数据结构与算法(第4版)》全面系统地介绍了数据结构,并以C++语言实现相关的算法。 主要强调了数据结构和算法之间的联系,使用面向对象的方法介绍数据结构,其内容包括算法的复杂度分析、链表、栈、队列、...

    数据结构与算法分析C描述第三版

     1.4.3 接口与实现的分离   1.4.4 vector和string   1.5 C++细节   1.5.1 指针   1.5.2 参数传递   1.5.3 返回值传递   1.5.4 引用变量   1.5.5 三大函数:析构函数、复制构造函数和operator...

    (清华的严蔚敏讲稿)数据结构与算法--c++

    第一章 绪论.doc 第二章 线性表.doc 第三章 栈和队列.doc 第四章 串.doc 第五章 数组.doc 第六章 树和二叉树.doc 第七章 图.doc 第九章 查找表.doc 第十章 排 序.doc 第十二章 文 件.doc 其他 广义表.doc

    Huffman编码(c++版本)_数据结构与算法分析课程设计报告

    1.要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法  2.熟练掌握二叉树的应用;具体要求如下:最小冗余码/哈夫曼码、ASCII码/定长码、哈夫曼码/不定长码、统计、构造Huffman树、在左分枝标0,右分枝标...

Global site tag (gtag.js) - Google Analytics