binSort.cpp
/*
* 这里是主函数的执行文件
* binSort.cpp
*/
#include<iostream>
#include"studentrecord1.h"
#include"chainwithiterator.h"
#include"myexceptions.h"
void binSort(chain<studentRecord>& theChain,int range)
{
chain<studentRecord> *bin;
bin = new chain<studentRecord> [range+1];
int numberOfElements = theChain.size();
for(int i = 1;i <= numberOfElements;i++)
{
studentRecord x = theChain.get(0);
theChain.erase(0);
//在排序后的链表插入新元素,且在链表头插入
bin[x.score].insert(0,x);
}
//从bin中收集元素,在存储到theChain链表中
for(int j = range;j>=0;j--)
{
while(!bin[j].empty())
{
studentRecord x = bin[j].get(0);
bin[j].erase(0);
theChain.insert(0,x);
}
}
delete [] bin;
}
int main(int argc, char *argv[])
{
studentRecord s;
chain<studentRecord> c;
for(int i = 1;i <= 20;i++)
{
s.score = i / 2;
s.name = new string(s.score,'a');
c.insert(0,s);
}
cout<<"The unsorted chain is"<<endl;
cout <<" "<< c <<endl;
binSort(c,10);
cout <<"The sorted chain is" <<endl;
cout <<" "<< c <<endl;
return 0;
}
chainNode.h
/*
* 链表节点定义
* chainNode.h
*/
#ifndef CHAINNODE_H
#define CHAINNODE_H
template<class T>
struct chainNode
{
//数据成员
T element;
chainNode<T>* next;
//函数
chainNode(){}
chainNode(const T& element)
{
this->element = element;
}
chainNode(const T& element,chainNode<T>* next)
{
this->element = element;
this->next = next;
}
};
#endif // CHAINNODE_H
chainWithIterator.h
/*
*链表迭代器的定义
* chainWithIterator.h
*/
#ifndef CHAINWITHITERATOR_H
#define CHAINWITHITERATOR_H
#include<iostream>
#include<sstream>
#include<string>
#include"linearlist.h"
#include"chainnode.h"
#include"myexceptions.h"
using namespace std;
class linkedDigraph;
template<class T> class linkedWDigraph;
template<class T>
class chain : public linearList<T>
{
friend linkedDigraph;
friend linkedWDigraph<int>;
friend linkedWDigraph<float>;
friend linkedWDigraph<double>;
public :
/*
* 构造函数,复制构造函数,析构函数
*/
chain(int initialCapaticy = 10);
chain(const chain<T>&);
~chain();
//抽象函数的具体声明
bool empty() const{return listSize == 0;}
int size() const{return listSize;}
T& get(int theIndex) const;
int indexOf(const T &theElement) const;
void insert(int theIndex,const T& theElement);
void erase(int theIndex);
void output(ostream& out) const;
//迭代器的开始和结束
class iterator;
iterator begin() {return iterator(firstNode);}
iterator end(){return iterator(NULL);}
//对chain的迭代器
class iterator
{
public:
typedef forward_iterator_tag iterator_category;
typedef T value_type;
typedef ptrdiff_t difference_type;
typedef T* pointer;
typedef T& reference;
//构造函数
iterator(chainNode<T>* theNode = NULL)
{
node = theNode;
}
//
T& operator*() const{return node->element;}
T* operator->()const{return &node->element;}
//对++的重载
iterator& operator++()//前加
{
node = node->next;
return *this;
}
iterator operator++(int)//后加
{
iterator old = *this;
node = node->next;
return old;
}
bool operator != (const iterator right) const
{
return node != right.node;
}
bool operator == (const iterator right) const
{
return node == right.node;
}
protected:
chainNode<T>* node;
};
protected:
void checkIndex(int theIndex) const;
chainNode<T>* firstNode;//指向链表汇总首节点
int listSize;//元素数量
};
/*
* 类中函数的具体实现
*/
//构造函数
template<class T>
chain<T>::chain(int initialCapaticy)
{
if(initialCapaticy < 1)
{
ostringstream s;
s << "Initial capacity = "<< initialCapaticy <<"Must be > 0";
throw illegalParameterValue(s.str());
}
firstNode = NULL;
listSize = 0;
}
//复制构造函数
template<class T>
chain<T>::chain(const chain<T>& theList)
{
listSize = theList.listSize;
//链表为空
if(listSize == 0)
{
firstNode = NULL;
return;
}
//链表非空
chainNode<T>* sourceNode = theList.firstNode;
firstNode = new chainNode<T>(sourceNode->element);//复制第一个元素到theList链表
sourceNode = sourceNode->next;
chainNode<T>* targetNode = firstNode;
while(sourceNode != NULL)
{
targetNode->next = new chainNode<T>(sourceNode->element);
targetNode = targetNode->next;
sourceNode = sourceNode->next;
}
targetNode->next = NULL;//结束链表
}
//析构函数,删除链表中所有节点
template<class T>
chain<T>::~chain()
{
chainNode<T> *nextNode;
while(firstNode != NULL)
{
nextNode = firstNode->next;
delete firstNode;
firstNode = nextNode;
}
}
//函数:checkIndex()
//用于检查元素索引是否合法
template<class T>
void chain<T>::checkIndex(int theIndex) const
{
if(theIndex < 0 || theIndex >= listSize)
{
ostringstream s;
s <<"index = "<<theIndex <<" size = " <<listSize;
throw illegalIndex(s.str());
}
}
//函数:get(int theIndex)
//获取索引为theIndex的元素
template<class T>
T& chain<T>::get(int theIndex) const
{
checkIndex(theIndex);
chainNode<T>* currentNode = firstNode;
for(int i = 0;i < theIndex;i++)
currentNode = currentNode->next;
return currentNode->element;
}
//返回某元素的索引
template<class T>
int chain<T>::indexOf(const T &theElement) const
{
chainNode<T>* currentNode = firstNode;
int index = 0;
while(currentNode != NULL && currentNode->element != theElement)
{
currentNode = currentNode->next;
index++;
}
if(currentNode == NULL)
return -1;
else
return index;
}
//删除索引为theIndex 的元素
template<class T>
void chain<T>::erase(int theIndex)
{
checkIndex(theIndex);
chainNode<T>* deleteNode;
if(theIndex == 0)
{
deleteNode = firstNode;
firstNode = firstNode->next;
}
else
{
chainNode<T>* p = firstNode;
for(int i = 0;i< theIndex-1;i++)//此处和书上写法不同,斯以为书上的较繁琐
{
p = p->next;
}
deleteNode = p->next;
p->next = p->next->next;
}
listSize--;
delete deleteNode;
}
//在某索引位置插入一个元素
template<class T>
void chain<T>::insert(int theIndex, const T &theElement)
{
if(theIndex < 0 || theIndex > listSize)
{
ostringstream s;
s <<"index = " << theIndex <<" size = "<<listSize;
throw illegalIndex(s.str());
}
if(theIndex == 0)
firstNode = new chainNode<T>(theElement,firstNode);
else
{
chainNode<T>* p = firstNode;
for(int i = 0;i<theIndex -1;i++)
p = p->next;
p->next = new chainNode<T>(theElement,p->next);
}
listSize++;
}
//将链表元素送到输出流
template<class T>
void chain<T>::output(ostream &out) const
{
for(chainNode<T>* currentNode = firstNode;
currentNode != NULL;
currentNode = currentNode->next)
out<< currentNode->element << " ";
}
//重载<<
template<class T>
ostream& operator << (ostream& out,const chain<T>& x)
{
x.output(out);
return out;
}
#endif // CHAINWITHITERATOR_H
linearList.h
/*
* 链表的抽象类
* linearList.h
*/
#ifndef linearList_
#define linearList_
#include<iostream>
using namespace std;
template<class T>
class linearList
{
public:
virtual ~linearList() {};//析构函数
virtual bool empty() const = 0;//判断链表是否为空
virtual int size() const = 0;//返回链表元素个数
virtual T& get(int theIndex) const = 0;//返回索引theIndex指代元素
virtual int indexOf(const T& theElement) const = 0;//返回某元素索引
virtual void erase(int theIndex) = 0;//删除索引为theIndex的元素
virtual void insert(int theIndex,const T& theElelemt) = 0;
virtual void output(ostream& out) const = 0;
};
#endif
myExceptions.h
/*
* 异常类
* myExceptions.h
*/
#ifndef MYEXCEPTIONS_H
#define MYEXCEPTIONS_H
#include<string>
using namespace std;
//不合法的参数值
class illegalParameterValue
{
public:
illegalParameterValue(string theMessage = "Illegal parameter value")
{
message = theMessage;
}
void outputMessage()
{
cout<< message <<endl;
}
private:
string message;
};
//不合法的输入数据
class illegalInputData
{
public:
illegalInputData(string theMessage="Illegal data input")
{
message = theMessage;
}
void outputMessage()
{
cout<< message <<endl;
}
private:
string message;
};
//不合法的索引
class illegalIndex
{
public:
illegalIndex(string theMessage = "Illegal index")
{
message = theMessage;
}
void outputMessage()
{
cout<< message <<endl;
}
private:
string message;
};
#endif // MYEXCEPTIONS_H
studentRecord1.h
/*
* 记录学生信息,包括姓名和分数
* studentRecord1.h
*/
#ifndef STUDENTRECORD1_H
#define STUDENTRECORD1_H
/*
* 学生信息的结构体定义
* studentRecord1.h
*/
#include <string>
using namespace std;
struct studentRecord
{
int score;
string *name;
int operator != (studentRecord x) const
{
return (score != x.score);
}
};
ostream& operator<<(ostream& out,const studentRecord& x)
{
out << x.score <<' ' <<*x.name <<endl;
return out;
}
#endif // STUDENTRECORD1_H