生日相同问题,C语言编程,用字典结构解决,求解啊速度~~~
发布网友
发布时间：2022-05-10 09:04
共3个回答
懂视网
时间：2022-05-10 13:25
也叫散列表,最大的特点是通过key来查找其对应的值其时间复杂度是O(1).
在Python中怎样用列表实现字典?
用列表实现字典最大的问题就是解决hash冲突,如果在列表中通过计算不同的key得到相同的相同了位置,这时候应该怎么办？
最简单的办法就是使用拉链法.
拉链法:就是在一个列表中每个位置再添加一个列表,这样就算是有hash冲突也能够存储进去,当选取的hash函数足够好,
num的数足够大,就能够保证列表中的每一个列表里面只有一个元素。根据key计算的元素所在的位置,然后来取值就能达
到O(1)的时间。
class MyDict:
def __init__(self, num=100): # 指定列表大小
self._num = num
self._lst = []
for _ in range(self._num):
self._lst.append([])
def update(self, key, value): # 添加 key-value
key_index = hash(key) % self._num
for i, (k, v) in enumerate(self._lst[key_index]):
if key == k:
self._lst[key_index][i] = [key, value]
break
else:
self._lst[key_index].append([key, value])
def get(self, key): # 根据指定的 key 弹出值
key_index = hash(key) % self._num
for k, v in self._lst[key_index]:
if k == key:
return v
else:
raise KeyError('No such {} key'.format(key))
def pop(self, key): # 根据 key 弹出元素 并且删除
key_index = hash(key) % self._num
for i, (k, v) in enumerate(self._lst[key_index]):
if k == key:
result = v
self._lst.pop[self._num](i)
return result
else:
raise KeyError('No such {} key'.format(key))
def __getitem__(self, key): # 可以通过下标来取值
key_index = hash(key) % self._num
for k, v in self._lst[key_index]:
if k == key:
return v
else:
raise KeyError('No such {} key'.format(key))
def keys(self): # 取得所有的key
for index in range(self._num):
for k, v in self._lst[index]:
yield k
def values(self): # 取得所有的 value
for index in range(self._num):
for k, v in self._lst[index]:
yield v
def items(self): # 取得所有的条目
for index in range(self._num):
for item in self._lst[index]:
yield item通过key查到的时间，可见下图
热心网友
时间：2022-05-10 10:33
楼主要求用C，麻烦呢，如果用C++倒是方便多了，闲着没事做，简单写了下，看下就好
#include <map>
#include <list>
#include <string>
using namespace std;
struct BirthInfo
{
int month;
int day;
BirthInfo()
{
month = 0;
day = 0;
}
bool operator == (const BirthInfo& rhs ) const
{
if ( month == rhs.month && day == rhs.day )
{
return true;
}
return false;
}
bool operator < (const BirthInfo& rhs ) const
{
if ( month < rhs.month )
{
return true;
}
else if ( month == rhs.month )
{
if ( day < rhs.day )
{
return true;
}
}
return false;
}
};
struct SameBirthInfo
{
int nCount;
list<string> StrNoList;
SameBirthInfo()
{
nCount = 0;
}
};
typedef map<BirthInfo , SameBirthInfo> Result;
int main()
{
int nStudentCount = 0;
string strNo = "";
BirthInfo BirInfo;
Result result;
SameBirthInfo sameBirthInfo;
cin >> nStudentCount;
while( nStudentCount -- > 0 )
{
cin >> strNo >> BirInfo.month >> BirInfo.day;
Result::iterator iter = result.find( BirInfo );
if ( iter == result.end() )
{
//找不到
pair<Result::iterator , bool> pInsRet = result.insert( Result::value_type(BirInfo,sameBirthInfo) );
if ( pInsRet.second )
{
pInsRet.first->second.nCount = 1; //记录下此生日有一人
pInsRet.first->second.StrNoList.push_back( strNo ); //记录下此人学号
}
}
else
{
//找到
iter->second.nCount++; //同一天生日人数++
iter->second.StrNoList.push_back( strNo ); //保存下这个学生的学号
}
}
//输出所有结果
Result::const_iterator cIter = result.begin();
while ( cIter != result.end() )
{
//先输出生日
cout << cIter->first.month << " " << cIter->first.day;
//输出所有学生学号
list<string>::const_iterator cStrIter = cIter->second.StrNoList.begin();
while ( cStrIter != cIter->second.StrNoList.end() )
{
cout << " " << cStrIter->c_str();
++cStrIter;
}
cout << endl;
++cIter;
}
return 0;
}
追问Σ( ° △ °|||)︴ 太...太厉害,只是窝一弱渣,看不懂C++...
能麻烦说说使用什么结构么?是顺序查找字典么?
追答用的其实就是map字典，我把学生的生日（月和日）作为一个查找键，找不到，就插入新的，找到了，就更新该键对应下面的学生信息
至于为什么要弄一个nCount来保存个数，方便你说的要求选中三个以上什么的而已，呵呵~
热心网友
时间：2022-05-10 11:51
