Chinaunix首页 | 论坛 | 博客
  • 博客访问: 753477
  • 博文数量: 274
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 862
  • 用 户 组: 普通用户
  • 注册时间: 2015-10-24 15:31
个人简介

不合格的程序猿

文章分类

全部博文(274)

文章存档

2019年(3)

2018年(1)

2017年(4)

2016年(160)

2015年(106)

我的朋友

分类: C/C++

2016-04-07 18:05:48

链表逆序
查找倒数第K个结点
链表去重
检查链表环路
查找链表环路起始结点


点击(此处)折叠或打开

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <time.h>

  5. #define MULTIPLE_NUMBER 9U

  6. typedef struct tagListNode{
  7.     int iData;
  8.     struct tagListNode *pstNext;
  9. }LIST_NODE_S;

  10. /* 在链表尾追加结点 */
  11. LIST_NODE_S *list_AddTail(LIST_NODE_S *pstHead, LIST_NODE_S *pstAddNode)
  12. {
  13.     LIST_NODE_S *pstNode;
  14.     LIST_NODE_S *pstTail;

  15.     if (NULL == pstHead)
  16.     {
  17.         pstHead = pstAddNode;
  18.         pstHead->pstNext = NULL;
  19.         return pstHead;
  20.     }

  21.     if (pstHead != pstAddNode)
  22.     {
  23.         for (pstNode = pstHead; NULL != pstNode; pstNode = pstNode->pstNext)
  24.         {
  25.             pstTail = pstNode;
  26.         }
  27.     
  28.         pstTail->pstNext = pstAddNode;
  29.         pstTail->pstNext->pstNext = NULL;
  30.     }

  31.     return pstHead;
  32. }

  33. /* 创建链表 */
  34. LIST_NODE_S *list_Create(int iCount)
  35. {
  36.     LIST_NODE_S *pstHead, *pstNode;
  37.     int iLoop;

  38.     pstHead = NULL;
  39.     for (iLoop = 0; iLoop < iCount; iLoop++)
  40.     {
  41.         pstNode = (LIST_NODE_S *)malloc(sizeof(LIST_NODE_S));
  42.         if (NULL == pstNode)
  43.         {
  44.             break;
  45.         }

  46.         memset(pstNode, 0, sizeof(LIST_NODE_S));
  47.         pstNode->iData = rand() % (MULTIPLE_NUMBER * iCount);

  48.         pstHead = list_AddTail(pstHead, pstNode);
  49.     }

  50.     return pstHead;
  51. }

  52. /* 打印链表 */
  53. void list_Display(LIST_NODE_S *pstHead)
  54. {
  55.     LIST_NODE_S *pstNode;

  56.     for (pstNode = pstHead; NULL != pstNode; pstNode = pstNode->pstNext)
  57.     {
  58.         printf("\t%d", pstNode->iData);
  59.     }
  60.     printf("\n\n");

  61.     return;
  62. }

  63. /* 单链表逆序 */
  64. LIST_NODE_S *list_Reverse(LIST_NODE_S *pstHead)
  65. {
  66.     LIST_NODE_S *pstA, *pstB, *pstC;

  67.     for (pstA = pstHead, pstB = pstA->pstNext; NULL != pstB; pstC = pstB->pstNext)
  68.     {
  69.         pstC = pstB->pstNext;
  70.         pstB->pstNext = pstA;
  71.         if (pstA == pstHead)
  72.         {
  73.             pstA->pstNext = NULL;
  74.         }
  75.         pstA = pstB;
  76.         if (NULL == pstC)
  77.         {
  78.             pstHead = pstB;
  79.             break;
  80.         }
  81.         pstB = pstC;
  82.     }

  83.     return pstHead;
  84. }

  85. /* 删除链表中的重复结点,不使用临时缓冲区 */
  86. void list_RemoveRepeat(LIST_NODE_S *pstHead)
  87. {
  88.     LIST_NODE_S *pstCurrent, *pstNode, *pstDel;

  89.     if (NULL == pstHead)
  90.     {
  91.         return;
  92.     }

  93.     for (pstCurrent = pstHead; NULL != pstCurrent; pstCurrent = pstCurrent->pstNext)
  94.     {
  95.         pstNode = pstCurrent;
  96.         for (pstNode = pstCurrent; NULL != pstNode->pstNext;)
  97.         {
  98.             if (pstNode->pstNext->iData == pstCurrent->iData)
  99.             {
  100.                 pstDel = pstNode->pstNext;
  101.                 pstNode->pstNext = pstNode->pstNext->pstNext;
  102.                 free(pstDel);
  103.             }
  104.             else
  105.             {
  106.                 pstNode = pstNode->pstNext;
  107.             }
  108.         }
  109.     }

  110.     return;
  111. }

  112. /* 找出单项链表中倒数第k个结点 */
  113. LIST_NODE_S *list_FindLastCountNode(LIST_NODE_S *pstHead, int iCount)
  114. {
  115.     LIST_NODE_S *pstA, *pstB;
  116.     int iLoop;

  117.     if (NULL == pstHead)
  118.     {
  119.         return pstHead;
  120.     }

  121.     pstA = pstHead;

  122.     for (pstB = pstA, iLoop = 0; NULL != pstB && iLoop < iCount; iLoop++, pstB = pstB->pstNext);
  123.     if (iLoop < iCount -1)
  124.     {
  125.         return NULL;
  126.     }

  127.     for (; NULL != pstB; pstB = pstB->pstNext, pstA = pstA->pstNext);

  128.     return pstA;
  129. }

  130. /* 删除单线链表中间的某个结点,嘉定只能访问该节点,pstDelNode不是尾节点 */
  131. void list_DelTheGivenNode(LIST_NODE_S *pstDelNode)
  132. {
  133.     LIST_NODE_S *pstNode;

  134.     if (NULL == pstDelNode || NULL == pstDelNode->pstNext)
  135.     {
  136.         return;
  137.     }

  138.     pstDelNode->iData = pstDelNode->pstNext->iData;
  139.     pstNode = pstDelNode->pstNext;
  140.     if (NULL != pstNode->pstNext)
  141.     {
  142.         pstDelNode->pstNext = pstNode->pstNext;
  143.     }
  144.     free(pstNode);

  145.     return;
  146. }

  147. /* 以给定值x为基准将链表分成两部分,所有小于x的结点排在大于等于x的结点之前 */
  148. LIST_NODE_S *list_ReorganizeByGivenNumber(LIST_NODE_S *pstHead, int iNumber)
  149. {
  150.     LIST_NODE_S *pstHeadBefore, *pstHeadAfter, *pstNode;
  151.     LIST_NODE_S *pstBeforeTail, *pstAfterTail, *pstNext;

  152.     if (NULL == pstHead)
  153.     {
  154.         return;
  155.     }

  156.     pstHeadBefore = NULL;
  157.     pstHeadAfter = NULL;
  158.     for (pstNode = pstHead; NULL != pstNode; pstNode = pstNext)
  159.     {
  160.         if (pstNode->iData < iNumber)
  161.         {
  162.             pstNext = pstNode->pstNext;
  163.             pstHeadBefore = list_AddTail(pstHeadBefore, pstNode);
  164.             pstBeforeTail = pstNode;
  165.         }
  166.         else
  167.         {
  168.             pstNext = pstNode->pstNext;
  169.             pstHeadAfter = list_AddTail(pstHeadAfter, pstNode);
  170.             pstAfterTail = pstNode;
  171.         }
  172.     }

  173.     if (NULL != pstHeadBefore)
  174.     {
  175.         pstBeforeTail->pstNext = pstHeadAfter;
  176.         pstHead = pstHeadBefore;
  177.     }
  178.     else
  179.     {
  180.         pstHead = pstHeadAfter;
  181.     }
  182.     pstAfterTail->pstNext = NULL;

  183.     return pstHead;
  184. }

  185. /* 检查链表是否有环路 */
  186. int list_CheckRing(LIST_NODE_S *pstHead)
  187. {
  188.     LIST_NODE_S *pstA, *pstB;
  189.     int iRet = 0;

  190.     for (pstA = pstHead, pstB = pstHead; NULL != pstA && NULL != pstA->pstNext; pstA = pstA->pstNext->pstNext, pstB = pstB->pstNext)
  191.     {
  192.         if (pstA == pstB)
  193.         {
  194.             iRet = 1;
  195.             break;
  196.         }
  197.     }

  198.     return iRet;
  199. }

  200. /* 给定一个有环链表,返回环路的开头节点 */
  201. LIST_NODE_S *list_FindTheStartNodeOfRing(LIST_NODE_S *pstHead)
  202. {
  203.     LIST_NODE_S *pstA, *pstB;
  204.     int iIsRing = 0;

  205.     for (pstA = pstHead, pstB = pstHead; NULL != pstA && NULL != pstA->pstNext; pstA = pstA->pstNext->pstNext, pstB = pstB->pstNext)
  206.     {
  207.         if (pstA == pstB)
  208.         {
  209.             iIsRing = 1;
  210.             break;
  211.         }
  212.     }

  213.     if (0 == iIsRing)
  214.     {
  215.         return NULL;
  216.     }

  217.     for (pstA = pstHead; pstA == pstB; pstA = pstA->pstNext, pstB = pstB->pstNext);

  218.     return pstA;
  219. }

  220. /* 检查链表是否回文: 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 0 */
  221. int list_IsRing(LIST_NODE_S *pstHead)
  222. {
  223.     int iRet = 0;
  224.     
  225.     /*
  226.         思路:
  227.             使用快慢runner的方法迭代链表,
  228.             循环的每一步,
  229.             将慢速runner的数据入栈,
  230.             在快速runner到达链表尾时,
  231.             慢速runner刚好位于链表中间位置。
  232.             此时链表前半部分已经压入栈中(反序的)
  233.             然后,(注意处理链表是奇数长度的情况)
  234.             迭代访问剩下的结点,
  235.             每次迭代时,
  236.             比较当前结点和栈顶元素。
  237.             若结果相同,
  238.             则该链表是回文序列。
  239.     */
  240.     
  241.     return iRet;
  242. }

  243. void list_test(void)
  244. {
  245.     int iMaxCount = 7;
  246.     int iCount = 3;
  247.     int iBaseNumber = 16;
  248.     LIST_NODE_S *pstHead, *pstNode;

  249.     srand(time(0));

  250.     pstHead = list_Create(iMaxCount);
  251.     printf("the original list:\n");
  252.     list_Display(pstHead);

  253.     pstHead = list_Reverse(pstHead);
  254.     printf("the list after reverse:\n");
  255.     list_Display(pstHead);

  256.     pstNode = list_FindLastCountNode(pstHead, iCount);
  257.     printf("the last %d node is %d\n", iCount, pstNode->iData);

  258.     list_DelTheGivenNode(pstNode);
  259.     printf("the list after delete the given node %d\n", pstNode->iData);
  260.     list_Display(pstHead);

  261.     list_RemoveRepeat(pstHead);
  262.     printf("the list after remove the repeat node:\n");
  263.     list_Display(pstHead);

  264.     pstHead = list_ReorganizeByGivenNumber(pstHead, iBaseNumber);
  265.     printf("the list after reorganize by given number %d:\n", iBaseNumber);
  266.     list_Display(pstHead);
  267.     
  268.     return;
  269. }

  270. void main(void)
  271. {
  272.     list_test();

  273.     return;
  274. }


阅读(1090) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~