数据结构重读 – 线性表的链式存储

1、链式存储,可以简称链表。

2、链表的一个结点(node)由两部分组成:数据域和指针域。

3、整个链表的存取必须从头指针开始,链表最后一个结点的指针为空,因此它是非随机存取的数据结构。

4、链表中插入结点:假设原结点为p,新结点为s,则:

s->next = p->next;

p->next = s;

不是很难理解吧……

5、基本操作还是比较简单的,下面假定采用无“空头”模式的如下链表:

6、假设链表A、B分别代表两个集合,现在要求A和B的并集操作。

基本思路:由于无法确定A、B都是有序的。检查B中每一个元素,如果在A中没有出现过,则插入到A中(注意集合的操作,必须考虑去重)。

测试驱动如下:

输入:A = {1, 3, 5, 7, 9}  B = {8, 5, 4, 3, 2}
输出:A={1,2, 4, 8, 3, 5, 7, 9}

7、还是A、B是集合,但都有(如都递增),求A和B的并集操作。

基本思路:类似归并。

需要注意的细节是,由于采用无头结构,会多分配一个(预分配结点),需要在最后释放掉。

测试驱动:

输入: A = {1, 3, 5, 7, 9}  B = {1, 5, 9, 20, 27}
输出: C={1, 3, 5, 7, 9, 20, 27}

8、还是A、B是集合,还是都有序(如都递增),求A和B集合的交操作。

其实比并简单些:

8、也可以用数组来描述线性链表,土名静态链表。

在如上的数据结构中,data还是存储数据,而指针next被替换成了数组下标next。

由于空间是以数组的形式预分配的,不再有NULL来判断一个结点是否有效。

我们要牺牲首尾元素[0]和[MAXSIZE-1]来构成两条链:
(1)[MAXSIZE-1]开始的链,为有效链,包含的data是有效的,通过next依次接下去。
(2)从[0]开始的链,为未分配链,当发生delete的时候,需要把无效的结点挂在这条链上。

还是由于空间都是以结点的形式预分配的,malloc、free的参数、返回值都将是下标而不再是指针,这些也都需要我们自己实现了。

注意:free和malloc都是针对free链即[0]有关的操作。

9、静态链表的插入、删除操作。

首先是简单的push_back和push_front:

然后是在指定位置删除和插入。

 

10、

 

 

Leave a Reply

Your email address will not be published.