双向链表及扩展.doc

双向链表及扩展/*一、实验题目：双向链表的实现，包括添加结点、删除节点，输出以及查询。重点：1、如何动态的添加结点和释放结点； 2、结点数据的初始化和资源释放代码分别放在那里； 3、链表数据的初始化和资源释放代码放在那里；二、实验要求：1、链表元素中要有指针指向动态分配的内存空间，练习析构函数的操作规则；2、链表应该至少有两个类，Node和List类；3、从list类中派生出stack类和queue类，并使之具有自身操作的特性；4、从list类中派生出set类，负责集合操作的实现。*/ by.cpp : 定义控制台应用程序的入口点。/#include stdafx.hint _tmain(int argc, _TCHAR* argv)return 0;#includeusing namespace std;#define NULL 0#define flag PHead-next=NULLclass Nodepublic:int value;Node *prior;Node *next;Node(int i,Node *p,Node *n)value=i;prior=p;next=n;Node();class CListprotected:Node *PHead;Node *PTail;int Lsize;public:CList()PHead=new Node(0,NULL,NULL);/PHead-prior =NULL;/PHead-prior=NULL;/PHead-next =NULL;PTail=new Node(0,NULL,NULL);/PTail-prior =NULL;/PTail-prior =NULL;/PTail-next=NULL;Lsize=0;CList()Node *GetHead();Node *GetTail();void AddHead(int i);void AddTail();void RemoveHead();void RemoveTail();void GetNext();/从前到后遍历结点。void GetPrior();/从后向前遍历结点。Node *GetAt(int i);/得到地i个结点。void SetAt(int i,int j);/使第i个结点的值为j.void RemoveAt(int i);void InsertBefore(int i,int j);void InsertAfter(int i,int j);void RemoveAll();void create(int i);void ListTraverse();void CList:ListTraverse()Node *p=PHead-next;while(p)coutvaluenext;Node * CList:GetHead()return PHead;Node *CList:GetTail()return PTail;void CList:AddHead(int i)Node *p=new Node(i,NULL,NULL);if(flag)PHead-next=p;PTail-next=p;p-prior=PHead;else/PHead-next-prior=p;/p-next=PHead-next;/PHead-next-prior=p;/PHead-next=p;p-next=PHead-next;PHead-next=p;p-prior=PHead;p-next-prior=p;coutAddHead valueendl;void CList:AddTail()int i;couti;Node *p=new Node(i,NULL,NULL);if(PHead-next=NULL)/coutemptynext=p;PTail-next=p;p-prior=PHead;elsePTail-next-next=p;p-prior=PTail-next;PTail-next=p;void CList:RemoveHead()if(PHead-next=NULL)coutemptynext=PTail-next&PHead-next!=NULL)PHead-next=NULL;delete PTail-next;PTail-next=NULL;coutThen the list is empty!next=PHead-next-next;delete PHead-next-prior;void CList:RemoveTail()if(flag)coutthe list is empty!next=PTail-next&PHead-next!=NULL)PHead-next=NULL;delete PTail-next;PTail-next=NULL;coutThen the list is empty!next=PTail-next-prior;delete PTail-next-next;PTail-next-next=NULL;void CList:GetNext()Node *p;p=PHead-next;if(flag)coutemptyendl;elsecoutThe list is:;while(p)coutvaluenext;coutnext;if(flag)coutemptyendl;elsecoutprior!=NULL)coutvalueprior;Lsize+;/*void CList:GetPrior() /GetPrior(int cur_e,int pre)函数的原本功能是pre等于cur_e的前一个元素Node *p=PTail-next;if(flag)coutemptyendl;elsecoutThe list is:;while(p!=PHead)coutvalueprior;*/Node *CList:GetAt(int i)Node *p;int n=0;if(iLsize)couterrornext;n+;return p;void CList:SetAt(int i,int j)Node *p;p=GetAt(i);p-value=j;void CList:RemoveAt(int i)Node *p;int n=0;if(iLsize)coutDO NOT EXIST!next;n+;if(n=Lsize)if(Lsize=1)delete p ;PHead-next=NULL;PTail-next=NULL;elsePTail-next=p-prior;delete p;PTail-next-next=NULL;else if(n=1&Lsize!=1)p=PHead-next;PHead-next=p-next ;delete p;elsep-prior -next =p-next ;p-next -prior =p-prior ;delete p;/*void CList:InsertBefore(int i,int j) /这个函数是找到要插入位置的前一个节点的地址，然后插入Node *p,q(j,NULL,NULL);int n=0;if(flag|i=1)AddHead(j); elseif(i=Lsize+1)AddTail(); else if(i=Lsize+2) couterrorprior; p-prior-next=&q; p-prior =&q; q.next =p; */void CList :InsertBefore(int i,int k)Node *p=PHead,*q;int j=0;q=new Node(k,NULL,NULL);while(jnext;q-next=p-next;p-next=q;q-next-prior=q;void CList:InsertAfter(int i,int j)Node *p,*q=new Node(j,NULL,NULL);int n=0;if(i=0)AddHead(j);if(i=Lsize) AddTail();if(i=Lsize+1)couterrornext-prior =q;q-next=p-next ;p-next =q;q-prior =p;/*void CList:RemoveAll() /RemoveAll这个函数用下面那个要好点while(flag)RemoveHead();*/void CList :RemoveAll()Node *p=PHead-next;Node *q;while(p)q=p;p=p-next;delete q;PHead-next=PHead-prior=NULL;PTail-next=PTail-prior=NULL;void CList:create(int i)int j=0;while(ji)AddTail();j+;class stack:public CListprivate:Node *base;Node *top;public:stack()base=PHead;top=PTail;stack()void push();void Pop(int &k);int GetTop();void show_stack();void create_stack();void stack:push() int i;couti;coutnext=top-next)/Node *q=new Node(NULL,NULL,NULL); / 这个地方q不用插入/p-next=q;/q-prior=p;/base-next=p;/top-next=q;top-next=p;base-next=p;p-prior=base;else top-next-prior-next=p;p-prior=top-next-prior;p-next=top-next;top-next-prior=p;coutthe top:valueendl;/*void stack:push()int i;couti;coutnext=NULL)coutemptynext=top-next&base-next!=NULL)delete base-next;delete top-next;base-next=NULL;top-next=NULL;coutThe stack had only one element,but now its empty!next-prior=top-next-prior-prior;delete top-next-prior;top-next-prior-next=top-next;*/void stack:Pop(int &k)Node *p=top-next;if(p=NULL)coutemptynext=p-prior;p-prior-next=NULL;k=p-value;int stack:GetTop()return top-next-prior-value;/*void stack:show_stack() / 遍历的问题int i=0;coutnext!=NULL)coutnext-prior-value,;Pop();i+;else coutstacks empty!endl;coutthe size of the stack isiendl;*/void stack:create_stack()int i;int j=0;couti;coutendl;while(ji)push();j+;class Queue:public CListprivate:Node *front;Node *rear;int Qsize;public:Queue();Queue()void Inserted();void Deleted();void create_queue();void show_Queue();Queue:Queue()front=PHead;rear=PTail;Qsize=0;void Queue:Inserted()int i;couti;coutnext=NULL)/如果队列为空，则插入第一个元素front-next=p;rear-next=p;p-prior=front;elserear-next-next=p;p-prior=rear-next;rear-next=p;coutThe Inserted value is:valuenext=NULL)/如果队列为空，则输出emptycoutemptynext=rear-next&front-next!=NULL)delete front-next;front-next=NULL;rear-next=NULL;coutnow its empty!next=front-next-next;delete front-next-prior;front-next-prior=NULL;Qsize-;void Queue:show_Queue()coutthe length of the queue is Qsizenext=NULL)coutNULLendl;coutnext!=NULL)/当队列不为空时，分别输出数值coutnext-value,;Deleted(); void Queue:create_queue()int i;int j=0;couti;coutendl;while(jnext=NULL)/本身链表为空的状态RPH=ob1.PHead;RPT=ob1.PTail;else if(ob1.PHead-next=NULL)/ob1链表为空的状态coutThe list has not been changed!next-next=ob1.PHead-next;ob1.PHead-next-prior=RPT-next;delete ob1.PHead;RPT-next=ob1.RPT-next;temp.RPH=RPH;temp.RPT=RPT;temp.Resize=Resize+ob1.Resize;return temp;/*Set Set:operator-(int i) / operator-这个函数只是比较了第一个元素！Set temp;Node *p;Node *q;if(RPH-next=NULL)coutempty,cannot operatenext;if(p-value!=i)p=p-next;else if(RPH-next=RPT-next&RPH-next!=NULL)/只有一个元素的情况delete RPH-next;RPH-next=NULL;RPT-next=NULL;else/p-prior-next=p-next;/p-next-prior=p-prior;/delete p;temp.RPH=RPH;temp.RPT=RPT;return temp;*/Set Set:operator-(int i)Set temp;int j=0;Node *p=RPH;Node *q;if(iResize)couterrorendl;while(jnext;q=p-next;p-next=q-next;q-next-prior=p;temp.RPH=RPH;temp.RPT=RPT;return temp;/*int Set:And(Set &c1,Set &c2)Node *p,*q;p=c1.PHead;q=c2.PHead;if(p-next=NULL|q-next=NULL)coutthe Andlist is NULLendl;else coutnext;q=q-next;if(p-value=q-value)coutvaluenext;q=q-next;elsecoutThe Andlist is NULL;coutnext;Node *q=c2.RPH-next;int j=0;/couthellovalue=q-value)cout第j是相同的元素:next;q=q-next;/couthelloendl;/Resize-;return 0;void Set:create_set(int i) /建立set类型的双向链表create(i);Resize=i;coutResizenext=NULL)coutThe set is emptyendl;elsecoutnext!=NULL)p=p-next;coutvalue ;/Resize+; /链表遍历就最好不要对链表的长度进行修改coutendl;coutThe size isResizeendl;void main()Node *p;int k;CList check;check.create(5);check.AddHead(13);check.GetNext();check.AddTail();check.ListTraverse();check.GetPrior();p=check.GetAt(3);coutendl;coutvalueendl;check.SetAt(2,9);check.GetNext ();/check.ListTraverse();check.RemoveAt(2);check.GetNext();/check.ListTraverse();check.InsertBefore(4,10);check.GetNext ();/check.ListTraverse();check.InsertAfter(5,20);check.GetNext ();/check.ListTraverse();check.RemoveHead();check.GetNext ();/check.ListTraverse();check.RemoveTail();check.GetNext ();/check.ListTraverse();check.RemoveAll();stack exm;exm.create_stack();/exm.show_stack();exm.Pop(k);/couthelloendl;coutkendl;/exm.ListTraverse();/exm.show_stack();/exm.push();/exm.show_stack();Queue cq;cq.create_queue();cq.Deleted();/cq.Inserted();cq.show_Queue();/cq.show_Queue();Set sq1,sq2,sq3,sq4,sq5;cout请输入第一个双向链表的数据:endl;sq1.create_set(4);cout请输入第二个双向链表的数据:endl;sq2.create_set(4);sq3=sq1+sq2;sq3.show_set();sq3=sq1.operator-(3);sq3.show_set();cout请输入第一个双向链表的数据:endl;sq4.create_set(4);sq4.show_set();cout请输入第二个双向链表的数据:endl;sq2.create_set(4);sq2.show_set();sq5.And(sq4,sq2);/sq5.show_set();/ sq5的链表肯定是空链表，调用And函数并没有给sq5赋值/return 0;运行结果：putin the value you want:9putin the value you want:8putin the value you want:7putin the value you want:6putin the value you want:5AddHead 13The list is:13_9_8_7_6_5_putin the value you want:013987650The list is:0_5_6_7_8_9_13_8The list is:13_9_8_7_6_5_0_The list is:13_8_7_6_5_0_The list is:13_8_7_10_6_5_0_The list is:13_8_7_10_6_20_5_0_The list is:8_7_10_6_20_5_0_The list is:8_7_10_6_20_5_please input the length of the stack:3The value you want to push:4the top:4The value you want to push:8the top:8The value you want to push:0the top:00please i