从零开始学Python-day3
Python--Day3学习要有定位,明确目标地去学习。---leaves
python02---list知识
一 list的概念
列表的概念：列表可以完成大多数集合类的数据结构实现。它支持字符，数字，字符串甚至可以包含列表（所谓嵌套)。
listarray数组 是同一种数据
list的优点：
可遍历
有序的
可以切片
快速生成list的方法： range(数字) list("字符串")
##列表中可以嵌套任意类型的数据
In : arr = ['C',1,2,True,False,],'python']
##range()快速生成list
In : arr = range(10)
In : arr
Out:
##list()快速生成list
In : arr1 =list('python')
In : arr1
Out: ['p', 'y', 't', 'h', 'o', 'n']
##可以通过索引获取值
In : arr
Out: ]
##索引值也能为负值
In : arr[-1]
Out: 'python'
##in判断元素是否在list中
In : arr1
Out: ['p', 'y', 't', 'h', 'o', 'n']
In : 'x' in arr1
Out: False
In : 'p' in arr1
##小练习自己实现in的功能
In : result = 0#用来存放判断后的结果
In : for i in arr1 :
...: if 'x' == i:
...: result = "True"
...: result = "False"
...: print result
...:
...:
False
二、list的方法(主要针对数字)
len() ====>list长度
max() ====>list 最大值
min() ====>list最小值
del() ====>删除索引值
列表可以使用'+'拼接和使用'*'重复
###del 用法 ==直接删除值
In : arr
Out: ['C', 1, 2, True, False, ], 'python']
In : del arr
In : arr
Out: ['C', 2, True, False, ], 'python']
##list 可以使用+拼接
In : l1 = ['c','d']
In : l2 = ['1',2]
In : l1 + l2
Out: ['c', 'd', '1', 2]
##list 可以使用+拼接
In : l1 = ['c','d']
In : print l1 * 2
Out: ['c', 'd','c','d']
##list修改值 ==>直接修改
In : l1 = ['c','d']
In : l1="hello"
In : l1
Out: ['c', 'hello']
三、排序
排序：编程世界的游戏规则。
各种排序算法的演示动画网址(民族舞蹈讲述排序)：
http://www.bilibili.com/video/av4722429/index_5.html
各种算法的动画演示(http://www.atool.org/sort.php)
3.1 冒泡排序
冒泡排序的原理：相邻两个元素挨个对比,如果一个元素比右边大,则交换位置。
冒泡排序过程如下：
arr =
第一次3和5比 不变
5和1比 交换
5和32比 不变
32和4比交换
第二次 在基础上
3 和1 比较交换
3 和5 比较不变
5 和4 比较交换
第三次在 基础上
1和3比较不变
3和4比较不变
第四次
1 和 3 比较不变
最终的冒泡排序代码如下：
# cat maopao.py
arr =
print arr
length = len(arr)
print length
for j in range(length-1):
print "di %s ci xun huan :" %j
for i in range(length-1-j):
if arr > arr:
arr,arr = arr,arr
print arr
print "The final result is %s" % arr
# python maopao.py
6
di 0 ci xun huan :
di 1 ci xun huan :
di 2 ci xun huan :
di 3 ci xun huan :
di 4 ci xun huan :
The final result is
#
3.2 选择排序
选择排序原理：拿一个元素分别与剩下的元素对比,选出最小或最大的
###选择排序实现代码如下：
# cat xuanze.py
arr =
print "The sortedarris : %s" % arr
l = len(arr)
print l
for i in range( l-1 ):
print "di%s ci xuanze paixu " %i
#jiang a qu chu laifen bie yuhoubian bijiao
for j in range(i+1,l):
if arr > arr:
arr ,arr = arr,arr
print arr
print "*" * 40
print arr
# python xuanze.py
The sortedarris :
5
di0 ci xuanze paixu
di1 ci xuanze paixu
di2 ci xuanze paixu
di3 ci xuanze paixu
****************************************
#
3.3 算法扩展
算法的复杂度： 算法两方面：1复杂度 2.稳定性
复杂度分为时间复杂度和空间复杂度
冒泡排序==>复杂度o（n^2）稳定性高
希尔排序 ===>复杂度不知道。目前还无法算出来
3.4 插入排序
插入排序的原理：是通过构建有序序列,对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序图解：
小知识：如何利用range()使list倒序：
In : for i in range(3,0,-1):
...: print i
...:
...:
3
2
1
插入排序代码(加深理解)
# cat test.py
def InsertSort(mylist):
size = len(mylist)
i = 1
for i in range(1, size):
print "===================================di %s ci xun huan ======================="% i
print "mylist=== mylist : %s == %s"%(mylist,mylist)
if mylist < mylist:
tmp = mylist
j = i - 1
print "****j : %s" %j
mylist = mylist
j = j - 1
while j >= 0 and mylist > tmp:
mylist = mylist
j = j - 1
mylist = tmp
#mylist0 =
mylist0 =
InsertSort(mylist0)
print(mylist0)
# python test.py
===================================di 1 ci xun huan =======================
mylist=== mylist : 5 == 6
****j : 0
===================================di 2 ci xun huan =======================
mylist=== mylist : 3 == 6
****j : 1
===================================di 3 ci xun huan =======================
mylist=== mylist : 1 == 6
****j : 2
===================================di 4 ci xun huan =======================
mylist=== mylist : 8 == 6
===================================di 5 ci xun huan =======================
mylist=== mylist : 7 == 8
****j : 4
===================================di 6 ci xun huan =======================
mylist=== mylist : 2 == 8
****j : 5
===================================di 7 ci xun huan =======================
mylist=== mylist : 4 == 8
****j : 6
#
四、list的切片
list的切片：切片功能强大,可读性差。主要用于获取连续数据
切片的原则：起点按照切片方向上的找到终点
list的具体切片小例子：
Out:arr =
In : arr[:4]
Out:
In : arr
Out:
In : arr[::2]
Out:
In : arr[::-1]
Out:
切片可以删除list元素
In : arr = ['a']
In : arr
Out:
##增加元素
In : arr = ['1','2','3']
In : arr
Out:
五、list的其他常用方法
append() 追加元素
count() 统计list中某个元素出现的次数
extend() 没有返回值,修改原数组
index() 没有返回值,查找某个元素的索引
insert(1,'value')在index出插入值value
pop() 弹出,默认弹出最后一个值,返回
remove() remove(value)删除具体值
reverse() 反向list
list 其他常用方法的举例
##append举例
In : arr =
In : arr.append('!')
In : arr
Out:
##count的使用
In : arr =
In : arr.count(1)
Out: 2
##extend的使用
In : arr1 =list('python')
In : arr2 = range(2)
In : arr1.extend(arr2)
In : arr1
Out: ['p', 'y', 't', 'h', 'o', 'n', 0, 1]
##index的使用
In : arr1
Out: ['p', 'y', 't', 'h', 'o', 'n', 0, 1]
In : arr1.index(0)
Out: 6
In : arr1.index('p')
Out: 0
##insert的用法
In : arr2
Out:
In : arr2.insert(1,'hello')
In : arr2
Out:
###pop()默认删除最后一个,也可以提供一个索引值弹出指定元素
In : arr2
Out:
In : arr2.pop()
Out: 1
In : arr2.pop(0)
Out: 0
In : arr2
Out: ['hello']
六、队列和桟
队列:先入先出===>append()和pop(0)
桟 : 先入后出===>append()和pop()
小练习：
#采用持续队列,让用户输入东西：
如果用户输入的是add
再让用户输入一件事情(吃饭)
如果用户输入的是do
把之前输入的值打印出来。
如果没事情可做,就打印nothing
如果输入的是其他值,则终止循环
具体代码如下：==>对应先入后出的思想
# cat 01.py
store = []
while True:
x = raw_input("qing shu ru action: ")
if x == "add":
y = raw_input("qing shu ru thing: ")
store.append(y)
print store
elif x == "do":
print "****do "
print len(store)
if len(store) != 0:
print store.pop() ##先入后出思想。
##先入先出思想。pop(0)
else:
print "nothing"
else :
print "The final result is %s" %store
break
###执行代码过程如下：
# python 01.py
qing shu ru action: add
qing shu ru thing: 111
['111']
qing shu ru action: add
qing shu ru thing: 222
['111', '222']
qing shu ru action: do
****do
2
222
qing shu ru action:
The final result is ['111']
七、数组、链表
数组1,2,3,4,5
优点： 根据索引寻找比较快,从最后追加也特别快.命中CPU缓存概率比较大
缺点:插入很慢, 删除也很慢。(插入的话,后边元素要依次往后移)
链表：1 ---> 2----> 3 ---->4 --->5
链表的查找很慢,插入很快,删除也很快。尾部追加也很快
哈希表d = {"name": "hello"}复杂度O(1)
复杂度为O(1),可以通过具体的值来建立关系(python的dict)
本身没有顺序,查找,删除,修改都很快key ===>var1
FNV哈希
MD5哈希
一致性哈希
八‘list与dict的区别
list 和dict的区别
相同：都可以存储复杂的数据结构,可以嵌套列表、字典等
不同：
list是有序的,通过index索引值来获取元素,赋值。删除,增加值
dict是无序的,key-value的键值对。通过key来获取value的值。
延伸
dict 和 json的区别
dict是Python中具体的数据结构
json：是一种数据交换格式(标准)json数据
九、练习：
###练习1 ：数组去重：
###小练习：
In : arr =
In : arr_1= []
In : for i in arr:
...: if i in arr_1:
...: pass
...: else:
...: arr_1.append(i)
...: print arr_1
...:
###小练习2
###arr1 =
###arr2 =
###求arr1和arr2的交集
In : arr1 =
In : arr2 =
In : arr_r = []
In : for i in arr1:
...: if (i in arr2) and (i not in arr_r):
...: arr_r.append(i)
...: print arr_r
...:
十、二分思想找到range(100000)中任意一个数字
二分思想：一个排好的list中,找到指定数字。
arr = range(10000)
x = raw_input("qing shuru yi ge shuzi ")
start = 0
end = len(arr)-1
count = 0
while True :
count += 1
half = ( start + end )/2
if int(x) > arr:
start = half
elif int(x) < arr:
end = half
else :
print "The index value is %s" %half
break
print "Total found%s times " %count
页:
[1]