從零開始學演算法:4.萬能陣列
作者: tiankonguse | 更新日期:
陣列是萬能的,那是不能的;因為他萬能的時候名字不叫陣列了。
這篇文章涉及的原始碼可以全部免費獲得,在公眾號中回覆“萬能陣列”可以獲得。
一、背景
大家好,我是tiankonguse。
由於某些原因,經常有人想學習演算法但之前又沒有相關經驗,不知道從何做起。 我思考了許久,計劃寫一個系列來分享如何入門學習演算法。
之前已經分享了《 ofollow,noindex" target="_blank">認識演算法 》、《 瞭解套路長啥樣 》、《 排序演算法 》、《 二分查詢 》,這是第五篇《萬能陣列》。
考慮到很多人不是科班出身的,或者當初沒好好學習,很多基礎知識都忘記了。
還有上次說的交接給我的一個專案,其中的關鍵邏輯就是使用陣列實現的,沒想到O(n)複雜度的操作到處都是,真實慘不忍睹。
所以這篇文章來給大家普及下陣列上的知識點,大家使用的時候對於複雜度高的操作應該儘量避免,不然後面就是一個瓶頸點。
以後這些問題即使解決了,效能翻了幾倍,也沒什麼好炫耀的,因為這些本來就是基礎,最初實現的時候就應該避免。
一、基礎知識
C語言中的陣列,使用的時候被當做一個定長的連續的空間。
我們可以通過下標在O(1)的時間上直接讀取或者修改對應位置的值。
所以陣列在很多時候是一種最常見高效的資料結構(姑且算資料結構)。
但是使用陣列的時候也會遇到一些問題。
比如陣列的空間不管我們有沒有使用,長度都是那麼多,不知道用了多少。
如果陣列滿了,想繼續加元素,就會陣列越界。
如果陣列前面想刪除,涉及到後面的元素copy到前面,時間複雜度是O(n)。
所以我們希望對陣列進行一個封裝,名字就叫做萬能陣列,可以實現任何我們想操作的事情。
為了程式碼簡單點,這裡不使用模板,直接以整數為例。
二、自動擴充套件陣列
使用資料時經常會發現空間不夠了,所以能夠自動擴大空間就好了。
自動擴充套件的基本思想是追加資料的時候,先判斷空間是不是用完了,如果用完了,申請一個更大的記憶體,舊資料copy過去,舊記憶體釋放,新資料賦值即可。
三、棧
棧是一種很常用的資料結構,特點就是後進先出。
可以想象你們一排車開進死衚衕了,最先進去的在最裡面,最後進去的在最外面。
那大家想出來,肯定是最外面的先出來,也就是最後進去的先出來(後進先出)。
棧的使用場景有:序列反選、逆序輸出、括號匹配、DFS等。
四、佇列
佇列是一種先進先出的資料結構。
最常見的例子就是排隊吃飯,先打飯的肯定是隊首的那個人。
由於佇列涉及到刪除陣列前面的元素,這裡可以使用一個標記來標記前面刪除了多少個元素。
對於記憶體擴充套件時,資料從頭對齊問題,這裡暫時不處理。
五、雙向佇列
棧大家都聽過,佇列大家也都聽過,那雙向佇列聽過的人就不多了吧。
雙向佇列,顧名思義,就是兩邊都可以進也都可以出的佇列,也就是棧和佇列的合體了。
不過這裡會有一個問題,隊首也可以插入資料了,有可能前面的空間用完不夠用了。
所以,我們到了不得不面對隊首空間的問題了,下一小節分享一個比較實用的方法。
六、迴圈佇列
在佇列和雙向佇列小節裡,我們發現了兩個問題。
問題1:佇列的隊尾沒空間了,隊首可能還有空間,我們沒辦法用起來,只能直接擴大記憶體。
問題2:雙向佇列的隊首沒空間了,隊尾可能有空間,我們也沒用起來,不但需要擴大記憶體,還要對資料進行偏移,好給隊首預留一些位置來。
我們要做的是,在還有空間時,儘量利用已有的空間。
比如隊尾的空間用完了,隊首還有,那入隊就放在隊首那一頭。
直到確實沒有空間了,我們才去擴充套件空間。
雙向迴圈佇列與迴圈佇列的思想是類似的,這裡以迴圈佇列為例來看看實現吧。
七、其他操作
上面對於陣列只進行了簡單的操作,即首尾增刪資料。
實際情況是可能在中間插入資料,也可能刪除中間的資料,還需要使用下標定位。
這個時候如果粗暴的實現的話,會發現複雜度是O(n)的。
比如刪除陣列的第一個元素,那麼陣列後面所有的元素都需要前移一下(通過迴圈佇列可以不移動)。
而在中間插入或刪除一個元素,操作位置後面的空間依舊需要移動,這個時候迴圈佇列就沒轍了。
面對這個問題該怎麼辦呢?
後續的文章慢慢介紹一些方法來。
這篇文章涉及的原始碼可以全部免費獲得,在公眾號中回覆“萬能陣列”可以獲得。
本文首發於公眾號:天空的程式碼世界,微信號:tiankonguse-code。
推薦閱讀:
今天長按識別上面的二維碼,在公眾號中回覆“ ACM模板 ”,你將免費獲得我大學耗時四年整理的《ACM演算法模板》。
回覆“ 演算法的世界 ”,或點選 閱讀原文 加入“tiankonguse的朋友們”,已有三百多個小夥伴加入。