標籤: 南投搬家費用

環境資訊中心外電；姜唯 翻譯；林大利 審校；稿源：ENS

2020年第50屆世界經濟論壇年會將在1月21日於瑞士達沃斯展開，主題是「團結打造永續世界」（Stakeholders for a Cohesive and Sustainable World），呼籲企業提升氣候行動的積極度。會議為期四天，吸引來自世界各地的3,000多名與會者。

今年的會議將有多位年輕的氣候行動者參與，包括17歲的瑞典環保少女童貝里（Greta Thunberg），盼說服世界各國領導人終結化石燃料經濟。

2020年第50屆世界經濟論壇年會將在1月21日於瑞士達沃斯展開。照片來源： （CC BY-SA 2.0）

童貝里等多名行動者1月10日在《衛報》發表評論：「我們要求在今年的論壇上，所有公司、銀行、機構和政府代表立刻停止所有對化石燃料探勘和開採的投資，立刻終止所有化石燃料補貼，並立刻徹底撤資化石燃料，」

「我們要的不是2050年、2030年或是2021年前完成，我們要立刻做，現在馬上做。」

根據2019年熱帶雨林行動網（Rainforest Action Network）、銀行追蹤（BankTrack）、原民環境網絡（Indigenous Environmental Network）、國際石油改革聯盟（Oil Change International）、美國山嶽協會（Sierra Club）和地球榮譽組織（Honor the Earth）共同發表，獲全球160多個組織背書的「」報告，自2015年簽署巴黎氣候協定至今，33家主要跨國銀行總共投資了1.9兆美元於化石燃料，而且過去兩年間，每年的融資額都在增加，其中6000億美元流向了100家最積極擴張的化石燃料公司。

報告顯示，全球主要銀行的商業慣例與政府間氣候變遷專門委員會（IPCC）2018年的全球暖化特別報告形成強烈對比。IPCC的《》描繪出急速淘汰化石燃料的急迫性，並估計到2035年，全球每年對乾淨能源的投資需求為2.4兆美元。

根據國際貨幣基金組織（IMF）的資料，光是在2017年，全世界就花了5.2兆美元在補貼化石燃料，包括煤炭、石油和天然氣。

美國明尼蘇達州的礦業工廠排放有毒氣體。圖片來源：Tony Webster（CC BY 2.0）

世界經濟論壇的主辦單位清楚收到環境行動人士的訊息，並且連續第四年讓會議保持氣候中立。

論壇發言人艾爾奇（Aylin Elci）說：「我們竭盡所能減少排放，從材料和資源的使用著手，提供更多當地、當季和植物性飲食；運輸方面，該論壇的汽車和巴士車隊今年有90％為油電或電動車。」

論壇發言人坎恩（Oliver Cann）表示，論壇無法減去的溫室氣體排放，主辦單位透過投資負碳排計畫來抵消。

自2017年起，世界經濟論壇持續計算年會相關碳排，透過資助全球經過認證的排放抵銷計畫來抵消，包括工作人員和與會者搭機的產生的碳排。坎恩說，除了減少碳排放之外，這些措施還創造了就業機會，改善了生活條件。

為了抵​​消2020年年會的碳排，論壇決定繼續資助兩個關鍵計畫。一是亞馬遜森林砍伐弧線上的「Jacundá」計畫，保護95,000公頃的原始森林並永續生產橡膠、阿薩伊果和巴西堅果。該計畫由社區主導，並在特種巴西保護區中執行，傳統社區在其中有管理資源的權利。

巴西亞馬遜的「Jacundá」原始森林。圖片來源：

第二個計畫是「綠色農場生物燃氣」，利用沼氣池處理產生的甲烷作為能源，殘留物則成為瑞士當地農場的肥料。

此外，論壇還跟瑞士氣候解決方案供應商「南極」公司合作，資助世界各地多個與堆肥、乾淨爐灶、水力和風力發電相關的碳排抵銷計畫：

印度「新德里堆肥」計畫每年將德里水果和蔬菜市場的73,000噸固體廢棄物轉成堆肥。

柬埔寨國家厭氧消化計畫將18,000座農場的廢棄物轉為肥料，也取代了生質爐，自2006年起省下150,000噸的木材。

在馬利，撒哈拉沙漠覆蓋了一半以上的國土。Katene乾淨爐灶計畫在當地的爐具製造工廠創造了400個工作機會，並種植了2400平方公尺的樹木對抗沙漠化。

中國四川省麻咪澤自然保護區中，當地社區砍柴生火煮飯的需求威脅周圍的生物多樣性和大熊貓的棲息地。世界自然基金會的節柴灶推廣計畫正在努力解決這個問題。

永續的水力發電是最有效的發電方式，但建築成本是發展的一大阻礙。 在巴西，Incomex Hydro計畫已經建了三座水力發電廠，生產乾淨能源，每年減少超過83,000噸的二氧化碳，可供應14,000戶住宅電力。

減少排放仍然是世界經濟論壇2020年年會永續發展工作的重點，是其組織永續發展戰略的一部分，目的是透過抵消無法避免的排放，促進瑞士海內外的永續發展。

在2020年年會召開之前，原民環境網執行總監高圖斯（Tom Goldtooth）提醒仍在投資化石燃料的銀行：「這些銀行所投資的未來，將損害未來七代以上子子孫孫的福祉。」

World Economic Forum 2020 Aims for Sustainability DAVOS-KLOSTERS, Switzerland, January 12, 2020 (ENS)

This year’s annual meeting of the World Economic Forum will call on corporations to raise their ambitions for climate action under the theme Stakeholders for a Cohesive and Sustainable World. The meeting’s 50th edition, opening January 21 and running for four days in Davos-Klosters, will bring together over 3,000 participants from throughout the world.

Young climate activists, including Swedish climate activist Greta Thunberg, 17, will be attending the World Economic Forum this year in an effort to convince world leaders to end the fossil fuel economy.

“We demand that at this year’s Forum, participants from all companies, banks, institutions and governments immediately halt all investments in fossil fuel exploration and extraction, immediately end all fossil fuel subsidies and immediately and completely divest from fossil fuels,” wrote Thunberg and other young climate activists in an opinion piece in “The Guardian” newspaper on January 10.

“We don’t want these things done by 2050, 2030 or even 2021, we want this done now – as in right now,” they wrote.

Since the 2015 Paris Agreement on climate, 33 major global banks have collectively poured US$1.9 trillion into fossil fuels, according to a March 2019 report, “Banking on Climate Change” by six nonprofit organizations and endorsed by over 160 organizations around the world.

Released by Rainforest Action Network, BankTrack, Indigenous Environmental Network, Oil Change International, Sierra Club, and Honor the Earth, the report reveals that 33 global banks have provided US$1.9 trillion to fossil fuel companies since the adoption of the Paris climate accord at the end of 2015. The amount of financing has risen in each of the past two years.

Of this total, $600 billion went to 100 companies that are most aggressively expanding fossil fuels. The report shows that the business practices of the world’s major banks stand in contrast to a 2018 special report on global warming by the Intergovernmental Panel on Climate Change (IPCC). That report, “Global Warming of 1.5 °C,” outlined the critical need for a rapid phase-out of fossil fuels and estimated that the world’s clean energy investment needs are $2.4 trillion per year up to 2035.

In 2017 alone, the world spent $5.2 trillion subsidizing fossil fuels – coal, oil and gas – according to the International Monetary Fund.

The organizers of the World Economic Forum have already got the message. For the fourth year in a row, the annual meeting will be climate neutral.

“We do everything we can to reduce emissions in the first place,” said Forum spokeswoman Aylin Elci. This involves looking at the use of materials and resources, the food served – more local, seasonal and plant-based than ever before – and transportation. The Forum’s fleet of cars and buses is 90 percent hybrid or electric this year.

All greenhouse gas emissions that the Forum cannot eliminate, organizers offset by investing in plans that reduce emissions levels in the atmosphere, says Forum spokesman Oliver Cann.

The Forum has been calculating and offsetting all emissions connected with the annual meeting, including staff and participant air travel, by funding certified offsetting projects around the world since 2017. Beyond carbon emission reduction, these initiatives also create jobs and improved living conditions, says Cann.

To offset the 2020 Annual Meeting, the Forum has decided to continue supporting two key projects. The Jacundá project in the Amazonian Arc of Deforestation known for its disappearing tropical forest protects an area of 95,000 hectares of native forest and sustainably produced rubber, açai and brazil nuts. The project is community-led and implemented on a specific Brazilian category of protected areas in which traditional communities own the right to manage the resources.

The second project is Biogas for Greener Farms, which uses methane generated by the processing of manure in biogas digesters as energy and the residue as fertilizer for local farms in Switzerland.

Cann details other offsetting projects supported by the Forum in collaboration with South Pole, a provider of global climate solutions headquartered in Zurich, Switzerland with 17 offices around the world.

Waste Composters

Composting New Dehli ensures that solid waste from fruit and vegetable markets in Delhi, India, does not end up in landfills and transforms 73,000 tonnes of it into compost every year.

In Cambodia, the National Biodigester program not only treats waste then used as fertilizer by over 18,000 farms but also replaces biomass stoves, saving 150,000 tonnes of wood since 2006.

Clean Cookstoves

In Mali, Katene Clean Cookstoves created 400 jobs in a local stove manufacturing factory and planted 2,400m2 of trees to counter desertification in a country that is more than half covered by the Sahara Desert.

Communities gathering firewood in China’s Mamize Nature Reserve in Sichuan province threaten the surrounding biodiversity and the habitat of giant pandas, an issue the WWF Mamize Firewood-Saving Cook Stove Project has been working to address.

Clean Energy – Hydro and Wind Power

Sustainable hydro plants are the most efficient way to generate electricity, but their cost can be a barrier to construction. In Brazil, Incomex Hydro has set up three hydro plants, which produce clean energy and reduce over 83,000 tonnes of CO2 a year – the equivalent of electricity for 14,000 houses.

Reducing emissions remains the first priority of the World Economic Forum’s sustainability efforts for the Annual Meeting 2020, which forms part of its broader institutional sustainability strategy.

The aim is to use offsetting to neutralize the emissions that cannot be avoided, in a way that fosters sustainable development in Switzerland and abroad.

In advance of the 2020 annual meeting, Tom Goldtooth, executive director of the Indigenous Environmental Network, has a message for banks that are funding fossil fuel development. “These banks are funding a future that will cost the well-being of the next seven generations of life and beyond.”

※ 全文及圖片詳見：

作者

如果有一件事是重要的，如果能為孩子實現一個願望，那就是人類與大自然和諧共存。

於特有生物研究保育中心服務，小鳥和棲地是主要的研究對象。是龜毛的讀者，認為龜毛是探索世界的美德。

延伸閱讀

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

1:概述

搜索樹是一種可以進行插入，搜索，刪除等操作的數據結構，可以用作字典或優先級隊列。二叉搜索樹是最簡單的搜索樹。其左子樹的鍵值<=根節點的鍵值，右子樹的鍵值>=根節點的鍵值。

如果共有n個元素,那麼每次操作需要的O(log n)的時間.

常用知識點

• 滿二叉樹 : 一棵深度為k，且有2^k-1個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。
• 完全二叉樹 : 而在一棵二叉樹中，除最後一層外，若其餘層都是滿的，並且最後一層要麼是滿的，要麼在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2^(k-1)個恭弘=叶 恭弘子節點，至多有2^k-1個節點。

2.基本操作

1. 查找(search)
2. 插入(insert)
3. 刪除(remove)

3:操作原理

查找

假設查找的值為x,從根節點的值開始比對,如果小於根節點的值,則往左兒子繼續查找,如果大於根節點的值,則往右兒子繼續查找.依次類推.直到當前節點的值等於要查找的值.

　　以查找數值10為例

插入

按照查找的步驟即可找到插入值應該在的位置

以插入數值6為例

刪除:

有四種情況:

1: // 當前節點無左節點 ,右字節點7覆蓋5, 

: 3: // 當前節點無右節點 ,右字節點7覆蓋5, 

 : 4: // 刪除節點5的左節點沒有右節點, 只需要8作為3的右節點 ,3節點覆蓋5

: 2:  如果以上3中情況都沒有,只需要尋找當前節點的左節點的所有字節點的最大值,用最大值填充5節點 4填充5

5:完整代碼

#include <stdio.h> 
#include <stdlib.h>
struct TNode{
    int data;
    struct TNode *lt;
    struct TNode *rt;    
};
struct TNode* insrtTree(struct TNode *t,int key,int i);
void printTree(struct TNode *root);
struct TNode* delTree(struct TNode* t,int key);
int find(struct TNode* t,int key); 
int arr[1000]={0};
int main(){
    int n,m;
    int i,t;
    scanf("%d%d",&n,&m); 
    struct TNode *root=NULL;
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]); 
        root=insrtTree(root,arr[i],i);
    }
    //t=arr[m-1];
    
    /*
    if(arr[m-1]==0){
        printf("Right child");
    }else{
        printf("Light child");
    }*/
    root=delTree(root,10);
    printTree(root);
    return 0;
}

int find(struct TNode* pt,int key){
    if(pt==NULL)return NULL;
    else if(pt->data==key)return 1;
    else if(pt->data>key) return find(pt->lt,key);
    else if(pt->data<key) return find(pt->rt,key);
}
// 刪除節點 
struct TNode* delTree(struct TNode* pt,int key){
    if(pt==NULL)return NULL;
    else if(pt->data>key) pt->lt=delTree(pt->lt,key);//尋找左節點 
    else if(pt->data<key) pt->rt=delTree(pt->rt,key);//尋找右節點
    //  找到節點 處理四種情況  
    else if(pt->lt==NULL){ // 當前節點無左節點 
        struct TNode* curt=pt->rt;
        free(pt);
        return curt;
    }else if(pt->rt==NULL){// 當前節點無右節點 
        struct TNode* curt=pt->lt;
        free(pt);
        return curt;
    }else if(pt->lt->rt==NULL){// 當前節點的左節點無右節點 
        struct TNode* curt=pt->lt;
        curt->rt=pt->rt;
        free(pt);
        return curt;
    }else{ 
    // 以上不滿足就把左兒子的子孫中最大的節點, 即右子樹的右子樹的...右子樹, 
    //提到需要刪除的節點位置
            struct TNode* p;
            for(p=pt->lt;p->rt->rt!=NULL;p=p->rt);
            struct TNode* curt=p->lt;
            p->rt=curt->rt;
            curt->lt=pt->lt;
            curt->rt=pt->rt;
            free(p);
            return curt;
    }
    return pt;
}
struct TNode* insrtTree(struct TNode *t,int key,int i){
    if(t==NULL){ //處理第一個節點 以及子節點為NULL情況 
        t=(struct TNode*)malloc(sizeof(struct TNode));
        t->lt=t->rt=NULL;
        t->data=key;
        return t;
    }
    if(t->data>key){// 插入左子樹情況 
         arr[i]=1;
        t->lt=insrtTree(t->lt,key,i);
    }else{         // 插入右子樹情況
        arr[i]=0;
        t->rt=insrtTree(t->rt,key,i);
    }
    return t;
}
void printTree(struct TNode *root){
    if(root==NULL)return;
    printf("%d ",root->data);
    printTree(root->lt);
    printTree(root->rt);
}

說明: 本身學習了 https://blog.csdn.net/li_l_il/article/details/88677927 但是完善了代碼 

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

【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

※評比南投搬家公司費用收費行情懶人包大公開

目錄

前言
本文主要多方面講解java繼承，旨在讓初學者通俗易懂，至於“我爸是李剛”，反正樓主也不知道誰爸是李剛。
@

1、繼承的概述

1.1、繼承的由來

至於由來簡單一句話：多個類中存在相同屬性和行為時，將這些內容抽取到單獨一個類中，那麼多個類無需再定義這些屬性和行為。

繼承描述的是事物之間的所屬關係，這種關係是 is-a 的關係。

1.2、繼承的定義

繼承：就是子類繼承父類的屬性和行為，使得子類對象具有與父類相同的屬性、相同的行為。子類可以直接訪問父類中的非私有的屬性和行為。

這裏再聲明一點，父類又稱為超類或者基類。而子類又稱為派生類這點很基礎！

1.3、繼承的優點

1. 提高代碼的復用性。
2. 類與類之間產生關係，為多態做了完美的鋪墊（不理解沒關係，之後我會再寫一篇多態的文章）

雖然繼承的優點很多但是Java只支持單繼承，不支持多繼承。

1.4、繼承的格式

通過 extends 關鍵字，可以聲明一個子類繼承另外一個父類，定義格式如下：

  class 父類 {
   ... 
   }
   class 子類 extends 父類 { 
   ... 
   } 

2、關於繼承之後的成員變量

當類之間產生了關係后，其中各類中的成員變量，產生了哪些影響呢？ 關於繼承之後的成員變量要從兩方面下手，一是成員變量不重名方面，二是成員變量重名方面。

2.1、成員變量不重名

如果子類父類中出現不重名的成員變量，這時的訪問是沒有影響的。代碼如下：

  class liGang {
        // 父類中的成員變量。
       String name ="李剛";//------------------------------父類成員變量是name
    }
    class LiXiaoGang extends liGang {
        // 子類中的成員變量
        String name2 ="李小剛";//--------------------------子類成員變量是name2
        // 子類中的成員方法
        public void show() {
            // 訪問父類中的name，
            System.out.println("我爸是"+name);
            // 繼承而來，所以直接訪問。
            // 訪問子類中的name2
            System.out.println("我是"+name2);
        }
    }
public class Demo {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang z = new LiXiaoGang();
            // 調用子類中的show方法
            z.show();
        }
    }
    //演示結果： 我爸是李剛   我是李小剛

2.2、 成員變量重名

如果子類父類中出現重名的成員變量，這時的訪問是有影響的。代碼如下：

class liGang {
        // 父類中的成員變量。
       String name ="李剛";//------------------------------父類成員變量是name
    }
    class LiXiaoGang extends liGang {
        // 子類中的成員變量
        String name ="李小剛";//---------------------------子類成員變量也是name
        // 子類中的成員方法
        public void show() {
            // 訪問父類中的name，
            System.out.println("我爸是"+name);
            // 繼承而來，所以直接訪問。
            // 訪問子類中的name2
            System.out.println("我是"+name);
        }
    }
public class Demo {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang z = new LiXiaoGang();
            // 調用子類中的show方法
            z.show();
        }
    }
    //演示結果： 我爸是李小剛   我是李小剛

子父類中出現了同名的成員變量時，在子類中需要訪問父類中非私有成員變量時，需要使用 super 關鍵字，至於修飾父類成員變量，類似於之前學過的 this 。 使用格式 super.父類成員變量名

this表示當前對象，super則表示父類對象，用法類似！

class liGang {
        // 父類中的成員變量。
       String name ="李剛";
    }
    class LiXiaoGang extends liGang {
        // 子類中的成員變量
        String name ="李小剛";
        // 子類中的成員方法
        public void show() {
            // 訪問父類中的name，
            System.out.println("我爸是"+super.name);
            // 繼承而來，所以直接訪問。
            // 訪問子類中的name2
            System.out.println("我是"+this.name);  //當然this可省略
        }
    }
public class Demo {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang z = new LiXiaoGang();
            // 調用子類中的show方法
            z.show();
        }
    }
    //演示結果： 我爸是李剛   我是李小剛

2.3、關於繼承中成員變量值得思考的一個問題

同學你有沒有想過這樣一個問題。如果父類中的成員變量
非私有：子類中可以直接訪問。
私有：子類是不能直接訪問的。如下：

當然，同學你要自己體驗體驗編譯報錯過程，看圖沒體驗感不得勁，~嘔，你這無處安放的魅力，無理的要求，我佛了，行吧~

  class liGang2 {
        // 父類中的成員變量。
        private String name ="李剛";

    }
    class LiXiaoGang2 extends liGang2 {
        // 子類中的成員變量
        String name ="李小剛";
        // 子類中的成員方法
        public void show() {
            // 訪問父類中的name，
            System.out.println("我爸是"+super.name);//------編譯失敗不能直接訪問父類私有屬性（成員變量）
            // 繼承而來，所以直接訪問。
            // 訪問子類中的name2
            System.out.println("我是"+this.name);  //當然this可省略
        }
    }
public class PrivateVariable {
        public static void main(String[] args) {
            // 創建子類對象
            ExtendDemo.LiXiaoGang z = new ExtendDemo.LiXiaoGang();
            // 調用子類中的show方法
            z.show();
        }
    }

通常開發中編碼時，我們遵循封裝的原則，使用private修飾成員變量，那麼如何訪問父類的私有成員變量呢？其實這個時候在父類中提供公共的getXxx方法和setXxx方法就可以了。代碼如下：

class liGang {
        // 父類中的成員變量。
      private String name ="李剛";

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }
    }
    class LiXiaoGang extends liGang {
        // 子類中的成員變量
        String name ="李小剛";
        // 子類中的成員方法
        public void show() {
            // 訪問父類中的name，
            System.out.println("我爸是"+super.getName());
            // 繼承而來，所以直接訪問。
            // 訪問子類中的name2
            System.out.println("我是"+this.name);  //當然this可省略
        }
    }
public class Demo {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang z = new LiXiaoGang();
            // 調用子類中的show方法
            z.show();
        }
    }
    //演示結果： 我爸是李剛   我是李小剛

分析如下：

3、關於繼承之後的成員方法

分析完了成員變量，現在我們一起來分析分析成員方法。
想一想，當類之間產生了關係，其中各類中的成員方法，又產生了哪些影響呢？ 同樣我們依舊從兩方面分析。
#### 3.1、成員方法不重名
如果子類父類中出現不重名的成員方法，這時的調用是沒有影響的。對象調用方法時，會先在子類中查找有沒有對 應的方法，若子類中存在就會執行子類中的方法，若子類中不存在就會執行父類中相應的方法。代碼如下：

 class liGang3 {
        // 父類中的成員方法。
       public void zhuangRen1(){//--------------------------父類方法名zhuangRen1
           System.out.println("我叫李剛，人不是我撞的，別抓我，我不認識李小剛");
       }
    }
    class LiXiaoGang3 extends liGang3 {

        // 子類中的成員方法
        public void zhuangRen() {//--------------------------子類方法名zhuangRen
            System.out.println("有本事你們告去，我爸是李剛");  
        }
    }
    public class MemberMethod {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang3 liXiaoGang = new LiXiaoGang3();
            // 調用子類中的show方法
            liXiaoGang.zhuangRen();
            liXiaoGang.zhuangRen1();
        }
    }
    
打印結果：有本事你們告去，我爸是李剛
        我叫李剛，人不是我撞的，別抓我，我不認識李小剛

#### 3.2、成員方法重名 【方法重寫】
成員方法重名大體也可以分兩種情況：

1、方法名相同返回值類型、參數列表卻不相同（優先在子類查找，沒找到就去父類）
2、方法名、返回值類型、參數列表都相同，沒錯這就是重寫(Override)

這裏主要講方法重寫 ：子類中出現與父類一模一樣的方法時（返回值類型，方法名和參數列表都相同），會出現覆蓋效果，也稱為重寫或者複寫。聲明不變，重新實現。 代碼如下：

    class liGang3 {
        // 父類中的成員方法。
       public void zhuangRen(int a){
           System.out.println("我叫李剛，人不是我撞的，別抓我");
       }
    }
    class LiXiaoGang3 extends liGang3 {

        // 子類中的成員方法
        public void zhuangRen(int a) {
            System.out.println("有本事你們告去，我爸是李剛");
        }
    }
    public class MemberMethod {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang3 liXiaoGang = new LiXiaoGang3();
            // 調用子類中的zhuangRen方法
            liXiaoGang.zhuangRen(1);

        }
    }
    結果打印：有本事你們告去，我爸是李剛

#### 3.3、繼承中重寫方法的意義
子類可以根據需要，定義特定於自己的行為。既沿襲了父類的功能名稱，又根據子類的需要重新實現父類方法，從而進行擴展增強。比如李剛會開車，李小剛就牛了，在父類中進行擴展增強還會開車撞人，代碼如下：

 class liGang3 {
        // 父類中的成員方法。
       public void kaiChe(){
           System.out.println("我會開車");
       }
    }
    class LiXiaoGang3 extends liGang3 {
        // 子類中的成員方法
        public void kaiChe(){
            super.kaiChe();
            System.out.println("我還會撞人");
            System.out.println("我還能一撞撞倆婆娘");
        }
    }
    public class MemberMethod {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang3 liXiaoGang = new LiXiaoGang3();
            // 調用子類中的zhuangRen方法
            liXiaoGang.kaiChe();

打印結果：   我會開車
           我還會撞人
           我還能一撞撞倆婆娘
        }
    }

不知道同學們發現了沒有，以上代碼中在子類中使用了 super.kaiChe()；super.父類成員方法，表示調用父類的成員方法。

最後重寫必須注意這幾點：

1、方法重寫時， 方法名與形參列表必須一致。
2、子類方法覆蓋父類方法時，必須要保證子類權限 >= 父類權限。
3、方法重寫時，子類的返回值類型必須要 <= 父類的返回值類型。
4、方法重寫時，子類拋出的異常類型要 <= 父類拋出的異常類型。

粗心的同學看黑板，look 這裏【注意：只有訪問權限是>=，返回值、異常類型都是<=】

下面以修飾權限為例，如下：

4、關於繼承之後的構造方法

為了讓你更好的體會，首先我先編寫一個程序

   class liGang4 {
        // 父類的無參構造方法。
        public liGang4(){
            System.out.println("父類構造方法執行了。。。");
        }
    }
    class LiXiaoGang4 extends liGang4 {
        // 子類的無參構造方法。
       public LiXiaoGang4(){
           System.out.println("子類構造方法執行了====");
       }
    }
    public class ConstructionDemo {
        public static void main(String[] args) {
            // 創建子類對象
            LiXiaoGang4 z = new LiXiaoGang4();

        }
    }

用一分鐘猜想一下結果是什麼，猜好了再看下面結果：

父類構造方法執行了。。。
子類構造方法執行了====

好了，看了結果之後，你可能有疑惑。父類構造器方法怎麼執行了？我們先來分析分析，首先在main方法中實例化了子類對象，接着會去執行子類的默認構造器初始化，這個時候在構造方法中默認會在第一句代碼中添加super();沒錯，他就是開掛般的存在，不寫也存在的！有的調~讀四聲“跳”~皮的同學就會說，你說存在就存在啊，無憑無據 ~呀，你這個該死的靚仔~ 如下：

構造方法的名字是與類名一致的，所以子類是無法繼承父類構造方法的。 構造方法的作用是初始化成員變量的。所以子類的初始化過程中，必須先執行父類的初始化動作。子類的構造方法中默認會在第一句代碼中添加super()，表示調用父類的構造方法，父類成員變量初始化后，才可以給子類使用。

當然我已經強調很多遍了 super() 不寫也默認存在，而且只能是在第一句代碼中,不在第一句代碼中行不行，答案是當然不行，這樣會編譯失敗，如下：

5、關於繼承的多態性支持的例子

直接上代碼了喔

class A{
    public String show(C obj) {
        return ("A and C");
    }

    public String show(A obj) {
        return ("A and A");
    }

}
class B extends A{
    public String show(B obj) {
        return ("B and B");
    }
}
class C extends B{
    public String show(A obj) {
        return ("A and B");
    }
}
public class Demo1 {
    public static void main(String[] args) {
        A a=new A();
        B b=new B();
        C c=new C();
        System.out.println("第一題 " + a.show(a));
        System.out.println("第二題 " + a.show(b));
        System.out.println("第三題 " + a.show(c));
    }
}
運行結果：
        第一題 A and A
        第二題 A and A
        第三題 A and C

其實吧，第一題和第三題都好理解，第二題就有點意思了，會發現A類中沒有B類型這個參數，這個時候，你就應該知道子類繼承就是父類，換句話說就是子類天然就是父類，比如中國人肯定是人，但是人不一定是中國人（可能是火星人也可能是非洲人），所以父類做為參數類型，直接傳子類的參數進去是可以的，反過來，子類做為參數類型，傳父類的參數進去，就需要強制類型轉換。

6、super與this的用法

了解他們的用法之前必須明確一點的是父類空間優先於子類對象產生

在每次創建子類對象時，先初始化父類空間，再創建其子類對象本身。目的在於子類對象中包含了其對應的父類空間，便可以包含其父類的成員，如果父類成員非private修飾，則子類可以隨意使用父類成員。代碼體現在子類的構 造方法調用時，一定先調用父類的構造方法。理解圖解如下：

#### 5.1、 super和this的含義：

super ：代表父類的存儲空間標識(可以理解為父親的引用)。

 

this ：代表當前對象的引用(誰調用就代表誰)。

#### 5.2、 super和this訪問成員

this.成員變量 ‐‐ 本類的
super.成員變量 ‐‐ 父類的
this.成員方法名() ‐‐ 本類的
super.成員方法名() ‐‐ 父類的

#### 5.3、super和this訪問構造方法

this(...) ‐‐ 本類的構造方法
super(...) ‐‐ 父類的構造方法

#### 5.4、super()和this()能不能同時使用?

不能同時使用，this和super不能同時出現在一個構造函數裏面，因為this必然會調用其它的構造函數，其它的構造函數必然也會有super語句的存在，所以在同一個構造函數裏面有相同的語句，就失去了語句的意義，編譯器也不會通過。
#### 5.5、總結一下super與this

子類的每個構造方法中均有默認的super()，調用父類的空參構造。手動調用父類構造會覆蓋默認的super()。 super() 和 this() 都必須是在構造方法的第一行，所以不能同時出現。

到這裏，java繼承你get到了咩，get到了請咩一聲，隨便隨手~點個讚唄~

推薦閱讀本專欄的下一篇java文章

歡迎各位關注我的公眾號，一起探討技術，嚮往技術，追求技術…

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

【其他文章推薦】

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

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

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

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

一 部署高可用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.線性表

線性表（英語：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];

參考資料：

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

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

【其他文章推薦】

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

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

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

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

一、故事的起因

JDK1.8最重要的就是引入了紅黑樹的設計（當衝突的鏈表長度超過8個的時候），為什麼要這樣設計呢？好處就是避免在最極端的情況下衝突鏈表變得很長很長，在查詢的時候，效率會非常慢。

• 紅黑樹查詢：其訪問性能近似於折半查找，時間複雜度O(logn)；
• 鏈表查詢：這種情況下，需要遍歷全部元素才行，時間複雜度O(n)；

本文主要是講解紅黑樹的實現，只有充分理解了紅黑樹，對於後面的分析才會更加順利。

簡單的說，紅黑樹是一種近似平衡的二叉查找樹，其主要的優點就是“平衡“，即左右子樹高度幾乎一致，以此來防止樹退化為鏈表，通過這種方式來保障查找的時間複雜度為log(n)。

關於紅黑樹的內容，網上給出的內容非常多，主要有以下幾個特性：

• 1、每個節點要麼是紅色，要麼是黑色，但根節點永遠是黑色的；
• 2、每個紅色節點的兩個子節點一定都是黑色；
• 3、紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）；
• 4、從任一節點到其子樹中每個恭弘=叶 恭弘子節點的路徑都包含相同數量的黑色節點；
• 5、所有的恭弘=叶 恭弘節點都是是黑色的（注意這裏說恭弘=叶 恭弘子節點其實是上圖中的 NIL 節點）；

在樹的結構發生改變時（插入或者刪除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的條件。

二、調整方式

上面已經說到當樹的結構發生改變時，紅黑樹的條件可能被破壞，需要通過調整使得查找樹重新滿足紅黑樹的條件。

調整可以分為兩類：一類是顏色調整，即改變某個節點的顏色，這種比較簡單，直接將節點顏色進行轉換即可；另一類是結構調整，改變檢索樹的結構關係。結構調整主要包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）。

2.1、左旋

左旋的過程是將p的右子樹繞p逆時針旋轉，使得p的右子樹成為p的父親，同時修改相關節點的引用，使左子樹的深度加1，右子樹的深度減1，通過這種做法來調整樹的穩定性。過程如下：

以jdk1.8為例，打開HashMap的源碼部分，紅黑樹內部類TreeNode屬性分析：

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        //指向父節點的指針
        TreeNode<K,V> parent;
        //指向左孩子的指針
        TreeNode<K,V> left;
        //指向右孩子的指針
        TreeNode<K,V> right;
        //前驅指針，跟next屬性相反的指向
        TreeNode<K,V> prev;
        //是否為紅色節點
        boolean red;
        ......
}

左旋方法rotateLeft如下：

/*
 * 左旋邏輯
 */
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            //root:表示根節點
            //p:表示要調整的節點
            //r:表示p的右節點
            //pp:表示p的parent節點
            //rl:表示p的右孩子的左孩子節點
            TreeNode<K,V> r, pp, rl;
            //r判斷，如果r為空則旋轉沒有意義
            if (p != null && (r = p.right) != null) {
                //多個等號的連接操作從右往左看，設置rl的父親為p
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //判斷p的父親，為空，為根節點，根節點的話就設置為黑色
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                //判斷p節點是左兒子還是右兒子
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                r.left = p;
                p.parent = r;
            }
            return root;
}

2.2、右旋

了解了左旋轉之後，相應的就會有右旋，邏輯基本也是一樣，只是方向變了。右旋的過程是將p的左子樹繞p順時針旋轉，使得p的左子樹成為p的父親，同時修改相關節點的引用，使右子樹的深度加1，左子樹的深度減1，通過這種做法來調整樹的穩定性。實現過程如下：

同樣的，右旋方法rotateRight如下：

/*
 * 右旋邏輯
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            //root:表示根節點
            //p:表示要調整的節點
            //l:表示p的左節點
            //pp:表示p的parent節點
            //lr:表示p的左孩子的右孩子節點
            TreeNode<K,V> l, pp, lr;
            //l判斷，如果l為空則旋轉沒有意義
            if (p != null && (l = p.left) != null) {
                //多個等號的連接操作從右往左看，設置lr的父親為p
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                //判斷p的父親，為空，為根節點，根節點的話就設置為黑色
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                //判斷p節點是右兒子還是左兒子
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                l.right = p;
                p.parent = l;
            }
            return root;
}

三、操作示例介紹

3.1、插入調整過程圖解

3.2、刪除調整過程圖解

3.3、查詢過程圖解

四、總結

至此，紅黑樹的實現就基本完成了，關於紅黑樹的結構，有很多種情況，情況也比較複雜，但是整體調整流程，基本都是先調整結構然後調整顏色，直到最後滿足紅黑樹特性要求為止。整篇文章，如果有理解不當之處，歡迎指正！

五、參考

1、
2、

作者：炸雞可樂
出處：

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

【其他文章推薦】

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

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

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

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