![](https://csdnimg.cn/release/download_crawler_static/41976340/bga.jpg)
在线性链表中包含元素 x 的结点之前插入新元素 b,插入过程:
(1)从可利用栈中取得一个结点,设该结点号为 p,即取得的结点的存储序号存放在
变量 p 中。并置结点 p 的数据域为插入的元素值 b。
(2)在线性链表中寻找包含元素 x 的前一个结点,该结点的存储序号为 q。
(3)将结点 p 插入到结点 q 之后。具体的操作: 首先,使结点 p 插入到结点 q 之后(即
结点 q 的后件结点),然后,使结点 q 的指针域 内容改为指向结点 p。
线性链表的插入操作, 新结点是为来自于可利用栈, 因此不会造成线性表的溢出。 同样,
由于可利用栈可被多个线性表利用, 因此, 不会造成存储空间的浪费, 大家动态地共同使用
存储空间。
3)线性链表的删除
线性链表的删除,即是在链式存储结构下的线性表中删除指定元素的结点。
操作方式:
(1)在线性表中找到包含指定元素 x 的前一个结点 p
(2)将该结点 p 后的包含元素 x 的结点从线性链表中删除,然后将被删除结点的后一
个结点 q 的地址提供给结点 p 的指针域,即将结点 p 指向结点 q。
(3)将删除的结点送回可利用栈。
从以上的删除操作可见, 删除一个指定的元素, 不需要移动其他的元素即可实现, 这是
顺序存储的线性表所不能实现的。同时,此操作还可更有效地利用计算机的存储空间。
3.循环链表 及其基本操作
在线性链表中, 虽然对数据元素的插入和删除操作比较简单, 但由于它对第一个结点和
空表需要单独处理,使得空表与非空表的处理不一致。
循环链表,即是采用另一种链接方式,它的特点如下:
(1)在循环链表中增加一个表头结点,其数据域为任意或根据需要来设置,指针域指
向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
(2)循环链表中最后一个结点的指针域不是空的, 而是指向表头结点。 在循环链表中,
所有结点的指针构成一个环状链。
在循环链表中, 只要指出表中任何一个结点的位置, 均可以从它开始扫描到所有的结点,
而线性链表做不到,线性链表是一种单向的链表,只能按照指针的方向进行扫描。
循环链表中设置了一个表头结点, 因此, 在任何时候都至少有一个结点, 因此空表与非
空表的运算相统一。
(六)树与二叉树
1.树的基本概念
树是一种简单的非线性结构。 在树结构中, 数据元素之间有着明显的层次结构。 在树的
图形表示中,用直线连接两端的结点,上端点为前件,下端点为后件。
A
B C D
E F G H I
J K L
M N