backup/C-Plus-Plus
1
0
Fork 0
mirror of https://github.com/TheAlgorithms/C-Plus-Plus.git synced 2026-03-21 20:31:43 +08:00
Code Issues Projects Releases Wiki Activity
Files
gh-pages
C-Plus-Plus/d1/df3/hash__search_8cpp.html
realstealthninja 98266a5de5 Documentation for c917fc4560
2025-08-18 16:19:29 +00:00

472 lines
34 KiB
HTML
Raw Permalink Blame History

<!-- HTML header for doxygen 1.12.0-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.14.0"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>TheAlgorithms/C++: search/hash_search.cpp File Reference</title>
<link rel="icon" href="../../favicon.svg" type="image/x-icon" />
<link href="../../tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../jquery.js"></script>
<script type="text/javascript" src="../../dynsections.js"></script>
<script type="text/javascript" src="https://cdn.jsdelivr.net/npm/@xpack-3rd-party/doxygen-awesome-css@2.2.0-1/doxygen-awesome-darkmode-toggle.js"></script>
<script type="text/javascript">
DoxygenAwesomeDarkModeToggle.init()
</script>
<script type="text/javascript" src="../../clipboard.js"></script>
<link href="../../navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../navtreedata.js"></script>
<script type="text/javascript" src="../../navtree.js"></script>
<script type="text/javascript" src="../../cookie.js"></script>
<link href="../../search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="../../search/searchdata.js"></script>
<script type="text/javascript" src="../../search/search.js"></script>
<script type="text/javascript">
window.MathJax = {
options: {
ignoreHtmlClass: 'tex2jax_ignore',
processHtmlClass: 'tex2jax_process'
},
loader: {
load: ['[tex]/ams']
},
tex: {
macros: {},
packages: ['base','configmacros','ams']
}
};
</script>
<script type="text/javascript" id="MathJax-script" async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-chtml.js"></script>
<link href="../../doxygen.css" rel="stylesheet" type="text/css" />
<link href="../../doxygen-awesome.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectlogo"><img alt="Logo" src="../../project_logo.png"/></td>
<td id="projectalign">
<div id="projectname">TheAlgorithms/C++<span id="projectnumber">&#160;1.0.0</span>
</div>
<div id="projectbrief">All the algorithms implemented in C++</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.14.0 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "../../search/",'.html');
</script>
<script type="text/javascript">
$(function() { codefold.init(); });
</script>
<script type="text/javascript" src="../../menudata.js"></script>
<script type="text/javascript" src="../../menu.js"></script>
<script type="text/javascript">
$(function() {
initMenu('../../',true,false,'search.php','Search',true);
$(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(function(){initNavTree('d1/df3/hash__search_8cpp.html','../../',''); });
</script>
<div id="container">
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div class="header">
<div class="headertitle"><div class="title">hash_search.cpp File Reference</div></div>
</div><!--header-->
<div class="contents">
<p>Hash Search Algorithm - Best Time Complexity Ω(1)
<a href="#details">More...</a></p>
<div class="textblock"><code>#include &lt;cstdlib&gt;</code><br />
<code>#include &lt;iostream&gt;</code><br />
</div><div class="textblock"><div class="dynheader">
Include dependency graph for hash_search.cpp:</div>
<div class="dyncontent">
<div class="center"><iframe scrolling="no" loading="lazy" frameborder="0" src="../../d3/d30/hash__search_8cpp__incl.svg" width="175" height="111"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
</div>
</div>
<p><a href="../../d1/df3/hash__search_8cpp_source.html">Go to the source code of this file.</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 id="header-nested-classes" class="groupheader"><a id="nested-classes" name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:list" id="r_list"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="../../d8/d10/structlist.html">list</a></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 id="header-define-members" class="groupheader"><a id="define-members" name="define-members"></a>
Macros</h2></td></tr>
<tr class="memitem:a392fb874e547e582e9c66a08a1f23326" id="r_a392fb874e547e582e9c66a08a1f23326"><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a392fb874e547e582e9c66a08a1f23326">MAX</a>&#160;&#160;&#160;6</td></tr>
<tr class="memdesc:a392fb874e547e582e9c66a08a1f23326"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determines how much data. <br /></td></tr>
<tr class="memitem:a77c722016053a1d484aa177ce205b367" id="r_a77c722016053a1d484aa177ce205b367"><td class="memItemLeft" align="right" valign="top">#define&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a>&#160;&#160;&#160;5</td></tr>
<tr class="memdesc:a77c722016053a1d484aa177ce205b367"><td class="mdescLeft">&#160;</td><td class="mdescRight">Determines the length of the hash table. <br /></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 id="header-typedef-members" class="groupheader"><a id="typedef-members" name="typedef-members"></a>
Typedefs</h2></td></tr>
<tr class="memitem:a8ca8dcb494104d273679e219e53d0555" id="r_a8ca8dcb494104d273679e219e53d0555"><td class="memItemLeft" align="right" valign="top">typedef struct <a class="el" href="../../d8/d10/structlist.html">list</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a8ca8dcb494104d273679e219e53d0555">node</a></td></tr>
<tr class="memitem:ad6fcd983304f85afa199d97a9b0ca9f6" id="r_ad6fcd983304f85afa199d97a9b0ca9f6"><td class="memItemLeft" align="right" valign="top"><a id="ad6fcd983304f85afa199d97a9b0ca9f6" name="ad6fcd983304f85afa199d97a9b0ca9f6"></a>
typedef struct <a class="el" href="../../d8/d10/structlist.html">list</a> *&#160;</td><td class="memItemRight" valign="bottom"><b>link</b></td></tr>
<tr class="memdesc:ad6fcd983304f85afa199d97a9b0ca9f6"><td class="mdescLeft">&#160;</td><td class="mdescRight">pointer to nodes <br /></td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 id="header-func-members" class="groupheader"><a id="func-members" name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:a566eaf0ffafd50bc61e644561fd27001" id="r_a566eaf0ffafd50bc61e644561fd27001"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a566eaf0ffafd50bc61e644561fd27001">h</a> (int key)</td></tr>
<tr class="memitem:ad0831425f1389166a9518f422d0c6ec5" id="r_ad0831425f1389166a9518f422d0c6ec5"><td class="memItemLeft" align="right" valign="top">void&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#ad0831425f1389166a9518f422d0c6ec5">create_list</a> (int key)</td></tr>
<tr class="memitem:a36ea13c16028f18ef2d5ff47f3fda7a2" id="r_a36ea13c16028f18ef2d5ff47f3fda7a2"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a36ea13c16028f18ef2d5ff47f3fda7a2">hash_search</a> (int key, int *counter)</td></tr>
<tr class="memitem:ae66f6b31b5ad750f1fe042a706a4e3d4" id="r_ae66f6b31b5ad750f1fe042a706a4e3d4"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#ae66f6b31b5ad750f1fe042a706a4e3d4">main</a> ()</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 id="header-var-members" class="groupheader"><a id="var-members" name="var-members"></a>
Variables</h2></td></tr>
<tr class="memitem:a6e1a77282bc65ad359d753d25df23243" id="r_a6e1a77282bc65ad359d753d25df23243"><td class="memItemLeft" align="right" valign="top">int&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#a6e1a77282bc65ad359d753d25df23243">data</a> [MAX] = {1, 10, 15, 5, 8, 7}</td></tr>
<tr class="memdesc:a6e1a77282bc65ad359d753d25df23243"><td class="mdescLeft">&#160;</td><td class="mdescRight">test data <br /></td></tr>
<tr class="memitem:af413b1740073db54796642b0ab814d6d" id="r_af413b1740073db54796642b0ab814d6d"><td class="memItemLeft" align="right" valign="top"><a class="el" href="../../d5/da1/structnode.html">node</a>&#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="#af413b1740073db54796642b0ab814d6d">hashtab</a> [<a class="el" href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a>]</td></tr>
<tr class="memdesc:af413b1740073db54796642b0ab814d6d"><td class="mdescLeft">&#160;</td><td class="mdescRight">array of nodes <br /></td></tr>
</table>
<a name="details" id="details"></a><h2 id="header-details" class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Hash Search Algorithm - Best Time Complexity Ω(1) </p>
<dl class="section copyright"><dt>Copyright</dt><dd>2020 Arctic2333</dd></dl>
<p>In this algorithm, we use the method of division and reservation remainder to construct the hash function, and use the method of chain address to solve the conflict, that is, we link a chain list after the data, and store all the records whose keywords are synonyms in the same linear chain list.</p>
<dl class="section warning"><dt>Warning</dt><dd>This program is only for educational purposes. It has serious flaws in implementation with regards to memory management resulting in large amounts of memory leaks. </dd></dl>
<dl class="todo"><dt><b><a class="el" href="../../dd/da0/todo.html#_todo000012">Todo</a></b></dt><dd>fix the program for memory leaks and better structure in C++ and not C fashion </dd></dl>
<p class="definition">Definition in file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
</div><a name="doc-define-members" id="doc-define-members"></a><h2 id="header-doc-define-members" class="groupheader">Macro Definition Documentation</h2>
<a id="a77c722016053a1d484aa177ce205b367" name="a77c722016053a1d484aa177ce205b367"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a77c722016053a1d484aa177ce205b367">&#9670;&#160;</a></span>HASHMAX</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define HASHMAX&#160;&#160;&#160;5</td>
</tr>
</table>
</div><div class="memdoc">
<p>Determines the length of the hash table. </p>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00022">22</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
</div>
</div>
<a id="a392fb874e547e582e9c66a08a1f23326" name="a392fb874e547e582e9c66a08a1f23326"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a392fb874e547e582e9c66a08a1f23326">&#9670;&#160;</a></span>MAX</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">#define MAX&#160;&#160;&#160;6</td>
</tr>
</table>
</div><div class="memdoc">
<p>Determines how much data. </p>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00021">21</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
</div>
</div>
<a name="doc-typedef-members" id="doc-typedef-members"></a><h2 id="header-doc-typedef-members" class="groupheader">Typedef Documentation</h2>
<a id="a8ca8dcb494104d273679e219e53d0555" name="a8ca8dcb494104d273679e219e53d0555"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a8ca8dcb494104d273679e219e53d0555">&#9670;&#160;</a></span>node</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">typedef struct <a class="el" href="../../d8/d10/structlist.html">list</a> node</td>
</tr>
</table>
</div><div class="memdoc">
<p>a one-way linked list define node as one item list </p>
</div>
</div>
<a name="doc-func-members" id="doc-func-members"></a><h2 id="header-doc-func-members" class="groupheader">Function Documentation</h2>
<a id="ad0831425f1389166a9518f422d0c6ec5" name="ad0831425f1389166a9518f422d0c6ec5"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ad0831425f1389166a9518f422d0c6ec5">&#9670;&#160;</a></span>create_list()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">void create_list </td>
<td>(</td>
<td class="paramtype">int</td> <td class="paramname"><span class="paramname"><em>key</em></span></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>The same after the remainder will be added after the same hash header To avoid conflict, zipper method is used Insert elements into the linked list in the header </p><dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">key</td><td>key to add to list </td></tr>
</table>
</dd>
</dl>
<dl class="section warning"><dt>Warning</dt><dd>dynamic memory allocated to <span class="tt">n</span> never gets freed. </dd></dl>
<dl class="todo"><dt><b><a class="el" href="../../dd/da0/todo.html#_todo000013">Todo</a></b></dt><dd>fix memory leak </dd></dl>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00055">55</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
<div class="fragment"><div class="line"><span class="lineno"> 55</span> { <span class="comment">// Construct hash table</span></div>
<div class="line"><span class="lineno"> 56</span> <a class="code hl_typedef" href="#ad6fcd983304f85afa199d97a9b0ca9f6">link</a> p, n;</div>
<div class="line"><span class="lineno"> 57</span> <span class="keywordtype">int</span> index;</div>
<div class="line"><span class="lineno"> 58</span> n = (<a class="code hl_typedef" href="#ad6fcd983304f85afa199d97a9b0ca9f6">link</a>)malloc(<span class="keyword">sizeof</span>(<a class="code hl_class" href="../../d5/da1/structnode.html">node</a>));</div>
<div class="line"><span class="lineno"> 59</span> n-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">key</a> = key;</div>
<div class="line"><span class="lineno"> 60</span> n-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#a1900fe79e875e2838625b2eb60837f8f">next</a> = NULL;</div>
<div class="line"><span class="lineno"> 61</span> index = <a class="code hl_function" href="#a566eaf0ffafd50bc61e644561fd27001">h</a>(key);</div>
<div class="line"><span class="lineno"> 62</span> p = <a class="code hl_variable" href="#af413b1740073db54796642b0ab814d6d">hashtab</a>[index].next;</div>
<div class="line"><span class="lineno"> 63</span> <span class="keywordflow">if</span> (p != NULL) {</div>
<div class="line"><span class="lineno"> 64</span> n-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#a1900fe79e875e2838625b2eb60837f8f">next</a> = p;</div>
<div class="line"><span class="lineno"> 65</span> <a class="code hl_variable" href="#af413b1740073db54796642b0ab814d6d">hashtab</a>[index].next = n;</div>
<div class="line"><span class="lineno"> 66</span> } <span class="keywordflow">else</span> {</div>
<div class="line"><span class="lineno"> 67</span> <a class="code hl_variable" href="#af413b1740073db54796642b0ab814d6d">hashtab</a>[index].next = n;</div>
<div class="line"><span class="lineno"> 68</span> }</div>
<div class="line"><span class="lineno"> 69</span>}</div>
<div class="ttc" id="ahash__search_8cpp_html_a566eaf0ffafd50bc61e644561fd27001"><div class="ttname"><a href="#a566eaf0ffafd50bc61e644561fd27001">h</a></div><div class="ttdeci">int h(int key)</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00045">hash_search.cpp:45</a></div></div>
<div class="ttc" id="ahash__search_8cpp_html_ad6fcd983304f85afa199d97a9b0ca9f6"><div class="ttname"><a href="#ad6fcd983304f85afa199d97a9b0ca9f6">link</a></div><div class="ttdeci">struct list * link</div><div class="ttdoc">pointer to nodes</div></div>
<div class="ttc" id="ahash__search_8cpp_html_af413b1740073db54796642b0ab814d6d"><div class="ttname"><a href="#af413b1740073db54796642b0ab814d6d">hashtab</a></div><div class="ttdeci">node hashtab[HASHMAX]</div><div class="ttdoc">array of nodes</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00035">hash_search.cpp:35</a></div></div>
<div class="ttc" id="astructlist_html_a1900fe79e875e2838625b2eb60837f8f"><div class="ttname"><a href="../../d8/d10/structlist.html#a1900fe79e875e2838625b2eb60837f8f">list::next</a></div><div class="ttdeci">struct list * next</div><div class="ttdoc">pointer to next link in the chain</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00031">hash_search.cpp:31</a></div></div>
<div class="ttc" id="astructlist_html_aaab2e33bc1ca6f44e72239bfb58f100c"><div class="ttname"><a href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">list::key</a></div><div class="ttdeci">int key</div><div class="ttdoc">key value for node</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00030">hash_search.cpp:30</a></div></div>
<div class="ttc" id="astructnode_html"><div class="ttname"><a href="../../d5/da1/structnode.html">node</a></div><div class="ttdef"><b>Definition</b> <a href="../../d3/d26/binary__search__tree_8cpp_source.html#l00011">binary_search_tree.cpp:11</a></div></div>
</div><!-- fragment -->
</div>
</div>
<a id="a566eaf0ffafd50bc61e644561fd27001" name="a566eaf0ffafd50bc61e644561fd27001"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a566eaf0ffafd50bc61e644561fd27001">&#9670;&#160;</a></span>h()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int h </td>
<td>(</td>
<td class="paramtype">int</td> <td class="paramname"><span class="paramname"><em>key</em></span></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>Mode of hash detection : Division method </p><dl class="params"><dt>Parameters</dt><dd>
<table class="params">
<tr><td class="paramdir">[in]</td><td class="paramname">key</td><td>to hash </td></tr>
</table>
</dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>hash value for <span class="tt">key</span> </dd></dl>
<dl class="section examples"><dt>Examples</dt><dd><a class="el" href="../../dc/dc4/_2_users_2runner_2work_2_c-_plus-_plus_2_c-_plus-_plus_2numerical_methods_2rungekutta_8cpp-example.html#_a2">/Users/runner/work/C-Plus-Plus/C-Plus-Plus/numerical_methods/rungekutta.cpp</a>.</dd>
</dl>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00045">45</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
<div class="fragment"><div class="line"><span class="lineno"> 45</span>{ <span class="keywordflow">return</span> key % <a class="code hl_define" href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a>; }</div>
<div class="ttc" id="ahash__search_8cpp_html_a77c722016053a1d484aa177ce205b367"><div class="ttname"><a href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a></div><div class="ttdeci">#define HASHMAX</div><div class="ttdoc">Determines the length of the hash table.</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00022">hash_search.cpp:22</a></div></div>
</div><!-- fragment -->
</div>
</div>
<a id="a36ea13c16028f18ef2d5ff47f3fda7a2" name="a36ea13c16028f18ef2d5ff47f3fda7a2"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a36ea13c16028f18ef2d5ff47f3fda7a2">&#9670;&#160;</a></span>hash_search()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int hash_search </td>
<td>(</td>
<td class="paramtype">int</td> <td class="paramname"><span class="paramname"><em>key</em></span>, </td>
</tr>
<tr>
<td class="paramkey"></td>
<td></td>
<td class="paramtype">int *</td> <td class="paramname"><span class="paramname"><em>counter</em></span>&#160;)</td>
</tr>
</table>
</div><div class="memdoc">
<p>Input the key to be searched, and get the hash header position through the H (int key) function, then one-dimensional linear search. If found </p><dl class="section return"><dt>Returns</dt><dd>element depth and number of searches If not found </dd>
<dd>
-1 </dd></dl>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00076">76</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
<div class="fragment"><div class="line"><span class="lineno"> 76</span> { <span class="comment">// Hash lookup function</span></div>
<div class="line"><span class="lineno"> 77</span> <a class="code hl_typedef" href="#ad6fcd983304f85afa199d97a9b0ca9f6">link</a> pointer;</div>
<div class="line"><span class="lineno"> 78</span> <span class="keywordtype">int</span> index;</div>
<div class="line"><span class="lineno"> 79</span> </div>
<div class="line"><span class="lineno"> 80</span> *counter = 0;</div>
<div class="line"><span class="lineno"> 81</span> index = <a class="code hl_function" href="#a566eaf0ffafd50bc61e644561fd27001">h</a>(key);</div>
<div class="line"><span class="lineno"> 82</span> pointer = <a class="code hl_variable" href="#af413b1740073db54796642b0ab814d6d">hashtab</a>[index].next;</div>
<div class="line"><span class="lineno"> 83</span> </div>
<div class="line"><span class="lineno"> 84</span> std::cout &lt;&lt; <span class="stringliteral">&quot;data[&quot;</span> &lt;&lt; index &lt;&lt; <span class="stringliteral">&quot;]:&quot;</span>;</div>
<div class="line"><span class="lineno"> 85</span> </div>
<div class="line"><span class="lineno"> 86</span> <span class="keywordflow">while</span> (pointer != NULL) {</div>
<div class="line"><span class="lineno"> 87</span> counter[0]++;</div>
<div class="line"><span class="lineno"> 88</span> std::cout &lt;&lt; <span class="stringliteral">&quot;data[&quot;</span> &lt;&lt; pointer-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">key</a> &lt;&lt; <span class="stringliteral">&quot;]:&quot;</span>;</div>
<div class="line"><span class="lineno"> 89</span> <span class="keywordflow">if</span> (pointer-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">key</a> == key)</div>
<div class="line"><span class="lineno"> 90</span> <span class="keywordflow">return</span> 1;</div>
<div class="line"><span class="lineno"> 91</span> <span class="keywordflow">else</span></div>
<div class="line"><span class="lineno"> 92</span> pointer = pointer-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#a1900fe79e875e2838625b2eb60837f8f">next</a>;</div>
<div class="line"><span class="lineno"> 93</span> }</div>
<div class="line"><span class="lineno"> 94</span> </div>
<div class="line"><span class="lineno"> 95</span> <span class="keywordflow">return</span> 0;</div>
<div class="line"><span class="lineno"> 96</span>}</div>
</div><!-- fragment -->
</div>
</div>
<a id="ae66f6b31b5ad750f1fe042a706a4e3d4" name="ae66f6b31b5ad750f1fe042a706a4e3d4"></a>
<h2 class="memtitle"><span class="permalink"><a href="#ae66f6b31b5ad750f1fe042a706a4e3d4">&#9670;&#160;</a></span>main()</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int main </td>
<td>(</td>
<td class="paramtype">void</td> <td class="paramname"><span class="paramname"><em></em></span></td><td>)</td>
<td></td>
</tr>
</table>
</div><div class="memdoc">
<p>main function </p>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00099">99</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
<div class="fragment"><div class="line"><span class="lineno"> 99</span> {</div>
<div class="line"><span class="lineno"> 100</span> <a class="code hl_typedef" href="#ad6fcd983304f85afa199d97a9b0ca9f6">link</a> p;</div>
<div class="line"><span class="lineno"> 101</span> <span class="keywordtype">int</span> key = 0, index, i, counter; <span class="comment">// Key is the value to be found</span></div>
<div class="line"><span class="lineno"> 102</span> index = 0;</div>
<div class="line"><span class="lineno"> 103</span> </div>
<div class="line"><span class="lineno"> 104</span> <span class="comment">// You can write the input mode here</span></div>
<div class="line"><span class="lineno"> 105</span> <span class="keywordflow">while</span> (index &lt; MAX) { <span class="comment">// Construct hash table</span></div>
<div class="line"><span class="lineno"> 106</span> <a class="code hl_function" href="#ad0831425f1389166a9518f422d0c6ec5">create_list</a>(<a class="code hl_variable" href="#a6e1a77282bc65ad359d753d25df23243">data</a>[index]);</div>
<div class="line"><span class="lineno"> 107</span> index++;</div>
<div class="line"><span class="lineno"> 108</span> }</div>
<div class="line"><span class="lineno"> 109</span> </div>
<div class="line"><span class="lineno"> 110</span> <span class="keywordflow">for</span> (i = 0; i &lt; <a class="code hl_define" href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a>; i++) { <span class="comment">// Output hash table</span></div>
<div class="line"><span class="lineno"> 111</span> std::cout &lt;&lt; <span class="stringliteral">&quot;hashtab [&quot;</span> &lt;&lt; i &lt;&lt; <span class="stringliteral">&quot;]\n&quot;</span>;</div>
<div class="line"><span class="lineno"> 112</span> </div>
<div class="line"><span class="lineno"> 113</span> p = <a class="code hl_variable" href="#af413b1740073db54796642b0ab814d6d">hashtab</a>[i].next;</div>
<div class="line"><span class="lineno"> 114</span> </div>
<div class="line"><span class="lineno"> 115</span> <span class="keywordflow">while</span> (p != NULL) {</div>
<div class="line"><span class="lineno"> 116</span> std::cout &lt;&lt; <span class="stringliteral">&quot;please int key:&quot;</span>;</div>
<div class="line"><span class="lineno"> 117</span> <span class="keywordflow">if</span> (p-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">key</a> &gt; 0)</div>
<div class="line"><span class="lineno"> 118</span> std::cout &lt;&lt; <span class="stringliteral">&quot;[&quot;</span> &lt;&lt; p-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#aaab2e33bc1ca6f44e72239bfb58f100c">key</a> &lt;&lt; <span class="stringliteral">&quot;]&quot;</span>;</div>
<div class="line"><span class="lineno"> 119</span> p = p-&gt;<a class="code hl_variable" href="../../d8/d10/structlist.html#a1900fe79e875e2838625b2eb60837f8f">next</a>;</div>
<div class="line"><span class="lineno"> 120</span> }</div>
<div class="line"><span class="lineno"> 121</span> std::cout &lt;&lt; std::endl;</div>
<div class="line"><span class="lineno"> 122</span> }</div>
<div class="line"><span class="lineno"> 123</span> </div>
<div class="line"><span class="lineno"> 124</span> <span class="keywordflow">while</span> (key != -1) {</div>
<div class="line"><span class="lineno"> 125</span> <span class="comment">// You can write the input mode here</span></div>
<div class="line"><span class="lineno"> 126</span> <span class="comment">// test key = 10</span></div>
<div class="line"><span class="lineno"> 127</span> key = 10;</div>
<div class="line"><span class="lineno"> 128</span> <span class="keywordflow">if</span> (<a class="code hl_function" href="#a36ea13c16028f18ef2d5ff47f3fda7a2">hash_search</a>(key, &amp;counter))</div>
<div class="line"><span class="lineno"> 129</span> std::cout &lt;&lt; <span class="stringliteral">&quot;search time = &quot;</span> &lt;&lt; counter &lt;&lt; std::endl;</div>
<div class="line"><span class="lineno"> 130</span> <span class="keywordflow">else</span></div>
<div class="line"><span class="lineno"> 131</span> std::cout &lt;&lt; <span class="stringliteral">&quot;no found!\n&quot;</span>;</div>
<div class="line"><span class="lineno"> 132</span> key = -1; <span class="comment">// Exit test</span></div>
<div class="line"><span class="lineno"> 133</span> <span class="comment">/* The test sample is returned as:</span></div>
<div class="line"><span class="lineno"> 134</span><span class="comment"> * data[0]:data[5]:data[15]:data[10]:search time = 3 The search is</span></div>
<div class="line"><span class="lineno"> 135</span><span class="comment"> * successful. There are 10 in this set of data */</span></div>
<div class="line"><span class="lineno"> 136</span> }</div>
<div class="line"><span class="lineno"> 137</span> </div>
<div class="line"><span class="lineno"> 138</span> <span class="keywordflow">return</span> 0;</div>
<div class="line"><span class="lineno"> 139</span>}</div>
<div class="ttc" id="ahash__search_8cpp_html_a36ea13c16028f18ef2d5ff47f3fda7a2"><div class="ttname"><a href="#a36ea13c16028f18ef2d5ff47f3fda7a2">hash_search</a></div><div class="ttdeci">int hash_search(int key, int *counter)</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00076">hash_search.cpp:76</a></div></div>
<div class="ttc" id="ahash__search_8cpp_html_a6e1a77282bc65ad359d753d25df23243"><div class="ttname"><a href="#a6e1a77282bc65ad359d753d25df23243">data</a></div><div class="ttdeci">int data[MAX]</div><div class="ttdoc">test data</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00024">hash_search.cpp:24</a></div></div>
<div class="ttc" id="ahash__search_8cpp_html_ad0831425f1389166a9518f422d0c6ec5"><div class="ttname"><a href="#ad0831425f1389166a9518f422d0c6ec5">create_list</a></div><div class="ttdeci">void create_list(int key)</div><div class="ttdef"><b>Definition</b> <a href="../../d1/df3/hash__search_8cpp_source.html#l00055">hash_search.cpp:55</a></div></div>
</div><!-- fragment -->
</div>
</div>
<a name="doc-var-members" id="doc-var-members"></a><h2 id="header-doc-var-members" class="groupheader">Variable Documentation</h2>
<a id="a6e1a77282bc65ad359d753d25df23243" name="a6e1a77282bc65ad359d753d25df23243"></a>
<h2 class="memtitle"><span class="permalink"><a href="#a6e1a77282bc65ad359d753d25df23243">&#9670;&#160;</a></span>data</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname">int data[MAX] = {1, 10, 15, 5, 8, 7}</td>
</tr>
</table>
</div><div class="memdoc">
<p>test data </p>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00024">24</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
<div class="fragment"><div class="line"><span class="lineno"> 24</span>{1, 10, 15, 5, 8, 7}; </div>
</div><!-- fragment -->
</div>
</div>
<a id="af413b1740073db54796642b0ab814d6d" name="af413b1740073db54796642b0ab814d6d"></a>
<h2 class="memtitle"><span class="permalink"><a href="#af413b1740073db54796642b0ab814d6d">&#9670;&#160;</a></span>hashtab</h2>
<div class="memitem">
<div class="memproto">
<table class="memname">
<tr>
<td class="memname"><a class="el" href="../../d5/da1/structnode.html">node</a> hashtab[<a class="el" href="#a77c722016053a1d484aa177ce205b367">HASHMAX</a>]</td>
</tr>
</table>
</div><div class="memdoc">
<p>array of nodes </p>
<p class="definition">Definition at line <a class="el" href="../../d1/df3/hash__search_8cpp_source.html#l00035">35</a> of file <a class="el" href="../../d1/df3/hash__search_8cpp_source.html">hash_search.cpp</a>.</p>
</div>
</div>
</div><!-- contents -->
</div><!-- doc-content -->
<div id="page-nav" class="page-nav-panel">
<div id="page-nav-resize-handle"></div>
<div id="page-nav-tree">
<div id="page-nav-contents">
</div><!-- page-nav-contents -->
</div><!-- page-nav-tree -->
</div><!-- page-nav -->
</div><!-- container -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a href="../../dir_19b2bf9199a15c634a08b1ede1dd896a.html">search</a></li><li class="navelem"><a href="../../d1/df3/hash__search_8cpp.html">hash_search.cpp</a></li>
<li class="footer">Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="../../doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.14.0 </li>
</ul>
</div>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink