文档章节

数据结构与算法之线性结构

SEOwhywhy
 SEOwhywhy
发布于 03/06 20:49
字数 3043
阅读 15
收藏 0

什么是数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系的组成。

  • 数据结构就是设计数据以何种方式存储在计算机中,列表、字典等都算是数据结构。

  • 程序=数据结构+算法,数据结构属于静态的部分,算法的调用为动态部分

数据结构的分类

根据逻辑结构划分:

  • 线性结构:数据结构中的元素一对一的关系,一前驱,一后继。
  • 树结构:数据结构中元素一对多的关系,一前驱,多后继。
  • 图结构:数据结构中元素存在多对多的关系,多前驱,多后继,我也不会。
    • 判断一个图形能不能一笔画完,就判断它的奇数度节点数目是否为0或2.这种能一笔画完的就是欧拉图,奇数度节点为四个,就是两笔画完。

线性结构

列表

列表和数组

python中的列表和其他语言中的数组很相似,区别为:

  • 数组是定长的。
  • 数组的数据类型也必须一致。
  • 对列表或数组来说,它们的下标操作是最快的。

列表解决的变长问题的方式

  • 假设一开始在内存中分配了四个元素存储的空间,那么前四个元素的append操作不会出现问题。
  • 当第五次append操作时,会先在内存中分配一个能够存储八个元素的空间,也就是翻倍。
  • 然后进行复制,把以前的四个元素依次放到相应的位置上。
  • 若再次超出长度,则继续执行上述操作。
  • 也就是使用了动态表的原理

append操作会不会使速度变慢?

  • 根据摊还分析,没有变长时的append和变长时的append均摊,最后的复杂度时O(3).
  • append越往后,变长时的出现频率就会越小
  • 浪费了一部分空间,最坏情况应该是浪费了长度除二减一的空间。

列表解决多数据类型问题的方式

  • 对于纯整数的数组,它的每一个元素占4个字节,那么就事先计算好内存分配的大小,计算方法为:- 第一个元素的地址+元素个数 乘 4
  • python的列表里存的不是值,而是指向这个值的内存地址。
  • 地址的大小是一样的,32位里地址是4个字节,64位里地址是8个字节。
  • 这种方法的缺点是内存开销翻倍,这也是python被人诟病的地方。

相关知识点

总是能听到一个词 堆栈 ,堆(heap)和栈(stack)是两个东西,传统的编程语言中把内存分为两个地方,堆空间和栈空间,堆存储的是一些动态生成的对象,与数据结构中的堆是不同的,栈空间由系统调用,存放函数的参数值,局部变量的值。
应该是早年间翻译的问题,一般听到堆栈指的就是栈。

  • 栈是一个数据集合,可以理解为只能在一端进行插入和删除操作的列表。
  • 栈的特点:后进先出(last-in,first-out)
    • 栈顶:操作永远在栈顶。
    • 栈底:最后一个元素。
  • 栈的基本操作:
    • 进栈(压栈):push
    • 出栈:pop
    • 取栈顶: gettop
  • 关于出栈顺序的问题:
    • 对于某个元素,如果进展顺序在它前面的元素出栈时在它后面,那么前面的元素顺序是相反的。
    • 不知道说的明不明白
    • 卡特兰数,n个数的出栈顺序,就是卡特兰数的第n项。

栈的应用--括号匹配问题

  • 给定一个字符串,问其中字符串是否匹配。
  • 括号本身满足栈的性质
  • 匹配失败的情况:
    • 括号不匹配
    • 匹配完毕栈没空
    • 栈空了又进元素
     
    1. def brace_match(s):

    2. stack = []

    3. d ={'(':')','[':']','{':'}'}

    4. for ch in s:

    5. if ch in {'(','[','{'}:

    6. stack.append(ch)

    7. elif len(stack):

    8. print('多了%s' %ch)

    9. return False

    10. elif d[stack[-1]] == ch:

    11. stack.pop()

    12. else:

    13. print('%s不匹配'%ch)

    14. if len(stack)==0:

    15. return True

    16. else:

    17. print("未匹配")

    18. return False

队列

相关知识点:

队列是一个数据集合,仅允许在列表的一端插入,另一端删除。

  • 进行插入的时队尾,进行删除操作的是队首,插入和删除操作也被称为进队(push)和出队(pop)。
  • 队列的性质:先进先出(first-in,first-out)
  • 双向队列:两边都能进行插入删除操作的队列。

队列的数组实现:

  • 简单的pop(0)操作复杂度过高,不采用。
  • 由于数组定长,不能继续添加数据,如果是列表,出队的操作就会出现空位,所以想办法让数组变成一个圆环。

  • 设置两个指针,队首指针front,队尾指针rear。
  • 由于,队列满的时候和队列空的时候rear和front都在一个位置,那么就无法判断了。于是设置成队列满的时候减去一做为队满的标志。
  • 这种队列就叫做环形队列。
    • 当队尾指针front=最大长度+1时,再前进一个位置就自动到0.
    • 实现方式:求余数运算
      • 队首指针前进1:front=(www.tiaotiaoylzc.com front+1)%maxsize
      • 队尾指针前进1:rear=(www.yongshi123.cn rear+1)%maxsize
      • 队空条件:rear=www.yongshiyule178.com front
      • 队满条件:(rear+1)www.dfgjpt.com%maxsize=front

通过两个栈做一个队列的方法

  • 1号栈进栈 模拟进队操作。
  • 2号站出栈,如果2号栈空,把1号站依次出栈并进2号栈,模拟出队操作。
  • 通过摊还分析,时间复杂度还是O(1)。

python关于队列的模块

 
  1. import queue #涉及线程安全用queue

  2. from collections import deque #常用解题的用deque

  3.  
  4. q = deque() #是一种双向队列,popleft出队

  5.  
  6. #模拟linux命令 head和tail,假如是tail 5

  7. deque(open('a.text','r',encooding='utf8'),5)

  8. #建立一个定长的队列,当队列满了之后,就会删除第一行,继续添加

链表

相关知识点:

链表就是非顺序表,与队列和栈对应。

  • 链表中每一个元素都是一个对象,每个对象称为一个节点,包含有数据域key和指向下一个节点的next,通过各个节点之间的相互连接,最终串联成一个链表。

  • 在机械硬盘中,文件就是以链表的形式存储的。
  • 以FAT32为例,文件的单位是文件块(block),一个文件块的大小是4k,一个文件的内容是由链表的方式连接文件块组成的。
  • 链表的第一个节点被称为头节点,数据可以是空的,也可以有值。
  • 头节点为空也是为了表示空链表,也叫做带空节点的链表,头节点也可以记录链表的长度

节点定义

 
  1. class Node(object):

  2. def __init__(self,item):

  3. self.item=item

  4. self.next=None

  5. #eg

  6. a=Node(1)

  7. b=Node(2)

  8. c=Node(3)

  9. a.next=b

  10. b.next=c #链表的最后一个节点的next就为None

链表类的实现

 
  1. class LinkList:

  2. def __init___(self,li,method='tail'):

  3. self.head = None

  4. self.tail = None

  5. if method == 'head':

  6. self.create_linklist_head(li)

  7. if method == 'tail'

  8. self.create_linklist_tail(li)

  9. else:

  10. rais ValueError('unsupport')

  11.  
  12. #头插法

  13. def create_linklist_head(self,li):

  14. self.head = Node(0)

  15. for v in li:

  16. n = Node(v)

  17. n.next = l.next #当插入下一个元素时,应该与下一个节点连接后再跟头节点连接

  18. self.head.next = n

  19. self.head.data += 1

  20.  
  21. #尾插法

  22. def create_linlist_tail(self,li):

  23. self.head = Node(0)

  24. self.tail = self.head

  25. for v in li:

  26. p = Node(v)

  27. self.tail.next = p

  28. self.tail = p

  29. self.head.data += 1

  30.  
  31. #链表的遍历输出

  32. def traverse_linlist(self):

  33. p = self.head.next

  34. while p:

  35. yield p.data

  36. p = p.next

插入删除总结

  • 插入
 
  1. #p表示待插入节点,curNode表示当前节点

  2. p.next = curNode.next #不能当前连接直接断开

  3. curNode,next = p

  • 删除
 
  1. p = curNode.next

  2. curNode.next = p.next

  3. del p #不写也一样,引用计数,python的内存回收机制

双链表

双链表中每个节点有两个指针:一个指向后面节点、一个指向前面节点。
节点定义:

 
  1. class Node(object):

  2. def __init__(self, item=None):

  3. self.item = item

  4. self.next =www.myzx1.com None

  5. self.prior = None

双链表的插入和删除

  • 插入
 
  1. p.next = curNode.next

  2. curNode.www.ycjszpgs.com next.prior = p

  3. p.prior =www.dfzx157.com curNode

  4. curNode.next = p

  • 删除
 
  1. p = curNode.next

  2. curNode.next = p.next

  3. p.next.prior = curNode

  4. del p

链表的复杂度分析

链表与列表相比

  • 按元素值查找:列表可以使用二分法是O(logn),链表是O(n)
  • 按下标查找:O(1),O(n)
  • 再某元素后插入:O(n),O(1)
  • 删除莫元素:O(n),O(1)
    总的来说链表再插入和删除某元素的操作时明显快于顺序表,而且通过双链表可以更容易实现栈和队列。

哈希表

直接寻址表

哈希表就是直接寻址表的改进。当关键字的全域U比较小时,直接寻址是一种简单有效的方法。

  • 全域的意思就是它的取值范围。
  • 也就是直接把关键字为key的value放在key的位置上
    直接寻址的缺点:
  • 当域U很大时,需要消耗大量内存。
  • 如果U很大,但关键字很少,浪费大量空间。
  • 若关键字不是数字则无法处理。
    直接寻址表的改进:
  • 构建大小为m的寻址表T
  • key为k的元素放到h(k)上
  • h(k)是一个函数,其将域U映射到表T(0,1,..,m-1)

哈希表

哈希表是一个通过哈希函数计算数据存储位置的线性表的存储结构,又叫做散列表。

  • 哈希表由一个直接寻址表和一个哈希函数组成。
  • 哈希函数h(k)将元素关键字k作为自变量,返回元素的存储下标。
  • 哈希表的基本操作:
    • insert(key,value):插入键值对。
    • get(key):如果存在键为key的键值对则返回其value。
    • delete(key):删除键为key的键值对。

简单哈希函数

  • 除法哈希:h(k)= k mod m
  • 乘法哈希:h(k) = floor(m(KA mod 1)) 0<A<1

哈希冲突

由于哈希表的大小是有限的,而要存储信息的数量是无限的,因此,对于任何哈希函数,都会出现两个元素映射到同一个位置的情况,这种情况就叫做哈希冲突。
解决哈希冲突的方法:
开放寻址法:如果哈希函数返回的位置已经有值,则可以向后探查新的位置来储存这个值。

  • 线性探查:如果位置p被占用,则探查 p+1,p+2....
  • 二次探查:如果位置p被占用,则探查p+1**2,p-1**2,p+2**2
  • 二度哈希:有n个哈希函数,当使用第一个哈希函数h1发生冲突时,则使用h2。
  • 哈希表的快速查找可以以空间换时间,需要保证元素个数除以数组容积小于0.5,这个比值就是装载率。
    拉链法:哈希表的每个位置都连接一个链表,当冲突发生时,冲突的元素被加到该位置链表的最后。
  • 拉链表需要保证每一个链表的长度都不要太长。
  • 拉链法的装载率是可以大于一的。
  • 插入、查找等操作的时间复杂度是O(1)的。

哈希在python中的应用

  • 字典和集合都是通过哈希表来实现的
  • 集合可以看作没有value的字典,因为集合也有不重复的性质。
  • 通过哈希函数把字典的键映射为函数:
 
  1. dic = {'name':'cui'}

  2. #可以认为是h('name')=1,则哈希表为[None,'cui

© 著作权归作者所有

SEOwhywhy
粉丝 8
博文 155
码字总数 342404
作品 0
私信 提问
数据结构基本概念 - 学习笔记

数据结构基本概念 1 数据:数据是用来描述现实世界的数字、字符、图像、声音,以及能够输入到计算机中并能被计算机处理的符号集合 2 数据元素:数据元素是数据的基本单位,在计算机中通常作为...

wqli
2012/09/22
73
0
数据结构

算法,解决问题之道,各行各业,各门各类均有其固有的难题,而解决问题之道大不相同,社会学,历史学,计算机学,金融学,国学,天文学问题虽不同,但其思维方式却是相通的。 古有筹策论,今...

HappyBoyLi
2016/03/04
0
0
第一阶段:Java内功秘籍-线性表

前言 为什么要学习数据结构与算法,如果你学会了做安卓,javaweb,前端等,都是你的武功秘籍,但是如果你的内功不够好,再厉害的功夫也是白费。 数据结构和算法:什么是数据结构,什么是数据...

达叔小生
2018/08/06
0
0
利用线性表的顺序结构求集合的并、交、差、补(C语言实现)

昨天用数据结构中的线性表的顺序结构实现了关于集合的并、交、差、补的集合运算,做个记录,希望也能帮助到其他人。 一、算法分析   (1)用数组A,B,C,E表示集合。假定A={1,3,4,5,6...

Tim_JX
2014/03/24
11.7K
0
数据结构和算法-C语言篇-绪论

数据结构与算法目录 前言 程序设计 = 数据结构 + 算法 什么是数据结构? 数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。 简单来说数...

香沙小熊
2017/12/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins World 贡献者峰会及专家答疑展位

本文首发于:Jenkins 中文社区 原文链接 作者:Marky Jackson 译者:shunw Jenkins World 贡献者峰会及专家答疑展位 本文为 Jenkins World 贡献者峰会活动期间的记录 Jenkins 15周岁啦!Jen...

Jenkins中文社区
22分钟前
6
0
杂谈:面向微服务的体系结构评审中需要问的三个问题

面向微服务的体系结构如今风靡全球。这是因为更快的部署节奏和更低的成本是面向微服务的体系结构的基本承诺。 然而,对于大多数试水的公司来说,开发活动更多的是将现有的单块应用程序转换为...

liululee
36分钟前
6
0
OSChina 周二乱弹 —— 我等饭呢,你是不是来错食堂了?

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @ 自行车丢了:给主编推荐首歌 《クリスマスの夜》- 岡村孝子 手机党少年们想听歌,请使劲儿戳(这里) @烽火燎原 :国庆快来,我需要长假! ...

小小编辑
今天
355
8
玩转 Springboot 2 之热部署(DevTools)

Devtools 介绍 SpringBoot 提供了热部署的功能,那啥是热部署累?SpringBoot官方是这样说的:只要类路径上的文件发生更改,就会自动重新启动应用程序。在IDE中工作时,这可能是一个有用的功能...

桌前明月
今天
5
0
CSS--列表

一、列表标识项 list-style-type none:去掉标识项 disc:默认实心圆 circle:空心圆 squire:矩形 二、列表项图片 list-style-img: 取值:url(路径) 三、列表项位置 list-style-position:...

wytao1995
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部