Evernote Export

線性結(jié)構(gòu)： python的列表操作 列表是如何存儲的：順序存儲的，是一塊連續(xù)的內(nèi)存，內(nèi)存是一堆格子，列表是一串連續(xù)的編號 32位機(jī)器上一個整數(shù)占4個字節(jié) 數(shù)組和列表有2點(diǎn)不同，1.數(shù)組的元素類型要求是相同的；2.數(shù)組長度固定 列表：1.python中列表的元素類型可以不同（python列表中存儲的不是數(shù)值而是地址）；2.python列表會根據(jù)輸入的長度自動根據(jù)序列來遞增列表 列表的append時間復(fù)雜度是O(1) 列表的插入和刪除的時間復(fù)雜度是O(n) 棧的結(jié)構(gòu)： 棧是一個數(shù)據(jù)集合，可以理解為只能在一端插入或進(jìn)行刪除操作的列表 棧的特點(diǎn)：后進(jìn)先出LIFO(last in first out) 棧的概念：棧頂、棧底 棧的基本操作： ? ? 進(jìn)棧（壓棧）：push
? ? 出棧：pop
? ? 取棧頂：gettop
棧的應(yīng)用 括號匹配問題：給一個字符串，其中包括小括號、中括號、大括號、求該字符串中的括號是否匹配 隊(duì)列 隊(duì)列是一個數(shù)據(jù)集合，僅允許在列表的一端進(jìn)行插入，另一端進(jìn)行刪除 進(jìn)行插入的一端稱為隊(duì)尾(rear)，插入動作稱為進(jìn)隊(duì)或入隊(duì) 進(jìn)行刪除的一端稱為隊(duì)頭(front),刪除動作稱為出隊(duì) 隊(duì)列的性質(zhì):先進(jìn)先出(First-in, First-out) 迷宮的兩種方式 棧-深度優(yōu)先搜索 思路：從一個節(jié)點(diǎn)開始，任意找下一個能走的點(diǎn)，當(dāng)找不到能走的點(diǎn)，退回上一個點(diǎn)尋找是否有其他方向的點(diǎn) 使用棧存儲當(dāng)前路徑 隊(duì)列-廣度優(yōu)先搜索 思路：從一個節(jié)點(diǎn)開始，尋找所有接下來能繼續(xù)走的點(diǎn)，繼續(xù)尋找，直到找到出口 使用隊(duì)列存儲當(dāng)前正在考慮的節(jié)點(diǎn) 鏈表 鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，鏈表是由一系列節(jié)點(diǎn)組成的元素集合。 每個節(jié)點(diǎn)包含兩個部分，數(shù)據(jù)域item和指向下一個節(jié)點(diǎn)的指針next。通過節(jié)點(diǎn)之間的相互連接，最終串聯(lián)成一個鏈表。 創(chuàng)建鏈表： ? ? 頭插法
? ? 尾插法
復(fù)雜度分析 按元素值查找O(n) 按下標(biāo)查找O(n) 在某一元素中插入O(1) 刪除元素O(1) 鏈表在插入和刪除的操作上明顯快于順序表 鏈表的內(nèi)存快于靈活的分配:試?yán)面湵碇匦聦?shí)現(xiàn)棧和隊(duì)列 鏈表這種鏈?zhǔn)酱鎯Φ臄?shù)據(jù)結(jié)構(gòu)對樹和圖的結(jié)構(gòu)有很大的啟發(fā)性 哈希表(散列表) 哈希表通過哈希函數(shù)來計(jì)算數(shù)據(jù)存儲位置的數(shù)據(jù)結(jié)構(gòu)，通常支持一下操作 insert(key,value):插入鍵值對(key,value) get(key):如果存在鍵為key的鍵值則返回其value，否則返回空值 delete(key):刪除key的鍵值對 直接尋址表 當(dāng)關(guān)鍵字的全域U比較小時，直接尋址是一種簡單而有效的方法 直接尋址的技術(shù)缺點(diǎn)： 當(dāng)域U很大時，需要消耗大量內(nèi)存，很不實(shí)際 如果域U很大而實(shí)際出現(xiàn)的key很少，則大量空間被浪費(fèi) 無法處理關(guān)鍵字不是數(shù)字的情況 哈希表，是一種線性表的存儲結(jié)構(gòu)。哈希表由一個直接尋址表和一個哈希函數(shù)組成，哈希函數(shù)h(k)將元素關(guān)鍵字k作為自變量，返回元素的存儲下標(biāo) 假設(shè)有一個長度為7的哈希表，哈希函數(shù)h(k) =?k%7，元素集合{14,22,3,5}的存儲方式如下圖 哈希沖突 由于哈希的大小是有限的，而要存儲的值的總數(shù)量是無限的，因此對于任何哈希函數(shù)，都會出現(xiàn)兩個不同的值但是映射到同個位置上的情況，這種情況稱為哈希沖突 解決哈希沖突方法 1.開放尋址法:如果哈希函數(shù)返回的位置已經(jīng)有值，則可以向后探查新的位置來存儲這個值 線性查探：如果位置被占用，則探查i+1，i+2... 二次查探：如果位置i被占用，則探查i+1^2,i-1^2,i+2^2,i-2^2 二度哈希：有n個哈希函數(shù)，當(dāng)使用第一個哈希函數(shù)h1發(fā)生沖突時，則嘗試使用?h2，h3... 2.拉鏈法：哈希表每個位置都連接一個鏈表，當(dāng)沖突發(fā)生時，沖突的元素將被加到該位置鏈表的最后 樹與二叉樹 樹是一種結(jié)構(gòu)，比如目錄結(jié)構(gòu) 樹是一種可以遞歸定義的數(shù)據(jù)結(jié)構(gòu) 樹是由n個節(jié)點(diǎn)組成的集合 ? ? 如果n=0，那這是一顆空樹
? ? 如果n>0,那存在1個節(jié)點(diǎn)作為樹的根節(jié)點(diǎn)，其他節(jié)點(diǎn)可以分為m個集合，每個集合本身又是一棵樹
二叉搜索樹 二叉搜索樹是一顆二叉樹且滿足性質(zhì)：設(shè)x是二叉樹的一個節(jié)點(diǎn)。如果y是x左子樹的一個節(jié)點(diǎn)，那么y.key<=x.key 如果y是x右子樹的一個節(jié)點(diǎn)，那么y.key>=x.key 二叉搜索樹的操作：查詢、插入、刪除 ? ? ? ? ? ? ? ? ? ? ? ? ?

?

轉(zhuǎn)載于:https://www.cnblogs.com/pandaboy1123/p/10098961.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的路飞学城Python-Day171的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。