开发者社区> shy丶gril> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介:
+关注继续查看

前面写的单链表结构体是重新设计的。包含头结点(或者头指针)以及链表长度的结构体,而我们通常实现的链表是直接把单链表结点结构体作为单链表来使用的,下面我们给出z这种实现方式,让我们一起来细细体会他们实现之间的区别

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


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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【C语言数据结构1】--数据结构和算法
如果没有接触过数据结构这门课程,或者说只是单单听过这个名词。那么在含义方面,数据结构对于我们来说是非常陌生的。在了解一门课程之前,我们总是要知道这门课程要学习什么。
12 0
C语言数据结构(9)--串的朴素模式匹配算法
本文目录 1. 模式匹配概念 2. 朴素的模式匹配算法 3. 朴素模式匹配代码实现
71 0
《C语言及程序设计》实践参考——循环的嵌套流程图
返回:贺老师课程教学链接  项目要求 循环的嵌套流程图(1)求s=1!+2!+……10!,即求1到10的阶乘和[参考解答] 或者:  (2)求s=1+2^2+3^3+4^4+5^5+6^6,要求n^n不能用求幂的运算直接计算(n^n表示n的n次方)[参考解答]
1268 0
《C语言及程序设计》实践参考——次数不定的循环的流程图
返回:贺老师课程教学链接  项目要求 次数不定的循环的流程图(1)用如下公式求  的近似值(计算直到最后一项的绝对值小于0.00001)  [参考解答] (2)Fibonacci数列在计算科学、经济学等领域中广泛使用,其特点是:第一、二个数是1,从第3个数开始,每个数是其前两个数之和。据此,这个数列为:1 1 2 3 5 8 13 21 34 55 89 ……,请设计流程图,输出这个数列,
1386 0
《C语言及程序设计》实践参考——简单循环的流程图
返回:贺老师课程教学链接  项目要求 简单循环的流程图(提示:m是一个变量,在程序中输入)(1)求1到m的倒数和,即  [参考解答] (2)求1到m的平方和[参考解答] (3)求1到m间所有奇数的和[参考解答] (4)求值:  [参考解答] (5)求m!,即  [参考解答]
1590 0
《C语言及程序设计》实践项目——循环控制结构流程图
返回:贺老师课程教学链接  画出实现下面求解任务的流程图 1、简单循环的流程图(提示:m是一个变量,在程序中输入)(1)求1到m的倒数和,即  (2)求1到m的平方和(3)求1到m间所有奇数的和(4)求值:  (5)求m!,即  [参考解答]2、次数不定的循环的流程图(1)用如下公式求  的近似值(计算直到最后一项的绝对值小于0.00001)  (2)Fibonacci数列在计算科学、经济学等
1037 0
《C语言及程序设计》实践项目——程序的单步执行
返回:贺老师课程教学链接  【调试程序:油量监控】  设计一个程序,用于赛车油量的监控。该程序在赛车油量偏低(少于1/4,即0.25)时,警示车手应该注意;在油箱接近满载(不低于3/4)时,提示提手不要停车。而对于其他情况下,不提示任何信息,以免车手分心。  请设计出这个程序来,输入油量刻度(0-1之内的数,如0.21),提示相应信息,如果需要的话。  提示:下面显示了几种情况,注意对程序的完
944 0
C语言及程序设计提高例程-7 返回指针的函数
贺老师教学链接  C语言及程序设计提高 本课讲解 返回指针的函数 #include <stdio.h> int *max(int *x, int *y) { int *t; if(*x > *y) t = x; else t = y; return t; } int main() { int a, b
829 0
+关注
文章
问答
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载