Sequential And Linked Lists - 顺序表 和 链表 - 顺序表部分 - java

x33g5p2x  于2021-11-22 转载在 Java  
字(1.9k)|赞(0)|评价(0)|浏览(306)

前言

1. 顺序表和链表,都属于数据结构的一部分。
2. 数据结构:C的数据结构 和 JAVA 的数据结构,有什么不一样?
     数据结构 只是一个单独的学科。和语言没有关系。
     语言的不同,只是决定了实现同一种逻辑的方法不同而已。
3. 数据结构:逻辑非常严谨的一门学科,要向学号数据结构
     必须做到两点 :1.多画图 , 2.多写代码  (别抄)

顺序表和链表 是 数组 与 类和对象 的一种整合。顺序表和链表 是 数据结构的基础。非常重要。

线性表

线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,
 常见的线性表:顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储

顺序表(一个面向对象的数组)

概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
可以这么去理解 顺序表 是一个面向对象的数组。但是一个数组是不能自己面向对象,我们需要提供一些方法,来对数组进行增删查改。
那么把数组这些方法(只用写一次) 和 数组 作为属性 放到一个类里面,将来我用这个类去new对象的时候,
通过这个对象我们可以去调用这些方法,去操作数组,这不就是面向对象嘛。

 简单来说 顺序表 就是 对一个数组进行增删查改。
 一个普通数组,我们也可以创建一些方法区操作它,但它始终面向不了对象。而且我们每次都需要为数组写操作方法。

顺序表一般可以分为:

静态顺序表:使用定长数组存储。
    动态顺序表:使用动态开辟的数组存储       
  
    静态顺序表适用于确定知道需要存多少数据的场景.
    静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用  
 相比之下动态顺序表更灵活, 根据需要分配动态的空间大小

 

顺序表讲解图

1(准备工作)

2(new对象)

3(顺序要实现的功能)

4(打印顺序表)

5 (获取顺序表的有效长度)

6(在pos位置增添元素)

代码实现(在pos位置增添元素)
public void add(int pos, int data) {
      // 1.
      if(pos<0||pos>this.usedSize){
          System.out.println("pos的位置不合法!");
          return;
      }
      // 2.
      dilatation();
      // 3.
      for (int i = this.usedSize-1; i >= pos; i--) {
          this.array[i+1]=this.array[i];
      }
      // 4.
      this.array[pos] = data;
      this.usedSize++;
  }
  // 扩容
  public void dilatation(){
     if(this.array.length == this.usedSize){
        this.array = Arrays.copyOf(this.array,this.array.length*2);
     }
  }
此时我们已经写好了 打印顺序表、获取顺序表的有效长度、在 pos 位置新增元素 的顺序表功能,我们来测试一下。
public class SequentialAndLinkedLists {
    public static void main(String[] args) {

        MySequentialList mySequentialList = new MySequentialList();
       // 通过 在 pos 位置新增元素 的功能 来给 数组赋值
        mySequentialList.add(0,1);
        mySequentialList.add(1,2);
        mySequentialList.add(2,3);
        mySequentialList.add(3,4);
        mySequentialList.add(4,5);
        mySequentialList.display();// 打印显示
        System.out.println(mySequentialList.size());// 打印有效元素个数

    }
}
效果附图

7 ( 判断是否包含某个元素 )

8 (查找某个元素对应的位置)

7 和 8 效果图

9(获取下标为pos的元素)

9 附图

10(给 pos 位置的元素设为 value)

10 附图

11 (删除第一次出现的关键字key)

至于为什么是 usedSize-1,是为了防止越界。(如果顺序表示满的情况,当 你循环走到 最后一个元素时,此时的 array[i+1],会访问不属于顺序表的空间,从而导致越界访问)

11 附图

11 效果图

11.2(特殊情况)

12 清空顺序表

附图

附上程序总图

调用方

实现者(顺序表)

本文结束

相关文章