简单单链表C++实现
#include <iostream>using namespace std;/***----------单链表--------***//***---有头节点，无尾指针---***//***----------尾插法--------***//***------head为头结点，元素从head.next开始----***//***或许可以把head的data里面存上length更美观***//***功能简单，有错请指正***/template<typename T>class LinkList{public:typedef struct Node{T data;struct Node *next;}Node;LinkList(){Head=new Node; /***Head始终存在***/Head->next=NULL; /***初始状态：0,NULL***/Length=0;}bool InitList(){LinkList();}bool ListEmpty(){if (Length==0&&Head->next==NULL)/***是否为初始状态***/{return true;}else return false;}void ClearList(){if (ListEmpty()){return;}Node *p=new Node;Node *q=new Node;p=Head; q=p->next; /***q始终指向p下一元素***/while(q->next!=NULL) /***p的next及q是否为尾元素***/{p->next=NULL; /***本来想在这里使head=NULL,发现不行，不知道为什么***/free(p); /***释放p指向的空间,但指针变量p中还有地址值,所以可以p=q***/p=q; /***p指向删除前元素的下一元素***/q=q->next; /***q也后移***/}free(p);p=NULL; /***释放p指向空间，释放指针p***/free(q);q=NULL;Head->next=NULL; /***头指针为空***/Length=0;}/***用e获得第i(1,2,...)个元素值***/bool GetElem(int i,T *e){if (i>Length||i<1){return false;}Node *p=new Node;p=Head->next; /***p指向第一个元素***/int j=1;for(;j<i;j++){p=p->next;}*e=p->data;}/***返回0为list中不存在e***/int LocateElem(T e){Node *p=new Node;p=Head;int j=0;while(p->next!=NULL&&p->data!=e)/***p在尾元素之前找到值e***/{p=p->next;j++;}if (j==Length&&p->data!=e)/***p到达末尾仍未找到***/{return 0;}return j;/***返回第j个***/}/***第i(1,2,3...)个后方插入元素e***/bool InsertList(int i,T e){if (i>Length||i<0){return false;}if (Head->next==NULL&&i==0)/***空表插入***/{Node *tem=new Node;tem->data=e;Head->next=tem; /***第一个元素***/tem->next=NULL;Length++;}else if (i==Length&&Length!=0)/***末尾插入***/{Node *p=new Node;p=Head->next;while(p->next!=NULL){p=p->next;}Node *tem=new Node;tem->data=e;p->next=tem; /***末尾插入***/tem->next=NULL;Length++;}else /***正常情况***/{int j=1;Node *p=new Node;p=Head->next;while(j<i&&p!=NULL){p=p->next;j++;}Node * tem=new Node;tem->data=e;tem->next=p->next; p->next=tem;Length++;}return true;}bool ListDelete(int i,T *e){if (i>Length){return false;}int j=0;Node *p=new Node;p=Head;while(j<i-1) /***p指向被删元素前一元素***/{p=p->next;j++;}Node *pnext=new Node;pnext=p->next;*e=pnext->data;p->next=p->next->next; /***删除指向关系***/free(pnext);return true;}int ListLength(){return Length;}void DisplayList(){if (ListEmpty()){cout<<"Empty List"<<endl;return;}Node *p=Head->next;int i=0;while(p!=NULL&&i<Length){i++;cout<<"The "<<i<<" element "<<p->data<<endl;p=p->next;}}private:Node *Head;int Length;};int main(){LinkList<int> MyList;for (int i=0;i<10;i++){MyList.InsertList(i,i+1);}/***第10个元素后插入新元素11***/MyList.InsertList(10,11);MyList.DisplayList();int e=0;MyList.GetElem(5,&e);cout<<"GetElem(5) "<<e<<endl;int k=MyList.LocateElem(11);cout<<"LocateElem(11)"<<k<<endl;/***删除第X个元素***/int m=0;MyList.ListDelete(10,&m);cout<<"ListDelete(10) "<<m<<endl;MyList.DisplayList();MyList.ClearList();MyList.DisplayList();return 0;}