单链表的一个C实现Word下载.docx

单链表的一个C实现Word下载.docx

《单链表的一个C实现Word下载.docx》由会员分享，可在线阅读，更多相关《单链表的一个C实现Word下载.docx（4页珍藏版）》请在冰点文库上搜索。

initdata）:

data（initdata）,next（NULL）{}Node（constT&

initdata,Node&

*p）:

data（initdata）,next（p）{}};

classSList{public:

SList（）;

SList（constT&

initdata）;

SList（constSList&

&

other）;

SList&

operator=（constSList&

~SList（）;

public:

voidInvert（）;

intIsEmpty（）const;

intGetCount（）const;

intInsertBefore（constintpos,constTdata）;

intInsertAfter（constintpos,constTdata）;

intAddHead（constTdata）;

intAddTail（constTdata）;

voidRemoveAt（constintpos）;

voidRemoveHead（）;

voidRemoveTail（）;

voidRemoveAll（）;

T&

GetTail（）;

TGetTail（）const;

GetHead（）;

TGetHead（）const;

GetAt（constintpos）;

TGetAt（constintpos）const;

voidSetAt（constintpos,Tdata）;

intFind（constTdata）const;

intFindCircle（）const;

intFindCross（SList&

testlist）;

protected:

intm_nCount;

*m_pNodeHead;

};

inlineSList&

:

SList（）:

m_nCount（0）,m_pNodeHead（NULL）{}template&

SList（constT&

m_nCount（0）,m_pNodeHead（NULL）{AddHead（initdata）;

}template&

SList（constSList&

other）:

m_nCount（0）,m_pNodeHead（NULL）{if（other.m_nCount&

0）{for（inti=1;

i&

=other.m_nCount;

i++）{AddTail（other.GetAt（i））;

}}}template&

operator=（constSList&

other）{if（this==&

other）{return*this;

}if（m_nCount&

0）{RemoveAll（）;

}if（other.m_nCount&

}}return*this;

~SList（）{RemoveAll（）;

}//reversethelisttemplate&

inlinevoidSList&

Invert（）{if（m_nCount&

=1）return;

*curNod,*preNod,*nextNod;

curNod=m_pNodeHead;

preNod=NULL;

for（inti=1;

=m_nCount;

i++）{nextNod=curNod-&

next;

curNod-&

next=preNod;

preNod=curNod;

curNod=nextNod;

}m_pNodeHead=preNod;

return;

inlineintSList&

IsEmpty（）const{return0==m_nCount;

AddHead（constTdata）{/*Node&

*pNewNode;

try{pNewNode=newNode&

;

}catch（std:

bad_alloc&

）{return0;

}pNewNode-&

data=data;

pNewNode-&

next=m_pNodeHead;

m_pNodeHead=pNewNode;

++m_nCount;

return1;

*/returnInsertBefore（1,data）;

AddTail（constTdata）{returnInsertAfter（GetCount（）,data）;

}//ifsuccess,returnthepositionofthenewnode.//iffail,return0.template&

InsertBefore（constintpos,constTdata）{inti;

intnRetPos;

*pTmpNode1;

*pTmpNode2;

）{nRetPos=0;

returnnRetPos;

//ifthelistisempty,replacetheheadnodewiththenewnode.if（NULL==m_pNodeHead）{pNewNode-&

next=NULL;

nRetPos=1;

}//isposrangevalid?

ASSERT（1&

=pos&

pos&

=m_nCount）;

//insertbeforeheadnode?

if（1==pos）{pNewNode-&

}//ifthelistisnotemptyandisnotinsertedbeforeheadnode,//seektotheposofthelistandinsertthenewnodebeforeit.pTmpNode1=m_pNodeHead;

for（i=1;

i&

pos;

++i）{pTmpNode2=pTmpNode1;

pTmpNode1=pTmpNode1-&

next=pTmpNode1;

pTmpNode2-&

next=pNewNode;

nRetPos=pos;

InsertAfter（constintpos,constTdata）{inti;

*pTmpNode;

//ifthelistisnotempty,//seektotheposofthelistandinsertthenewnodeafterit.pTmpNode=m_pNodeHead;

++i）{pTmpNode=pTmpNode-&

next=pTmpNode-&

pTmpNode-&

nRetPos=pos+1;

GetCount（）const{returnm_nCount;

RemoveAt（constintpos）{ASSERT（1&

inti;

pTmpNode1=m_pNodeHead;

//headnode?

if（1==pos）{m_pNodeHead=m_pNodeHead-&

deletepTmpNode1;

--m_nCount;

}for（i=1;

++i）{//wewillgetthepreviousnodeofthetargetnodeafter//theforloopfinished,anditwouldbestoredintopTmpNode2pTmpNode2=pTmpNode1;

}pTmpNode2-&

next=pTmpNode1-&

RemoveHead（）{ASSERT（0!

RemoveAt

（1）;

RemoveTail（）{ASSERT（0!

RemoveAt（m_nCount）;

RemoveAll（）{inti;

intnCount;

nCount=m_nCount;

if（nCount==0）{return;

}for（i=0;

nCount;

++i）{pTmpNode=m_pNodeHead-&

deletem_pNodeHead;

m_pNodeHead=pTmpNode;

}m_pNodeHead=NULL;

m_nCount=0;

inlineT&

GetTail（）{ASSERT（0!

*pTmpNode=m_pNodeHead;

}returnpTmpNode-&

data;

inlineTSList&

GetTail（）const{ASSERT（0!

GetHead（）{ASSERT（0!

returnm_pNodeHead-&

GetHead（）const{ASSERT（0!

GetAt（constintpos）{ASSERT（1&

GetAt（constintpos）const{ASSERT（1&

SetAt（constintpos,Tdata）{ASSERT（1&

}pTmpNode-&

Find（constTdata）const{inti;

for（i=0;

++i）{if（data==pTmpNode-&

data）returni+1;

pTmpNode=pTmpNode-&

}return0;

}/*判断链表是否有环，如果有环则返回环的首结点位置，否则返回0*/template&

FindCircle（）const{if（0==m_nCount）{return0;

}Node&

*p1=m_pNodeHead;

*p2=m_pNodeHead;

/*判断链表是否有环，当p1=p2时说明链表有环，程序跳出循环。

如果p2一直走到链表尽头则说明没有环。

*/do{if（p1!

=NULL&

p2!

p2-&

next!

=NULL）{p1=p1-&

p2=p2-&

next-&

}elsereturn0;

}while（p1!

=p2）;

/*求出环的起点节点，并将其返回*/p2=m_pNodeHead;

while（p1!

=p2）{p1=p1-&

}inti;

p2=m_pNodeHead;

for（i=1;

i++）{if（p1==p2）break;

}returni;

}/*判断两个链表是否交叉，如果交叉返回首个交叉节点位置（在本链表中的位置，而不是testlist中的位置），否则返回0。

假定：

这两个链表本身均无环*/template&

FindCross（SList&

testlist）{if（0==m_nCount||0==testlist.m_nCount）{return0;

}if（FindCircle（）||testlist.FindCircle（））{return0;

}/*将第二个链表接在第一个链表后面*/Node&

*pTail=m_pNodeHead;

m_nCount;

i++）{pTail=pTail-&

}pTail=testlist.m_pNodeHead;

m_nCount+=testlist.m_nCount;

inti=FindCircle（）;

pTail=NULL;

m_nCount-=testlist.m_nCount;

returni;

}#endif