数据结构

算法-2.3

本节将第二章的第三节出现的算法进行实现，算法序号和原书中的序号保持一致。

Table of Contents

算法
其他同类文章

算法

这里将第二章的第三节出现的算法进行实现，算法序号和原书中的序号保持一致。

algo-2.8 查找线性表中的指定索引位置的元素

在现有的线性链表查找等于某个特定值的元素，对应的方法是：

algo-2.9 线性链表元素的插入

在algo-2.4 线性链表元素的插入已经描述

algo-2.10 线性链表元素的删除

在algo-2.5 线性链表元素的删除已经描述

algo-2.11 线性表表头插入元素

该算法建立线性表，并接受N个元素，每个元素的内容为手动输入，然后依次插入表头，形成一个和输入逆向的线性表。这里将这个过程拆成两部分：头插和赋值。

首先展示核心的链表头插算法

// InsertToHead always insert element into the list's head
func (s *SingleLinkedList) InsertToHead(element any) error {
 node := &SingleLinkedListNode{
     Data: element,
 }

 node.Next = s.head.Next
 s.head.Next = node

 s.length += 1

 return nil
}

然后就是使用for进行赋值，使用UT进行验证：这里依次输入5,4,3,2,1，预期结果为1,2,3,4,5

func TestSingleLinkedList_InsertToHead(t *testing.T) {
 inputArray := []int{5, 4, 3, 2, 1}

 sl := NewSingleLinkedList(false)
 for i := 0; i < len(inputArray); i++ {
     if err := sl.InsertToHead(inputArray[i]); err != nil {
         t.Error(err)
         t.FailNow()
     }
 }

 sl.Traverse()
}

结果为如下所示，可见结果正常：

=== RUN   TestSingleLinkedList_InsertToHead
Gonna traverse to print all element:
 index: 0, value: 1
 index: 1, value: 2
 index: 2, value: 3
 index: 3, value: 4
 index: 4, value: 5
--- PASS: TestSingleLinkedList_InsertToHead (0.00s)
PASS

algo-2.12 两个有序线性表的合并——省空间版本

之前我们在algo-2.2 两个有序线性表的合并已经实现了两个有序线性表的合并算法。但是2.2的算法是额外生成了第三个链表，新增的元素个数是两个输入线性表的长度总和。

而该算法直接使用了两个已有线性表的元素，只是生成一个头结点，将原属于两个输入链表的元素重新按照顺序进行串联得到新的链表，该算法没有新增任何链表元素结点，所以节省了存储空间。但是该算法也有明显的副作用，就是很可能会破坏原有输入链表元素间的先后关系，使得原有链表不可用于后续操作。

// MergeList Algo 2.12: Merge two non-decreasing order list into a new non-decreasing order list
func MergeList(a, b *SingleLinkedList) (*SingleLinkedList, error) {
	c := NewSingleLinkedList(false)
	pa := a.head.Next
	pb := b.head.Next
	pc := c.head
	for pa != nil && pb != nil {
		ok, err := utils.LessThenOrEqual(pa.Data, pb.Data)
		if err != nil {
			return nil, err
		}
		if ok {
			pc.Next = pa
			pa = pa.Next
		} else {
			pc.Next = pb
			pb = pb.Next
		}
		pc = pc.Next
		c.length++
	}

	for pa != nil {
		pc.Next = pa
		pa = pa.Next
		pc = pc.Next
		c.length++
	}

	for pb != nil {
		pc.Next = pb
		pb = pb.Next
		pc = pc.Next
		c.length++
	}

	return c, nil
}

algo-2.13 查找线性表中的特定元素

在现有的线性静态链表中查找等于某个特定值的元素，对应的方法是：

静态链表的GetElementIndexByValue方法

algo-2.14 & algo-2.15 & algo-2.16

原书的做法：

初始化算法（algo-2.14）：对提前创建好的静态链表space进行了初始化，形成了一个带有额外不存储数据的第一个结点（index==0），且最后一个元素(index==MAXSIZE-1)指向头结点的链表结构。
同时初始化动作将整个数据形成了一个依次指向后一个结点，最后一个结点指向第一个结点的结构。这点很重要，后续备用结点就利用了这种结构。
第一个结点永远指向第一个可用的备用结点，且备用结点也依次指向其他备用结点(由第2点的初始化保证)，所以第一个结点就是备用结点的入口。
分配结点的算法（algo-2.15）：通过备用结点入口（index==0）查询到第一个可用的结点index并返回，同时改变备用结点的指向，使其指向新的第一个备用结点的index。
回收结点的算法（algo-2.16）：改变备用结点入口指向，使其指向将待回收的结点，并将待回收结点指向为原第一个可用结点（头插法）。这样就可以保证所有备用结点永远都在一个链上，且备用结点入口不变。

本文这里对于整个静态链表结点的操作略有不同：

初始化时，只是分配go的切片类型来存储最大容量为capacity的元素，但不会将所有切片中的元素进行类似algo-2.14中进行初始化指针指向。
回收结点的算法：采用了一个map来作为结点GC,来记录被回收的结点index，当在下一次分配请求到来时，会优先分配已回收的结点。
分配结点的算法：如果GC中有可分配的结点，则优先使用该结点，否则从剩余空闲的结点中分配一个结点。

这些主要体现在以下方法中：

algo-2.17

原书对 $(A-B)\cup(B-A)$ 的实现，核心思路是在初始化后的静态链表的基础上:

将第一个结点（index==0）固定为备用结点的入口，该入口永远指向第一个备用的结点，分配和回收操作只在备用结点入口上进行修改（其实就是以后会提到的堆栈结构，在栈顶进行入栈和出栈的操作）。这样做的好处是显然易见的，当进行多次分配和回收之后，备用结点不像链表刚初始化时一样都在一起，而是分散的分布在数组中，通过这种方法就可以将所有备用结点串联在一起，也为结点的分配提供了简单而统一的操作。
将静态链表概念中的表头结点固定在第二个（index==1）结点上，用来指向插入链表中的第一个实际元素，然后再通过实际元素上的链表指向依次找到后续结点。

本文这里并非照搬该算法，但是总体思路大致一致，在上述三个本书算法的基础上，进行了实现，且使用到的方法都符合线性表的接口定义：

// 求A、B两个静态链表的对称差集
// SymmetricDifference just like: (A-B) Union (B-A)
func SymmetricDifference(a, b *StaticLinkedList) (*StaticLinkedList, error) {
	result := NewStaticLinkedList(a.capacity + b.capacity)

	// Loop insert a into result
	for i := 0; i < a.length; i++ {
		ele, err := a.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}

		if err := result.InsertByIndex(result.GetLength(), ele); err != nil {
			return nil, err
		}
	}

	for i := 0; i < b.length; i++ {
		ele, err := b.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}

		if eleIndex, err := result.GetElementIndexByValue(ele); err != nil {
			// if err is can't find element, just insert into result
			if strings.Contains(err.Error(), "can't find element") {
				if err := result.InsertByIndex(result.GetLength(), ele); err != nil {
					return nil, err
				}
			} else {
				return nil, err
			}
		} else {
			// You find the element from B is also in A, so delete the element from result
			if _, err := result.DeleteByIndex(eleIndex); err != nil {
				return nil, err
			}
		}
	}

	return result, nil
}

algo-2.18 循环双向链表元素的插入

与单向链表的主要区别就是处理prior指针，以及curr指针可能为空的处理。

循环双向链表的InsertByIndex方法

algo-2.19 循环双向链表元素的删除

与单向链表的主要区别就是处理prior指针，以及curr指针可能为空的处理。

循环双向链表的DeleteByIndex方法

algo-2.20 & algo-2.21

原书重新定义了带表头结点的链表结构，在链表结构中加了代表长度的字段，同时添加了表头、表尾指针。和原书之前直接使用链表结点相比，增加了一层包装，对于某些操作进行了优化。比如，获取链表长度这个功能，原来需要遍历整个线性表之后才能获取到，而现在将长度作为链表的一个字段进行存储，可以直接获取。

而我们的链式线性表的实现则从一开始就采用了类似这种结构。以循环双向链表为例；

在代表链表的结构体中，我们不仅有长度、头指针，还添加了一个是否是循环链表的标志位(isCircular)。
在代表结点的结构体中，我们还添加了一个是否是头结点的标志位(isHead)。真正的链中，第一个结点是用于标记表头结点的辅助结点，并不用来存储真实的数据。而表头结点所指示的第一个Next结点才是真正的数据结点。

所以这里我们不再对原书这两个算法涉及到的新结构进行重复实现。虽然原书中增加了一些方法，是我们开头的线性表中没有进行定义的，但是思路别无二致，我们这里也就不再添加，感兴趣的读者可以自己在原有线性表定义的方法列表基础上尝试新增。

其他同类文章

2023-10-23 DATA-STRUCTURE · CHAPTER02
data structure chapter02