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

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

阅读量：3656 次

发布时间：2019-05-21

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

#include 
   
    #include 
    
     using namespace std;/*问题:使用链表，生成[0 ,maxval]范围内m各随机整数的有序序列分析：这是典型的插入排序。每次将一个带插入的元素插入到前面已经排好序的结果中。      1】先查找到待插入位置，2】修改结点指针指向输入: 100(元素最大值) 10(输出的元素个数) 输出; 输出10个0~100且有序的元素 */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 );  }  template
     
      class IntSetList{public:	IntSetList(int maxVal)	{		_maxVal = maxVal;		_head = NULL;		_n = 0;	}	void setHead(Node* head)	{		_head = head;		_n = 1;	}	~IntSetList()	{		deleteList();	}	void deleteList()	{		Node* node = _head;		//每个结点先要寻找到下一个指针，再删除		while(node)		{			Node* nextNode = node->_next;			delete(_head);			node = nextNode;		}	}	void insert(T value)	{		//如果没满，先寻找插入的位置(必须确保不重复)，然后修改指针指向		Node* node = _head;		Node* previousNode = NULL;		while(node)		{			if(node->_value < value)			{				previousNode = node;				node = node->_next;			}			//重复，不插入，直接返回			else if(node->_value == value)			{				return;			}			//这里说明找到了不重复的元素，插入			else			{				//如果不是首次插入				if(previousNode)				{					Node* newNode = new Node();					newNode->_value = value;					previousNode->_next = newNode;					newNode->_next = node;					_n++;					return;				}				//如果是首次插入，需要修改头结点指针				else				{					Node* newNode = new Node();					newNode->_value = value;					newNode->_next = _head;					_head = newNode;					_n++;					return;				}			}		}		//走到这里说明：待插入的元素恰好是在链表尾部，需要插入		Node* newNode = new Node();		newNode->_value = value;		previousNode->_next = newNode;		_n++;	}	int size()	{		return _n;	}public:	Node* _head;//头指针	//int _maxSize;//链表本来就是适用结点数量未知的情形	int _maxVal;	int _n;//记录当前有多少个结点};void print(IntSetList
      
        list){	Node* head = list._head;	while(head)	{		cout << head->_value << " ";		head = head->_next;	}	cout << endl;}void process(){	int maxVal;	int maxSize;	while(cin >> maxVal >> maxSize)	{		IntSetList
       
         intSetList(maxVal);		while(intSetList.size() < maxSize)		{			int value = randRange(0 , maxVal);			//非首次插入			if(intSetList.size() > 0)			{				intSetList.insert(value);			}			//首次插入，需要建立头结点			else			{				Node* head = new Node();				head->_value = value;				intSetList.setHead(head);			}		}		print(intSetList);	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}