线性表和链表

一，线性结构

1.Array

Array文档：可以自行阅读相关文档来了解Array

class array.array(typecode[, initializer])

 

 

array.append(x)：添加元素到数组末尾

array.count(x)：计算元素出现次数

array.extend(iterable)：将迭代器中的元素依次添加到数组末尾，不过要注意元素的类型要一致，要不然会抛出TypeError

array.fromfile(f, n)：读取文件中n个元素，如果文件中元素数量小于n，抛出EOFError，不过之前写入的数据仍然存在。

array.fromlist(list)：与上例差不多，相当于for x in list: a.append(x)，类型要一致。

array.fromstring(s)：与上例差不多。

array.index(x)：返回第一次元素出现的下标。

array.insert(i, x)：将元素x插入到i的位置上。

array.pop([i])：移除i下标的元素并且返回这个值，默认-1（最后一个）。

array.remove(x)：移除掉第一个x元素，不对后续x元素处理。

array.reverse()：反转数组。

array.tofile(f)：把数组内容写到文件中。

array.tolist()：把数组转化为列表，不改变内容。

array.tostring()：把数组转化为字符串。

array.tounicode()：和tostring差不多，但是要注意数组类型是'u'。要不然会抛出ValueError。

文档内容差不多就这些，大部分是写方法，加粗的为不常用的，还有一些方法会有些版本限制，稍微注意。

2.List实现Array部分功能

 

3.代码实现

class Array():
    def __init__(self,size):
        self.__size = size
        self.__item = [None]*size
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, index):
        return self.__item[index]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value

    def remove(self,value):
       for i,ele in enumerate(self.__item):
           if ele == value:
               self.__item[i] = None
       return


if __name__ == '__main__':
    a1 = Array(10)
    a1[0] = 1
    a1[1] = 2
    a1[2] = 3
    a1[3] = 4
    a1.remove(2)

    for value in a1:
        print(value)

 

 

二，链式结构

1.单链表

1.基本原理

和线性结构不同，链式结构内存不连续的，而是一个个串起来的，这个时候就需要每个链接表的节点保存一个指向下一个节点的指针。 这里可不要混淆了列表和链表（它们的中文发音类似，但是列表 list 底层其实还是线性结构，链表才是真的通过指针关联的链式结构）。 看到指针你也不用怕，这里我们用的 python，你只需要一个简单赋值操作就能实现，不用担心 c 语言里复杂的指针。

先来定义一个链接表的节点，刚才说到有一个指针保存下一个节点的位置，我们叫它 next， 当然还需要一个 value 属性保存值。

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

然后就是我们的单链表 LinkedList ADT:

class LinkedList(object):
    """ 链接表 ADT
    [root] -> [node0] -> [node1] -> [node2]
    """

 

 

2.代码实现

class Node():
    def __init__(self,value=None,next=None):
        self.value = value
        self.next = next

    def __str__(self):
        return 'Node:{}'.format(self.value)


class LinkedList():
    def __init__(self):
        self.root = Node()
        self.size = 0
        self.next = None#增加新数据时，将新数据地址与谁关联

    def append(self,value):
        node = Node(value)
        if not self.next:
            self.root.next = node
        else:
            self.next.next = node
        self.next = node
        self.size += 1

    def append_first(self,value):
        node = Node(value)
        if not self.next:
            self.root.next = node
            self.next = node
        else:
            temp = self.root.next
            self.root.next = node
            node.next = temp
        self.size += 1

    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.next:
                yield current
                current = current.next
            yield current
    def find(self,value):
        for n in self.__iter__():
            if n.value == value:
                return n
    def find_count(self,value):
        count = 0
        for n in self.__iter__():
            if n.value == value:
                count += 1
        return count

    def remove(self,value):
        prev = self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prev.next == None
                    self.next = prev
                prev.next = n.next
                del n
                self.size -= 1
                return True
            prev = n

    def remove_all(self,value):
        prev = self.root
        for n in self.__iter__():
            if n.value == value:
                if n == self.next:
                    prev.next == None
                    self.next = prev
                prev.next = n.next
                del n
                self.size -= 1
                continue
            prev = n






if __name__ == '__main__':
    link = LinkedList()
    link.append(11)
    link.append(11)
    link.append(11)
    link.append(14)
    link.append(15)
    link.append(16)
    for value in link:
        print(value)
    print(link.find(11))
    print(link.find_count(11))
    link.remove(16)
    for value in link:
        print(value)
    link.remove_all(11)
    print("--"*20)
    for value in link:
        print(value)

 

2.双链表

上边我们亲自实现了一个单链表，但是能看到很明显的问题，单链表虽然 append 是 O(1)，但是它的 find 和 remove 都是 O(n)的， 因为删除你也需要先查找，而单链表查找只有一个方式就是从头找到尾，中间找到才退出。 我们需要在一个链表里能高效的删除元素， 并把它追加到访问表的最后一个位置，这个时候单链表就满足不了了。

1.基本原理

这里就要使用到双链表了，相比单链表来说，每个节点既保存了指向下一个节点的指针，同时还保存了上一个节点的指针。

class Node(object):
    def __init__(self, value=None, prev=None, next=None):
        self.value, self.prev, self.next = value, prev, next
  • 看似我们反过来遍历双链表了。反过来从哪里开始呢？我们只要让 root 的 prev 指向 tail 节点，不就串起来了吗？
  • 直接删除节点，当然如果给的是一个值，我们还是需要查找这个值在哪个节点？ - 但是如果给了一个节点，我们把它拿掉，直接让它的前后节点互相指过去不就行了？哇欧，删除就是 O(1) 了，两步操作就行啦

 

 

 

2.代码实现

class Node():
    def __init__(self,value=None,prev=None,next=None):
        self.value = value
        self.next = next
        self.prev = prev
    def __str__(self):
        return "Node:{}".format(self.value)

class DoubleLinkedList():
    def __init__(self):
        self.size = 0
        self.root = Node()
        self.end = None

    def append(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root#新节点指向根节点
            self.end = node#末节点指针指向新节点


        #有节点
        else:
            self.end.next = node#末节点指向新节点
            node.prev = self.end  # 新节点指向末节点
            self.end = node#末节点移动到新节点
        self.size += 1

    def append_first(self,value):
        node = Node(value=value)
        #无节点
        if not self.end:
            self.root.next = node  # root节点指向新节点
            node.prev = self.root  # 新节点指向根节点
            self.end = node  # 末节点指针指向新节点
        else:
            node.prev = self.root#新节点指向根节点
            temp = self.root.next#保存原来的第一个节点
            self.root.next = node#将新节点替换为第一个节点
            node.next = temp#让新节点的下一个节点为原来的第一个节点
            temp.prev = node#将原来的第一个节点的上一个节点设置为新节点
        self.size += 1


    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current
                current = current.next
            return current
        else:
            print("LinkedList is empty")

    #逆向迭代
    def inverse_iter(self):
        current = self.end
        if current:
            while current is not self.root:
                yield current
                current = current.prev
        else:
            print("LinkedList is empty")

    def find(self,value):
        pass

    def find_count(self,value):
        pass

    def remove(self,value):
        pass

    def remove_all(self,value):
        pass

if __name__ == '__main__':
    link = DoubleLinkedList()
    link.append(11)
    link.append(12)
    link.append(13)
    link.append(14)
    link.append(15)

    gen = (link.inverse_iter())
    for value in gen:
        print(value)

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/691263.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

数据库(27)——多表查询——自连接

数据库(27)——多表查询——自连接

语法 SELECT 字段列表 FROM 表A 别名A JOIN 表A 别名B ON 条件...; 自连接可以是内连接查询也可以是外连接查询。 演示 我新增了字段friend便于演示 查询所有人的名字以及他们的friend的人的名字： select a.name,b.name from user a,user b where a.friendb.id; 其…
阅读更多...
LeetCode72编辑距离

LeetCode72编辑距离

题目描述 解析 一般这种给出两个字符串的动态规划问题都是维护一个二维数组，尺寸和这两个字符串的长度相等，用二维做完了后可以尝试优化空间。这一题其实挺类似1143这题的，只不过相比1143的一种方式，变成了三种方式，就…
阅读更多...
构建数字社会：Web3时代的社会治理与价值重构

构建数字社会：Web3时代的社会治理与价值重构

随着数字化技术的飞速发展，我们正逐渐迈入Web3时代，这是一个以去中心化、开放性和透明性为特征的新时代。在这个时代，数字技术将不仅仅改变我们的生活方式和商业模式，还将对社会治理和价值观念产生深远影响。本文将探讨Web3时代下…
阅读更多...
今天是放假带娃的一天

今天是放假带娃的一天

端午节放假第一天 早上5点半宝宝就咔咔乱叫了，几乎每天都这个点醒，准时的很，估计他是个勤奋的娃吧，要早起锻炼婴语，哈哈 醒来后做饭、洗锅、洗宝宝的衣服、给他吃D3，喂200ml奶粉、给他洗澡、哄睡&#xff0…
阅读更多...
Unity2D游戏制作入门 | 12(之人物受伤和死亡的逻辑动画)

Unity2D游戏制作入门 | 12(之人物受伤和死亡的逻辑动画)

上期链接：Unity2D游戏制作入门 | 11(之人物属性及伤害计算)-CSDN博客 上期我们聊到了人物的自身属性和受伤时的计算，我们先给人物和野猪挂上属性和攻击属性的代码，然后通过触发器触发受伤的事件。物体（人物也好敌人也行&#xff…
阅读更多...
信息系统项目管理师0148：输出（9项目范围管理—9.3规划范围管理—9.3.3输出）

信息系统项目管理师0148：输出（9项目范围管理—9.3规划范围管理—9.3.3输出）

点击查看专栏目录 文章目录 9.3.3 输出 9.3.3 输出 范围管理计划 范围管理计划是项目管理计划的组成部分，描述将如何定义、制定、监督、控制和确认项 目范围。范围管理计划用于指导如下过程和相关工作： ①制定项目范围说明书；②根据详细项目范…
阅读更多...
【树莓派内核版本降级】笔记

【树莓派内核版本降级】笔记

【树莓派内核版本降级】笔记 文章目录 【树莓派内核版本降级】笔记一、起因二、降级流程1.降级失败经验（使用一体化的降级命令）2.手动下载固件（降级成功） 一、起因 我在学习树莓派内核开发以及驱动开发的时候，树莓派在…
阅读更多...
【uni-app】申请高德地图key，封装map.js，实现H5、iOS、Android通过getlocation获取地图定位信息

【uni-app】申请高德地图key，封装map.js，实现H5、iOS、Android通过getlocation获取地图定位信息

文章目录 map组件基础使用封装map.js，实现定位1、使用第三方地图：高德，申请对应平台key1、申请H5 key2、申请微信小程序 key3、申请android key查看证书详情，可以看到SHA1查看/设置Android包名 4、申请ios key 2、封装map1、lib/m…
阅读更多...
例54：Draw使用

例54：Draw使用

建立一个控制台工程，输入代码： Screen 13 移动到（50,50）而不绘图 Draw "BM 50,50" B:移动但不绘制,M:移动到指定位置 将绘图颜色设置为2（绿色） Draw "C2" C将颜色改为n …
阅读更多...
2024最新 Jenkins + Docker实战教程（八）- Jenkins实现集群并发构建

2024最新 Jenkins + Docker实战教程（八）- Jenkins实现集群并发构建

😄 19年之后由于某些原因断更了三年，23年重新扬帆起航，推出更多优质博文，希望大家多多支持～ 🌷 古之立大事者，不惟有超世之才，亦必有坚忍不拔之志 🎐 个人CSND主页——Mi…
阅读更多...
SEO之关键词分布

SEO之关键词分布

初创企业搭建网站的朋友看1号文章；想学习云计算，怎么入门看2号文章谢谢支持： 1、我给不会敲代码又想搭建网站的人建议 2、新手上云 经过核心关键词确定与关键词扩展，应该已经得到一个至少包含几百个相关关键词的大列表。这些关键…
阅读更多...
解决 There is no getter for property named ‘null‘ in ‘class 报错

解决 There is no getter for property named ‘null‘ in ‘class 报错

1. 问题 mybatis-plus在更新删除操作时报错 Closing non transactional SqlSession [org.apache.ibatis.session.defaults.DefaultSqlSession750ee72a] 2024-06-08 21:03:07 [http-nio-8080-exec-3] ERROR o.a.c.c.C.[.[.[.[dispatcherServlet] - Servlet.service() for servl…
阅读更多...
人工智能在【肿瘤生物标志物】领域的最新研究进展｜顶刊速递·24-06-08

人工智能在【肿瘤生物标志物】领域的最新研究进展｜顶刊速递·24-06-08

小罗碎碎念 本期文献速递的主题是——人工智能在“肿瘤生物标志物”领域的最新研究进展。 重点关注 今天推荐的6篇文献中，第二篇和第三篇是小罗最喜欢的，因为对于临床来说，比较具有实际意义，也和自己的想法很契合。 尤其是第三篇…
阅读更多...
python 多任务之多进程

python 多任务之多进程

多任务 优势 多个任务同时执行可以大大提高程序执行效率，可以充分利用CPU资源，提高程序的执行效率 概念 是指在同一时间内执行多个任务 多进程 概念 进程（process）是资源分配的最小单位，他是操作系统进行资源分配…
阅读更多...
Vue3【十二】09Computed计算属性

Vue3【十二】09Computed计算属性

Vue3【十二】09Computed计算属性 计算属性 获取全名 这种方式是只读的不能修改 这样定义fullName是一个计算属性&#xff0c;可读可写 案例截图 目录结构 代码 Person.vue <template><div class"person"><h1>我是 Person 组件</h1>姓&…
阅读更多...
Latex中表格（3）

Latex中表格（3）

Latex中的表格 一、多行或多列单元格 这篇主要说Latex中表格出现多行或者多列单元格的形式. 一、多行或多列单元格 可能用到的宏包 \usepackage{booktabs}\usepackage{multirow} 代码&#xff1a; \begin{table}[h!] \centering \caption{Your caption here} \begin{tabul…
阅读更多...
Vue学习day05笔记

Vue学习day05笔记

day05 一、学习目标 1.自定义指令 基本语法&#xff08;全局、局部注册&#xff09;指令的值v-loading的指令封装 2.插槽 默认插槽具名插槽作用域插槽 3.综合案例&#xff1a;商品列表 MyTag组件封装MyTable组件封装 4.路由入门 单页应用程序路由VueRouter的基本使用 …
阅读更多...
张量之力：人工智能的多维舞台

张量之力：人工智能的多维舞台

在人工智能&#xff08;AI&#xff09;的广阔天地里&#xff0c;张量&#xff08;Tensor&#xff09;这一数学概念如同璀璨的明星&#xff0c;以其独特的魅力和强大的功能&#xff0c;为AI技术的发展和应用注入了新的活力。张量&#xff0c;这个源自物理学的概念&#xff0c;如…
阅读更多...
day32--Spring（一）

day32--Spring（一）

一、Spring简介 1 Spring课程介绍 问题导入 我们为什么要学习Spring框架&#xff1f; 1.1 为什么要学 Spring技术是JavaEE开发必备技能&#xff0c;企业开发技术选型命中率>90% 专业角度 简化开发&#xff0c;降低企业级开发的复杂性框架整合&#xff0c;高效整合其他技…
阅读更多...
浅谈安全用电管理系统对重要用户的安全管理

浅谈安全用电管理系统对重要用户的安全管理

1用电安全管理的重要性 　　随着社会经济的不断发展&#xff0c;电网建设力度的不断加大&#xff0c;供电的可靠性和供电质量日益提高&#xff0c;电网结构也在不断完善。但在电网具备供电的条件下&#xff0c;部分高危和重要电力用户未按规定实现双回路电源线路供电&#xff1…
阅读更多...
最新文章

Copyright @ 2022~2023