学步园

以下是常用链表的算法：

#include <stdio.h><br /> #include <vector><br /> #include <cassert><br /> using std::vector;<br /> typedef struct _node<br /> {<br /> int value;<br /> _node* pNext;<br /> _node(int va):value(va),pNext(0){}<br /> }NODE,*PNODE;</p> <p>//创建一个链表<br /> void CreateList(PNODE& pList);<br /> //释放链表的内存<br /> void DeleteList(PNODE pList);<br /> //输出链表<br /> void OutPut(PNODE pList);<br /> //链表逆序<br /> void ConvertList(PNODE& pList);<br /> //判断是否为循环链表<br /> bool IsCircle(PNODE pList);<br /> //打印出倒数第K个节点的值<br /> void PrintNode(PNODE pList ,int k);<br /> //链表排序<br /> void SortNode(PNODE pList);<br /> //合并两个链表<br /> PNODE Merge(PNODE list1,PNODE list2);<br /> //删除指定位置的的元素<br /> void Delete(PNODE* pList,int iDel);<br /> //在指定位置插入元素<br /> void Insert(PNODE* pList,int iInsert,int nVal);<br /> int main()<br /> {<br /> PNODE pHead = NULL;<br /> CreateList(pHead);<br /> OutPut(pHead);<br /> //ConvertList(pHead);<br /> //OutPut(pHead);<br /> //if (IsCircle(pHead))<br /> // printf("have a circle/n");<br /> //else<br /> // printf("have no a circle/n");<br /> //PrintNode(pHead,9);<br /> SortNode(pHead);<br /> OutPut(pHead);<br /> DeleteList(pHead);<br /> return 0;<br /> };</p> <p>void CreateList(PNODE& pList)<br /> {<br /> printf("end to -1/n");<br /> int value;<br /> scanf("%d",&value);<br /> while(value != -1)<br /> {<br /> PNODE p = new NODE(value);<br /> p->pNext = pList;<br /> pList = p;<br /> scanf("%d",&value);<br /> }</p> <p>}</p> <p>void DeleteList(PNODE pList)<br /> {<br /> PNODE p = pList;<br /> PNODE pTemp;<br /> while (p!=NULL)<br /> {<br /> pTemp = p;<br /> p=p->pNext;<br /> delete pTemp;<br /> }<br /> }<br /> void OutPut(PNODE pList)<br /> {<br /> PNODE p = pList;<br /> while(p!=NULL)<br /> {<br /> printf("%d ",p->value);<br /> p=p->pNext;<br /> }</p> <p> printf("/n");<br /> }</p> <p>void ConvertList(PNODE& pList)<br /> {<br /> PNODE pre,next,now;<br /> now = pList;<br /> pre = NULL;<br /> while (now!=NULL)<br /> {<br /> next = now->pNext;<br /> now->pNext = pre;<br /> pre = now;<br /> now = next;<br /> }</p> <p> pList = pre;<br /> }</p> <p>bool IsCircle(PNODE pList)<br /> {<br /> if (pList == NULL)<br /> return false;</p> <p> PNODE p1,p2;<br /> p1 = pList;<br /> p2 = pList->pNext;<br /> while (p2 != NULL && p2->pNext != NULL)<br /> {<br /> p1 = p1->pNext;<br /> p2 = p2->pNext->pNext;<br /> if (p1 == p2)<br /> return true;<br /> }</p> <p> return false;<br /> }</p> <p>void PrintNode(PNODE pList ,int k)<br /> {<br /> vector<PNODE> vecSave;<br /> int total = 0;<br /> PNODE pHead = pList;<br /> while(pHead != NULL)<br /> {<br /> if (total%3==0)<br /> vecSave.push_back(pHead);<br /> ++total;<br /> pHead = pHead->pNext;<br /> }</p> <p> int pos = total - k;<br /> int index = pos/3;<br /> int y = pos%3;<br /> PNODE pSearchList = vecSave[index];<br /> for (int i = 0;i<y;i++)<br /> pSearchList = pSearchList->pNext;</p> <p> printf("%d/n",pSearchList->value);<br /> }</p> <p>void SortNode(PNODE pList)<br /> {<br /> PNODE pHead = pList;<br /> for (;pHead->pNext!=NULL;pHead = pHead->pNext)<br /> {<br /> PNODE p = pHead->pNext;<br /> while(p!=NULL)<br /> {<br /> if (p->value > pHead->value)<br /> {<br /> int temp = p->value;<br /> p->value = pHead->value;<br /> pHead->value = temp;<br /> }<br /> p = p->pNext;<br /> }<br /> }<br /> }</p> <p>//要有序<br /> PNODE Merge(PNODE list1,PNODE list2)<br /> {<br /> //先排序<br /> SortNode(list1);<br /> OutPut(list1);<br /> SortNode(list2);<br /> OutPut(list2);</p> <p> PNODE pa,pb,p,q,head;<br /> pa = list1;<br /> pb = list2;<br /> head = p = q = NULL;<br /> while(pa != NULL && pb != NULL)<br /> {<br /> if(pa->value > pb->value)<br /> {<br /> p = pa;<br /> pa = pa->pNext;<br /> }<br /> else<br /> {<br /> p = pb;<br /> pb = pb->pNext;<br /> }</p> <p> p->pNext = head;<br /> head = p;<br /> }</p> <p> if(pa != NULL)<br /> q = pa;<br /> else<br /> q = pb;<br /> while(q != NULL)<br /> {<br /> p = q;<br /> q = q->pNext;<br /> p->pNext = head;<br /> head = p;<br /> }</p> <p> return head;<br /> }</p> <p>void Delete(PNODE* pList,int iDel)<br /> {<br /> assert(pList != NULL);<br /> assert(iDel > 0);<br /> PNODE pHead = *pList;<br /> PNODE pDel;<br /> //特殊情况<br /> if(iDel == 1)<br /> {<br /> pDel = pHead;<br /> pHead = pHead->pNext;<br /> *pList = pHead;<br /> delete pDel;<br /> return ;<br /> }</p> <p> //一般情况，移动到iDel-1的位置<br /> for(int i = 2;i<iDel && pHead->pNext;i++)<br /> pHead = pHead->pNext;</p> <p> if(pHead->pNext != NULL)<br /> {<br /> PNODE pDel = pHead->pNext;<br /> pHead->pNext = pHead->pNext->pNext;<br /> delete pDel;<br /> }<br /> }</p> <p>void Insert(PNODE* pList,int iInsert,int nVal)<br /> {<br /> assert(*pList != NULL);<br /> assert(iInsert > 0);<br /> PNODE pHead = *pList;<br /> PNODE pNew= new NODE(nVal);</p> <p> //特殊情况<br /> if(iInsert == 1)<br /> {<br /> pNew->pNext = pHead;<br /> pHead = pNew;<br /> *pList = pHead;<br /> return;<br /> }</p> <p> for(int i = 2;2 < iInsert && pHead->pNext ;i++)<br /> pHead = pHead->pNext;</p> <p> if(pHead->pNext != NULL)<br /> {<br /> pNew->pNext = pHead->pNext;<br /> pHead->pNext = pNew;<br /> }<br /> else<br /> {<br /> pHead ->pNext = pNew;<br /> pNew->pNext = NULL;<br /> }<br /> }