数据结构知识点(list,tuple,冒泡法)

分类

  • 数值型
    int、float、complex、bool
  • 序列对象
    字符串str、列表list、tuple
  • 键值对
    集合set、字典dict

数值型

  • complex:有实数和虚数部分组成
  • float:有整数和小数组成。只有双精度

类型转换

  • int(X) 返回一个整数
  • float(x) 返回一个浮点数
  • complex(x)、complex(x,y) 返回一个复数
  • bool(x) 返回布尔值

数字的处理函数

  • round() 四舍六入五取偶
    数据结构知识点(list,tuple,冒泡法)
  • floor() 地板,往下取
    ceil() 天花板,往上取
    数据结构知识点(list,tuple,冒泡法)
  • min()
    max()
    pow(x,y) 等于x**y
    math.sqrt()
  • 进制函数
    bin()
    oct()
    hex()
  • math.pi π
    math.e 自然常数e

类型判断

  • type(obj),返回类型,而不是字符串
  • isinstance(obj,class_or_tuple),返回布尔值
  • 示例
    数据结构知识点(list,tuple,冒泡法)

列表list

  • 特点
    sequence
    item (could be anything)
    线性的数据结构
    列表是可变
    使用[]表示
  • 定义
    list(iterable) -> new list initialized from iterable’s items

索引,也叫下标

  • 正索引:从左至右,从0开始,为列表中每一个元素编号
  • 负索引:从右至左,从-1开始
  • 正负索引不可以超界
  • 左边是头部,右边是尾部,左边是下界,右边是上界
  • 列表通过索引访问
    list[index],index就是索引,使用中扩号访问

列表查询

  • index(value,[start,[stop]])
    通过值value,从指定区间查找列表内的元素是否匹配
    匹配第一个值就立即返回索引
  • count(value)
    返回列表中匹配value的次数
  • 时间复杂度
    index和count都是O(n)
    随着列表数据规模越大,效率越低
  • len()
    获得list元素的个数

列表基本操作

  • list[index] = value
  • append(obj) -> None
    尾部追加元素,返回None
    就地修改
    时间复杂度O(1)

    lst=[2,3]
    lst.append(1)
    
  • insert(index,object) ->None #很少用到
    超越上界,尾部追加
    超越下届,头部追加
  • extend(iteratable) -?None
    将可迭代对象的元素追加进来,返回None,就地修改
  • + ->list
    将两个列表连接起来,产生新的列表
  • * ->list
    重复操作,将本列表元素重复n次,返回新的列表
    数据结构知识点(list,tuple,冒泡法)
    # a=[[1]]*3只是复制了引用(门牌号),当对三者中任何一个发生改变,其他两个也会相应的改变
    # b=[[1],[1],[1]]里面就是不同的三个引用

  • remove(value) -> None
    从左至右查找第一个匹配value的值,移除该元素,返回None
    就地修改 #用的比较少,一般用pop
  • pop(index) ->item
    不指定索引index,就从列表尾部弹出一个元素
  • clear() ->None
    清楚列表所有元素,剩下一个空列表
  • reverse() ->None
    将列表元素反转
  • sort(key=None,reverse=False) ->None
    对列表元素进行排序,就地修改,默认升序
    reverse为True,反转,降序
    key为一个函数,指定key按照什么规则排序
  • in
    [3,4] in [1,2,[3,4]]
    for x in [1,2,3,4]

列表复制

  • copy() -> list

数据结构知识点(list,tuple,冒泡法)

  • shadow copy
    浅拷贝,遇到引用类型,只是复制了一个引用而已(记下了门牌号)
    数据结构知识点(list,tuple,冒泡法)
  • 深拷贝
    import copy
    lst=[1,2,[3,4],5]
    lst1=copy.deepcopy(lst)
    lst[2][1]=20
    lst==lst1,lst is lst1
    

    数据结构知识点(list,tuple,冒泡法)


随机数

  • random模块
  • randint(a,b) 返回[a,b]之间的整数
  • choice(seq) 从非空序列的元素中随机挑选一个元素,比如random.choice(range(10))
  • randrange 从集合中获取一个号随机数
    random.randrange)(1,7,2)
  • random.shuffle(list) ->None
    就地打乱列表元素

注意

  • 列表list用for循环进行遍历的时候,会出错,不建议这样使用
    • 例1
      数据结构知识点(list,tuple,冒泡法)
    • 例2 ,利用index来遍历删除
      数据结构知识点(list,tuple,冒泡法)
      这样虽然删除了,但是列表l变成l=[1,2,3,4,5],就报错了
      数据结构知识点(list,tuple,冒泡法)
      range的开始范围是0-4,中间遍历的时候删除了一个元素4,这个时候列表就变成了l=[1,2,3,5],这时候就会报错了,提示超界,原因就是遍历的时候删除了元素

tuple 元组

  • 特点
    一个有序的元素组成的集合
    使用()表示
    不可变对象

    • 元组是只读的,增、改、删都没有
  • 定义
    tuple(iterable) -> tuple initialized from iterable’s items

    t=tuple()
    t=(1,2,3,4)
    t=(1,)  #一个元素定义必须有逗号
    

索引

  • 知识点同list
  • 元组通过索引访问
    tuple[index],index就是索引,使用中扩号访问

    t[-1]=4
    

查询

  • 查询同list
  • 主要记住 len(tuple)

命名元组namedtuple

  • namedtuole(typename,field_names,verbose=False,rename=False)
    • 命名元组,返回一个元组的子类,并定义了字段
    • field_names可以是空格或逗号分割的字段的字符串,可以是字段的列表

数据结构知识点(list,tuple,冒泡法)


冒泡法

  • 交换排序
  • 第一轮比较,需要比较n-1次,第二轮是n-2次,以此类推,最后只剩下两个数比较
  • 最差的排序情况是,初始顺序与目标顺序完全相反,遍历次数就是n-1,……,1的和n(n-1)/2
    • 例如[4,3,2,1]要求升序排序[1,2,3,4]
  • 最好的排序情况是,初始顺序与目标顺序相同,遍历n-1次
  • 时间复杂度O(n²)

  • 简单冒泡法实现
    numlist = [[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9]]
    nums = numlist[1]
    print(nums)
    length = len(nums)
    count_swap = 0 
    count = 0
    
    for i in range(length):
        for j in range(length-i-1):
            count += 1
            if nums[j] > nums[j+1]:
                tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
                count_swap += 1
    print(nums,count_swap,count)
    
    #  count_swap是为了查看交换的次数
    #  count是为了查看进行了多少次比较(包括没有交换的比较)
    

  • 优化版(错误示范)
    numlist = [[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,9,8]]
    nums = numlist[1]
    print(nums)
    length = len(nums)
    count_swap = 0
    count = 0
    flag=False        
    
    for i in range(length):
        for j in range(length-i-1):
            count += 1
            if nums[j] > nums[j+1]:
                tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
                flag = True
                count_swap += 1
        if not flag:
            break
    print(nums,count_swap,count) 
    

    数据结构知识点(list,tuple,冒泡法)

    #  flag=Flash放错位置了,放在最上面不起作用,只有放在for i循环下面才起作用。
    #  如果for j的第一次循环没有比较的话(也就是123456789这样的排序),那么这次循环后就会结束,其他的情况都是在第一次循环会进行比较交换,也就是执行了if语句,那么flag就变成了True,这样在后面的循环中,哪次循环没有比较才会break。
    #  这样大大提高了效率
    

  • 优化(正确) *****记住
    numlist = [[1,9,8,5,6,7,4,3,2],[1,2,3,4,5,6,7,8,9],[1,2,3,4,5,6,7,9,8]]
    nums = numlist[1]
    print(nums)
    length = len(nums)
    count_swap = 0
    count = 0
    
    for i in range(length):
        flag = False
        for j in range(length-i-1):
            count += 1
            if nums[j] > nums[j+1]:
                tmp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = tmp
                flag = True
                count_swap += 1
        if not flag:
            break
    print(nums,count_swap,count)
    

    数据结构知识点(list,tuple,冒泡法)

本文来自投稿,不代表Linux运维部落立场,如若转载,请注明出处:http://www.178linux.com/87559

(0)
nolannolan
上一篇 2017-09-24 23:34
下一篇 2017-09-25

相关推荐

  • vim编辑器的常见使用

    1、vim介绍 Vim是从 vi 发展出来的一个文本编辑器,处理文本文件功能强大。 三种主要模式: Vim打开文件,默认命令(Normal)模式,可以移动光标,剪切和粘贴。 按键i 进入插入(Insert)模式,用户可以编辑文本。 扩展(Extended)命令模式(或末行模式)用户:wq可保存退出,或者:q!强制退出。 Exc按键可退出当前模式。 2、文本操…

    Linux干货 2017-07-30
  • Homework Week-7 RAID及bash编程

    1、创建一个10G分区,并格式为ext4文件系统;    (1) 要求其block大小为2048, 预留空间百分比为2, 卷标为MYDATA, 默认挂载属性包含acl;    (2) 挂载至/data/mydata目录,要求挂载时禁止程序自动运行,且不更新文件的访问时间戳; fdisk /dev/sda n …

    Linux干货 2016-09-26
  • 最简单的Linux系统——更加深入了解Linux启动过程

    自制一个最简单的Linux: 1、有一个新的磁盘,并创建分区 2、挂载分区,创建目录 3、拷贝内核文件 4、创建MBR和grub.conf文件 5、创建/etc/fstab文件,设置开机自动挂载 6、拷贝一个bash程序 7、卸载分区,以新磁盘重启系统

    Linux干货 2016-09-11
  • rpm包管理(二)

    查询查询库文件包查询[select-options][query-options]licdR常用的查询用法:卸载:二进制文件的恢复包效验使用rpm命令导入公钥(KEY文件)验证rpm包来源(光盘)的来源及完整性检查包安装后生成的文件,是否发生过变动RPM包管理器的数据库如果某个rpm相关内容被删除如果rpm命令的包被删除了信息库被删除了删除/usr/bin下…

    Linux干货 2016-09-19
  • 一起学DNS系列(十四)DNS查询工具之DIG的使用(1)

      这几节主要讲2个常用的DNS的命令行诊断工具,分别是linux下的DIG和windows下的NSLOOKUP,我们首先来说DIG工具。 DIG,全称Domain Information Groper。原本是Linux平台上BIND服务器诊断的工具(已上传至附件),现在已经有了windows的版本,这节就是利用此工具在windows环境下来做一些…

    2015-03-17
  • OpenSSL

    一、什么是OpenSSL 在电脑网络上,OpenSSL是一个开放源代码的软件库包,应用程序可以使用这个包来进行安全通讯,避免窃听,同时确认另一端连接者的身份。这个包广泛被应用在互联网的网页服务器上。其主要库是以C语言所写成,实现了基本的加密功能,实现了SSL与TLS协议。 OpenSSL由三部分组成:     libencryp…

    Linux干货 2016-04-25