编程珠玑： 13章搜索 13.4使用整数结构，生成[0 ,maxval]范围内m各随机整数的有序序列 -------解题总结-白红宇

编程珠玑： 13章搜索 13.4使用整数结构，生成[0 ,maxval]范围内m各随机整数的有序序列 -------解题总结

阅读量：3658 次

发布时间：2019-05-21

本文共 3197 字，大约阅读时间需要 10 分钟。

#include 
   
    #include 
    
     using namespace std;/*问题:使用箱子和链表，生成[0 ,maxval]范围内m各随机整数的有序序列分析：采用比如4个相似，将元素划分到每个箱子中，每个箱子内部用链表表示。		等同于是对链表的优化输入: 100(元素最大值) 10(输出的元素个数) 输出; 输出10个0~100且有序的元素 关键：1 采用比如4个相似，将元素划分到每个箱子中，每个箱子内部用链表表示。		等同于是对链表的优化2 插入元素：首先计算元素应该在哪个箱子中：这里让数据除以箱子的个数取余来确定分配的箱子，这样无法确保后面打印时候有序	箱子编号 = 插入值* 箱子个数 / 最大值，这样会导致溢出，上下同除一箱子个数，为防止除数为0，箱子个数加1,: 	箱子编号 = 插入值 / (1 + 最大值 / 箱子个数)*/typedef struct Node{	Node():_next(NULL){}	Node* _next;	int _value;}Node;int randRange(int min ,int max)  {      if(min > max)      {          int temp = min;          min = max;          max = min;      }      return ( rand() % (max - min + 1) + min );  }  const int BIN_NUM = 4;template
     
      class SetIntBins{public:	SetIntBins(int maxVal)	{		_maxVal = maxVal;		_binNum = BIN_NUM;		_n = 0;		_bins = new Node*[_binNum];		//需要为每个箱子设置头结点，		for(int i = 0 ; i < _binNum ; i++)		{			_bins[i] = new Node();			_bins[i]->_value = maxVal;		}	}	void deleteList(Node* head)	{		while(head)		{			Node* nextNode = head->_next;			delete head;			head = nextNode;		}	}	~SetIntBins()	{		//删除所有箱子		for(int i = 0 ; i < _binNum ; i++)		{			deleteList(_bins[i]);		}		delete _bins;	}	/*插入元素：首先计算元素应该在哪个箱子中：这里让数据除以箱子的个数取余来确定分配的箱子，这样无法确保后面打印时候有序	箱子编号 = 插入值* 箱子个数 / 最大值，这样会导致溢出，上下同除一箱子个数，为防止除数为0，箱子个数加1,: 	箱子编号 = 插入值 / (1 + 最大值 / 箱子个数)	*/	void insert(T value)	{		//int binIndex = value % _binNum; // 		int binIndex =  value / ( 1 + _maxVal / _binNum);		//然后插入到对应箱子的链表中		Node* head = _bins[binIndex];		//如果箱子首结点的下一个结点为空，说明是第一次插入需要直接插入		if(!head->_next)		{			Node* newNode = new Node();			newNode->_value = value;			head->_next = newNode;			_n++;		}		else		{			insertNode(value , head->_next , head);		}	}	void insertNode(T value , Node* node , Node* previousNode)	{		//如果没满，先寻找插入的位置(必须确保不重复)，然后修改指针指向		while(node)		{			if(node->_value < value)			{				previousNode = node;				node = node->_next;			}			//重复，不插入，直接返回			else if(node->_value == value)			{				return;			}			//这里说明找到了不重复的元素，插入			else			{				Node* newNode = new Node();				newNode->_value = value;				previousNode->_next = newNode;				newNode->_next = node;				_n++;				return;			}		}		//走到这里说明：待插入的元素恰好是在链表尾部，需要插入		Node* newNode = new Node();		newNode->_value = value;		previousNode->_next = newNode;		_n++;	}	int size()	{		return _n;	}	//如果是按照除以箱子个数取余，那么最后输出结果的时候，无法知道顺序。只能用比如0~99:分配第一个箱子存放0~24这种	void report(int* v)	{		if(NULL == v)		{			return;		}		int j = 0;		for(int i = 0 ; i < _binNum ; i++)		{			Node* head = _bins[i]->_next;			while(head)			{				v[j++] =  head->_value;				head = head->_next;			}		}	}public:	int _binNum;	Node** _bins;//若干个箱子，每个箱子中存放的是结点指针	int _maxVal;	int _n;};void print(int* v , int size){	if(NULL == v || size <= 0)	{		cout << "No result" << endl;	}	else	{		for(int i = 0 ; i < size; i++)		{			cout << v[i] << " ";		}		cout << endl;	}}void process(){	int maxVal;	int maxSize;	while(cin >> maxVal >> maxSize)	{		int* array = new int[maxSize + 1];		SetIntBins
      
        intSetBins(maxVal);		while(intSetBins.size() < maxSize)		{			int value = randRange(0 , maxVal);			intSetBins.insert(value);		}		intSetBins.report(array);		print(array , maxSize);		delete[] array;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}