开发文章

线性表的链式存储

1. 基本概念

  • 链式存储定义
    为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。

链式存储定义.png

链式存储定义.png

  • 表头结点
    链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息

  • 数据结点
    链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息
  • 尾结点
    链表中的最后一个数据结点,其下一元素指针为空,表示无后继。

2.设计与实现

  • 在C语言中可以用结构体来定义链表中的指针域–数据节点/业务节点
  • 链表中的表头结点也可以用结构体实现–表头结点

结构体实现.png

插入操作

插入操作.png

  • 获取

带头结点、位置从0的单链表返回链表中第3个位置处元素的值

复制内容到剪贴板
  1. LinkListNode* LinkList_Get(LinkList* list, int pos)  
  2. {   
  3.     int  i = 0;  
  4.     TLinkList *tList = (TLinkList *)list;  
  5.     LinkListNode *current = NULL;  
  6.     LinkListNode *ret = NULL;  
  7.   
  8.     if (list==NULL ||pos<0 || pos>=tList->length)  
  9.     {  
  10.         return NULL;  
  11.     }  
  12.     current = (LinkListNode *)tList;  
  13.     for (i=0; i<pos; i++)  
  14.     {  
  15.         current = current->next;  
  16.     }  
  17.     ret = current->next;  
  18.     return ret ;  
  19. }  

—返回第三个位置的

移动pos次以后,当前指针指向哪里?

答案:指向位置2,所以需要返回 ret = current->next;

备注:

循环遍历时, 遍历第1次,指向位置0
遍历第2次,指向位置1
遍历第3次,指向位置2
遍历第n次,指向位置n-1;
所以如果想返回位置n的元素的值,需要怎么做
ret = current->next;
此问题是:指向头结点的指针移动n次指向第n-1个元素。

删除

删除.png

3.实现代码

  • 头文件
复制内容到剪贴板
  1. #ifndef _MYLINKLIST_H_  
  2. #define _MYLINKLIST_H_  
  3.   
  4. #include <stdlib.h>  
  5. #include <stdio.h>  
  6. #include <memory.h>  
  7.   
  8.   
  9. typedef void LinkList;//数据类型的封装  
  10.   
  11. /*线性表(链表)节点的数据结构--只含指向自身类型的指针(域)*/  
  12. typedef struct _tag_LinkListNode  
  13. {  
  14.     struct _tag_LinkListNode* next;  
  15. }LinkListNode;  
  16.   
  17. LinkList* LinkList_Create();  
  18.   
  19. void LinkList_Destroy(LinkList* list);  
  20.   
  21. void LinkList_Clear(LinkList* list);  
  22.   
  23. int LinkList_Length(LinkList* list);  
  24.   
  25. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);  
  26.   
  27. LinkListNode* LinkList_Get(LinkList* list, int pos);  
  28.   
  29. LinkListNode* LinkList_Delete(LinkList* list, int pos);  
  30.   
  31. #endif  

实现文件

复制内容到剪贴板
  1. #include "TLinkList.h"  
  2.   
  3. /*线性表链式存储的表头数据结构*/  
  4. typedef struct _tag_LinkList  
  5. {  
  6.     LinkListNode  head;//表头节点(里面的指针域指向链表第一个节点)  
  7.     int length;//节点个数  
  8. }TLinkList;//链表的抽象数据类型  
  9.   
  10.   
  11. /*链表创建*/  
  12. LinkList* LinkList_Create()  
  13. {  
  14.     TLinkList * tmp = NULL;  
  15.     tmp = (TLinkList*)malloc(sizeof(TLinkList));//为表头分配内存  
  16.     if (NULL == tmp)//检查分配结果  
  17.     {  
  18.         printf("malloc error!\n");  
  19.         return NULL;  
  20.     }  
  21.     /*表头数据成员初始化*/  
  22.     memset(tmp, 0, sizeof(TLinkList));  
  23.   
  24.     /*返回表头地址*/  
  25.     return tmp;  
  26. }  
  27.   
  28. /*链表销毁*/  
  29. void LinkList_Destroy(LinkList* list)  
  30. {  
  31.     if (list != NULL)//合法性检测  
  32.     {  
  33.         free(list);//释放内存  
  34.         list = NULL;//避免野指针  
  35.     }  
  36.     else  
  37.     {  
  38.         printf("list is error!\n");  
  39.     }  
  40.     return ;  
  41. }  
  42.   
  43. /*清空链表*/  
  44. void LinkList_Clear(LinkList* list)  
  45. {  
  46.     TLinkList * tmp = NULL;  
  47.     if (list == NULL)  
  48.     {  
  49.         printf("list is error!\n");  
  50.         return;  
  51.     }  
  52.     tmp = (TLinkList*)list;  
  53.   
  54.     /*将长度置零*/  
  55.     tmp->length = 0;  
  56.   
  57.     /*将指向第一个节点的指针置零*/  
  58.     tmp->head.next= NULL;  
  59.     return ;  
  60. }  
  61.   
  62. /*获取链表中节点个数*/  
  63. int LinkList_Length(LinkList* list)  
  64. {  
  65.   
  66.     TLinkList * tmp = NULL;  
  67.     if (list == NULL)  
  68.     {  
  69.         printf("list is error!\n");  
  70.         return -1;  
  71.     }  
  72.     tmp = (TLinkList*)list;  
  73.     return tmp->length;  
  74. }  
  75.   
  76.   
  77. /*插入节点*/  
  78. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)  
  79. {  
  80.     TLinkList * tmp = NULL;//指向链表表头  
  81.     LinkListNode * current = NULL;//辅助指针变量  
  82.     int i = 0;//循环用变量  
  83.   
  84.     /*合法性检测*/  
  85.     if (list == NULL || node == NULL || pos < 0)  
  86.     {  
  87.         printf("argv is error!\n");  
  88.         return -2;  
  89.     }  
  90.     tmp = (TLinkList*)list;  
  91.   
  92.     /*容错纠正*/  
  93.     if (pos >= tmp->length)  
  94.     {  
  95.         pos = tmp->length;  
  96.     }  
  97.   
  98.     /*将辅助指针变量指向表头节点*/  
  99.     current = &(tmp->head);  
  100.   
  101.     /*辅助指针变量往后跳到指向要插入位置的前一个节点*/  
  102.     for (i = 0; i < pos && current->next != NULL; i++)  
  103.     {  
  104.         current = current->next;  
  105.     }  
  106.   
  107.     /*新节点的指针域指向后一个节点*/  
  108.     node->next = current->next;  
  109.   
  110.     /*前一个节点的指针域指向新节点*/  
  111.     current->next = node;  
  112.   
  113.     /*修改长度*/  
  114.     tmp->length++;  
  115.     return 0;  
  116. }  
  117.   
  118.   
  119. /*获取指定位置的元素*/  
  120. LinkListNode* LinkList_Get(LinkList* list, int pos)  
  121. {  
  122.     TLinkList * tmp = NULL;  
  123.     LinkListNode * current = NULL;  
  124.     int i = 0;  
  125.     if (list == NULL ||  pos < 0)  
  126.     {  
  127.         printf("argv is error!\n");  
  128.         return NULL;  
  129.     }  
  130.     tmp = (TLinkList*)list;  
  131.   
  132.     if (pos >= tmp->length)  
  133.     {  
  134.         pos = tmp->length;  
  135.     }  
  136.     current = &(tmp->head);  
  137.     for (i = 0; i < pos && current->next != NULL; i++)  
  138.     {  
  139.         current = current->next;  
  140.     }  
  141.   
  142.     /*返回相应位置的业务节点的地址*/  
  143.     return current->next;  
  144. }  
  145.   
  146. /*删除指定位置的节点*/  
  147. LinkListNode* LinkList_Delete(LinkList* list, int pos)  
  148. {  
  149.     TLinkList * tmp = NULL;  
  150.     LinkListNode * current = NULL;  
  151.     LinkListNode * del_res = NULL;//第二个辅助指针变量,用于保存要删除的节点  
  152.   
  153.     int i = 0;  
  154.   
  155.     /*合法性检测*/  
  156.     if (list == NULL || pos < 0)  
  157.     {  
  158.         printf("argv is error!\n");  
  159.         return NULL;  
  160.     }  
  161.     tmp = (TLinkList*)list;  
  162.   
  163.     /*容错性纠正*/  
  164.     if (pos >= tmp->length)  
  165.     {  
  166.         pos = tmp->length;  
  167.     }  
  168.   
  169.     /*辅助指针变量指向表头结点*/  
  170.     current = &(tmp->head);  
  171.   
  172.     /*辅助指针变量往后跳到指定位置的前一个位置*/  
  173.     for (i = 0; i < pos && current->next != NULL; i++)  
  174.     {  
  175.         current = current->next;  
  176.     }  
  177.   
  178.     /*保存要删除的节点以便上层应用回收内存*/  
  179.     del_res = current->next;  
  180.   
  181.     /*将前一个位置的指针域指向指定位置的后一个节点*/  
  182.     current->next = del_res->next;  
  183.   
  184.     /*修改长度*/  
  185.     tmp->length--;  
  186.   
  187.     /*返回被删除的节点的地址*/  
  188.     return del_res;  
  189. }  

测试文件

复制内容到剪贴板
  1. #include "TLinkList.h"  
  2.   
  3.   
  4. typedef struct Teacher  
  5. {  
  6.     LinkListNode node;  
  7.     char name[64];  
  8.     int age;  
  9. }Teacher;  
  10.   
  11. int main()  
  12. {  
  13.     Teacher     t1, t2, t3;  
  14.     int         length, i = 0;  
  15.   
  16.     LinkList        *list = NULL;  
  17.     t1.age = 31;  
  18.     t2.age = 32;  
  19.     t3.age = 33;  
  20.   
  21.   
  22.     list = LinkList_Create();  
  23.   
  24.     length = LinkList_Length(list);  
  25.   
  26.     //业务节点是teacher和算法分类的。。。。思想  
  27.     LinkList_Insert(list, (LinkListNode *)&t1, LinkList_Length(list));  
  28.     LinkList_Insert(list, (LinkListNode *)&t2, LinkList_Length(list));  
  29.     LinkList_Insert(list, (LinkListNode *)&t3, LinkList_Length(list));  
  30.   
  31.     //遍历链表   
  32.     for (i = 0; i<LinkList_Length(list); i++)  
  33.     {  
  34.         Teacher *tmp = (Teacher *)LinkList_Get(list, i);  
  35.         if (tmp != NULL)  
  36.         {  
  37.             printf("age:%d ", tmp->age);  
  38.         }  
  39.     }  
  40.   
  41.     while (LinkList_Length(list) > 0)  
  42.     {  
  43.         Teacher *tmp = (Teacher *)LinkList_Delete(list, 0);  
  44.         if (tmp != NULL)  
  45.         {  
  46.             printf("age:%d ", tmp->age);  
  47.         }  
  48.     }  
  49.     LinkList_Destroy(list);  
  50.     system("pause");  
  51.     return 0;  
  52. }  

4.优缺点


  • 优点:
  • 无需一次性定制链表的容量
  • 插入和删除操作无需移动数据元素


  • 缺点:
  • 数据元素必须保存后继元素的位置信息
  • 获取指定数据的元素操作需要顺序访问之前的元素

感谢 lzjsqn 支持 磐实编程网 原文地址:
blog.csdn.net/lzjsqn/article/details/52971948

上一篇:谈谈AVL树

下一篇:AES算法实现分析

文章信息

发布时间:2016-10-31

作者:lzjsqn

发布者:aquwcw

浏览次数: