Personal Blog

数据结构

算法-2.1

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

Table of Contents

算法

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

  1. 下面出现的LinearList是go中的interface，只是逻辑上的概念
  2. 因为只要实现了interface的类型都可以作为参数传递给该方法，所以这里既可以使用线性表,也可以使用链表作为具体实现。

algo-2.1 两个线性表的并集

实现两个线性表的并集： A = A 并 B

// Union two list, just like A = A Union B
func Union(a, b LinearList) error {
	aLen, bLen := a.GetLength(), b.GetLength()
	for i := 0; i < bLen; i++ {
		bElement, err := b.GetElementByIndex(i)
		if err != nil {
			return err
		}
		_, err = a.GetElementIndexByValue(bElement)
		if err != nil && strings.Contains(err.Error(), "can't find element") {
			if err := a.InsertByIndex(aLen, bElement); err != nil {
				return err
			}
			aLen = a.GetLength()
		} else if err != nil {
			return err
		} else if err == nil {
			continue
		}
	}
	return nil
}

algo-2.2 两个有序线性表的合并

实现将两个有序线性表的合并，合并生成的线性表依然有序

// MergeList Merge two non-decreasing order list into a new non-decreasing order list
func MergeList(a, b LinearList) (LinearList, error) {
	result := model.NewSingleLinkedList(false)
	var i, j = 0, 0
	for i < a.GetLength() && j < b.GetLength() {
		aElement, err := a.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}

		bElement, err := b.GetElementByIndex(j)
		if err != nil {
			return nil, err
		}

		ok, err := utils.LessThenOrEqual(aElement, bElement)
		if err != nil {
			return nil, err
		}
		if ok {
			if err := result.InsertByIndex(result.GetLength(), aElement); err != nil {
				return nil, err
			}
			i++
		} else {
			if err := result.InsertByIndex(result.GetLength(), bElement); err != nil {
				return nil, err
			}
			j++
		}
	}

	for i < a.GetLength() {
		aElement, err := a.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}
		if err := result.InsertByIndex(result.GetLength(), aElement); err != nil {
			return nil, err
		}
		i++
	}

	for i < b.GetLength() {
		bElement, err := b.GetElementByIndex(i)
		if err != nil {
			return nil, err
		}
		if err := result.InsertByIndex(result.GetLength(), bElement); err != nil {
			return nil, err
		}
		i++
	}

	return result, nil
}

其他同类文章

DATA-STRUCTURE · CHAPTER02
data structure chapter02

Archive