003-线性表的链式存储

moc

1、基本概念
链式存储结构：为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息以外，还需要存储指示其直接后继元素的信息。
n个结点（ai的存储映像）链结成一个链表，即线性表的链式存储结构，因此链表中每个结点需要包含一个指针域，即单链表。

2、内核链表
相比于传统链表，Linux内核链表实现了链表的算法和具体的业务结点的分离。详细参考：传送门

3、设计与实现
强调：
        ① 指针指向谁就把谁的地址赋给指针；
        ② 分清链表的操作逻辑 和 辅助指针变量之间的关系。
1. 插入元素

        ① 让辅助指针current指向插入元素的位置，辅助指针初始指向头指针，只需向后以插入的位置号即可；
        ② 让node连接后续链表  ==> node->next = current->next;
        ③ 让前面链表 连接新的node结点 ==> current->next = node.

1. int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
   
2. {
   
3.         int ret = 0, i = 0;
   
4.         TLinkList *tList = NULL;
   
5.         LinkListNode *current = NULL;
   
6.         if (list == NULL || node == NULL || pos < 0)
   
7.         {
   
8.                 ret = -1;
   
9.                 printf("Fun LinkList_Insert() paramter error!");
   
10.                 return ret;
    
11.         }
    
12. 
    
13.         tList = (TLinkList*)list;
    
14.         current = &(tList->header);  // 辅助指针指向链表头部
    
15. 
    
16.         for (i = 0; i < pos && (current->next != NULL); i++)
    
17.         {
    
18.                 current = current->next;
    
19.         }
    
20. 
    
21.         // 1 让node连接后续链表
    
22.         node->next = current->next;
    
23.         // 2 让前面链表 连接新的node结点
    
24.         current->next = node;
    
25. 
    
26.         tList->length++;
    
27.         return 0;
    
28. }

复制代码

2. 删除元素

        ① 让辅助指针current指向删除元素的前一个位置，辅助指针初始指向头指针，只需向后以插入的位置号即可；
        ② 缓存被删除的结点位置 ==> ret = current->next;
        ③ 指向后一个结点 ==>current->next = ret->next.

1. LinkListNode* LinkList_Delete(LinkList* list, int pos)
   
2. {
   
3.         int i = 0;
   
4.         TLinkList *tList = NULL;
   
5.         LinkListNode *current, *ret = NULL;
   
6.         if (list == NULL || pos < 0)
   
7.         {
   
8.                 printf("Fun LinkList_Insert() paramter error!");
   
9.                 return NULL;
   
10.         }
    
11. 
    
12.         tList = (TLinkList*)list;
    
13.         current = &(tList->header);
    
14. 
    
15.         for (i = 0; i < pos && (current->next != NULL); i++)
    
16.         {
    
17.                 current = current->next;
    
18.         }
    
19. 
    
20.         // 缓存被删除的结点位置
    
21.         ret = current->next;
    
22. 
    
23.         // 指向后一个结点
    
24.         current->next = ret->next;
    
25. 
    
26.         tList->length--;
    
27.         return ret;
    
28. }

复制代码

4、链式结构的优缺点
优点：
        无需一次性定制链表的容量，可动态增减；
        插入和删除操作无需移动数据元素。
缺点：
        数据元素必须保存后继元素的位置信息；
        获取指定数据元素的操作需要访问之前的元素。
完整代码： 线性表链式存储.zip (2.02 KB, 下载次数: 8)

2018-9-23 17:00 上传

点击文件名下载附件
线性表链式存储