本文目录：
 

 
 
数据结构分类
1、数组
2、栈
3、队列
4、链表
5、树
6、散列表
7、堆
8、图
 
 
 
数据结构分类
 
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 
 常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示： 
  
 每一种数据结构都有着独特的数据存储方式，下面为大家介绍它们的结构和优缺点。
 
1、数组
 
数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。
 
int[] data = new int[100]；data[0]  = 1;
 
优点： 
 1、按照索引查询元素速度快 
 2、按照索引遍历数组方便
 
缺点： 
 1、数组的大小固定后就无法扩容了 
 2、数组只能存储一种类型的数据 
 3、添加，删除的操作慢，因为要移动其他的元素。
 
适用场景： 
 频繁查询，对存储空间要求不大，很少增加和删除的情况。
 
2、栈
 
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。 
  
 栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
 
3、队列
 
队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下： 
  
 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用。
 
4、链表
 
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。 
  
 链表的优点： 
 链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素； 
 添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
 
缺点： 
 因为含有大量的指针域，占用空间较大； 
 查找元素需要遍历链表来查找，非常耗时。
 
适用场景： 
 数据量较小，需要频繁增加，删除操作的场景
 
5、树
 
树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
 
每个节点有零个或多个子节点； 
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
 
在日常的应用中，我们讨论和用的更多的是树的其中一种结构，就是二叉树。 
  
 二叉树是树的特殊一种，具有如下特点：
 
1、每个结点最多有两颗子树，结点的度最大为2。 
 2、左子树和右子树是有顺序的，次序不能颠倒。 
 3、即使某结点只有一个子树，也要区分左右子树。 
 
二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
 
扩展： 
 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大，但算法上比较复杂，想学习的话还是需要花时间去深入的。
 
6、散列表
 
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
 
记录的存储位置=f(key) 
 
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
 
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下： 
  
 从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。 
 
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
 
7、堆
 
堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
 
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
 
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
 
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。 
 (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下： 
  
 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
 
8、图
 
图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。 
 
按照顶点指向的方向可分为无向图和有向图： 
  
  
 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构，这里不做展开，读者有兴趣可以自己学习深入。

循环结构
 
 
循环结构可以减少源程序重复书写的工作量(代码量)，用来描述重复执行某段算法的问题，这是程序设计中最能发挥计算机特长的程序结构。
 
Python中循环结构分为两类，分别是 while 和 for .. in
 
while
 
格式1：
 
num1,num2 = 3,5
while num1 < num2:
    print('如果条件成立，会进入循环体，我所处的这块区域，就是循环体')
    num1 += 1   #控制循环条件中的变量，否则进入死循环
 
 
 
死循环： 死循环就是循环不会终止的循环类型，设置条件永远为True来实现，但非常占用资源
 
 
格式2：
 
num1,num2 = 3,5
while num1 < num2:
    print('如果条件成立，会进入循环体')
    num1 += 1
else:
    print('条件不成立时，我会被输出')
 
 
 
注意： while循环中的else是在while条件表达式为假的情况下执行的代码内容
 
 
for ... in
 
for 变量 in 容器：用于遍历容器类的数据(字符串，列表，元组，字典，集合)
 
格式1：
 
user_list = ['小明','小红','小强','小军']
for val in user_list:
    print(val)
 
格式2：
 
data = ('a','alibaba'),('b','baidu'),('c','changhong')
for k,v in data:
    print(k,'======>',v)
 
使用格式2请注意： 要求遍历的容器必须是以下几种格式
 
[(),(),()]    列表中有元组
[[],[],[]]    列表中有列表
((),(),())    元组中有元组
{(),(),()}    集合中有元组
字典的特殊使用

格式3：
 
data = ('a','b','c','d','e')
for v in data:
    print(v)
else:
    print('我else区间又来啦！')
 
 
 
循环结束时执行else区间的代码
 
 
流程控制语句
 
 
break
 
翻译：破坏，结束
作用：在循环中break的作用是终止当前循环结构的后续所有操作，一点程序运行了break，循环也就终止了。

continue
 
翻译：继续
作用：在循环中continue的作用是跳过本次循环，开始下一次循环。continue执行之后本次循环的后续代码不再执行，直接进入下一次循环。

pass
 
翻译：忽略
作用：pass是没有任何意义的空语句，主要用来占位用，避免语法错误。

遍历循环 for
无限循环 while
循环控制保留字
循环的高级用法
 
遍历循环
 
遍历某个结构形成的运行方式
 
for  <循环变量>  in  <遍历结构> ：
            <语句块>
 
从遍历结构中逐一提取元素，放在循环变量
由保留字for和in组成，完整遍历所有元素后结束
每次循环，从遍历结构中提取元素放入循环变量，并执行一次语句块
 
遍历循环的应用
 
1.1计数循环(N次)
 
for i in range(N):
      <语句块>
遍历由range()函数产生的数字序列，产生循环
eg1：
for i in range(5):                       或    for i  range(5)：
     print(i)													print("hello:",i)
 运行结果为											运行结果为
 0																hello: 0
 1																hello: 1
 2																hello: 2
 3																hello: 3
 4																hello: 4
 
1.2计数循环(N次)
 
for i in range(M, N, K) :
		<语句块>
遍历由range()函数产生的数字序列，产生循环
从 M 开始到 N 之前的整数，并且以 K 为步长
 
eg2:
for i in range(1,6):                       或    for i  range(1,6,2)：
     print(i)													print("hello:",i)
 运行结果为											运行结果为
 1																hello: 1
 2																hello: 3
 3																hello: 5
 4																
 5																
 
1.3字符串遍历循环
 
for c in s:
	<语句块>
s是字符串，遍历字符串每个字符，产生循环
 
eg1:
for c in "prthon123":
		print(c, end=",")
输出结果为：p,y,t,h,o,n,1,2,3
 
1.4列表循环遍历
 
for item in ls:
	<语句块>
ls是一个列表，遍历每个元素，产生循环
 
eg2:
for  item in  [123,"PY",456]:
		print(item, end=",")
输出结果为：123, PY,456
 
1.5文件遍历循环
 
for line in fi:
	<语句块>
fi是一个文件标识符，遍历其每行，产生循环。


 
2无限循环
 
由条件控制的循环运行方式
 
while  <条件>：
		<语句块>
反复执行语句块，直到条件不满足时结束
 
eg1:
a=3
while a>0:
	a=a-1
	print(a)
输出结果为：
2
1
0
 
2.1循环控制保留字
 
break 和continue
 
break跳出并结束当前整个循环，执行循环后的语句
continue结束当次循环，继续执行后续次数循环
break和continue可以与for和while循环搭配使用
 
eg1:
for  c in "PYTHON":
	  if c == "T" :
	  		continue
	  print(c,end=" ")
运行结果为：
PYHON
 
eg2：
for  c in "PYTHON":
	  if c == "T" :
	  		break
	  print(c,end=" ")
运行结果为：
PY
 
eg3:
s = "PYTHON"														
while  s !=" ":
	for c in s:
		print(c, end=" ")
	s = s[:-1]
运行结果为：
PYTHONPYTHOPYTHPYTPYP

EG4"
s = "PYTHON"														
while  s !=" ":
	for c in s:
		if c == "T":
			break
		print(c, end=" ")
	s = s[:-1]
运行结果为：
PYPYPYPYPYP
break仅退出最内层的当前循环
 
random库
 
是使用随机数的python标准库
 
 
伪随机数：采用梅森旋转算法生成的（伪）随机序列中元素
 
 
random库主要用于生成随机数
 
 
使用random库：import random
 random库包含两类函数，常用共8个
 
 
基本随机函数：seed() ，random()
 
 
扩展随机数函数：randint() , getrandbits(), uniform(), randrange(), choice(), shuffle()
 

for循环是Linux shell 中最常用的结构。for 循环有三种结构：一种结构是列表for循环；第二种结构是不带列表for循环；第三种结构是类C风格的for循环。上篇博文讲解了不带列表for循环，本篇博文重点看类C风格for循环。类C风格的for循环也可被称为计次for循环，一般用于循环次数已知的情况。
 
下面是类C风格for循环的语法格式
 
 
for((expr1; expr2; expr3))
do
    command
    command
    ...
done
其中表达式expr1为循环变量赋初值的语句；表达式expr2决定是否进行循环的表达式，当判断expr2退出状态为0时，执行do和done之间的循环体，当退出状态为非0时，将退出for循环执行done后的命令；表达式expr3用于改变循环变量的语句。类C风格的for循环结构中，循环体也是一个块语句，要么是单条命令，要么是多条命令，但必须包裹在do和done之间。

 
 

 
 
ex9、输出前5个正数
 
 
[zhangqi@localhost shellscript]$ cat for_ex9.sh 
#!/bin/bash

#使用类C风格for循环输出1~5
for ((integer = 1; integer <= 5; integer++)) 
do
    echo "$integer"
done

[zhangqi@localhost shellscript]$ sh for_ex9.sh 
1
2
3
4
5
[zhangqi@localhost shellscript]$ 


 脚本中for循环首先声明了循环变量integer，并赋值为1，之所以称integer为循环变量，是因为integer用于控制循环执行的次数和结束条件，接着判断integer是否小于或等于5，若integer小于或等于5,成立，则执行循环体do和done之间的命令，而后执行修正表达式“integer++”，将integer的值加1，再次判断integer小于或等于5是否成立，以此类推，直至循环结束。 
 

 
 
使用类C风格for循环要注意以下事项：
 
 
如果循环条件最初的退出状态为非0，则不会执行循环体
当执行更新语句时，如果循环条件的退出状态永远为0，则for循环将永远执行下去，从而产生死循环
Linux shell中不运行使用非整数类型的数作为循环变量
如果循环体中的循环条件被忽略，则默认的退出状态为0
在类C风格的for循环中，可以将三个语句全部忽略掉，下面是合法的for循环
 

 
for((; ; ))
do
    echo "hello world"
done
 
 ex10、循环计算1~100内所有的奇数之和
 

 
[zhangqi@localhost shellscript]$ cat for_ex10.sh 
#!/bin/bash

sum=0

for((i = 1; i <= 100; i = i + 2))
do
    let "sum += i"
done

echo "sum = $sum"

[zhangqi@localhost shellscript]$ sh for_ex10.sh 
sum = 2500
[zhangqi@localhost shellscript]$ 

 
 其中循环条件为 i<=100，初始条件i=1，因此，i=i+2将步长设定为2，每执行一次循环体，就将i的值增加2，最终产生结果sum 为2500
 

 
 
 

 ex11、使用逗号运算符对两个变量进行操作
 

 
[zhangqi@localhost shellscript]$ cat for_ex11.sh 
#/bin/bash

limit=5

for((a = 1, b = 5; a <= limit; a++, b --))
do 
    let "temp=a-b"
    echo "$a-$b=$temp"
done

[zhangqi@localhost shellscript]$ sh for_ex11.sh 
1-5=-4
2-4=-2
3-3=0
4-2=2
5-1=4
[zhangqi@localhost shellscript]$ 

 
 在脚本中，对变量a 和 变量b 同时初始化，通过a <=limit 来设置循环条件，然后通过a++设置a加1操作、b--设置b减1操作，每执行一次for循环，都判断a是否小于等于limit，该循环将不断的执行，直到a > 5。
 

 
 
 

 在使用类C风格的for循环时，要保证for循环可以正常结束，也就是必须保证循环条件的结果存在退出状态为非0的情况，否则将无休止地执行下去，从而产生死循环。