这篇文章依然介绍线性表的链式存储结构-单链表
单链表的整表创建
线性表顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和容量确定的数组并赋值的过程。单链表和线性表顺序存储结构不一样，它不像单链表那样内存地址是连续的，元素存储的地址比较分散，可以存储在内存中未被使用的任意位置，它的大小和位置不是预先分配好的，而是根据实际需求即时生成，因此单链表是一个 动态表，创建单链表的过程就是一个动态生成链表的过程，从 空表 的初始状态，依次建立各元素结点，并插入链表
单链表整表创建的过程需要用到我们前面文章中介绍到的 头插法 与 尾插法：
头插法创建单链表
1.声明一个结点 p 和 计数器变量 i
2.初始化一个空链表 L
3.将 L 头结点的指针域指向 NULL，建立一个带有头结点的单链表
4.循环：
- 生成一个新结点赋值给 p
- 随机生成一个数字赋值给结点p的数据域 p->data
- 将 p 插入到头结点与前一新结点之间
实现代码如下：
// 定义一个链表结构
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.循环：
- 将下一个结点赋值给 q
- 使用 free 函数将 p 释放
- 将 q 赋值给 p
代码实现如下：
// 单链表的整表删除
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.查找
- 顺序存储结构 O(1)
- 单链表 O(n)
2.插入和删除 - 顺序存储结构 O(n)
- 单链表在第一次查找到需要操作的元素位置后,插入和删除操作的时间复杂度仅为 O(1)
空间性能
- 顺序存储结构需要预先分配存储空间，分大了，浪费空间，分小了，容易溢出
- 单链表不需要预先分配空间，根据实际需求分配
通过上面的比对，我们可以得到几点经验性的结论：
- 若线性表频繁的查找，插入和删除操作比较少，那么我们可以选择顺序存储结构。若插入和删除操作频繁时，可以选择单链表。这些都是线性表不同存储方式的优缺点，实际开发中的数据存储结构肯定更加复杂我们需要根据具体的场景选择适合的数据存储结构
- 当线性表中的元素我们不清楚具体有多少时或者线性表的数据元素个数变化比较大的时候，最好选择单链表结构；而对于那些事先就能知道其数据元素个数，可以选择顺序存储结构
网友评论