数据结构模版----单链表SimpleLinkList[不带头结点](C语言实现)

简介:

下面给出的是单链表不带头结点的另一种实现方式,也是最复杂的一种方式

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <stdbool.h>  
  4. #include <assert.h>  
  5.   
  6. //#define DEBUG             // 调试插桩信息宏  
  7.   
  8. ///*////////////////////////////////////////////////////////////////////////////  
  9. ///  
  10. /// 带头结点的单链表结构体  
  11. ///  
  12. ///*////////////////////////////////////////////////////////////////////////////  
  13.   
  14. typedef int ElemType;       // 自定义数据类型  
  15.   
  16. //typedef struct LinkListNode*  PLinkListNode;          // 链表结点指针域  
  17.   
  18. // 链表结点数据域  
  19. typedef struct LinkListNode  
  20. {  
  21.     ElemType            m_data;         // 数据域  
  22.     struct LinkListNode *m_next;            // 指针域  
  23. }LinkListNode;  
  24.   
  25. // 带头结点的单项链表  
  26. typedef struct LinkListNode*  LinkList;  
  27.   
  28.   
  29. ///*////////////////////////////////////////////////////////////////////////////  
  30. ///  
  31. /// 初始化单链表  
  32. ///  
  33. /// 初始化单链表  
  34. /// void InitLinkList(LinkList *list)  
  35. ///*///////////////////////////////////////////////////////////////////////////  
  36.   
  37. /** 
  38. void InitLinkList(LinkList *list) 
  39. 参数 
  40.     list    :   指向一个链表指针,此处传入表头地址 
  41. 返回值 
  42.     无 
  43. 功能 
  44.     初始化单链表, 执行以下操作 
  45.     ①开辟头结点的空间 ②进行必要的初始化[头结点的初始化和单链表结点数目的初始化] 
  46. 注意 
  47.     使用InitLinkList初始化的单链表(初始化时malloc了头结点m_head的空间) 
  48.     而使用用FinitLinkList来进行后处理(后处理时free了头结点的m_head空间) 
  49.     以免发生内存泄漏 
  50. */  
  51. void InitLinkList(LinkList *list)  
  52. {  
  53.     (*list) = NULL;         // 初始化只头指针  
  54. }  
  55.   
  56.   
  57. ///*////////////////////////////////////////////////////////////////////////////  
  58. ///  
  59. /// 销毁以及后处理单链表  
  60. ///  
  61. /// 后处理单链表,  
  62. /// void FinitLinkList(LinkList *list)  
  63. ///  
  64. /// 清空单链表中的所有元素  
  65. /// void ClearLinkList(LinkList *list)  
  66. ///*////////////////////////////////////////////////////////////////////////////  
  67.   
  68. /** 
  69. void FinitLinkList(LinkList *list) 
  70. 参数 
  71.     list    :   指向一个链表指针,此处传入表头地址 
  72. 返回值 
  73.     无 
  74. 功能 
  75.     后处理单链表, 执行以下操作 
  76.     ①开辟头结点的空间 ②进行必要的初始化[头结点的初始化和单链表结点数目的初始化] 
  77. 注意 
  78.     使用InitLinkList初始化的单链表(初始化时malloc了头结点m_head的空间) 
  79.     而使用用FinitLinkList来进行后处理(后处理时free了头结点的m_head空间) 
  80.     以免发生内存泄漏 
  81. */  
  82. void FinitLinkList(LinkList *list)  
  83. {  
  84.     (*list) = NULL;  
  85. }  
  86.   
  87.   
  88.   
  89. /** 
  90. void ClearLinkList(LinkList *list) 
  91. 参数 
  92.     list    :   指向一个链表指针,此处传入表头地址 
  93. 返回值 
  94.     无 
  95. 功能 
  96.     清空单链表中的所有元素 
  97. */  
  98. void ClearLinkList(LinkList *list)  
  99. {  
  100.     while((*list) != NULL)  
  101.     {  
  102.         DeleteNode(list, 0);  
  103.     }  
  104. }  
  105.   
  106.   
  107. ///*////////////////////////////////////////////////////////////////////////////  
  108. ///  
  109. /// 查找函数  
  110. ///  
  111. /// 查找到链表list中第position个结点  
  112. /// LinkListNode* FindPosNode(LinkList *list, int position)  
  113. ///  
  114. /// 在链表list中找到currNode的前一个结点  
  115. /// LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode)  
  116. ///  
  117. /// 判断结点node指向的区域是不是链表中的结点  
  118. /// int IsNodeInList(LinkList *list, LinkListNode *node)  
  119. ///  
  120. /// 找到数据域为data的结点首次出现的位置并返回结点信息  
  121. /// LinkListNode* FindDataNode(LinkList *list, ElemType data, int *position)  
  122. ///*////////////////////////////////////////////////////////////////////////////  
  123.   
  124. /** 
  125. LinkListNode* FindPosNode(LinkList *list, int position) 
  126.  
  127. 参数 
  128.     list    :   指向一个链表指针,此处传入表头地址 
  129.     positon :   带查找的链表指针的位置 
  130. 返回值 
  131.     若成功返回指向待查找结点的指针 
  132.     若失败返回NULL 
  133. 功能 
  134.     该函数的功能是:    查找到链表list中第position个结点 
  135. */  
  136. LinkListNode* FindPosNode(LinkList *list, int position)  
  137. {  
  138.     assert(list != NULL);  
  139.     assert((*list) != NULL);                                    // 链表不能为空  
  140.     assert(position >= 0 && position < LengthLinkList(list));     // 查找的位置只能在[0, length)  
  141.   
  142.     LinkListNode    *pNode  = (LinkListNode *)(*list);  
  143.     int             pos     = 0;  
  144.   
  145.     while(pNode != NULL && pos < position)       // 遍历单链表,找到第position个结点的位置  
  146.     {  
  147.         pNode = pNode->m_next;  
  148.         pos++;  
  149.     }  
  150.   
  151.     if(pNode == NULL || pos < position)  
  152.     {  
  153.         return NULL;  
  154.     }  
  155.     else  
  156.     {  
  157. #ifdef DEBUG  
  158.         printf("Find the %d point SUCCESS...[%p]\n", position, pNode);  
  159. #endif // DEBUG  
  160.         return pNode;  
  161.     }  
  162. }  
  163.   
  164. /** 
  165. LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode); 
  166.  
  167. 参数 
  168.     list        :   指向一个链表指针,此处传入表头地址 
  169.     currNode    :   待查找的链表指针的位置 
  170. 返回值 
  171.     若成功返回指向待查找结点的指针 
  172.     若失败返回NULL 
  173. 功能 
  174.     在链表list中找到currNode的前一个结点 
  175. */  
  176.   
  177. LinkListNode *FindPrevNode(LinkList *list, LinkListNode *currNode)  
  178. {  
  179.     assert(list !=  NULL);  
  180.     assert(currNode != NULL);  
  181.   
  182.     LinkListNode *pNode = (LinkListNode *)(*list);  
  183.   
  184.     while(pNode->m_next != NULL && pNode->m_next != currNode)  
  185.     {  
  186.         pNode = pNode->m_next;  
  187.     }  
  188.   
  189.     if(pNode->m_next == currNode)                // 查找成功  
  190.     {  
  191.         return pNode;  
  192.     }  
  193.     else                                        // 查找失败  
  194.     {  
  195.         return NULL;  
  196.     }  
  197. }  
  198.   
  199. /** 
  200. int IsNodeInList(LinkList *list, LinkListNode *node) 
  201.  
  202. 参数 
  203.     list    :   指向一个链表指针,此处传入表头地址 
  204.     node    :   指向待查找的结点的指针 
  205. 返回值 
  206.     若成功 返回结点node在链表中的位置 
  207.     若失败 返回-1 
  208. 功能 
  209.     判断结点node指向的区域是不是链表中的结点 
  210. */  
  211. int IsNodeInList(LinkList *list, LinkListNode *node)  
  212. {  
  213.     assert(list != NULL);                                   // 链表不能为空   assert(Node != NULL);                                   // 待查找的指针不能为空  
  214.   
  215.     LinkListNode    *pNode  = (LinkListNode *)(*list);  
  216.     int             pos     = -1;  
  217.   
  218.     while(pNode != NULL && pNode != node)       // 遍历单链表,找到第position个结点的位置  
  219.     {  
  220.         pNode = pNode->m_next;  
  221.         pos++;  
  222.     }  
  223.   
  224.     if(pNode == NULL)  
  225.     {   // 查找成功  
  226.         return -1;  
  227.     }  
  228.     else  
  229.     {   // 查找失败  
  230. #ifdef DEBUG  
  231.         printf("Find the [%p] point in the first %d pointer of the list...\n", node, pos);  
  232. #endif // DEBUG  
  233.         return pos;  
  234.     }  
  235. }  
  236.   
  237.   
  238. /** 
  239. LinkListNode* FindDataNode(LinkList *list, ElemType data, int *position 
  240.  
  241. 参数 
  242.     list    :   指向一个链表指针,此处传入表头地址 
  243.     data    :   待查找的结点的数据信息 
  244. 返回值 
  245.     若成功 返回结点node在链表中的位置 
  246.     若失败 返回-1 
  247. 功能 
  248.     找到数据域为data的结点首次出现的位置并返回结点信息 
  249. */  
  250. LinkListNode* FindDataNode(LinkList *list, ElemType data, int *position)  
  251. {  
  252.     LinkListNode *node = (LinkListNode *)(*list);  
  253.     int pos = 0;  
  254.     while(node != NULL && node->m_data != data)  
  255.     {  
  256.         node = node->m_next;  
  257.         pos++;  
  258.     }  
  259.     *position = pos;                // 将出现的位置传递回去  
  260.   
  261.     return node;                    // 返回结点的信息  
  262. }  
  263. ///*////////////////////////////////////////////////////////////////////////////  
  264. ///  
  265. /// 插入函数  
  266. ///  
  267. /// 将数据data插入链表的prevNode结点的下一个位置个位置  
  268. /// LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data)  
  269. ///  
  270. /// 将数据data插入链表的第position个位置  
  271. /// LinkListNode *InsertNode(LinkList *list, int position, ElemType data)  
  272. ///*////////////////////////////////////////////////////////////////////////////  
  273.   
  274. /** 
  275. void InsertNode(LinkList *list, int position, ElemType data) 
  276. 参数 
  277.     list    :   指向一个链表指针,此处传入表头地址 
  278.     positon :   待插入结点的位置 
  279.     data    :   待插入结点的数据 
  280. 返回值 
  281.     无 
  282. 功能 
  283.     该函数的功能是:    将数据data插入链表的第position个位置 
  284. */  
  285. LinkListNode* InsertNode(LinkList *list, int position, ElemType data)  
  286. {  
  287.     assert(position >=0 && position < LengthLinkList(list) + 1);  // 插入的位置应该在[0-length]  
  288.   
  289.     LinkListNode *pNode = NULL;  
  290.     LinkListNode *newNode = NULL;  
  291.   
  292.     // 为新结点开辟空间并且  
  293.     if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL)    // 为新结点开辟空间  
  294.     {   // 开辟新结点失败  
  295.         fprintf(stderr, "not enough memeory\n");  
  296.         exit(EXIT_FAILURE);  
  297.     }  
  298.     else  
  299.     {   // 开辟新结点成功并且赋值  
  300.         newNode->m_data = data;  
  301.         newNode->m_next = NULL;  
  302.     }  
  303.   
  304.     // 将新结点添加在链表中  
  305.     if(position == 0)           // 如果要插入第一个元素  
  306.     {  
  307.         // 如果当前链表是空链表  
  308.         if(list != NULL && (*list) == NULL) // LinkList list = NULL创建的空链表  
  309.         {   // 此时(*list)->m_next会出现ERROR  
  310.             (*list) = newNode;  
  311.         }  
  312.         else                                // 否则链表不是空链表  
  313.         {  
  314.             newNode->m_next = (*list);  
  315.             (*list) = newNode;  
  316.         }  
  317.     }  
  318.     else                                // 否则当前链表不是空链表  
  319.     {  
  320.         pNode = FindPosNode(list, position - 1);        // 找到待插入点的前一个指针  
  321.         // 将指针newNode连接在pNode的后面  
  322.         newNode->m_next = pNode->m_next;  
  323.         pNode->m_next = newNode;  
  324.     }  
  325. #ifdef DEBUG  
  326.     printf("Insert the value %d into list at position %d...\n", data, position);  
  327. #endif // DEBUG  
  328.   
  329.     return newNode;                 // 返回指向插入的新结点的指针  
  330. }  
  331.   
  332. /** 
  333. LinkListNode* AddNode(LinkList *list, LinkListNode *prevNode, ElemType data); 
  334. 参数 
  335.     list        :   指向一个链表指针,此处传入表头地址 
  336.     prevNode    :   待插入位置的前一个结点 
  337.     data        :   待插入结点的数据 
  338. 返回值 
  339.     无 
  340. 功能 
  341.     该函数的功能是:    将数据data插入链表的prevNode结点的下一个位置个位置 
  342. [注意]    由于单链表不存在链表头,那么第一个元素不存在前驱,因此插入第一个元素时,默认其prevNode是list 
  343. */  
  344. LinkListNode *AddNode(LinkList *list, LinkListNode *prevNode, ElemType data)  
  345. {  
  346.     assert(prevNode != NULL);                       // 插入点不能是空指针  
  347.   
  348.     LinkListNode *newNode = NULL;  
  349.     if((newNode = (LinkListNode *)malloc(sizeof(LinkListNode))) == NULL)    // 为新结点开辟空间  
  350.     {   // 开辟新结点失败  
  351.         fprintf(stderr, "not enough memeory\n");  
  352.         exit(EXIT_FAILURE);  
  353.     }  
  354.     //else  
  355.     //{  
  356.     // 开辟新结点成功  
  357.     newNode->m_data = data;  
  358.     newNode->m_next = NULL;  
  359.     if(prevNode == (LinkListNode *)(*list))     // 如果要插入的元素是第一个元素  
  360.     {  
  361.         if(list != NULL && (*list) == NULL) // 如果当前链表是空链表(LinkList list = NULL创建的空链表)  
  362.         {   // 此时(*list)->m_next会出现ERROR  
  363.             (*list) = newNode;  
  364.         }  
  365.         else                                // 否则链表不是空链表  
  366.         {  
  367.             newNode->m_next = (*list)->m_next;  
  368.             (*list) = newNode;  
  369.         }  
  370.     }  
  371.     else  
  372.     {  
  373.         // 将指针newNode连接在pNode的后面  
  374.         newNode->m_next = prevNode->m_next;  
  375.         prevNode->m_next = newNode;  
  376.     }  
  377.   
  378. #ifdef DEBUG  
  379.     printf("The new node is inserted after point pointer[%p]\n", prevNode);  
  380. #endif // DEBUG  
  381.     return newNode;  
  382. }  
  383.   
  384. ///*////////////////////////////////////////////////////////////////////////////  
  385. ///  
  386. /// 删除函数  
  387. ///  
  388. /// 删除链表list中prevNode结点之后的指针个指针  
  389. /// void DeleteNode(LinkList *list, int position)  
  390. ///  
  391. /// 删除链表list中prevNode结点之后的指针个指针  
  392. /// ElemType SubNode(LinkList *list, LinkListNode *prevNode)  
  393. ///  
  394. /// 删除链表list中prevNode结点之后的指针个指针  
  395. /// ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode)  
  396. ///*////////////////////////////////////////////////////////////////////////////  
  397.   
  398. /** 
  399. ElemType DeleteNode(LinkList *list, int position); 
  400. 参数 
  401.     list    :   指向一个链表指针,此处传入表头地址 
  402.     positon :   待删除结点的位置 
  403. 返回值 
  404.     返回待删除结点的数据域 
  405. 功能 
  406.     将单链表的第position个结点删除 
  407. */  
  408. ElemType DeleteNode(LinkList *list, int position)  
  409. {  
  410.     assert(list != NULL);                                   // 链表指针不能为空不能为空  
  411.     assert(position >=0 && position < LengthLinkList(list));      // 待删除的指针位置仅限于链表中存在的位置  
  412.   
  413.     LinkListNode    *delNode = NULL;  
  414.     ElemType        delElem = -1;  
  415.   
  416.     if(position == 0)               // 如果链表中仅剩最后一个元素  
  417.     {  
  418.         delNode = (*list);              // 待删除的结点就是头指针指向的结点  
  419.         if((*list)->m_next == NULL)  // 当前链表中仅剩最后一个元素  
  420.         {  
  421.             (*list) = NULL;         // 修改头指针为空[参数必须使用LinkListNode **形式, 因为修改了头指针的指向]  
  422.         }  
  423.         else                        // 如果链表中有多个元素  
  424.         {  
  425.             (*list) = delNode->m_next;  
  426.         }  
  427.     }  
  428.     else                                // 否则待删除的是其他结点  
  429.     {  
  430.         LinkListNode *pNode = FindPosNode(list, position - 1);          // 找到第position - 1个结点  
  431.   
  432.         // 删除pNode的后一个结点  
  433.         delNode = pNode->m_next;  
  434.         pNode->m_next = delNode->m_next;  
  435.     }  
  436.     delElem = delNode->m_data;       // 保存待删除结点的数据域  
  437.     free(delNode);  
  438. #ifdef DEBUG  
  439.     printf("Delete the list in the first [%d, %d] node...\n", position, delElem);  
  440. #endif // DEBUG  
  441.     return delElem;  
  442. }  
  443.   
  444. /** 
  445. ElemType SubNode(LinkList *list, LinkListNode *prevNode);) 
  446. 参数 
  447.     list    :   指向一个链表指针,此处传入表头地址 
  448.     positon :   待删除结点的位置 
  449. 返回值 
  450.     返回待删除结点的数据域 
  451. 功能 
  452.     删除链表list中prevNode结点之后的指针个指针 
  453. */  
  454. ElemType SubNode(LinkList *list, LinkListNode *prevNode)  
  455. {  
  456.     assert(list != NULL);                       // 链表不能为空  
  457.     assert(prevNode != NULL);                       // 待删除结点的前一个位置不能为空  
  458.     assert(IsNodeInList(list, prevNode) != -1); // 待删除位置的前一个结点必须在链表中  
  459.   
  460.     LinkListNode    *delNode = NULL;  
  461.     ElemType        delElem = -1;  
  462.   
  463.     if(prevNode == (*list))             // 如果待删除的元素是链表中第一个元素  
  464.     {  
  465.         delNode = (*list);              // 待删除的结点就是头指针指向的结点  
  466.         if((*list)->m_next == NULL)  // 当前链表中仅剩最后一个元素  
  467.         {  
  468.             (*list) = NULL;         // 修改头指针为空[参数必须使用LinkListNode **形式, 因为修改了头指针的指向]  
  469.         }  
  470.         else                        // 如果链表中有多个元素  
  471.         {  
  472.             (*list) = delNode->m_next;  
  473.         }  
  474.     }  
  475.     else                                // 否则待删除的是其他结点  
  476.     {  
  477.         // 删除prevode的后一个结点  
  478.         LinkListNode *delNode = prevNode->m_next;  
  479.         prevNode->m_next = delNode->m_next;  
  480.     }  
  481.     delElem = delNode->m_data;  
  482.     free(delNode);  
  483.   
  484.   
  485.     return delElem;  
  486. }  
  487.   
  488.   
  489. /** 
  490. ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode); 
  491. 参数 
  492.     list    :   指向一个链表指针,此处传入表头地址 
  493.     positon :   待删除结点的位置 
  494. 返回值 
  495.     返回待删除结点的数据域 
  496. 功能 
  497.     删除链表list中prevNode结点之后的指针个指针 
  498. */  
  499. ElemType DeleteCurrNode(LinkList *list, LinkListNode *currNode)  
  500. {  
  501.     assert(list != NULL);                           // 链表不能为空  
  502.     assert(currNode != NULL);                           // 待删除结点的前一个位置不能为空  
  503.     assert(IsNodeInList(list, currNode) != -1); // 待删除的结点必须在链表中  
  504.   
  505.     ElemType delElem = -1;                          // 待删除结点的数据域  
  506.     LinkListNode *delNode = NULL;                   // 指向将要删除的结点的指针  
  507.   
  508.     if(currNode->m_next != NULL)                 // 如果待删除结点不是最后一个结点  
  509.     {  
  510.         // 将currNode的后一个结点delNode作为删除结点,  
  511.         delNode = currNode->m_next;  
  512.         currNode->m_next = delNode->m_next;           //从链表中删除delNode  
  513.   
  514.         // 并将delNode的数据域保存到delNode中  
  515.         delElem = currNode->m_data;                  // delElem保存currNode的数据域  
  516.         currNode->m_data = delNode->m_data;           // 真正删除的结点其实是currNode下一个结点, 因此用currNode保存下一个结点的数据域  
  517.     }  
  518.     else                                            // 否则待删除结点是最后一个结点  
  519.     {  
  520.         // 直接将最后一个结点删除即可, 应该把其前一个结点的指针域赋值为空  
  521.         delNode = currNode;  
  522.         // 下面应该将currnNode的前一个结点的指针域赋值为空[时间复杂度O(n)]  
  523.         LinkListNode *prevNode = FindPrevNode(list, currNode);  
  524.         prevNode->m_next = NULL;  
  525.   
  526.     }  
  527.     free(delNode);  
  528.   
  529.     return delElem;  
  530. }  
  531.   
  532. ///*////////////////////////////////////////////////////////////////////////////  
  533. ///  
  534. /// 其他函数  
  535. ///  
  536. /// 显示单链表的信息  
  537. /// void ShowList(LinkList *list  
  538. ///  
  539. /// 删除链表list中prevNode结点之后的指针个指针  
  540. /// void SetNode(LinkList *list, int position, ElemType data)  
  541. ///  
  542. /// 获取单链表list第position个结点的数据域  
  543. /// ElemType GetNode(LinkList *list, int position)  
  544. ///  
  545. /// 获取单链表list的长度[即元素个数]  
  546. /// int LengthLinkList(LinkList *list)  
  547. ///  
  548. /// 判断当前链表是否是空链表  
  549. /// bool IsEmptyLinkList(LinkList *list)  
  550. ///*////////////////////////////////////////////////////////////////////////////  
  551.   
  552.   
  553. /** 
  554. void ShowLinkList(LinkList *list) 
  555. 参数 
  556.     list    :   指向一个链表指针,此处传入表头地址 
  557. 返回值 
  558.     无 
  559. 功能 
  560.     显示单链表的信息 
  561. */  
  562. void ShowList(LinkList *list)  
  563. {  
  564.     printf("there are %d data in list\n", LengthLinkList(list));  
  565.   
  566.     LinkListNode *pNode = (LinkListNode *)(*list);          // 从头指针开始遍历  
  567.   
  568.     while(pNode != NULL)                                //开始遍历单链表  
  569.     {  
  570.         printf("%d  ", pNode->m_data);  
  571.         pNode = pNode->m_next;  
  572.     }  
  573.     printf("\n");  
  574.   
  575. //  ElemType data;  
  576. //  for(int pos = 0; pos < list->m_length; pos++)  
  577. //  {  
  578. //      data = GetNode(list, pos);  
  579. //      printf("%d  ", data);  
  580. //  }  
  581. //  printf("\n");  
  582. }  
  583.   
  584.   
  585. /** 
  586. void SetNode(LinkList *list, int position, ElemType data) 
  587. 参数 
  588.     list    :   指向一个链表指针,此处传入表头地址 
  589.     positon :   待修改的结点的数据 
  590.     data    :   待更正的新数据域 
  591. 返回值 
  592.     无 
  593. 功能 
  594.     修改单链表list第position个结点的数据域为data 
  595. */  
  596. void SetNode(LinkList *list, int position, ElemType data)  
  597. {  
  598.     LinkListNode *pNode = FindPosNode(list, position);      // 找到单链表的第position个结点  
  599.   
  600.     pNode->m_data = data;  
  601. }  
  602.   
  603. /** 
  604. ElemType GetNode(LinkList *list, int position 
  605. 参数 
  606.     list    :   指向一个链表指针,此处传入表头地址 
  607.     positon :   待查询的结点的位置 
  608. 返回值 
  609.     获取到的结点数据 
  610. 功能 
  611.     获取单链表list第position个结点的数据域 
  612. */  
  613. ElemType GetNode(LinkList *list, int position)  
  614. {  
  615.     LinkListNode *pNode = FindPosNode(list, position);      // 找到单链表的第position个结点  
  616.   
  617.     return pNode->m_data;  
  618. }  
  619.   
  620. /** 
  621. int LengthLinkList(LinkList *list) 
  622. 参数 
  623.     list    :   指向一个链表指针,此处传入表头地址 
  624. 返回值 
  625.     单链表的长度 
  626. 功能 
  627.     获取单链表的长度 
  628. */  
  629. int LengthLinkList(LinkList *list)  
  630. {  
  631.     assert(list != NULL);  
  632.   
  633.     int length = 0;  
  634.     LinkListNode *pNode = (LinkListNode *)(*list);  
  635.   
  636.     while(pNode != NULL)  
  637.     {  
  638.         pNode = pNode->m_next;  
  639.         length++;  
  640.     }  
  641.     return length;  
  642. }  
  643.   
  644.   
  645.   
  646. /** 
  647. bool IsEmptyLinkList(LinkList *list) 
  648. 参数 
  649.     list    :   指向一个链表指针,此处传入表头地址 
  650. 返回值 
  651.     如果单链表是空表,返回true 
  652.     否则返回false 
  653. 功能 
  654.     获取单链表的长度 
  655. */  
  656. bool IsEmptyLinkList(LinkList *list)  
  657. {  
  658.     return (list == NULL);  
  659.     // return (list->m_head == NULL);  
  660. }  
  661.   
  662.   
  663. #define LIST_SIZE 7  
  664. // MAIN  
  665. int main(void)  
  666. {  
  667.     int pos;  
  668.   
  669.     printf("TEST 1...\n");  
  670. //  LinkList *plist = NULL;             // ERROR创建单链表  
  671.   
  672.   
  673.     printf("\n\nTEST 2...\n");  
  674.     LinkList list = NULL;  
  675.     InitLinkList(&list);                                // 初始化单链表  
  676.     for(int pos = 0; pos < LIST_SIZE; pos++)         // 训话向单链表中插入数据  
  677.     {  
  678.         InsertNode(&list, 0, pos + 1);  
  679.     }  
  680.     ShowList(&list);                                    // 显示单链表  
  681.     ClearLinkList(&list);                               // 清空单链表  
  682.     FinitLinkList(&list);       // ERROR== list->m_head->m_next == NULL  
  683.     ShowList(&list);  
  684.   
  685.     return  EXIT_SUCCESS;  
  686. }  


转载:http://blog.csdn.net/gatieme/article/details/42611645

目录
相关文章
|
1月前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
1月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
1月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
154 6
|
1月前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
106 5
|
1月前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
1月前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表,常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈,顺序栈使用数组存储,链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛,如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成,链栈则基于单链表的头插法实现。
183 3
|
1月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
1月前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
1月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。