数据结构 链表类定义代码.doc

链表类定义：将该类保存在文件LinkList.h中。/链表类定义：将该类保存在文件LinkList.h中。template struct NodeT data;Node *next; /此处也可以省略;template class LinkListpublic:LinkList( )first=new Node; first-next=NULL; /建立只有头结点的空链表LinkList(T a , int n); /建立有n个元素的单链表LinkList( ); /析构函数int Length( ); /求单链表的长度T Get(int i); /取单链表中第i个结点的元素值int Locate(T x); /求单链表中值为x的元素序号void Insert(int i, T x); /在单链表中第i个位置插入元素值为x的结点T Delete(int i); /在单链表中删除第i个结点void PrintList( ); /遍历单链表，按序号依次输出各元素private:Node *first; /单链表的头指针;template LinkList: LinkList( )Node * p=first; /工作指针p初始化while (p) /释放单链表的每一个结点的存储空间Node * q=p; /暂存被释放结点p=p-next; /工作指针p指向被释放结点的下一个结点，使单链表不断开delete q; template T LinkList:Get(int i) Node *p; int j; p=first-next; j=1; /或p=first; j=0; while (p & jnext; /工作指针p后移 j+; if (!p) throw 位置; else return p-data;template void LinkList:Insert(int i, T x) Node *p; int j; p=first ; j=0; /工作指针p初始化 while (p & jnext; /工作指针p后移 j+; if (!p) throw 位置; else Node *s; s=new Node; s-data=x; /向内存申请一个结点s，其数据域为x s-next=p-next; /将结点s插入到结点p之后 p-next=s;template T LinkList:Delete(int i) Node *p; int j; p=first ; j=0; /工作指针p初始化 while (p & jnext; j+; if (!p | !p-next) throw 位置; /结点p不存在或结点p的后继结点不存在 else Node *q; int x; q=p-next; x=q-data; /暂存被删结点 p-next=q-next; /摘链 delete q; return x;template LinkList: LinkList(T a , int n)first=new Node;first-next=NULL; /初始化一个空链表for (int i=0; in; i+) Node * s=new Node;s-data=ai; /为每个数组元素建立一个结点s-next=first-next; /插入到头结点之后first-next=s;template void LinkList:PrintList( )Node *p;p=first-next;while (p) coutdatanext;#include #includeLinkList.hvoid main( ) int r =10,9,8,7,6,5,4,3,2,1; LinkList a( r , 10 ); cout原表为:endl; a.PrintList(); coutendl; a.Insert(1,-2); /执行插入操作; a.Insert(2,-1); a.Insert(3,0 ); cout执行插入后输出为:endl; a.PrintList(); coutendl; a.Delete(0); a.Delete(-1); a.Delete(-2); cout执行删除后输出为:endl; a.PrintL