下面我们通过一个问题来简单介绍数据结构
问题:用Python来保存一个班级的学生信息,要求有一下内容,name , age, hometown。
1、用列表实现:
[
("zhangsan", 24, "beijing")
("lisi", 24, "beijing")
("wangwu", 24, "beijing")
]
如果想取出张三的时候是:
for stu in stus:
if stu(0) == "zhangsan"
需要遍历每一个列表中的值,这样的时间复杂度是O(n)。
2、用散列表,在Python中就是字典来存储
{
'zhangsan':{'age':24, 'hometown':'beijings'},
'lisi':{'age':24, 'hometown':'beijings'},
'wangwu':{'age':24, 'hometown':'beijings'}
}
这时我们取出其中的张三,
stus['zhangsan']
可以直接通过键取出对应的值,时间复杂度为O(1)。
所以,存储同样的数据,使用列表和字典会对你访问数据时候的便捷度产生了不同的结果。
简单介绍内存知识
内存: 真正存储数据并跟CPU打交道的地方
内存是一个连续的存储空间,就像进出超市时候的储物柜,你存个东西,会给你一个小票,这个小票就是寻找你这个储物柜的地址,你通过这个地址来访问这个储物柜。
比如:
0x03 | 0x04 | 0x05 |
0x06 | 0x07 | 0x08 |
0x09 | 0x10 | 0x11 |
当然,现实中的内存地址比这个长的多。
总结:
算法是解决问题的思路, 数据结构是解决的数据是以什么样的方式存在的。
程序 = 数据结构 + 算法