03B-5慕课视频播放-Data Structures and Algorithm Design Part I-MOOC慕课视频教程-柠檬大学

接下来考察列表的唯一化问题

也就是如何将列表中

可能存在的重复元素剔除掉

在我们接下来将要介绍的这个算法中

我们始终将整个列表视作由三部分组成

这个前缀部分

作为这个算法的一条不变性

已经能够保证不包含任何重复的节点

而我们当前所要考察的呢

就是接下来的这个节点

不妨将它称作p

当然此时可能还存在一个非空后缀

我们这个算法的关键部分是

如果当前那个节点的数值为e

我们就以e为目标

在前缀中对它进行查找

无论查找成功与否

我们都可以将问题的规模

有效地降低至少一个单位

具体的算法可以实现为这样一段代码

我们来解读一下

首先是处理平凡情况

确保这个列表中至少包含两个节点

接下来这一步可以认为是初始化

我们可以看到p最初的时候

是指向首节点

也就是说这个时候的前缀

实际上可以认为是空的

所以刚才我们所说的

不变性自然也就满足

那么接下来

算法的主体部分是这个循环

可以看到每一次我们都将

p中所存的那个元素

这就是e 作为查找的对象

那么查找的范围在哪呢？

是以p为基准的r个真前驱

那么这个r是多少呢？

这个实际上也是这个算法的一个不变性

我们说 r在任何时候其实就等于

整个这个前缀的长度

换而言之也就是在整个

这个前缀中进行查找

无非两种情况

一种就是这个find这个操作

返回了一个非空的元素

它的数值当然就等于e

在这里呢我们是以q来指向它的

这个时候大家可以看到

我们将这两个重复元素中的一个

具体来说也就是这个q删除掉

否则的话呢如果q是一个null呢？

那就意味着查找失败

换而言之

在这样的一个前缀中根本就不存在

语义相同的元素

所以在这个时候 p这个节点

可以归入这样的一个前缀中去

使得这个前缀拓展一个单位

在这种情况下

我们就可以将r加1

也就是说前缀的长度

增加一个单位

同时p转入它的后继元素

继续迭代

直到抵达哨兵trailer

也就意味着整个列表全部扫描

并且处理完毕

细心的同学可能已经注意到

这里如果发现了一个q

与刚才那个p相同的话

我们倾向于去删除q

既然它们数值都一样

为什么我们不去删除p呢？

在此大家不妨暂停一下

略加思考然后再继续

是的

我想你应该已经找到答案了

如果我们不是删除q 而是删除p

表面上看是等价的

但是在接下来的这步迭代中

我们首先要将p转向p的后继这个操作

就存在风险

因为p这个时候实际上已经

没有一个明确的指向

很有可能会发生错误

所以相对而言

删除q是更安全的一个方法

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

-A.Computation

--01A-1

--01A-2

--01A-3

--01A-4

--01A-5

--演示

--01A-6

--（a）计算--作业

-B.Computational_Models

--01B-1

--01B-2

--01B-3

--01B-4

--01B-5

--01B-6

--01B-7

--01B-8

-B.Computational_Models--Homework

-C.Big_o

--01C-1

--01C-2

--01C-3

--01C-4

--01C-5

--01C-6

--01C-7

-C.Big_o--Homework

01.Introduction II

-D.Algorithm_analysis

--01D-1

--01D-2

--01D-3

--01D-4

--01D-5

--01D-6

--01D-7

-D.Algorithm_analysis--Homework

-E.Iteration+Recursion

--01E-1

--01E-2

--01E-3

--01E-4

--01E-5

--01E-6

--01E-7

--01E-8

--01E-09

-E.Iteration+Recursion--Homework

-F.Dynamic_Programming

--01XC-1

--01XC-2

--01XC-3

--01XC-4

--01XC-5

--01XC-6

-- 演示

--01XC-7

--01XC-8

--01XC-9

--01XC-A

-F.Dynamic_Programming--Homework

-Homework

02.Vector I

-A.Interface+Implementation

--02A-1

--02A-2

--02A-3

--02A-4

--02A-5

-A.Interface+Implementation--Homework

-B.extendable_vector

--02B-1

--02B-2

--02B-3

--02B-4

--02B-5

-B.extendable_vector--Homework

-C.unsorted_Vector

--02C-1

--02C-2

--02C-3

--02C-4

--02C-5

--02C-6

--02C-7

--02C-8

-C.unsorted_Vector--Homework

-D1.Sorted_Vector.uniquify

--02D1-1

--02D1-2

--02D1-3

--02D1-4

--02D1-5

-D1.Sorted_Vector.uniquify--Homework

-D2.Sorted_Vector.binary_search

--02D2-1

--02D2-2

--02D2-3

--02D2-4

--02D2-5

--02D2-6

--02D2-7

-D2.Sorted_Vector.binary_search--Homework

02.Vector II

-D3.Sorted_Vector.fibonaccian_search

--02D3-1

--02D3-2

--02D3-3

--02D3-4

-D3.Sorted_Vector.fibonaccian_search--Homework

-D4.Sorted_Vector.binary_search_optimized

--02D4-1

--02D4-2

--02D4-3

--02D4-4

--02D4-5

-D4.Sorted_Vector.binary_search_optimized--Homework

-D5.Sorted_Vector.interpolation_search

--02D5-1

--02D5-2

--02D5-3

--02D5-4

--02D5-5

-D5.Sorted_Vector.interpolation_search--Homework

-E.Bubblesort

--02 E-1

--02E-2

--02E-3

--02E-4

--02E-5

-E.Bubblesort--Homework

-F.Mergesort

--02F-1

--02F-2

--02F-3

--02F-4

--02F-5

--02F-6

-F.Mergesort-Homework

-Homework

03.List

-A.interface+Implementation

--03A-1

--03A-2

--03A-3

--03A-4

-A.interface+Implementation--Homework

-B.Unsorted_list

--03B-1

--03B-2

--03B-3

--03B-4

--03B-5

-B.Unsorted_list--Homewrok

-C.Sorted_list

--03C-1

--03C-2

--03C-3

-C.Sorted_list--Homewrok

-D.Selectionsort

--03D-1

--03D-2

--03D-3

--03D-4

--03D-5

--03D-6

-D.Selectionsort--Homework

-E.Insertionsort

--03E-1

--03E-2

--03E-3

--03E-4

--03E-5

--03E-6

--03E-7

--03E-8

-E.Insertionsort--Homework

-（xd）：LightHouse

--03XD

-Homework

04.Stack+Queue

-A.stack-ADT+implementation

--04A-1

--04A-2

--04A-3

-A.stack-ADT+implementation--Homework

-C1.stack-App-conversion

--04C1-1

--04C1-2

--04C1-3

-C1.stack-App-conversion--Homework

-C2.stack-App-parentheses

--04C2-1

--04C2-2

--04C2-3

--04C2-4

--04C2-5

--04C2-6

-C2.stack-App-parentheses--Homewrok

-C3.stack-App-permutation

--04C3-1

--04C3-2

--04C3-3

--04C3-4

--04C3-5

-C3.stack-App-permutation--Homework

-C4.stack-App-infix

--04C4-1

--04C4-2

--04C4-3

--04C4-4

--04C4-5

--04C4−6A

--04C4−6B

--04C4−6C

--04C4-6D

-C4.stack-App-infix--Homework

-C5.stack-App-rpn

--04C5-1

--04C5-2

--04C5-3

--04C5-4

-C5.stack-App-rpn--Homework

-D.Queue-ADT+implementation

--04D-1

--04D-2

--04D-3

-Homework

05.Binary_Tree

-A.Tree

--05A-1

--05A-2

--05A-3

--05A-4

--05A-5

--05A-6

--05A-7

-A.Tree--Homework

-B.Representation

--05B-1

--05B-2

--05B-3

--05B-4

--05B-5

-B.Representation--Homework

-C.Binary_Tree

--05C-1

--05C-2

--05C-3

-C.Binary_Tree--Homework

-D.Implementation

--05D-1

--05D-2

--05D-3

--05D-4

--05D-5

-D.Implementation--Homework

-E1.Preorder

--05E1-1

--05E1-2

--05E1-3

--05E1-4

--05E1-5

--05E1-6

--05E1-7

--05E1-8

--05E1-9

-E1.Preorder--Homework

-E2.Inorder

--05E2-1

--05E2-2

--05E2-3

--05E2-4

--05E2-5

--05E2-6

--05E2-7

-E2.Inorder--Homework

-E4.LevelOrder

--05E4-1

--05E4-2

--05E4-3

-E4.LevelOrder--Homework

-E5.reconstruction

--05E5-1

--05E5-2

--05E5-3

-E5.reconstruction--Homework

-Homework

06.Graph

-A.Introduction

--06A-1

--06A-2

--06A-3

-A.Introduction--Homework

-B1.Adjacency_Matrix

--06B1-1

--06B1-2

--06B1-3

--06B1-4

--06B1-5

--06B1-6

--06B1-7

--06B1-8

--06B1-9

-B1.Adjacency_Matrix--Homework

-C.BFS

--06C-1

--06C-2

--06C-3

--06C-4

--06C-5

--06C-6

--06C-7

--06C-8

-C.BFS--Homework

-D.DFS

--06D-1

--06D-2

--06D-3

--06D-4

--06D-5

--06D-6

--06D-7

-D.DFS--Homework

-Homework

03B-5在线视频

03B-5课程教案、知识点、字幕

Data Structures and Algorithm Design Part I课程列表：

01.Introduction I

01.Introduction II

02.Vector I

02.Vector II

03.List

04.Stack+Queue

05.Binary_Tree

06.Graph

03B-5笔记与讨论

也许你还感兴趣的课程: