freqlist.h

一个我的数据结构解题集合

#ifndef FREQLIST_H__
#define FREQLIST_H__

#include "List.h"

#include <stdexcept>
#include <iostream>
#include <iomanip>
using namespace std;

template <typename T>
struct FreqListData {	// 包装后的数据类型, 带有freq场
	/* 默认构造函数
	 */
	FreqListData()
		: freq(0) {}

	/* 拷贝构造函数,
	 * 复制一个FreqListData
	 */
	FreqListData(const FreqListData& that)
		: data(that.data), freq(that.freq) {}

	/* 单参数构造函数,
	 * 提供T类型到FreqListData的隐式转换
	 * v: 数据
	 */
	FreqListData(const T& v)
		: data(v), freq(0) {}

	/* 隐式转换到T类型
	 * 以支持T类型所支持的比较等操作
	 */
	operator const T&() const {
		return data;
	} // operator T() const

	T data;		// 存放数据
	int freq;	// 结点被访问的次数

}; // FreqListNode


template <typename T>
class FreqList {
private:
	typedef FreqListData<T> Data;	// 包装后的数据类型 (带有freq场)

	mutable List<Data> list_;		// 内部使用的链表
									// * 由于内部链表的实现不完善, 没有const迭代器
									// * 致使某些const成员函数无法正常编译, 
									// * 故此处将其设为mutable

public:

	/* 在链表中插入元素e
	 * 使用前应用has函数确认当前链表中不含元素e,
	 * 如果链表中含有元素e, 抛出std::invalid_argument异常
	 */
	void insert(const T& e) {
		if ( has(e) ) {					// 前提被违反
			throw std::invalid_argument(
					"FreqList::insert(const T& e) : requirement ( !has(e) ) violated\n"
				);
		}

		list_.insert(list_.end(), e);	// 插入内部链表的尾部
	} // insert(const T&)


	/* 删除链表中的元素e
	 * 使用前应用has函数确认当前链表中存在元素e,
	 * 如果链表中没有元素e, 抛出std::invalid_argument异常
	 */
	void remove(const T& e) {
		// 取得元素e所在结点的迭代器
		List<Data>::Itor itor = list_.search(list_.begin(), e);

		list_.remove(itor);		// 如果没有e, 该操作抛出异常

	} // remove(const T&)


	/* 查询链表中是否含有元素e,
	 * 该操作不改变元素所在结点的freq值
	 */
	bool has(const T& e) const {
		return list_.search(list_.begin(), e) != list_.end();
	} // has(const T&) const


	/* 查找链表中的元素e
	 * 如果找到, 该元素结点的访问频率+1,
	 * 链表保持按freq降序排列状态, 返回true,
	 * 否则返回false
	 */
	bool search(const T& e) {
		List<Data>::Itor itor = list_.search(list_.begin(), e);
		if ( itor == list_.end() )		// 没有找到
			return false;
		
		// 找到了
		++(itor->data.freq);			// 增加freq值

		// 查找第一个满足以下条件的结点: freq小于等于e所在结点的freq
		List<Data>::Itor p = list_.begin();
		for ( ; (p->data.freq > itor->data.freq) && ( p != list_.end() ); p = p->next)
			;	// 空循环体

		if (p == itor) return true;	// 原位恰当, 不必调整
		
		// 调整p的位置, 以保持按freq降序排列状态
		Data datcopy(itor->data);

		list_.remove(itor);			// 先从原始位置移除
		list_.insert(p, datcopy);	// 再插入新的位置

		return true;

	} // search(const T&)

	/* 在cout打印链表的内部信息
	 * 包括数据场和freq值
	 */
	void print() const {
		cout << "List:\n";
		List<Data>::Itor itor = list_.begin();
		for ( ; itor != list_.end(); itor=itor->next)
			cout << "\tData: " << setw(12) << itor->data.data
				 << "Freq: " << itor->data.freq << "\n";
		cout << endl;

	} // print() const

	/* 查询链表的所含元素的个数
	 */
	int size() const {
		return list_.size();
	} // size() const

};


#endif  // FREQLIST_H__