常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)和算法

常見(jiàn)數(shù)據(jù)結(jié)構(gòu)

1 棧

棧(stack)又名堆棧,它是一種運(yùn)算受限的線性表锯厢。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算(先進(jìn)后出)钙蒙。這一端被稱為棧頂毅贮,把另一端稱為棧底。向一個(gè)棧插入新元素又稱作進(jìn)棧驾凶、入椦栏Γ或壓棧,它是把新元素放到棧頂元素的上面调违,使之成為新的棧頂元素窟哺;從一個(gè)棧刪除元素又稱作出棧或退棧技肩,它是把棧頂元素刪除掉且轨,使其相鄰的元素成為新的棧頂元素。


棧.jpg
public class Stack {
    private int[] array = new int[5];// 棧
    private int top = -1;// 指針
    // 壓棧
    public boolean push(int x) {
        if(top<array.length-1){
            array[++top] = x;
            return true;
        }else{
            throw new RuntimeException("overFlow");//上溢
        }
    }
    // 出棧
    public int pop() {
        if (!isEmpty()) {
            return array[top--];
        } else {
            throw new RuntimeException("underflow");//下溢
        }
    }
    // 是否為空
    public boolean isEmpty() {
        return top == -1 ? true : false;
    }
}

2 隊(duì)列

隊(duì)列是一種特殊的線性表虚婿,特殊之處在于它只允許在表的前端(front)進(jìn)行刪除操作旋奢,而在表的后端(rear)進(jìn)行插入操作,和棧一樣然痊,隊(duì)列是一種操作受限制的線性表至朗。進(jìn)行插入操作的端稱為隊(duì)尾,進(jìn)行刪除操作的端稱為隊(duì)頭剧浸。

隊(duì)列.jpg

public class Queue {
    Object[] array = new Object[4]; // 對(duì)象數(shù)組锹引,此時(shí)隊(duì)列最多存儲(chǔ)3個(gè)對(duì)象
    int first = 0; // 隊(duì)首下標(biāo)
    int last = 0; // 隊(duì)尾下標(biāo);指向指向即將添加的下一個(gè)元素位置
    /**
     * 將一個(gè)對(duì)象追加到隊(duì)列尾部
     * @return 隊(duì)列滿時(shí)返回false,否則返回true
     */
    public boolean add(Object obj) {
        if ((last + 1) % array.length == first) {
            return false;
        }
        array[last] = obj;
        last = (last + 1) % array.length;
        return true;
    }
    /**
     * 隊(duì)列頭部的第一個(gè)對(duì)象出隊(duì)
     * @return 出隊(duì)的對(duì)象,隊(duì)列空時(shí)返回null
     */
    public Object remove() {
        if (last == first) {
            return null;
        }
        Object obj = array[first];
        first = (first + 1) % array.length;
        return obj;
    }
}

單向鏈表

單鏈表有一個(gè)頭節(jié)點(diǎn)head唆香,指向鏈表在內(nèi)存的首地址嫌变。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型,節(jié)點(diǎn)有兩個(gè)成員:整型成員(實(shí)際需要保存的數(shù)據(jù))和指向下一個(gè)結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址(事實(shí)上躬它,此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組)腾啥。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問(wèn)需從鏈表的頭找起,后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無(wú)論在表中訪問(wèn)那一個(gè)節(jié)點(diǎn)碑宴,都需要從鏈表的頭開(kāi)始软啼,順序向后查找。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)延柠,其指針域?yàn)榭栈雠玻瑢懽鳛?strong>NULL。

單向鏈表.jpg
public class LinkedList {
    public Node head = null;

    public void add(int x) {
        Node node = new Node(x, null);
        Node p = head;
        // 注意鏈表為空的時(shí)候的插入
        if (head == null) {
            head = node;
        }
        // 尾插法
        else {
            while (p.next != null) {
                p = p.next;
            }
            p.next = node;
        }
    }
    /**
     * 遍歷打印
     */
    public void travese(Node head) {
        Node p = head;
        while (p != null) {
            System.out.println(p.item);
            p = p.next;
        }
    }
    /*
     * 元素
     */
    private static class Node {
        int item;
        Node next;

        public Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

算法

1 排序

/** 快速排序  遞歸  比較povit后贞间,povit的左邊是小于它的數(shù)贿条,povit右邊是大于它的數(shù)  下次遞歸  */
    public void quickSort(int arr[], int low, int high) {
        int l = low;
        int h = high;
        int povit = arr[low];

        while (l < h) {
            while (l < h && arr[h] >= povit)
                h--;
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                l++;
            }

            while (l < h && arr[l] <= povit)
                l++
            if (l < h) {
                int temp = arr[h];
                arr[h] = arr[l];
                arr[l] = temp;
                h--;
            }
        }
        System.out.print("l=" + (l + 1) + "h=" + (h + 1) + "povit=" + povit + "\n");
        if (l > low) sort(arr, low, l - 1);
        if (h < high) sort(arr, l + 1, high);
    }

/** 冒泡排序  按照下標(biāo)向后相鄰數(shù)依次比較  大數(shù)向后走 
第一次下標(biāo)0(j控制)與1比較  下一次下標(biāo)1與2比較  再下一次下標(biāo)2與3比較  大的放后面 每走完一圈最大數(shù)放置到了最后
*/
    public static void bubbleSort(int[] ary) {
        for (int i = 0; i < ary.length - 1; i++) {// length-1次,最后一個(gè)不用冒了.
            for (int j = 0; j < ary.length - 1 - i; j++) {
                if (ary[j] > ary[j + 1]) {
                    int t = ary[j];  ary[j] = ary[j + 1]; ary[j + 1] = t;
                }
            }
        }
    }

    /**選擇排序    從下標(biāo)0(i控制)開(kāi)始與后面所有的數(shù)比較 ,第一輪下標(biāo)0與1增热,2整以,3...比較    下一輪 2與3,4峻仇,5...比較  大的放后面  */
    public static void selectionSort(int[] ary) {
        for(int i=0;i<ary.length-1;i++){
            for(int j=i+1;j<ary.length;j++){
                if(ary[i]>ary[j]){
                    int t = ary[i];  ary[i] = ary[j];  ary[j] = t;
                }
            }
        }
    }

    /**插入排序   從下標(biāo)1開(kāi)始 公黑,與它前面所有的數(shù)比較,比它大移到后面摄咆,比較到比它小的數(shù)為止凡蚜,就把它插到比他小的后面*/
    public static void insertSort(int[] ary){
        int t,i,j;
        for(i=1;i<ary.length;i++){
            System.out.println(Arrays.toString(ary));
            t = ary[i];
            for(j=i-1;j>=0&&ary[j]>t;j--){
                ary[j+1] = ary[j];
            }
            ary[j+1] = t;
        }
    }

2 二分法查找法

/*
 * 二分查找  假如數(shù)組是有序且按升序排列  取到中間的下標(biāo)  如果查找數(shù)大于左邊的數(shù),則左邊的數(shù)無(wú)需再搜尋吭从,直接搜尋右邊的數(shù)朝蜘。
 */
public static int search(int[] nums, int num) {
    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        // 與中間值比較確定在左邊還是右邊區(qū)間,以調(diào)整區(qū)域
        if (num > nums[mid]) {
            low = mid + 1;
        } else if (num < nums[mid]) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return -1;
}

3 位移

java中有三種移位運(yùn)算符:

<<      :     左移運(yùn)算符,num << 1,相當(dāng)于num乘以2
>>      :     右移運(yùn)算符涩金,num >> 1,相當(dāng)于num除以2
>>>    :     無(wú)符號(hào)右移谱醇,忽略符號(hào)位,空位都以0補(bǔ)齊

1010      十進(jìn)制:10     原始數(shù)         number
10100    十進(jìn)制:20     左移一位       number = number << 1;
1010      十進(jìn)制:10     右移一位       number = number >> 1;

對(duì)于:>>>
無(wú)符號(hào)右移步做,忽略符號(hào)位副渴,空位都以0補(bǔ)齊
value >>> num     --   num 指定要移位值value 移動(dòng)的位數(shù)。

無(wú)符號(hào)右移的規(guī)則只記住一點(diǎn):忽略了符號(hào)位擴(kuò)展全度,0補(bǔ)最高位  無(wú)符號(hào)右移運(yùn)算符>>> 只是對(duì)32位和64位的值有意義
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末佳晶,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子讼载,更是在濱河造成了極大的恐慌轿秧,老刑警劉巖,帶你破解...
    沈念sama閱讀 210,978評(píng)論 6 490
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件咨堤,死亡現(xiàn)場(chǎng)離奇詭異菇篡,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)一喘,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 89,954評(píng)論 2 384
  • 文/潘曉璐 我一進(jìn)店門驱还,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)嗜暴,“玉大人,你說(shuō)我怎么就攤上這事议蟆∶屏ぃ” “怎么了?”我有些...
    開(kāi)封第一講書人閱讀 156,623評(píng)論 0 345
  • 文/不壞的土叔 我叫張陵咐容,是天一觀的道長(zhǎng)舆逃。 經(jīng)常有香客問(wèn)我,道長(zhǎng)戳粒,這世上最難降的妖魔是什么路狮? 我笑而不...
    開(kāi)封第一講書人閱讀 56,324評(píng)論 1 282
  • 正文 為了忘掉前任,我火速辦了婚禮蔚约,結(jié)果婚禮上奄妨,老公的妹妹穿的比我還像新娘。我一直安慰自己苹祟,他們只是感情好砸抛,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,390評(píng)論 5 384
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著树枫,像睡著了一般锰悼。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上团赏,一...
    開(kāi)封第一講書人閱讀 49,741評(píng)論 1 289
  • 那天,我揣著相機(jī)與錄音耐薯,去河邊找鬼舔清。 笑死,一個(gè)胖子當(dāng)著我的面吹牛曲初,可吹牛的內(nèi)容都是我干的体谒。 我是一名探鬼主播,決...
    沈念sama閱讀 38,892評(píng)論 3 405
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼臼婆,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼抒痒!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起颁褂,我...
    開(kāi)封第一講書人閱讀 37,655評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤故响,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后颁独,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體彩届,經(jīng)...
    沈念sama閱讀 44,104評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,451評(píng)論 2 325
  • 正文 我和宋清朗相戀三年誓酒,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了樟蠕。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,569評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖寨辩,靈堂內(nèi)的尸體忽然破棺而出吓懈,到底是詐尸還是另有隱情,我是刑警寧澤靡狞,帶...
    沈念sama閱讀 34,254評(píng)論 4 328
  • 正文 年R本政府宣布耻警,位于F島的核電站,受9級(jí)特大地震影響耍攘,放射性物質(zhì)發(fā)生泄漏榕栏。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,834評(píng)論 3 312
  • 文/蒙蒙 一蕾各、第九天 我趴在偏房一處隱蔽的房頂上張望扒磁。 院中可真熱鬧,春花似錦式曲、人聲如沸妨托。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 30,725評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)兰伤。三九已至,卻和暖如春钧排,著一層夾襖步出監(jiān)牢的瞬間敦腔,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 31,950評(píng)論 1 264
  • 我被黑心中介騙來(lái)泰國(guó)打工恨溜, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留符衔,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 46,260評(píng)論 2 360
  • 正文 我出身青樓糟袁,卻偏偏與公主長(zhǎng)得像判族,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子项戴,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,446評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容