Java之線性表的鏈式存儲——單鏈表

我們都知道，線性表的存儲結構分為兩種，順序存儲結構和鏈式存儲結構，線性表的分類可以參考下圖來學習記憶。今天我們主要來學習一下鏈式存儲結構。

一、鏈式存儲介紹

“鏈式存儲結構，地址可以連續也可以不連續的存儲單元存儲數據元素”——來自定義。

其實，你可以想象這樣一個場景，你想找一個人（他的名字叫小譚）,於是你首先去問 A ， A 說他不知道，但是他說 B 可能知道，並告訴了你 B 在哪裡，於是你找到 B ，B 說他不知道，但是他說 C 可能知道，並告訴了你 C 的地址，於是你去找到 C ，C 真的知道小譚在何處。

上面場景其實可以幫助我們去理解鏈表，其實每一個鏈表都包含多個節點，節點又包含兩個部分，一個是數據域（儲存節點含有的信息），一個是指針域（儲存下一個節點或者上一個節點的地址），而這個指針域就相當於你去問B，B知道C的地址，這個指針域就是存放的 C 的地址。

鏈表下面其實又細分了3種：單鏈表、雙向鏈表和循環鏈表。今天我們先講單鏈表。

二、單鏈表介紹

什麼是單鏈表呢？單鏈表就是每一個節點只有一個指針域的鏈表。如下圖所示，就是一個帶頭節點的單鏈表。下面我們需要知道什麼是頭指針，頭節點和首元節點。

頭指針：指向鏈表節點的第一個節點的指針

頭節點：指在鏈表的首元節點之前附設的一個節點

首元節點：指在鏈表中存儲第一個實際數據元素的節點（比如上圖的 a1 節點）

三、單鏈表的創建

單鏈表的創建有兩種方式，分別是頭插法和尾插法。

1、頭插法

頭插法，顧名思義就是把新元素插入到頭部的位置，每次新加的元素都作為鏈表的第一個節點。那麼頭插入法在Java中怎麼實現呢。首先我們需要定義一個節點，如下

public class ListNode {
  public int val; //數據域
  public ListNode next;//指針域
}

然後我們就創建一個頭指針（不帶頭節點）

//元素個數
int n = 5;
//創建一個頭指針
ListNode headNode = new ListNode();
//頭插入法
headNode= createHead(headNode, n);

然後創建一個私有方法去實現頭插法，這裏我們插入5個新元素，頭插入的核心是要先斷開首元節點和頭指針的連接，也就是需要先將原來首元節點的地址存放到新節點的指針域里，也就是 newNode.next = headNode.next，然後再讓頭指針指向新的節點 headNode.next = newNode，這兩步是頭插入的核心，一定要理解。

/**
 * 頭插法
 * 新的節點放在頭節點的後面，之前的就放在新節點的後面
 * @param headNode 頭指針
 * @return
 */
private static ListNode createHead(ListNode headNode, int n) {
  //插入5個新節點
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    //將之前的所有節點指向新的節點（也就是新節點指向之前的所有節點）
    newNode.next = headNode.next;
    //將頭指針指向新的節點
    headNode.next = newNode;
  }
  return headNode;
}

最後我把鏈表打印輸出一下（其實也是單鏈表的遍歷），判斷條件就是只有當指針域為空的時候才是最後一個節點。

private static void printLinkedList(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    System.out.println(headNode.next.val);
    headNode = headNode.next;
  }
  System.out.println("該單鏈表的節點總數：" +countNode);
}

最後的輸出結果顯然是逆序，因為沒一個新的元素都是從頭部插入的，自然第一個就是最後一個，最後一個就是第一個：

2、尾插法

尾插法，顧名思義就是把新元素插入到尾部的位置（也就是最後一個位置），每次新加的元素都作為鏈表的第最後節點。那麼尾插法在 Java 中怎麼實現呢，這裏還是採用不帶頭節點的實現方式，頭節點和頭指針和頭插入的實現方式一樣，這裏我就直接將如何實現：

/**
 * 尾插法
 * 找到鏈表的末尾結點，把新添加的數據作為末尾結點的後續結點
 * @param headNode
 */
private static ListNode createByTail(ListNode headNode, int n) {
  //讓尾指針也指向頭指針
  ListNode tailNode = headNode;
  for (int i = 1; i <= n; i++) {
    ListNode newNode = new ListNode();
    newNode.val = i;
    newNode.next = null;

    //插入到鏈表尾部
    tailNode.next = newNode;
    //指向新的尾節點，tailer永遠存儲最後一個節點的地址
    tailNode = newNode;

  }
  return headNode;
}

和頭插入不同的是，我們需要聲明一個尾指針來輔助我們實現，最開始，尾指針指向頭指針，每插入一個元素，尾指針就后移一下，這裏我們來講一下原理：每次往末尾新加一個節點，我們就需要把原來的連接斷開，那怎麼斷開呢，我們首先需要讓尾指針指向新的節點，也就是 tailNode.next = newNode; 然後再讓尾指針后移一個位置，讓尾指針指向最後一個節點。也就是尾指針始終指向最後一個節點，最後將頭指針返回，輸出最後結果：

四、單鏈表的刪除

既然單鏈表創建好了，怎麼在鏈表裡面刪除元素呢，單鏈表的刪除，我分為了兩種情況刪除，分別是刪除第i個節點和刪除指定元素的節點。

1、刪除第i個節點

我們可以先來理一下思路：在單鏈表裡，節點與節點之間都是通過指針域鏈接起來的，所以如果我們想實現刪除的操作，實際上是需要我們去改變相應指針域對應得地址的。當想去刪除第i個元素的時候，比如要刪除上圖的第3個元素（也就是3），實際上我們要做的就是要讓2號元素指向4號元素（其實就是需要修改2號元素的指針域，讓2號元素的指針域存儲4號元素）。那麼怎麼做才能實現這一步呢？很顯然，要實現這個步驟，我們必須要找到4號元素和2號元素，但是再仔細想一下，其實我們只需要找到2號元素就可以了，因為4號元素的地址存儲再2號的下一個元素的指針域裏面。

所以綜上所述分析我們可以得出刪除的兩個核心步驟：

1.刪除第i個節點，需要先找到第 i-1 個個節點，也就是第i個節點的前一個節點；

2.然後讓第 i-1 個節點指向第 i-1 個節點的下下個節點

下面的代碼具體實現了怎麼刪除第i個元素。

/**
 * 刪除第i個節點
 * 1,2 4,4,5
 * 刪除之後應該是1,2,4,5
 * @param headNode
 * @param index
 * @return
 */
public static ListNode deleteNodeByIndex(ListNode headNode, int index) {
  int count = 1;
  //將引用給它
  ListNode preNode = headNode;
  //看計數器是不是到了i-1，如果到了i-1,就找到了第i-1個節點
  while (preNode.next != null && count <= index -1){
    //尋找要刪除的當前節點的前一個節點
    count++;
    preNode = preNode.next;
  }
  if (preNode != null){
    preNode.next = preNode.next.next;
  }
  return headNode;
}

2、刪除指定元素的那個節點

刪除指定元素節點的實現方法有兩種，第一種就是先找到指定元素對應的鏈表的位置（ index ），然後再按照刪除第 i 個節點的思路刪除即可。實現方法如下圖所示：

/**
 * 刪除鏈表指定數值的節點
 * @param headNode
 * @param val
 * @return
 */
private static ListNode deleteNodeByNum(ListNode headNode, int val) {
  ListNode deleteOne = headNode;
  int countByDeleteOne = 1;
  while (deleteOne.next != null){
    if (deleteOne.next.val == val){
      deleteOne = deleteOne.next;
      break;
    }
    countByDeleteOne ++;
    deleteOne = deleteOne.next;
  }
  return deleteNodeByIndex(headNode, countByDeleteOne);
}

第二種方法的實現就很精妙（前提是此節點不是尾節點）

public void deleteNode(ListNode node) {
  //刪除node即通過將後面的值賦給node，然後更改node的指針指向下下一個結點即可
  node.val = node.next.val;
  node.next = node.next.next;
}

五、單鏈表的查詢（及修改）

單鏈表的查詢實現很簡單，就是遍歷當前單鏈表，然後用一個計數器累加到當前下標，那麼當前的這個節點就是要查詢的那個節點，然後再返回即可，當然需要判斷傳過來的這個下標是否合法。當然如果需要修改，就需要把當前找到的節點的數據域重新賦上需要修改的值即可，這裏就不上代碼了。具體實現如下：

private static ListNode searchLinkedList(ListNode headNode, int index) {
  //如果下標是不合法的下標就表示找不到
  if (index < 1 || index > getLinkedListLength(headNode)){
      return null;
  }
  for (int i = 0; i < index; i++) {
    headNode = headNode.next;
  }
  return headNode;
}

獲取單鏈表的長度（注意我這裏定義的 headNode 是頭指針不是頭節點）

/**
 * 求單鏈表長度
 * @param headNode
 * @return
 */
private static int getLinkedListLength(ListNode headNode) {
  int countNode = 0;
  while (headNode.next != null){
    countNode++;
    headNode = headNode.next;
  }
 return countNode;
}

六、小結

單鏈表的相關操作就講解完了，其實通過上面對單鏈表的相關操作，我們不難發現，單鏈表的刪除和插入其實很方便，只需要改變指針的指向就可以完成，但是查找元素的時候就比較麻煩，因為在查找的時候，需要把整個鏈表從頭到尾遍歷一次。

公眾號：良許Linux

有收穫？希望老鐵們來個三連擊，給更多的人看到這篇文章

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

Docker 是一個開發、發布和運行應用程序的開放平台。Docker使您能夠將應用程序與基礎架構分離，以便快速交付軟件。有了 Docker，你可以像管理應用程序一樣管理你的基礎設施。通過利用 Docker 快速發布、測試和部署代碼的方法，您可以顯著減少編寫代碼和在生產環境中運行它之間的延遲。

Docker 平台

Docker 提供了在鬆散隔離的環境（稱為容器）中打包和運行應用程序的能力。隔離和安全性允許您在給定的主機上同時運行多個容器。容器是輕量級的，因為它們不需要額外的hypervisor負載，而是直接在主機的內核中運行。這意味着您可以在給定的硬件組合上運行比使用虛擬機時更多的容器。你甚至可以在實際是虛擬機的主機中運行 Docker 容器！

Docker 提供了工具和平台來管理容器的生命周期:

• 使用容器開發應用程序及其支持組件。
• 容器成為分發和測試應用程序的單元。
• 準備就緒后，將應用程序作為容器或編排好的服務部署到生產環境中。無論您的生產環境是本地數據中心、雲提供商還是兩者的混合，操作都是一樣的。

Docker 引擎

Docker 引擎是一個 客戶端-服務器 應用程序，具有以下主要組件:

• 一個服務器，它是一種稱為守護進程（dockerd 命令）的長時間運行程序。
• 一個 REST API，它指定程序可以用來與守護進程對話並指示它做什麼的接口。
• 一個命令行界面(CLI)客戶端(docker命令)。

CLI 使用Docker REST API通過腳本或直接CLI命令控制Docker守護進程或與之交互。
許多其他Docker應用程序使用底層API和CLI。

這個守護進程創建和管理 Docker 對象，如鏡像、容器、網絡和卷（images, containers, networks, and volumes）。

注意: Docker使用的是開源 Apache 2.0 許可證。

有關更多細節，請參閱下面的 Docker 架構。

我可以用 Docker 做什麼？

快速、一致地交付應用程序

Docker 允許開發人員使用提供應用程序和服務的本地容器，在標準化的環境中工作，從而簡化了開發生命周期。容器對於持續集成和持續交付(CI/CD)工作流非常有用。

考慮以下示例場景：

• 開發人員在本地編寫代碼，並使用 Docker 容器與同事共享他們的工作。
• 他們使用 Docker 將應用程序推送到測試環境，並執行自動和手動測試。
• 當開發人員發現 bug 時，他們可以在開發環境中修復它們，並將它們重新部署到測試環境中進行測試和驗證。
• 當測試完成時，向客戶提供修復就像將更新后的鏡像推送到生產環境一樣簡單。

響應式部署和擴展

Docker 的基於容器的平台允許高度可移植的工作負載。Docker 容器可以運行在開發人員的本地筆記本電腦上、數據中心的物理或虛擬機上、雲提供商上或在混合的環境中。

Docker 的可移植性和輕量級性質也使得它可以很容易地動態管理工作負載，根據業務需要，在接近實時的情況下擴展或拆除應用程序和服務。

在相同硬件上運行更多工作負載

Docker 是輕量級和快速的。它為基於管理程序的虛擬機提供了一種可行的、經濟有效的替代方案，因此您可以使用更多的計算能力來實現業務目標。Docker 非常適合高密度環境和中小型部署，在這些環境中，您需要用更少的資源做更多的事情。

Docker 架構

Docker 使用客戶端-服務器架構。Docker 客戶端與 Docker 守護進程通信，後者負責構建、運行和分發Docker 容器等繁重的工作。Docker 客戶端和守護進程可以運行在同一個系統上，或者您可以將一個 Docker 客戶端連接到一個遠程 Docker 守護進程。Docker 客戶端和守護進程通過 UNIX 套接字或網絡接口使用 REST API 進行通信。

Docker 守護進程

Docker 守護進程(dockerd)偵聽 Docker API 請求並管理 Docker 對象，如鏡像、容器、網絡和卷。
守護進程還可以與其他守護進程通信來管理 Docker 服務。

Docker 客戶端

Docker 客戶端(docker)是許多 Docker 用戶與 Docker 交互的主要方式。當您使用諸如docker run之類的命令時，客戶端將這些命令發送給dockerd, dockerd 會執行這些命令。docker 命令使用 Docker API。Docker 客戶端可以與多個守護進程通信。

Docker 註冊表

Docker 註冊表存儲 Docker 鏡像。
Docker Hub 是一個任何人都可以使用的公共註冊表，默認情況下 Docker 被配置為在 Docker Hub 上尋找鏡像。您甚至可以運行自己的私有註冊表。如果您使用 Docker 數據中心(DDC)，它包括 Docker 可信註冊表(DTR)。

當您使用 docker pull 或 docker run 命令時，所需的鏡像將從配置的註冊表中拉取。當您使用 docker push 命令時，您的鏡像將被推送到您配置的註冊表中。

Docker 對象

當您使用 Docker 時，您正在創建和使用鏡像、容器、網絡、卷、插件和其他對象。本節簡要介紹其中一些對象。

鏡像（IMAGES）

鏡像是一個只讀模板，帶有創建 Docker 容器的指令。鏡像通常基於另一個鏡像，並進行一些額外的定製。例如，您可以構建基於 ubuntu 鏡像的鏡像，但是安裝了 Apache web server 和您的應用程序，以及運行應用程序所需的配置細節。

您可以創建自己的鏡像，也可以只使用其他人創建併發布在註冊表中的鏡像。要構建自己的鏡像，需要創建一個 Dockerfile，其中包含一個簡單的語法，用於定義創建鏡像並運行它所需的步驟。Dockerfile 中的每條指令都會在鏡像中創建一個層。當你改變 Dockerfile 並重建鏡像時，只有那些已經改變的層才會重建。這是使鏡像與其他虛擬化技術相比如此輕量級、小巧和快速的原因之一。

容器（CONTAINERS）

容器是鏡像的可運行實例。您可以使用 Docker API 或 CLI 創建、啟動、停止、移動或刪除容器。您可以將一個容器連接到一個或多個網絡，將存儲附加到該容器，甚至基於其當前狀態創建一個新鏡像。

默認情況下，容器與其他容器及其主機相對隔離良好。您可以控制容器的網絡、存儲或其他底層子系統與其他容器或主機的隔離程度。

容器是由它的鏡像以及創建或啟動它時提供給它的任何配置選項定義的。當刪除容器時，對其狀態的任何未存儲在持久存儲中的更改都會消失。

docker run 命令示例

下面的命令運行一個 ubuntu 容器，以交互方式連接到本地命令行會話，並運行 /bin/bash。

$ docker run -i -t ubuntu /bin/bash

當你運行這個命令時，會發生以下情況(假設你使用默認的註冊表配置):

1. 如果你沒有本地的 ubuntu 鏡像，Docker會從你配置的註冊表中拉取它，就像你已經手動運行 docker pull ubuntu 一樣。
2. Docker 創建一個新的容器，就像手動運行 docker container create 命令一樣。
3. Docker 為容器分配一個讀寫文件系統，作為容器的最後一層。這允許運行中的容器在其本地文件系統中創建或修改文件和目錄。
4. Docker 創建一個網絡接口，將容器連接到默認網絡，因為您沒有指定任何網絡選項。這包括為容器分配IP地址。默認情況下，容器可以使用主機的網絡連接連接到外部網絡。
5. Docker 啟動容器並執行 /bin/bash。由於容器以交互方式運行並連接到你的終端(由於有-i和-t標誌)，所以可以將輸出記錄到終端，同時你可以使用鍵盤提供輸入。
6. 當您鍵入 exit 終止 /bin/bash 命令時，容器將停止，但不會被刪除。您可以重新啟動或刪除它。

服務（SERVICES）

服務允許您跨多個 Docker 守護進程擴展容器，這些守護進程組成一個集群，多個管理者和工作者一起工作。一個集群的每個成員都是一個 Docker 守護進程，所有的守護進程都使用 Docker API 進行通信。服務允許您定義所需的狀態，例如在任何給定時間必須可用的服務副本的數量。默認情況下，服務在所有工作節點之間進行負載均衡。對於消費者來說，Docker 服務看起來像一個單獨的應用程序。Docker 引擎在 Docker 1.12 及更高的版本支持集群模式。

底層技術

Docker 是用 Go 編寫的，並利用 Linux 內核的幾個特性來實現其功能。

命名空間

Docker 使用名為命名空間的技術來提供稱為容器的隔離工作區。當您運行一個容器時，Docker 為該容器創建一組命名空間。

這些命名空間提供了一個隔離層。容器的每個方面都在一個單獨的命名空間中運行，其訪問權限僅限於該命名空間。

Docker 引擎在 Linux 上使用如下命名空間:

• pid 命名空間: 進程隔離 (PID: 進程ID)。
• net 命名空間: 管理網絡接口 (NET: Networking)。
• ipc 命名空間: 管理對 IPC 資源的訪問 (IPC: 進程間通信)。
• mnt 命名空間: 管理文件系統掛載點 (MNT: Mount)。
• uts 命名空間: 隔離內核標識符和版本標識符 (UTS: Unix分時系統)。

控制組

Linux 上的 Docker 引擎還依賴於另一種稱為控制組(cgroups)的技術。cgroup 將應用程序限製為特定的資源集。控制組允許 Docker 引擎將可用的硬件資源共享給容器，並可以選擇強制限制和約束。例如，可以限制特定容器的可用內存。

聯合文件系統

聯合文件系統，或 UnionFS，是通過創建層來操作的文件系統，使其非常輕便和快速。Docker 引擎使用 UnionFS 為容器提供構建塊。Docker 引擎可以使用多種 UnionFS 變體，包括 AUFS、btrfs、vfs 和 DeviceMapper。

容器格式

Docker 引擎將命名空間、控制組和 UnionFS 組合到一個稱為容器格式的包裝器中。默認的容器格式是 libcontainer。未來，Docker 可能會通過與 BSD Jails 或 Solaris Zones 等技術集成來支持其他容器格式。

作者 ： Docker 官網
譯者 ： 技術譯民
出品 ： 技術譯站
鏈接 ： 英文原文
公眾號：技術譯站

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

C++和C#的前自增++n和后自增n++，都是先自增后取值和先取值后自增的含義，但在複雜一點的賦值語句中，我發現細節上有很大的差異。

發現這個問題主要是一個無聊的晚上，我想搞清楚后自增是什麼時候結算，自己搗鼓了一下之後我把我自己的測試結果告訴了朋友，結果學java的朋友和我爭論了半天，最後發現同樣的代碼，大家輸出是不一樣的。之後我又用了C#寫了同樣的測試代碼，發現輸出和他java是一樣的，這讓我豁然開朗，遂寫下這篇博客希望分享我的結論，如果有錯誤的話，歡迎評論區指正。

前排提醒：C++和C#我都是用的VS2017，不同編譯環境的C++代碼輸出結果可能不一樣

先說我的結論：

C++：i++遇到順序點（逗號，分號）之後i才自增，即我一直以來認為的一條語句結束后結算。但++i前自增的值會影響賦值語句所有i的值。

C#：C#不允許使用‘，’逗號運算符，但也並非到’;’分號才結算，賦值語句是從左到右，按序取值，i++在取完i的值之後馬上就自增了，但不影響之前取的i的值，隻影響後續i的取值。

心得：實際開發還是盡量自增單行寫，第一個是可讀性好，第二個是不容易出問題。（應該也就只有筆試會出現以下實驗的代碼了）

結論看不明白的可以看看我無聊的小實驗：

最簡單常見的版本：

int arr[] = { 0,0,0 };
int n = 0;
arr[n] = n++;//語句a
for (int num : arr)
{
	cout << num << ' ';
}
//輸出是0 0 0，語句a結束后n自增到1

上面這段代碼其實在C#也是一樣的輸出，但如果下面這樣寫，結果就不一樣了。

C++版：

int arr[] = { 0,0,0 };
int n = 0;
arr[n++] = n;//語句a
for (int num : arr)
{
	cout << num << ' ';
}
//輸出是0 0 0，語句a結束后n自增到1，C++結果和上面的一樣

C#版：

int[] arr = { 0, 0, 0 };
int n = 0;
arr[n++] = n;//語句a
foreach (int num in arr)
{
	Console.Write(num + " ");
}
//輸出是1 0 0，現在應該能理解結論了，從左到右，先取n作為索引值，然後自增之後影響到了等號右邊的n的值
//語句a則為arr[0] = 1;

就是這樣的差異開始引申出了問題，也是讓我迷惑的開始，接下來我會通過更複雜的例子和反彙編的指令來解釋和證明我的結論，先列舉C++的部分，之後再C#，感興趣的可以往下看。

C++部分：

//代碼01
int arr[] = { 0,0,0 };
int n = 0;
arr[n++] = n + (n++) + ++n;
for (int num : arr)
{
	cout << num << ' ';
}
//輸出為0 3 0，具體操作流程為語句先結算了++n，使得n自增到1.而出現的兩個n++都在賦值語句結束后結算
//所以編譯結果為arr[1] = 1 + 1 + 1; 然後i自增兩次到3

以下為反彙編的結果：

一開始看到這個我有點懵逼，但是通過比對下面這段代碼的反彙編指令，就能看出來了。

//代碼02
int[] arr = { 0, 0, 0 };
int n = 0;
arr[++n] = n + (n++) + ++n;//把索引處的n++改為了++n
foreach (int num in arr)
{
	Console.Write(num + " ");
}
//輸出為0 0 6，具體操作流程為語句先結算兩次++n，使得n自增到2.而n++在賦值語句結束后結算
//所以編譯結果為arr[2] = 2 + 2 + 2; 然後i自增到3
//這下應該發現n在這條語句中取值的時候都是同樣的值了

以下為上面代碼02的反彙編結果：

通過和上面的指令比對可以看出來了，具體差異在00251F3A這段指令，arr[++n]這段代碼02在累加前多進行了一次對n的自增，然後將自增后的值賦給了n，然後開始進行累加，而上面arr[n++]那段代碼01是在累加結束之後，在01161F4A那條指令對n++進行自增的結算，所以就算看不懂全部的指令，也應該能通過比對這兩段代碼看出他們的差異，從而證明了C++對於后自增的處理，是在語句結束之後結算。

說到語句結束，我之前寫了一篇關於逗號運算符的博客，可以結合今天這個結論看看下面這段代碼的輸出結果。

int arr[] = { 0,0,0 };
int n = 0;
arr[n] = (n++, n + (n++) + ++n);//在逗號左邊添加了n++的語句
for (int num : arr)
{
	cout << num << ' ';
}
//輸出為0 0 6
//原因為逗號也屬於一條語句結束的標誌，所以結算了n++，n=1，然後執行新的語句n + (n++) + ++n
//逗號右邊的語句先結算了++n，n=2，所以最後賦值語句為arr[2] = 2 + 2 + 2; 然後n++到3

至此C++的部分結束。

接下來C#的測試結果將顛覆上面的結論，如果不用java或者C#的話，下面的內容可能沒有用（朋友java的輸出結果和我C#一樣，不過也是希望大家自己試試，我自己沒有試過）

C#部分：

//代碼01 C#版
int[] arr = { 0, 0, 0 };
int n = 0;
arr[n++] = n + (n++) + ++n;
foreach (int num in arr)
{
	Console.Write(num + " ");
}
//輸出為5 0 0 和VC++完全不一樣對吧
//具體原因為C#的賦值語句是從左到右，先取了n的值作為索引，然後馬上對n自增，n=1
//來到等號右邊，第一個n取值為1，第二個n取值為1，然後自增到2，第三個n先自增到3，然後取值為3
//所以最終編譯結果為arr[0] = 1 + 1 + 3;  即5 0 0的原因
//為了節省篇幅，我直接告訴你arr[++n] = n + (n++) + ++n的結果為0 5 0，如果你上面看懂了這個應該也懂

貼一下C#這段代碼的反彙編結果：

可以看到第一行是取n的值，然後把n作為索引值，之後inc指令對n自增1。證明了上面的結論。

即：C#的賦值語句為從左到右，按序取值，n++在取完n的值之後馬上自增，但不影響之前取的值，隻影響後續n的取值。

小結：

所以++n 先自增后取值和n++ 先取值后自增是能直接套在C#上的，而對於VC++來說，后自增的結算是非常“緩慢”的，到語句結束才結算。

感謝您的觀看。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

隨著環保意識抬頭，越來越多地方政府推政策因應環保趨勢。桃園縣環保局鼓勵民眾使用電動機車，除了購車補助額度位居全國第一，更推出免費試騎 7 天的活動，讓民眾能夠體驗電動機車的高續航力及充電迅速等便利性，增加使用環保運具的意願。

桃園縣政府環境保護局為改善空氣品質，積極推廣使用電動機車等低污染交通工具，環保局局長陳世偉表示，電動車輛具有零加油、零廢氣、低保養、低噪音及低充電費等特性，是最環保的交通工具；尤其現在電池技術成熟，使得電動車輛的續航力大增，壽命也有效延長保固。

  （Source：）

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

• 搖搖棒，理工男的擇偶權（上）

• 搖搖棒，理工男的擇偶權（中）

• 搖搖棒，理工男的擇偶權（下）

 

前言

搖搖棒是載有一列LED的棒，通過適當的程序控制，在搖動起來時，由於人眼有視覺暫留現象（persistence of vision，POV），會形成一幅圖像。你可以上淘寶搜索，關注一下搖搖棒的核心參數（賣點）與显示效果。

 

一年多前，我做了一根搖搖棒，16個粉紅色LED，在520那天送給了女朋友。她很喜歡，她的同學和我的同學都很好奇。

那時候我做了兩根，當然不是因為我是渣男。另一根我帶去了高考（高二等級考）考場，內置了“全員A+”的字樣，本來想交給老師來給我們應援的，但是在烈日之下我只能很勉強地看見搖搖棒显示的字，於是就不了了之了。

我不服，又設計了搖搖棒2.0。製作完硬件以後，它就一直堆在我的書桌旁。

 

一年過去了，女朋友丟了，體重增加了，唯一不變的是我還是什麼降分約都沒有——唉，又要參加等級考了（寫作之時已經考完了）。

我想起了搖搖棒。

這一回，搖搖棒是我在高考前夕唯一的樂趣，是我在老師心中瓜皮形象的轉折點，是我作為一個理工男的擇偶權。

 

系列概述

本系列文章分為三篇：上篇介紹單機的搖搖棒，中篇介紹聯機的搖搖棒，下篇介紹圖靈完全的搖搖棒。

本文為上篇。目前進度大概到中篇的一半，但我覺得只有完成了後續（最好是所有）才能更好地審視前面的工作，用沒有回溯的思路整理成一篇博客。

寫文章要照應標題，不過這簡直就是做夢，我還是好好介紹搖搖棒吧，不去想那些有的沒的。

 

先放個效果圖吧（曝光時間0.2s）：

 

核心原理

人們對搖搖棒有所好奇，無非是好奇它的核心原理，至於細節與實現，我說出來也沒有人要聽。這也是我開通博客的原因。

 

首先，棒上所有的輸入輸出設備都由程序控制，運行程序的是一塊單片機。

搖動周期是任意的（自適應的），別太誇張就行，所以搖搖棒需要檢測運動周期。用於檢測的硬件是位於棒頂端的水銀開關：

真空、密封的玻璃管中有一滴水銀，一個引腳始終與水銀接觸，另一個只有當水銀位於一端時才接觸。接觸時兩引腳導通，用一個很簡單的電路就可以把導通與否轉換成高低電平被單片機讀取。

改變水銀位置需要施力，搖搖棒運動過程中有加速度，提供了慣性力。然而，水銀開關只能指示加速度的方向，而不是更容易使用的加速度、速度、位置；加速度的方向也不能簡單地認為是一個周期內翻轉兩次——這就需要一個精巧的程序來控制。

我寫的程序能讓單片機知道（意會，別跟我杠什麼單片機沒有意識）它在一個周期中的相對位置，從而知道每一時刻該亮起圖像的哪一部分。哦對了，字符是轉換成點陣圖像存儲的，每一個像素點都是搖搖棒亮燈的依據。

於是，在一個周期中，圖像的每一列都被在對應的位置显示了一會。人眼有視覺暫留現象，這些列一起組成了一幅圖像，它的內容是字符。當然，簡單的圖案也是可以的。

 

硬件

以上為搖搖棒的原理圖，可以分為以下幾個部分：

• 供電：18650電池座、電源開關、SX1308（B628）升壓、AMS1117-3.3穩壓；

  搖搖棒1.0直接用3.7V鋰離子電池供電，但實際電壓為2.7V到4.2V，亮度差異很大；2.0的供電部分先升壓到5V，為了便於在高亮度下控制亮度。

  藍牙模塊需要3.3V電源，所以加了個LDO。

• 控制：ATMega328P單片機、晶振、ISP下載接口；

  單片機選擇的是我最擅長的AVR系列中的ATmega328P，與爛大街的Arduino相同（但我沒從那邊抄過哪怕一行代碼）。晶振是20MHz的，官方允許的最高頻率，為了獲得更好的性能。

  下載器接口是我自己定義的ISP接口，比標準的佔用更少空間，但畢竟是非標準的，這是個歷史遺留問題。

• 輸入：電池電壓檢測、水銀開關、光敏電阻、按鍵×2；

  水銀開關接通時，SWC為低電平；斷開時，由於沒有負載，SWC為高電平；R05稱為上拉電阻。這就是那個很簡單的電路。電容C04本來想用於濾波的，實測反而礙事，拿掉了。兩個按鍵同理，上拉電阻在單片機內部配置。

  光敏電阻R06阻值與光強負相關，與定值電阻R07分壓后的輸出電壓與光強正相關，接到單片機的ADC（模-數轉換器）上，從而檢測環境光強度並調整亮度，深夜寫代碼與陽光下展（liào）示（mèi）都能適配。

• 輸出：5片74HC595、2個N溝道MOS管、32個藍綠雙色LED、2個RGBW LED；

  595是串行轉并行芯片，MOS是一種三極管，詳見AVR單片機教程——矩陣鍵盤。595輸出串聯排阻後接LED再接到MOS管，連接方式下面細說。

  單片機上DAT1、DAT3、DAT4、CLK、STO引腳控制595，前3個是數據信號。設計3個數據信號是為了加速輸出，不過最快的輸出方式是用SPI，沒有用它是設計上的失誤。

• 藍牙：藍牙模塊、簡單的電平轉換電路。

  中篇內容，跳過。

 

兩個RGBW共8個燈，剛好對應595的8個輸出。不幸的是，595位於下方RGBW的背面，而另一個RGBW位於頂端，在狹窄的PCB中避開其他元器件和信號線走4根線並不容易，這是PCB布線的難點。也許還有別的難點，只是時間太久遠，我已經忘了。

595輸出串聯電阻後接LED，輸出低電平時LED不亮，高電平時有電流因而亮，電阻起到限流作用。不同顏色的燈串聯不同阻值的電阻是為了平衡亮度，在RGB都點亮時顏色接近白色。

4片595輸出LED0到LED31，越上方的編號越小。每個藍綠雙色LED的兩個陽極共同連接一個LEDx信號，綠、藍陰極分別連接到GRN和BLU，是兩個MOS管的漏極。當Q的柵極GRNC為高電平時，漏極和連接到GND的源極之間導通，電阻忽略不計，如果此時LEDx為高電平則對應綠燈亮起；低電平時不導通，無論LEDx如何，綠燈一個都不會亮——這段時間留給藍燈。

簡而言之，GRNC為高電平時595控制綠燈，BLUC為高電平時595控制藍燈。如果GRNC和BLUC的電平轉換非常快，快到電平變化的一個周期內LED只移動了很小一段距離，看起來就是天藍色的。而事實上，GRNC和BLUC的電平變化還沒那麼簡單。

 

PCB渲染圖如上。大致布局是，正面最上方水銀開關和光敏電阻，往下一個RGBW、32個藍綠、一個RGBW，IC和電阻等貼片器件都在反面對應的位置。然後是下載器接口、電源開關、兩個按鍵、電感、晶振，最後是電池，反面有升壓電路、單片機、藍牙模塊等。在手握搖搖棒時這些元器件會被碰到，影響正常工作，所以全部被我蓋了一層熱熔膠：

畢竟圖吧簽到12級。

 

硬件設計決定了搖搖棒功能的上限。比如，它不可能显示紅色的圖像（除非你能搖得快到紅移）。

本篇中搖搖棒能實現的功能有：

• 以任意的藍綠組合顏色呈現圖像，包括漸變色；

• 自動根據環境光強調整显示亮度；

• 用按鍵切換显示圖像、複位周期檢測、調整亮度等。

 

驅動

這個項目不算簡單，所以我要加上驅動層，把底層的寄存器操作封裝成C語言函數，在適當的地方提供回調接口。後面將看到驅動層之上並非直接是應用程序，驅動負責到哪一步也是一個問題。我的想法是，應用程序不需要插入代碼的地方就封裝，否則就留給上層解決；明顯的異步操作用回調。

驅動層主要包括以下接口：

1. LED，規定數據格式，提供以一定亮度亮燈的函數；

2. 水銀開關，檢測加速度方向，附帶濾波；

3. 按鍵，封裝按鍵雙擊、長按等高級事件；

4. ADC，檢測電源電壓與光強，後者可以異步；

5. 定時器，程序結構的核心，定時回調與全局時鐘；

6. 藍牙，依舊跳過。

詳解一下奇數編號的驅動。

 

LED

32個雙色LED加上2個RGBW的模式可以用5個字節表示，我規定第[0]字節的最低位對應最上方的LED，第[3]字節的最高位對應最下方，第[4]字節最低位對應上方RGBW的紅色，最高位對應下方RGBW的白色。這樣就不難寫出驅動5片595的代碼：

uint8_t d0, d1, d2;
d0 = data[0];
d1 = data[2];
for (uint8_t i = 0; i != 8; ++i)
{
    cond_bit(read_bit(d0, 0), PORTC, 0);
    cond_bit(read_bit(d1, 0), PORTC, 1);
    d0 >>= 1;
    d1 >>= 1;
    clock_bit(PORTC, 3);
}
d0 = data[1];
d1 = data[3];
d2 = data[4];
for (uint8_t i = 0; i != 8; ++i)
{
    cond_bit(read_bit(d0, 0), PORTC, 0);
    cond_bit(read_bit(d1, 0), PORTC, 1);
    cond_bit(read_bit(d2, 0), PORTC, 2);
    d0 >>= 1;
    d1 >>= 1;
    d2 >>= 1;
    clock_bit(PORTC, 3);
}
clock_bit(PORTC, 4);

其中的位操作宏定義為：

#define set_bit(r, b) ((r) |= (1u << (b)))
#define reset_bit(r ,b) ((r) &= ~(1u << (b)))
#define read_bit(r, b) ((r) & (1u << (b)))
#define cond_bit(c, r, b) ((c) ? set_bit(r, b) : reset_bit(r, b))
#define flip_bit(r, b) ((r) ^= (1u << (b)))
#define clock_bit(r, b) (flip_bit(r, b), flip_bit(r, b)
#define bit_mask(n, b) (((1u << (n)) - 1) << (b))

配合GRNC和BLUC的高低電平可以显示出綠、藍和天藍色，但這還不算完。GRNC和BLUC連接到單片機的OC0A和OC0B引腳，它們是定時器0的波形輸出引腳，可以產生PWM波。一個PWM周期內一段時間高電平，對應LED亮，低電平時暗，切換快到人眼完全看不出來，從而感覺到亮度是均勻的，與PWM占空比正相關的。一會讓GRNC輸出PWM波，BLUC保持低電平，一會相反，切換依然快到看不出來，於是就實現了任意的藍綠亮度組合。

原先這種設計只是為了解決藍綠亮度不相同的問題，後來漸漸地發展出了漸變色的功能。

typedef enum
{
    COLOR_NONE, COLOR_GREEN, COLOR_BLUE
} color_t;

void led_set(color_t color, uint8_t duty, const uint8_t data[5])
{
    TCCR0A &= ~(bit_mask(2, COM0A0) | bit_mask(2, COM0B0));
    // ...
    uint8_t com0x;
    volatile uint8_t* ocr0x;
    switch (color)
    {
    case COLOR_GREEN:
        com0x = 0b10 << COM0A0;
        ocr0x = &OCR0A;
        break;
    case COLOR_BLUE:
        com0x = 0b10 << COM0B0;
        ocr0x = &OCR0B;
        break;
    default:
        return;
    }
    if (duty == 0)
        return;
    TCCR0A |= com0x;
    *ocr0x = duty - 1;
    TCNT0 = 0xFF;
}

中間省略的是上面那段代碼。

 

按鍵

我一直想寫一個能處理長按、雙擊等事件的按鍵庫，這次正是一個機會。至少在這一篇中，按鍵是控制好搖搖棒的唯一方式。而按鍵一共只有兩個，為了使輸入方式更豐富，就只能在每個按鍵的事件種類上動手腳。

首先要消抖。按鍵在被按下和抬起的過程中，電平並不是直上直下的，可能存在抖動。如果把每一次跳變都算一個事件的話，隨意按一下可能就被算作雙擊了，所以需要消抖。我用的是最簡單的消抖方法：用一個變量記錄按鍵的狀態，當按鍵的電平與原狀態不同且保持10ms不變時，才認為此時按鍵進入新的狀態。水銀開關的消抖也是類似的。

#include <avr/io.h>

#define BUTTON_COUNT 2

static bool pin[BUTTON_COUNT];
static uint8_t filter[BUTTON_COUNT] = {0};

static inline bool button_read(uint8_t which)
{
    switch (which)
    {
    case 0:
        return read_bit(PINB, 1);
    case 1:
        return read_bit(PINB, 2);
    }
    return false;
}

static inline button_event_t button_filter(uint8_t which)
{
    if (which >= BUTTON_COUNT)
        return false;
    bool now = button_read(which);
    if (now == pin[which])
        filter[which] = 0;
    else if (++filter[which] == 50)
    {
        pin[which] = now;
        filter[which] = 0;
        return now ? BUTTON_LEFT_RELEASED : BUTTON_LEFT_PRESSED;
    }
    return BUTTON_NONE;
}

void button_init()
{
    set_bit(PORTB, 1);
    set_bit(PORTB, 2);
    for (uint8_t i = 0; i != BUTTON_COUNT; ++i)
        pin[i] = button_read(i);
}

定義三種模式，最複雜的模式中包括以下事件：

typedef enum
{
    MODE_NONE, MODE_SIMPLE, MODE_ADVANCED
} button_mode_t;

typedef enum
{
    BUTTON_NONE,
    BUTTON_LEFT_PRESSED, BUTTON_LEFT_RELEASED,
    BUTTON_LEFT_SHORT, BUTTON_LEFT_LONG, BUTTON_LEFT_CONT,
    BUTTON_LEFT_DOUBLE,
    BUTTON_RIGHT_PRESSED, BUTTON_RIGHT_RELEASED,
    BUTTON_RIGHT_SHORT, BUTTON_RIGHT_LONG, BUTTON_RIGHT_CONT,
    BUTTON_RIGHT_DOUBLE,
    BUTTON_BOTH
} button_event_t;

BUTTON_LEFT_CONT指左按鍵長按以後保持按下的事件，每100毫秒觸發一次；BUTTON_BOTH是兩個按鍵同時按下的事件。

函數button_get()返回一個button_event_t變量。每次調用只更新一個按鍵，因此不會有多個返回值。該函數需要客戶輪詢。

同時處理這麼多事件的方法是用狀態機：

BOTH向FREE的轉移條件為另一個按鍵也處於BOTH狀態。具體timeout值見下面的代碼，代碼中數值除以5得到毫秒數。

比如，0ms時按下，200ms時抬起，400ms時按下，600ms時抬起，狀態轉移過程為：

1. 0ms，FREE→BOTH；

2. 100ms，BOTH→SHORT，事件PRESSED；

3. 200ms，SHORT→DOUBLE；

4. 400ms，DOUBLE→FREE，事件DOUBLE。

typedef enum
{
    STATE_FREE, STATE_BOTH, STATE_SHORT, STATE_DOUBLE, STATE_LONG
} state_t;

static button_mode_t mode = MODE_NONE;
static const button_event_t base[BUTTON_COUNT] = {0, BUTTON_RIGHT_PRESSED - BUTTON_LEFT_PRESSED};
static state_t state[BUTTON_COUNT];
static uint16_t count[BUTTON_COUNT];
static uint8_t turn = 0;

void button_mode(button_mode_t m)
{
    if (mode == m)
        return;
    mode = m;
    if (m == MODE_ADVANCED)
        for (uint8_t i = 0; i != BUTTON_COUNT; ++i)
            state[i] = STATE_FREE;
}

button_event_t button_get()
{
    button_event_t result = BUTTON_NONE;
    button_event_t filter = button_filter(turn);
    if (mode == MODE_SIMPLE)
        result = filter;
    else if (mode == MODE_ADVANCED)
    {
        switch (state[turn])
        {
        case STATE_FREE:
            if (filter == BUTTON_LEFT_PRESSED)
            {
                state[turn] = STATE_BOTH;
                count[turn] = 0;
            }
            break;
        case STATE_BOTH:
        {
            uint8_t other = 1 - turn;
            if (state[other] == STATE_BOTH)
            {
                result = BUTTON_BOTH;
                state[turn] = STATE_FREE;
                state[other] = STATE_FREE;
            }
            else if (filter == BUTTON_LEFT_RELEASED)
            {
                result = BUTTON_LEFT_PRESSED;
                state[turn] = STATE_DOUBLE;
                count[turn] = 0;
            }
            else if (++count[turn] == 500)
            {
                result = BUTTON_LEFT_PRESSED;
                state[turn] = STATE_SHORT;
                count[turn] = 0;
            }
            break;
        }
        case STATE_SHORT:
            if (filter == BUTTON_LEFT_RELEASED)
            {
                state[turn] = STATE_DOUBLE;
                count[turn] = 0;
            }
            else if (++count[turn] == 2500)
            {
                result = BUTTON_LEFT_LONG;
                state[turn] = STATE_LONG;
                count[turn] = 0;
            }
            break;
        case STATE_DOUBLE:
            if (filter == BUTTON_LEFT_PRESSED)
            {
                result = BUTTON_LEFT_DOUBLE;
                state[turn] = STATE_FREE;
            }
            else if (++count[turn] == 500)
            {
                result = BUTTON_LEFT_SHORT;
                state[turn] = STATE_FREE;
            }
            break;
        case STATE_LONG:
            if (filter == BUTTON_LEFT_RELEASED)
            {
                result = BUTTON_LEFT_RELEASED;
                state[turn] = STATE_FREE;
            }
            else if (++count[turn] == 500)
            {
                result = BUTTON_LEFT_CONT;
                count[turn] = 0;
            }
            break;
        }
    }
    if (result != BUTTON_NONE && result != BUTTON_BOTH)
        result += base[turn];
    if (++turn == BUTTON_COUNT)
        turn = 0;
    return result;
}

 

廢話兩句。以前上課的時候有人問我單片機按鍵雙擊怎麼寫，當時我心裏還沒底，因為沒寫過，就讓他多加一個按鍵。這時我們老師說，註冊一個回調就可以了呀！

嗯，算你懂得回調。

 

定時器

程序中主循環的周期為0.1ms，但是一個周期中執行指令的時間相比於周期長度而言已經不可忽略，為了精準地控制時間，需要使用定時器。沒錯，這裏的定時器和之前提到的用於產生PWM波的是同一類東西，不同的是之前用的是定時器0，這裏用的是定時器2，兩者互不干擾。

設置定時器2分頻係數為8，匹配值為250，則每2000個CPU時鐘周期產生一个中斷。CPU時鐘頻率為20MHz，因此定時器中斷的間隔為0.1ms。客戶須在每次中斷中調用button_get，這就是除以5得到毫秒數的原理。

定時器中斷有兩項職責，一是維護一個時鐘，每一周期增加1，可重置，主要用於水銀開關周期檢測；二是調用上層的回調函數timer_handler，驅動中僅聲明為extern（另一種方法是通過函數指針註冊回調）。

#include <avr/io.h>
#include <avr/interrupt.h>

static uint16_t tick = 0;

ISR(TIMER2_COMPA_vect)
{
    ++tick;
    timer_handler();
}

void timer_init()
{
    if (0)
        TIMER2_COMPA_vect();
    TCCR2A = 0b10 << WGM20;
    TCCR2B = 0 << WGM22 | 0b010 << CS20;
    OCR2A = 249;
    TIMSK2 = 1 << OCIE2A;
    sei();
}

void clock_reset()
{
    tick = 0;
}

uint16_t clock_get()
{
    return tick;
}

 

應用程序

驅動封裝了硬件操作，而用戶只想關心显示什麼內容，兩者之間還需要插入一層，這一層主要實現運動周期檢測，並在周期中合適的時刻根據用戶提供的數據進行显示。

兩層之間用回調函數和配置信息耦合。回調函數包括定時器回調、按鍵事件回調與圖像更新回調；配置信息定義如下：

typedef struct
{
    uint8_t width;
    uint8_t height_byte;
    const uint8_t* display;
    uint8_t in_flash : 1;
    uint8_t bright;
    uint8_t color;
    uint8_t rgbw;
} Config;

display指向點陣數據，共width * height_byte字節，每height_byte字節表示一列，RGBW另存。

客戶通過set_config函數更新配置，Config參數被立即拷貝到一個特定的位置，但不會立即應用於显示，而是等待當前显示周期（即運動周期）結束，在下次更新中應用，簡而言之配置被緩衝了。

 

在C語言中，即使一個數組聲明為const，它也存放在RAM中，但是ATmega328P只有2k字節RAM，显示的字數很多的話會放不下。AVR編程中可以用PROGMEM宏指定數據存放在flash中，in_flash即表示點陣是否存儲在flash中。

#include <stdint.h>
#include <avr/pgmspace.h>

static const uint8_t jiayou[] PROGMEM =
{
    0x00, 0x00, 0x00, 0x40, 0x00, 0x40, 0x40, 0x00, 0x20, 0x40, 0x00, 0x18,
    0x40, 0x00, 0x07, 0x40, 0xF8, 0x09, 0xFE, 0x1F, 0x08, 0x40, 0x00, 0x10,
    0x40, 0x00, 0x30, 0x40, 0x00, 0x18, 0xC0, 0xFF, 0x0F, 0xC0, 0x07, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xC0, 0xFF, 0x7F, 0x40, 0x00, 0x08,
    0x40, 0x00, 0x08, 0x40, 0x00, 0x08, 0x40, 0x00, 0x08, 0x40, 0x00, 0x08,
    0xC0, 0xFF, 0x3F, 0x40, 0x00, 0x30, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x80, 0x00, 0x00, 0x00, 0x01, 0x02, 0x00, 0x07, 0x72,
    0x08, 0x06, 0x7F, 0x18, 0xE0, 0x01, 0x10, 0x18, 0x00, 0x00, 0x07, 0x00,
    0xC0, 0x00, 0x00, 0xC0, 0xFF, 0x7F, 0xC0, 0xFF, 0x7F, 0x40, 0x20, 0x10,
    0x40, 0x20, 0x10, 0x40, 0x20, 0x10, 0xFE, 0xFF, 0x1F, 0xFE, 0xFF, 0x1F,
    0x40, 0x20, 0x10, 0x40, 0x20, 0x10, 0x40, 0x20, 0x10, 0xC0, 0xFF, 0x7F,
    0xC0, 0xFF, 0x3F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
};

（點陣數據可用PCtoLCD2002生成；原諒我用拼音命名變量。）

指向flash中數據的指針與普通指針相同，但是不能直接解引用，要先用memcpy_P函數拷貝到RAM中：

memcpy_P(display.current, display.ptr + display.phase * display.height_byte, display.height_byte);

並不是所有點陣數據都放在flash中，比如程序還可以通過藍牙接收數據，把它寫進flash就太麻煩了。

 

程序結構為，先執行初始化，包括硬件與變量，然後進入死循環，保持程序運行。初始化的最後是啟動定時器，隨後定時器會每0.1ms產生一次中斷，所有實際工作都在中斷中完成。

int main()
{
    startup();
    while (1)
        ;
}

 

周期檢測

那時做完第一版發了個朋友圈，就有人問這個問題：

的確，周期檢測是搖搖棒的難點（對於那些問我“把搖搖棒放在桌上不動能不能显示”的人就不是了），是我寫第一版甚至第二版的程序時唯一心慌的地方。雖然免去了為MPU6050寫I²C驅動的煩惱，但5毛錢的水銀開關也自有麻煩之處。讓我們來一探究竟吧！

 

水銀開關電路的輸出信號首先要經過濾波，這是驅動層封裝好的：

typedef enum
{
    MERCURY_NONE, MERCURY_LEFT, MERCURY_RIGHT
} mercury_event_t;

static bool status;
static uint16_t count = 0;

static inline bool mercury_read()
{
    return !read_bit(PINB, 0);
}

void mercury_init()
{
    status = mercury_read();
}

mercury_event_t mercury_get()
{
    bool now = mercury_read();
    if (now == status)
        count = 0;
    else if (++count == 100)
    {
        status = now;
        count = 0;
        return now ? MERCURY_RIGHT : MERCURY_LEFT;
    }
    return MERCURY_NONE;
}

 

然後就是算法的主體部分。算法可以用狀態機描述，只有穩定與不穩定兩個狀態，用stable變量表示，初始值為false。period為上一周期的長度，單位為定時器周期即0.1ms，是兩個狀態共用的；計數器count在兩個狀態中有不同的含義，但共用一個變量。

算法只監聽水銀珠從右到左這一事件，大致上是棒從右到左經過中點。定義局部變量uint16_t clock = clock_get();，表示當前周期已經持續的時間。大多數分支都會調用clock_reset複位時鐘，並在使用完clock后把它寫為0，標志著新的周期開始。

在不穩定狀態中，要想進入穩定狀態，必須連續若干次滿足以下條件：本次周期長度大於前一周期的0.5倍並且小於1.5倍。count記錄這一條件成立的次數，一旦某一次條件不成立則清零，並把period更新為當前周期長度。目標次數被設置為2。

在穩定狀態中，根據周期長度分3類討論：

1. 周期長度大於等於前一周期的0.75倍並且小於1.5倍，這意味着當前周期和上一周期差不多長，用戶在穩定地搖動。把period設為兩個周期的平均值，這樣可以允許周期緩慢變化。

2. 周期長度小於0.75倍，這可能是噪音導致的，應該忽略，不複位時鐘。但是這種情況連續出現很多次就不對了，用count記錄次數，達到一定值時要進入不穩定狀態。這個值被設置為2。

3. 周期長度大於等於1.5倍，用戶停止了搖動，直接進入不穩定狀態。事實上停止搖動后LED還會閃一下，因為不免存在抖動，導致程序又判定出一個周期。

測試過程中發現，如果突然把搖動頻率翻倍，由於有第2個分支的存在，算法會把兩個周期判定為一個；有時剛開始搖動就會這樣。解決這個問題需要在分支1和2中動點手腳：用half_flag表示分支1中clock是否是period的一半，具體來講是3/8到5/8；half_count表示連續出現“一周期中進入分支1一次且half_flag為真”的次數。當half_count達到2時就可以認為算法進入了錯誤的狀態，需要減半period以恢復正常。

bool stable;
uint16_t period;
uint8_t count;
bool half_flag;
uint8_t half_count;

void timer_handler()
{
    // ...
    uint16_t clock = clock_get();
    if (mercury_get() == MERCURY_LEFT)
    {
        if (stable)
        {
            if (clock < period * 3 / 4)
            {
                if (++count == 2)
                {
                    stable = false;
                    count = 0;
                }
                if (period * 3 / 8 < clock && clock < period * 5 / 8)
                {
                    half_flag = true;
                }
            }
            else if (clock < period * 3 / 2)
            {
                clock_reset();
                if (count == 1 && half_flag)
                {
                    if (++half_count == 2)
                    {
                        half_count = 0;
                        clock = 0;
                    }
                }
                else
                {
                    half_count = 0;
                }
                period = (period + clock) / 2;
                count = 0;
                half_flag = false;
                clock = 0;
            }
            else
            {
                stable = false;
                count = 0;
            }
        }
        else
        {
            clock_reset();
            if (period / 2 < clock && clock < period * 3 / 2)
            {
                if (++count == 2)
                {
                    stable = true;
                    period = (period + clock) / 2;
                    count = 0;
                    half_flag = false;
                    half_count = 0;
                    clock = 0;
                }
            }
            else
            {
                period = clock;
                count = 0;
            }
        }
    }
    // ...
}

 

知道了周期長度與起始時刻，也就知道了每一時刻在周期中的位置。一個周期的3/8到5/8，也就是從左到右中間的部分，可以显示圖像，显示的列隨clock均勻變化，由於中間段接近勻速，显示的圖像是比較均勻的。

為什麼不在從右到左過程中显示呢？因為周期起始的位置並不精確地是正中間，還受周期、重力和手的影響，取3/8到5/8而不是1/4到3/4就包含對這些因素的考量。如果在相差半個周期的位置也显示的話，兩幅圖像肯定無法重合，即使動態調整位置也無濟於事。

 

性能優化

也許你已經注意到，上面的代碼中從未出現過int，只有uint8_t和uint16_t等確定長度的整數類型。這樣做可以帶來可移植性，更重要的是AVR作為8位單片機對整數長度十分敏感，能用8位就不要用16位。

mega系列有雙周期硬件乘法器，但沒有硬件除法器，除數確定的除法編譯器會轉化為乘法來計算，不確定的就只能調用除法路徑了。這種除法偶爾算一次還行，每個定時器周期都算就會嚴重拖慢速度，比如這句判斷是否該切換列的語句：

if (clock == period * 3 / 8 + (uint32_t)period * phase / width / 4)
    // ...

要加uint32_t轉換是因為period是uint16_t類型，整數提升成unsigned int（int是16位整型），計算結果為unsigned類型，但實際乘積會溢出，就不得不轉換成更長的long。這下可好，每周期計算32位整數除法，同時觸犯兩條禁忌。

我的性能優化就從這裏入手，逐漸擴展到所有計算過程不太簡單但不常變化的量，它們都存儲在結構體compute中：

struct
{
    uint16_t threshold_low;
    uint16_t threshold_high;
    uint16_t half_low;
    uint16_t half_high;
    uint16_t clock_base;
    uint16_t clock_step;
    uint16_t clock_compare;
    uint16_t green_step;
    uint16_t blue_step;
    uint8_t rgbw_duty;
} compute;

clock開頭的三個變量就是用來優化前述語句的。在显示周期開始，即clock == 0時，先計算：

compute.clock_base = motion.period * 3 / 8;
compute.clock_step = motion.period / display.width;
compute.clock_compare = compute.clock_base;

compute.clock_compare就是if中與clock比較的值。在display.phase增加后，需要重新計算compute.clock_compare的值，其中除以4是可以接受的計算：

compute.clock_compare = compute.clock_base + compute.clock_step * display.phase / 4;

你也許會問，為什麼不把除以4放進compute.clock_step的計算中？考慮誤差較大的情況：motion.period == 2047, display.width == 128，compute.clock_step比理想值小了6.2%，圖像的寬度將壓縮為原來的93.8%；如果把除以4放進去，誤差會達到25.0%，這就比較嚴重了。

轉換為uint32_t先乘后除無疑是更加精準的，優化後由於整數除法只能得到整數結果而產生了更大的誤差，因此這裏的性能優化與編譯器優化還不同：編譯器要遵守“as-if”規則，而我是在用可接受的精度下降換取可觀的速度提升。

利用超綱的手段（藍牙），我得知優化前定時器中斷的執行時間超過了定時器周期的80%，優化後下降到了40%以下（都是-O3），性能提升十分明顯。擠出來的計算資源將會在下篇中派上用場。

 

一個相似的例子是漸變色模式中LED亮度（對應PWM占空比）的計算。原來的計算式為：

duty = led.green * phase / width;

優化以後為：

compute.green_step = (led.green << 8) / (display.width - 1);
duty = (compute.green_step * phase) >> 8;

如果不左移8位直接除，因為有整數除法的誤差，显示效果將是瞬變而不是漸變，所以我要先左移8位再右移8位，這與上面的除以4是類似的，只是更加顯式。

我的重點不在移位的藝術性上。請你看看優化后的第一個語句有什麼問題，已知三個變量的類型分別為uint16_t、uint8_t和uint8_t。

點擊展開答案

led.green在移位運算中被提升為int（而不是unsigned），移位運算結果為int類型，除法運算結果亦為int類型。當led.green >= 128時，除法結果為負數，賦給無符號的compute.green_step，變成無符號數與phase相乘再移位。我搞不清楚結果是個什麼東西，反正显示效果不是漸變色。

解決方法很簡單，把led.green轉換成uint16_t再參与運算即可。發現這個問題花了我一個小時，真是成也摳門敗也摳門啊！

 

下期預告

另一端的效果圖見文首。

 

後記

本文中的周期檢測算法能實現其功能，並具有一定容錯與自恢復能力，但是還不完美。

即使算法能從雙倍周期中恢復出來，半速显示仍會持續至少2個理論周期，或4個實際周期。從觀賞者的角度上看，半速显示是相當醜陋的——翻轉、拉伸、邊緣畸變、交疊，可謂集大成者。有趣的是，這種自恢復是我在寫作本文期間才想到並應用的；此前我給用戶提供的對策是按下按鍵以重置算法，然而矛盾的是用戶如果要給別人展示，自己就看不到显示效果，也就無從得知這種錯誤，只會讓觀賞者覺得我是個遜仔。

這個問題也許可以歸結於性能與容錯性的權衡：要允許噪音，就必須接受短暫的半速显示。

權衡歸權衡，真正的缺陷依然存在：算法允許穩定以後周期內出現噪音，但是如果每個周期內都有噪音，也就無法進入穩定狀態，但是信號的周期仍客觀存在。其實噪音很大程度上來源於濾波沒有濾乾淨，但濾波中的時間閾值也不能設置地太高，如果要把這種噪音留到濾波后級去解決，我就不知道該怎麼辦了。

 

和搖搖棒一樣利用POV原理的還有旋轉燈，你可以在淘寶用“旋轉 POV”關鍵字搜索。旋轉燈可以說是升級版的搖搖棒，電機代替了手，無線輸電代替了電池，显示效果也上了有一個檔次，甚至可以柱面、球面显示。不過作為靈魂的水銀開關被磁傳感器替代了，所以我感覺旋轉燈的編碼難度不會高於搖搖棒，難度更偏向於硬件設計。

前两天看到一篇微信推送，視頻里出現4根棒組成的便攜式旋轉燈，甚至有旋轉燈陣列組成的屏幕，評論區直呼看不懂，我直呼羡慕。

旋轉燈局限於面显示（球面也是面），而光立方能增加一個維度，是真正的立體显示。光立方是靜態的，唯一動的部分大概就是動態掃描了，沒有一點難度，只是焊接太累了。正因工作量大且效果花哨，送給女朋友非常合適，這一點我已經驗證過了。

光立方的致命缺陷在於分辨率低，難以提高LED數量的根本原因在於它是三維的。搖搖棒是一維的，動起來以後成為二維，不難想象二維的運動起來可以變成三維——我還真在網上見過把光立方的一個面轉起來的，分辨率與維數兼得。

這些東西記在這裏，給讀者拓寬眼界，也給我自己種棵草。

 

我沒有仔細看過別人的搖搖棒設計，在第二版的設計、裝配、編程過程中甚至沒有以“搖搖棒”為關鍵字搜索過，一方面因為網上大多都是我不會的51，另一方面我不喜歡讀別人的單片機代碼，這與51的擴展語法脫不了干係，更重要的是我覺得那些都是上個世代的代碼——我的第一版搖搖棒的程序竟然是用C++14寫的！更誇張的是，回調用的是std::vector<std::function<void()>>，後來還逐漸演化為C#中event的類似物。事實上，AVR工具鏈並沒有C++的標準庫，這兩個類模板是我自己實現的。

那時年幼無知，不懂得謙虛，包括對人與對單片機。

 

文章寫完了。除了前言和後記差強人意以外，中間的技術介紹完全就是半吊子——有所涉及，卻無法深入。譬如LED的電路，我本應詳細介紹595與PWM及其背後的思想；又譬如周期檢測，我本應帶領讀者一步一步實現這個算法。所以我只能更改本文的目標，把完整清晰地介紹搖搖棒下調為僅供讀者觀賞（如果你有意深入了解我的搖搖棒，可以後台聯繫我），甚至連這個小目標都達不到。

或許搖搖棒的材料更適合用於講座或視頻，文字這一形式對表達有所限制，然而高手不應該被表達形式限制，所以歸根結底是我太菜了。

 

不知怎的，完成了碼量是前一版幾倍的項目外加一篇博客，收穫感甚至比不上許久以前就着別人的博客實現出一個std::function。可能是這個項目對於目前的我過於簡單，這當然是件值得欣喜的事；或者，

是因為高考臨近了吧。

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※教你寫出一流的銷售文案?

※超省錢租車方案

1、java agent是什麼？

—》對用戶透明，不侵入用戶業務代碼。讓java虛擬機加載agent jar

2、java agent有什麼用？

—>應用場景例如：調用鏈追蹤項目，在用戶無感知的情況下，記錄日誌。目前業內使用該技術的有，SkyWalking,Pinpoint(這個監控的粒度更小)

-各個 Java IDE 的調試功能，例如 eclipse、IntelliJ ；

-熱部署功能，例如 JRebel、XRebel、 spring-loaded；

-各種線上診斷工具，例如 Btrace、Greys，還有阿里的 Arthas；

-各種性能分析工具，例如 Visual VM、JConsole 等

3、java agent的實現原理?

https://zhuanlan.zhihu.com/p/147375268

4、 入門案例

4.1、 如何製造自己第一個java agent jar包

4.1.1、 第一步：我們需要一個插件來幫助我們生成帶特定格式的MAINIFEST.MF的jar

4.1.2、 第二步：在啟動項目的時候，在jvm參數中添加 -javaagent: *\ving-agent-0.0.1-SNAPSHOT.jar （在jvm上先加載agent包）

（偷偷地問）特定格式的MAINIFEST.MF是怎樣的？需要包括下面的內容

Manifest-Version: 1.0
Can-Redefine-Classes: true
Can-Retransform-Classes: true
Premain-Class: cn.think.in.java.clazz.loader.asm.agent.PreMainTraceAgent

（再偷偷地問），難度每次都讓我手動去弄這個文件，我覺得很麻煩呀，有沒一個工具能幫我們將agent項目打包成包含MAINIFEST.MF的jar？
—–》對，你猜對了，真的有這個工具。那就是maven插件。（說到打包，肯定要想到maven或者gradle了吧）

            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-jar-plugin</artifactId>
                <version>2.2</version>
                <configuration>
                    <archive>
                        <manifestEntries>
                            <Project-name>${project.name}</Project-name>
                            <Project-version>${project.version}</Project-version>
                            <Premain-Class>com.tuling.agent.Agent</Premain-Class>
                            <Can-Redefine-Classes>true</Can-Redefine-Classes>
                            <Can-Retransform-Classes>true</Can-Retransform-Classes>
                            <Boot-Class-Path>javassist-3.18.1-GA.jar</Boot-Class-Path>
                        </manifestEntries>
                    </archive>
                    <skip>true</skip>
                </configuration>
            </plugin>

插件

打包之後

測試

問題二：如果有一個類已經被虛擬機加載了，那麼我們的agent包裏面的邏輯就不能加載這個類。但是我就是想把這類替換掉，怎麼辦呢？（熱更新，虛擬機不停的情況下，替換成用戶最新的代碼）

插件

agent代碼的修改

重新打包

測試

問題三：
當JVM已裝置某個類，但是我們想重新走一次premain方法，我們怎樣做呢？
插件

修改agent代碼

打包

測試

思考

看到這裏，細心的朋友，可能會帶有疑問，我在實踐的時候，發現這個類的字節碼的生成並不簡單，如果讓我自己去手動去生成那就很麻煩呀？（麻煩–》複雜度高—》容易出錯—-》上線容易出問題—》那就直接不考慮該技術）
—-》為了解決這個問題，java-ssist就出現了。關於java-ssist，請點擊。

https://www.cnblogs.com/vingLiu/p/13193517.html

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※新北清潔公司,居家、辦公、裝潢細清專業服務

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案