有序线性表.doc

有序线性表/file:sortedChain.h#ifndef _SORTEDCHAIN_H_#define _SORTEDCHAIN_H_#include sortedChainNode.h#include exception.htemplate class SortedChainpublic:SortedChain()first = 0;SortedChain();bool IsEmpty() const return first = 0;int Length() const;bool Search(const K& k,E& e) const;SortedChain& Delete(const K& k,E& e);SortedChain& Insert(const E& e);SortedChain& DistinctInsert(const E& e);void Output(ostream& out) const;private:SortedChainNode *first;template SortedChain:SortedChain()SortedChainNode *next;while(first)next = first-link;delete first;first = next;template int SortedChain:Length() constSortedChainNode *current = first;int len = 0;while(current)len+;current = current-link;return len;template bool SortedChain:Search(const K& k,E& e) const/搜索与k匹配的元素，结果放入e /如果没有匹配的元素，则返回falseSortedChain *p = first;/搜索与k相匹配的元素for(;p & p-data link);/验证是否与k相匹配if(p & p-data = k)/与k相匹配e = p-data;return true;return false;/不存在相匹配的元素template SortedChain& SortedChain:Delete(const K& k,E& e)/删除与k相匹配的元素 /并将被删除的元素放入e /如果不存在匹配元素，则引发异常BadInputSortedChainNode *p = first,*tp = 0;/跟踪p/搜索与k相匹配的元素for(;p & p-data link);/验证是否与k相匹配if(p & p-data = k)/找到一个相匹配的元素e = p-data;/保存data域/从链表中删除p所指向的元素if(tp)tp-link = p-link;elsefirst = p-link;/p是链首节点delete p;return *this;throw BadInput();/不存在相匹配的元素template SortedChain& SortedChain:Insert(const E& e)/如果表中不存在关键值与e相同的元素，则插入e /否则引发异常BadInputSortedChainNode *p = first,*tp = 0;/跟踪p/移动tp以便把e插入到tp之后for(;p & p-data link);/若没有出现重复关键值，则产生一个关键值为e的新节点SortedChainNode *q = new SortedChainNode;q-data = e;/将新节点插入到tp之后q-link = p;if(tp)tp-link = q;elsefirst = q;return *this;template SortedChain& SortedChain:DistinctInsert(const E& e)/如果表中不存在关键值与e相同的元素，则插入e /否则引发异常BadInputSortedChainNode *p = first,*tp = 0;/跟踪p/移动tp以便把e插入到tp之后for(;p & p-data link);/检查关键值是否重复if(p & p-data = e)throw BadInput();/若没有出现重复关键值，则产生一个关键值为e的新节点SortedChainNode *q = new SortedChainNode;q-data = e;/将新节点插入到tp之后q-link = p;if(tp)tp-link = q;elsefirst = q;return *this;template void Chain:Output(ostream& out) constSortedChainNode *current;for(current = first;current;current = current-link)outdata ;template ostream& operator(ostream& out,const SortedChain& x)x.Output(out);return out;#endif/file:sortedChainNode.h#ifndef _SORTEDCHAINNODE_H_#define _SORTEDCHAINNODE_H_templateclass SortedChain;templateclass SortedChainNodefriend SortedChain;public:SortedChainNode()data = 0;link = NULL;SortedChainNode(E x)data = x;link = NULL;private:E data;SortedChainNode *link;#endif/file:exception.h#ifndef _EXCEPTION_H_#define _EXCEPTION_H_#include class NoMem public: NoMem() ;int my_new_h