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

1.數(shù)據(jù)結(jié)構(gòu)的存儲一般常用的有幾種？各有什么特點(diǎn)？

數(shù)據(jù)結(jié)構(gòu)的存儲一般常用的有兩種 順序存儲結(jié)構(gòu) 和 鏈?zhǔn)酱鎯Y(jié)構(gòu)

• 順序存儲結(jié)構(gòu):

  比如，數(shù)組，1-2-3-4-5-6-7-8-9-10，存儲是按順序的。再比如棧和隊列等

• 鏈?zhǔn)酱鎯Y(jié)構(gòu):

  比如，數(shù)組，1-2-3-4-5-6-7-8-9-10，鏈?zhǔn)酱鎯筒灰粯恿?1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)。每個數(shù)字后面跟著一個地址 而且存儲形式不再是順序

2.集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹形結(jié)構(gòu) 圖形結(jié)構(gòu)

• 集合結(jié)構(gòu)

  一個集合，就是一個圓圈中有很多個元素，元素與元素之間沒有任何關(guān)系 這個很簡單

• 線性結(jié)構(gòu)

  一個條線上站著很多個人。 這條線不一定是直的。也可以是彎的。也可以是值的 相當(dāng)于一條線被分成了好幾段的樣子 （發(fā)揮你的想象力）。 線性結(jié)構(gòu)是一對一的關(guān)系

• 樹形結(jié)構(gòu)

  做開發(fā)的肯定或多或少的知道xml 解析 樹形結(jié)構(gòu)跟他非常類似。也可以想象成一個金字塔。樹形結(jié)構(gòu)是一對多的關(guān)系

• 圖形結(jié)構(gòu)

  這個就比較復(fù)雜了。他呢 無窮。無邊 無向（沒有方向）圖形機(jī)構(gòu) 你可以理解為多對多 類似于我們?nèi)说慕患P(guān)系

3.單向鏈表 雙向鏈表 循環(huán)鏈表

• 單向鏈表 A->B->C->D->E->F->G->H. 這就是單向鏈表 H 是頭 A 是尾 像一個只有一個頭的火車一樣 只能一個頭拉著跑
  單向鏈表

• 雙向鏈表
  雙向鏈表

• 循環(huán)鏈表

  循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯Y(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個環(huán)形的鏈。發(fā)揮想象力 A->B->C->D->E->F->G->H->A. 繞成一個圈。就像蛇吃自己的這就是循環(huán) 不需要去死記硬背哪些理論知識。

4.數(shù)組和鏈表區(qū)別

• 數(shù)組

  數(shù)組元素在內(nèi)存上連續(xù)存放，可以通過下標(biāo)查找元素；插入、刪除需要移動大量元素，比較適用于元素很少變化的情況

• 鏈表

  鏈表中的元素在內(nèi)存中不是順序存儲的，查找慢，插入、刪除只需要對元素指針重新賦值，效率高

5.堆、棧和隊列

堆

• 堆是一種經(jīng)過排序的樹形數(shù)據(jù)結(jié)構(gòu)，每個節(jié)點(diǎn)都有一個值，通常我們所說的堆的數(shù)據(jù)結(jié)構(gòu)是指二叉樹。所以堆在數(shù)據(jù)結(jié)構(gòu)中通常可以被看做是一棵樹的數(shù)組對象。而且堆需要滿足一下兩個性質(zhì)：

  1）堆中某個節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；

  2）堆總是一棵完全二叉樹。

• 堆分為兩種情況，有最大堆和最小堆。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆，在一個擺放好元素的最小堆中，父結(jié)點(diǎn)中的元素一定比子結(jié)點(diǎn)的元素要小，但對于左右結(jié)點(diǎn)的大小則沒有規(guī)定誰大誰小。

• 堆常用來實(shí)現(xiàn)優(yōu)先隊列，堆的存取是隨意的，這就如同我們在圖書館的書架上取書，雖然書的擺放是有順序的，但是我們想取任意一本時不必像棧一樣，先取出前面所有的書，書架這種機(jī)制不同于箱子，我們可以直接取出我們想要的書。

棧

• 棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。我們把允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧的特殊之處在于它限制了這個線性表的插入和刪除位置，它始終只在棧頂進(jìn)行。

• 棧是一種具有后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為后進(jìn)先出的線性表，簡稱 LIFO（Last In First Out）結(jié)構(gòu)。也就是說后存放的先取，先存放的后取，這就類似于我們要在取放在箱子底部的東西（放進(jìn)去比較早的物體），我們首先要移開壓在它上面的物體（放進(jìn)去比較晚的物體）。

• 堆棧中定義了一些操作。兩個最重要的是PUSH和POP。PUSH操作在堆棧的頂部加入一個元素。POP操作相反，在堆棧頂部移去一個元素，并將堆棧的大小減一。

• 棧的應(yīng)用—遞歸

隊列

• 隊列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊尾，允許刪除的一端稱為隊頭。它是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，和棧一樣，隊列是一種操作受限制的線性表。

• 隊列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為先進(jìn)先出的線性表，簡稱 FIFO（First In First Out）結(jié)構(gòu)。也就是說先放的先取，后放的后取，就如同行李過安檢的時候，先放進(jìn)去的行李在另一端總是先出來，后放入的行李會在最后面出來。

6.輸入一棵二叉樹的根結(jié)點(diǎn)，求該樹的深度？

二叉樹的結(jié)點(diǎn)定義如下：

struct BinaryTreeNode
{
    int m_nValue ；
    BinaryTreeNode* m_pLeft;
    BinarvTreeNode* m_pRight ；
}

• 如果一棵樹只有一個結(jié)點(diǎn)，它的深度為1。
• 如果根結(jié)點(diǎn)只有左子樹而沒有右子樹，那么樹的深度應(yīng)該是其左子樹的深度加1；同樣如果根結(jié)點(diǎn)只有右子樹而沒有左子樹，那么樹的深度應(yīng)該是其右子樹的深度加1。
• 如果既有右子樹又有左子樹，那該樹的深度就是其左、右子樹深度的較大值再加1。

int TreeDepth(TreeNode* pRoot)
{
    if(pRoot == nullptr)
        return 0;
    int left = TreeDepth(pRoot->left);
    int right = TreeDepth(pRoot->right);

    return (left>right) ? (left+1) : (right+1);
}

7.輸入一課二叉樹的根結(jié)點(diǎn)，判斷該樹是不是平衡二叉樹？

• 重復(fù)遍歷結(jié)點(diǎn)

  先求出根結(jié)點(diǎn)的左右子樹的深度，然后判斷它們的深度相差不超過1，如果否，則不是一棵二叉樹；如果是，再用同樣的方法分別判斷左子樹和右子樹是否為平衡二叉樹，如果都是，則這就是一棵平衡二叉樹。

• 遍歷一遍結(jié)點(diǎn)

  遍歷結(jié)點(diǎn)的同時記錄下該結(jié)點(diǎn)的深度，避免重復(fù)訪問。

方法1:

struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};

int TreeDepth(TreeNode* pRoot){
    if(pRoot==NULL)
        return 0;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    return left>right?(left+1):(right+1);
}

bool IsBalanced(TreeNode* pRoot){
    if(pRoot==NULL)
        return true;
    int left=TreeDepth(pRoot->left);
    int right=TreeDepth(pRoot->right);
    int diff=left-right;
    if(diff>1 || diff<-1)
        return false;
    return IsBalanced(pRoot->left) && IsBalanced(pRoot->right);
}

方法2：

bool IsBalanced_1(TreeNode* pRoot,int& depth){
    if(pRoot==NULL){
        depth=0;
        return true;
    }
    int left,right;
    int diff;
    if(IsBalanced_1(pRoot->left,left) && IsBalanced_1(pRoot->right,right)){
        diff=left-right;
        if(diff<=1 || diff>=-1){
            depth=left>right?left+1:right+1;
            return true;
        }
    }
    return false;
}

bool IsBalancedTree(TreeNode* pRoot){
    int depth=0;
    return IsBalanced_1(pRoot,depth);
} 

推薦文集

• 2020 高級iOS開發(fā)面試題（最新整理）

注明：內(nèi)容摘自網(wǎng)絡(luò)，如有侵權(quán)聯(lián)系小編刪除