數(shù)據(jù)結(jié)構(gòu)
1.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常用的有幾種饥瓷？各有什么特點(diǎn)舷丹？
數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)一般常用的有兩種 順序存儲(chǔ)結(jié)構(gòu) 和 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
-
順序存儲(chǔ)結(jié)構(gòu):
比如氓奈，數(shù)組翘魄，1-2-3-4-5-6-7-8-9-10，存儲(chǔ)是按順序的舀奶。再比如棧和隊(duì)列等
-
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu):
比如暑竟，數(shù)組，1-2-3-4-5-6-7-8-9-10，鏈?zhǔn)酱鎯?chǔ)就不一樣了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地址)-6(地址)-10(地址)但荤。每個(gè)數(shù)字后面跟著一個(gè)地址 而且存儲(chǔ)形式不再是順序
2.集合結(jié)構(gòu) 線性結(jié)構(gòu) 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu)
-
集合結(jié)構(gòu)
一個(gè)集合罗岖，就是一個(gè)圓圈中有很多個(gè)元素，元素與元素之間沒(méi)有任何關(guān)系 這個(gè)很簡(jiǎn)單
-
線性結(jié)構(gòu)
一個(gè)條線上站著很多個(gè)人腹躁。 這條線不一定是直的桑包。也可以是彎的。也可以是值的 相當(dāng)于一條線被分成了好幾段的樣子 （發(fā)揮你的想象力）纺非。 線性結(jié)構(gòu)是一對(duì)一的關(guān)系
-
樹(shù)形結(jié)構(gòu)
做開(kāi)發(fā)的肯定或多或少的知道xml 解析 樹(shù)形結(jié)構(gòu)跟他非常類(lèi)似哑了。也可以想象成一個(gè)金字塔。樹(shù)形結(jié)構(gòu)是一對(duì)多的關(guān)系
-
圖形結(jié)構(gòu)
這個(gè)就比較復(fù)雜了烧颖。他呢 無(wú)窮弱左。無(wú)邊 無(wú)向（沒(méi)有方向）圖形機(jī)構(gòu) 你可以理解為多對(duì)多 類(lèi)似于我們?nèi)说慕患P(guān)系
3.單向鏈表 雙向鏈表 循環(huán)鏈表
-
單向鏈表 A->B->C->D->E->F->G->H. 這就是單向鏈表 H 是頭 A 是尾 像一個(gè)只有一個(gè)頭的火車(chē)一樣 只能一個(gè)頭拉著跑 單向鏈表
-
雙向鏈表 雙向鏈表
-
循環(huán)鏈表
循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)炕淮，所不同的是拆火，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈鳖悠。發(fā)揮想象力 A->B->C->D->E->F->G->H->A. 繞成一個(gè)圈榜掌。就像蛇吃自己的這就是循環(huán) 不需要去死記硬背哪些理論知識(shí)。
4.數(shù)組和鏈表區(qū)別
-
數(shù)組
數(shù)組元素在內(nèi)存上連續(xù)存放乘综，可以通過(guò)下標(biāo)查找元素憎账；插入、刪除需要移動(dòng)大量元素卡辰，比較適用于元素很少變化的情況
-
鏈表
鏈表中的元素在內(nèi)存中不是順序存儲(chǔ)的胞皱，查找慢，插入九妈、刪除只需要對(duì)元素指針重新賦值反砌，效率高
5.堆、棧和隊(duì)列
堆
-
堆是一種經(jīng)過(guò)排序的樹(shù)形數(shù)據(jù)結(jié)構(gòu)萌朱，每個(gè)節(jié)點(diǎn)都有一個(gè)值宴树，通常我們所說(shuō)的堆的數(shù)據(jù)結(jié)構(gòu)是指二叉樹(shù)。所以堆在數(shù)據(jù)結(jié)構(gòu)中通尘郏可以被看做是一棵樹(shù)的數(shù)組對(duì)象酒贬。而且堆需要滿足一下兩個(gè)性質(zhì)：
1）堆中某個(gè)節(jié)點(diǎn)的值總是不大于或不小于其父節(jié)點(diǎn)的值；
2）堆總是一棵完全二叉樹(shù)翠霍。
堆分為兩種情況锭吨，有最大堆和最小堆。將根節(jié)點(diǎn)最大的堆叫做最大堆或大根堆寒匙，根節(jié)點(diǎn)最小的堆叫做最小堆或小根堆零如，在一個(gè)擺放好元素的最小堆中，父結(jié)點(diǎn)中的元素一定比子結(jié)點(diǎn)的元素要小，但對(duì)于左右結(jié)點(diǎn)的大小則沒(méi)有規(guī)定誰(shuí)大誰(shuí)小考蕾。
堆常用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列祸憋，堆的存取是隨意的，這就如同我們?cè)趫D書(shū)館的書(shū)架上取書(shū)肖卧，雖然書(shū)的擺放是有順序的夺衍，但是我們想取任意一本時(shí)不必像棧一樣，先取出前面所有的書(shū)喜命，書(shū)架這種機(jī)制不同于箱子沟沙，我們可以直接取出我們想要的書(shū)。
棧
棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表壁榕。我們把允許插入和刪除的一端稱為棧頂矛紫，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧牌里。棧的特殊之處在于它限制了這個(gè)線性表的插入和刪除位置颊咬，它始終只在棧頂進(jìn)行。
棧是一種具有后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)牡辽，又稱為后進(jìn)先出的線性表喳篇，簡(jiǎn)稱 LIFO（Last In First Out）結(jié)構(gòu)。也就是說(shuō)后存放的先取态辛，先存放的后取麸澜，這就類(lèi)似于我們要在取放在箱子底部的東西（放進(jìn)去比較早的物體），我們首先要移開(kāi)壓在它上面的物體（放進(jìn)去比較晚的物體）奏黑。
堆棧中定義了一些操作炊邦。兩個(gè)最重要的是PUSH和POP。PUSH操作在堆棧的頂部加入一個(gè)元素熟史。POP操作相反馁害，在堆棧頂部移去一個(gè)元素，并將堆棧的大小減一蹂匹。
棧的應(yīng)用—遞歸
隊(duì)列
隊(duì)列是只允許在一端進(jìn)行插入操作碘菜、而在另一端進(jìn)行刪除操作的線性表。允許插入的一端稱為隊(duì)尾限寞，允許刪除的一端稱為隊(duì)頭忍啸。它是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作昆烁，而在表的后端進(jìn)行插入操作吊骤，和棧一樣缎岗，隊(duì)列是一種操作受限制的線性表静尼。
隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，又稱為先進(jìn)先出的線性表，簡(jiǎn)稱 FIFO（First In First Out）結(jié)構(gòu)鼠渺。也就是說(shuō)先放的先取鸭巴，后放的后取，就如同行李過(guò)安檢的時(shí)候拦盹，先放進(jìn)去的行李在另一端總是先出來(lái)鹃祖，后放入的行李會(huì)在最后面出來(lái)。
6.輸入一棵二叉樹(shù)的根結(jié)點(diǎn)普舆，求該樹(shù)的深度恬口？
二叉樹(shù)的結(jié)點(diǎn)定義如下：
struct BinaryTreeNode
{
int m_nValue ；
BinaryTreeNode* m_pLeft;
BinarvTreeNode* m_pRight 沼侣；
}
- 如果一棵樹(shù)只有一個(gè)結(jié)點(diǎn)祖能，它的深度為1。
- 如果根結(jié)點(diǎn)只有左子樹(shù)而沒(méi)有右子樹(shù)蛾洛，那么樹(shù)的深度應(yīng)該是其左子樹(shù)的深度加1养铸；同樣如果根結(jié)點(diǎn)只有右子樹(shù)而沒(méi)有左子樹(shù)，那么樹(shù)的深度應(yīng)該是其右子樹(shù)的深度加1轧膘。
- 如果既有右子樹(shù)又有左子樹(shù)钞螟，那該樹(shù)的深度就是其左、右子樹(shù)深度的較大值再加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.輸入一課二叉樹(shù)的根結(jié)點(diǎn)鳞滨，判斷該樹(shù)是不是平衡二叉樹(shù)？
-
重復(fù)遍歷結(jié)點(diǎn)
先求出根結(jié)點(diǎn)的左右子樹(shù)的深度蟆淀，然后判斷它們的深度相差不超過(guò)1太援，如果否，則不是一棵二叉樹(shù)扳碍；如果是提岔，再用同樣的方法分別判斷左子樹(shù)和右子樹(shù)是否為平衡二叉樹(shù)，如果都是笋敞，則這就是一棵平衡二叉樹(shù)碱蒙。
-
遍歷一遍結(jié)點(diǎn)
遍歷結(jié)點(diǎn)的同時(shí)記錄下該結(jié)點(diǎn)的深度，避免重復(fù)訪問(wèn)夯巷。
方法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);
}
推薦文集
注明：內(nèi)容摘自網(wǎng)絡(luò)赛惩，如有侵權(quán)聯(lián)系小編刪除
