003-线性表的链式存储
1、基本概念链式存储结构：为了表示每个数据元素与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息以外，还需要存储指示其直接后继元素的信息。
n个结点（ai的存储映像）链结成一个链表，即线性表的链式存储结构，因此链表中每个结点需要包含一个指针域，即单链表。
2、内核链表
相比于传统链表，Linux内核链表实现了链表的算法和具体的业务结点的分离。详细参考：传送门
3、设计与实现
强调：
① 指针指向谁就把谁的地址赋给指针；
② 分清链表的操作逻辑 和 辅助指针变量之间的关系。
1. 插入元素
① 让辅助指针current指向插入元素的位置，辅助指针初始指向头指针，只需向后以插入的位置号即可；
② 让node连接后续链表==> node->next = current->next;
③ 让前面链表 连接新的node结点 ==> current->next = node.
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
int ret = 0, i = 0;
TLinkList *tList = NULL;
LinkListNode *current = NULL;
if (list == NULL || node == NULL || pos < 0)
{
ret = -1;
printf("Fun LinkList_Insert() paramter error!");
return ret;
}
tList = (TLinkList*)list;
current = &(tList->header);// 辅助指针指向链表头部
for (i = 0; i < pos && (current->next != NULL); i++)
{
current = current->next;
}
// 1 让node连接后续链表
node->next = current->next;
// 2 让前面链表 连接新的node结点
current->next = node;
tList->length++;
return 0;
}
2. 删除元素
① 让辅助指针current指向删除元素的前一个位置，辅助指针初始指向头指针，只需向后以插入的位置号即可；
② 缓存被删除的结点位置 ==> ret = current->next;
③ 指向后一个结点 ==>current->next = ret->next.
LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
int i = 0;
TLinkList *tList = NULL;
LinkListNode *current, *ret = NULL;
if (list == NULL || pos < 0)
{
printf("Fun LinkList_Insert() paramter error!");
return NULL;
}
tList = (TLinkList*)list;
current = &(tList->header);
for (i = 0; i < pos && (current->next != NULL); i++)
{
current = current->next;
}
// 缓存被删除的结点位置
ret = current->next;
// 指向后一个结点
current->next = ret->next;
tList->length--;
return ret;
}
4、链式结构的优缺点
优点：
无需一次性定制链表的容量，可动态增减；
插入和删除操作无需移动数据元素。
缺点：
数据元素必须保存后继元素的位置信息；
获取指定数据元素的操作需要访问之前的元素。
完整代码：
页:
[1]