資料結構概述(參考資料,嚴蔚敏的資料結構.高一凡把書中的僞算法全部用代碼寫了出來)
資料結構定義:
如何把現實中大量而複雜的問題以特定的資料類型和特定的存儲結構儲存到主存儲器(記憶體)中,以及在此基礎上為實作某個功能(比如查找某個元素,删除某個元素,對所有元素進行排序),而執行的相應操作,這個相應的操作也叫算法.
資料結構 = 個體 + 個體的關系
算法 = 對存儲資料的操作
解析:如果要存儲一個一萬個元素的數組,可能沒有那麼大的連續的存儲空間,如果不能存儲,那麼就談不上操作.那麼解決這種問題就要靠連結清單來存儲.
算法:
解題的方法和步驟
衡量算法的标準:
1.時間複雜度.大概程式要執行的次數,而非執行的時間.(為什麼是次數,而不是時間?因為每台機器的處理能力不一樣 .是以不能用時間來算)
2.空間複雜度.算法執行過程中大概所占用的最大記憶體
3.難易程度.算法要别人能夠看懂,不能隻有自己可以看懂
4.健壯性.不能給一個非法的資料程式就挂掉了
資料結構的地位:資料結構是軟體中最核心的課程
程式 = 資料的存儲 + 資料的操作 + 可以被計算機執行的語
什麼是棧,什麼是堆:
所謂的棧記憶體和堆記憶體并不是記憶體裡面有一塊區域叫棧,有一塊區域叫堆.所謂的棧記憶體和對記憶體實際上指的是配置設定記憶體的算法不一樣,如果是以壓棧出棧的方式配置設定的記憶體,就叫棧記憶體.如果是以堆排序的方式配置設定的記憶體就叫堆記憶體
預備知識:
指針:
指針的重要性:指針式 C語言的靈魂
定義:位址(記憶體單元的編号,從0開始的非負整數,對于32位的處理器來說範圍是: 0~FFFFFFFF (0~4G-1)
指針:指針就是位址,位址就是指針
指針變量是存放記憶體單元位址的變量
指針的本質是一個操作受限的非負整數(不能進行算術運算,隻有在特定的時候(如果兩個指針變量指向的是同一塊連續空間中的不同存儲單元)能做相減的運算)
結構體:
為什麼會出現結構體: 為了表示一些複雜的資料類型,而普通變量無法滿足要求
什麼叫結構體:結構體是使用者根據實際需要自己定義的複合資料類型
如何使用結構體:
struct Student{
int sid;
char name[200];
int age;
};
兩種方式: struct Student st = {1000,”zhangsan”,20};
struct Student *pst = &st;
1.st .sid
2.pst—>sid (pst 所指向的結構體變量中的 sid 這個成員)
注意事項:
1.結構體變量不能加減乘除,但是可以互相指派
2.普通結構體變量和結構體指針變量作為函數傳參的問題(結構體形參時,一般要傳位址,因為傳結構體變量記憶體開銷會大)
動态記憶體的配置設定與釋放:
動态構造一維數組
malloc() 函數傳回的是配置設定的記憶體的首位址
假設動态構造一個int型數組 int *p = (int *)malloc(int len);
1、 malloc隻有一個int型的形參，表示要求系統配置設定的位元組數
2、 malloc函數的功能是請求系統len個位元組的記憶體空間，如果請求配置設定成功，則傳回第一個位元組的位址，如果配置設定不成功，則傳回NULL
3、 malloc函數能且隻能傳回第一個位元組的位址，是以我們需要把這個無任何實 際意義的第一個位元組的位址(俗稱幹位址)轉化為一個有實際意義的位址，是以malloc前面必須加(資料類型 *),表示把這個無實際意義的第一個位元組的位址轉化為相應類型的位址。如:int *p = (int *)malloc(50);表示将系統配置設定好的50個位元組的第一個位元組的位址轉化為int *型的位址，更準确的說是把第一個位元組的位址轉化為四個位元組的位址，這樣p就指向了第一個的四個位元組，p+1就指向了第2個的四個位元組,p+i就指向了第i+1個的4個位元組。p[0]就是第一個元素， p[i]就是第 i+1個元素 double *p = (double *)malloc(80); 表示将系統配置設定好的80個位元組的第一個位元組的位址轉化為double *型的位址，更準确的說是把第一個位元組的位址轉化為8個位元組的位址，這 樣p就指向了第一個的8個位元組，p+1就指向了第2個的8個位元組，p+i就指向了第i+1個的8個位元組。p[0]就是第一個元素， p[i]就是第 i+1個元素
4、 free(p)釋放p所指向的記憶體，而不是釋放p本身所占用的記憶體
号外: CPU不能直接通路硬碟,記憶體是 CPU 唯一能夠通路的大容量儲存設備.當然了 CPU 内部還有寄存器可以通路.
CPU 是如何與記憶體打交道的?
CPU 和記憶體是通過三根總線來互動的:
即位址總線(尋址,即要對那塊記憶體進行處理,對于32位的處理器來說,記憶體的最大位址就是2的32次方-1 也就是4G,是以如果處理器是32位的那麼用8G 的記憶體也是沒有效果的,因為超出4G 的記憶體将不會被通路的到),
控制總線(讀或者寫),
資料總線(傳輸資料,CPU 把内部資料寫到記憶體,或者将記憶體中的資料讀到 CPU)
子產品一:線性結構(把所有的結點用一根直線穿起來)
連續存儲[數組]
1.什麼叫做數組:元素類型相同,大小相等
2.數組的優缺點
離散存儲[連結清單]
定義: n個結點離散配置設定, 彼此通過指針相連, 每個結點隻有一個前驅結點,每個結點隻有一個後續結點,首結點沒有前驅結點,尾節點沒有後續結點.
專業術語:
1.首結點:第一個有效的結點
2.尾結點:最後一個有效的結點
3.頭結點:第一個有效結點之前的那個結點,頭結點并不存放有效資料,加頭結點的目的主要是為了友善對連結清單的操作
4.頭指針:指向頭結點的指針變量
5.尾指針:指向尾結點的指針變量
頭結點—>首結點—> ……結點......—>尾結點
結點
struct Node{
int data;//資料域
struct Node *pNode; 指針域
}
每一個連結清單的結點都會有資料域和指針域
如果希望通過一個函數來對連結清單進行處理,我們至少需要接受連結清單的哪些參數? 隻需要一個參數:頭指針.因為我們通過頭指針可以推算對外連結表的其他所有參數
分類:
1.單連結清單:
2.雙連結清單:每一個結點有兩個指針域
3.循環連結清單:能通過任何一個結點找到其他所有的結點
4.非循環連結清單:
算法:
狹義的算法是與資料的存儲方式密切相關的, 廣義的算法是與資料的存儲方式無關.
1.周遊:
2.查找:
3.清空:
4.銷毀:
5.求長度:
排序:
删除結點:
8.插入結點:
泛型:利用某種技術達到的效果就是:不同的存儲方式,執行的操作是一樣的
資料的存儲結構有幾種:
1.線性: 連續存儲[數組]
優點: 存取元素效率非常高
缺點: 插入删除元素效率低, 需要大塊連續的記憶體塊,通常受存儲空間的限制,事先需要知道數組的長度
2.離散存儲[連結清單]
優點:存儲空間沒有限制,插入删除元素效率高
缺點: 存取速度很慢,
線性結構的兩種常見應用之一 棧:
定義:一種可以實作”先進後出”的存儲結構,棧類似于箱子
分類:
靜态棧
動态棧
算法:
出棧
壓棧
應用:
函數調用
中斷
表達式求值 (例如求32+5/6-4 ,這個就會用到兩個棧,一個棧用來存儲-、/、+、 另一個棧用來存儲4、6、5、2、3)
記憶體配置設定
緩沖處理
迷宮
線性結構的兩種常見方式之二 隊列:
定義:一種可以實作”先進先出”的存儲結構
分類:
鍊式隊列 (用連結清單實作的)
靜态隊列 (用數組實作的)
靜态隊列通常都必須是循環隊列,
循環隊列的講解:
1.靜态隊列為什麼必須是循環隊列
2.循環隊列需要幾個參數來确定
需要兩個參數來确定,front 和 rear
3.循環隊列各個參數的含義
兩個參數場合不同的含義.建議初學者先記住,然後慢慢體會:
1).隊列初始化
front 和 rear 的值都是零
2).隊列非空
front 代表的是隊列的第一個元素
rear 代表的是隊列的最後一個有效元素的下一個元素
3).隊列空
front 和 rear 的值相等,但不一定是零
4.靜态隊列入隊僞算法講解
兩步完成:
1.将值存入r 所代表的位置
2.錯誤寫法 r = r+1
正确的寫法是: r = (r+1)%數組的長度
image.png
5.循環隊列出隊僞算法講解
f = (f+1)%數組的長度
6.如何判斷循環隊列是否為空
如果 front 和 rear 的值相等,則該隊列就一定為空
7.如何判斷循環隊列是否已滿
兩種方式:1.多增加一個标志參數(一般不用)
2.少用一個元素(通常使用這種方式) ,如果r和f緊挨着,則隊列已滿
if ( (r+1)%數組的長度 == f ) 已滿;
else 不滿;
隊列算法:
入隊
出隊
隊列的具體應用: 所有和時間有關的操作都有隊列的影子
專題:遞歸
定義:一個函數自己直接或間接調用自己
image.png
遞歸滿足的三個條件:
1.遞歸必須得有一個明确的終止條件
2.該函數所處理的資料規模必須在遞減
3.這個轉化必須是可解的
遞歸和循環:
遞歸:
易于了解
速度慢
存儲空間大
循環:
不易了解
速度快
存儲空間小
1.1+2+3+4+…100的和
2.求階乘
3.漢諾塔
4.走迷宮
遞歸的應用:
樹和森林就是以遞歸的方式定義的
樹和圖的很多算法都是以遞歸來實作的
很多數學公式就是以遞歸的方式定義的
斐波拉契序列:1 2 3 5 8 13 ...
子產品二:非線性結構
樹
樹定義
專業定義:
1.有且隻有一個稱為跟的結點
2.有若幹個互不相交的子樹,這些樹本身也是一顆樹
通俗定義:
1.樹是由結點和邊組成
2.每個結點隻有一個父節點但是可以有多個子節點
3.但有一個節點例外,該節點沒有父節點,此節點稱為根節點
專業術語:
1.節點
2.父節點
3.子節點
4.子孫
5.堂兄弟
6.深度:從根節點到最底層結點的層數成為深度,根節點是第一層
7.葉子節點:沒有子節點的節點
8.非終端結點:實際就是非葉子節點
9.度:子節點的個數稱為度
樹分類
一般樹:任意一個節點的子節點的個數都不受限制
二叉樹:任意一個結點的子節點個數最多有兩個,且子節點位置不可以更改(左子樹和右子樹順序不可更改)
二叉樹的分類:
1.一般二叉樹
2.滿二叉樹:在不增加樹的層數的前提下,無法再多添加一個結點的二叉樹就是滿二叉樹
3.完全二叉樹:如果隻是删除了滿二叉樹最底層最右邊的連續若幹個節點,這樣形成的二叉樹就是完全二叉樹
森林:n個互不相交的樹的集合
樹的存儲
二叉樹的存儲
1.連續存儲[完全二叉樹]:
優點:查找某個節點的父節點和子節點(也包括判斷有沒有)速度很快
缺點:耗用記憶體空間過大
2.鍊式存儲:
一般樹的存儲
雙親表示法:求父節點友善
孩子表示法:求子節點友善
雙親孩子表示法:求父節點和子節點都很友善
二叉樹表示法
把一個普通樹轉化成二叉樹來存儲
具體表示方法:設法保證任意一個結點的,左指針域指向它的第一個孩子,右指針域指向它的堂兄弟,隻要能滿足此條件,就可以把一個普通樹轉化為二叉樹,一個普通樹轉化成的二叉樹一定沒有右子樹
森林的存儲:
森林的存儲就是把森林先轉化成完全二叉樹,然後再存儲,森林轉化成完全二叉樹的過程如下:把 A 當做完全二叉樹的根節點,樹 A 沒有子節點,是以樹 A沒有左子樹,但是 A有兄弟(樹 B)是以, A有右子樹(B) ,B 有子節點(C,D,E) ,是以 B 有左子樹(C);C 沒有子節點,但是有兄弟結點(D),是以 C沒有左子樹,但是有右子樹(D);D沒有子節點,但是有兄弟節點(E),是以 D 沒有左子樹,但是有右子樹(E);E 有子節點(F),沒有兄弟節點,是以 E有右子樹 F, 但沒有左子樹; 對于結點 B, 由于 B 有兄弟結點 G, 是以 B 有右子樹 G;G 有子節點 K,沒有兄弟節點,是以 G 有左子樹K;K 有子節點 M, 但是 K 沒有兄弟結點,是以 K 有右子樹M;M有子節點,沒有兄弟結點,是以 M 有左子樹 L;L 沒有子節點,但是有兄弟結點N,是以 L 有右子樹N;N沒有子節點,但是有兄弟結點 Q, 是以 N 沒有左子樹,但是有右子樹 Q;Q沒有子節點,但是有兄弟結點 F,是以 Q 沒有左子樹,但是有右子樹 F;
森林轉化成二叉樹總量的來說就是:如果一個節點有子節點,就把該子節點當做該節點的左子樹,如果有兄弟節點,就把兄弟節點,當做該節點的右子樹.
下圖是有A, B, C 為根節點的數組成的森林,
image.png
樹的操作
二叉樹的操作
周遊:
先序周遊(先通路根節點)
根節點排最先，然後同級先左後右
中序周遊(中間通路根結點)
先左後根最後右
後序周遊(最後通路根結點)
先左後右最後根
已知兩種周遊序列求原始二叉樹:
已知先序和中序 或者 已知後序和中序 才可以唯一的推出一個二叉樹,但是已知先序和後序是不能推出一個二叉樹的
例子:
示例1:
先序: ABCDEFGH
中序: BDCEAFHG
求後序: DECBHGFA
示例2:
先序: ABDGHCEFI
中序: GDHBAECIF
求後序: GHDBEIFCA
示例3:
中序: BDCEAFHG
後序: DECBHGFA
求先序: ABCDEFGH
一般樹的存儲
連續存儲[完全二叉樹]
鍊式存儲
森林的存儲
連續存儲[完全二叉樹]
鍊式存儲
應用:
樹是資料庫中資料組織一種重要形式
作業系統字元京城的關系本身就是一棵樹
面向對象語言中類的繼承關系
赫夫曼樹
子產品三: 查找和排序
折半查找
排序
冒泡排序:(第一個和第二個比較,第二個和第三個比較,第三個和第四個比較,第四個和第五個比較....)
插入排序:(把第二個插入第一個某個位置,使前兩個有序,把第三個插入前兩個的某個位置,使前三個有序,把第四個插入前三個的某個位置,使前四個有序)
選擇排序:(從所有的資料中找一個最小的出來,放在第一個位置,然後從剩下的資料中找出最小的放在第二個位置,然後從剩下的資料中找出最小的資料放在第三個位置)
快速排序:(是對冒泡排序的一種改進,通過一趟排序将要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分别進行快速排序，整個排序過程可以遞歸
歸并排序:(歸并是先是兩個兩個排,使兩個有序,然後再四個四個排,使四個有序,….,整體排一次,使整體有序)
排序和查找的關系
排序是查找的前提
排序是重點
再次讨論什麼是泛型: 同一種邏輯結構,無論該邏輯結構實體存儲是什麼樣子的,我們可以對它執行形同的操作
面向過程與面向對象的差別:
面向過程側重于算法,面向對象側重于解決問題