#include<iostream> #include<assert.h> using namespace std; template<class T> class Chain; template<class T> class ChainNode{ friend class Chain<T>; public: ChainNode(){} //ChainNode(const T& data_): data(data_){} private: T data; ChainNode<T> *next; }; template<class T> ostream& operator<<(ostream& out,const Chain<T>&x); template<class T> class Chain{ public: Chain(){} ~Chain();//链表析构函数，用于上述链表种所有节点 Chain<T>* CreateList(int len); bool IsEmpty(); int Length() const; //返回链表中元素的总数 bool Find(int k,T& x) const;//寻找链表中的第k个元素，并将其传送到x。如果不存在第k个元素，则返回false，否则返回true int Search(const T&x) const;//寻找x，如果发现x，则返回x的地址下标,如果x不在链表中，则返回0 Chain<T>& Insert(int k,const T& x);//在第k个元素之后插入x Chain<T>& Delete(int k);//把第k个元素取至x，然后从链表中删除第k个元素 void Output(ostream& outs) const; friend ostream& operator<< <>(ostream& out,const Chain<T>&x);//重载<<*/ private: ChainNode<T> *first,*last; }; //创建链表 template<class T> Chain<T>* Chain<T>::CreateList(int len) { ChainNode<T> *link,*s; int flag = 1; first = new ChainNode<T>; link = first; cout<<"输入"<<len<<"个元素:"<<endl; while(len-->0) { s = new ChainNode<T>; cout<<"input the numbers:"; cin>>link->data; //创建的数据 if(link->data == 0) flag = 0; link->next = s; link = s; } link->next = NULL; } //析构函数 template<class T> Chain<T>::~Chain() {//链表析构函数，用于删除上述链表种所有节点 ChainNode<T>* link; while(first) { link = first->next; delete first; first = link; } } template<class T> bool Chain<T>::IsEmpty() { if(first->next == NULL) return false; else return true; } template<class T> int Chain<T>::Length() const {//返回链表中元素的总数 ChainNode<T> *current = first; int len = 0; while(current!=NULL) { len++; current = current->next; } return len-1; }
template<class T> bool Chain<T>::Find(int k,T& x)const {//寻找链表中的第k个元素，并将其传送到x。如果不存在第k个元素，则返回false，否则返回true if(k<1) { cout<<"i值非法"<<endl; return false; } ChainNode<T> *current = first; int index = 1; while(index<k && current) { current = current->next; index++; } if(current) { x = current->data; return true; } return false; //不存在第k个元素 } //查找 template<class T> int Chain<T>::Search(const T&x) const {//寻找x，如果发现x，则返回x的地址下标 //如果x不在链表中，则返回0 ChainNode<T> *current = first; int index = 1; while(current && current->data!=x) { current = current->next; index++; } if(current) return index; return 0; } //删除 template<class T> Chain<T>& Chain<T>::Delete(int k) {//把第k个元素取至x，然后从链表中删除第k个元素 //如果不存在第k个元素，则引发异常OutOfBounds if(k<1 || !first) cout<<"不存在您要删除的元素!"<<endl; //throw OutOfBounds(); //不存在第k个元素 //p最终指向第k个节点 ChainNode<T> *p = first; //将p移动至第k个元素，并从链表中删除该元素 if( k==1) //p已经指向第k个元素 first = first->next; else { //用q指向第k－1个元素 ChainNode<T> *q = first; for(int index = 1;index<k-1 && q; index++) q = q->next; //if(!q || !q->next) // cout<<"不存在第k个元素"<<endl; //throw OutOfBounds();//不存在第k个元素 p = q->next; //存在第k个元素,p现在已经指向第k个节点了 q->next = p->next;//从链表中删除元素 } delete p; //释放p节点 return *this; } //插入 template<class T> Chain<T>& Chain<T>::Insert(int k,const T& x) { if(k<0) cout<<"插入位置非法"<<endl;//throw OutOfBounds(); ChainNode<T> *p = first; for(int index = 1; index<k && p;index++) p = p->next;
ChainNode<T> *y = new ChainNode<T>; y->data = x; if(p) { y->next = p->next; p->next = y; } else { y->next = first; first = y; return *this; } } //输出 template<class T> void Chain<T>::Output(ostream& outs) const { ChainNode<T> *current; for(current = first;current->next!=NULL;current = current->next) outs<< current->data <<" "; } //重载<< template<class T> ostream& operator<<(ostream& outs,const Chain<T>& x) { x.Output(outs); return outs; } int main() { Chain<int> L1,L2; int wantFind; L1.CreateList(4); if(L1.IsEmpty()) cout<<"链表非空"<<endl; else cout<<"链表是空的!"<<endl; cout<<"链表长度是:"<<L1.Length()<<endl; cout<<"原始链表是:"<<L1<<endl; cout<<"查找第2个元素。。。"<<endl; if(L1.Find(2,wantFind)) cout<<"找到了第2个元素! 第2个元素是:" <<wantFind<<endl; cout<<"查找元素5:"<<endl; cout<<"元素5是第"<<L1.Search(5)<<"个"<<endl; cout<<"删除元素2..."<<endl; L1.Delete(L1.Search(2));//把第k个元素取至x，然后从链表中删除第k个元素 cout<<"删除2后的链表是"<<L1<<endl; cout<<"在第3个元素之后插入9..."<<endl; L1.Insert(3,9); cout<<"插入9后的链表是"<<L1<<endl; system("pause"); return 0; } 这个链表类终于能正确运行了，但是运行完就出现异常 ， 不知道是什么原因
[此贴子已经被作者于2005-9-10 9:55:10编辑过]
