线性表的顺序存储结构、链式存储结构上的基本操作

//LinkList.cpp #include "LinkList.h" template<class T> LinkList<T>::LinkList () { first = new Node<T>; first ->next = NULL; } template<class T> LinkList<T>::LinkList (T a[], int n) { first = new Node<T>; Node<T> *r, *s; r = first; for ( int i =0; i<n; i ++) { s = new Node<T>; s->data = a[i]; r->next =s; r=s; } r->next =NULL; } template<class T> LinkList<T>::~LinkList () { } template<class T> T LinkList<T>::Get (int i) { Node<T> *p; int j; p = first->next ; j=1; while ( p&& j<i) { p =p->next ; j++; } if (!p) throw "Location"; else return p->data ; } template<class T> int LinkList<T>::Locate(T x) { Node<T> *p; int j; p=first->next ; j=1; if( p && p->next) { while(p->data !=x) { p=p->next ; j++; } return j; } else throw "Location"; } template<class T> void LinkList<T>::Insert (int i, T x) { Node<T>*p; int j; p = first; j=0; while (p && j<i-1) { p=p->next ; j++; } if (!p) throw"Location"; else { Node<T> *s; s = new Node<T>; s->data = x; s->next = p->next ; p->next = s; } } template<class T> int LinkList<T>::Length () { Node <T> *p = first->next; int i = 0; while(p) { p = p->next; i++; } return i; } template<class T> T LinkList<T>::Delete(int i) { Node<T> *p; int j; p=first; j=0; while(p && j<i-1) { p=p->next; j++; } if (!p || !p->next) throw "Location"; else { Node<T> *q; int x; q=p->next; x=q->data; p->next=q->next; delete q; return x; } } template<class T> void LinkList<T>::PrintList () { Node<T> *p; p=first->next; while(p) { cout<<p->data<<endl; p=p->next; } } //LinkList.h #ifndef LinkList_H #define LinkList_H template <class T> struct Node { T data; Node<T> *next; }; template <class T> class LinkList { public: LinkList(); LinkList(T a[], int n); ~LinkList(); int Length(); T Get(int i); int Locate(T x); void Insert(int i, T x); T Delete(int i); void PrintList(); private : Node<T> *first; }; #endif //LinkListMain.cpp #include <iostream> #include "LinkList.cpp" using namespace std; void main() { LinkList<int> a; cout<<"执行插入操作："<<endl; try { a.Insert(1,4); a.Insert(2,5); a.Insert(3,6); } catch(char* wrong) { cout << wrong; } cout<<"已经插入“4，5，6”"<<endl; cout<<"单链表的长度为:"<<endl; cout<<a.Length()<<endl; cout<<endl; cout<<"单链表a的元素为:"<<endl; a.PrintList(); cout<<endl; cout<<"按位查找第二个元素："<<endl; cout<<"第二个元素为："<<endl; cout<<a.Get(2)<<endl; cout<<endl; cout<<"按值查找5"<<endl; cout<<"值为5的元素位置为:"<<endl; cout<<a.Locate(5)<<endl; cout<<endl; cout<<"执行删除4的操作"<<endl; a.Delete(1); cout<<"已删除成功，单链表a的长度为"; cout<<a.Length()<<endl; cout<<endl; cout<<"链表a中元素为："<<endl; a.PrintList(); int r[ ]={1,2,3,4,5}; LinkList <int> b(r,5); cout<<"执行插入操作前单链表b为："<<endl; b.PrintList(); cout<<"插入前单链表b的长度为"<<endl; cout<<b.Length()<<endl; try { b.Insert(3,8); } catch(char* wrong) { cout << wrong; } cout<<"执行插入操作后单链表b为:"<<endl; b.PrintList(); cout<<"插入后单链表b的长度为："<<endl; cout<<b.Length()<<endl; cout<<endl; try { if(a.Length()) { cout<<"执行删除第一个元素操作："<<endl; cout<<endl; b.Delete(1); cout<<"已删除成功，单链表b的长度为："<<endl; cout<<b.Length()<<endl; } else { cout<<"顺序表b长度为0"<<endl; } } catch(char* wrong) { cout << wrong; } cout<<"执行插入操作后单链表b为："<<endl; b.PrintList(); int i; cin>>i; }