#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; first = new ChainNode<T>; link = first; cout<<"输入"<<len<<"个元素:"<<endl; while(len-->0) { s = new ChainNode<T>; cout<<"input the numbers:"; cin>>s->data; //创建的数据
link->next = s; link = s; } link->next = NULL; return this; } //析构函数 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 == NULL) return true; else return false; } 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->next; 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->next; 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个元素 ChainNode<T> *p = first; //p指向当前节点的前驱 int j = 0; ChainNode<T> *q = p->next; while( p && j< k - 1) { p = p->next ; j++; } if(!(p->next)|| j> k - 1) cout<<"删除位置不合理！"<<endl; q = p->next ; p->next = q->next; delete q; //释放删除了的节点 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->next;current ;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; cout<<"查找元素2:"<<endl; cout<<"元素2是第"<<L1.Search(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; } // 特别声明， 偶改动了好几次， 虽然kai上次调的能运行，但是太偶然了，存在错误 //例如我吧 creatlist里的 cin>>link->data; //创建的数据 改为 cin>>s->data; //创建的数据 //删除和输出都改动了点， first是头节点，不存放元素的指针 //这个链表类能执行删除，插入，输出， 可是程序结束时候出现异常，说内存非法访问 // 在.NET里弄的
