數(shù)據(jù)結(jié)構(gòu)“使用指南”

一、什么是數(shù)據(jù)結(jié)構(gòu)？

數(shù)據(jù)結(jié)構(gòu)是指相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。簡單來說，數(shù)據(jù)結(jié)構(gòu)就是設(shè)計數(shù)據(jù)以何種方式組織并存儲在計算機中。比如：列表、集合與字典等都是一種數(shù)據(jù)結(jié)構(gòu)。

“程序=數(shù)據(jù)結(jié)構(gòu)+算法”

二、數(shù)據(jù)結(jié)構(gòu)的分類

數(shù)據(jù)結(jié)構(gòu)按照其邏輯結(jié)構(gòu)可分為線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)

• 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系

• 樹結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系

• 圖結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系

下面就來說說線性結(jié)構(gòu)

三、線性結(jié)構(gòu)

（1）棧

1、定義：棧是一個數(shù)據(jù)集合，可以理解為只能在一端進行插入或者刪除操作的列表。

2、棧的特點：后進先出（last-in，first-out），簡稱LTFO表

3、棧的概念：

• 棧頂：允許插入和刪除的這一端稱之為棧頂

• 棧底：另一固定的一端稱為棧底

• 空棧：不含任何元素的棧稱為空棧

4、棧的基本操作：

• 進棧（壓棧）：push

• 出棧：pop

• 取棧頂：gettop

如圖：

5、棧的Python實現(xiàn)

不需要自己定義，使用列表結(jié)構(gòu)即可。

• 進棧函數(shù)：append

• 出棧函數(shù)：pop

• 查看棧頂元素：li[-1]

li = []
li.append(1)
li.append(2)
li.append(3)
print(li)
print(li.pop())
print(li.pop())
print(li.pop())
# print(li.pop()) ?#當(dāng)棧空的時候就會報錯
# print(li[-1]) #查看棧頂元素

6、棧的應(yīng)用----括號匹配問題

問題：給一個字符串，其中包含小括號，中括號，大括號，求該字符串中的括號是否匹配

例如：

()()[]{} ? ? ? ?匹配
([{()}]) ? ? ? ?匹配
[]( ? ? ? ?不匹配
[(]) ? ? ? ?不匹配

代碼如下：

# 方式一
def brace_match(s):
 ? ?'''括號匹配問題'''
 ? ?stack = []
 ? ?# {()}[]
 ? ?match = {')': '(', '}': '{', ']': '['}
 ? ?match2 = {'(': ')', "{": "}", "[": "]"}
 ? ?for ch in s:
 ? ? ? ?# print(i)
 ? ? ? ?if ch in {'(', '{', '['}: ?# 如果左括號在里面就把左括號添加進去，等待和右括號匹配
 ? ? ? ? ? ?stack.append(ch)
 ? ? ? ?elif len(stack) == 0: ?# 如果再次進來括號的時候，這時候發(fā)現(xiàn)棧空了，說明缺少了左括號了
 ? ? ? ? ? ?print('缺少了%s' % match[ch])
 ? ? ? ? ? ?return False
 ? ? ? ?elif stack[-1] == match[ch]: ?# 比如棧頂元素是(,ch=')'
 ? ? ? ? ? ?stack.pop()
 ? ? ? ?else:
 ? ? ? ? ? ?print('括號不匹配')
 ? ? ? ? ? ?return False

 ? ?if len(stack) > 0: ?# 如果棧剩余了，說明缺少了右括號
 ? ? ? ?print('缺少了%s' % match2[stack[-1]])
 ? ? ? ?return False
 ? ?return '匹配成功'

# 方式二
def check_kuohao(s):
 ? ?stack = []
 ? ?for char in s:
 ? ? ? ?if char in {'(', '[', '{'}:
 ? ? ? ? ? ?stack.append(char)
 ? ? ? ?elif char == ')':
 ? ? ? ? ? ?if len(stack) > 0 and stack[-1] == '(':
 ? ? ? ? ? ? ? ?stack.pop()
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?return False
 ? ? ? ?elif char == ']':
 ? ? ? ? ? ?if len(stack) > 0 and stack[-1] == '[':
 ? ? ? ? ? ? ? ?stack.pop()
 ? ? ? ? ? ?else:
 ? ? ? ? ? ? ? ?return False
 ? ? ? ?elif char == '}':
 ? ? ? ? ? ?if len(stack) > 0 and stack[-1] == '{':
 ? ? ? ? ? ? ? ?stack.pop()
 ? ? ? ?else:
 ? ? ? ? ? ?return False
 ? ?if len(stack) == 0:
 ? ? ? ?return True
 ? ?else:
 ? ? ? ?return False

ret = brace_match('{()}]')
print(ret)

print(check_kuohao('{()}]'))

（2）隊列

1、介紹

• 隊列是一個數(shù)據(jù)集合，僅允許在列表的一端進行插入，另一端進行刪除，

• 進行插入的一端稱為隊尾（rear），插入動作稱之為進隊或入隊

• 進行刪除的一端稱之為對頭（front），刪除動作稱為出隊

雙向隊列：對列的兩端都允許進行進隊和出隊操作

2、隊列的實現(xiàn)

隊列能否簡單用列表實現(xiàn)？為什么？

• 初步設(shè)想：列表+兩個下標(biāo)指針

• 創(chuàng)建一個列表和兩個變量，front變量指向隊首，rear變量指向隊尾。初始時，front和rear都為0。

• 進隊操作：元素寫到li[rear]的位置，rear自增1。

• 出隊操作：返回li[front]的元素，front自減1。

3、隊列的實現(xiàn)原理-----環(huán)形對列

環(huán)形隊列：當(dāng)隊尾指針front == Maxsize + 1時，再前進一個位置就自動到0。

• 實現(xiàn)方式：求余數(shù)運算

• 隊首指針前進1：front = (front + 1) % MaxSize

• 隊尾指針前進1：rear = (rear + 1) % MaxSize

• 隊空條件：rear == front

• 隊滿條件：(rear + 1) % MaxSize == front

4、對列的內(nèi)置模塊

使用方法：from collections import deque ??#deque是支持雙向隊列的

• 創(chuàng)建隊列：queue = deque(li)

• 進隊：append

• 出隊：popleft

• 雙向隊列隊首進隊：appendleft

• 雙向隊列隊尾進隊：pop

from collections import deque
queue = deque()#創(chuàng)建隊列
queue.append('first')
queue.append('second')
queue.append('third')
print(queue.popleft())
print(queue.popleft())
print(queue.popleft())#出隊,,先進先出
print([i for i in queue]) ?#查看隊列里的元素

queue.appendleft('one')#雙向隊列隊首進隊
queue.appendleft('two')#雙向隊列隊首進隊
queue.appendleft('five')#雙向隊列隊首進隊
print(queue.pop())
print(queue.pop())#雙向隊列從隊尾出隊
print([i for i in queue])

#單向隊列
from queue import Queue
q = Queue()
q.put('a')
q.put('b')
q.put('c')
print(q.get()) ?#a

（3）單鏈表

鏈表中每一個元素都是一個對象，每一個對象都是一個節(jié)點，包含有數(shù)據(jù)域key和指向下一個節(jié)點的指針next。通過各個節(jié)點之間的互相連接，最終串聯(lián)成一個列表

1、節(jié)點定義：

class Node(object):
 ? ?def __init__(self, item):
 ? ? ? ? self.item = item
 ? ? ? ? self.next = None

2、建立鏈表

頭插法

尾插法

3、鏈表的遍歷

4、鏈表節(jié)點的插入和刪除

# 插入：
p.next = curNode.next
curNode.next = p

#刪除：
p = curNode.next
curNode.next = p.next ?#當(dāng)前節(jié)點的下一個指向就指向他下一個的下一個
del p

插入：

刪除：

< >（4）雙鏈表

雙鏈表中的每個節(jié)點有兩個指針：一個指向后面節(jié)點、一個指向前面節(jié)點

1、節(jié)點定義：

class Node(object):
 ? ?def __init__(self,item):
 ? ? ? ?self.item = item ?#數(shù)據(jù)
 ? ? ? ?self.next = None ?#下一個指向
 ? ? ? ?self.prior = None #上一個指向

2、雙鏈表節(jié)點的插入和刪除

#插入
p.next = curNode.next
curNode.next.prior = p
p.prior = curNode
curNode.next = p

#刪除
p = curNode.next
curNode.next = p.next
p.next.prior = curNode
del p

（5）哈希表

哈希表（又稱為散列表），是一種線性表的存儲結(jié)構(gòu)。哈希表由一個順序表（數(shù)組）和一個哈希函數(shù)組成。哈希函數(shù)h(k)將k作為自變量，返回元素的存儲下標(biāo)。

1、簡單哈希函數(shù)

• 除法哈希：h(k) = k mod m ?#mod就是%? ? ? #除留余數(shù)法

• 乘法哈希：h(k) = floor(m(kA mod 1))? ?0

假設(shè)有一個長度為7的數(shù)組，哈希函數(shù)h(k)=k%7。元素集合{14,22,3,5}的存儲方式如下圖。

2、哈希沖突

由于哈希表的大小是有限的，而要存儲的值的總數(shù)量是無限的，因此對于任何哈希函數(shù)，都會出現(xiàn)兩個不同元素映射到同一個位置上的情況 ，

這種情況叫做哈希沖突。

比如h(k)=k%7, h(0)=h(7)=h(14)=...

3、解決哈希沖突的辦法

• a、開放尋址法

• b、拉鏈發(fā)

開放尋址法：如果哈希函數(shù)返回的位置已經(jīng)有值，則可以向后探查新的位置來存儲這個值。

• 線性探查：如果位置i被占用，則探查i+1, i+2,……

• 二次探查：如果位置i被占用，則探查i+12,i-12,i+22,i-22,……

• 二度哈希：有n個哈希函數(shù)，當(dāng)使用第1個哈希函數(shù)h1發(fā)生沖突時，則嘗試使用h2,h3,……

?拉鏈法：哈希表每個位置都連接一個鏈表，當(dāng)沖突發(fā)生時，沖突的元素將被加到該位置鏈表的最后。

4、哈希表在Python中的應(yīng)用

a、字典與集合都是通過哈希表來實現(xiàn)的

b、 在Python中的字典：a = {'name': 'Alex', 'age': 18, 'gender': 'Man'}，使用哈希表存儲字典，通過哈希函數(shù)將字典的鍵映射為下標(biāo)。

假設(shè)h(‘name’) = 3, h(‘a(chǎn)ge’) = 1, h(‘gender’) = 4，則哈希表存儲為[None, 18, None, ’Alex’, ‘Man’]

c、在字典鍵值對數(shù)量不多的情況下，幾乎不會發(fā)生哈希沖突，此時查找一個元素的時間復(fù)雜度為O(1)。