c#中位圖算法及其應用的示例分析

這篇文章給大家分享的是有關c#中位圖算法及其應用的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

• 位圖算法

    位圖法就是bitmap的縮寫，所謂bitmap，是用每一位來存放某種狀態，適用于大規模數據，但數據狀態又不是很多的情況。通常是用來判斷某個數據存不存在的。

• 應用

 1.給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。

  解決方法：申請512M的內存一個bit位代表一個unsigned int值讀入40億個數，設置相應的bit位讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。

   2.使用位圖法判斷×××數組是否存在重復

    解決辦法：判斷集合中存在重復是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然后再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到 5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重復。這種給新數組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。

    3.使用位圖法進行×××數組排序

  解決辦法：

 首先遍歷數組，得到數組的最大最小值，然后根據這個最大最小值來縮小bitmap的范圍。這里需要注意對于int的負數，都要轉化為unsigned int來處理，而且取位的時候，數字要減去最小值。

應用1代碼實現：

#pragma once
#include<vector>
template<class T>
struct DataType
{
	long long operator()(const T&key)
	{
		return key;
	}
};
template<class T>
struct StringType
{
	long long operator()(const string&key)
	{
		long long size = 0;
		for (int i = 0; i < key.size(); i++)
		{
			size += key[i];
		}
		return size;
	}
};
template<class T,class BMFunc=DataType<T>>
class BitMap
{
public:
	BitMap(size_t size = 1)
	{
		_a.resize(size / 32 + 1);
	}
	~BitMap(){}
	void set(T &x)
	{
		BMFunc bmf;
		size_t index = bmf(x)/ 32;
		size_t num = bmf(x) % 32;
		if (!(_a[index] & (1 << num)))
		{
			_a[index] |= (1 << num);
			_size++;
		}
		
	}
	void Reset(T x)
	{
		BMFunc bmf;
		size_t index = bmf(x) / 32;
		size_t num = bmf(x) % 32;
		if (!(_a[index] & (1 << num)))
		{
			_a[index] &= (~(1 << num));
			_size--;
		}
	}
	bool Test(T x)
	{
		BMFunc bmf;
		size_t index = bmf(x)/ 32;
		size_t num = bmf(x)% 32;
		return _a[index] &(1 << num);
	}
protected:
	vector<size_t> _a; 
	size_t _size;
};

應用2代碼實現：

bool hasDuplicatedItem(int *a, int len)
{
	int length, max, i;
	length = len;
	max = a[0];
	for (i = 1; i < length; i++){
		if (a[i] > max)
			max = a[i];
	}
	int *arr;
	arr = (int*)malloc(sizeof(int)* (max + 1));
	for (i = 0; i < length; i++){
		if (arr[a[i]])
			return true;
		else
			arr[a[i]] = 1;
	}
	return false;
}

應用3代碼實現：

void bitmapSort(int *a, int len)
{
	int length, max, min, i, index;
	length = len;
	min = max = a[0];
	//找出數組最大值
	for (i = 1; i < length; i++){
		if (a[i] > max){
			max = a[i];
		}
		if (min > a[i]) {
			min = a[i];
		}
	}
	//得到位圖數組
	int *arr;
	arr = (int*)malloc(sizeof(int)* (max - min + 1));
	for (i = 0; i < length; i++){
		index = a[i] - min;
		arr[index]++;
	}
	//重整a中的元素
	int arr_length;
	arr_length = max - min + 1;
	index = 0;
	for (i = 0; i < arr_length; i++){
		while (arr[i] > 0){
			a[index] = i + min;
			index++;
			arr[i]--;
		}
	}
}

感謝各位的閱讀！關于“c#中位圖算法及其應用的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！