数据结构之单链表的创建与删除

对于每个链表来说,它所占用空间的大小和位置是不需要预先分配划定的,可以根据系统的情况和实际的需求即时生成。
创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起,依次建立各元素结点,并逐个插入链表。
单链表整表创建的算法思路:

  1. 声明一指针 p 和计数器变量 i;
  2. 初始化一空链表 L;
  3. 让 L 的头结点的指针指向 NULL,即建立一个带头结点的单链表;
  4. 循环:
    • 生成一新结点赋值给 p;
    • 随机生成一数字赋值给 p 的数据域 p->data;
    • 将 p 插入到头结点与前一新结点之间。

头插法

先让新结点的 next 指向头结点之后,然后让表头的那个指向新节点。

xpHzPtnjhT.png!large

头插法建立链表虽然算法非常简单,但生成的链表中结点的次序和输入的顺序是相反的。这也是头插法不好的一个方面。
我们为什么不把新结点都放到最后呢,这才是排队时的正常思维,所谓的先来厚道。我们把每次新结点都插在终端结点的后面,这种算法称之为「尾插法」。

尾插法

r->next = p;
r = p;

kfXOOoRcFY.png!large 将刚才的表尾终结点 r 的指针指向新结点 p。 dUcwKJqDeH.png!large 本来 r 是在 ai-1 元素的结点,可现在它已经不是最后的结点了,现在最后的结点是 ai,所以应该要让将 p 结点这个最后的结点赋值给 r。此时 r 又是最终的尾结点了。

单链表的整表删除

当不打算使用这个单链表时,需要把它销毁,其实也就是在内存中将它释放掉,以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路:

  1. 声明指针 p 和 q;
  2. 将第一个结点赋值给 p;
  3. 循环:
    • 将下一结点赋值给 q;
    • 释放 p;
    • 将 q 赋值给 p;
ai
本作品采用《CC 协议》,转载必须注明作者和本文链接
不要试图用百米冲刺的方法完成马拉松比赛。
本帖由 Galois 于 9个月前 解除加精
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!