99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記 1.概念

數(shù)據(jù)：

成都創(chuàng)新互聯(lián)公司是一家專業(yè)的成都網(wǎng)站建設(shè)公司，我們專注成都做網(wǎng)站、成都網(wǎng)站制作、成都外貿(mào)網(wǎng)站建設(shè)、網(wǎng)絡(luò)營銷、企業(yè)網(wǎng)站建設(shè)，友情鏈接，廣告投放為企業(yè)客戶提供一站式建站解決方案，能帶給客戶新的互聯(lián)網(wǎng)理念。從網(wǎng)站結(jié)構(gòu)的規(guī)劃UI設(shè)計到用戶體驗提高，創(chuàng)新互聯(lián)力求做到盡善盡美。

• 可輸入性
• 可識別性和處理性
• 符號集合

---

數(shù)據(jù)元素：

• 數(shù)據(jù)的基本單位
• 整體考慮

---

數(shù)據(jù)項：

• 最小單位

---

關(guān)鍵字：

• 主關(guān)鍵字：唯一識別
• 次關(guān)鍵字

---

數(shù)據(jù)對象：

• 同性質(zhì)的數(shù)據(jù)元素集合

---

數(shù)據(jù)結(jié)構(gòu)：

• 內(nèi)容：

  • 邏輯結(jié)構(gòu)：抽象的數(shù)據(jù)模型。用戶視圖，面向問題

    • 集合
    • 線性（1 to 1）
    • 樹（1 to n）
    • 圖（n to n）

  • 存儲結(jié)構(gòu)（物理）：邏輯結(jié)構(gòu)在計算機中的表示。面向計算機，實現(xiàn)視圖

    • 順序（相鄰元素物理位置相鄰）
    • 鏈?zhǔn)剑ㄏ噜徳刂羔槍崿F(xiàn)相鄰）
    • 散列（關(guān)鍵字定地址）
    • 索引

• 性質(zhì)：

  • 存在相互聯(lián)系
  • 數(shù)據(jù)元素集合

• 形式定義：（D，R）

  • D：數(shù)據(jù)元素有限集

  • R：D上的關(guān)系有限集

    D = { a , b , c , d }

    R = { ( a , b ) , ( a , c ) , ( b , d ) }

    

---

數(shù)據(jù)類型：（值 + 操作）DT

• 值的結(jié)合
• 值集上的操作

---

抽象數(shù)據(jù)類型：（數(shù)據(jù)結(jié)構(gòu) + 操作）ADT

• 數(shù)據(jù)結(jié)構(gòu)

• 其結(jié)構(gòu)上的操作

• 可用（D，S，P）表示

  • D：數(shù)據(jù)對象

  • S：D上關(guān)系集

  • P：對D的操作集

    ADT Complex{					//ADT 類型名{
        D = { e1 , e2 },			//	  數(shù)據(jù)對象
        R = {< e1 , e2 >},			//	  數(shù)據(jù)關(guān)系
        InitComplex( &Z , v1 , v2 )	//	  基本操作
    }ADT Complex					//	  }ADT 類型名

---

算法：指令的有限序列

• 有窮
• 確定(無二義性)
• 可行
• 輸入(可以沒有輸入)
• 輸出

---

算法分析:

• 時間復(fù)雜度
• 空間復(fù)雜度

---

2.算法分析

算法分析-----大"O"符號

• 若兩個正常數(shù) c , n0 ,對任意n >= n0 都有T(n)<= c × f(n), 則稱T(n) = O(f(n))

• 若
  A ( n ) = a m n m + a m ? 1 n m ? 1 + . . . a 0 A(n) = a_mn^m + a_{m-1}n^{m-1} + ...a_0 A(n)=am?nm+am?1?nm?1+...a0?
  是一個m次多項式,則A(n) = O(n^m).

  • 計算時間復(fù)雜度時,可忽略最高和最低的 次冪系數(shù)

• 算法執(zhí)行時間 = Σ(基本操作(i)的執(zhí)行次數(shù)x基本操作(i)的執(zhí)行時間)

• 算法空間復(fù)雜度: 算法執(zhí)行所需空間的增長率

  • S(n) = O(g(n))
  • 若所需額外空間是常數(shù),稱"原地工作"
  • 程序本身所占空間
  • 輸入數(shù)據(jù)所占空間
  • 輔助變量所占空間

---

3.線性表

定義:

• n(n >= 0)個具有相同類型的數(shù)據(jù)元素的有限序列

---

長度:

• 線性表中數(shù)據(jù)元素個數(shù)

---

特征:

• 唯一"第一元素"
• 唯一"最后元素"
• 除最后元素,均有唯一后繼
• 出第一元素,均有唯一前驅(qū)
• 線性表的基地址即起始地址

---

線性表鏈?zhǔn)酱鎯?/p>

任意存儲單元存放線性表元素,無連續(xù)性(淡化"位序")

• 便于插入,刪除的操作

• 邏輯相鄰,物理未必相鄰,即"鏈?zhǔn)酱鎯?

• 節(jié)點:

  data(數(shù)據(jù)域)	Next(指針域)

• 單鏈表:表節(jié)點中只包含一個指針域

---

• 頭指針: 指向鏈表第一個節(jié)點的指針
• 頭節(jié)點: 通常在單鏈表前加一節(jié)點
• 首節(jié)點: 第一個元素節(jié)點
• 尾節(jié)點: 最后一個元素節(jié)點

---

查找（按位查找）

• 刪除單鏈表元素時，只要改前節(jié)點指針即可，但要注意釋放不用的內(nèi)存
• 由于順序存取結(jié)構(gòu)，為找第i個元素，必須先找到第i-1個元素

templateT linklist::GetElem(int i){
        P = Head->next;		//工作指針（首節(jié)點），也可頭節(jié)點
        j = 1;				//計數(shù)器，初始為1（首節(jié)點），若頭節(jié)點，為0
       	while(p && j< i){  //順位工作指針，直至i
            P = P->next;
            j++;
        }
        if(!P || j >i){	//空表或i<0或i>表長
            throw "位置"	  //查找位置不合理
        }else{
            return P->data;
        }
    }						//O(n)

---

插入

頭插法：每次新申請節(jié)點放在“頭節(jié)點”后

templatevoid LinkList::CreatList(int n){
        for(int i = 1;i<= n;i++){
            s = new Node;
            cin>>s->data;
            s->next = head->next
                head->next = s;
        }
    }

尾插法：保證工作指針指向最后節(jié)點，方便插入

templatevoid LinkList::CreatList(int n){
        Node*P,*S;			//工作指針，P指向尾節(jié)點
        P = Head;
        for(int i =1，i<= n;i++){
            s = new Node;
            cin>>s->data;
            s->next = p->next;	//新節(jié)點鏈插入表尾
            p->next = s;
            p = s;
        }
    }

---

4.鏈表

循環(huán)鏈表：終點指針指向head

雙向鏈表

單鏈中每個節(jié)點再設(shè)置一個指向其前驅(qū)節(jié)點的指針域

• 空間換時間

---

靜態(tài)鏈表

用數(shù)組描述鏈表，包括：

• data域：存放數(shù)據(jù)
• next域：存放該元素后繼所在數(shù)組下標(biāo)
• 其中0單位的next存放首元素下標(biāo)

• 缺點：

  • 沒有解決連續(xù)存儲分配帶來的表長難以確定
  • 其還需要維護一個空閑鏈
  • 不可隨機存儲

• 間接尋址

  • 存儲不相鄰，但地址存儲位置相鄰，可隨機存取，但仍存在表廠難以確定的情況

---

5.順序存儲和鏈?zhǔn)酱鎯?p>順序存儲

• 優(yōu)點：
  • 隨機存取
  • 無需為表示邏輯關(guān)系占用額外內(nèi)存（指針）
• 缺點：
  • 容量要先固定
  • 不方便刪除、移動

---

鏈?zhǔn)酱鎯?/p>

• 優(yōu)點：
  • 方便刪除、移動
  • 無需先頂容量
• 缺點：
  • 只可順序訪問
  • 存儲密度低

---

6.棧

• 棧頂指向an的上方
• 后進先出
• 出入棧要檢查上下是否溢出

---

常用操作

- InitStack(&S)		//初始化
- DestroyStack(&S)	//銷毀
- Push(&S,e)			//入棧
- Pop(&S)				//出棧
- GetTop(S)			//獲取棧頂元素
- StackEmpty(S)		//測棧空
- ClearStack(&S)		//清空棧

---

順序棧

templateclass SqStack{
    Private:
	    T *base;			//棧底指針
    	int top;			//棧頂
	    int stackSize;		//棧容量
    public:...
}

---

鏈棧

不帶頭結(jié)點

templatestruct Node{
    T data;
    Node*next;
}

---

順序棧vs鏈棧

時間：出入棧均為常數(shù)級

時間：

• 順序棧：容量受限制
• 鏈棧：因指針需要額外存儲空間

---

鏈棧特點

• 無棧滿問題，空間可擴充
• 插入與刪除僅在棧頂執(zhí)行
• 鏈棧棧頂在鏈頭
• 適合多棧操作

---

7.隊列

基本操作

- T* base;			//存儲空間基址
- int front;		//隊頭指針
- int rear;			//隊尾指針
- queueSize;		//隊容量
- InitQueue(&Q)		//初始化
- DestroyQueue(&Q)	//銷毀
- GetQueue(Q)		//獲取頭元素
- EnQueue(&Q,e)		//入隊
- DeQueue(&Q,e)		//出隊
- QueueEmpty()		//判斷隊空
- QueueFull()		//判斷隊滿
- ClearQueue();		//清空隊列
- QueueTranverse();	//遍歷隊列

---

**特點: **

• 有頭空節(jié)點
• 只允許在表的一端進行插入，而在另一端刪除元素的線性表
• 先進先出
• 假溢出：數(shù)組低端根據(jù)“先進先出”產(chǎn)生前空閑空間，但后端已滿的現(xiàn)象，通過循環(huán)隊列（頭尾相接）解決

---

鏈隊

僅在表頭刪除和表尾插入的單鏈表

---

循環(huán)隊列

---

循環(huán)棧

8.串相關(guān)

概念

• 串：零或多個字符組成，有限序列，一串字符，即S1S2…Sn
• 空串：零個字符，即NULL
• 空格串：空格組成的串
• 字串：主串中任意連續(xù)字符組成
• 空串是任何串的子串

---

串匹配

• 結(jié)果：字串第一字符在主串中的位序
• KMP：僅子串移動，O(n+m)
• BF：主，子串均多次回溯，最好O(n+m)。最差O(n*m)

---

9.矩陣壓縮存放

類型

• 對稱矩陣：Aij = Aji
• 三角矩陣：帶寬、奇
• 對角矩陣
• 稀疏矩陣:e<= 0.05 e = 非零元個數(shù)/元素個數(shù)
• 三對角矩陣

---

10.廣義表

• 數(shù)據(jù)元素有相對次序
• 長度：最外層包含元素個數(shù)
• 深度：括號重數(shù)
• 可以是一個遞歸表，深度無窮，長度有限
• 可分為
  • 表頭Head（）=
  • 表尾：Tail（） = （ ， ，）
• 表頭可為原子或表
• 表尾一定是表

---

11.樹

• n個有限數(shù)據(jù)元素集合
• n = 0時，為空樹
• 根節(jié)點：先祖，無前驅(qū)
• 子樹：根節(jié)點子樹
• 節(jié)點的度：某節(jié)點所擁有的子樹個數(shù)
• 樹的度：樹中各節(jié)點度的大值
• 葉子節(jié)點：終端節(jié)點，無子代
• 分支節(jié)點：非終端節(jié)點
• 孩子，雙親，兄弟
• 祖先，后代
• 路徑長度：經(jīng)過的邊數(shù)
• 層數(shù)：根節(jié)點為1
• 有序樹，無序樹：若一棵樹中節(jié)點子樹從左向右有次序，為有序樹
• 森林：樹的集合，可謂0
• Tree = （root，F(xiàn)）

---

二叉樹

根的元素，分叉為左子樹，右子樹。子樹數(shù)量<=2（大二分叉）

滿二叉樹

• 葉子只出現(xiàn)在最下一層（深度相同）
• 度只為0或2

完全二叉樹

• 在滿二叉樹中，從最后節(jié)點開始，連續(xù)去任意個節(jié)點，即為一顆完全二叉樹

平衡二叉樹

• AVL
• |左子樹深度 - 右子樹深度|<= 1
• 平衡因子：左子樹高度 - 右子樹高度 = -1 or 0 or -1
• 按中序遍歷會是一個從小到大的排列

---

性質(zhì)

• 一棵非空二叉樹的第i層上支隊2^(i-1)個節(jié)點
• 深度為k的而擦函數(shù)中，最多有2^k-1個節(jié)點
• 對于非空二叉樹，若葉子節(jié)點數(shù)n0，度為2的節(jié)點度為n2，則n0 = n2 +1
• 具有n個節(jié)點的完全而擦函數(shù)的深度為log2n +1
• 對于具有n個節(jié)點而擦函數(shù)，編號1~n；對于任意的i
  • if（i >1）,則i的節(jié)點的雙親節(jié)點序號為（i/2）
  • if（i = 1），則i為根節(jié)點
  • if（2i<= n）,則i的節(jié)點的左孩子節(jié)點序號為2i
  • if（2i >n）,則i的節(jié)點無左孩子
  • if（2i + 1<= n）,則i的節(jié)點的右孩子節(jié)點序號為2i+1
  • if（2i + 1 >n ）,則i的節(jié)點無右孩子
• 二叉樹的順序存儲結(jié)構(gòu)一般僅存“完全二叉樹”
• 三叉鏈表：祖宗節(jié)點、左子樹、數(shù)據(jù)、右子樹

---

遍歷

• 先序：根節(jié)點訪問先后
• 中序：默認(rèn)從左至右
• 后序
• 層序遍歷：第一層開始，逐層訪問，從上至下，從左至右

---

線索二叉樹

• 線索：序列中的第一個（前驅(qū)）和后一個（后繼）
• 包含“線索”的存儲結(jié)構(gòu)，“線索鏈表”
• 若有左孩子，則無前驅(qū)指向（二占一）
• 若有右孩子，則無后繼指向（二占一）

---

赫夫曼（哈夫曼）樹

• 節(jié)點路徑長度：節(jié)點間分支個數(shù)
• 樹的路徑長度：根到每個節(jié)點路徑長度和
• 樹的帶權(quán)路徑長度：書中所有葉子節(jié)點的帶權(quán)路徑之和WPL
• WPL最小的二叉樹為“最優(yōu)二叉樹”，“哈夫曼樹”
• 權(quán)值越大的葉子節(jié)點越靠近根節(jié)點
• 只有度為0（葉子）或2（分支）的節(jié)點

---

赫夫曼編碼

• 等長編碼：一組對象的二進制位串的長度相等
• 前綴編碼：一組編碼中任一編碼都不是其他任何一個編碼的前綴
  • 保證了解碼時不會有多種可能
• 規(guī)定赫夫曼樹左分支代表0.右分支為1，從根節(jié)點到每個葉子節(jié)點所經(jīng)過的路徑組成01序列為葉子編碼

---

樹轉(zhuǎn)二叉樹：

• 左是孩子，右是兄弟

---

樹遍歷

• 先根遍歷：先訪問根節(jié)點，再依次訪問各子樹
• 后根遍歷：先訪問子樹
• 樹不動

---

森林遍歷

• 先序遍歷：先訪問森林中第一棵樹的根節(jié)點，即依次從左至右隊森林中每顆樹進行先根遍歷
• 中序遍歷：依次從左至右隊森林中每一顆樹進行后根遍歷

---

12.圖

• Graph = （V，E），V表示頂點，E表示邊集
• 無向圖，有向圖，無向網(wǎng)，有向網(wǎng)

鄰接點：

• 邊的兩點互為鄰接點

有向完全圖：

• 任意兩頂點間都有方向互相反的兩條弧相連接
• n(n-1)條邊

無向完全圖

• 任意兩頂點間只有一條邊相連接
• [n(n-1)]/2條邊
• 稠密圖，稀疏圖

度：

• 頂點邊數(shù)
• 出度、入度

權(quán)：

• 網(wǎng)

子圖：

• 完全繼承于父圖

連通圖：

• 圖中任意兩點都有路徑相連接

連通分量：

• 非連通圖中極大連通子圖

強連通圖：

• 任意兩頂點間存在一條有向路徑

---

圖生成樹

• n個頂點，e條邊
• 其中n個頂點和n-1條邊構(gòu)成一個極小的連通子圖為生成樹

---

圖的存儲

• 鄰階矩陣
  • A[ i ] [ j ] = 1 (vi,vj)有邊
  • A[ i ] [ j ] = 0 (vi,vj)無邊
  • 無向圖形成矩陣是對稱矩陣
  • 矩陣中同一元素行和列”1“的大量數(shù)為度數(shù)
  • 網(wǎng)圖即代換”1“的值
• 鄰接表
  • 無向圖：i的度為邊表中節(jié)點個數(shù)
  • 有向圖：節(jié)點數(shù)為出度數(shù)（逆表中為入度）
  • 網(wǎng)圖中添加域量賦權(quán)

---

圖的遍歷

• 深度優(yōu)先：棧式（返回）
• 廣度優(yōu)先：隊列式（不返回）

---

關(guān)節(jié)點

• 若一個節(jié)點丟失，圖出現(xiàn)多個連通分量，則是

重連通圖

• 無關(guān)節(jié)點

最小生成樹

• 無向連通圖生成樹不唯一（WPL相同）
• 有且僅有n-1條邊
• Prim：點擴散式
• kruskal：小組織連接成大組織

最短路徑

• 一個源點到其余點
• 此路徑上，必定只含一條弧，且權(quán)值最小
• Dijkstra：a-b,a-c,a-d（點->線->面）
• Floyd:成鄰接矩陣，所有可能路徑

DAG圖

• 有向無環(huán)圖

AOV網(wǎng)與拓?fù)渌惴?/p>

• 輸出入度為0的節(jié)點
• 刪除該點與其邊
• 重復(fù)

關(guān)鍵路徑：

• 始終點時間大的路徑
• e[ i ] = l[ i ]的路徑
  • e[ i ]活動最早開始時間
  • l[ i ]活動最晚開始時間

---

13.查找

有序折半查找

• 有序、順序存儲
• 流程：
  • 查找值與中間元素關(guān)鍵字比較：
  • 相等則成功
  • 小于則左半?yún)^(qū)繼續(xù)折半查找（不包括中點）
  • 大于則右半?yún)^(qū)
  • T(n) = O(log2n)

哨兵順序查找

• T(n) = O(n)

動態(tài)查找

• 又叫樹表查找
• 流程：
  • 用二叉樹排序樹（BST）
  • 左子樹上節(jié)點均小于根節(jié)點
  • 左子樹上節(jié)點均大于根節(jié)點
  • 左右子樹也遵循上述規(guī)則
• 最好Tn = O(log2n)
• 最壞Tn = O(n)

14.哈希函數(shù)

散列函數(shù)

特點：

• 函數(shù)簡單,速度快
• 計算出的地址，應(yīng)在哈希地址集中大致均勻分布
• 解決沖突方案

---

常用哈希函數(shù)

• 直接定址
  • Hash(k) = a * k + b
  • 線性哈希
  • 不會發(fā)生沖突
• 除留余數(shù)
  • Hash(k) = k mod p
  • p一般選質(zhì)數(shù)
  • 若表長為m，則要求p<= m
  • 一定有沖突
• 乘余取整
• 數(shù)字分析
• 平方取中
• 折疊

---

處理沖突

• 開放定址
  • 關(guān)鍵字所得hash地址沖突，則區(qū)尋找下一個空的哈希地址
  • 線性：向后探測是否為空
  • 二次探測：1^2,-12,2^2,-22···左右平方探測
  • 雙哈希：偽隨機數(shù)列
• 建立一個公共溢出區(qū)
  • 一個基本表
  • 一個溢出表

---

哈希表查找分析

• 比較次數(shù)取決于產(chǎn)生沖突的多少
• 沖突產(chǎn)生因素：
  • 哈希函數(shù)是否平均
  • 處理沖突的方法
  • 填滿因子α = 元素個數(shù)/表長
  • 哈希表平均查找長度僅取決于填滿因子

---

15.排序

• 穩(wěn)定性：相同關(guān)鍵碼元素間位置關(guān)系是否受排序影響
• 內(nèi)排序（僅在內(nèi)存）
• 外排序
• 單鍵排序
• 多鍵排序
• 是否基于比較

---

內(nèi)排序

• 插入
  • 直接、折半、表插入、希爾
• 交換
  • 快速排序、冒泡
• 選擇
  • 簡單選擇、樹形、堆
• 歸并
  • 二路歸并

---

三大經(jīng)典排序方法

• 時間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)
• 均穩(wěn)定

---

快速排序

• 樞軸
• 左右排形成類似于”樹“的結(jié)構(gòu)
• 時間復(fù)雜度：O(nlog2n) ~ O(n^2)
• 不穩(wěn)定
• 最壞情況時就是冒泡排序
• 輔助存儲空間：O(log2n) ~ O(n)

---

堆排序

• 定義滿足Ki< K2i且Ki< K(2i+1)
• 或定義滿足Ki >K2i且Ki >K(2i+1)
• 是一種具有完全二叉樹的性質(zhì)：根節(jié)點小于孩子節(jié)點

---

16.表達式

前綴表達式

• 構(gòu)造樹，從右向左取第一個最低級運算作為根節(jié)點
• 左右子樹再重復(fù)操作

---

后綴表達式

• 最近的兩數(shù)與最近的符號進行運算
• 重復(fù)操作
  hash地址沖突，則區(qū)尋找下一個空的哈希地址
  • 線性：向后探測是否為空
  • 二次探測：1^2,-12,2^2,-22···左右平方探測
  • 雙哈希：偽隨機數(shù)列
• 建立一個公共溢出區(qū)
  • 一個基本表
  • 一個溢出表

---

哈希表查找分析

• 比較次數(shù)取決于產(chǎn)生沖突的多少
• 沖突產(chǎn)生因素：
  • 哈希函數(shù)是否平均
  • 處理沖突的方法
  • 填滿因子α = 元素個數(shù)/表長
  • 哈希表平均查找長度僅取決于填滿因子

---

15.排序

• 穩(wěn)定性：相同關(guān)鍵碼元素間位置關(guān)系是否受排序影響
• 內(nèi)排序（僅在內(nèi)存）
• 外排序
• 單鍵排序
• 多鍵排序
• 是否基于比較

---

內(nèi)排序

• 插入
  • 直接、折半、表插入、希爾
• 交換
  • 快速排序、冒泡
• 選擇
  • 簡單選擇、樹形、堆
• 歸并
  • 二路歸并

---

三大經(jīng)典排序方法

• 時間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)
• 均穩(wěn)定

---

快速排序

• 樞軸
• 左右排形成類似于”樹“的結(jié)構(gòu)
• 時間復(fù)雜度：O(nlog2n) ~ O(n^2)
• 不穩(wěn)定
• 最壞情況時就是冒泡排序
• 輔助存儲空間：O(log2n) ~ O(n)

---

堆排序

• 定義滿足Ki< K2i且Ki< K(2i+1)
• 或定義滿足Ki >K2i且Ki >K(2i+1)
• 是一種具有完全二叉樹的性質(zhì)：根節(jié)點小于孩子節(jié)點

---

16.表達式

前綴表達式

• 構(gòu)造樹，從右向左取第一個最低級運算作為根節(jié)點
• 左右子樹再重復(fù)操作

---

后綴表達式

• 最近的兩數(shù)與最近的符號進行運算
• 重復(fù)操作

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享標(biāo)題：數(shù)據(jù)結(jié)構(gòu)筆記-創(chuàng)新互聯(lián)
當(dāng)前網(wǎng)址：http://www.ef60e0e.cn/article/djopds.html