线性表的链式存储结构1.1

2020-07-04  本文已影响0人  lotusgrm

这篇文章依然介绍线性表的链式存储结构-单链表

单链表的整表创建

线性表顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和容量确定的数组并赋值的过程。单链表和线性表顺序存储结构不一样，它不像单链表那样内存地址是连续的，元素存储的地址比较分散，可以存储在内存中未被使用的任意位置，它的大小和位置不是预先分配好的，而是根据实际需求即时生成，因此单链表是一个 动态表，创建单链表的过程就是一个动态生成链表的过程，从 空表 的初始状态，依次建立各元素结点，并插入链表
单链表整表创建的过程需要用到我们前面文章中介绍到的 头插法 与 尾插法：
头插法创建单链表
1.声明一个结点 p 和 计数器变量 i
2.初始化一个空链表 L
3.将 L 头结点的指针域指向 NULL，建立一个带有头结点的单链表
4.循环：

// 定义一个链表结构
typedef struct ListNode
{
    int date;              // 链表一个结点的数据域
    struct ListNode *next; // 指向下一个结点的指针域,即存储的是下一个结点的内存地址
} Node, *ListLink;         // 结构体变量

// 创建一个新链表
void CreateListHead(int n) {
    // 使用malloc函数为链表结构动态分配一块内存空间，分配成功则返回一个指向该链表结构的指针，该指针指向该分配内存空间的首地址
    // 即 *L 是头指针
    *L = (ListLink)malloc(sizeof(Node));
    // 将该结构体的next置为NULL,创建一个包含头结点的单链表
    (*L)->next = NULL;

    // 初始化随机数种子
    srand(time(0));

    // 循环
    for (int i = 0; i < n; ++i)
    {
        *p = (ListLink)malloc(sizeof(Node));// 生成新结点
        (*p)->data = rand() % 100 + 1; // 随机生成 100 以内的数据,并将数据元素赋值给新结点的数据域

        // 执行插入操作
        (*p)->next = (*L)->next;
        (*L)->next = p; 
    }
}

尾插法实现单链表创建
代码实现如下：

// 定义一个链表结构
typedef struct ListNode
{
    int date;              // 链表一个结点的数据域
    struct ListNode *next; // 指向下一个结点的指针域,即存储的是下一个结点的内存地址
} Node, *ListLink;         // 结构体变量

void CreateListTail(int n) {
    // 初始化一个空链表
    *L = (ListLink)malloc(sizeof(ListNode));
    // 将该结构体的next设为 NULL 创建一个带有头结点的单链表
    (*L)->next = NULL;

    // 定义尾结点
    ListLink end = NULL;

    // 将头结点赋值给尾结点
    // 在没有创建其他结点之前,只有头结点,这个时候头结点就是尾结点,尾结点就是头结点
    end = *L;

    // 初始化随机种子
    srand(time(0));
    
    // 循环
    for (int i = 0; i < n; ++i)
    {
        // 创建新结点
        *p = (ListLink)malloc(sizeof(ListNode));
        (*p)->next = rand() % 100 + 1; // 随机生成 100 以内的数据,并将数据元素赋值给新结点的数据域

        // 执行插入操作
        end->next = (*p);
        end = (*p);
    }
    end->next = NULL;
}

注意：在循环结束后我们要把尾结点的指针域置为 NULL,置为 NULL 的原因方便以后遍历时能确认其是尾部

单链表的整表删除

单链表整表删除的算法思路如下：
1.声明两个结点 p 和 q
2.将链表的第一个结点赋值给 p
3.循环：

// 单链表的整表删除
Status DeleteList(ListLink *L) {
    // 声明两个结点 p 和 q
    ListLink p,q;

    //将链表的第一个节点赋值给 p
    p = (*L)->next;

    while(p) {
        // 将下一个结点赋值给 q
        q = p->next;
        // 使用 free 函数将 p 释放
        free(p);
        q=p;
    }

    // 当 p 为空时跳出循环

    // 头结点指针域为空
    (*L)->next = NULL;
}
总结

通过上面的介绍我们简单的对线性表的顺序存储结构和单链表做下对比

存储方式
时间性能

1.查找

空间性能

通过上面的比对，我们可以得到几点经验性的结论：

上一篇下一篇

猜你喜欢

热点阅读