线性表-顺序存储结构（数据结构及算法02）

一、顺序存储结构：

image.png

a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继
n为线性表的长度，若n==0时，线性表为空表。

image.png

线性表优缺点：

优点：尾插效率高，支持随机访问。
缺点：中间插入或者删除效率低。
应用：数组、ArrayList

二、链式存储结构：

image.png

三、蛮力法（brute force method，也称为穷举法或枚举法):

是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。但是，用蛮力法设计的算法时间特性往往也是最低的，典型的指数时间算法一般都是通过蛮力搜索而得到的。（即输入资料的数量依线性成长，所花的时间将会以指数成长）

1、冒泡排序：

应用：数据量足够小，比如斗牛游戏的牌面排序

多关键字排序

public  void bubbleSort(int[] array){
    //3 1 5 8 2 9 4 6 7    n*(n-1)/2    n
    for(int i=array.length-1;i>0;i--) {
        boolean flag=true;
        for (int j = 0; j < i; j++) {
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag=false;
            }
        }
        if(flag){
            break;
        }
    }
}

2、选择排序：

快速排序的基础

    /**
     * 选择排序法
     * @param array
     */
    public  void selectSort(int[] array){
        for(int i=0;i<array.length-1;i++) {
            int index = i;
            for (int j = i+1; j < array.length; j++) {
                if (array[j] < array[index]) {
                    index = j;
                }
            }
            if(index!=i) {
                //如果已经是最小的，就不需要交换
                int temp = array[index];
                array[index] = array[i];
                array[i] = temp;
            }
        }
    }

测试代码：

   @Test
   public void testSort(){
       int[] array=new int[]{3,2,5,8,1,9,4,6,7,10,0};
       for (int i : array) {
           System.out.print(i+" ");
       }
       System.out.println("\r");
//        bubbleSort(array);
       selectSort(array);
       for (int i : array) {
           System.out.print(i+" ");
       }
   }

打印结果：

3 2 5 8 1 9 4 6 7 10 0
0 1 2 3 4 5 6 7 8 9 10

四、递归基础

程序调用自身的编程技巧称为递归（recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

斐波那契数列、汉诺塔算法

使用场景:Poker 花色、点数综合排序

Poker实体对象:

public class Cards implements Comparable{
    public int pokerColors;//花色
    public int cardPoints;//点数
    public Cards(int pokerColors, int cardPoints) {
        this.pokerColors = pokerColors;
        this.cardPoints = cardPoints;
    }
    //提供一个方法，用来比较对象的大小
    @Override
    public int compareTo(@NonNull Object o) {
        Cards c=(Cards)o;
        if(this.cardPoints>c.cardPoints){
            return 1;
        }else if(this.cardPoints<c.cardPoints){
            return -1;
        }
        //点数相等，判断花色
        if(this.pokerColors>c.pokerColors){
            return 1;
        }else if(this.pokerColors<c.pokerColors){
            return -1;
        }
        return 0;
    }
    @Override
    public String toString() {
        return "Cards{" +
                "pokerColors=" + pokerColors +
                ", cardPoints=" + cardPoints +
                '}';
    }
}

冒泡排序:

    public void bubbleSort(Cards[] array){  
        for(int i=array.length-1;i>0;i--) {
            boolean flag=true;
            for (int j = 0; j < i; j++) {
                if (array[j].compareTo(array[j+1])>0) {
                    Cards temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    flag=false;
                }
            }
            if(flag){
                break;
            }
        }
    }

测试代码:

    @Test
    public void testCards(){
        Cards[] array=new Cards[]{
                new Cards(1,2),
                new Cards(2,2),
                new Cards(3,2),
                new Cards(2,9),
                new Cards(1,7),
                new Cards(3,5),
                new Cards(4,3)
        };
        bubbleSort(array);
        for (Cards cards : array) {
            System.out.println(cards.toString());
        }
    }

打印结果:

Cards{pokerColors=1, cardPoints=2}
Cards{pokerColors=2, cardPoints=2}
Cards{pokerColors=3, cardPoints=2}
Cards{pokerColors=4, cardPoints=3}
Cards{pokerColors=3, cardPoints=5}
Cards{pokerColors=1, cardPoints=7}
Cards{pokerColors=2, cardPoints=9}

最后编辑于：2020.06.10 14:51:50