精华内容
下载资源
问答
  • 一种数据项按照相对位置存放的数据集,特别的,被称为“无序表unordered list”, 其中数据项只按照存放位置来索引,如第1个、第2个……、最后一个等。 抽象数据类型List List的基本操作 函数 含义 List() ...

    参考自 MOOC数据结构与算法Python版

    一、什么是列表List

    一种数据项按照相对位置存放的数据集,特别的,被称为“无序表unordered list”, 其中数据项只按照存放位置来索引,如第1个、第2个……、最后一个等。

    二、抽象数据类型List

    2.1 List的基本操作

    函数 含义
    List() 创建一个空列表
    add(item) 添加一个数据项到列表中,假设item原先不存在于列表中
    append(item) 添加一个数据项到表末尾,假设item原先不存在于列表中
    remove(item) 从列表中移除item,列表被修改, item原先应存在于表中
    search(item) 在列表中查找item,返回布尔类型值
    isEmpty() 返回List是否为空
    size() 返回List中包含数据项的个数
    index(item) 返回数据项在表中的位置
    insert(pos, item) 将数据项插入到位置pos,假设item原先不存在与列表中,同时原列表具有足够多个数据项,能让item占据位置pos
    pop() 从列表末尾移除数据项,假设原列表至少有1个数据项
    pop(pos) 移除位置为pos的数据项,假设原列表存在位置pos

    三、 Python实现链表:节点Node

    • 为了实现无序表数据结构, 可以采用链接表的方案。
    • 虽然列表数据结构要求保持数据项的前后相对位置, 但这种前后位置的保持, 并不要求数据项依次存放在连续的存储空间(在数据项之间建立链接指向, 就可以保持其前后相对位置)
    • 链表实现的最基本的元素是Node
    • 每个节点至少要包含2个信息: 数据项本身,以 及指向下一个节点的引用信息。注意:next为None的意义是没有下一个节点了

    链表实现:

    • 可以采用链接节点的方式构建数据集来实现无序表
    • add: 最后被加入的数据项是头节点
    • size:从链条头head开始遍历到表尾同时用变量累加经过的节点个数
    • search:从链表头head开始遍历到表尾, 同时判断当前节点的数据项是否目标
    • remove(item):首先要找到item, 这个过程跟search一样, 但在删除节点时, 需要特别的技巧:current指向的是当前匹配数据项的节点,而删除需要把前一个节点的next指向current的下一个节点,所以我们在search current的同时,还要维护前一个(previous)节点的引用。找到item之后, current指向item节点,previous指向前一个节点, 开始执行删除,需要区分两种情况:
      1. current是首个节点
      2. 位于链条中间的节点

    代码如下:

    class Node:
       def __init__(self,initdata):
           self.data = initdata
           self.next = None
           self.head = None
       def getData(self):
           return self.data
       def getNext(self):
           return self.next
       def setData(self,newdata):
           self.data = newdata
       def setNext(self, newnext):
           self.next = newnext
       def add(self, item):
           temp = Node(item)
           temp.setNext(self.head)
           self.head = temp
       def size(self):
           current = self.head
           count = 0
           while current!=None:
               count += 1
               current = current.getNext()
           return count
       def search(self,item):
           current = self.head
           found = False
           while current != None and not found:
               if current.getData() == item:
                   found = True
               else:
                   current = current.getNext()
           return found
       def remove(self,item):
           current = self.head
           previous = None
           found  = False
           while not found(): #必须在可以找到的情况下
               if current.getData() == item:
                   found = True
               else:
                   previous = current
                   current = current.getNext()
           if previous == None:   #头节点
               self.head = current.getNext()
           else: #中间的某个节点
               previous.setNext(current.getNext)
    

    3.1 从尾到头打印链表

    剑指offer原题,复原了接口

    class Solution:
        # 返回从尾部到头部的列表值序列,例如[1,2,3]
        def printListFromTailToHead(self, listNode):
            # write code here
            # 方法一  使用栈
            if not listNode:
                return []
            temp = []
            result = []
            while listNode:
                temp.append(listNode.value) # 进栈
                listNode = listNode.next
            while temp:
                result.append(temp.pop()) # 出栈
            return result
    class node(object):
        def __init__(self, item):
            self.value = item
            self.next = None
    if __name__ == '__main__':
        # 创建链表
        head_node = node(67)
        node1 = node(0)
        node2 = node(24)
        node3 = node(58)
        head_node.next = node1
        node1.next = node2
        node2.next = node3
        so = Solution()
        print(so.printListFromTailToHead(head_node))
    
    output:
    [58, 24, 0, 67]
    
    展开全文
  • 集合这个概念应该大家在学习数学的时候都听过并且有学习过,它也是一种数据结构,我们还是需要用代码来实现集合的很多方法。 学习过ES6语法的小伙伴应该知道,ES6新增了一种 Set 数据结构,这就是集合,尽管官方已经...

    本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

    集合这个概念应该大家在学习数学的时候都听过并且有学习过,它也是一种数据结构,我们还是需要用代码来实现集合的很多方法。

    学习过ES6语法的小伙伴应该知道,ES6新增了一种 Set 数据结构,这就是集合,尽管官方已经向我们提供了这种数据结构,但是为了学习它的思想和实现过程,我们还是来亲自学习实现一下吧,顺便学习一下ES6中 Set 数据结构是如何实现的

    • 公众号:前端印象
    • 不定时有送书活动,记得关注~
    • 关注后回复对应文字领取:【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

    在这里插入图片描述

    一、什么是集合

    集合就是一种包含着不同元素的数据结构,即在集合结构里,每一个元素都是独一无二的,互不相同,同时所有数据都是无序的。

    如图中的每个圆圈就代表一个集合,集合中存储着相应的数据
    在这里插入图片描述

    其中,集合1集合2 中同样是存储着数据 1 2 3 4,但分布情况却不同,这说明集合的无序性,而且 集合1集合2并不相等

    二、集合分类

    集合也有几种特殊的分类,即 并集交集差集子集。其展示的是两个集合之间的关系

    (1)交集

    交集就是由既属于 集合1 又属于 集合2 的元素组成的集合。

    如图

    在这里插入图片描述

    集合1中有数据 1 2 3 4
    集合2中有数据 1 2 4 5 8

    那么既属于 集合1 又属于 集合2 的元素就是 1 2 4,因此这几个元素就组合成了新的集合 集合3,也称为 集合1集合2交集

    (2)并集

    并集: 由所有属于 集合1集合2 的元素组成的集合

    如图
    在这里插入图片描述

    集合1中有数据 1 4
    集合2中有数据 2 3 5 8

    那么 集合1集合2 所有元素组合起来就是 1 2 3 4 5 8·,这些元素组合起来就组成了新集合 集合3,也称 集合3集合1集合2并集

    (3)差集

    差集: 就是属于 集合1 但不属于 集合2 的所有元素组成的集合

    如图
    在这里插入图片描述
    集合1中有数据 1 2 4
    集合2中有数据 1 3 5 8

    那么属于 集合1 但不属于 集合2 的元素就是 2 4,这两个元素组成了新的集合 集合3,也称 集合3集合1集合2差集

    (4)子集

    子集: 是判断属于 集合1 的元素是否也都属于 集合2

    如图
    在这里插入图片描述
    集合1中有数据 1 2 4
    集合2中有数据 1 2 3 4 5 8

    此时因为 集合1 中的所有元素同时也属于 集合2,所以说 集合1集合2 的子集,也可以说是 集合1 属于 集合2

    三、集合的方法

    了解了以上这些集合的概念,接下来我们来看一下封装一个集合,都有哪些方法。

    首先一个数据结构,必备的增删改查方法是肯定需要的,其次我们尽可能地与ES6的 Set 数据结构中的方法一致,这样方便大家之后学习

    方法 作用
    add() 将一个数据添加到集合中
    has() 判断一个元素是否存在于集合中
    delete() 删除集合中的某个元素
    clear() 清空集合内的所有元素
    size() 返回集合内的元素个数
    values() 返回集合内的所有元素,保存在数组中
    union() 获取与另一个集合的并集
    intersect() 获取与另一个集合的交集
    difference() 获取与另一个集合的差集
    subset() 判断是否为另一个集合的子集

    四、用代码实现集合

    (1)创建一个构造函数

    首先创建一个大的构造函数,用于存放集合的一些属性和方法。

    function Set() {
        // 属性
        this.items = {}
    }
    

    属性 items 用于存放集合中的元素,这里之所以使用对象来存储而不是数组,是因为数组若实现无重复数据很麻烦,需要遍历全部元素,而对象就很方便,直接通过 key 就能获取到集合中是否已存在该数据

    (2)实现has()方法

    has() 方法是用于判断集合中是否存在某数据。该方法接收一个参数 value 用于查找数据

    这里先介绍一个JS中对象的内置方法:
    hasOwnProperty() 方法可以判断某属性是否为对象的自有属性,若是,则返回 true ;否则返回 false

    所以实现思路就很简单了,直接将参数 value 传给 hasOwnProperty() 方法,并将其返回结果作为 has() 方法的返回结果即可

    我们来看一下代码吧

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 判断是否存在元素
        Set.prototype.has = function(value) {
            return this.items.hasOwnProperty(value)
        }
    }
    

    因为这里我们还没有介绍到 add() 方法,因此还没法验证该方法是否可行,而且之后我们会在别的方法中频繁用到 has() 方法用于验证集合中元素是否重复,这里就不做过多的验证了

    (3)实现add()方法

    add() 方法是用于向集合中添加数据,并返回当前集合。该方法接收一个参数 value 用于存储

    实现思路很简单,先通过我们封装的 has()方法 判断集合中是否存在该元素,若存在,则直接返回 false ;否则直接通过 obj[key] = value 的方式存储即可。这里我们是将参数 value 既作为 key 又作为 value

    来看一下代码

    function Set() {
        // 属性
        this.items = {}
    
    	// 方法
    	// 添加元素
        Set.prototype.add = function(value) {
    		// 判断是否存在重复元素
    		if(this.has(value)) return false;
    		
    		// 存储元素
            this.items[value] = value
    		
    		// 返回当前集合内容
            return this.items
        }
    }
    

    我们来使用一下该方法

    let set = new Set()
    
    set.add(3)
    set.add(1)
    set.add(6)
    
    console.log(set.items)
    /* 打印结果:
    	{ 
    	    '1': 1, 
    	    '3': 3, 
    	    '6': 6 
    	}
    */
    

    可以看到,我们三个添加数据的操作都成功了

    (4)实现delete()方法

    delete() 方法就是用于删除集合中指定的元素。该方法接收一个参数 value 用于查找到对应的元素并删除

    实现思路很简单,先通过 has() 方法判断集合中是否存在该元素,若不存在,则直接返回 false ,表示删除失败 ;否则,直接用关键字 delete 删除集合中对应的元素,并返回 true 表示删除成功

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 删除元素
        Set.prototype.delete = function(value) {
        	// 判断集合中是否存在该元素
            if(!this.has(value)) return false;
            
            // 删除指定元素
            delete this.items[value]
    		
    		// 返回 true,表示删除成功
            return true
        }
    }
    

    我们来使用一下该方法

    let set = new Set()
    
    // 添加三个元素,分别为 3 1 6
    set.add(3)
    set.add(1)
    set.add(6)
    
    // 删除元素 6
    set.delete(6)
    
    console.log(set.items)
    /* 打印结果:
    	{ 
    	    '1': 1, 
    	    '3': 3
    	}
    */
    

    我们可以看到,6 成功被删除了

    (5)实现clear()方法

    clear() 方法时用于清空集合中的所有元素的。该方法无需传入参数

    实现思路: 直接将 this.items 指向一个空的对象即可

    我们看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 清空集合
        Set.prototype.clear = function() {
            this.items = {}
        }
    }
    

    来使用一下该方法

    let set = new Set()
    
    // 添加三个元素,分别为 3 1 6
    set.add(3)
    set.add(1)
    set.add(6)
    
    // 清空集合
    set.clear()
    
    console.log(set.items)
    /* 打印结果:
    	{}
    */
    

    我们可以看到,集合中的所有元素已经被清空了

    (6)实现size()方法

    size() 方法就是返回集合中的元素个数。该方法无需传入参数

    这里先介绍一个JS中对象的内置方法:
    keys()方法可以接收一个对象参数,并返回该对象所有的键,存放在一个数组中并返回

    实现思路: 通过 keys() 获取包含集合所有键的数组,并返回该数组的 length 即可

    我们来看一下代码吧

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 判断集合内元素个数
        Set.prototype.size = function() {
            return Object.keys(this.items).length
        }
    }
    

    来使用一下该方法

    let set = new Set()
    
    console.log(set.size())   // 0,此时集合为空
    
    // 添加三个元素,分别为 3 1 6
    set.add(3)
    set.add(1)
    set.add(6)
    
    console.log(set.size())   // 3,此时集合内有三个元素
    

    (7)实现values()方法

    values() 方法是用于返回集合中的所有元素。该方法无需传入任何参数

    实现思路: 直接将通过方法 keys() 获取到的数组返回即可

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 返回集合内所有元素
        Set.prototype.values = function() {
            return Object.keys(this.items)
        }
    }
    

    我们来使用一下该方法

    let set = new Set()
    
    console.log(set.values())   // [],此时集合为空
    
    // 添加三个元素,分别为 3 1 6
    set.add(3)
    set.add(1)
    set.add(6)
    
    console.log(set.values())   // ['1', '3', '6'],此时集合内有三个元素,分别为 1 、3 、6
    

    (8)实现union()方法

    union() 方法用于获取当前集合与另一个集合的并集。该方法需要传入一个集合 otherSet 作为参数

    实现思路:

    1. 先创建一个空的新集合 newSet
    2. 通过 values() 方法获取到包含当前集合的所有元素的数组 oldSetValue,并对其进行遍历,将遍历到每一个元素都添加到 newSet() 中去
    3. 再通过 values() 方法获取到包含 otherSet 的所有元素的数组 otherSetValue,并对其进行遍历,将遍历到每一个元素都添加到 newSet() 中去
    4. 返回 newSet

    在该实现过程中,我们是通过 add() 方法将两个集合中的所有元素添加到新的集合中的,因为 add() 方法中已经包含了检验元素的重复性部分,所以我们无需担心两个集合的元素是否会重复

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 获取交集
        Set.prototype.union = function(otherSet) {
        	// 1. 创建新的空集合
            let newSet = new Set()
    		
    		// 2. 获取当前集合的所有元素
            let oldSetValue = this.values()
            
            // 2.1 遍历当前集合的元素,并添加到 newSet中
            for(let i = 0; i < oldSetValue.length; i++) {
                newSet.add(oldSetValue[i])
            }
            
    		// 3. 获取 otherSet集合的所有元素
            let otherSetValue = otherSet.values()
    
    		// 3.1 遍历 otherSet集合的元素,并添加到 newSet中
            for(let j = 0; j < otherSetValue.length; j++) {
                newSet.add(otherSetValue[j])
            }
    		
    		// 4. 返回获取到的交集
            return newSet
        }
    }
    

    我们来使用一下该方法

    // 创建集合1
    let set1 = new Set()
    
    // 向集合1中添加元素 3 1 6
    set1.add(3)
    set1.add(1)
    set1.add(6)
    
    // 创建集合2
    let set2 = new Set()
    
    // 向集合2中添加元素 3 2 8
    set2.add(3)
    set2.add(2)
    set2.add(8)
    
    // 获取集合1和集合2的并集,即集合3
    let set3 = set1.union(set2)
    
    // 查看集合3内的所有元素
    console.log(set3.values())
    /* 打印结果:
    	[ '1', '2', '3', '6', '8' ]
    */
    

    (9)实现intersect()方法

    intersect() 方法是用于获取当前集合与另一个集合的交集。该放需要传入一个集合 otherSet 作为参数

    实现思路:

    1. 先创建一个空的新集合 newSet
    2. 通过 values() 方法获取到包含当前集合的所有元素的数组 oldSetValue,并对其进行遍历,判断每一个元素是否也存在于 otherSet 中,若不存在,则不做任何处理
    3. 若存在,则将该元素添加到 newSet 中去
    4. 返回 newSet

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 获取并集
        Set.prototype.intersect = function(otherSet) {
        	// 1. 创建空的新集合
            let newSet = new Set()
            
            // 2. 获取当前集合的所有元素
            let oldSetValue = this.values()
    
    		// 3. 遍历当前集合的所有元素
            for(let i = 0; i < oldSetValue.length; i++) {
            
                let item = oldSetValue[i]
                
                // 3.1 元素同时存在于 otherSet中
                if(otherSet.has(item)) {
                    newSet.add(item)
                }
            }
    		
    		// 4. 返回获取到的交集
            return newSet
        }
    }
    

    我们来使用一下该方法

    // 创建集合1
    let set1 = new Set()
    
    // 向集合1中添加元素 3 1 6
    set1.add(3)
    set1.add(1)
    set1.add(6)
    
    // 创建集合2
    let set2 = new Set()
    
    // 向集合2中添加元素 3 2 8
    set2.add(3)
    set2.add(2)
    set2.add(8)
    
    // 获取集合1和集合2的交集,即集合3
    let set3 = set1.intersect(set2)
    
    // 查看集合3内的所有元素
    console.log(set3.values())
    /* 打印结果:
    	[ '3' ]
    */
    

    (10)实现difference()方法

    difference() 方法是用于获取当前集合与另一个集合的差集。该放需要传入一个集合 otherSet 作为参数

    实现思路:

    1. 先创建一个空的新集合 newSet
    2. 通过 values() 方法获取到包含当前集合的所有元素的数组 oldSetValue,并对其进行遍历,判断每一个元素是否也存在于 otherSet 中,若存在,则不做任何处理
    3. 若不存在,则将该元素添加到 newSet 中去
    4. 返回 newSet

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 获取差集
        Set.prototype.difference = function(otherSet) {
    		// 1. 创建空的新集合
            let newSet = new Set()
    		
    		// 2. 获取当前集合的所有元素
            let oldSetValue = this.values()
    
    		// 3. 遍历当前集合的所有元素
            for(let i = 0; i < oldSetValue.length; i++) {
            
                let item = oldSetValue[i]
                
                // 3.1 otherSset中没有该元素
                if(!otherSet.has(item)) {
                    newSet.add(item)
                }
            }
    		
    		// 4. 返回获取到的差集
            return newSet
        }
    }
    

    我们来使用一下该方法

    // 创建集合1
    let set1 = new Set()
    
    // 向集合1中添加元素 3 1 6
    set1.add(3)
    set1.add(1)
    set1.add(6)
    
    // 创建集合2
    let set2 = new Set()
    
    // 向集合2中添加元素 3 2 8
    set2.add(3)
    set2.add(2)
    set2.add(8)
    
    // 获取集合1和集合2的差集,即集合3
    let set3 = set1.difference(set2)
    
    // 查看集合3内的所有元素
    console.log(set3.values())
    /* 打印结果:
    	[ '1', '6' ]
    */
    

    (11)实现subset()方法

    subset() 方法用于判断当前集合是否为另一个集合的子集。该方法需要传入一个集合 otherSet 作为参数

    实现思路:

    1. 先创建一个空的新集合 newSet
    2. 通过 values() 方法获取到包含当前集合的所有元素的数组 oldSetValue,并对其进行遍历,判断每一个元素是否也存在于 otherSet 中,若不存在,则直接返回 false,表示当前集合不是 otherSet 的子集
    3. 若所有元素遍历完后,该方法仍为返回任何值,此时直接返回 true,表示当前集合为 otherSet 的子集

    我们来看一下代码

    function Set() {
        // 属性
        this.items = {}
    	
    	// 方法
    	// 判断是否为另一个集合的子集
        Set.prototype.subset = function(otherSet) {
        	
        	// 1. 创建空的新集合
            let oldSetValue = this.values()
            for(let i = 0; i < oldSetValue.length; i++) {
                if(!otherSet.has(oldSetValue[i])) {
                    return false
                }
            }
    
            return true
        }
    }
    

    我们来是用一下该方法

    // 创建集合1
    let set1 = new Set()
    
    // 向集合1中添加元素 3 1 
    set1.add(3)
    set1.add(1)
    
    // 创建集合2
    let set2 = new Set()
    
    // 向集合2中添加元素 3 2 8 1 9
    set2.add(3)
    set2.add(2)
    set2.add(8)
    set2.add(1)
    set2.add(9)
    
    // 判断集合1是否为集合2的子集
    let ret = set1.subset(set2)
    
    // 查看集合3内的所有元素
    console.log(ret)
    // 打印结果:true
    

    五、结束语

    集合的讲解就到这里了,希望大家对集合有了更深一层的理解。下一篇文章我将讲解一下

    大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

    然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

    或者也可以去我的github上获取完整代码,欢迎大家点个Star

    我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

    展开全文
  • 一种数据项按照相对位置存放的数据集 特别的,被称为“无序表unordered list”,其中数据项只按照存放位置来索引,如第1个、第2个……、最后一个等。(为了简单起见,假设表中不存在重复数据项) 如一个考试分数的...

    列表List:什么是列表?

    在前面基本数据结构的讨论中, 我们采用Python List来实现了多种线性数据结构

    列表List是一种简单强大的数据集结构,提供了丰富的操作接口

    但并不是所有的编程语言都提供了List数据类型,有时候需要程序员自己实现。

    一种数据项按照相对位置存放的数据集

    特别的,被称为“无序表unordered list”,其中数据项只按照存放位置来索引,如第1个、第2个……、最后一个等。(为了简单起见,假设表中不存在重复数据项)

    如一个考试分数的集合“54, 26, 93, 17,77和31”

    如果用无序表来表示, 就是[54, 26, 93,17, 77, 31]

    无序表List的操作如下:

    • List():创建一个空列表
    • add(item):添加一个数据项到列表中,假设
    • item原先不存在于列表中
    • remove(item):从列表中移除item,列表被修改, item原先应存在于表中
    • search(item):在列表中查找item,返回布尔类型值
    • isEmpty():返回列表是否为空
    • size():返回列表包含了多少数据项
    • append(item):添加一个数据项到表末尾,假设item原先不存在于列表中
    • index(item):返回数据项在表中的位置
    • insert(pos, item):将数据项插入到位置pos,假设item原先不存在与列表中,同时原列表具有足够多个数据项,能让item占据位置pos
    • pop():从列表末尾移除数据项,假设原列表至少有1个数据项
    • pop(pos):移除位置为pos的数据项,假设原列表存在位置pos

    采用链表实现无序表

    为了实现无序表数据结构, 可以采用链接表的方案。

    虽然列表数据结构要求保持数据项的前后相对位置, 但这种前后位置的保持, 并不要求数据项依次存放在连续的存储空间

    在这里插入图片描述

    如下图, 数据项存放位置并没有规则, 但如果在数据项之间建立链接指向, 就可以保持其前后相对位置

    第一个和最后一个数据项需要显式标记出来,一个是队首,一个是队尾,后面再无数据了。
    在这里插入图片描述

    链表实现:节点Node

    链表实现的最基本元素是节点Node

    每个节点至少要包含2个信息: 数据项本身,以及指向下一个节点的引用信息注意next为None的意义是没有下一个节点了,这个很重要
    在这里插入图片描述

    代码

    class Node:
        def __init__(self, initdata):
            self.data = initdata
            self.next = None
    
        def getData(self):
            return self.data
    
        def getNext(self):
            return self.next
    
        def setData(self, newdata):
            self.data = newdata
    
        def setNext(self, newnext):
            self.next = newnext
    

    可以采用链接节点的方式构建数据集来实现无序表

    链表的第一个和最后一个节点最重要如果想访问到链表中的所有节点,就必须从第一个节点开始沿着链接遍历下去

    在这里插入图片描述

    所以无序表必须要有对第一个节点的引用信息

    设立一个属性head,保存对第一个节点的引用空表的head为None
    在这里插入图片描述

    随着数据项的加入, 无序表的head始终指向链条中的第一个节点

    注意!无序表mylist对象本身并不包含数据项(数据项在节点中)其中包含的head只是对首个节点Node的引用判断空表的isEmpty()很容易实现
    在这里插入图片描述

    接下来, 考虑如何实现向无序表中添加数据项, 实现add方法。

    由于无序表并没有限定数据项之间的顺序

    新数据项可以加入到原表的任何位置

    按照实现的性能考虑, 应添加到最容易加入的位置上。

    由链表结构我们知道

    要访问到整条链上的所有数据项

    都必须从表头head开始沿着next链接逐个向后查找

    所以添加新数据项最快捷的位置是表头,整个链表的首位置

    add方法

    ### 按照右图的代码调用, 形成的链表如下图

    链接次序很重要!add方法实现代码如下:

    def add(self, item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head = temp
    

    在这里插入图片描述

    size:从链条头head开始遍历到表尾同时用变量累加经过的节点个数。

    在这里插入图片描述

    def size(self):
        current = self.head
        count = 0
        while current != None:
            count = count + 1
            current = current.getNext()
        return count
    

    从链表头head开始遍历到表尾, 同时判断当前节点的数据项是否目标

    在这里插入图片描述

    def search(self, item):
        current = self.head
        found = False
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
        return found
    

    remove(item)方法

    首先要找到item, 这个过程跟search一样, 但在删除节点时, 需要特别的技巧

    current指向的是当前匹配数据项的节点而删除需要把前一个节点的next指向current的下一个节点,所以我们在search current的同时,还要维护前一个(previous)节点的引用
    在这里插入图片描述

    找到item之后, current指向item节点,previous指向前一个节点, 开始执行删除, 需要区分两种情况:

    current是首个节点;或者是位于链条中间的节点
    在这里插入图片描述
    在这里插入图片描述

    def remove(self, item):
        current = self.head
        previous = None
        found = False
    
        while not found:
            if current.getData() == item:
                found = True
            else:
                previous = current
                current = current.getNext()
    
        if previous == None:
            self.head = current.getNext()
        else:
            previous.setNext(current.getNext())
    

    完整代码如下:

    class UnorderedList:
        def __init__(self):
            self.head = None
    
        def add(self, item):
            temp = Node(item)
            temp.setNext(self.head)
            self.head = temp
    
        def size(self):
            current = self.head
            count = 0
            while current != None:
                count = count + 1
                current = current.getNext()
            return count
    
        def search(self, item):
            current = self.head
            found = False
            while current != None and not found:
                if current.getData() == item:
                    found = True
                else:
                    current = current.getNext()
            return found
    
        def remove(self, item):
            current = self.head
            previous = None
            found = False
    
            while not found:
                if current.getData() == item:
                    found = True
                else:
                    previous = current
                    current = current.getNext()
    
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())
    
    展开全文
  • 当然,在连续存储的情况下不需要额外保存相对位置(如数组),但是如果数据以图1这样的随机方式保存,这就需要为每个元素配置额外的信息,指明它下个元素的位置(图2),这样每个元素的相对位置,就通过个元素到...

    无序列表的实现:链表

    为了实现无序列表,先要实现我们通常称为“链表”的结构。前面说过我们保持列表元素之间的相对位置。当然,在连续存储的情况下不需要额外保存相对位置(如数组),但是如果数据以图1这样的随机方式保存,这就需要为每个元素配置额外的信息,指明它下一个元素的位置(图2),这样每个元素的相对位置,就通过一个元素到另一个元素的链接实现了。



    元素不固定物理位置


    2通过明确链接维持相对关系

    特别要注意,链表第一个元素的位置必须单独指定,一旦知道了第一个元素,它就能告诉我们第2个元素的位置,依次类推。链表的外部引用通常就指向它的头部。类似地,最后一个元素,也要表明他“下面没有了”。

    节点类

    节点(Node)是实现链表的基本模块,每个节点至少包括两个重要部分。首先,包含节点自身的数据,称为“数据域”。其次,包括对下一个节点的“引用”。下面代码是Node类的代码。为了构造节点,需要初始化节点的数据,如图3,为节点赋值并返回一个节点对象。不过图4才是一般节点的图示方式。节点类也包括访问和修改数据域及指针域的的方法。

    Listing 1

    classNode:
        def__init__(self,initdata):
            self.data= initdata
            self.next=None
     
        defgetData(self):
            returnself.data
     
        defgetNext(self):
            returnself.next
     
        defsetData(self,newdata):
            self.data= newdata
     
        defsetNext(self,newnext):
            self.next= newnext

    用上述类创建一个节点对象

    >>> temp= Node(93)
    >>> temp.getData()
    93

    特殊的引用值None在节点类和链表中都非常重要。对None的引用代表没有下一个节点,象构造函数中,就是创建一个节点,把并它的“引用”赋值为None。因为有时把最后一个节点称为“接地点”,我们干脆用电气上的接地符号代表None。初始化一个“引用”时,先赋值为None,是个不错的主意。


    3节点对象包括数据域和对下一个节点的引用



    4节点的典型表示法

    无序列表类

    如前所述,无序列表通过一个节点的集合来实现,每个节点包括对下一个节点的引用。只要我们找到第一个节点,跟着引用就能走遍每个数据项。按这个想法,无序列表类必须保存对第一个节点的引用。下面是构造方法,注意每个列表对象包含对“列表头”(head)的引用。

    Listing 2

    classUnorderedList:
     
        def__init__(self):
            self.head=None

    创建列表的时候进行初始化,这里没有数据项,赋值语句

    >>> mylist= UnorderedList()

    创建的链表如图5所示。我们已经讨论过节点类的特殊引用None,这里用来表示head没有引用任何节点。最后,前面给出的链表例子如图6所示,head指向第一个节点,第一个节点包括第一个数据项。同样,第一个节点包括对下一个节点的引用。特别重要的是,链表类不包括任何节点对象,相反,它只包括对列表第一个元素的引用。

    5 空列表




    6 整数链表

    下面代码段中的isEmpty方法,用来检查head引用是否是None,方法中的返回值表达式self.head==None,只有当链表中没有节点时为真。既然一个新建链表是空,构造函数和“isEmpty“函数一定保持一致,这也显示了用None来代表“结束”的优势。在python语言中,None能够和任意的引用作比较,如果两个变量引用了同一对象,他们就是相等的。今后还会经常用到这种方法。

    Listing 3

    defisEmpty(self):
        returnself.head==None
    这样的话,怎样把新的数据项加入列表呢?需要实现一个新add方法。但在此之前,需要处理一个重要问题:链表把新数据项放在什么位置?既然列表是无序的,新数据项的位置与原有元素关系不大,新数据项可放在任意位置,这样的话,我们可以把新项放在最容易处理的位置。

    回想链表结构只为我们提供了一个入入,即列表的head,所有其他节点都要通过引用逐个访问,这说明,最容易的处理的地方就是在head位置,或开始的位置。换个说法,新数据项总是列表的第一个项,原有数据项都通过引用依次排在它的后面。

    图6显示了通过 add方法几次形成的链表。

    >>> mylist.add(31)
    >>> mylist.add(77)
    >>> mylist.add(17)
    >>> mylist.add(93)
    >>> mylist.add(26)
    >>> mylist.add(54)

    注意到31是第一个加入的数据,最终它是链表里最后一个。同样,54是最后加入的,它成为链表的第一个节点的数据

    Add方法在代码4中实现。每个数据项都在节点对象内部。第2行创建一个新节点,并把数据保存在它的数据域内。然后需要把这个节点与现有结构连接起来,图7表明了两个步骤。第一步,把新节点的引用改成对原来第一个节点的引用。这样列表里其他节点就与新节点建立了链接,只要把修改head为对新节点的引用。第4行的赋值语句设置列表的head

    上面两个步骤的顺序特别重要,如果3和4反序会怎么样?如果先修改了head的引用,就象图8所示,因为head是对列表节点的唯一外部引用入口,一旦失去,所有原来的节点将从内存中消失。

    Listing 4

    代码4

    defadd(self,item):
        temp = Node(item)
        temp.setNext(self.head)
        self.head= temp

    7 两步增加新节点


    8两步顺序倒置的结果

    下面我们要建立的方法size, search, remove,都基于链表的一种技术,即遍历实现的。遍历指系统地访问每个节点的过程。为此,我们从第一个节点的外部引用开始,每访问过一个节点,通过引用移动到下一个节点实现遍历。

    为了实现size方法,我们也要遍历链表,这个过程中用一个变量记录我们经过的节点。代码5显示了计数器代码。外部引用叫做current,第二行中初始化为链表的head。开始时因为没有经历过任何节点,所以计数器变量为0,第4-6行实现了遍历。只要current引用没有看到None,就把current指向下一个节点(第6行)。

    最后,迭代结束后,count得以返回。图9显示了处理过程。

    Listing 5

    defsize(self):
        current =self.head
        count =0
        while current !=None:
            count = count +1
            current = current.getNext()
     
        return count

    图9 从头到尾的遍历

    在无序列表中查找一个值 也要使用遍历技术,当访问每个节点的时候,都要比较它的数据是否与要查找的数据相符。这样,可能不用遍历全部的节点就能找到,如果找到了就不必继续找下去。事实上,如果我们真到了列表的尾部,就说明没找到。

    List6显示了查找方法的实现。象在size方法中一样,遍历从head开始(2行),另用了一个found变量记录是否已经找到。因为开始的状态是没找到,found初始化为False。第4行使用了两个条件决定是否要继续遍历,1后面还有节点2、还没找到。行5行检查当前节点的数值是否符合,如果是,found值为True,遍历结束。

     

    Listing 6

    defsearch(self,item):
        current =self.head
        found =False
        while current !=Noneandnot found:
            if current.getData()== item:
                found =True
            else:
                current = current.getNext()
     
        return found

    试着查找一下17

    >>> mylist.search(17)
    True

    17在列表中,遍历过程只需到含17的节点,在这点上,found被置Truewhile的条件不成立,退出循环,返回found值。如图10所示


    图10 查找17
    Remove方法需要两个步骤。首先,需要遍历列表找到要删除的数据,一旦找到,再删除。第一步和查找很象,遍历列表,找到这个数据——因为假定数据是存在的,一定在到达None之前找到——这表明要用found的布尔值来标志

    找到后,found变成Truecurrent就是对包含要删除的数据的节点的引用。一种可能的方式是用一种标志代替原来的数值,表明这个数值不存在。但这样一来,链表的节点数量和实际的数量对不上,所以不如直接删除这个节点。

    为了删除节点,我们要把待删除节点前面的那个节点的next指向待删除节点后面那个节点就可以了。不幸的是,找到current以后,我们没办法再回到它前面,来不及改了。

    解决办法办法是在遍历时使用两个外部引用,current和以前一样,标志当前正在遍历的,新的引用,我们叫它previous,跟在current后面遍历,这样current找到要删除节点时,previous正好停在current前面节点上。

    Listing7显示了remove方法的全部代码。2-3行为两个引用分配初值。注意,current开始于headprevious是要跟在current后面的,所以previous的初值是None,因为head前面没有节点(图11)。Found仍是叠代的控制变量。

    在6-7行检查是否找到了要删除的节点,如果是,found为True。如果不是,previous和current各自向前一步到下一个节点。再次注意,这个前移的步骤非常关键,previous必须先移动到当前current的位置,current才能向前走。这个过程时常称为“尺蠖”,因为这瞬间previous和current指向同一对象,就象尺蠖弓腰。图12显示了previous和current在查找17的过程中的运动。

    尺蠖,又名弓腰虫,行动时一屈一伸像个拱桥——译者)

    Listing 7

    defremove(self,item):
        current =self.head
        previous =None
        found =False
        whilenot found:
            if current.getData()== item:
                found =True
            else:
                previous = current
                current = current.getNext()
     
        if previous ==None:
            self.head= current.getNext()
        else:
            previous.setNext(current.getNext())

    11 previouscurrent的初始化


    12 previoucurrent的运动历程


    一旦查找过程结束,开始删除过程。图13显示了要修改的链接。不过有一种特殊情况要处理,如果要删除的数据就在第一个节点上,current就是第一个节点,这里previous仍然是None,我们前面说过,prevous所在节点是要修改它的next引用。但在这种特殊情况下,要修改的不是previousnext,而是列表的head。(图14


    13 删除中间某节点



    14 移除第一个节点


    12行让我们检查是否上面所说的特殊情况。如果previous还没有前移,它就仍然是None,但这时foundTrue,在这种情况下(13)head被修改为指向current的下个节点,效果上就是删除了第一个节点。不过,如果previous不是None,那么要删除的节点就是在中间某处。这种情况下,previous所在节点的next要做修改,15行使用了setNext方法完成删除。要注意的是,在两种情况下,修改引用都指向了current.getNext()

    不过这两种情况是否适用于要删除的节点在最后节点上呢?留作练习。

    以下是无序列表的全部代码及测试代码

    class Node:
        def __init__(self, initdata):
            self.data = initdata
            self.next = None
     
        def getData(self):
            return self.data
     
        def getNext(self):
            return self.next
     
        def setData(self, newdata):
            self.data = newdata
     
        def setNext(self, newnext):
            self.next = newnext
     
     
    classUnorderedList:
        def __init__(self):
            self.head = None
     
        def isEmpty(self):
            return self.head == None
     
        def add(self, item):
            temp = Node(item)
            temp.setNext(self.head)
            self.head = temp
     
        def size(self):
            current = self.head
            count = 0
            while current != None:
                count = count + 1
                current = current.getNext()
     
            return count
     
        def search(self, item):
            current = self.head
            found = False
            while current != None and not found:
                if current.getData() == item:
                    found = True
                else:
                    current = current.getNext()
     
            return found
     
        def remove(self, item):
            current = self.head
            previous = None
            found = False
            while not found:
                if current.getData() == item:
                    found = True
                else:
                    previous = current
                    current = current.getNext()
     
            if previous == None:
                self.head = current.getNext()
            else:
                previous.setNext(current.getNext())
     
     
    mylist =UnorderedList()
     
    mylist.add(31)
    mylist.add(77)
    mylist.add(17)
    mylist.add(93)
    mylist.add(26)
    mylist.add(54)
     
    print(mylist.size())
    print(mylist.search(93))
    print(mylist.search(100))
     
    mylist.add(100)
    print(mylist.search(100))
    print(mylist.size())
     
    mylist.remove(54)
    print(mylist.size())
    mylist.remove(93)
    print(mylist.size())
    mylist.remove(31)
    print(mylist.size())
    print(mylist.search(93))



    其他方法,append,insert,indexpop留为练习。练习要注意,每个方法都要考虑是否适用于第一个元素或其他情况。另外,insertindexpop需要链表的索引名,我们约定索引名是整数,从0开始。


    展开全文
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,篇文章足够。能换你个收藏了吧?
  • 数据结构】有序树和无序树的区别

    万次阅读 多人点赞 2017-07-20 16:42:43
    这个问题想了好久才弄清楚,现在总结一下。 概念是这样的: ...无序树 ...树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树 ...换而言之,兄弟结点有...那么,3个结点到底能组成多少有序树,多少
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    1.数据结构:是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学中是指所有能...
  • 超硬核!数据结构学霸笔记,考试面试吹牛就靠它

    万次阅读 多人点赞 2021-03-26 11:11:21
    上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。
  • redis的五种数据结构原理分析

    万次阅读 多人点赞 2018-11-13 15:51:08
    redis中的五种数据结构分析 应用场景分析 总结   关于Redis redis是个开源的使用C语言编写的个kv存储系统,是个速度非常快的非关系远程内存数据库。它支持包括String、List、Set、Zset、hash五种数据...
  • 今天参加个小考试,就是考的这
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    数据结构指的是“组数据的存储结构”,算法指的是“操作数据的组方法”。 数据结构是为算法服务的,算法是要作用再特定的数据结构上的。 最常用的数据结构预算法: 数据结构:数组、链表、栈、队列、散列表、...
  • 2022考研数据结构_1 绪论

    万次阅读 2020-12-28 16:29:19
    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 1.2 数据结构起源 ​ 1968年,美国的高德纳教授开创了数据结构的课程体系。 ​ 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们...
  • github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接 https://github.com/Lpyexplore/structureAndAlgorithm-JS 数组是我们平时常见的并且经常使用的一种数据结构,那么它具有...
  • redis5种数据结构讲解及使用场景

    万次阅读 多人点赞 2017-12-12 10:36:22
    redis提供了5中数据结构,理解每种数据结构的特点对于redis开发运维非常重要。 、字符串 字符串类型是redis最基础的数据结构,首先键是字符串类型,而且其他几种结构都是在字符串类型基础上构建的, 所以字符串...
  • redis中的5种数据结构

    万次阅读 2016-04-22 22:24:53
    种数据结构都有相关的命令,比如set命令表示使用string来存储value,get命令的参数只能为对应value值存储为string的key,操作其他数据结构需要相应的命令,这些命令可以从redis官方站点查询。string使用string时,...
  • 逻辑结构:数据的逻辑结构是对数据之间关系的描述,与存储结构无关,同一种逻辑结构可以有多多种存储结构。 逻辑结构主要分为两大类:线性存储结构和非线性存储结构 线性存储结构是数据元素有序集合,数据结构之间...
  • JavaScript数据结构-集合

    千次阅读 2016-11-06 15:41:57
    集合(set)是一种包含不同元素的数据结构。集合中的元素称为成员。集合具有两个重要特性: (1)集合中的成员是无序的 (2)集合中不允许相同成员存在 当想创建一个数据结构,用来保存一些独一无二的元素时,...
  • 基本数据结构

    千次阅读 2019-03-18 09:29:46
    集合结构:该结构数据元素间的关系是“属于同个集合”; 线性结构:该结构数据元素之间存在的关系; 树形结构:该结构数据元素之间存在对多的关系; 图形结构:该结构数据元素之间存在多对多的...
  • * 有个整形数组A,请设计个复杂度为O(n)的算法,算出排序后相邻两数的最大差值。 给定个int数组A和A的大小n,请返回最大的差值。保证数组元素多于1个。 * @author Administrator * */ 今天在牛客网刷题时,...
  • 数据结构之Vector

    千次阅读 2017-04-17 22:27:07
    向量是一种抽象数据类型ADT,与数组不同,它提供了很多接口,能够实现更多的功能。如何理解ADT抽象数据类型,看下面这幅图片(图片均来源于学堂在线,引用请标注出处) OK那么Vector给我们提供了哪些接口呢? 接
  • Redis支持五种数据类型:string(字符串),hash(哈希),list(列表),set(无序集合)及zset(有序集合)。 在秒杀项目里,我用过redis的Set和Hash结构: String:个 key 对应个字符串,string是Redis 最...
  • 数据结构

    千次阅读 多人点赞 2017-07-05 16:07:40
    章一、选择题 1、数据结构的研究的3大方面内容是逻辑结构、存储结构、数据间的运算。 2、数据间的逻辑结构包括线性结构、和非线性结构两大类。3、数据的存储结构分为顺序结构、链式存储结构、索引存储结构、...
  • 数据结构和算法03】链表

    千次阅读 多人点赞 2016-04-12 20:29:44
    不管在哪一种数组中删除效率都很低。况且一个数组创建后,它的大小是无法改变的。 在本章中,我们将讨论下链表这个数据结构,它可以解决上面的一些问题。链表可能是继数组之后第二种使用得最广泛的通用数据结构了...
  • HashMap是无序

    千次阅读 2013-12-02 18:15:53
    设计初衷主要是为了解决键值(key-value)对应关联的,HashMap的优势是可以很快的根据键(key)找到该键对应的值(value),但是我们在使用的过程中需要注意一下,HashMap是一种无序的存储结构。HashMap的实现是假定...
  • 数据结构之图

    千次阅读 2016-12-22 22:07:09
    基本概念图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间可能存在关系。即结点之间的关系可以是任意的,图中任意元素之间...
  • 简单说数据结构——集合

    千次阅读 2017-03-23 16:37:30
    集合的定义是由无序且唯一(即不能重复)的项组成的。不包含任何元素的集合就叫做空集。上高中那会,我们都接触过集合,其中一些概念比如交集、并集、差集等等。ECMAScript6也实现了集合这种数据结构——Set类。...
  • 数据结构与顺序表 +理解数据结构与算法 +掌握顺序表的操作 数据结构 是指相互之间有一定联系的数据元素的集合,元素之间的相互联系 称为 逻辑结构。 数据元素之间的逻辑结构分为:  集合 线性 树形 ...
  • 初入数据结构的树(Tree)以及Java代码实现 树的定义 为什么叫树? 树型结构的元素具有对多关系 树的定义 树的一些基本概念 树的结点 后代,祖先 子树、空树 树的度与高(深度),结点的度与层次 有序树,无序...
  • Redis 五常见的数据结构:zset

    千次阅读 2019-02-19 17:20:22
    Redis 五常见的数据结构:zset

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 118,774
精华内容 47,509
关键字:

哪一种数据结构是无序的

数据结构 订阅