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

1、initdata） : data（initdata）, next（NULL） Node（const T &initdata, Node& *p） : data（initdata）, next（p） ; class SList public: SList（）; SList（const T &initdata）; SList（const SList& other）; SList& operator=（const SList& SList（）; public: void Invert（）; int IsEmpty（） const; int GetCount（） const; int InsertBe

2、fore（const int pos, const T data）; int InsertAfter（const int pos, const T data）; int AddHead（const T data）; int AddTail（const T data）; void RemoveAt（const int pos）; void RemoveHead（）; void RemoveTail（）; void RemoveAll（）; T& GetTail（）; T GetTail（） const; GetHead（）; T GetHead（） const; GetAt（const int

3、pos）; T GetAt（const int pos） const; void SetAt（const int pos, T data）; int Find（const T data） const; int FindCircle（） const; int FindCross（SList& testlist）; protected: int m_nCount; *m_pNodeHead; ; inline SList&:SList（） : m_nCount（0）, m_pNodeHead（NULL） template&SList（const T & m_nCount（0）, m_pNodeHe

4、ad（NULL） AddHead（initdata）; template&SList（const SList& other） : m_nCount（0）, m_pNodeHead（NULL） if（other.m_nCount&0） for（int i=1;i&=other.m_nCount;i+） AddTail（other.GetAt（i）; template&operator=（const SList& other） if（this=&other） return *this; if（m_nCount&0） RemoveAll（）; if（other.m_nCount& return *t

5、his;SList（） RemoveAll（）; /reverse the list template& inline void SList&Invert（） if（m_nCount&=1） return; *curNod,*preNod,*nextNod; curNod=m_pNodeHead; preNod=NULL; for（int i=1;=m_nCount;i+） nextNod=curNod-&next; curNod-&next=preNod; preNod=curNod; curNod=nextNod; m_pNodeHead=preNod; return; inline in

6、t SList&IsEmpty（） const return 0 = m_nCount;AddHead（const T data） /*Node& *pNewNode; try pNewNode = new Node&; catch （std:bad_alloc&） return 0; pNewNode-&data = data; pNewNode-&next = m_pNodeHead; m_pNodeHead = pNewNode; +m_nCount; return 1;*/ return InsertBefore（1,data）;AddTail（const T data） return

7、 InsertAfter（GetCount（）, data）; / if success, return the position of the new node. / if fail, return 0. template&InsertBefore（const int pos, const T data） int i; int nRetPos; *pTmpNode1; *pTmpNode2;） nRetPos = 0; return nRetPos; / if the list is empty, replace the head node with the new node. if （NU

8、LL = m_pNodeHead） pNewNode-&next = NULL; nRetPos = 1; / is pos range valid? ASSERT（1 &= pos & pos &= m_nCount）; / insert before head node? if （1 = pos） pNewNode-& / if the list is not empty and is not inserted before head node, / seek to the pos of the list and insert the new node before it. pTmpNod

9、e1 = m_pNodeHead; for （i = 1; i & pos; +i） pTmpNode2 = pTmpNode1; pTmpNode1 = pTmpNode1-&next = pTmpNode1; pTmpNode2-&next = pNewNode; nRetPos = pos;InsertAfter（const int pos, const T data） int i; *pTmpNode; / if the list is not empty, / seek to the pos of the list and insert the new node after it.

10、pTmpNode = m_pNodeHead; +i） pTmpNode = pTmpNode-&next = pTmpNode-& pTmpNode-& nRetPos = pos + 1;GetCount（） const return m_nCount;RemoveAt（const int pos） ASSERT（1 & int i; pTmpNode1 = m_pNodeHead; / head node? if （1 = pos） m_pNodeHead = m_pNodeHead-& delete pTmpNode1; -m_nCount; for （i = 1; +i） / we

11、will get the previous node of the target node after / the for loop finished, and it would be stored into pTmpNode2 pTmpNode2 = pTmpNode1; pTmpNode2-&next = pTmpNode1-&RemoveHead（） ASSERT（0 ! RemoveAt（1）;RemoveTail（） ASSERT（0 ! RemoveAt（m_nCount）;RemoveAll（） int i; int nCount; nCount = m_nCount; if（n

12、Count=0） return; for （i = 0; nCount; +i） pTmpNode = m_pNodeHead-& delete m_pNodeHead; m_pNodeHead = pTmpNode; m_pNodeHead=NULL; m_nCount = 0; inline T&GetTail（） ASSERT（0 ! *pTmpNode = m_pNodeHead; return pTmpNode-&data; inline T SList&GetTail（） const ASSERT（0 !GetHead（） ASSERT（0 ! return m_pNodeHead

13、-&GetHead（） const ASSERT（0 !GetAt（const int pos） ASSERT（1 &GetAt（const int pos） const ASSERT（1 &SetAt（const int pos, T data） ASSERT（1 & pTmpNode-&Find（const T data） const int i; for （i = 0; +i） if （data = pTmpNode-&data） return i + 1; pTmpNode = pTmpNode-& return 0; /*判断链表是否有环，如果有环则返回环的首结点位置，否则返回0*/

14、 template&FindCircle（） const if（0=m_nCount） return 0; Node&* p1=m_pNodeHead;* p2=m_pNodeHead; /*判断链表是否有环，当p1=p2时说明链表有环，程序跳出循环。如果p2一直走到链表尽头则说明没有环。*/ do if（p1!=NULL&p2!p2-&next!=NULL） p1=p1-& p2=p2-&next-& else return 0; while（p1!=p2）; /*求出环的起点节点，并将其返回*/ p2=m_pNodeHead; while（p1!=p2） p1=p1-& int i; p2

15、=m_pNodeHead; for（i=1;i+） if（p1=p2） break; return i; /*判断两个链表是否交叉，如果交叉返回首个交叉节点位置（在本链表中的位置，而不是testlist中的位置），否则返回0。 假定：这两个链表本身均无环*/ template&FindCross（SList& testlist） if（0=m_nCount|0=testlist.m_nCount） return 0; if（FindCircle（）|testlist.FindCircle（） return 0; /*将第二个链表接在第一个链表后面*/ Node&* pTail=m_pNodeHead;m_nCount;i+） pTail=pTail-& pTail=testlist.m_pNodeHead; m_nCount+=testlist.m_nCount; int i=FindCircle（）; pTail=NULL; m_nCount-=testlist.m_nCount; return i; #endif