C语言哈希表概念超详细讲解

2024-10-18 01:43:39

1. 哈希概念

哈希其实在学排序时已经用过了，就是计数排序。计数排序也是用的一种映射关系。

比如对此数组进行计数排序：1 1 9 9 9 3 3 8 8

我用的是绝对映射，所以开辟的数组空间它的大小必须能映射到最大的元素。

但是对于哈希来讲，可以用决定映射嘛？当然不可以，如果是绝对映射会造成很大的空间浪费。所以哈希用的是取模的方式来存数据。

比如：哈希表的空间我给定只能存放 10个元素

存进来的数对10进行取模，那么必定可以存方到这个哈希表中。

比如：存 100 ，它对10取模得 0，那它就存在第一个位置；存 52 ，它对10进行取模得 2，那它就存到下标为 2的位置。

也就是说无论多大的数据，都可以存到哈希表中。但是有两个问题：

数据都能进行取模吗？假如我要求哈希表中存的是一个字符串，字符串不能进行取模运算，该怎么办？这就是数据可否哈希的问题，我们要把存进哈希表的数据，变为可哈希数据。
如果我存的是 4，下一次我要存的是 14。由于 4的位置已经被占了，我存的 14 该存放到何处？要是直接存，就意味着前面存的 4 会被覆盖，造成数据丢失。这就是哈希冲突问题。

2. 哈希冲突

造成了哈希冲突，得解决哈希冲突问题。

这里给出两种解决手段：

闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。

它相当于如果我本来要存的位置，已经被占了，那么我就要在哈希表中找一个空位置存放。开散列：开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

这种办法是常用的，它相当于哈希表每个位置都存的是一个哈希桶，如果发送哈希冲突，直接就放在哈希桶里就行了。

3. 哈希实现

哈希表其实就是一个数组，数组中存的是节点数据，发生哈希冲突后，采用的是往后找空位置的方法。

图解：

(1) 10 % 6 == 4,所以插入到下标为4的位置

(2) 20%6==2,插入到下标为2的位置

(3)12%6 == 0,插入到下标为0的位置。

(4)22%6 == 4，插入到下标为4的位置，发现已经有数据了，所以向后找空位置。

(5)44%6 == 2，插入到下标为2的位置，发现已经有数据了，所以向后找空位置。

哈希桶其实就是一个数组，数组中存的是节点链表，发生哈希冲突后，是直接插入到节点链表中。

如果是哈希桶，存放上面的数据，是什么样的呢？

图解：

它相当于把发生冲突的数据挂在了冲突位置的下面。

3.1 闭散列(哈希表)

#include<vector>
#include<iostream>
using namespace std;
namespace hash_table
{
	enum status
	{
		Empty,
		Exist,
		Delete
	};
	template<class K,class V>
	struct hashdate
	{
		pair<K, V> _kv;
		status _status = Empty;
	};
	template<class K,class V>
	class close_hashtable
	{
		typedef hashdate<K, V> Node;
	private:
		vector<Node> _tables;
		size_t _n = 0;
	public:
		Node* find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			size_t start = key % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status != Empty)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
					return &_tables[index];
				i++;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}
        bool erase(const K& key)
		{
			Node* ret = find(key);
			if (ret == nullptr)
				return false;
			ret->_status = Delete;
			_n -= 1;
			return true;
		}
		bool insert(const pair<K,V>& kv)
		{
			Node* ret = find(kv.first);
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				close_hashtable<K, V> tmp;
				tmp._tables.resize(newsize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					tmp.insert(_tables[i]._kv);
				}
				_tables.swap(tmp._tables);
			}
			size_t start = kv.first % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status == Exist)
			{
				i++;
				index = start + i;
				index %= _tables.size();
			}
			_tables[index]._kv = kv;
			_tables[index]._status = Exist;
			_n += 1;
			return true;
		}
	};
}

以上就是闭散列的实现。我们来一步一步的解析以上代码。

(1) 用枚举常量来标记哈希表中每个位置的状态，状态有空，不为空，被删除。

大家可能会对被删除这个状态产生疑问，一个位置不就是有数据和没数据吗？主要是大家想如果直接物理上删除，把位置状态设置为空，那么就会影响后面的数据。

比如：删除 5 这个数据、

直接将 5 的位置设置为空，那么 15 这个数据会受到影响。因为对哈希表大小取模后，等于 5 的不一定只有 5，还有 15，25，35。如果将 5位置直接设置为空，就相当于后面的数据中已经没有 15，25，35 了。具体我们往下看查找的实现。

    enum status
	{
		Empty,
		Exist,
		Delete
	};

(2) 哈希表中的数据类型，以及哈希表的底层结构

哈希表中的数据类型，是一个结构体，包括了一个键值对和状态：

template<class K,class V>
	struct hashdate
	{
		pair<K, V> _kv;
		// 默认状态为空
		status _status = Empty;
	};

哈希表的底层结构，可以是一个数组，还得有一个无符号整数用来处理哈希表中数据的个数：

	typedef hashdate<K, V> Node;
	private:
		vector<Node> _tables;
		size_t _n = 0;

(3) 哈希表的查找

        Node* find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			size_t start = key % _tables.size();
			size_t i = 0;
			size_t index = start + i;

			while (_tables[index]._status != Empty)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
					return &_tables[index];
				i++;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}

注意： while循环中，它的条件是 _tables[index]._status != Empty 说明即使当下位置状态是 Delete 也会往后找要查找的数据。这也解释了上文中所述。

找到了的条件是 (_tables[index]._kv.first == key && _tables[index]._status == Exist)

找到了返回数据的地址，找不到返回空。

(4) 哈希表的插入

        bool insert(const pair<K,V>& kv)
		{
		    // 去重
			Node* ret = find(kv.first);
			if (ret)
			{
				return false;
			}
            // 扩容，后面讲，大家可能对这个条件有疑问
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				close_hashtable<K, V> tmp;
				tmp._tables.resize(newsize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					tmp.insert(_tables[i]._kv);
				}
				_tables.swap(tmp._tables);
			}
			size_t start = kv.first % _tables.size();
			size_t i = 0;
			size_t index = start + i;
            // 找空的位置
			while (_tables[index]._status == Exist)
			{
				i++;
				index = start + i;
				index %= _tables.size();
			}
            // 插入操作
			_tables[index]._kv = kv;
			_tables[index]._status = Exist;
			_n += 1;
			return true;
		}

扩容是有说法的，首先我们要知道什么时候需要扩容？

如果为空，必然需要扩容，默认给 10 个大小即可。
当有效数据个数除以数组大小大于等于 0.7 时，需要扩容

其实有效数据个数除以数组大小被称为载荷因子，当载荷因子大于 0.7时，就说明需要扩容了。这是大佬们搞出来的，我们还需要知道，载荷因子越大就说明填入哈希表的元素越多，越可能发送哈希冲突。

扩容的操作，我是创建了一个新的哈希表，然后把原表中的数据插入到新表中。这里还有一个坑，就是，可不可以直接将旧表的数据拷贝到新表中，答案是不行。

举个例子：

原表是：

新表是：

直接拷贝的话是这样的：

看图也懂了哈，扩容后的表是需要重新插入数据，因为位置可能会发送改变。

扩容完了，就是插入了，如果当下的位置是 Delete 或者 Eempty 那么就可以直接插入；否则就需要向后面查找空的位置，进行插入。

(5) 哈希表的删除

        bool erase(const K& key)
		{
			Node* ret = find(key);
			if (ret == nullptr)
				return false;
			ret->_status = Delete;
			_n -= 1;
			return true;
		}

删除很简单，就是将那个位置的状态改为 Delete，然后有效数据个数减一就行了。

3.1.1 闭散列的细节

首先，上面的哈希表其实还有问题。

比如：不是所有的数据都可以取模，这个问题，并没有解决，上面实现是直接取模。

所以还需要实现一个将数据转为可哈希数据的仿函数。为什么是仿函数呢？因为数据类型较多，情况不一，这里还用到了模板特化的知识，大家坐稳扶好。

    template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& key)
		{
			size_t value = 0;
			for (auto ch : key)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}
	};

第二个就是模板的特化，它的作用就是将string对象可以转换成整型(可哈希)。至于为什么每次都乘以 31 ，这也是大佬的手法，因为多次测试后发现，乘以 31 会使哈希冲突少一些。

默认情况下，就是直接返回 key，也就是默认情况下都是可哈希的。

如果你要哈希一个自定义对象，那么还得是用模板的特化，自己处理。

所以有了仿函数之后，我们就不必担心，传过去的数据是否能够被哈希了，靠仿函数去处理。具体怎么用，后面会给出完整代码。

其次，还有一个问题，就是线性探索和二次探索：

大家可能对这俩词不陌生，也就是哈希表中，发生哈希冲突后，查找空位置时，是连续的查找空位置还是平方次的跳跃的查找。

当然是二次查找更优秀一些，上面的程序用的是线性探索，也就是那个 i++，它就是连续的往后查找。为什么呢？因为如果是线性探索，它会比较拥挤，连续位置太多，从而引发踩踏效应，也就导致，每次来的数据，都需要去找空位置。

二次探索很简单，把 i++ 变成 i =i *i。

3.1.2 优化后的闭散列

enum status
	{
		Empty,
		Exist,
		Delete
	};
	template<class K>
	struct Hash
	{
		size_t operator()(const K& key)
		{
			return key;
		}
	};
	template<>
	struct Hash<string>
	{
		size_t operator()(const string& key)
		{
			size_t value = 0;
			for (auto ch : key)
			{
				value *= 31;
				value += ch;
			}
			return value;
		}
	};
	template<class K,class V>
	struct hashdate
	{
		pair<K, V> _kv;
		status _status = Empty;
	};
	template<class K,class V,class Hashfunc = hash<K>>
	class close_hashtable
	{
		typedef hashdate<K, V> Node;
	private:
		vector<Node> _tables;
		size_t _n = 0;
	public:
		Node* find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			Hashfunc hf;
			size_t start = hf(key)% _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status != Empty)
			{
				if (_tables[index]._kv.first == key && _tables[index]._status == Exist)
					return &_tables[index];
				i = i*i;
				index = start + i;
				index %= _tables.size();
			}
			return nullptr;
		}
		bool erase(const K& key)
		{
			Node* ret = find(key);
			if (ret == nullptr)
				return false;
			ret->_status = Delete;
			_n -= 1;
			return true;
		}
		bool insert(const pair<K,V>& kv)
		{
			Node* ret = find(kv.first);
			if (ret)
			{
				return false;
			}
			if (_tables.size() == 0 || _n * 10 / _tables.size() >= 7)
			{
				size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				close_hashtable<K, V> tmp;
				tmp._tables.resize(newsize);
				for (size_t i = 0; i < _tables.size(); i++)
				{
					tmp.insert(_tables[i]._kv);
				}
				_tables.swap(tmp._tables);
			}
			Hashfunc hf;
			size_t start = hf(kv.first) % _tables.size();
			size_t i = 0;
			size_t index = start + i;
			while (_tables[index]._status == Exist)
			{
				i = i*i;
				index = start + i;
				index %= _tables.size();
			}
			_tables[index]._kv = kv;
			_tables[index]._status = Exist;
			_n += 1;
			return true;
		}
	};

3.2 扩散列(哈希桶)

template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;
		HashNode(const pair<K, V>& kv)
			:_kv(kv),
			_next(nullptr)
		{
		}
	};
	template<class K,class V,class Hashfunc = Hash<K>>
	class link_hashtable
	{
		typedef HashNode<K, V> Node;
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	public:
		Node* find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			Hashfunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}
		bool erase(const K& key)
		{
			Node* ret = find(key);
			if (ret == nullptr)
			{
				return false;
			}
			Hashfunc hf;
			size_t index = hf(key) % _tables.size();
			Node* pre = nullptr;
			Node* cur = _tables[index];
			while (cur)
			{
				Node* next = cur->_next;
				if (cur->_kv.first == key)
				{
					if (pre == nullptr)
					{
						_tables[index] = next;
					}
					else
					{
						pre->_next = next;
					}
					delete cur;
					_n -= 1;
					return true;
				}
				else
				{
					pre = cur;
					cur = next;
				}
			}
			return false;
		}
		bool insert(const pair<K,V>& kv)
		{
			Node* ret = find(kv.first);
			if (ret)
			{
				return false;
			}
			Hashfunc hf;
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = hf(cur->_kv.first) % newTables.size();
						// 头插
						cur->_next = newTables[index];
						newTables[index] = cur;
						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;
		}
	};
}

(1) 哈希桶的节点以及底层结构

哈希桶的节点是一个单向链表，它得有数据，是一个键值对，还得有下一个节点的指针。

template<class K,class V>
	struct HashNode
	{
		pair<K, V> _kv;
		HashNode<K,V>* _next;
		HashNode(const pair<K, V>& kv)
			:_kv(kv),
			_next(nullptr)
		{
		}
	};

哈希桶的底层，是一个数组，数组中存的是节点的指针，当然还得有一个有效数据的个数，它是用于判断是否需要扩容的。

template<class K,class V,class Hashfunc = Hash<K>>
	class link_hashtable
	{
		typedef HashNode<K, V> Node;
	private:
		vector<Node*> _tables;
		size_t _n = 0;
	public:
	}

(2) 哈希桶的查找

查找也简单呢，就是迭代往下查找，如果找到就返回，位置的指针，找不到就返回空。

        Node* find(const K& key)
		{
			if (_tables.size() == 0)
				return nullptr;
			Hashfunc hf;
			size_t index = hf(key) % _tables.size();
			Node* cur = _tables[index];
			while (cur)
			{
				if (cur->_kv.first == key)
					return cur;
				else
					cur = cur->_next;
			}
			return nullptr;
		}

(3) 哈希桶的插入

       bool insert(const pair<K,V>& kv)
		{
			Node* ret = find(kv.first);
			if (ret)
			{
				return false;
			}
			Hashfunc hf;
			if (_n == _tables.size())
			{
				size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;
				vector<Node*> newTables;
				newTables.resize(newSize);
				for (size_t i = 0; i < _tables.size(); ++i)
				{
					Node* cur = _tables[i];
					while (cur)
					{
						Node* next = cur->_next;
						size_t index = hf(cur->_kv.first) % newTables.size();
						// 头插
						cur->_next = newTables[index];
						newTables[index] = cur;
						cur = next;
					}
                    // 将旧桶置空
					_tables[i] = nullptr;
				}
				_tables.swap(newTables);
			}
			size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;
		}

先考虑插入的数据的key有没有重复，如果重复了那就直接返回。其实就是个头插，中间代码很多是扩容，我们先不考虑扩容，其实插入的代码就是：

           size_t index = hf(kv.first) % _tables.size();
			Node* newnode = new Node(kv);
			newnode->_next = _tables[index];
			_tables[index] = newnode;

扩容的话，和哈希表同理，扩完容之后，哈希桶的位置可能会变化，所以要自己完成重新插入工作，不过扩容的条件不再是载荷因子 >=0.7，而是载荷因子等于 1时才扩容。

(4) 哈希桶的删除

        bool erase(const K& key)
		{
			Node* ret = find(key);
			if (ret == nullptr)
			{
				return false;
			}
			Hashfunc hf;
			size_t index = hf(key) % _tables.size();
            // 前一个节点
			Node* pre = nullptr;
			//桶的第一个节点
			Node* cur = _tables[index];
			while (cur)
			{
			    // 桶的下一个节点
				Node* next = cur->_next;
                // 找到要删除的节点
				if (cur->_kv.first == key)
				{
				    // 头删
					if (pre == nullptr)
					{
						_tables[index] = next;
					}
					// 中间删或者尾删
					else
					{
						pre->_next = next;
					}
					delete cur;
					_n -= 1;
					return true;
				}
				else
				{
				    // 往桶下面迭代
					pre = cur;
					cur = next;
				}
	        }
		}

一上来先检查要删除的数据是否存在，存在就往下走，不存在直接返回。

然后就是找要删除的数据在那个桶中：

            Hashfunc hf;
			size_t index = hf(key) % _tables.size();

再就是在这个桶中删除，我们需要考虑几件事:

桶中是单向链表，删除的话我需要维护链表的关系，所以需要记录删除数据的前一个数据
要删除的节点如果是头节点，就不需要维护和前一个数据的关系，因为它就是第一个
要删除的节点在中间或者最后，那就需要维护和前一个的关系

3.2.1 扩散列的细节

扩散列是有极端情况的，比如我开辟的数组大小是 10 ，插入的数据是 10，20，30，40，50，60 …… 10000000000，这些数据都插入到了一个桶里面。

会导致哈希桶变成这样：

会发现，效率退化了，哈希的查找一般情况是O(1) ，但是这种情况下，退化成O(n)了。所以应该怎么办？大佬其实是给出解决方案的，就是一个桶中的元素超过了某一个量，那么就会将这个桶中的数据用红黑树组织起来，对于这个量jave和C++还不一样。

这就是所谓的桶中种树。

但是上面的哈希桶，我没有支持这种高级操作，我觉得只要了解这个事情就行了，至于实现，也是可以的，但是对于我们要学习哈希，没太大帮助。

4. 哈希表和哈希桶的比较

哈希桶处理溢出，需要增设链接指针，似乎增加了存储开销。

事实上：由于哈希表必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

哈希表处理哈希冲突用的是抢占别的位置，可能会导致数据比较阻塞，也就是每进来一个数据都需要去抢占别人的位置。

哈希桶处理哈希冲突用的是在冲突位置，增加链节点的方法，但是有可能造成，单向链表太长从而影响效率，所以需要将单向链表变为红黑树管理起来。

5. 结尾语

学完哈希，能干什么？说实话哈希很重要，学数据结构，你说你不会哈希，那么就相当于你白学数据结构了，就是这么夸张哈，以后工作也会大量用到哈希的。所以大家加油。在我的下一篇文章中，会利用哈希桶去实现unordered_map和unordered_set，也算是用上了哈希。当然位图呀，布隆过滤器呀，海量处理数据等都会用到哈希。

到此这篇关于C语言哈希表概念超详细讲解的文章就介绍到这了,更多相关C语言哈希表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

哈希表实验C语言版实现

复制代码代码如下: /* 数据结构C语言版哈希表 */#include <stdio.h>#include <malloc.h>#define NULLKEY 0 // 0为无记录标志 #define N 10 // 数据元素个数 typedef int KeyType;// 设关键字域为整型 typedef struct{ KeyType key; int ord;}ElemType; // 数据元素类型 // 开放定址哈希表的存储结构 int hashsize[]={11
C语言数据结构哈希表详解

/* * 程序名:hash.c,此程序演示哈希表的实现,数据元素单链表带头结点. * */ #include <stdio.h> #include <stdlib.h> #include <string.h> // 哈希表中数据元素的结构体. typedef struct Element { unsigned int key; // 关键字. int value; // 数据元素其它数据项,可以是任意数据类型. // char value[1001]; // 数据元素其
C语言基于哈希表实现通讯录

本文为大家分享了C语言基于哈希表实现通讯录的具体代码,供大家参考,具体内容如下 1．需求分析本演示程序用C语言编写,完成哈希表的生成,电话号码的插入.以及查找等功能. (1)按提示输入相应的联系人的相关资料: (2)以相应的输出形式输出所存储的的联系人的资料: (3)程序可以达到建立.添加.查找.打印的功能: (4)程序可以判断用户输入的非法数据并引导正确的输入. 2．概要设计存储电话号码的记录时,若在存储位置和其关键字之间建立某种确定的对应关系使得每个关键字和存储结构中一个唯一的存储位置相
C语言哈希表概念超详细讲解

目录 1. 哈希概念 2. 哈希冲突 3. 哈希实现 3.1 闭散列(哈希表) 3.1.1 闭散列的细节 3.1.2 优化后的闭散列 3.2 扩散列(哈希桶) 3.2.1 扩散列的细节 4. 哈希表和哈希桶的比较 5. 结尾语 1. 哈希概念哈希其实在学排序时已经用过了,就是计数排序.计数排序也是用的一种映射关系. 比如对此数组进行计数排序 :1 1 9 9 9 3 3 8 8 我用的是绝对映射 ,所以开辟的数组空间它的大小必须能映射到最大的元素. 但是对于哈希来讲,可以用决定映射
C语言折半查找法的超详细讲解

折半查找法仅适用于对已有顺序的数组.数据进行操作!!!(从小到大)自我总结:折半查找法就是相当于(通过改变low或high的大小)把中间位置指到了key那个数那里,所以mid应该处于循环里面,即mid=(high+low)/2.注意:low,mid,high都要与下标绑定,也就是说它们就是下标.且循环条件是:high>=low. 同时注意:⑴若原来数组是由小到大排列的则: mid=(high+low)/2; if(key<a[mid])//说明要找的值在左边
C语言超详细讲解数据结构中的线性表

目录前言一.分文件编写 1.分文件编写概念 2.代码展示二.动态分布内存malloc 1.初识malloc 2.使用方法三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据四.代码展示与运行效果 1.代码展示 2.运行效果总结前言计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,
C语言超详细讲解指针的概念与使用

目录一.指针与一维数组 1. 指针与数组基础 2. 指针与数组 3. 一个思考二.指针与字符串三.指针和二维数组 1. 指针数组与数组指针 2. 指针数组 3. 数组指针一.指针与一维数组 1. 指针与数组基础先说明几点干货: 1. 数组是变量的集合,并且数组中的多个变量在内存空间上是连续存储的. 2. 数组名是数组的入口地址,同时也是首元素的地址,数组名是一个地址常量,不能更改. 3. 数组的指针是指数组在内存中的起始地址,数组元素的地址是指数组元素在内存中的其实地址. 对于第一点数
C语言超详细讲解顺序表的各种操作

目录顺序表是什么顺序表的结构体顺序表的接口函数顺序表相关操作的菜单顺序表的初始化添加元素陈列元素往最后加元素往前面加元素任意位置加元素删除最后元素删除前面元素删除任意元素整体代码(fun.h部分) 整体代码(fun.cpp部分) 整体代码(主函数部分) 结果展示顺序表是什么顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素.使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数
C语言超详细讲解线性表

目录 1. 顺序表 1.1 管理结点 1.2 顺序表的插入 1.3 顺序表的删除 1.4 顺序表的扩容 2. 链表 2.1 定义 2.2 头部插入 2.3 尾部插入 2.4 任意位置插入 2.5 任意位置删除 2.6 虚头结点 1. 顺序表顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构.此种存储方式使得顺序表的物理结构与逻辑结构都是连续的. 与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用ulimit -s查看系统限制的大小,单位为KB),因此顺序表往往使用
C语言数据结构超详细讲解单向链表

目录 1.链表概况 1.1 链表的概念及结构 1.2 链表的分类 2. 单向链表的实现 2.1 SList.h(头文件的汇总,函数的声明) 2.2 SList.c(函数的具体实现逻辑) 2.2.1 打印链表 2.2.2 搞出一个新节点(为其他函数服务) 2.2.3 链表尾插 2.2.4 链表头插 2.2.5 链表尾删 2.2.6 链表头删 2.2.7 查找节点 2.2.8 在pos位置之前插入 2.2.9 在pos位置之后插入 2.2.10 删除pos位置 2.2.11 删除pos之后位置 2.
C语言超详细讲解数据结构中双向带头循环链表

目录一.概念二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表三.主要功能 3.1.在pos节点前插入数据尾插头插 3.2.删除pos处节点数据尾删头删 3.3.查找数据四.总代码 List.h 文件 List.c 文件 Test.c 文件五.拓展一.概念前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带
C语言超详细讲解栈的实现及代码

目录前言栈的概念栈的结构栈的实现创建栈结构初始化栈销毁栈入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空总代码 Stack.h 文件 Stack.c 文件 Test.c 文件前言栈的概念栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入
C语言超详细讲解队列的实现及代码

目录前言队列的概念队列的结构队列的应用场景队列的实现创建队列结构队列初始化队列销毁入队列出队列队列判空获取队列元素个数获取队列头部元素获取队列尾部元素总代码 Queue.h 文件 Queue.c 文件 Test.c 文件前言队列的概念队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾出队列:进行删除操作的一端称为队头队列和前文所学的栈