全部资源
全部资源
C/C++
C#
PHP
Java
Python
VB
ASP
Html/CSS
Matlab
JavaScript
数据库
模板
其他

好朋友插队算法

收藏(0)
  • 大小: 4.45MB
    文件类型: .zip
    金币: 1
    下载: 0 次
    发布日期: 2023-11-16
  • 语言: 其他
  • 标签: 插队  
高速下载

资源简介

好朋友之间的插队，用哈希表数据结构来实现的

资源截图

小图 大图

代码片段和文件信息 

/*
本实验假设售票大厅有多个售票窗口，无论到哪个窗口买票都必须排队，但是新来的人不一定排在队尾，允许插队（即直接排在朋友的后面）。
假设已经在排队的人不会离开，也不会移到其他队伍去。买到票的人依次出队。每个人仅买一次票，买完票就离开。每个人都有名字。
每个来买票的人先进行观察判断：
　1．如果所有的队伍中都没有发现朋友，则选择最短的队伍排在其队尾；
 2．如果所有的队伍中仅发现一个朋友，则可以（不是必须）插在此朋友的后面；但是，插队前应考查是否合算，
 插入此位置离售票窗口的距离（即队伍前面的人数）必须小于其他队伍的长度，否则应选择最短的队伍排在其队尾；
 　3．如果所有的队伍中发现多个朋友，这种情况就比较复杂：
  　　（1）	如果多个朋友是集中在一个队伍里，则可以插在最后那个朋友的后面；
	　　（2）	如果多个朋友是分散在多个队伍里，则插队的原则是离售票窗口最近；
	  　4．如果朋友排在队伍的第一位（即队首），则不允许插队；
	   　
		本实验要求编写程序模拟这种排队买票时允许插队的情形。要求程序中应用散列表来存放和查找数据，应用求余法构造合理的散列函数
		，应用平方探测法来解决Hash映射的冲突现象。程序可能需要四个文本文件：
		　（1）初始化文件input.txt，包含售票窗口及其购票队伍的初始设置
		 　（2）朋友组文件friend.txt，同一个名字也可能出现在不同的组
		  （3）来购票的人的完整名单people.txt，其中包含出现在friend.txt中的名字；文件中名字的顺序表示不同的到来顺序；
		  文件中每行有一个名字，如果某行有多个名字则表示他们同时到达售票厅（这是比较复杂的情形）
		  （4）售票结果文件output.txt（按售票窗口分组显示），可以考虑各窗口卖票的节奏（即售票员的售票速度）

		  本实验训练的内容包括六个方面：
		  　1.面向对象程序设计方法，类模板的应用；
		   　2.散列表（Hash Table）的应用，队列（或链表）的应用；
			　3.应用求余法构造合理的散列函数；
			 　4.应用平方探测法解决Hash映射的冲突现象；
			  　5.文件的读写操作；
			   6.程序测试计划、用例的设计和测试方法。
			   */
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int window_number=4;
const int max_friend_group=100;

class Hash_
{
private:
	int what_group;      //该人所在的朋友组号
	string name;      
	int times;   //同名冲突次数
	bool is_NULL;   //判断该存储位置是否为空

public:
	Hash_（）;
	~Hash_（）;
	void set_what_group（int what_group）;
	void set_name（string name）;
	void set_is_NULL（bool is_NULL）;
	string get_name（）;
	bool get_is_NULL（）;
	int get_what_group（）;
	int get_times（）{return times;}

	void add_times（）;
};
Hash_::Hash_（）
{
	what_group=-1;
	name=““;
	times=0;
	is_NULL=true;
}

Hash_::~Hash_（）
{
}
int Hash_::get_what_group（）
{
	return what_group;
}
bool Hash_::get_is_NULL（）
{
	return is_NULL;
}
void Hash_::set_is_NULL（bool is_NULL）
{
	this->is_NULL=is_NULL;
}
void Hash_::set_name（string name）
{
	this->name=name;
}
void Hash_::set_what_group（int what_group）
{
	this->what_group=what_group;
}
string Hash_::get_name（）
{
	return name;
}
void Hash_::add_times（）
{
	times++;
}


class Queue;
class Hash_Table
{

public:
	Hash_ _Hash[100];
	Hash_Table（）;
	~Hash_Table（）;
	//friend bool Queue::find_myself_position（string nameint what_window）;   
	void set_size（）;
	int get_Hash_Value（string str）;         //取得哈希函数对应的哈希值
	void create_Hash_Table（）;       //构建哈希表
	void deal_Conflict（int positionstring strHash_ &_hash）;             //平方探测法解决冲突
};
Hash_Table::Hash_Table（）
{
}
Hash_Table::~Hash_Table（）
{
}
int Hash_Table::get_Hash_Value（string str）  
{  
	int b = 551;  
	int a = 689;  
	long hash = 0;  
	string::iterator _it;
	for（_it=str.begin（）;_it!=str.end（）;_it++）  
	{  
		hash = hash * a + （*_it）*10;
		a    = a * b;  
	}  
	return hash%97;  
}  

void Hash_Table::deal_Conflict（int positionstring strHash_ &_hash）
{
	int i;
	if（_Hash[position].get_name（）==str）
		_Hash[position].add_t

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-05-15 00:17  来插队吧\
     目录           0  2013-05-15 00:16  来插队吧\Debug\
     文件      172544  2013-05-15 00:16  来插队吧\Debug\来插队吧.exe
     文件      700096  2013-05-15 00:16  来插队吧\Debug\来插队吧.ilk
     文件     1502208  2013-05-15 00:16  来插队吧\Debug\来插队吧.pdb
     目录           0  2013-05-14 23:50  来插队吧\来插队吧\
     文件       10599  2013-05-15 00:17  来插队吧\来插队吧\1.cpp
     文件        3341  2013-05-14 22:09  来插队吧\来插队吧\1.dsp
     文件         510  2013-05-14 22:10  来插队吧\来插队吧\1.dsw
     文件       41984  2013-05-14 22:10  来插队吧\来插队吧\1.ncb
     文件       48640  2013-05-14 22:10  来插队吧\来插队吧\1.opt
     文件         678  2013-05-14 22:10  来插队吧\来插队吧\1.plg
     目录           0  2013-05-15 00:16  来插队吧\来插队吧\Debug\
     文件      622654  2013-05-14 22:09  来插队吧\来插队吧\Debug\1.exe
     文件      870000  2013-05-14 22:10  来插队吧\来插队吧\Debug\1.ilk
     文件      689038  2013-05-15 00:16  来插队吧\来插队吧\Debug\1.obj
     文件     3562652  2013-05-14 22:09  来插队吧\来插队吧\Debug\1.pch
     文件     1229824  2013-05-14 22:09  来插队吧\来插队吧\Debug\1.pdb
     文件        7756  2013-05-15 00:16  来插队吧\来插队吧\Debug\CL.read.1.tlog
     文件         210  2013-05-15 00:16  来插队吧\来插队吧\Debug\CL.write.1.tlog
     文件         522  2013-05-15 00:16  来插队吧\来插队吧\Debug\cl.command.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link-cvtres.read.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link-cvtres.write.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link-rc.read.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link-rc.write.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172-cvtres.read.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172-cvtres.write.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172-rc.read.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172-rc.write.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172.read.1.tlog
     文件           2  2013-05-15 00:16  来插队吧\来插队吧\Debug\link.2172.write.1.tlog
............此处省略84个文件信息

评论

共有 条评论