Chinaunix首页 | 论坛 | 博客
  • 博客访问: 185399
  • 博文数量: 89
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 828
  • 用 户 组: 普通用户
  • 注册时间: 2013-10-08 10:44
文章分类
文章存档

2014年(9)

2013年(80)

我的朋友

分类: C/C++

2013-11-11 15:19:37

链表在C语言项目中很常见,学号链表,先从单链表开始,通常在学习阶段的单链表实现是基于某种数据类型或结构量身定做的操作方法,这种方法,没有通用性,在实际项目开发中,段不可取。于是乎,学习一种“浮云”般对单链表的操作是非常重要的。我们研究各个数据结点的数据,就会发现,无论它是什么类型,都有一个共同的特点,就是,他们都是存储在内存中的,它们拥有各子唯一的内存地址,于是乎,我们使用单链表的每个结点存储目标数据的地址,就可以抽象出一种通用的单链表操作方法,具体的操作方法,如下,此代码支持任何数据类型的单链表操作:

/**********************************************************************************************/

file : LinkList.h


  1.   
  1. #ifndef _LINKLIST_H_  
  2. #define _LINKLIST_H_  
  3.   
  4. typedef void LinkList;  
  5. typedef void LinkListNode;  
  6.   
  7. extern LinkList* LinkList_Create();  
  8.   
  9. extern void LinkList_Destroy(LinkList* list);  
  10.   
  11. extern void LinkList_Clear(LinkList* list);  
  12.   
  13. extern int LinkList_Length(LinkList* list);  
  14.   
  15. extern int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);  
  16.   
  17. extern LinkListNode* LinkList_Get(LinkList* list, int pos);  
  18.   
  19. extern LinkListNode* LinkList_Delete(LinkList* list, int pos);  
  20.   
  21. extern void LinkList_Reverse(LinkList* list);  
  22.   
  23. #endif  




/*******************************************************************************************************/

file : LinkList.c


  1. #include   
  2. #include   
  3. #include "LinkList.h"  
  4.   
  5.   
  6. typedef struct _tag_TLinkListNode TLinkListNode;  
  7. struct _tag_TLinkListNode  
  8. {  
  9.     unsigned int addr;  
  10.     TLinkListNode* next;  
  11. };  
  12.   
  13.   
  14. typedef struct _tag_TLinkList  
  15. {  
  16.     int length;  
  17.     TLinkListNode* header;  
  18. }TLinkList;  
  19.   
  20.   
  21. LinkList* LinkList_Create()  
  22. {  
  23.     TLinkList* ret = (TLinkList*)malloc(sizeof(TLinkList));  
  24.       
  25.     if(ret != NULL)  
  26.     {  
  27.         ret->length = 0;  
  28.         ret->header = NULL;  
  29.     }  
  30.       
  31.     return (LinkList*)ret;  
  32. }  
  33.   
  34.   
  35. void LinkList_Destroy(LinkList* list)  
  36. {  
  37.     LinkList_Clear(list);  
  38.     free(list);  
  39.     list = NULL;  
  40. }  
  41.   
  42.   
  43. void LinkList_Clear(LinkList* list)  
  44. {  
  45.     TLinkList* sList = (TLinkList*)list;  
  46.       
  47.     if(sList != NULL)  
  48.     {  
  49.         while(sList->header != NULL)  
  50.         {  
  51.             TLinkListNode* pList = sList->header;  
  52.             sList->header = pList->next;  
  53.             free(pList);  
  54.             sList->length--;  
  55.         }  
  56.     }  
  57. }  
  58.   
  59.   
  60. /************************************************************************ 
  61. * 获取单链表长度 
  62. * 返回-1表示获取失败 
  63. * 返回非负数既是单链表当前长度 
  64. ************************************************************************/  
  65. int LinkList_Length(LinkList* list)  
  66. {  
  67.     int ret = -1;  
  68.     TLinkList* sList = (TLinkList*)list;  
  69.       
  70.     if(sList != NULL)  
  71.     {  
  72.         ret = sList->length;  
  73.     }  
  74.       
  75.     return ret;  
  76. }  
  77.   
  78.   
  79. /************************************************************************ 
  80. * 插入结点 
  81. * 插入 成功返回真 
  82. * 插入失败返回假  
  83. ************************************************************************/  
  84. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)  
  85. {  
  86.     int i = 0;  
  87.     TLinkList* sList = (TLinkList*)list;  
  88.     int ret = (sList != NULL) && (pos >= 0) && (node != NULL);  
  89.       
  90.     if(ret)  
  91.     {  
  92.         TLinkListNode* pNew = (TLinkListNode*)malloc(sizeof(TLinkListNode));  
  93.         if(pNew != NULL)  
  94.         {  
  95.             pNew->addr = (unsigned int)node;  
  96.   
  97.   
  98.             if(pos == 0 || sList->header == NULL)  
  99.             {  
  100.                 pNew->next = sList->header;  
  101.                 sList->header = pNew;  
  102.             }  
  103.             else  
  104.             {  
  105.                 TLinkListNode* current = sList->header;  
  106.           
  107.                 for(i = 1; (i < pos) && (current->next != NULL); i++)  
  108.                 {  
  109.                     current = current->next;  
  110.                 }  
  111.           
  112.                 pNew->next = current->next;  
  113.                 current->next = pNew;  
  114.             }  
  115.             sList->length++;  
  116.         }  
  117.         else  
  118.         {  
  119.             ret = 0;  
  120.         }  
  121.     }  
  122.       
  123.     return ret;  
  124. }  
  125.   
  126. /************************************************************************ 
  127. * 获取pos位置的结点 
  128. * 成功返回结点指针 
  129. * 失败返回空  
  130. ************************************************************************/  
  131. LinkListNode* LinkList_Get(LinkList* list, int pos)  
  132. {  
  133.     int i = 0;  
  134.     TLinkList* sList = (TLinkList*)list;  
  135.     LinkListNode* ret = NULL;  
  136.       
  137.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )  
  138.     {  
  139.         if(0 == pos)  
  140.         {  
  141.             ret = (LinkListNode*)(sList->header->addr);  
  142.         }  
  143.         else  
  144.         {  
  145.             TLinkListNode* current = sList->header;  
  146.             for(i=1; i
  147.             {  
  148.                 current = current->next;  
  149.             }  
  150.             ret = (LinkListNode*)(current->next->addr);  
  151.         }  
  152.     }  
  153.       
  154.     return ret;  
  155. }  
  156.   
  157. /************************************************************************ 
  158. * 删除pos位置的结点,并将删除的结点指针返回 
  159. * 成功返回结点指针 
  160. * 失败返回空  
  161. ************************************************************************/  
  162. LinkListNode* LinkList_Delete(LinkList* list, int pos)  
  163. {  
  164.     TLinkList* sList = (TLinkList*)list;  
  165.     LinkListNode* ret = NULL;  
  166.     int i = 0;  
  167.       
  168.     if( (sList != NULL) && (0 <= pos) && (pos < sList->length) )  
  169.     {  
  170.         TLinkListNode* current = sList->header;  
  171.         if(0 == pos)  
  172.         {  
  173.             ret = (LinkListNode*)(sList->header->addr);  
  174.             sList->header = current->next;  
  175.             free(current);  
  176.         }  
  177.         else  
  178.         {  
  179.             for(i=0; i
  180.             {  
  181.                 current = current->next;  
  182.             }  
  183.             ret = (LinkListNode*)(current->next->addr);  
  184.             current->next = current->next->next;  
  185.             free(current->next);  
  186.         }  
  187.           
  188.         sList->length--;  
  189.     }  
  190.       
  191.     return ret;  
  192. }  
  193.   
  194. /************************************************************************ 
  195. * 两种单链表逆序的操作 
  196. * 无返回值 
  197. ************************************************************************/  
  198. #if 1  
  199. /************************************************************************  
  200. // 修改结点指针  
  201. void LinkList_Reverse(LinkList* list)  
  202. {  
  203.     TLinkList* sList = (TLinkList*)list;  
  204.     TLinkListNode* p1 = sList->header;  
  205.   
  206.   
  207.     if(LinkList_Length(list) == 2)  
  208.     {  
  209.         sList->header = p1->next;  
  210.         sList->header->next = p1;  
  211.         p1->next = NULL;  
  212.     }  
  213.     else if(LinkList_Length(list) > 2)  
  214.     {  
  215.         TLinkListNode* p2 = p1->next;  
  216.         sList->header = p2->next;  
  217.         p1->next = NULL;  
  218.   
  219.   
  220.         while(sList->header != NULL)  
  221.         {  
  222.             p2->next = p1;  
  223.             p1 = p2;  
  224.             p2 = sList->header;  
  225.             sList->header = sList->header->next;  
  226.         }  
  227.         sList->header = p2;  
  228.         p2->next = p1;  
  229.     }  
  230. }  
  231. #else  
  232. // 利用单链表删除、插入操作,将原有单链表第0个数据结点取出来,存入临时单链表中的第0个数据  
  1. // 结点位置,直到原有单链表为空,再将临时单链表还给原有链表指针  
  2. void LinkList_Reverse(LinkList* list)  
  3. {  
  4.     if(LinkList_Length(list) >= 2)  
  5.     {  
  6.         TLinkList* sList = (TLinkList*)list;  
  7.         LinkList* swapList = LinkList_Create();  
  8.         while(sList->header != NULL)  
  9.         {  
  10.             LinkList_Insert(swapList, LinkList_Delete(list, 0), 0);  
  11.         }  
  12.   
  13.   
  14.         sList->header = ((TLinkList*)swapList)->header;  
  15.         sList->length = ((TLinkList*)swapList)->length;  
  16.         ((TLinkList*)swapList)->header = NULL;  
  17.         ((TLinkList*)swapList)->length = 0;  
  18.         LinkList_Destroy(swapList);  
  19.     }  
  20. }  
  21. #endif  
阅读(457) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~