003-线性表的链式存储

moc

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

2018-9-23 17:00 上传

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