AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

数据结构模版----单链表SimpleLinkList[带头结点&&面向对象设计思想](C语言实现)

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

链表中的数据是以节点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表）

单链表是链式存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。

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


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

文章标签：
存储
C语言
关键词：
C语言数据结构
数据结构c语言
数据结构单链表
C语言单链表
数据结构结点
shy丶gril
目录
相关文章
土木林森
|
26天前
|
算法 数据处理 C语言
C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧，涵盖基本概念、应用场景、实用技巧及示例代码，并讨论了位运算的性能优势及其与其他数据结构和算法的结合，旨在帮助读者掌握这一高效的数据处理方法。
土木林森
38 1
XIAZHI
|
1月前
|
存储 算法 搜索推荐
【趣学C语言和数据结构100例】91-95
本文涵盖多个经典算法问题的C语言实现，包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题，读者可以深入了解排序算法、数据处理方法和图论基础知识，提升编程能力和算法理解。
XIAZHI
46 4
XIAZHI
|
1月前
|
存储 机器学习/深度学习 搜索推荐
【趣学C语言和数据结构100例】86-90
本文介绍并用C语言实现了五种经典排序算法：直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景，如直接插入排序适合小规模或基本有序的数据，快速排序则适用于大规模数据集，具有较高的效率。通过学习这些算法，读者可以加深对数据结构和算法设计的理解，提升解决实际问题的能力。
XIAZHI
43 4
XIAZHI
|
1月前
|
存储 算法 数据处理
【趣学C语言和数据结构100例】81-85
本文介绍了五个经典算法问题及其C语言实现，涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大，且在实际应用中极为广泛，有助于提升编程能力和数据结构理解。
XIAZHI
41 4
XIAZHI
|
1月前
|
算法 数据可视化 数据建模
【趣学C语言和数据结构100例】76-80
本文介绍了五种图论算法的C语言实现，涵盖二叉树的层次遍历及广度优先搜索（BFS）和深度优先搜索（DFS）的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点；BFS利用队列从源节点逐层遍历图节点，适用于最短路径等问题；DFS通过递归或栈深入图的分支，适合拓扑排序等场景。这些算法是数据结构和算法学习的基础，对提升编程能力和解决实际问题至关重要。
XIAZHI
51 4
XIAZHI
|
1月前
|
存储 算法 vr&ar
【趣学C语言和数据结构100例】71-75
本文介绍了五个C语言数据结构问题及其实现，涵盖链表与二叉树操作，包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法，解决了理论与实际应用中的常见问题，有助于提升编程能力和数据结构理解。
XIAZHI
39 4
XIAZHI
|
1月前
|
存储 算法 C语言
【趣学C语言和数据结构100例】66-70
本书《趣学C语言和数据结构100例》精选了5个典型的数据结构问题及C语言实现，涵盖链表与数组操作，如有序集合的集合运算、有序序列表的合并、数组中两顺序表位置互换、三递增序列公共元素查找及奇偶数重排。通过详细解析与代码示例，帮助读者深入理解数据结构与算法设计的核心思想，提升编程技能。
XIAZHI
34 4
龙大吉
|
27天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
53 5
土木林森
|
26天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略，涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面，旨在通过综合策略提升程序性能，满足实际需求。
土木林森
57 1
XIAZHI
|
1月前
|
存储 机器学习/深度学习 算法
【趣学C语言和数据结构100例】61-65
本文介绍了五个关于C语言和数据结构的经典问题及其实现方法，涵盖查找链表共同后缀、删除重复节点、重新排列链表元素、合并有序链表以及特定条件下的链表排序。每个问题通过具体的算法设计，不仅展示了链表操作的灵活性，还强调了效率优化的重要性。通过这些问题的探讨，读者可以深入理解链表的基本操作和高级应用，提升解决实际问题的能力。
XIAZHI
49 4