数据结构--线性表的链式表现形式.doc

/# define LEN 30/30typedef int ElemType;/ElemType/typedef struct LNode/ElemType data;/LNode *next;LNode;/class LinkListprivate:/LNode *head;public:/1 -LinkList();/2 LinkList(int d1);/3 LinkList(int n, int mark,int seed);/4 LinkList(LinkList &HL);/5 LinkList();/6 void ClearList();/7 void ListInsert(ElemType &item, int mark);/8 bool ListDelete(ElemType &item , int mark);/9 bool UpdateList(ElemType &item, ElemType e);/10 ElemType GetElem(int pos);/11 bool ListEmpty();/12 bool FindList(ElemType &item);/13 void pailie(int mark);/14 void Traverse(void f(ElemType &);/15 void MergeList(LinkList &la, LinkList &lb);/16 int ListSize();/# includelinklist.h# include# include# include# include/1 LinkList:LinkList()head=new LNode;head-next=NULL;/2 LinkList:LinkList(int d1)head=new LNode;head-next-data=d1;head-next-next=NULL;/3 LinkList:LinkList(int n, int mark,int seed)/ElemType aLEN+1;srand(seed);int i,j;/forfor(i=1;i=n;i+)ai=rand()%100;/for(i=1;i=n;i+)for(j=1;jaj+1 | mark=-1 & ajaj+1)int t=aj;aj=aj+1;aj+1=t;head=new LNode;LNode *p=head;LNode *q;for(i=1;idata=ai;p-next=q;p=p-next;p-next=NULL;/4 LinkList:LinkList(LinkList &HL)head=new LNode;LNode *p1=HL.head-next,*p=head,*q;while(p1)q=new LNode;q-data=p1-data;p-next=q;p1=p1-next;p=q;p-next=NULL;/5 LinkList:LinkList()LNode *p=head-next,*q;while(p)q=p-next;free(p);p=q;head-next=NULL;/6 void LinkList:ClearList()LNode *p=head-next, *q;while(p)q=p-next;free(p);p=q;head-next=NULL;/7 void LinkList:ListInsert(ElemType &item, int mark)LNode *p=head,*q;for(int i=1;inext;q=new LNode;q-data=item;q-next=p-next;p-next=q;/8 bool LinkList:ListDelete(ElemType &item, int mark)if(ListEmpty() | markListSize()return false;LNode *p=head,*q;q=new LNode;int i;for(i=1;inext;item=p-next-data;q=p-next-next;free(p-next);p-next=q;return true;/9 bool LinkList:UpdateList(ElemType &item ,ElemType e)LNode *p=head-next;while(p)if(p-data=item)p-data=e;return true;p=p-next;return false;/10 ElemType LinkList:GetElem(int pos)LNode *p=head-next;int i=1;while(p)if(i=pos)return p-data;i+;p=p-next;return head-data;/11 int LinkList:ListSize()int i=0;LNode *p=head-next;while(p)i+;p=p-next;return i;/12 bool LinkList:FindList(ElemType &item)LNode *p=head-next;while(p)if(p-data=item)return true;p=p-next;return false;/13 bool LinkList:ListEmpty()return ListSize()=0;/14 void LinkList:Traverse(void f(ElemType &)LNode *p=head-next;while(p)f(p-data);p=p-next;/15 void LinkList:MergeList(LinkList &la, LinkList &lb)LNode *pa=la.head-next, *pb=lb.head-next,*p=head,*q;while(pa&pb)q=new LNode;if(pa-datadata)q-data=pa-data;p-next=q;pa=pa-next;p=q;elseq-data=pb-data;p-next=q;pb=pb-next;p=q;while(pa)q=new LNode;q-data=pa-data;p-next=q;pa=pa-next;p=q;while(pb)q=new LNode;q-data=pb-data;p-next=q;pb=pb-next;p=q;p-next=NULL;/16 void LinkList:pailie(int mark)ElemType aLEN+1;LNode *p=head-next;int k,i,j;for(k=1;p!=NULL;k+,p=p-next)ak=p-data;k-;for(i=1;i=k;i+)for(j=1;jaj+1 | mark=-1 &ajnext;for(i=1;inext)p-data=ai;/# includelinklist.h# include# include# includevoid ff(ElemType &a)couta ;void main()couttest.cpp:endl;int init_size,mark,seed;coutlist1!endl;coutinit_size;coutmark;coutseed;LinkList list1(init_size,mark,seed);coutlist1!endl;cout:endl;list1.Traverse(ff);coutendl;coutlist1:list1.ListSize()endl;cin.get();coutlist1:endl;int i;couti;coutlist1i:list1.GetElem(i)endl;ElemType it;couti;list1.ListDelete(it,i);coutlist1iit:endl;list1.Traverse(ff);coutendl;coutlist1:list1.ListSize()endl;ElemType olds,news;coutolds;coutnews;list1.UpdateList(olds,news);coutlist1:endl;list1.Traverse(ff);coutendl;cin.get();coutlist2!endl;coutinit_size;coutmark;coutseed;LinkList list2(init_size,mark,seed);coutlist2!endl;coutlist2:endl;list2.Traverse(ff);coutendl;cout:list2.ListSize()endl;cin.get();coutlist1list2list3!endl;LinkList list3;list3.MergeList(list1,list2);cout!endl;coutlist3:endl;list3.Traverse(ff);coutendl;coutlist3:list3.ListSize()endl;coutmark;list3.pailie(mark);coutlist3:endl;list3.Traverse(ff);coutendl;list3.ClearList();coutlist3!endl;coutlist4!endl;LinkList list4;coutinit_size;cout:endl;ElemType b;for(i=1;ib;list4.ListInsert(b,i);cout!endl;coutlist4:endl;list4.Traverse(ff);c