数据结构课件计算机专业

class TExcepLinearList { public: int errNo; char errMessage[CNST_SizeErrMessage]; TExcepLinearList(int mErrNo) { errNo=mErrNo; strcpy(errMessage, errMessageList.GetMessage(errNo)); } }; template <class TElem> class TLinearList0 {protected: public: long len; virtual TBool IsEmpty() {if (len <=0) return True; else return False;} virtual TElem &Get(long idx) = 0; //声明虚函数，不需要给出实现 virtual TElem *Set(long idx, TElem &elem) = 0; virtual TElem *Prior(long idx) = 0; virtual TElem *Next(long idx) = 0; virtual TElem *GetAddress(long idx)=0; virtual long CountElem(TElem &elem)=0; virtual long Locate(TElem &elem, long sn=1) = 0; virtual long Locate(TElem &elem, long *foundElem) = 0; virtual long LocateFirst(TElem &elem) = 0; virtual long LocateNext(TElem &elem) = 0; virtual TElem *Insert(TElem &elem, long sn=1) = 0; virtual TElem *Delete(long sn=1)=0; virtual long Delete(TIndexSelector &sel, TElem **elemDeleted=NULL)=0; virtual long DeleteByIndex(long *idxTobeDel,long numIdx, TElem *elemDeleted=NULL)=0;}; template <class TElem> //上面是模板声明，表明TElem是一个可变（调）类型，在使用TLinkNode时动态决定 struct TLinkNode { TElem info; //info的类型是可变的类模板TElem TLinkNode *next; // 这里的TLinkNode后可以省略<TElem> }; template <class TElem> class TLinearListLink : public TLinearList0<TElem> { protected: TLinkNode<TElem> *head; TLinkNode<TElem> *lastVisited; long lastVisitedIndex; TElem buffElem; void ReleaseAll();public: TLinearListLink(void); ~TLinearListLink(void); virtual TElem &Get(long idx); virtual TElem *GetAddress(long idx); virtual TElem *Set(long idx, TElem &elem); virtual long CountElem(TElem &elem); virtual TElem *Prior(long idx); virtual TElem *Next(long idx); virtual long Locate(TElem &elem, long sn=1); virtual long Locate(TElem &elem, long *foundElemIndex=NULL); virtual long LocateFirst(TElem &elem); virtual long LocateNext(TElem &elem); virtual TElem *Insert(TElem &elem, long sn=1); virtual TElem *Delete(long sn=1); virtual long Delete(TIndexSelector &sel, TElem *elemDeleted=NULL); virtual long DeleteByIndex(long *idxTobeDel, long numIdx, TElem *elemDeleted=NULL); void Print(); //Only for test //Newly added functions virtual TElem &Get(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *GetNode(long idx); virtual long GetNodeIndex(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *SetNode(TLinkNode<TElem> *pNode, TElem &elem, TLinkNode<TElem> *pNodeNext); virtual TLinkNode<TElem> *SetNodeElem(TLinkNode<TElem> *pNode, TElem &elem); virtual TLinkNode<TElem> *SetNodeNext(TLinkNode<TElem> *pNode, TLinkNode<TElem> *pNodeNext); virtual TLinkNode<TElem> *PriorNode(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *NextNode(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *PriorNode(long idx); virtual TLinkNode<TElem> *NextNode(long idx); virtual TLinkNode<TElem> *LocateNode(TElem &elem, long sn=1); virtual long LocateNode(TElem &elem, TLinkNode<TElem> *foundElemPointer[]); virtual TLinkNode<TElem> *LocateNodeFirst(TElem &elem); virtual TLinkNode<TElem> *LocateNodeNext(TElem &elem); virtual TLinkNode<TElem> *InsertAfter(TLinkNode<TElem> *pNodeTobeInserted, TLinkNode<TElem> *pNodeBase); virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNodeTobeInserted, TLinkNode<TElem> *pNodeBase); virtual TLinkNode<TElem> *DeleteAfter(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *Delete(TLinkNode<TElem> *pNode); virtual TLinkNode<TElem> *Insert(TLinkNode<TElem> *pNode, long sn=1); }; template <class TElem> TLinearListLink< TElem>::TLinearListLink() { head=NULL; len=0; lastVisitedIndex=0; lastVisited=NULL; }; template <class TElem> TLinearListLink <TElem> ::~TLinearListLink() { if (head!=NULL) ReleaseAll(); }; template <class TElem> void TLinearListLink< TElem>::ReleaseAll() {//释放链表中所有元素 TLinkNode<TElem> *p, *q; p=head; //p指向当前要处理的结点 while (p!=NULL) //从头到尾依次释放各结点 { q=p; //移动p前，令q指向p所指结点，以防p后移丢失p原指的结点 p=p->next; //p后移一步，p指向下一个要处理的结点 delete q; //释放q所指结点 } }; template <class TElem> TElem &TLinearListLink< TElem>::Get(TLinkNode<TElem> *pNode) {//返回指定结点中的元素内容 if ( pNode==NULL) TExcepLinearList(4); return pNode->info; } template <class TElem>long TLinearListLink<TElem>:: GetNodeIndex(TLinkNode<TElem> *pNode) {//返回指定结点在表中的序号 if ( pNode==NULL) TExcepLinearList(4); TLinkNode<TElem> *p; long i; i=0; p=head; while (p!=NULL) //从头到尾扫描各结点 { if (p==pNode) break; i++; p=p->next; } if ( p==NULL) TExcepLinearList(4); //未找到 return i; //已找到，返回其序号 } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem>::GetNode(long idx) { //返回指定序号idx所对应的结点的指针 TLinkNode<TElem> *p; long i; if (idx<0 || idx>=len) throw TExcepLinearList(2); if (lastVisited!=NULL && idx >= lastVisitedIndex) { p=lastVisited; i=lastVisitedIndex; } else { p=head; i=0; } while (p!=NULL) { if (i==idx) break; i++; p=p->next; } if ( p==NULL) throw TExcepLinearList(0); lastVisitedIndex=i; //记下本次最后访问到的结点的序号 lastVisited=p; //记下本次最后访问的结点的地址 return p; } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem> ::SetNode(TLinkNode<TElem> *pNode, TElem &elem, TLinkNode<TElem> *pNodeNext) { //对给定结点的info和next字段同时置值，返回被置值的结点指针 if (pNode==NULL) throw ExcepLinearList(4); pNode->info = elem; pNode->next = pNodeNext; return pNode; } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem> ::SetNodeElem(TLinkNode<TElem> *pNode, TElem &elem) { //给指定的结点(pNode)置内容 if (pNode==NULL) throw ExcepLinearList(4); pNode->info = elem; return pNode; } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem> ::SetNodeNext(TLinkNode<TElem> *pNode, TLinkNode<TElem> *pNodeNext) { //给指定的结点(pNode)置后继(pNodeNext) if (pNode==NULL) throw TExcepLinearList(4); pNode->next = pNodeNext; return pNode; } template <class TElem>TLinkNode <TElem> *TLinearListLink< TElem>::NextNode ( TLinkNode<TElem> *pNode) { //返回给定结点(pNode)的后继结点的指针 if ( pNode->next==NULL) TExcepLinearList(4); lastVisited=pNode; return pNode->next; }; template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem>:: PriorNode(TLinkNode<TElem> *pNode) { //返回给定结点(pNode)的前驱结点的指针 TLinkNode<TElem> *p; long i; if (lastVisited!=NULL) if (lastVisited->next==pNode) return lastVisited; i=0; p=head; if (pNode==head) throw TExcepLinearList(4); while (p!=NULL) { if (p->next==pNode) break; i++; p=p->next; } if (p==NULL) throw TExcepLinearList(4); lastVisited=p; lastVisitedIndex=i; return p; }; template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem>::PriorNode(long idx) { //求对应结点的前驱结点的指针 return GetNode(idx-1); } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem>::NextNode(long idx) { //求对应结点的后继结点的指针 return GetNode(idx+1); } template <class TElem> TLinkNode<TElem> *TLinearListLink< TElem>::LocateNode(TElem &elem, long sn) { //返回元素值为elem的第sn次出现的结点的指针 TLinkNode<TElem> *p, *p0; long k, i; k=sn; if (k<0) k=k+CountElem(elem)+1; //sn为负时，将其换算为正,成员函数CountElem(elem)返回值为elem的元素的个数，用此值换算sn if (k<0 ) throw TExcepLinearList(2); p0=NULL; p=head; i=0; while (p!=NULL) { if (p->info==elem) { i++; p0=p; if (k==i) return p; } p=p->next; } if (p0==NULL) throw TExcepLinearList(3); else return p0