數據結構：從多個方面詳細闡述

一、數據結構的概念

數據結構是計算機科學中一種重要的基礎概念，它是指數據對象及其之間的關係，是計算機存儲、組織數據的方式。數據結構既包含數據對象的物理結構，也包括它們之間的邏輯聯繫和操作。通俗地說，數據結構是為解決某一類問題，而組織起來的特定方式的數據類型的總稱。

數據結構包括線性結構、樹形結構、圖形結構等多種類型，每一種類型都對應着不同的應用領域。比如，線性結構可以用來表示遞進關係，樹形結構可以用來表示層級關係，圖形結構可以用來表示各種關係。其中，線性結構最為簡單，也最常用，因此下面將以線性結構為例子來對數據結構進行詳細闡述。

二、線性結構

線性結構是指數據元素之間存在一個唯一的前驅後繼關係的結構。常見的線性結構有數組、鏈表、隊列和棧等。下面將以鏈表為例子來詳細介紹。

1. 鏈表的定義

<template<typename T> class LinkedList { 
  private:
    struct Node {
        T data;
        Node* next;
        Node(const T& data=T(), Node* next=nullptr) : data(data), next(next) {}
    };
    int size;
    Node* dummyHead;
  }

以上是鏈表的定義代碼。鏈表是由多個結點構成的，每個結點都有一個數據域和一個指向下一個結點的指針域。鏈表的第一個結點沒有前驅，最後一個結點沒有後繼，所以需要在鏈表的頭部添加一個虛擬結點(dummyHead)來便於操作。

2. 鏈表的操作

鏈表的操作包括添加、刪除、查找等，下面將以添加操作為例子來介紹。鏈表的添加操作有兩種，分別是在鏈表頭部添加結點和在鏈表尾部添加結點。

(1) 在鏈表頭部添加結點

void addFirst(const T& data) {
    dummyHead->next = new Node(data, dummyHead->next);
    size++;
}

在鏈表的頭部添加一個結點，只需要將新結點的指針域指向原來的頭結點，再將dummyHead的指針域指向新的頭結點即可。

(2) 在鏈表尾部添加結點

void addLast(const T& data) {
  Node* cur = dummyHead;
  while (cur->next != nullptr) {
    cur = cur->next;
  }
  cur->next = new Node(data);
  size++;
}

在鏈表的尾部添加一個結點，只需要先找到鏈表的最後一個結點，再將該結點的指針域指向新的結點即可。

三、其他數據結構

除了線性結構，數據結構還包括樹形結構、圖形結構等多種類型。樹形結構包括二叉樹、平衡樹、B樹等，圖形結構包括有向圖、無向圖等。它們的定義和操作都有所不同，但是都有着其獨特的特點和應用場景。

1. 二叉搜索樹

二叉搜索樹是一種特殊的二叉樹，它的每個結點都有一個關鍵字(Key)，並且所有左子樹結點的關鍵字都小於該結點的關鍵字，所有右子樹結點的關鍵字都大於該結點的關鍵字。下面是二叉搜索樹的定義和一些操作代碼。

<template<typename T> class BST {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        Node(const T& data=T(), Node* left=nullptr, Node* right=nullptr) : data(data), left(left), right(right) {}
    };
    int size;
    Node* root;
    ...
public:
  // 向二分搜索樹中添加元素e
  void add(const T& e) {
    root = add(root, e);
  }
  
private:
  Node* add(Node* node, const T& e) {
    if (node == nullptr) {
      size++;
      return new Node(e);
    }
    if (e data) {
      node->left = add(node->left, e);
    } else if (e > node->data) {
      node->right = add(node->right, e);
    }
    return node;
  }
}

以上是二叉搜索樹的定義和添加操作代碼。二叉搜索樹的定義較為簡單，只需要保證左子樹比該結點小，右子樹比該結點大即可。在添加元素時，只需要比較該元素與當前結點的大小關係即可。如果比當前結點小，就繼續在左子樹中添加; 如果比當前結點大，就繼續在右子樹中添加。

2. 圖形結構

圖形結構有向圖、無向圖等多種類型。有向圖中每個結點有多個入度和多個出度，無向圖中每個結點都有多個度數。以下是一個無向圖的定義和遍歷操作的代碼。

<template<typename T> class Graph {
private:
    vector<vector<T>> adj;// 圖的鄰接表
    vector<bool> visited; // 標記每個結點是否被遍歷過
    ...
public:
  // 深度優先搜索算法
  void dfs(int v) {
    visited[v] = true;
    cout << v << " ";
    for (T w : adj[v]) {
      if (!visited[w]) {
        dfs(w);
      }
    }
  }
}

以上是無向圖的定義和深度優先遍歷算法。無向圖中每個結點都有多個度數，因此需要使用鄰接表來表示。深度優先遍歷算法需要從一個指定的結點開始遍歷，將該結點標記為已遍歷，然後遞歸遍歷其鄰接結點。深度優先遍歷算法可以用來解決一些搜索問題，比如迷宮問題。