上一篇文章程序員面試闖關(guān)（一）：字符串匹配+排序+查找列舉說明了各種常見的排序算法等算法基礎(chǔ)，這里，主要分析下數(shù)據(jù)結(jié)構(gòu)相關(guān)的基礎(chǔ)和注意點。
一、線性表
1. 數(shù)組（順序存儲結(jié)構(gòu)）
- 效率分析
- 查找：O(1)【數(shù)組的存儲是連續(xù)內(nèi)存空間】
- 插入和刪除：
- 最好情況：O(1)
①插入到最后一個位置 ②刪除最后一個元素 - 最壞情況：O(n)
①插入到第一個位置 ②刪除第一個元素 - 平均情況：O((n-1)/2) = O(n)
- 最好情況：O(1)
- 整體分析：
- 適合：存數(shù)據(jù)，取數(shù)據(jù)【無須為了表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間，可以快速地存取表中任一位置的元素】
- 不適合：插入和刪除數(shù)據(jù)【需要頻繁移動元素】
2. 鏈表（鏈式存儲結(jié)構(gòu)）
- 頭指針與頭結(jié)點的異同：
- 頭指針：
- 是指鏈表指向第一個結(jié)點的指針，若鏈表有頭結(jié)點，則是指向頭結(jié)點的指針。
- 頭指針具有標識作用，所以常用它來冠以鏈表的名字
- 無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。
- 頭結(jié)點：
- 頭結(jié)點是為了操作的統(tǒng)一和方便而設(shè)定的，放在第一個元素的結(jié)點之前，其數(shù)據(jù)域一般無意義（一般用于存放鏈表的長度）
- 有了頭結(jié)點，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與其他結(jié)點的操作就統(tǒng)一。
- 頭結(jié)點不一定是鏈表的必要元素。
- 效率分析
- 查找：O(n)
- 插入和刪除：O(1)
- 優(yōu)勢：
- 相比于數(shù)組：數(shù)組需要預(yù)先分配存儲空間，容易造成空間浪費和溢出。而單鏈表不需要分配空間，元素個數(shù)也不受限制。
- 細分
- 單鏈表：就是上述這種，內(nèi)存空間分配不連續(xù)。
-
靜態(tài)鏈表：【就是為了給沒有指針的語言設(shè)計的方案
】用數(shù)組去模擬鏈表，內(nèi)存空間。具體實現(xiàn)：設(shè)計一個結(jié)構(gòu)體，創(chuàng)建一個結(jié)構(gòu)體數(shù)組，這個數(shù)組很長，足夠你用了，然后，用兩個結(jié)構(gòu)體實例，一個作為數(shù)組頭，一個作為數(shù)組尾，用于說明實際的數(shù)組長度：typedef struct{ ElemType data; int cur; //表示下一個元素的下標（一般會指向它下一個位置，如果是末尾，則指向‘0’） }- 優(yōu)點：要插入或刪除元素，只需要先在數(shù)組末尾添加這個元素，然后，修改這個元素的cur和插入點元素的cur即可。避免了元素移位的復雜過程。
- 缺點：表長度難以確定的問題；失去了數(shù)組的隨機存取快的特性。
- 循環(huán)鏈表
- 雙向鏈表
二、棧和隊列
1. 棧
- 概念：棧是限定僅在表尾進行插入和刪除操作的線性表。
- 結(jié)構(gòu)：
- 順序結(jié)構(gòu)（一個棧）：
typedef struct{ int data[MAXSIZE]; int top; //表示棧頂下標（-1表示：棧空） }Stack- 順序結(jié)構(gòu)（兩個棧共享空間）：
typedef struct{ int data[MAXSIZE]; int topA; //表示棧A的棧頂下標（-1表示：?？眨? int topB; //表示棧B的棧頂下標（MAXSIZE 表示：棧空） }DoubleStack- 鏈式結(jié)構(gòu)：
typedef struct StackNode{///棧元素 int data; struct StackNode *next; }StackNode , *LinkStackPtr; typedef struct LinkStack{//鏈棧 LinkStackPtr top;///指向棧頂?shù)闹羔? int count;//棧大?。?表示：空棧） }LinkStack;
2. 隊列
- 概念：隊列是只允許一端進行插入操作，另一端進行刪除操作的線性表。
-
循環(huán)隊列：
- 目的：為了解決存儲空間的循環(huán)利用的問題。
- 性質(zhì)：
- 隊列滿的條件是：(rear+1)%QueueSize == front 【其中‘rear’表示隊尾，‘font’表示隊頭】
- 結(jié)構(gòu)如下：
typedef struct{ int data[MAXSIZE]; int front; //頭指針（初始化為：0） int rear; //尾指針（初始化為：0，隊列不空，就指向隊列最后一個元素的下一個位置） } - 操作：
- 入隊：
Q->rear = (Q->rear + 1)%MAXSIZE;- 出隊：
Q->front = (Q->front + 1)%MAXSIZE;
-
鏈隊列：
- 結(jié)構(gòu)：
typedef struct QNode{ int data; struct QNode *next; }QNode , *QueuePtr; typedef struct{ QueuePtr front, rear; /*隊頭，隊尾指針*/ }
- 結(jié)構(gòu)：
三、樹
1. 各種概念重溫
- 結(jié)點層次（Level）：根為第一層，根的孩子為第二層。
- 其雙親在同一層的結(jié)點互為堂兄弟。
- 森林：m（m>=0）課互不相交的樹的集合。
2. 一般樹的存儲結(jié)構(gòu)
-
雙親表示法【缺點：找父親O(1),找孩子O(n)】
其實是對象數(shù)組（包含其父結(jié)點的下標）
typedef struct PTNode{ int data; int parent;//父結(jié)點的下標，‘-1’表示沒有父結(jié)點，本身是根結(jié)點 } typedef struct{ PTNode nodes[100]; //結(jié)點數(shù)組 int r, n; //根位置 ， 結(jié)點數(shù) } -
孩子表示法【缺點：①找父親O(n),找孩子O(1) ②要加孩子，結(jié)構(gòu)需要改，遍歷更加復雜】
其實是將n個結(jié)點用一個長度為n的結(jié)點數(shù)組裝起來，每個結(jié)點的子結(jié)點用一條屬于這個結(jié)點的單鏈表來表示，如果是葉子結(jié)點，那么則沒有子鏈表，它的firstchild為null。
typedef struct CTNode{ ///孩子結(jié)點 int child; struct CTNode *next; } *ChildPtr; typedef struct{ ////表頭結(jié)構(gòu) int data; ChildPtr firstchild; } CTBox; typedef struct{ /////樹結(jié)構(gòu) CTBox nodes[100]; //結(jié)點數(shù)組 int r,n; ///根位置和結(jié)點數(shù) } -
孩子兄弟表示法【缺點，還是難找到父結(jié)點 ，如果要改，需要加多一個指針】
一個結(jié)構(gòu)體，兩個指針（一個縱向，一個橫向），相當于他的“長子”和“二弟”。
typedef struct CSNode{ int data; struct CSNode *firstChild;///它的第一個孩子結(jié)點 struct CSNode *rightChild;///它本身的兄弟結(jié)點 }
3. 二叉樹
-
相關(guān)概念：
- 斜樹：所有結(jié)點都在左子樹 稱為左斜樹；所有結(jié)點都在右子樹 稱為右斜樹。
- 完全二叉樹的特點：
- 葉子結(jié)點只能在最下兩層。
- 最下層葉子一定集中在左部連續(xù)位置。
- 如果結(jié)點度數(shù)為1，此結(jié)點必定只有左子樹。
- 同樣結(jié)點數(shù)的二叉樹，完全二叉樹的深度最小。
- 二叉樹的性質(zhì)：
- 在二叉樹的第i層上至多有2^(i-1)個結(jié)點
- 深度為k的二叉樹至多有2^k -1個結(jié)點
- 任意一顆二叉樹，n2（度數(shù)為2的結(jié)點） = n0（度數(shù)為0的結(jié)點）-1
- 樹的邊數(shù)（也叫：分支線總數(shù)）和結(jié)點數(shù)的關(guān)系：邊數(shù) = n-1 = n1+2*n2
-
具有n個結(jié)點的完全二叉樹的深度為
表示：不大于logn的最大整數(shù)+1
-
如果放在一個數(shù)組中，那么，父子結(jié)點之間的下標關(guān)系如下：
二叉樹相關(guān)操作
-
線索二叉樹
- 定義：因為二叉鏈表只能知道某個結(jié)點的左右孩子結(jié)點的地址，而不知道它在遍歷時的一個‘前驅(qū)’和‘后繼’結(jié)點是誰。于是，將原來的結(jié)點結(jié)構(gòu)中的左右孩子成員，在判斷為null的情況下， 變?yōu)檫@個結(jié)點的前驅(qū)和后繼結(jié)點。這樣，一來充分利用了空間，二來方便了我們查找某個結(jié)點的前驅(qū)和后繼結(jié)點。
- 結(jié)構(gòu)：
typedef enum {LInk , Thread} PointerTag; //Link == 0 表示指向左右孩子，Thread==1 表示指向前驅(qū)和后繼結(jié)點 typedef struct BiThrNode{ int data; //數(shù)據(jù) struct BiThrNode *lchild , *rchild;//左右孩子指針（或者前驅(qū)后繼結(jié)點） PointerTag LTag; //左標志 PointerTag RTag; //右標志 } BiThrNode, *BiThrTree; -
中序遍歷示例
- 意義
如果實際中所用的二叉樹需要經(jīng)常遍歷或查找結(jié)點時需要某種遍歷序列中的前驅(qū)和后繼，那么采用線索二叉鏈表的存儲結(jié)構(gòu)是不錯選擇。
-
二叉樹、數(shù)、森林之間的轉(zhuǎn)換
-
樹轉(zhuǎn)二叉樹：
-
森林轉(zhuǎn)二叉樹：
-
二叉樹轉(zhuǎn)樹：
-
二叉樹轉(zhuǎn)森林：
-
樹轉(zhuǎn)二叉樹：
哈夫曼樹
從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成兩個結(jié)點之間的路徑，路徑上的分支數(shù)目稱作 路徑長度。【帶權(quán)路徑長度WPL最小的二叉樹，稱作 赫夫曼樹】
四、圖
1. 定義：G(V【頂點集合】, E【邊的集合】)
2. 相關(guān)概念
- 完全圖：任意兩個點之間有邊的圖
- 簡單圖：無重復的邊或頂點到自身的邊
- 度：頂點的邊數(shù)
3. 圖的存儲結(jié)構(gòu)
- 鄰接矩陣
- 存儲方式：用兩個數(shù)組來表示圖。一個一維數(shù)組存儲圖中頂點信息，一個二維數(shù)組存儲圖中的邊或弧的信息。
- 優(yōu)勢：
- 容易判斷兩個頂點是否有邊
- 要知道某個頂點的度，其實就是這個頂點vi 在鄰接矩陣中的第i行（或第i列）的元素之和。
- 求頂點vi的所有鄰接點，只需要遍歷矩陣第i行。
-
圖解（無向連通圖為例）：
- 鄰接表
-
存儲方式：用兩個對象結(jié)構(gòu)，一個來表示頂點，另一個則表示該頂點的鄰接頂點權(quán)值信息。每個頂點對象，都是一個鏈表的表頭結(jié)點，他后面接著的是他的所有鄰接頂點的信息列表。如下圖，表示每一個頂點的鏈表結(jié)構(gòu)模型。
每一個頂點的鄰接表
-
鄰接矩陣和鄰接表的比較：
- 當圖中結(jié)點數(shù)目較小且邊較多時，采用鄰接矩陣效率更高。
- 當節(jié)點數(shù)目遠大且邊的數(shù)目遠小于相同結(jié)點的完全圖的邊數(shù)時，采用鄰接表存儲結(jié)構(gòu)更有效率。
五、二叉樹和圖的各個?？挤椒ùa匯總（代碼可直接復制運行）
1. 二叉樹各個方法
package basic.tree;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
/**
* 二叉樹
* Created by androidjp on 16/8/17.
*/
public class BiTree {
public String data;
public BiTree left;
public BiTree right;
public static Scanner scanner = new Scanner(System.in);
/**
* 以 先序遍歷 的順序進行元素插入
*
* @return 創(chuàng)建好的二叉樹
*/
public static BiTree createTree() {
String s = scanner.next();
char ch = s.charAt(0);
if (ch == '#') {
return null;
}
BiTree root = new BiTree();
root.data = s;
root.left = null;
root.right = null;
//遞歸進行插入
root.left = createTree();
root.right = createTree();
return root;
}
/**
* 先序遍歷二叉樹
*
* @param tree
*/
public static void preTraverse(BiTree tree) {
if (tree == null)
return;
System.out.print(tree.data + " ");
preTraverse(tree.left);
preTraverse(tree.right);
}
/**
* 中序遍歷二叉樹
*
* @param tree
*/
public static void orderTraverse(BiTree tree) {
if (tree == null)
return;
orderTraverse(tree.left);
System.out.print(tree.data +" ");
orderTraverse(tree.right);
}
/**
* 后序遍歷二叉樹
*
* @param tree
*/
public static void postTraverse(BiTree tree) {
if (tree == null)
return;
postTraverse(tree.left);
postTraverse(tree.right);
System.out.print(tree.data + " ");
}
/**
* 二叉樹的深度優(yōu)先遍歷
* 【二叉樹不同于圖,圖需要標記元素是否已經(jīng)被遍歷過,因為可能存在環(huán),而樹則不用考慮環(huán)的問題,于是少了判斷這一步】
* 使用棧 遍歷
*
* @param tree
*/
public static void depthFirstTraverse(BiTree tree) {
Stack<BiTree> stack = new Stack<>();
stack.push(tree);
while (!stack.empty()) {
tree = stack.peek();
System.out.print(tree.data + " ");
stack.pop();
//注意 元素入棧先后順序: right -> left
if (tree.right!= null){
stack.push(tree.right);
}
if (tree.left != null) {
stack.push(tree.left);
}
}
}
/**
* 廣度優(yōu)先遍歷(也稱為:層次遍歷)
* 利用隊列
* @param tree
*/
public static void breadFirstTraverse(BiTree tree){
Queue<BiTree> queue = new ArrayDeque<>();
queue.add(tree);
while(!queue.isEmpty()){
tree = queue.poll();
System.out.print(tree.data + " ");
if (tree.left!=null){
queue.add(tree.left);
}
if (tree.right!=null){
queue.add(tree.right);
}
}
}
public static void main(String[] args) {
BiTree tree = new BiTree();
///(根節(jié)點 -> 左孩子 -> 右孩子)創(chuàng)建二叉樹,如輸入: 1 2a 3a # 4b # # 3b # # 2b # #
tree = createTree();
BiTree ptr = tree;
//先序遍歷
preTraverse(ptr);
System.out.println();
//中序遍歷
ptr = tree;
orderTraverse(ptr);
System.out.println();
//后序遍歷
ptr = tree;
postTraverse(ptr);
System.out.println();
//深度優(yōu)先遍歷
ptr = tree;
depthFirstTraverse(ptr);
System.out.println();
//廣度優(yōu)先遍歷
ptr = tree;
breadFirstTraverse(ptr);
System.out.println();
}
}
2. 圖的廣度和深度優(yōu)先比遍歷（鄰接矩陣表示權(quán)值）
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
* 使用鄰接矩陣來表示'邊'的圖結(jié)構(gòu)
* Created by androidjp on 16/9/8.
*/
public class MyGraph<V> {
private ArrayList<V> vertexList;//點集合
private int[][] edges; //鄰接矩陣表示的邊集合
private int numOfEdges; //邊數(shù)
public MyGraph(int num){
vertexList = new ArrayList(num);
edges = new int[num][num];
numOfEdges = 0;
}
///邊數(shù)
public int getNumOfEdges(){
return this.numOfEdges;
}
///結(jié)點數(shù)
public int getNumOfVertex(){
return this.vertexList.size();
}
//獲取第i個結(jié)點
public V getVertex(int i){
return this.vertexList.get(i);
}
//獲取i、j兩個結(jié)點之間的權(quán)值
public int getWeight(int i, int j){
return this.edges[i][j];
}
//插入結(jié)點
public void insertVertex(V vertex) {
vertexList.add(vertexList.size(),vertex);
}
//插入結(jié)點
public void insertEdge(int v1,int v2,int weight) {
edges[v1][v2]=weight;
numOfEdges++;
}
//刪除結(jié)點
public void deleteEdge(int v1,int v2) {
edges[v1][v2]=0;
numOfEdges--;
}
//得到第一個鄰接結(jié)點的下標
public int getFirstNeighbor(int index) {
for(int j=0;j<vertexList.size();j++) {
if (edges[index][j]>0) {
return j;
}
}
return -1;
}
//根據(jù)前一個鄰接結(jié)點的下標來取得下一個鄰接結(jié)點
public int getNextNeighbor(int v1,int v2) {
for (int j=v2+1;j<vertexList.size();j++) {
if (edges[v1][j]>0) {
return j;
}
}
return -1;
}
//私有函數(shù)，深度優(yōu)先遍歷
private void depthFirstSearch(boolean[] isVisited,int i) {
//首先訪問該結(jié)點，在控制臺打印出來
System.out.print(getVertex(i)+" ");
//置該結(jié)點為已訪問
isVisited[i]=true;
int w=getFirstNeighbor(i);
while (w!=-1) {
if (!isVisited[w]) {
depthFirstSearch(isVisited,w);
}
w=getNextNeighbor(i, w);
}
}
//對外公開函數(shù)，深度優(yōu)先遍歷，與其同名私有函數(shù)屬于方法重載
public void depthFirstSearch() {
boolean[] isVisited = new boolean[getNumOfVertex()];
for(int i=0;i<isVisited.length;i++)
isVisited[i] = false;
for(int i=0;i<getNumOfVertex();i++) {
//因為對于非連通圖來說，并不是通過一個結(jié)點就一定可以遍歷所有結(jié)點的。
if (!isVisited[i]) {
depthFirstSearch(isVisited,i);
}
}
}
//私有函數(shù)，廣度優(yōu)先遍歷
private void broadFirstSearch(boolean[] isVisited,int i) {
int u,w;
LinkedList queue=new LinkedList();
//訪問結(jié)點i
System.out.print(getVertex(i)+" ");
isVisited[i]=true;
//結(jié)點入隊列
queue.addLast(i);
while (!queue.isEmpty()) {
u=((Integer)queue.removeFirst()).intValue();
w=getFirstNeighbor(u);
while(w!=-1) {
if(!isVisited[w]) {
//訪問該結(jié)點
System.out.print(getVertex(w)+" ");
//標記已被訪問
isVisited[w]=true;
//入隊列
queue.addLast(w);
}
//尋找下一個鄰接結(jié)點
w=getNextNeighbor(u, w);
}
}
}
//對外公開函數(shù)，廣度優(yōu)先遍歷
public void broadFirstSearch() {
boolean[] isVisited = new boolean[getNumOfVertex()];
for(int i=0;i<isVisited.length;i++)
isVisited[i] = false;
for(int i=0;i<getNumOfVertex();i++) {
if(!isVisited[i]) {
broadFirstSearch(isVisited, i);
}
}
}
public static void main(String args[]) {
int n = 8, e = 9;//分別代表結(jié)點個數(shù)和邊的數(shù)目
String labels[] = {"1", "2", "3", "4", "5", "6", "7", "8"};//結(jié)點的標識
MyGraph<String> graph = new MyGraph<String>(n);
for (String label : labels) {
graph.insertVertex(label);//插入結(jié)點
}
//插入九條邊
graph.insertEdge(0, 1, 1);
graph.insertEdge(0, 2, 1);
graph.insertEdge(1, 3, 1);
graph.insertEdge(1, 4, 1);
graph.insertEdge(3, 7, 1);
graph.insertEdge(4, 7, 1);
graph.insertEdge(2, 5, 1);
graph.insertEdge(2, 6, 1);
graph.insertEdge(5, 6, 1);
graph.insertEdge(1, 0, 1);
graph.insertEdge(2, 0, 1);
graph.insertEdge(3, 1, 1);
graph.insertEdge(4, 1, 1);
graph.insertEdge(7, 3, 1);
graph.insertEdge(7, 4, 1);
graph.insertEdge(6, 2, 1);
graph.insertEdge(5, 2, 1);
graph.insertEdge(6, 5, 1);
System.out.println("深度優(yōu)先搜索序列為：");
graph.depthFirstSearch();
System.out.println();
System.out.println("廣度優(yōu)先搜索序列為：");
graph.broadFirstSearch();
}
}
