飞道的博客

【数据结构与算法Java实现】-线性表-顺序表

2020-05-16 13:29 308人阅读  评论(0)

线性表

基本运算

//    1. 初始化InitList（L）
//    2. 销毁线性表DestroyList（L）
//    3. 求线性表的长度GetLength（L）
//    4. 求线性表中第i个元素GetElem（L，i，e）
//    5. 按值查找Locate（L，x）
//    6. 插入元素InsElem（L，x，i）
//    7. 删除元素DelElem（L，i）
//    8. 输出元素值DispList（L）
  1. 初始化InitList（L）。其作用是建立一个空表L（即建立线性表的某种存储结果，但不含任何数据元素）。
  2. 销毁线性表DestroyList（L）。其作用是释放线性表L的内存空间。
  3. 求线性表的长度GetLength（L）。其作用是返回线性表L的长度。
  4. 求线性表中第i个元素GetElem（L，i，e）。其作用是返回线性表L的第i个数据元素。
  5. 按值查找Locate（L，x）。若L中存在一个或多个值与x相等的元素，则其作用是返回第一个值为x的元素的逻辑序号。
  6. 插入元素InsElem（L，x，i）。其作用是在线性表L的第i个位置上增加一个以x为值的新元素，使L由（a1，…，ai—1，ai，…，an）变为（a1，…，ai—1，x，ai，…，an）。其中，参数i的合法取值范围是1≤i≤n+1。
  7. 删除元素DelElem（L，i）。其作用是删除线性表L的第i个元素ai，使L由（a1，…，ai—1，ai，ai+1，…，an）变为（a1，…，ai—1，ai+1，…，an）。其中，参数i的合法取值范围是1≤i≤n。
  8. 输出元素值DispList（L）。其作用是按前后次序输出线性表L的所有元素值。

顺序表

基本操作

  1. 实现

    package datastructure;

import java.awt.image.AreaAveragingScaleFilter;
import java.util.Arrays;

public class List {
    private Object[] data;//数据
    private int length;//长度
    private int maxSize;//容量
    
    public Object getData(int i) {
        return data[i];
    }

    public int getLength() {
        return length;
    }

    public void add(Object x) {
        if (length + 2 > maxSize) {
            maxSize += 100;
            data = Arrays.copyOf(data, maxSize);
        }
        data[length] = x;
        length++;
    }

    //    1. 初始化InitList（L）
    public List() {
        this.maxSize = 100;
        data = new Object[maxSize];
        length = 0;
    }

    //    2. 销毁线性表DestroyList（L）
    public boolean DestroyList() {
        length = 0;
        data = new Object[maxSize];
        return true;
    }

    //    3. 求线性表的长度GetLength（L）
    public int GetLength() {
        return length;
    }

    //    4. 求线性表中第i个元素GetElem（L，i，e）
    public Object GetElem(int i) {
        if (i < 1 || i > length) {
            throw new RuntimeException("i值超出范围,i=" + i);
        } else {
            return data[i - 1];
        }
    }

    //    5. 按值查找Locate（L，x）
    public Object Locate(Object x) {
        int i = 0;
        while (i < length) {
            if (data[i] == x) {
                return i + 1;
            }
            i++;
        }
        throw new RuntimeException("表中无此值：" + x);
    }

    //    6. 插入元素InsElem（L，x，i）
    public void InsElem(Object x, int i) {
        if (1 > i || i > length + 1) {
            throw new RuntimeException("i值超出范围：i=" + i + "不能插入。i应在1到" + (length + 1) + "之间。");
        } else {
            if (length + 2 > maxSize) {
                maxSize += 100;
                data = Arrays.copyOf(data, maxSize);
            }
            for (int n = length; n >= i; n--) {
                data[n] = data[n - 1];
            }
            data[i - 1] = x;
            length++;
        }
    }

    //    7. 删除元素DelElem（L，i）
    public void DelElem(int i) {
        if (1 > i || i > length) {
            throw new RuntimeException("i值超出范围：i=" + i);
        } else {
            for (int n = i - 1; n < length; n++) {
                data[n] = data[n + 1];
            }
            length--;
            if (length < maxSize - 100 - 2) {
                maxSize -= 100;
                data = Arrays.copyOf(data, maxSize);
            }
        }
    }

    //    8. 输出元素值DispList（L）
    public void DispList() {
        System.out.printf("[");
        for (int i = 0; i < length; i++) {
            if (i != length - 1) {
                System.out.printf(data[i] + ",");
            } else {
                System.out.println(data[i] + "]");
            }
        }
    }
}

  2. 测试

    package datastructure;

public class ListTest {
    public static void main(String[] args) {
        int i;
        Object x;

        List list = new List();
        list.InsElem(1, 1);
        list.InsElem(3, 2);
        list.InsElem(1, 3);
        list.InsElem(5, 4);
        list.InsElem(4, 5);
        list.InsElem(2, 6);
        System.out.printf("线性表：");
        list.DispList();
        System.out.printf("长度：" + list.GetLength());

        i = 3;
        System.out.println("第" + i + "个元素：" + list.GetElem(i));
        x = 1;
        System.out.println("元素" + x + "是第" + list.Locate(x) + "个元素");
        i = 4;
        System.out.println("删除第" + i + "个元素");
        list.DelElem(i);
        System.out.printf("线性表：");
        list.DispList();

    }
}

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-c4cIgrQz-1589551464155)(C:\Users\ZhShy\AppData\Roaming\Typora\typora-user-images\image-20200515173407339.png)]

    // 整体创建
    public void CreatList(Object[] objects) {
        for (int i = 0; i < objects.length; i++) {
            data[i] = objects[i];
        }
        length = objects.length;
    }

算法

基于顺序表基本操作的算法设计

  1. 假设有一个顺序表L，其中元素为整数且所有元素值均不相同。设计一个算法将最大值元素与最小值元素交换。

    public void SwapMaxMin() {
    int maxIndex, minIndex;
    maxIndex = minIndex = 0;
    for (int i = 1; i < length; i++) {
        if ((int) data[i] > (int) data[maxIndex]) {
            maxIndex = i;
        }
        if ((int) data[i] < (int) data[minIndex]) {
            minIndex = i;
        }
    }
    Object t = data[maxIndex];
    data[maxIndex] = data[minIndex];
    data[minIndex] = t;

}

  2. 设计一个算法，从线性表中删除自第i个元素开始的k个元素，其中，线性表用顺序表L存储。

    public void Deletek(int i, int k) {
    if (i < 1 || i > length || i + k > length) {
        throw new RuntimeException("i或k超过范围，i=" + i + ",k=" + k + "无法操作." +
                "i应处于1~" + length + "范围，k应处于" + (length - i) + "~0范围.");
    } else {
        for (int n = i + k - 1; n <= length; n++) {
            data[n - k] = data[n];
        }
        length -= k;
    }
}

  3. 假设有一个顺序表L，其中元素为整数且所有元素值均不相同。设计一个尽可能高效的算法将所有奇数移到所有偶数的前面。

    public void Move() {
    int i, j;
    i = 0;
    j = length - 1;
    while (i < j) {
        while ((int) data[i] % 2 != 0) {
            i++;
        }
        while ((int) data[j] % 2 == 0) {
            j--;
        }
        if (i < j) {
            Object t = data[i];
            data[i] = data[j];
            data[j] = t;
        }
    }

基于整体建表的算法设计

  1. 已知一个整数线性表采用顺序表L存储。设计一个尽可能高效的算法删除其中所有值为x的元素（假设L中值为x的元素可能有多个）。

    public void Deletex(Object x) {
    int k = 0;
    for (int i = 0; i < length; i++) {
        if (!(data[i].equals(x))) {
            data[k] = data[i];
            k++;
        }
    }
    length = k;
}

  2. 已知一个整数线性表采用顺序表L存储。设计一个尽可能高效的算法删除其中所有值为负整数的元素（假设L中值为负整数的元素可能有多个）。

    public void Deleteminus() {
    int k = 0;
    for (int i = 0; i < length; i++) {
        if ((int) data[i] >= 0) {
            data[k] = data[i];
            k++;
        }
    }
    length = k;
}

有序顺序表的二路归并算法

  1. 有两个按元素值递增有序的顺序表A和B，设计一个算法将顺序表A和B的全部元素归并到一个按元素递增有序的顺序表C中。并分析算法的空间复杂度和时间复杂度。

    public static List Merge(List A, List B) {
    List C = new List();
    int la = A.getLength();
    int lb = B.getLength();
    int i, j, k;
    i = j = k = 0;
    while (i < la && j < lb) {
        int a = (int) A.getData(i);
        int b = (int) B.getData(j);
        if (a < b) {
            C.add(a);
            i++;
        } else {
            C.add(b);
            j++;
        }
    }
    while (i < la) {
        C.add(A.getData(i));
        i++;
    }
    while (j < lb) {
        C.add(B.getData(j));
        j++;
    }
    return C;
}

    空间复杂度：O（1）
    时间复杂度：O（n）

  2. 有两个递增有序顺序表A和B，设计一个算法由顺序表A和B的所有公共元素产生一个顺序表C。并分析该算法的空间复杂度和时间复杂度。

    public static List Commelem(List A, List B) {
    List C = new List();
    int i, j;
    i = j = 0;
    while (i < A.getLength() && j < B.getLength()) {
        int a = (int) A.getData(i);
        int b = (int) B.getData(j);
        if (a < b) {
            i++;
        } else if (a > b) {
            j++;
        } else {
            C.add(a);
            i++;
            j++;
        }
    }
    return C;
}

    空间复杂度：O（1）
    时间复杂度：O（n）

  3. 有两个递增有序顺序表A和B，分别含有n和m个整数元素（最大的元素不超过32 767），假设这n+m个元素均不相同。设计一个尽可能高效的算法求这n+m个元素中第k小的元素。如果参数k错误，算法返回0；否则算法返回1，并且用参数e表示求出的第k小的元素。

    public static int Topkl(List A, List B, int k) {
    int e = 0;
    int i, j;
    i = j = 0;
    while (i < A.getLength() && j < B.getLength()) {
        k--;
        int a = (int) A.getData(i);
        int b = (int) B.getData(j);
        if (a < b) {
            if (k == 0) {
                e = a;
                return e;
            }
            i++;
        } else {
            if (k == 0) {
                e = b;
                return e;
            }
            j++;
        }

    }
    if (i < A.getLength()) {
        e = (int) A.getData(i + k - 1);
    } else if (j < B.getLength()) {
        e = (int) B.getData(j + k - 1);
    }
    return e;
}

转载：https://blog.csdn.net/weixin_43651049/article/details/106150524
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场