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

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

简介:
+关注继续查看

上一篇写单链表是带头结点的,但是其他这种写法的单链表中,头结点其实就不是那么必要了,因为我们的单链表结构体中增加了一项m_length

下面的不加头结点的单链表奉上

不带头结点的单链表结构体


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


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

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

相关文章
C语言简单实现14个例题(谭浩强第四版)
版权声明:转载请注明出处:http://blog.csdn.net/dajitui2024 https://blog.csdn.net/dajitui2024/article/details/79396241 1、仅供学习交流参考。
1037 0
《C语言程序设计与实践(第2版)》——2.7 函数
C语言的程序是由一个个函数构成的,除了有且必须有的main主函数以外,用户也可以自己定义函数。此外,C语言的编译系统还提供了一些库函数。函数为程序的封装提供了一种简便的方法,在其他地方使用函数时不需要考虑它是如何实现的。
976 0
《C语言及程序设计》实践参考——链表的合并
返回:贺老师课程教学链接 【项目1-链表的合并】 输入一个整数m,表示A链表的长度,再输入m个数作为A链表中的m个数据元素,建立链表A,其头指针为heada。输入一个整数n,表示B链表的长度,再输入n个数表示B链表中的n个数据元素,建立链表B,其头指针为headb。输入i、len、j,将要从单链表A中删除自第i个元素起的共len个元素,然后将单链表A插入到单链表B的第j个
1024 0
《C语言及程序设计》实践参考——链表版通信录
返回:贺老师课程教学链接 【项目4-链表版通信录】 利用链表存储数据,写一个通信录程序,能够记录多个联系人的编号、姓名、性别、联系电话、地址,完成数据的录入、添加、删除、修改以及查询功能。 [参考解答] 本解答自网络:链接 #include<stdio.h> #include<string.h> #include<stdlib.h>
1068 0
《C语言及程序设计》实践参考——改造链表
返回:贺老师课程教学链接 【项目3 - 改造链表】 下面是一个建立动态链表的程序。阅读程序,然后按要求改造程序。 #include <iostream> using namespace std; #include <stdio.h> #include <malloc.h> #define N 5 typedef struct
871 0
《C语言及程序设计》实践参考——字符串处理函数
返回:贺老师课程教学链接  实践要求 【项目4-字符串处理函数】指针是神奇的,指向整型的指针int *p1,可以操作整型数组int a[];指向字符型的指针char *p2,可以操作字符数组(字符串)char str[];更灵活的是,在函数的传递中,指针、数组名在一定程度上可以互换。请编制函数,对字符串的进行各种操作。 序 功能 用数组名作形参 用指针作形参 1 字符串str1和str
1309 0
《C语言及程序设计》实践参考——歌手大奖赛计分函数版
返回:贺老师课程教学链接  项目要求 【项目2-歌手大奖赛计分函数版】(1)在歌手大奖赛中,有n位评委为参赛的选手打分,分数为0~10分(运行时由人输入)。选手最后得分为:去掉一个最高分和一个最低分后其余分数的平均值。请编写一个程序,完成相关的功能。 要求利用一个函数void calScore(int n),对一位选手成绩的输入成绩、计算和显示实现,其中n为评委人数。这样,在main函数
1114 0
《C语言及程序设计》实践参考——大奖赛计分(续一)
返回:贺老师课程教学链接  项目要求 【项目1:大奖赛计分(续一)】在歌手大奖赛中,有10个评委为参赛的选手打分,分数为1~10分。请在大奖赛计分程序基础上,增加功能,若用户输入不在0-10范围内,则立即要求重输,直到正确。 [参考解答] #include <stdio.h> #define n 10 int main( ) { int i; double av
971 0
《C语言及程序设计》实践参考——大奖赛计分
返回:贺老师课程教学链接  项目要求 【项目4:大奖赛计分】  (1)基本要求:在歌手大奖赛中,有10个评委为参赛的选手打分,分数为1~10分。选手最后得分为:去掉一个最高分和一个最低分后其余8个分数的平均值。请编写一个程序实现。 #include <stdio.h> #define n 10 int main( ) { int i=1; double ave
1065 0
《C语言及程序设计》实践参考——Bessel函数
返回:贺老师课程教学链接  项目要求 【项目3:Bessel函数】Bessel函数Jn(X)有以下的递推关系: 编写程序,利用递推关系,由任意的n和x≠0求Jn(X)。 [参考解答] #include <stdio.h> #include <math.h> int main( ) { double jn, j0, j1, x; int n, i;
981 0
+关注
文章
问答
文章排行榜
最热
最新
相关课程
更多
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载