徹底搞懂 netty 線程模型

編者注:Netty是Java領域有名的開源網絡庫,特點是高性能和高擴展性,因此很多流行的框架都是基於它來構建的,比如我們熟知的Dubbo、Rocketmq、Hadoop等。本文就netty線程模型展開分析討論下 : )

IO模型

  • BIO:同步阻塞IO模型;
  • NIO:基於IO多路復用技術的“非阻塞同步”IO模型。簡單來說,內核將可讀可寫事件通知應用,由應用主動發起讀寫操作;
  • AIO:非阻塞異步IO模型。簡單來說,內核將讀完成事件通知應用,讀操作由內核完成,應用只需操作數據即可;應用做異步寫操作時立即返回,內核會進行寫操作排隊並執行寫操作。

NIO和AIO不同之處在於應用是否進行真正的讀寫操作。

reactor和proactor模型

  • reactor:基於NIO技術,可讀可寫時通知應用;
  • proactor:基於AIO技術,讀完成時通知應用,寫操作應用通知內核。

netty線程模型

netty的線程模型是基於Reactor模型的。

netty單線程模型

Reactor 單線程模型,是指所有的 I/O 操作都在同一個 NIO 線程上面完成的,此時NIO線程職責包括:接收新建連接請求、讀寫操作等。

在一些小容量應用場景下,可以使用單線程模型(注意,Redis的請求處理也是單線程模型,為什麼Redis的性能會如此之高呢?因為Redis的讀寫操作基本都是內存操作,並且Redis協議比較簡潔,序列化/反序列化耗費性能更低)。但是對於高負載、大併發的應用場景卻不合適,主要原因如下:

  • 一個NIO線程同時處理成百上千的連接,性能上無法支撐,即便NIO線程的CPU負荷達到100%,也無法滿足海量消息的編碼、解碼、讀取和發送。
  • 當NIO線程負載過重之後,處理速度將變慢,這會導致大量客戶端連接超時,超時之後往往會進行重發,這更加重了NIO線程的負載,最終會導致大量消息積壓和處理超時,成為系統的性能瓶頸。
  • 可靠性問題:一旦NIO線程意外跑飛,或者進入死循環,會導致整個系統通信模塊不可用,不能接收和處理外部消息,造成節點故障。

Reactor多線程模型

Rector 多線程模型與單線程模型最大的區別就是有一組 NIO 線程來處理連接讀寫操作,一個NIO線程處理Accept。一個NIO線程可以處理多個連接事件,一個連接的事件只能屬於一個NIO線程。

在絕大多數場景下,Reactor 多線程模型可以滿足性能需求。但是,在個別特殊場景中,一個 NIO 線程負責監聽和處理所有的客戶端連接可能會存在性能問題。例如併發百萬客戶端連接,或者服務端需要對客戶端握手進行安全認證,但是認證本身非常損耗性能。在這類場景下,單獨一個 Acceptor 線程可能會存在性能不足的問題,為了解決性能問題,產生了第三種 Reactor 線程模型——主從Reactor 多線程模型。

Reactor主從多線程模型

主從 Reactor 線程模型的特點是:服務端用於接收客戶端連接的不再是一個單獨的 NIO 線程,而是一個獨立的 NIO 線程池。Acceptor 接收到客戶端 TCP連接請求並處理完成后(可能包含接入認證等),將新創建的 SocketChannel注 冊 到 I/O 線 程 池(sub reactor 線 程 池)的某個I/O線程上, 由它負責SocketChannel 的讀寫和編解碼工作。Acceptor 線程池僅僅用於客戶端的登錄、握手和安全認證,一旦鏈路建立成功,就將鏈路註冊到後端 subReactor 線程池的 I/O 線程上,由 I/O 線程負責後續的 I/O 操作。

netty線程模型思考

netty 的線程模型並不是一成不變的,它實際取決於用戶的啟動參數配置。通過設置不同的啟動參數,Netty 可以同時支持 Reactor 單線程模型、多線程模型。

為了盡可能地提升性能,Netty 在很多地方進行了無鎖化的設計,例如在 I/O 線程內部進行串行操作,避免多線程競爭導致的性能下降問題。表面上看,串行化設計似乎 CPU 利用率不高,併發程度不夠。但是,通過調整 NIO 線程池的線程參數,可以同時啟動多個串行化的線程并行運行,這種局部無鎖化的串行線程設計相比一個隊列多個工作線程的模型性能更優。(小夥伴們後續多線程併發流程可參考該類實現方案

Netty 的 NioEventLoop 讀取到消息之後,直接調用 ChannelPipeline 的fireChannelRead (Object msg)。 只要用戶不主動切換線程, 一直都是由NioEventLoop 調用用戶的 ChannelHandler,期間不進行線程切換。這種串行化處理方式避免了多線程操作導致的鎖的競爭,從性能角度看是最優的。

Netty擁有兩個NIO線程池,分別是bossGroupworkerGroup,前者處理新建連接請求,然後將新建立的連接輪詢交給workerGroup中的其中一個NioEventLoop來處理,後續該連接上的讀寫操作都是由同一個NioEventLoop來處理。注意,雖然bossGroup也能指定多個NioEventLoop(一個NioEventLoop對應一個線程),但是默認情況下只會有一個線程,因為一般情況下應用程序只會使用一個對外監聽端口。

這裏試想一下,難道不能使用多線程來監聽同一個對外端口么,即多線程epoll_wait到同一個epoll實例上?

epoll相關的主要兩個方法是epoll_wait和epoll_ctl,多線程同時操作同一個epoll實例,那麼首先需要確認epoll相關方法是否線程安全:簡單來說,epoll是通過鎖來保證線程安全的, epoll中粒度最小的自旋鎖ep->lock(spinlock)用來保護就緒的隊列, 互斥鎖ep->mtx用來保護epoll的重要數據結構紅黑樹

看到這裏,可能有的小夥伴想到了Nginx多進程針對監聽端口的處理策略,Nginx是通過accept_mutex機制來保證的。accept_mutex是nginx的(新建連接)負載均衡鎖,讓多個worker進程輪流處理與client的新連接。當某個worker進程的連接數達到worker_connections配置(單個worker進程的最大處理連接數)的最大連接數的7/8時,會大大減小獲取該worker獲取accept鎖的概率,以此實現各worker進程間的連接數的負載均衡。accept鎖默認打開,關閉它時nginx處理新建連接耗時會更短,但是worker進程之間可能連接不均衡,並且存在“驚群”問題。只有在使能accept_mutex並且當前系統不支持原子鎖時,才會用文件實現accept鎖。注意,accept_mutex加鎖失敗時不會阻塞當前線程,類似tryLock。

現代linux中,多個socker同時監聽同一個端口也是可行的,nginx 1.9.1也支持這一行為。linux 3.9以上內核支持SO_REUSEPORT選項,允許多個socker bind/listen在同一端口上。這樣,多個進程可以各自申請socker監聽同一端口,當連接事件來臨時,內核做負載均衡,喚醒監聽的其中一個進程來處理,reuseport機制有效的解決了epoll驚群問題。

再回到剛才提出的問題,java中多線程來監聽同一個對外端口,epoll方法是線程安全的,這樣就可以使用使用多線程監聽epoll_wait了么,當然是不建議這樣乾的,除了epoll的驚群問題之外,還有一個就是,一般開發中我們使用epoll設置的是LT模式(水平觸發方式,與之相對的是ET默認,前者只要連接事件未被處理就會在epoll_wait時始終觸發,後者只會在真正有事件來時在epoll_wait觸發一次),這樣的話,多線程epoll_wait時就會導致第一個線程epoll_wait之後還未處理完畢已發生的事件時,第二個線程也會epoll_wait返回,顯然這不是我們想要的,關於java nio的測試demo如下:

public class NioDemo {
    private static AtomicBoolean flag = new AtomicBoolean(true);
    public static void main(String[] args) throws Exception {
        ServerSocketChannel serverChannel = ServerSocketChannel.open();
        serverChannel.socket().bind(new InetSocketAddress(8080));
        // non-block io
        serverChannel.configureBlocking(false);
        Selector selector = Selector.open();
        serverChannel.register(selector, SelectionKey.OP_ACCEPT);

        // 多線程執行
        Runnable task = () -> {
            try {
                while (true) {
                    if (selector.select(0) == 0) {
                        System.out.println("selector.select loop... " + Thread.currentThread().getName());
                        Thread.sleep(1);
                        continue;
                    }

                    if (flag.compareAndSet(true, false)) {
                        System.out.println(Thread.currentThread().getName() + " over");
                        return;
                    }

                    Iterator<SelectionKey> iter = selector.selectedKeys().iterator();
                    while (iter.hasNext()) {
                        SelectionKey key = iter.next();

                        // accept event
                        if (key.isAcceptable()) {
                            handlerAccept(selector, key);
                        }

                        // socket event
                        if (key.isReadable()) {
                            handlerRead(key);
                        }

                        /**
                         * Selector不會自己從已選擇鍵集中移除SelectionKey實例,必須在處理完通道時手動移除。
                         * 下次該通道變成就緒時,Selector會再次將其放入已選擇鍵集中。
                         */
                        iter.remove();
                    }
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        };

        List<Thread> threadList = new ArrayList<>();
        for (int i = 0; i < 2; i++) {
            Thread thread = new Thread(task);
            threadList.add(thread);
            thread.start();
        }
        for (Thread thread : threadList) {
            thread.join();
        }
        System.out.println("main end");
    }

    static void handlerAccept(Selector selector, SelectionKey key) throws Exception {
        System.out.println("coming a new client... " + Thread.currentThread().getName());
        Thread.sleep(10000);
        SocketChannel channel = ((ServerSocketChannel) key.channel()).accept();
        channel.configureBlocking(false);
        channel.register(selector, SelectionKey.OP_READ, ByteBuffer.allocate(1024));
    }

    static void handlerRead(SelectionKey key) throws Exception {
        SocketChannel channel = (SocketChannel) key.channel();
        ByteBuffer buffer = (ByteBuffer) key.attachment();
        buffer.clear();

        int num = channel.read(buffer);
        if (num <= 0) {
            // error or fin
            System.out.println("close " + channel.getRemoteAddress());
            channel.close();
        } else {
            buffer.flip();
            String recv = Charset.forName("UTF-8").newDecoder().decode(buffer).toString();
            System.out.println("recv: " + recv);

            buffer = ByteBuffer.wrap(("server: " + recv).getBytes());
            channel.write(buffer);
        }
    }
}

netty線程模型實踐

(1) 時間可控的簡單業務直接在 I/O 線程上處理

時間可控的簡單業務直接在 I/O 線程上處理,如果業務非常簡單,執行時間非常短,不需要與外部網絡交互、訪問數據庫和磁盤,不需要等待其它資源,則建議直接在業務 ChannelHandler 中執行,不需要再啟業務的線程或者線程池。避免線程上下文切換,也不存在線程併發問題。

(2) 複雜和時間不可控業務建議投遞到後端業務線程池統一處理

複雜度較高或者時間不可控業務建議投遞到後端業務線程池統一處理,對於此類業務,不建議直接在業務 ChannelHandler 中啟動線程或者線程池處理,建議將不同的業務統一封裝成 Task,統一投遞到後端的業務線程池中進行處理。過多的業務ChannelHandler 會帶來開發效率和可維護性問題,不要把 Netty 當作業務容器,對於大多數複雜的業務產品,仍然需要集成或者開發自己的業務容器,做好和Netty 的架構分層。

(3) 業務線程避免直接操作 ChannelHandler

業務線程避免直接操作 ChannelHandler,對於 ChannelHandler,IO 線程和業務線程都可能會操作,因為業務通常是多線程模型,這樣就會存在多線程操作ChannelHandler。為了盡量避免多線程併發問題,建議按照 Netty 自身的做法,通過將操作封裝成獨立的 Task 由 NioEventLoop 統一執行,而不是業務線程直接操作,相關代碼如下所示:

如果你確認併發訪問的數據或者併發操作是安全的,則無需多此一舉,這個需要根據具體的業務場景進行判斷,靈活處理。

推薦閱讀

歡迎小夥伴關注【TopCoder】閱讀更多精彩好文。

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

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

北京公車採購案 八成為電動車

北京公交集團持續落實首都空氣清淨規劃,2016年計畫採購2700輛新的公車,其中有81%將採購電動車款,以減少大眾運輸系統的碳排放量。

北京霧霾問題嚴重,改用電動車來取代汽油車是減輕空氣汙染的方法之一。2015年間,北京公交集團共置換了2306輛汽油公車為新式環保公車,其中有一半以上是新能源電動車。同時,2015年改造超過8000輛柴油公車,減少60%的氮氧化合物排放量。

在純電動車基礎設施方面,北京公交集團陸續興建吳癸電動車線路網、變電站、充電站網絡等,共有21個公車站可供純電動車充電。

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

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

北汽豪擲80億元佈局新能源汽車

2015年12月28日,北京汽車集團有限公司就“北汽新能源汽車動力電池”、“北汽集團常州產業基地”兩個專案,與常州市政府簽約。

此次北汽集團擬在常州建設的兩個項目總投資80億元,其中,北汽新能源汽車動力電池專案總投資約30億元,規劃動力電池產能達到5G瓦時,同時將以滆湖低碳濕地公園培訓中心為主體,打造北汽新能源綠色商學院,其主要目的是加強新體系電池基礎研究和關鍵技術開發,推進新一代鋰離子電池的工程化和產業化,實現對動力電池產業鏈核心環節資源掌控,以支撐北汽新能源業務需求。

而北汽集團常州產業基地專案總投資50億元,總規劃年產30萬輛整車及配套零部件、物流專案,其中一期年產15萬輛SUV、MPV和輕型客車,二期重點生產新能源汽車,打造產業生態鏈。

此前,北汽集團總投資100億元的新能源汽車和總投資50億元的通用航空兩個項目已經於今年4月和10月相繼落戶常州。

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

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

010.Kubernetes二進制部署kube-controller-manager

一 部署高可用kube-controller-manager

1.1 高可用kube-controller-manager介紹


本實驗部署一個三實例 kube-controller-manager 的集群,啟動后將通過競爭選舉機制產生一個 leader 節點,其它節點為阻塞狀態。當 leader 節點不可用時,阻塞的節點將再次進行選舉產生新的 leader 節點,從而保證服務的可用性。

為保證通信安全,本文檔先生成 x509 證書和私鑰,kube-controller-manager 在如下兩種情況下使用該證書:

  • 與 kube-apiserver 的安全端口通信;
  • 在安全端口(https,10252) 輸出 prometheus 格式的 metrics。

1.2 創建kube-controller-manager證書和私鑰

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# cat > kube-controller-manager-csr.json <<EOF
  3 {
  4   "CN": "system:kube-controller-manager",
  5   "hosts": [
  6     "127.0.0.1",
  7     "172.24.8.71",
  8     "172.24.8.72",
  9     "172.24.8.73"
 10   ],
 11   "key": {
 12     "algo": "rsa",
 13     "size": 2048
 14   },
 15   "names": [
 16     {
 17       "C": "CN",
 18       "ST": "Shanghai",
 19       "L": "Shanghai",
 20       "O": "system:kube-controller-manager",
 21       "OU": "System"
 22     }
 23   ]
 24 }
 25 EOF
 26 #創建kube-controller-manager的CA證書請求文件



解釋:

hosts 列表包含所有 kube-controller-manager 節點 IP;

CN 和 O 均為 system:kube-controller-manager,kubernetes 內置的 ClusterRoleBindings system:kube-controller-manager 賦予 kube-controller-manager 工作所需的權限。



  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# cfssl gencert -ca=/opt/k8s/work/ca.pem \
  3 -ca-key=/opt/k8s/work/ca-key.pem -config=/opt/k8s/work/ca-config.json \
  4 -profile=kubernetes kube-controller-manager-csr.json | cfssljson -bare kube-controller-manager	#生成CA密鑰(ca-key.pem)和證書(ca.pem)


1.3 分發證書和私鑰

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
  3 [root@k8smaster01 work]# for master_ip in ${MASTER_IPS[@]}
  4   do
  5     echo ">>> ${master_ip}"
  6     scp kube-controller-manager*.pem root@${master_ip}:/etc/kubernetes/cert/
  7   done


1.4 創建和分發kubeconfig


kube-controller-manager 使用 kubeconfig 文件訪問 apiserver,該文件提供了 apiserver 地址、嵌入的 CA 證書和 kube-controller-manager 證書:

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
  3 [root@k8smaster01 work]# kubectl config set-cluster kubernetes \
  4   --certificate-authority=/opt/k8s/work/ca.pem \
  5   --embed-certs=true \
  6   --server=${KUBE_APISERVER} \
  7   --kubeconfig=kube-controller-manager.kubeconfig
  8 
  9 [root@k8smaster01 work]# kubectl config set-credentials system:kube-controller-manager \
 10   --client-certificate=kube-controller-manager.pem \
 11   --client-key=kube-controller-manager-key.pem \
 12   --embed-certs=true \
 13   --kubeconfig=kube-controller-manager.kubeconfig
 14 
 15 [root@k8smaster01 work]# kubectl config set-context system:kube-controller-manager \
 16   --cluster=kubernetes \
 17   --user=system:kube-controller-manager \
 18   --kubeconfig=kube-controller-manager.kubeconfig
 19 
 20 [root@k8smaster01 work]# kubectl config use-context system:kube-controller-manager --kubeconfig=kube-controller-manager.kubeconfig
 21 
 22 [root@k8smaster01 ~]# cd /opt/k8s/work
 23 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
 24 [root@k8smaster01 work]# for master_ip in ${MASTER_IPS[@]}
 25   do
 26     echo ">>> ${master_ip}"
 27     scp kube-controller-manager.kubeconfig root@${master_ip}:/etc/kubernetes/
 28   done


1.5 創建kube-controller-manager的systemd

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
  3 [root@k8smaster01 work]# cat > kube-controller-manager.service.template <<EOF
  4 [Unit]
  5 Description=Kubernetes Controller Manager
  6 Documentation=https://github.com/GoogleCloudPlatform/kubernetes
  7 
  8 [Service]
  9 WorkingDirectory=${K8S_DIR}/kube-controller-manager
 10 ExecStart=/opt/k8s/bin/kube-controller-manager \\
 11   --profiling \\
 12   --cluster-name=kubernetes \\
 13   --controllers=*,bootstrapsigner,tokencleaner \\
 14   --kube-api-qps=1000 \\
 15   --kube-api-burst=2000 \\
 16   --leader-elect \\
 17   --use-service-account-credentials\\
 18   --concurrent-service-syncs=2 \\
 19   --bind-address=##MASTER_IP## \\
 20   --secure-port=10252 \\
 21   --tls-cert-file=/etc/kubernetes/cert/kube-controller-manager.pem \\
 22   --tls-private-key-file=/etc/kubernetes/cert/kube-controller-manager-key.pem \\
 23   --port=0 \\
 24   --authentication-kubeconfig=/etc/kubernetes/kube-controller-manager.kubeconfig \\
 25   --client-ca-file=/etc/kubernetes/cert/ca.pem \\
 26   --requestheader-allowed-names="" \\
 27   --requestheader-client-ca-file=/etc/kubernetes/cert/ca.pem \\
 28   --requestheader-extra-headers-prefix="X-Remote-Extra-" \\
 29   --requestheader-group-headers=X-Remote-Group \\
 30   --requestheader-username-headers=X-Remote-User \\
 31   --authorization-kubeconfig=/etc/kubernetes/kube-controller-manager.kubeconfig \\
 32   --cluster-signing-cert-file=/etc/kubernetes/cert/ca.pem \\
 33   --cluster-signing-key-file=/etc/kubernetes/cert/ca-key.pem \\
 34   --experimental-cluster-signing-duration=8760h \\
 35   --horizontal-pod-autoscaler-sync-period=10s \\
 36   --concurrent-deployment-syncs=10 \\
 37   --concurrent-gc-syncs=30 \\
 38   --node-cidr-mask-size=24 \\
 39   --service-cluster-ip-range=${SERVICE_CIDR} \\
 40   --pod-eviction-timeout=6m \\
 41   --terminated-pod-gc-threshold=10000 \\
 42   --root-ca-file=/etc/kubernetes/cert/ca.pem \\
 43   --service-account-private-key-file=/etc/kubernetes/cert/ca-key.pem \\
 44   --kubeconfig=/etc/kubernetes/kube-controller-manager.kubeconfig \\
 45   --logtostderr=true \\
 46   --v=2
 47 Restart=on-failure
 48 RestartSec=5
 49 
 50 [Install]
 51 WantedBy=multi-user.target
 52 EOF


1.6 分發systemd

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
  3 [root@k8smaster01 work]# for (( i=0; i < 3; i++ ))
  4   do
  5     sed -e "s/##MASTER_NAME##/${MASTER_NAMES[i]}/" -e "s/##MASTER_IP##/${MASTER_IPS[i]}/" kube-controller-manager.service.template > kube-controller-manager-${MASTER_IPS[i]}.service
  6   done						#修正相應IP
  7 [root@k8smaster01 work]# ls kube-controller-manager*.service
  8 [root@k8smaster01 ~]# cd /opt/k8s/work
  9 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
 10 [root@k8smaster01 work]# for master_ip in ${MASTER_IPS[@]}
 11   do
 12     echo ">>> ${master_ip}"
 13     scp kube-controller-manager-${master_ip}.service root@${master_ip}:/etc/systemd/system/kube-controller-manager.service
 14   done						#分發system


二 啟動並驗證

2.1 啟動kube-controller-manager 服務

  1 [root@k8smaster01 ~]# cd /opt/k8s/work
  2 [root@k8smaster01 work]# source /opt/k8s/bin/environment.sh
  3 [root@k8smaster01 work]# for master_ip in ${MASTER_IPS[@]}
  4   do
  5     echo ">>> ${master_ip}"
  6     ssh root@${master_ip} "mkdir -p ${K8S_DIR}/kube-controller-manager"
  7     ssh root@${master_ip} "systemctl daemon-reload && systemctl enable kube-controller-manager && systemctl restart kube-controller-manager"
  8   done


2.2 檢查kube-controller-manager 服務

  1 [root@k8smaster01 ~]# source /opt/k8s/bin/environment.sh
  2 [root@k8smaster01 ~]# for master_ip in ${MASTER_IPS[@]}
  3   do
  4     echo ">>> ${master_ip}"
  5     ssh root@${master_ip} "systemctl status kube-controller-manager|grep Active"
  6   done



2.3 查看輸出的 metrics

  1 [root@k8smaster01 ~]# curl -s --cacert /opt/k8s/work/ca.pem --cert /opt/k8s/work/admin.pem --key /opt/k8s/work/admin-key.pem https://172.24.8.71:10252/metrics |head


注意:以上命令在 kube-controller-manager 節點上執行。

2.4 查看權限

  1 [root@k8smaster01 ~]# kubectl describe clusterrole system:kube-controller-manager



ClusteRole system:kube-controller-manager 的權限很小,只能創建 secret、serviceaccount 等資源對象,各 controller 的權限分散到 ClusterRole system:controller:XXX 中。

當在 kube-controller-manager 的啟動參數中添加 –use-service-account-credentials=true 參數,這樣 main controller 會為各 controller 創建對應的 ServiceAccount XXX-controller。內置的 ClusterRoleBinding system:controller:XXX 將賦予各 XXX-controller ServiceAccount 對應的 ClusterRole system:controller:XXX 權限。

  1 [root@k8smaster01 ~]# kubectl get clusterrole|grep controller



如deployment controller:

  1 [root@k8smaster01 ~]# kubectl describe clusterrole system:controller:deployment-controller


2.5 查看當前leader

  1 [root@k8smaster01 ~]# kubectl get endpoints kube-controller-manager --namespace=kube-system  -o yaml



kubelet 認證和授權:https://kubernetes.io/docs/admin/kubelet-authentication-authorization/#kubelet-authorization
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

代碼注入及其拓展–逆向開發

今天繼續講述逆向開發中另一個比較重要的課程是代碼注入內容,本篇篇幅比較長,但還是有很多乾貨的,希望大家通過此篇文章更加了解逆向開發中的要點和知識點.我們將分解幾個內容,進行講解:

  1. Framework注入
  2. Dylib注入
  3. MethodSwizzle
  4. 微信示例講解
  5. 總結

讓代碼執行自己的代碼,整體方案如下:

如何讓別人的app來執行自己的代碼呢? 這就要通過代碼注入的方式來達到,而代碼注入的方式有兩種: 一種是通過framework, 一種是dylib方式,另種方案,可以通過Runtime機制

代碼注入思路:

DYLD會動態加載動態庫Framework中所有動態庫,在frameworks中加入自己的一個動態庫,然後在動態庫中hook和注入代碼.

一、FrameWork注入

 1.準備工作

  • 微信6.6.5(越獄應用)
  • MachOView軟件

  MachOView的下載地址:

  如果想看源碼如下:MachOView源碼:

  • yololib工具(給MachOView注入framework)

  yololib工具下載地址:

  • 簽名文件appsign文件

2.流程

2.1 加入準備工作,導入微信6.6.5版本以及腳本appSign.sh重簽名文件

2.2 將appSign導入到項目腳本中

 

 

 2.3 有了上面的兩個步驟后,然後編譯一下工程,會出現一個temp工程,裡面包含了payload文件

2.4 显示包內容,查看可執行文件

 2.5 我們通過MachOView軟件查看WeChat

我們看到有很多的DYLIB,代表的是加載動態庫

2.6  我們在項目中新建framework

 

2.7 新建文件用於驗證

2.8 想要達到剛加載就運行,代碼要寫在load方法

 2.9 編譯一下,查看app包位置會多出一個framework

2.10 显示包內容,在framework查看

由上可知,WJHookFrameWork已經加入成功。

2.11 但是運行並沒有成功,沒有執行load里的代碼

原因:用MachOView打開可執行的WeChat,沒有找到WJHookFrameWork

下面我們講述怎麼將WJHookFramework寫入到MachoView文件中?

3. WJHookFramework寫入到MachOView文件中

需要使用yololib工具,建議將yololib放到 /usr/local/bin

3.1 解壓越獄包

3.2 將WeChat.app显示包內容,找到WeChat可執行的文件

需要增加執行權限: chmod +x WeChat

3.3 寫入WeChat可執行文件

yololib WeChat Frameworks/WJHookFrameWork.framework/WJHookFrameWork

通過上面的過程,查看MachOView文件Load commands中是否有WJHookFrameWork

上面圖显示已經加入成功。

3.4 刪除原有的ipa,打包payload

zip -ry WeChat.ipa Payload

將WeChat.ipa放入App目錄中,刪除其他的文件夾。

 

3.5 再次運行,發現成功!!!

上面就是framework方式代碼注入。大家可以私信我,如有不懂!!!

 二、Dylib注入

2.1 新建工程,添加腳本到build phases 


加入腳本文件

2.2添加第三方庫dylib(mac os的,非ios)

2.3 添加依賴

2.4 修改第三方類庫僅限mac使用,修改Base SDK

2.5 修改signing 

2.6 腳本中注入動態庫的代碼

# ${SRCROOT} 它是工程文件所在的目錄
TEMP_PATH="${SRCROOT}/Temp"
#資源文件夾,我們提前在工程目錄下新建一個APP文件夾,裏面放ipa包
ASSETS_PATH="${SRCROOT}/APP"
#目標ipa包路徑
TARGET_IPA_PATH="${ASSETS_PATH}/*.ipa"
#清空Temp文件夾
rm -rf "${SRCROOT}/Temp"
mkdir -p "${SRCROOT}/Temp"

#----------------------------------------
# 1. 解壓IPA到Temp下
unzip -oqq "$TARGET_IPA_PATH" -d "$TEMP_PATH"
# 拿到解壓的臨時的APP的路徑
TEMP_APP_PATH=$(set -- "$TEMP_PATH/Payload/"*.app;echo "$1")
# echo "路徑是:$TEMP_APP_PATH"

#----------------------------------------
# 2. 將解壓出來的.app拷貝進入工程下
# BUILT_PRODUCTS_DIR 工程生成的APP包的路徑
# TARGET_NAME target名稱
TARGET_APP_PATH="$BUILT_PRODUCTS_DIR/$TARGET_NAME.app"
echo "app路徑:$TARGET_APP_PATH"

rm -rf "$TARGET_APP_PATH"
mkdir -p "$TARGET_APP_PATH"
cp -rf "$TEMP_APP_PATH/" "$TARGET_APP_PATH"

#----------------------------------------
# 3. 刪除extension和WatchAPP.個人證書沒法簽名Extention
rm -rf "$TARGET_APP_PATH/PlugIns"
rm -rf "$TARGET_APP_PATH/Watch"

#----------------------------------------
# 4. 更新info.plist文件 CFBundleIdentifier
#  設置:"Set : KEY Value" "目標文件路徑"
/usr/libexec/PlistBuddy -c "Set :CFBundleIdentifier $PRODUCT_BUNDLE_IDENTIFIER" "$TARGET_APP_PATH/Info.plist"

#----------------------------------------
# 5. 給MachO文件上執行權限
# 拿到MachO文件的路徑
APP_BINARY=`plutil -convert xml1 -o - $TARGET_APP_PATH/Info.plist|grep -A1 Exec|tail -n1|cut -f2 -d\>|cut -f1 -d\<`
#上可執行權限
chmod +x "$TARGET_APP_PATH/$APP_BINARY"

#----------------------------------------
# 6. 重簽名第三方 FrameWorks
TARGET_APP_FRAMEWORKS_PATH="$TARGET_APP_PATH/Frameworks"
if [ -d "$TARGET_APP_FRAMEWORKS_PATH" ];
then
for FRAMEWORK in "$TARGET_APP_FRAMEWORKS_PATH/"*
do

#簽名
/usr/bin/codesign --force --sign "$EXPANDED_CODE_SIGN_IDENTITY" "$FRAMEWORK"
done
fi

#注入
yololib "$TARGET_APP_PATH/$APP_BINARY" "Frameworks/libHankHook.dylib"

2.7 編譯運行成功(也和上面一樣在類中加入load代碼)

 

上面就是dylib方式代碼注入,希望對大家有所幫助!!!

 通過上面的兩種方式實現代碼注入,讓別人的app運行自己的app,下面總結如下:

 三、MethodSwizzle

3.1 概念

iOS 中實現AOP編程思想的方式其中之一是Method Swizzling,而 Method Swizzling 是利用Runtime特性把一個方法和另個方法的實現做替換,程序運行時修改Dispatch Table里SEL和IMP之間的映射關係.

通過swizzling method改變目標函數selector所指向實現,在新的實現中來實現所要改的內容即可.

3.2 特點

  • 繼承: 修改較多,無法敢保證他人一定繼承基類
  • 類別: 類別中重寫方法會覆蓋到原有的實現,其實,在真實的開發中,重寫方法並不是為了取代它,而是為了添加一些實現; 如果幾個類別實現了同樣的方法, 但只有一個類別的方法會被調用.
  • AOP優勢: 減少了重複代碼

3.3 代碼

@implementation NSURL (HKURL)

+(void)load
{
    Method URLWithStr = class_getClassMethod(self, @selector(URLWithString:));
    
    Method HKURL = class_getClassMethod(self, @selector(HKURLWithStr:));
    
    //交換
    method_exchangeImplementations(URLWithStr, HKURL);
}

+(instancetype)HKURLWithStr:(NSString *)str{
    //調用系統原來的方法
    NSURL * url = [NSURL HKURLWithStr:str];
    if (url == nil) {
        str = @"https://www.blog.com";
    }
    url = [NSURL HKURLWithStr:str];
    
    return url;
}

在上面的代碼中,利用method swizzling的交換方法.其他Runtime的使用方法,以及為什麼寫在load方法中,請參考本人另篇博客

拓展: 為什麼寫在load中?

  • load方法在源文件被裝載到程序中會被自動調用,不需要手動調用,也不需要該類使用不使用無關,在main()前被執行.
  • 當子類重寫了load,假如子類的類別重寫了load,load的調用順序會這樣: 父類、子類、子類類別
  • 但是如果有多個子類category都重寫了load,每個子類category中load都會調用一次
  • 假如子類沒有重寫load,子類的默認load也不會去調用父類的load.此與正常繼承不太一樣.
  • 在正常的開發中, 除了method swizzle ,其他的邏輯代碼盡量不放在load,load方法中的代碼邏輯要盡量簡單

 

四、微信示例Demo

4.1 微信–破壞註冊

4.1.1 將微信程序運行出來,如下圖所示

4.1.2 根據上面紅色找出類名,方法名

4.1.3 通過插件class-dump導出微信的.h文件

class-dump是將OC運行時聲明的信息導出來的工具, 其實可以導出.h文件. 用此工具將未經過加密的app的頭文件導出來.

使用它同樣也要講此工具拷貝到MAC的目錄下/usr/local/bin下.

4.1.4 經過sublime text來找出對應的文件

4.1.5 通過第三部分講解,利用runtime交換方法

4.1.6 結果

 

4.2 竊取微信密碼

4.2.1 找到輸入密碼框的內容

從上面看出,登錄按鈕為一個FixTitleColorButton對象,Target名字存放的地址為0x280afaa40,Action名字存放地址是0x280afac00。

4.2.2 查看賬號密碼的輸入框

發現賬號密碼輸入框對象屬於都一個對象,叫做WCUITextField

4.2.3 利用LLDB查看登錄具體的Target和Action

從上面卡出,登錄按鈕在WCAccountMainLoginViewController頁面中;

登錄點擊方法叫做onNext

4.2.4 利用Sublime查看WeChat文件

發現確實有onNext()方法,並從中看出賬號輸入框和密碼輸入框都是WCAccountTextFieldItem中,但是並沒有發現textFileld,但是可以看到WCAccountTextFieldItem是繼承於WCBaseTextFieldItem,我們再看看WCBaseTextFieldItem文件內容

看出一個m_textField對象,通過tex字段取出string。

4.2.5 在賬號欄中輸入賬號和密碼

po [(WCAccountMainLoginViewController *)0x1128bbc00 valueForKey:@"_textFieldUserPwdItem"]
po [(WCAccountTextFieldItem *)0x28328e880 valueForKey:@"m_textField"]
po [(WCUITextField *)0x112163a00 text]

通過LLDB調試輸入的密碼是123456。

4.2.6 Hook登錄,獲取密碼

+ (void)load {
    NSLog(@"來了,老弟");
    Method onNext = class_getInstanceMethod(objc_getClass("WCAccountMainLoginViewController"), sel_registerName("onNext"));
    //1.保存原始的IMP
    old_onNext = method_getImplementation(onNext);
    //2.SET
    method_setImplementation(onNext, (IMP)my_next);
}

IMP (*old_onNext)(id self,SEL _cmd);

void my_next(id self,SEL _cmd){
    // 獲取密碼
    NSString *pwd = [[[self valueForKey:@"_textFieldUserPwdItem"] valueForKey:@"m_textField"] performSelector:@selector(text)];
    NSString *accountTF = [[[self valueForKey:@"_textFieldUserNameItem"] valueForKey:@"m_textField"] performSelector:@selector(text)];
    NSLog(@"密碼是!%@",pwd);
    // 將密碼追加在賬號欄的後面
    [[[self valueForKey:@"_textFieldUserNameItem"] valueForKey:@"m_textField"] performSelector:@selector(setText:) withObject:[NSString stringWithFormat:@"%@+%@",accountTF,pwd]];
    //調用原來的方法
    old_onNext(self,_cmd);
}

上面用的是setIMP和getIMP的方式,對原方法進行Hook,也可以用class_replaceMethod(),method_exchangeImplementations()。

 

五、總結

首先從代碼注入的方式:framework和dylib兩種方式,然後講到Method swizzling方式嘗試Hook,最後又以demo的方式來闡述代碼注入和Hook,希望對大家理解逆向開發的代碼注入有所幫助!!!,歡迎大家繼續關注!!!

 

 

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

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

對於計算機相關專業我們在迷茫什麼

計算機相關專業初識–對於計算機相關專業我們在迷茫什麼

前言

由於種種原因,迫使我寫下這篇博客,我相信,初入計算機相關專業的萌新肯定很迷茫,我該學什麼,我該如何去學,我該如何學好等等問題纏繞心頭。有很多學弟學妹問我該如何去學計算機相關專業,作為過來人,我決定將我的所知所得寫下來,讓初入計算機相關專業的萌新的學習之路走得更順暢一些。

一、什麼是計算機

對於剛學習計算機相關專業的萌新來說,了解一下計算機的工作原理是十分必要的,但是在這裏我們不過多闡述,讓大家簡單了解一下就好。

讓我們先來看一下對於計算機名詞的解釋:

計算機(computer)俗稱電腦,是現代一種用於高速計算的电子計算機器,可以進行數值計算,又可以進行邏輯計算,還具有存儲記憶功能。是能夠按照程序運行,自動、高速處理海量數據的現代化智能电子設備。

划重點:

  • 我們注意到,計算機就是一種用於進行數值計算的現代化智能电子設備。需要理解的是為什麼是進行數值計算,在這裏,你會疑惑,為什麼是數值計算呢,我輸入的明明不是数字呀?這個問題很容易解釋清楚,因為計算機只是一種电子設備,它不具有人類獨立思考和不斷學習的能力,它的所有功能都是事先設定好的,所以當計算機面對輸入字符的時候,會將它統一按照ASCII(計算機編碼系統)規則轉換為數值“0”和“1”(二進制數值),所以,在計算機里,數據存儲都是用“0”和“1”(即二進制數值)來實現。

  • 還有一點值得注意,按照程序運行,那麼問題來了,程序是什麼?程序就是一組計算機能識別和執行的指令, 它以某些程序設計語言編寫,運行於某種目標結構體繫上 。舉個例子,程序就像是用英語(程序設計語言,例如c,c++)寫的文章,要讓一個懂的英語的人(編譯器,如C的編譯器gcc,這裏要注意編譯器和IDE的區別,通常IDE包含編譯器)同時也會閱讀這篇文章的人(結構體系)來閱讀、理解、標記這篇文章。

有學妹問過我,為什麼簡單的代碼,能實現豐富的效果。其實這取決於編譯器的強大能力。下面來簡單介紹一下,編輯器,編譯器,IDE(集成開發環境)的區別。

  • 編輯器:編輯器就是用來編輯的軟件,比如windows自帶的記事本就是一個編輯器, 記事本沒有語法高亮,不显示行號,當一段可執行代碼寫完后無法通過內置環境執行,必須手動輸入命令執行編譯等等一些弊端,所以很少有程序員會用記事本去寫代碼 , 寫代碼比較好用的編輯器軟件有vscode,vim,sublime,notepad++,emacs,atom等等 ,雖然編輯器原始功能不足,但是開發人員為了使編輯器更加友好,所以有很多內置插件可供使用,完全可以手動打造一個IDE。
  • 編譯器:簡單來說,編譯器就是將“一種語言(一般為高級語言,如c,c++,java,python等,計算機不可直接識別和執行)”翻譯為“另一種語言(一般為低級語言,低級語言即機器語言,機器語言是用二進制代碼錶示的計算機能直接識別和執行的一種機器指令的集合)”的程序。舉個例子,用Dev-C++寫好一段可執行"hello,world!"C語言代碼之後,我們要讓它在屏幕打印出來我們想要它輸出的"hello,world!",就需要通過gcc編譯器執行編譯后才能显示。其他語言同理。
  • IDE:集成開發環境,用於程序開發環境的應用程序,一般包含代碼編輯器編譯器調試器圖像用戶界面等工具。集成了代碼編寫程序分析程序編譯程序調試等功能。如 jetbrains 的用於Java開發的 IntelliJ IDEA 、用於JavaScript開發的WebStorm、用於Python開發Pycharm,微軟的 Visual Studio系列 ,IBM的Eclipse。

二、我們該學什麼

很多初入計算機相關專業的萌新,總是很迷茫,不知道自己該學什麼,通常是他們知道如何去學好學校開設的每一門課程,就是不知道自己該向哪些方向學習,這些方向指的是專業技能和就業方向,諸如web開發、Android/IOS開發、數據分析、人工智能、網絡安全、遊戲開發、軟件測試等等。有這種疑惑很正常,迷茫也是正常的,但我們總要讓自己了解自己所需,然後腳踏實地,一步一步去充實自己的能力。而我想做的也很簡單,就是幫助大家解除心裏的疑惑。那麼,我們開始進入正題。

1. 我們該如何選擇適合自己的方向

對於這個問題,其實是很難回答清楚的,因為每個人的興趣都不相同,所以就很難去站在自己的角度去回答疑問者的問題。但是,原理都是想通的,我相信我的經驗會幫助到你們。

  • 通常,學校每學期都會開設一門或多門語言(程序設計語言,下文同),那麼,喜歡一門語言,首先要愛上它的語言風格,諸如Java的嚴謹,Python的自由,總有一款適合你;其次,在學習語言的過程中,一定要了解它能幹什麼,市場環境如何,工作崗位多少等綜合因素,再決定要不要去深入這門語言,並且主攻自己感興趣的那個方向。

  • 對於學校沒有開設,但是自己又想學習的語言而言,該如何去選擇。首先,學校開設的語言基本是市場比較流行的語言,也符合市場需求,所以,完全可以在學校開設的語言中去選擇自己想要了解並學習的語言。此外,我們可以藉助 TIOBE ( TIOBE 編程社區指數是編程語言流行度的指標,該榜單每月更新一次,指數基於全球技術工程師、課程和第三方供應商的數量。包括流行的搜索引擎,如谷歌、必應、雅虎、維基百科、亞馬遜、YouTube 和百度都用於指數計算。 )去了解語言的流行程度,流行程度決定市場需求,以此來參考自己想要了解並學習的語言,在此附上2019年11月語言排名。

2. 主流編程語言主要應用場景

  • Java

    1. 企業級應用開發: 大到全國聯網的系統,小到中小企業的應用解決方案,Java都佔有極為重要的地位 。
    2. web後端開發: JSP+Servlet+JavaBean 是一種比較流行的開發模式。
    3. 移動領域:手機遊戲。
    4. Android App開發: android 開發只用到了JAVA的語法和JAVA SE的一小部分API。
  • C

    C語言是一門基礎語言,是其他一些語言的基礎,例如MATLAB,Object-C,Lua等.同時也是學習來比較難的語言,達到精通的程度沒有3-10年左右很難,C語言沒有比較完善的開發框架,是面向過程的一門語言,講究算法跟邏輯。

    1. 科研
    2. 服務器: 網絡核心設備,如路由器、交換機、防火牆。
    3. 操作系統:類unix系統(Linux/freebsd)
    4. 嵌入式開發: 在一個特定的硬件環境上開發與構建特定的可編程軟件系統的綜合技術。
    5. 自動化控制
  • Python

    1. 圖形處理
    2. 數學處理
    3. 文本處理
    4. 數據庫編程
    5. 網絡編程
    6. 多媒體應用
    7. pymo引擎: 運行於Symbian S60V3,Symbian S60V5,Symbian 3,Android,Windows,Linux,Mac Os,Maemo,MeeGo系統上的AVG遊戲引擎。
    8. 黑客編程
    9. 網絡安全
  • C++

    1. 遊戲開發
    2. 科學計算
    3. 網絡軟件
    4. 操作系統
    5. 設備驅動程序
    6. 移動設備
    7. 嵌入式開發
    8. 科研
    9. 編譯器
  • C#

    1. web後端開發
    2. 桌面軟件開發
    3. 人工智能
    4. 遊戲開發
  • JavaScript
    唯一能用於前後端開發的語言web前端開發
    1. web前端開發
    2. node web後端開發
    3. 操作系統
    4. 後台
    5. 桌面軟件開發
    6. 混合App
    7. 小程序
  • PHP

    1. web後端開發
    2. 桌面軟件開發
    3. 命令行腳本
  • SQL

    1. 操作數據庫
  • Swift

    1. 蘋果生態系統應用開發
  • Ruby

    1. web開發
  • R

    數據科學闖天下,左手Python右手R

    1. 機器學習
    2. 數據分析
    3. 科學計算
  • Go

    1. web後端開發
    2. 高性能服務器應用

3. 主流編程語言學習路徑(將持續更新,僅供參考)

  • JavaScript

4. 主流編程語言入門學習書籍推薦

語言 書籍
C 《嗨翻C語言》
C++ 《C++權威教程》
Java 《Java輕鬆學》
Python 《Python編程從入門到實戰》
JavaScript 《JavaScript入門經典》
PHP 《PHP編程實戰》
SQL 《SQL基礎教程》
Swift 《Swift編程權威指南》
Ruby 《Ruby從入門到精通》
R 《R語言實戰》
Go 《Go語言聖經》

5. 編程學習網站推薦

網站 網址
菜鳥教程
W3School
實驗樓
猿學
慕課網
SegmentFault
博客園
GitHub
掘金
學習數據科學
易百教程
看雲

三、總結

通篇寫完,感覺自己也重新學到了很多,學習就是一個反覆複習的過程,每次學習都能帶給自己不一樣的收穫。希望以上內容可以給初入計算機相關專業的萌新帶來一些幫助,後面我會不斷更新和優化本文,請大家持續關注。

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

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

Spring 框架常用語法進行總結

 

Spring 框架常用語法進行總結:

spring框架的二大主要的功能就是IOC和AOP。

IOC: 控制反轉(依賴注入)

AOP: 面向切面編程

學習spring最好的方法就是去看官網,裏面有詳細的說明及使用原則

介紹spring 中的註解的使用,xml配置等目前在市面上面較少。

 

首先介紹Java自帶的元註解 (元註解就是 能註解到註解上的註解,能用在其他註解上的註解 )

Java5.0定義了4個標準的meta-annotation類型

@Target :

用於描述註解的範圍,即註解在哪用。它說明了Annotation所修飾的對象範圍:Annotation可被用於 packages、types(類、接口、枚舉、Annotation類型)、類型成員(方法、構造方法、成員變量、枚舉值)、方法參數和本地變量(如循環變量、catch參數)等。取值類型(ElementType)

   CONSTRUCTOR:用於描述構造器
  FIELD:用於描述域即類成員變量
  LOCAL_VARIABLE:用於描述局部變量
  METHOD:用於描述方法
  PACKAGE:用於描述包
  PARAMETER:用於描述參數
  TYPE:用於描述類、接口(包括註解類型) 或enum聲明
  TYPE_PARAMETER:1.8版本開始,描述類、接口或enum參數的聲明
  TYPE_USE:1.8版本開始,描述一種類、接口或enum的使用聲明
  
eg :

public @interface Log {
  ......
}

 

@Retention :

用於描述註解的生命周期,表示需要在什麼級別保存該註解,即保留的時間長短。取值類型RetentionPolicy)

   SOURCE:在源文件中有效(即源文件保留)
  CLASS:在class文件中有效(即class保留)
  RUNTIME:在運行時有效(即運行時保留)  
eg:

@Target({ElementType.METHOD, ElementType.TYPE})
@Retention(RetentionPolicy.RUNTIME)
public @interface Log {
  ......
}

 

@Documented :

用於描述其它類型的annotation應該被作為被標註的程序成員的公共API,因此可以被例如javadoc此類的工具文檔化。它是一個標記註解,沒有成員。

eg :

@Target({ElementType.METHOD, ElementType.TYPE})
@Retention(RetentionPolicy.RUNTIME)
@Documented
public @interface Log {
  ......
}
@Inherited :

用於表示某個被標註的類型是被繼承的。如果一個使用了@Inherited修飾的annotation類型被用於一個class,則這個annotation將被用於該class的子類。

 

 

Spring 常用的註解

在註解配置中常用的啟動方法就是:

<--在XML中啟用方法-->
ApplicationContext applicationContext = new ClassPathXmlApplicationContext("beans.xml");
Person bean = (Person) applicationContext.getBean("person");
System.out.println(bean);

--------------------------------------------------------------------------
   <--在註解中啟用方法-->
ApplicationContext applicationContext = new AnnotationConfigApplicationContext(MainConfig.class);
Person bean = applicationContext.getBean(Person.class);
System.out.println(bean);


getBeanNamesForType:得到當前IOC容器加載進來的bean的名稱
String[] namesForType = applicationContext.getBeanNamesForType(Person.class);
for (String name : namesForType) {
System.out.println(name);
}
@Component

組件,沒有明確的角色

@Service

在業務邏輯層使用(service層)

@Repository

在數據訪問層使用(dao層)

@Controller

在展現層使用,控制器的聲明(Controller)

@Bean

注入ioc容器中,默認是以方法的名稱作為注入容器裏面的名稱,需注意@bean可以不在配置類裏面使用,不過經過@Bean註解使用過的方法所在的類也會被加載到ioc容器裏面。

//配置類==配置文件

@Configuration

告訴Spring這是一個配置類,用在一個類的上面,配置類

@Configuration == <bean id=”person” class=”com.opendev.entity.Person”></bean>

@ComponentScan

value:指定要掃描的包,用在配置類上面,告訴程序在spring中的掃包範圍

@ComponentScans

掃描多個包還有提供掃包的自定義掃包規則

 

package com.atguigu.config;

import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.ComponentScan;
import org.springframework.context.annotation.Configuration;
import org.springframework.context.annotation.FilterType;
import org.springframework.context.annotation.ComponentScan.Filter;
import org.springframework.context.annotation.ComponentScans;

import com.atguigu.bean.Person;

//配置類==配置文件
@Configuration  //告訴Spring這是一個配置類

@ComponentScans(
value = {
@ComponentScan(value="com.atguigu",includeFilters = {
/*@Filter(type=FilterType.ANNOTATION,classes={Controller.class}),
@Filter(type=FilterType.ASSIGNABLE_TYPE,classes={BookService.class}),*/
@Filter(type=FilterType.CUSTOM,classes={MyTypeFilter.class})
},useDefaultFilters = false)
}
)
//@ComponentScan value:指定要掃描的包
//excludeFilters = Filter[] :指定掃描的時候按照什麼規則排除那些組件
//includeFilters = Filter[] :指定掃描的時候只需要包含哪些組件
//FilterType.ANNOTATION:按照註解
//FilterType.ASSIGNABLE_TYPE:按照給定的類型;
//FilterType.ASPECTJ:使用ASPECTJ表達式
//FilterType.REGEX:使用正則指定
//FilterType.CUSTOM:使用自定義規則
public class MainConfig {

//給容器中註冊一個Bean;類型為返回值的類型,id默認是用方法名作為id
@Bean("person")//聲明了注入ioc容器裏面的對象為person,默認都是以方法名作為id
public Person person01(){
return new Person("lisi", 20);
}
}

 

//類中組件統一設置。滿足當前條件,這個類中配置的所有bean註冊才能生效;

@Conditional

裏面需要寫上相應接口的實現類

@Import

導入組件,id默認是組件的全類名

spring中bean的作用域

默認是單實例的

//默認是單實例的
/**
* ConfigurableBeanFactory#SCOPE_PROTOTYPE    
* @see ConfigurableBeanFactory#SCOPE_SINGLETON  
* @see org.springframework.web.context.WebApplicationContext#SCOPE_REQUEST request
* @see org.springframework.web.context.WebApplicationContext#SCOPE_SESSION sesssion
* @return\
* @Scope:調整作用域
* prototype:多實例的:ioc容器啟動並不會去調用方法創建對象放在容器中。
* 每次獲取的時候才會調用方法創建對象;
* singleton:單實例的(默認值):ioc容器啟動會調用方法創建對象放到ioc容器中。
* 以後每次獲取就是直接從容器(map.get())中拿,
* request:同一次請求創建一個實例
* session:同一個session創建一個實例
*
* 懶加載:
* 單實例bean:默認在容器啟動的時候創建對象;
* 懶加載:容器啟動不創建對象。第一次使用(獲取)Bean創建對象,並初始化;
*
*/
//@Scope("prototype")
@Lazy
@Bean("person")
public Person person(){
System.out.println("給容器中添加Person....");
return new Person("張三", 25);
}
spring中bean 的生命周期
/**
* bean的生命周期:
* bean創建---初始化----銷毀的過程
* 容器管理bean的生命周期;
* 我們可以自定義初始化和銷毀方法;容器在bean進行到當前生命周期的時候來調用我們自定義的初始化和銷毀方法
*
* 構造(對象創建)
* 單實例:在容器啟動的時候創建對象
* 多實例:在每次獲取的時候創建對象\
*
* BeanPostProcessor.postProcessBeforeInitialization
* 初始化:
* 對象創建完成,並賦值好,調用初始化方法。。。
* BeanPostProcessor.postProcessAfterInitialization
* 銷毀:
* 單實例:容器關閉的時候
* 多實例:容器不會管理這個bean;容器不會調用銷毀方法;
*
*
* 遍歷得到容器中所有的BeanPostProcessor;挨個執行beforeInitialization,
* 一但返回null,跳出for循環,不會執行後面的BeanPostProcessor.postProcessorsBeforeInitialization
*
* BeanPostProcessor原理
* populateBean(beanName, mbd, instanceWrapper);給bean進行屬性賦值
* initializeBean
* {
* applyBeanPostProcessorsBeforeInitialization(wrappedBean, beanName);
* invokeInitMethods(beanName, wrappedBean, mbd);執行自定義初始化
* applyBeanPostProcessorsAfterInitialization(wrappedBean, beanName);
*}
*
*
*
* 1)、指定初始化和銷毀方法;
* 通過@Bean指定init-method和destroy-method;
* 2)、通過讓Bean實現InitializingBean(定義初始化邏輯),
* DisposableBean(定義銷毀邏輯);
* 3)、可以使用JSR250;
* @PostConstruct:在bean創建完成並且屬性賦值完成;來執行初始化方法
* @PreDestroy:在容器銷毀bean之前通知我們進行清理工作
* 4)、BeanPostProcessor【interface】:bean的後置處理器;
* 在bean初始化前後進行一些處理工作;
* postProcessBeforeInitialization:在初始化之前工作
* postProcessAfterInitialization:在初始化之後工作
*
* Spring底層對 BeanPostProcessor 的使用;
* bean賦值,注入其他組件,@Autowired,生命周期註解功能,@Async,xxx BeanPostProcessor;
*
*
*
*/
spring中的自動裝配
/**
* 自動裝配;
* Spring利用依賴注入(DI),完成對IOC容器中中各個組件的依賴關係賦值;
*
* 1)、@Autowired:自動注入:
* 1)、默認優先按照類型去容器中找對應的組件:applicationContext.getBean(BookDao.class);找到就賦值
* 2)、如果找到多個相同類型的組件,再將屬性的名稱作為組件的id去容器中查找
* applicationContext.getBean("bookDao")
* 3)、@Qualifier("bookDao"):使用@Qualifier指定需要裝配的組件的id,而不是使用屬性名
* 4)、自動裝配默認一定要將屬性賦值好,沒有就會報錯;
* 可以使用@Autowired(required=false);
* 5)、@Primary:讓Spring進行自動裝配的時候,默認使用首選的bean;
* 也可以繼續使用@Qualifier指定需要裝配的bean的名字
* BookService{
* @Autowired
* BookDao bookDao;
* }
*
* 2)、Spring還支持使用@Resource(JSR250)和@Inject(JSR330)[java規範的註解]
* @Resource:
* 可以和@Autowired一樣實現自動裝配功能;默認是按照組件名稱進行裝配的;
* 沒有能支持@Primary功能沒有支持@Autowired(reqiured=false);
* @Inject:
* 需要導入javax.inject的包,和Autowired的功能一樣。沒有required=false的功能;
* @Autowired:Spring定義的; @Resource、@Inject都是java規範
*
* AutowiredAnnotationBeanPostProcessor:解析完成自動裝配功能;
*
* 3)、 @Autowired:構造器,參數,方法,屬性;都是從容器中獲取參數組件的值
* 1)、[標註在方法位置]:@Bean+方法參數;參數從容器中獲取;默認不寫@Autowired效果是一樣的;都能自動裝配
* 2)、[標在構造器上]:如果組件只有一個有參構造器,這個有參構造器的@Autowired可以省略,參數位置的組件還是可以自動從容器中獲取
* 3)、放在參數位置:
*
* 4)、自定義組件想要使用Spring容器底層的一些組件(ApplicationContext,BeanFactory,xxx);
* 自定義組件實現xxxAware;在創建對象的時候,會調用接口規定的方法注入相關組件;Aware;
* 把Spring底層一些組件注入到自定義的Bean中;
* xxxAware:功能使用xxxProcessor;
* ApplicationContextAware==》ApplicationContextAwareProcessor;
*
*
*
*
*/

 

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

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

工信部擬規範新能源汽車廢舊動力電池綜合利用

工業和資訊化部近日就《新能源汽車廢舊動力蓄電池綜合利用行業規範條件》向社會公開徵求意見,擬要求已在禁止建設區域投產運營的廢舊動力蓄電池綜合利用企業,要在一定期限內通過“依法搬遷、轉產”等方式逐步退出。

禁止建設區域包括:國家法律、法規、規章及規劃確定或縣級以上人民政府批准的自然保護區、生態功能保護區、風景名勝區、飲用水水源保護區、基本農田保護區和其他需要特別保護的區域等。

意見稿還對廢舊動力電池綜合利用作出規範。廢舊動力蓄電池綜合利用企業應依據相關國家、行業標準,參考新能源汽車和動力蓄電池生產企業提供的拆卸、拆解技術資訊,嚴格遵循先梯級利用後再生利用的原則,提高綜合利用水準。

根據意見稿,濕法冶煉條件下,鎳、鈷、錳的綜合回收率應不低於98%;火法冶煉條件下,鎳、稀土的綜合回收率應不低於97%;不得擅自丟棄、傾倒、焚燒與填埋廢舊動力電池中的有色金屬、石墨、塑膠、橡膠、隔膜、電解液等零部件和材料。

在能源消耗方面,意見稿規定,企業應加強對拆卸、儲存、拆解、檢測和再生利用等環節的能耗管控,努力降低綜合能耗,提高能源利用效率,鼓勵企業採用先進適用的節能技術工藝及裝備。

此外,工信部同日發佈《新能源汽車廢舊動力蓄電池綜合利用行業規範公告管理暫行辦法(徵求意見稿)》,擬對新能源汽車廢舊動力蓄電池綜合利用企業實行動態管理,委託相關專業機構負責協助做好公告管理相關工作。

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

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!

2016上海國際汽車新能源及智慧技術展覽會

創新技術 智能演繹 展會日期:2016年6月28日-30日 展會地點:上海新國際博覽中心   觀眾數量:30,000人次(預計) 展覽週期:二年一屆,2016年首屆 同期展會:上海國際汽車零部件及相關服務展覽會   主辦單位: 中國國際貿易促進委員會上海市分會 中國國際貿易促進委員會汽車行業分會 中國汽車工程學會 上海市國際展覽有限公司   展位價格: 室內光地:650元/平方米(36平米起租) 標準展位:900元/平方米(9平米起租)   參展範圍: -節能汽車、純電動車,混合動力車,燃料電池車,輕型電動車,天然氣(液化氣)車,醇類及其他代用燃料車和節能汽車。 -電池、電機、電控等核心零部件和先進技術應用;輕量化材料、整車優化設計及混合動力等節能技術產品; 自動駕駛,汽車共用,模組化(集成化)構造,汽車車載資訊系統及智慧化設備;汽車相關後市場服務及產品。 -充電樁、充電機、配電櫃、充換電池及電池管理系統、停車場充電設施、智慧監控、充電站供電解決方案、充電站-智慧電網解決方案等。 -檢測,維修,監控,實驗,安全防護裝備及媒體等.   展會諮詢: 北京盛大超越國際展覽有限公司 連絡人:岳巍 先生 電話(微信):135 5286 5285 郵箱:     附:其他推薦展會   2016中國國際汽車新能源及技術應用展覽會 節能與新能源汽車產業發展規劃成果展覽會   展會時間:2016年10月13-16日 展會地點:北京•國家會議中心 展覽規模:30,000平方米(2015年) 觀眾數量:60,000人次(2015年) 展覽週期:每年一屆,2013年首屆 詳情請點擊  

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

【其他文章推薦】

※想知道網站建置網站改版該如何進行嗎?將由專業工程師為您規劃客製化網頁設計後台網頁設計

※不管是台北網頁設計公司台中網頁設計公司,全省皆有專員為您服務

※Google地圖已可更新顯示潭子電動車充電站設置地點!!

※帶您來看台北網站建置台北網頁設計,各種案例分享

【algo&ds】2.線性表

1.線性表

線性表(英語:Linear List)是由n(n≥0)個元素()a[0],a[1],a[2]…,a[n-1]組成的。

其中:

  • 數據元素的個數n定義為表的長度 = “list”.length() (”list”.length() = 0(表裡沒有一個元素)時稱為空表)
  • 將非空的線性表(n>=1)記作:(a[0],a[1],a[2],…,a[n-1])
  • 數據元素a[i](0≤i≤n-1)只是個抽象符號,其具體含義在不同情況下可以不同

一個數據元素可以由若干個數據項組成。數據元素稱為記錄,含有大量記錄的線性表又稱為文件。這種結構具有下列特點:存在一個唯一的沒有前驅的(頭)數據元素;存在一個唯一的沒有後繼的(尾)數據元素;此外,每一個數據元素均有一個直接前驅和一個直接後繼數據元素。

2.線性表的存儲結構

  • 鏈表
    • 單鏈表
      • 動態單鏈表
      • 靜態單鏈表
    • 循環鏈表
      • 單循環鏈表
      • 雙循環鏈表
    • 靜態鏈表

3.順序表

利用數組的連續存儲空間順序存放線性表的各元素

3.1結構體定義

如果需要使用自定義的結構體來維護一個順序表,通常來講結構體的元素一般是一個固定大小的數組(可用長度足夠大),以及當前數組存放的元素個數,也即數組的長度

typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    int Last;//記錄順序表的最後一個元素的下標
} ;
struct LNode L;
List PtrL;

訪問結構體的成員

  • 訪問下標為 i 的元素:L.Data[i] 或 PtrL->Data[i]
  • 線性表的長度:L.Last+1 或 PtrL->Last+1
  • 指針變量PtrL還可以這樣訪問兩個屬性(*PtrL).Data[i](*PtrL).Last,不過這種訪問方式並不常用

而一般來講,為了簡單,不會去維護這樣一個結構體,(因為一旦維護了這個結構體,就需要去封裝相應的函數,比如說常見的插入、刪除、查找等操作),而是直接類似下面這樣

ElementType data[MaxSize];
int length;

定義一個足夠大的數組,然後定義一個對應關聯的變量來時刻維護數組的長度。

這兩種定義方式沒有什麼區別,一種是把常用操作封裝好,方便調用,另一種則是需要時刻自己維護對應的屬性。因為順序表的結構足夠簡單,所以不定義結構體也是可以的。

3.2順序表的常見操作

為了方便,這一節內容記錄的都是在定義的結構體基礎上,封裝的常見操作。

1.初始化

List MakeEmpty( ) {
    List PtrL;
    PtrL = (List )malloc( sizeof(struct LNode) );
    PtrL->Last = -1;
    return PtrL;
}

初始化的順序表,長度為0,所以Last為-1

2.查找

int Find( ElementType X, List PtrL ) {
    int i = 0;
    while( i <= PtrL->Last && PtrL->Data[i]!= X )
        i++;
    if (i > PtrL->Last) return -1; /* 如果沒找到,返回-1 */
    else return i; /* 找到后返回的是存儲位置 */
}

查找操作比較簡單,從順序表的第一個元素(下標為0開始)開始遍歷。

還有一種更加巧妙一點的實現方式,就是引入哨兵思想。

int Find( ElementType X, List PtrL ) {
    PtrL->Data[0] = x;//順序表第一個元素就是哨兵,賦值為x
    int i = PtrL->Last;//從最後一個元素開始遍歷
    while( PtrL->Data[i]!= X )
        i--;
    return i;
}

這樣做的好處很明顯,少了邊界的判斷,可以優化時間複雜度,編碼也更加簡單。

注意:這裏把下標為0的元素設置為哨兵,則要求順序表從下標為1開始存儲。而且,函數如果沒有找到,則一定返回i=0

3.插入

看圖示應該要注意,移動的方向是從后往前移,如果從前往後移,則Data[i]=Data[i+1]=…=Data[n],因為後面的元素都被前面移過來的元素給覆蓋了。

void Insert( ElementType X, int i, List PtrL ) {
    int j;
    if ( PtrL->Last == MAXSIZE-1 ) { /* 表空間已滿,不能插入*/
        printf("表滿");
        return;
    }
    if ( i < 1 || i > PtrL->Last+2) { /*檢查插入位置的合法性*/
        printf("位置不合法");
        return;
    }
    for ( j = PtrL->Last; j >= i-1; j-- )
        PtrL->Data[j+1] = PtrL->Data[j]; /*將 ai~ an倒序向後移動*/
    PtrL->Data[i-1] = X; /*新元素插入*/
    PtrL->Last++; /*Last仍指向最後元素*/
    return;
}

為什麼這裏需要判斷順序表的空間是否已滿?

因為這個數組,是在初始化之後就固定了數組可容納的元素個數MaxSize,一旦超出,則程序下標就會越界。C++提供了動態數組vector,可以很方便的支持動態擴展數組長度,而且基本的插入刪除等操作都封裝好了,可以很方便的使用。

4.刪除

同樣的,需要注意元素移動的方向,如果從后往前移,則最後面的元素會一直覆蓋到Data[i]。

void Delete( int i, List PtrL ) {
    int j;
    if( i < 1 || i > PtrL->Last+1 ) { /*檢查空表及刪除位置的合法性*/
        printf (“不存在第%d個元素”, i );
        return ;
    }
    for ( j = i; j <= PtrL->Last; j++ )
        PtrL->Data[j-1] = PtrL->Data[j]; /*將 ai+1~ an順序向前移動*/
    PtrL->Last--; /*Last仍指向最後元素*/
    return;
}

5.排序

因為排序算法比較多,本文不展開講解,可以參考以下博文,內容包括了常見的十大排序算法的算法分析,時間複雜度和空間複雜度分析以及c實現和動圖圖解。

4.鏈表

不要求邏輯上相鄰的兩個元素物理上也相鄰;通過“鏈”建立起數據元素之間的邏輯關係。插入、刪除不需要移動數據元素,只需要修改“鏈”。

4.1單鏈表

typedef struct LNode *List;
struct LNode {
    ElementType Data;
    List Next;
};
struct Lnode L;
List PtrL;
1.求表長
int Length ( List PtrL ) {
    List p = PtrL; /* p指向表的第一個結點*/
    int j = 0;
    while ( p ) {
        p = p->Next;
        j++; /* 當前p指向的是第 j 個結點*/
    }
    return j;
}

時間複雜度O(n)

2.查找

按序查找

List FindKth( int K, List PtrL ) {
    List p = PtrL;
    int i = 1;
    while (p !=NULL && i < K ) {
        p = p->Next;
        i++;
    }
    if ( i == K ) return p;
    /* 找到第K個,返回指針 */
    else return NULL;
    /* 否則返回空 */
}

時間複雜度O(n)

按值查找

List Find( ElementType X, List PtrL ) {
    List p = PtrL;
    while ( p!=NULL && p->Data != X )
        p = p->Next;
    return p;
}

時間複雜度O(n)

3.插入

(1)先構造一個新結點,用s指向;
(2)再找到鏈表的第 i-1個結點,用p指向;
(3)然後修改指針,插入結點 ( p之後插入新結點是 s)

List Insert( ElementType X, int i, List PtrL ) {
    List p, s;
    if ( i == 1 ) { /* 新結點插入在表頭 */
        s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
        s->Data = X;
        s->Next = PtrL;
        return s; /*返回新表頭指針*/
    }
    p = FindKth( i-1, PtrL ); /* 查找第i-1個結點 */
    if ( p == NULL ) { /* 第i-1個不存在,不能插入 */
        printf("參數i錯");
        return NULL;
    } else {
        s = (List)malloc(sizeof(struct LNode)); /*申請、填裝結點*/
        s->Data = X;
        s->Next = p->Next; /*新結點插入在第i-1個結點的後面*/
        p->Next = s;
        return PtrL;
    }
}
4.刪除

(1)先找到鏈表的第 i-1個結點,用p指向;
(2)再用指針s指向要被刪除的結點(p的下一個結點);
(3)然後修改指針,刪除s所指結點;
(4)最後釋放s所指結點的空間。

List Delete( int i, List PtrL ) {
    List p, s;
    if ( i == 1 ) { /* 若要刪除的是表的第一個結點 */
        s = PtrL; /*s指向第1個結點*/
        if (PtrL!=NULL) PtrL = PtrL->Next; /*從鏈表中刪除*/
        else return NULL;
        free(s); /*釋放被刪除結點 */
        return PtrL;
    }
    p = FindKth( i-1, PtrL ); /*查找第i-1個結點*/
    if ( p == NULL ) {
        printf("第%d個結點不存在", i-1);
        return NULL;
    } else if ( p->Next == NULL ) {
        printf("第%d個結點不存在", i);
        return NULL;
    } else {
        s = p->Next; /*s指向第i個結點*/
        p->Next = s->Next; /*從鏈表中刪除*/
        free(s); /*釋放被刪除結點 */
        return PtrL;
    }
}

4.2雙鏈表

雙向鏈表,又稱為雙鏈表,是的一種,它的每個數據結點中都有兩個,分別指向直接後繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和後繼結點。

typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

4.3循環鏈表

4.3.1單循環鏈表

存儲結構和單鏈表相同。

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

// 設立尾指針的單循環鏈表的12個基本操作
void InitList(LinkList *L) { // 操作結果:構造一個空的線性表L
    *L = (LinkList)malloc(sizeof(struct LNode)); // 產生頭結點,並使L指向此頭結點
    if (!*L) // 存儲分配失敗
        exit(OVERFLOW);
    (*L)->next = *L; // 指針域指向頭結點
}

void DestroyList(LinkList *L) { // 操作結果:銷毀線性表L
    LinkList q, p = (*L)->next; // p指向頭結點
    while (p != *L) { // 沒到表尾
        q = p->next;
        free(p);
        p = q;
    }
    free(*L);
    *L = NULL;
}

void ClearList(LinkList *L) /* 改變L */ { // 初始條件:線性表L已存在。操作結果:將L重置為空表
    LinkList p, q;
    *L = (*L)->next; // L指向頭結點
    p = (*L)->next; // p指向第一個結點
    while (p != *L) { // 沒到表尾
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = *L; // 頭結點指針域指向自身
}

Status ListEmpty(LinkList L) { // 初始條件:線性表L已存在。操作結果:若L為空表,則返回TRUE,否則返回FALSE
    if (L->next == L) // 空
        return TRUE;
    else
        return FALSE;
}

int ListLength(LinkList L) { // 初始條件:L已存在。操作結果:返回L中數據元素個數
    int i = 0;
    LinkList p = L->next; // p指向頭結點
    while (p != L) { // 沒到表尾
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem(LinkList L, int i, ElemType *e) { // 當第i個元素存在時,其值賦給e並返回OK,否則返回ERROR
    int j = 1; // 初始化,j為計數器
    LinkList p = L->next->next; // p指向第一個結點
    if (i <= 0 || i > ListLength(L)) // 第i個元素不存在
        return ERROR;
    while (j < i) { // 順指針向後查找,直到p指向第i個元素
        p = p->next;
        j++;
    }
    *e = p->data; // 取第i個元素
    return OK;
}

int LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { // 初始條件:線性表L已存在,compare()是數據元素判定函數
    // 操作結果:返回L中第1個與e滿足關係compare()的數據元素的位序。
    //           若這樣的數據元素不存在,則返回值為0
    int i = 0;
    LinkList p = L->next->next; // p指向第一個結點
    while (p != L->next) {
        i++;
        if (compare(p->data, e)) // 滿足關係
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(LinkList L, ElemType cur_e, ElemType *pre_e) { // 初始條件:線性表L已存在
    // 操作結果:若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅,
    //           否則操作失敗,pre_e無定義
    LinkList q, p = L->next->next; // p指向第一個結點
    q = p->next;
    while (q != L->next) { // p沒到表尾
        if (q->data == cur_e) {
            *pre_e = p->data;
            return TRUE;
        }
        p = q;
        q = q->next;
    }
    return FALSE; // 操作失敗
}

Status NextElem(LinkList L, ElemType cur_e, ElemType *next_e) { // 初始條件:線性表L已存在
    // 操作結果:若cur_e是L的數據元素,且不是最後一個,則用next_e返回它的後繼,
    //           否則操作失敗,next_e無定義
    LinkList p = L->next->next; // p指向第一個結點
    while (p != L) { // p沒到表尾
        if (p->data == cur_e) {
            *next_e = p->next->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE; // 操作失敗
}

Status ListInsert(LinkList *L, int i, ElemType e) /* 改變L */ { // 在L的第i個位置之前插入元素e
    LinkList p = (*L)->next, s; // p指向頭結點
    int j = 0;
    if (i <= 0 || i > ListLength(*L) + 1) // 無法在第i個元素之前插入
        return ERROR;
    while (j < i - 1) { // 尋找第i-1個結點
        p = p->next;
        j++;
    }
    s = (LinkList)malloc(sizeof(struct LNode)); // 生成新結點
    s->data = e; // 插入L中
    s->next = p->next;
    p->next = s;
    if (p == *L) // 改變尾結點
        *L = s;
    return OK;
}

Status ListDelete(LinkList *L, int i, ElemType *e) /* 改變L */ { // 刪除L的第i個元素,並由e返回其值
    LinkList p = (*L)->next, q; // p指向頭結點
    int j = 0;
    if (i <= 0 || i > ListLength(*L)) // 第i個元素不存在
        return ERROR;
    while (j < i - 1) { // 尋找第i-1個結點
        p = p->next;
        j++;
    }
    q = p->next; // q指向待刪除結點
    p->next = q->next;
    *e = q->data;
    if (*L == q) // 刪除的是表尾元素
        *L = p;
    free(q); // 釋放待刪除結點
    return OK;
}

void ListTraverse(LinkList L, void(*vi)(ElemType)) { // 初始條件:L已存在。操作結果:依次對L的每個數據元素調用函數vi()
    LinkList p = L->next->next; // p指向首元結點
    while (p != L->next) { // p不指向頭結點
        vi(p->data);
        p = p->next;
    }
    printf("\n");
}

4.3.2雙循環鏈表

// 線性表的雙向鏈表存儲結構
typedef struct DuLNode {
    ElemType data;
    struct DuLNode *prior, *next;
} DuLNode, *DuLinkList;

// 帶頭結點的雙向循環鏈表的基本操作(14個)
void InitList(DuLinkList *L) {
    // 產生空的雙向循環鏈表L
    *L = (DuLinkList)malloc(sizeof(DuLNode));
    if (*L)
        (*L)->next = (*L)->prior = *L;
    else
        exit(OVERFLOW);
}

void DestroyList(DuLinkList *L) {
    // 操作結果:銷毀雙向循環鏈表L
    DuLinkList q, p = (*L)->next; // p指向第一個結點
    while (p != *L) { // p沒到表頭
        q = p->next;
        free(p);
        p = q;
    }
    free(*L);
    *L = NULL;
}

void ClearList(DuLinkList L) { // 不改變L
    // 初始條件:L已存在。操作結果:將L重置為空表
    DuLinkList q, p = L->next; // p指向第一個結點
    while (p != L) { // p沒到表頭
        q = p->next;
        free(p);
        p = q;
    }
    L->next = L->prior = L; // 頭結點的兩個指針域均指向自身
}

Status ListEmpty(DuLinkList L) {
    // 初始條件:線性表L已存在。操作結果:若L為空表,則返回TRUE,否則返回FALSE
    if (L->next == L && L->prior == L)
        return TRUE;
    else
        return FALSE;
}

int ListLength(DuLinkList L) {
    // 初始條件:L已存在。操作結果:返回L中數據元素個數
    int i = 0;
    DuLinkList p = L->next; // p指向第一個結點
    while (p != L) { // p沒到表頭
        i++;
        p = p->next;
    }
    return i;
}

Status GetElem(DuLinkList L, int i, ElemType *e) {
    // 當第i個元素存在時,其值賦給e並返回OK,否則返回ERROR
    int j = 1; // j為計數器
    DuLinkList p = L->next; // p指向第一個結點
    while (p != L && j < i) { // 順指針向後查找,直到p指向第i個元素或p指向頭結點
        p = p->next;
        j++;
    }
    if (p == L || j > i) // 第i個元素不存在
        return ERROR;
    *e = p->data; // 取第i個元素
    return OK;
}

int LocateElem(DuLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) {
    // 初始條件:L已存在,compare()是數據元素判定函數
    // 操作結果:返回L中第1個與e滿足關係compare()的數據元素的位序。
    // 若這樣的數據元素不存在,則返回值為0
    int i = 0;
    DuLinkList p = L->next; // p指向第1個元素
    while (p != L) {
        i++;
        if (compare(p->data, e)) // 找到這樣的數據元素
            return i;
        p = p->next;
    }
    return 0;
}

Status PriorElem(DuLinkList L, ElemType cur_e, ElemType *pre_e) {
    // 操作結果:若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅,
    // 否則操作失敗,pre_e無定義
    DuLinkList p = L->next->next; // p指向第2個元素
    while (p != L) { // p沒到表頭
        if (p->data == cur_e) {
            *pre_e = p->prior->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE;
}

Status NextElem(DuLinkList L, ElemType cur_e, ElemType *next_e) {
    // 操作結果:若cur_e是L的數據元素,且不是最後一個,則用next_e返回它的後繼,
    // 否則操作失敗,next_e無定義
    DuLinkList p = L->next->next; // p指向第2個元素
    while (p != L) { // p沒到表頭
        if (p->prior->data == cur_e) {
            *next_e = p->data;
            return TRUE;
        }
        p = p->next;
    }
    return FALSE;
}

DuLinkList GetElemP(DuLinkList L, int i) { // 另加
    // 在雙向鏈表L中返回第i個元素的地址。i為0,返回頭結點的地址。若第i個元素不存在,
    // 返回NULL
    int j;
    DuLinkList p = L; // p指向頭結點
    if (i < 0 || i > ListLength(L)) // i值不合法
        return NULL;
    for (j = 1; j <= i; j++)
        p = p->next;
    return p;
}

Status ListInsert(DuLinkList L, int i, ElemType e) {
    // 在帶頭結點的雙鏈循環線性表L中第i個位置之前插入元素e,i的合法值為1≤i≤表長+1
    // 改進算法2.18,否則無法在第表長+1個結點之前插入元素
    DuLinkList p, s;
    if (i < 1 || i > ListLength(L) + 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i - 1); // 在L中確定第i個元素前驅的位置指針p
    if (!p) // p=NULL,即第i個元素的前驅不存在(設頭結點為第1個元素的前驅)
        return ERROR;
    s = (DuLinkList)malloc(sizeof(DuLNode));
    if (!s)
        return OVERFLOW;
    s->data = e;
    s->prior = p; // 在第i-1個元素之後插入
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    return OK;
}

Status ListDelete(DuLinkList L, int i, ElemType *e) {
    // 刪除帶頭結點的雙鏈循環線性表L的第i個元素,i的合法值為1≤i≤表長
    DuLinkList p;
    if (i < 1) // i值不合法
        return ERROR;
    p = GetElemP(L, i); // 在L中確定第i個元素的位置指針p
    if (!p) // p = NULL,即第i個元素不存在
        return ERROR;
    *e = p->data;
    p->prior->next = p->next; // 此處並沒有考慮鏈表頭,鏈表尾
    p->next->prior = p->prior;
    free(p);
    return OK;
}

void ListTraverse(DuLinkList L, void(*visit)(ElemType)) {
    // 由雙鏈循環線性表L的頭結點出發,正序對每個數據元素調用函數visit()
    DuLinkList p = L->next; // p指向頭結點
    while (p != L) {
        visit(p->data);
        p = p->next;
    }
    printf("\n");
}

void ListTraverseBack(DuLinkList L, void(*visit)(ElemType)) {
    // 由雙鏈循環線性表L的頭結點出發,逆序對每個數據元素調用函數visit()
    DuLinkList p = L->prior; // p指向尾結點
    while (p != L) {
        visit(p->data);
        p = p->prior;
    }
    printf("\n");
}

4.4靜態鏈表

前面講解的都是動態鏈表,即需要指針來建立結點之間的連接關係。而對有些問題來說結點的地址是比較小的整數(例如5位數的地址),這樣就沒有必要去建立動態鏈表,而應使用方便得多的靜態鏈表。
靜態鏈表的實現原理是hash,即通過建立一個結構體數組,並令數組的下標直接表示結點的地址,來達到直接訪問數組中的元素就能訪問結點的效果。另外,由於結點的訪問非常方便,因此靜態鏈表是不需要頭結點的。靜態鏈表結點定義的方法如下:

struct Node{
    typename data;//數據域
    int next;//指針域
}node[size];

參考資料:

  • 《算法筆記》
  • 《數據結構和算法》-極客時間專欄

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

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!