关于静态链表实现 (A-B)U(B-A)

所谓(A-B)U(B-A),实际上就是A独有的那一部分和B独有的那一部分的并集

qq%e6%88%aa%e5%9b%be20160921161103也就是简简单单的如图所示

其实这个问题本身用动态链表(就是常规链表)是很好解决的,但是由于我们要用静态链表来实现,所以就会显得略微有一些麻烦,到底哪里麻烦?

  1. 相对于动态链表,静态链表的内存分配函数需要自己来实现
  2. 相对于动态链表,静态链表的内存回收函数需要自己来实现.
  3. 静态链表的连接方式,和动态链表也有所不同
  4. 静态链表在实际操作中比动态链表更容易断(人为因素)

首先大概说一下答题思想吧,如果想先把两个链表建立起来在互相查找删减,实现会很麻烦,因此我采用的方法是:首先我完全建立A集合,然后再B集合输入的过程中对A中已经存在的元素进行删除操作

由于我采用的是传统写法因此对于时间复杂度可能不会考虑太多

首先我们要解决的一个问题就是静态链表的初始化函数,这个其实还是挺简单的

伪代码:

木有

C语言代码:

总得思想就是和静态链表建立一样,不多啰嗦

然后第二个需要考虑的问题就是静态链表的内存分配(包括分配新的空间和删除不需要的空间),因此在这里需要两个函数来完成这个内存分配mallocSpace和freeSpace

在这里一定不要忘记静态链表的载体数组的首元素的作用:第一个未使用(可分配)节点的位置

最后呢就是一个主体部分的了

这个kernel函数有一些比较有意思的地方

这个步骤的存在是为了声明一个头节点,因为在静态链表的实际操作中0位置是存储第一个未使用(可分配)节点的位置,所以就需要一个表头来记录正式链表的头,因此需要申请一个空的空间作为表头

这条while语句的第二个条件是防止Anow跳到0(实在惭愧这个bug看了这么久才看出来)

千万不要忘记了在后续添加B集合的时候要把原有集合A的最后一个成员的指针域的0改成新申请的静态地址(就是数组位置)

这大致就是我犯的错误了,最后附上我自己写的显示全部数组成员的代码

About the author

NOBUG.IN

Add comment

By NOBUG.IN

Your sidebar area is currently empty. Hurry up and add some widgets.