数据结构模版----单链表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

目录
相关文章
|
7天前
|
存储 Java
java数据结构,线性表链式存储(单链表)的实现
文章讲解了单链表的基本概念和Java实现,包括头指针、尾节点和节点结构。提供了实现代码,包括数据结构、接口定义和具体实现类。通过测试代码演示了单链表的基本操作,如添加、删除、更新和查找元素,并总结了操作的时间复杂度。
java数据结构,线性表链式存储(单链表)的实现
|
22天前
|
存储 人工智能 C语言
数据结构基础详解(C语言): 栈的括号匹配(实战)与栈的表达式求值&&特殊矩阵的压缩存储
本文首先介绍了栈的应用之一——括号匹配,利用栈的特性实现左右括号的匹配检测。接着详细描述了南京理工大学的一道编程题,要求判断输入字符串中的括号是否正确匹配,并给出了完整的代码示例。此外,还探讨了栈在表达式求值中的应用,包括中缀、后缀和前缀表达式的转换与计算方法。最后,文章介绍了矩阵的压缩存储技术,涵盖对称矩阵、三角矩阵及稀疏矩阵的不同压缩存储策略,提高存储效率。
|
22天前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
24天前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
24天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
24天前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
4天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
4天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题