《一步一步写算法(之双向链表).doc》由会员分享，可在线阅读，更多相关《一步一步写算法(之双向链表).doc（4页珍藏版）》请在金锄头文库上搜索。
1、一步一步写算法（之双向链表）【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：】 前面的博客我们介绍了单向链表。那么我们今天介绍的双向链表，顾名思义，就是数据本身具备了左边和右边的双向指针。双向链表相比较单向链表，主要有下面几个特点： （1）在数据结构中具有双向指针 （2）插入数据的时候需要考虑前后的方向的操作 （3）同样，删除数据的是有也需要考虑前后方向的操作 那么，一个非循环的双向链表操作应该是怎么样的呢？我们可以自己尝试一下： （1）定义双向链表的基本结构1. typedefstruct_DOUBLE_LINK_NODE2. 3. intdata;4. struct_DOUBL
2、E_LINK_NODE*prev;5. struct_DOUBLE_LINK_NODE*next;6. DOUBLE_LINK_NODE; （2）创建双向链表节点1. DOUBLE_LINK_NODE*create_double_link_node(intvalue)2. 3. DOUBLE_LINK_NODE*pDLinkNode=NULL;4. pDLinkNode=(DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE);5. assert(NULL!=pDLinkNode);6. 7. memset(pDLinkNode,0,sizeof(D
3、OUBLE_LINK_NODE);8. pDLinkNode-data=value;9. returnpDLinkNode;10. （3）删除双向链表1. voiddelete_all_double_link_node(DOUBLE_LINK_NODE*pDLinkNode)2. 3. DOUBLE_LINK_NODE*pNode;4. if(NULL=*pDLinkNode)5. return;6. 7. pNode=*pDLinkNode;8. *pDLinkNode=pNode-next;9. free(pNode);10. delete_all_double_link_node(pDL
4、inkNode);11. （4）在双向链表中查找数据1. DOUBLE_LINK_NODE*find_data_in_double_link(constDOUBLE_LINK_NODE*pDLinkNode,intdata)2. 3. DOUBLE_LINK_NODE*pNode=NULL;4. if(NULL=pDLinkNode)5. returnNULL;6. 7. pNode=(DOUBLE_LINK_NODE*)pDLinkNode;8. while(NULL!=pNode)9. if(data=pNode-data)10. returnpNode;11. pNode=pNode-n
5、ext;12. 13. 14. returnNULL;15. （5）双向链表中插入数据1. STATUSinsert_data_into_double_link(DOUBLE_LINK_NODE*ppDLinkNode,intdata)2. 3. DOUBLE_LINK_NODE*pNode;4. DOUBLE_LINK_NODE*pIndex;5. 6. if(NULL=ppDLinkNode)7. returnFALSE;8. 9. if(NULL=*ppDLinkNode)10. pNode=create_double_link_node(data);11. assert(NULL!=p
6、Node);12. *ppDLinkNode=pNode;13. (*ppDLinkNode)-prev=(*ppDLinkNode)-next=NULL;14. returnTRUE;15. 16. 17. if(NULL!=find_data_in_double_link(*ppDLinkNode,data)18. returnFALSE;19. 20. pNode=create_double_link_node(data);21. assert(NULL!=pNode);22. 23. pIndex=*ppDLinkNode;24. while(NULL!=pIndex-next)25.
7、 pIndex=pIndex-next;26. 27. pNode-prev=pIndex;28. pNode-next=pIndex-next;29. pIndex-next=pNode;30. returnTRUE;31. （6）双向链表中删除数据1. STATUSdelete_data_from_double_link(DOUBLE_LINK_NODE*ppDLinkNode,intdata)2. 3. DOUBLE_LINK_NODE*pNode;4. if(NULL=ppDLinkNode|NULL=*ppDLinkNode)5. returnFALSE;6. 7. pNode=fi
8、nd_data_in_double_link(*ppDLinkNode,data);8. if(NULL=pNode)9. returnFALSE;10. 11. if(pNode=*ppDLinkNode)12. if(NULL=(*ppDLinkNode)-next)13. *ppDLinkNode=NULL;14. else15. *ppDLinkNode=pNode-next;16. (*ppDLinkNode)-prev=NULL;17. 18. 19. else20. if(pNode-next)21. pNode-next-prev=pNode-prev;22. pNode-pr
9、ev-next=pNode-next;23. 24. 25. free(pNode);26. returnTRUE;27. （7）统计双向链表中数据的个数1. intcount_number_in_double_link(constDOUBLE_LINK_NODE*pDLinkNode)2. 3. intcount=0;4. DOUBLE_LINK_NODE*pNode=(DOUBLE_LINK_NODE*)pDLinkNode;5. 6. while(NULL!=pNode)7. count+;8. pNode=pNode-next;9. 10. returncount;11. （8）打印双向链表中数据1. voidprint_double_link_node(constDOUBLE_LINK_NODE*pDLinkNode)2. 3. DOUBLE_LINK_NODE*pNode=(DOUBLE_LINK_NODE*)pDLinkNode;4. 5. while(NULL!=pNode)6. printf(%dn,pNode-data);7. pNode=pNode-next;8. 9. 注意： 今天我们讨论的双向链表是非循环的，大家可以考虑一下如果改成循环双向链表，应该怎么写？如果是有序的循环双向链表，又该怎么写？【预告： 下面我们讨论的是循环单向链表】
