一、数据结构
数据是一个抽象的概念，将其进行分类后得到程序设计语言中的基本类型。如：int，float,char等，数据元素之间不是独立的，存在特定的关系，这些关系便是结构，数据结构指数据对象中数据元素之间的关系。
【示例】
#保存班级的学生信息,根据学生学号查询学生
#一个班级的学生信息是多条数据。必须使用能够保存多条数据的类型 列表 元组 字典 集合
#学生信息（sno sname age score)
#1列表保存学生信息，学生信息使用元组保存
stus=[('1001','张三',23,98),
('1002','李四',23,99)]
#1列表保存学生信息，学生信息使用字典
stu1=[{'sno':'1001','sname':'张三','age':23,'score':98},
{'sno':'1002','sname':'李四','age':23,'score':99}]
#如果使用列表保存学生信息，必须遍历当前列表，拿学号进行判断,时间复杂度O(n)
for stu in stus:
pass #获取到当前学生信息
#字典保存学生信息
stus={'1001':{'sname':'张三','age':23,'score':98},
'1002':{'sname':'李四','age':23,'score':99}}
#如果使用的字典保存，根据key进行获取，时间复杂度O(1)
stu=stus['1002']
二、链表
顺序表的构建需要预先知道数据大小来申请连续的存储空间，而在进行扩充时又需要进行数据的搬迁，所以使用起来不是很灵活。
链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
链表的定义：链表是一种常见的基础数据结构，是一种线性表，但是不像顺序表一样连续存储数据，而是在每一个节点（数据存储单元）里存放下一个节点的位置信息（即地址）。
单向链表：
单向链表也叫单链表，是链表中最简单的一种形式，它的每个节点包含两个域，一个信息域（元素域）和一个连接域。这个连接指向链表中的下一个节点，而最后一个节点的链接域则指向一个空值。
- 表元素域elem用来存放具体的数据
- 链接域next用来存放下一个节点的位置（python中的标识)
- 变量p指向链表的头节点（首节点）的位置，从p出发能找到表中的任意节点
| 方法名 | 说明 |
| is_empty() | 链表是否为空 |
| length() | 链表长度 |
| travel() | 遍历整个链表 |
| add(item) | 链表头部添加元素 |
| append(item) | 链表尾部添加元素 |
| insert(pos, item) | 指定位置添加元素 |
| remove(item) | 删除节点 |
| search(item) | 查找节点是否存在 |
【示例】
class Node(object):
def __init__(self,elem):
#elem指数据元素
self.elem=elem
#指向下一个节点的链接域
self.next=None
#构造单向链表类
class SingleLinkList:
#初始化方法
def __init__(self,node=Node):
self._head=node
#在头部添加元素
def add(self,item):
pass
#在尾部添加元素
def append(self,item):
pass
#在指定位置添加元素
def insert(self,pos,item):
pass
#删除节点
def remove(self,item):
pass
#查找节点是否存在
def search(self,item):
pass
#判断单向链表是否为空
def is_empty(self):
pass
if __name__=='__main__':
#初始化元素值为20的单向链表
singleLinkList=SingleLinkList(20)
#初始化一个空的单向链表
singleLinkList=SingleLinkList()【示例】单链表是否为空、计算长度实现
class Node(object):
def __init__(self,elem):
#elem指数据元素
self.elem=elem
#指向下一个节点的链接域
self.next=None
#构造单向链表类
class SingleLinkList:
#初始化方法
def __init__(self,node=None):
#判断node是否为空
if node!=None:
headNode=Node(node)
self._head=headNode
else:
self._head=node
self._head=node
#在头部添加元素
def add(self,item):
pass
#在尾部添加元素
def append(self,item):
pass
#在指定位置添加元素
def insert(self,pos,item):
pass
#删除节点
def remove(self,item):
pass
#查找节点是否存在
def search(self,item):
pass
#判断单向链表是否为空
def is_empty(self):
#判断head指向是None,如果是None则是空链表
if self._head==None:
return True
else:
return False
return self._head==None
#计算链表的长度
def length(self):
count=0
curNode=self._head
while curNode!=None:
count+=1
curNode=curNode.next
return count
if __name__=='__main__':
#初始化元素值为20的单向链表
singleLinkList=SingleLinkList(20)
#初始化一个空的单向链表
singleLinkList=SingleLinkList()
print('是否为空链表：',singleLinkList.is_empty())
print('链表的长度:',singleLinkList.length())
三、链表与顺序表的对比
链表失去了顺序表随机读取的有点，同时链表由于增加了节点的指针域，空间开销比较大，但对于存储空间的使用要相对灵活。
链表与顺序表的各种操作复杂度如下所示：
| 操作 | 链表 | 顺序表 |
| 访问元素 | O(n) | O(1) |
| 在头部插入/删除 | O(1) | O(n) |
| 在尾部插入/删除 | O(n) | O(1) |
| 在中间插入/删除 | O(n) | O(n) |
四、双向链表
双向链表：每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空值。
【示例】
#双向链表的节点
class Node:
def __init__(self,elem):
self.elem=elem
self.next=None #后继 下一个节点
self.prev=None #前驱 前一个节点
class DoubleLinkList:
#初始化方法
def __init__(self,node=Node):
#判断node是否为空
if node!=None:
headNode=Node(node)
self._head=headNode
else:
self._head=node
def is_empty(self):
return self._head==None
#在头部添加元素
def add(self,item):
node = Node(item)
#判断是否为空链表
if self.is_empty():
self._head=node
else:
#将新节点的链接域next指向头节点
node.next=self._head
#将_head的头节点的prev指向node
self._head.prev=node
#将链表的头_head指向新节点
self._head=node
#在尾部追加元素
def append(self,item):
node=Node(item)
if self.is_empty(): #双链表为空的时候
self._head=node
else:
curNode=self._head
while curNode.next!=Node:
curNode=curNode.next
#修改节点指向 最后一个节点的next指向node
curNode.next=node
#将node节点的前驱指向当前节点
node.prev=curNode
#遍历链表
def travel(self):
curNode=self._head
while curNode!=None:
print(curNode.elem,end='\t')
curNode=curNode.next
print("")
if __name__=='__main__':
doubleLinkList=DoubleLinkList()
doubleLinkList.add(11)
doubleLinkList.add(22)
doubleLinkList.add(33)
doubleLinkList.travel()
print('-------追加-------')
doubleLinkList.append(100)
doubleLinkList.travel()
五、栈
栈：有些地方称为堆栈，是一种容器，可存入数据元素、访问元素、删除元素，他的特点在于只能允许在容器的一端（称为栈顶端指标）进行加入数据和输出数据的运算，没有了位置概念，保证了任何时候可以访问、删除的元素都是此前后存入的那个元素，确定了一种默认的访问顺序。
由于栈数据结构只允许在一端进行操作，因而按照后进先出的工作原理运行
栈结构实现：
- Stack()创建一个新的空栈
- push(item)添加一个新的元素item到栈顶
- pop()弹出栈顶元素
- peek()返回栈顶元素
- is_empty()判断栈是否为空
- size()返回栈的元素个数
【示例】栈知识的运用
class Stack(object):
#定义初始化方法
def __init__(self):
#初始化一个空列表
self._list=[]
#压栈
def push(self,item):
self._list.append(item)
#弹出元素
def pop(self):
return self._list.pop()
#返回栈顶元素
def peek(self):
return self._list[len(self._list)-1]
#判断栈是否为空
def is_empty(self):
return self._list==[]
#计算栈的大小
def size(self):
return len(self._list)
if __name__=='__main__':
stack=Stack()
print('是否是空栈',stack.is_empty())
#压栈
stack.push(1)
stack.push(2)
stack.push(3)
stack.push(4)
print('是否是空栈', stack.is_empty())
print('栈的长度', stack.size())
#弹出
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
六、队列
队列是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。与栈不同的是，
队列是一种先进先出的线性索
队列的操作：
- Queue()创建一个空的队列
- enqueue(item)往队列中添加一个item元素
- daqueue()从队列头部删除一个元素
- is_empty()判断队列是否为空
- size()返回队列的大小
【示例】队列知识的运用
class Queue:
def __init__(self):
self._list=[]
#进队
def enqueue(self,item):
self._list.insert(0,item)
#出队
def dequeue(self):
return self._list.pop()
#判断队列是否为空
def is_empty(self):
return self._list==[]
#计算队列的大小
def size(self):
return len(self._list)
if __name__=='__main__':
queue=Queue()
#判断是否为空
print('队列是否为空：',queue.is_empty())
queue.enqueue(10)
queue.enqueue(20)
queue.enqueue(30)
queue.enqueue(40)
print('队列是否为空：', queue.is_empty())
print('队列的大小：',queue.size())
print('-----出队------')
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())