JAVA顺序结构,数据结构顺序表的实现
00-1010 1.什么是线性表2。序列表3。手撕序列表的属性定义和构造方法。接口实现保证了序列表的空间增加。打印顺序表。确定序列表中是否有元素。在pos位置找到元素。将pos位置的元素值设置为value。删除第一个关键字。获取序列表的长度。清空序列表。删除所有密钥。
00-1010线性表是最基本、最简单、最常用的数据结构。线性表*(线性表)*是一种数据结构。线性表是具有相同特征的N个数据元素的有限序列。常见的线性表有序列表、链表、栈、队列、字符串等。
注：这里所说的线性表都是指逻辑结构，即其逻辑结构是线性的，但其物理结构不一定是线性的。
在数据结构的逻辑层面上，线性表可以分为一般线性表和受限线性表。一般线性表也称“线性表”，可以自由删除或添加节点。线性表主要包括栈和队列。受限意味着节点的操作受到限制。
00-1010顺序表是以数组形式存储在计算机内存中的线性表。线性表的顺序存储是指通过一组具有连续地址的存储单元对线性表中的每个元素进行顺序存储，使线性表中逻辑相邻的数据元素存储在相邻的物理存储单元中。
表格可以分为以下两类：
静态序列表：动态序列表由定长数组实现：数组长度可以动态增加。静态序列表是相当严格的。数组长度太小就担心后面的数据存储不了，太大就有空间浪费。
所以我们一般用动态增长的顺序表，按需取用。
00-1010在学习数据结构的过程中，我们不仅要学习如何使用数据结构，了解其理论部分，还要自己去实践，重新认识数据结构，这样我们的理解会更深入。
如果我们简单的在序列表中使用一个数组，会出现一些问题：序列表中有多少有效数据，是否满了等等。所以我们在实现序列表的时候，会增加另一个size属性(序列表的容量可以通过data.length获得)。
目录
公共类MyArrayList { public int[]data；//存储数据public int size//有效数据的数量}
一、什么是线性表
public MyArrayList(){ this . data=new int[10]；//后面容量不够。this . size=0；//初始没有有效数据，大小为0
00-1010对于序列表，我们通常有以下接口来实现：
//打印订单表public void display()；//在pos位置添加元素public void add(int pos，int num)；//确定顺序表是否包含元素public boolean contains(int num)；//查找一个元素的位置public int search(int key)；//获取Pos位置的元素public int Get pos(int pos)；//将pos位置的元素值设置为value public void setpos (intpos，int value)；//删除第一次出现的关键字key public void remove(int key)；//获取序列表长度public int size()；//清空订单表public void clear()；在实现这些接口的过程中，只要涉及到数组下标，就要检查下标的合法性，注意是使用size还是data.length
00-1010在给序列表添加元素时，一定要保证序列表有足够的空间来添加元素，否则会导致数组下标越界的发生。
私保容量(){ if(this . size==this . data . length){//描述已满，该展开this . data=arrays . copy of(this . data，2 * this . data . length)；}}
00-1010在向序列表中添加元素时，注意在大小位置添加元素(相当于尾部插入)。同时，确保序列表中有足够的空间用于插入，并注意移动元素(下标越界)时的边界条件
，移动元素过多等），也别忘了size++
public void add(int pos, int num) { if (pos < 0 pos > this.size) { // 检验下表合法性 throw new RuntimeException("ArrayIndexOutOfBoundsException : " + pos); } ensureCapacity(); for (int i = this.size; i > pos; i--) { this.data[i] = this.data[i - 1]; } this.data[pos] = num; this.size++;}
打印顺序表
注意这里只打印有效数据
public String printMyArrayList() { String str = "["; for (int i = 0; i < this.size - 1; i++) { // for循环中的右边界应该用size而不用data.length str += this.data[i] + ", "; } str += this.data[this.size - 1]; str += "]"; return str;}测试
对前面写的三个接口做测试
public class UseArrayList { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0, 0); myArrayList.add(1, 1); myArrayList.add(2, 2); myArrayList.add(3, 3); myArrayList.add(4, 2); myArrayList.add(0, 100); // 头插 myArrayList.add(2, 666); // 中间插 System.out.println(myArrayList.printMyArrayList()); }}运行结果：
判断顺序表中是否包含某个元素
public boolean contains(int num) { for (int i = 0; i < this.size; i++) { if (this.data[i] == num) { return true; } } return false;}测试：
public class UseArrayList { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0, 0); myArrayList.add(1, 1); myArrayList.add(2, 2); myArrayList.add(3, 3); System.out.println(myArrayList.contains(3)); System.out.println(myArrayList.contains(2)); System.out.println(myArrayList.contains(0)); System.out.println(myArrayList.contains(666)); }}运行结果：
查找元素
查找顺序表中某个元素的位置（返回下标）
public int search(int key) { for (int i = 0; i < this.size; i++) { if (this.data[i] == key) { return i; } } return -1; // 不存在这个元素，返回-1}测试：
public class UseArrayList { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0, 0); myArrayList.add(1, 1); myArrayList.add(2, 2); myArrayList.add(3, 3); System.out.println(myArrayList.search(0)); System.out.println(myArrayList.search(3)); System.out.println(myArrayList.search(666)); }}
获取 pos 位置的元素
注意：size位置为无效元素
public int getPos(int pos) { if (pos < 0 pos >= this.size) { throw new RuntimeException("ArrayIndexOfBoundsException : " + pos); } return this.data[pos];}测试：
public class UseArrayList { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0, 0); myArrayList.add(1, 1); myArrayList.add(2, 2); myArrayList.add(3, 3); System.out.println(myArrayList.getPos(0)); System.out.println(myArrayList.getPos(3)); System.out.println(myArrayList.getPos(1)); System.out.println(myArrayList.getPos(6)); }}
将 pos 位置的元素值设为 value
这里不涉及元素的移动
public void setPos(int pos, int value) { if (pos < 0 pos >= this.size) { // size位置为无效元素 throw new RuntimeException("ArrayIndexOfBoundsException : " + pos); } this.data[pos] = value;}测试：
public class UseArrayList { public static void main(String[] args) { MyArrayList myArrayList = new MyArrayList(); myArrayList.add(0, 0); myArrayList.add(1, 1); myArrayList.add(2, 2); myArrayList.add(3, 3); myArrayList.setPos(0, 666); myArrayList.setPos(3, 777); System.out.println(myArrayList.printMyArrayList()); }}
删除第一次出现的关键字key
注意在删除的时候的数组边界以及改变size
public void remove(int key) { int pos = search(key); if (pos == -1) { return; // 若是这个数字不存在，则返回 } for (int i = pos; i < this.size - 1; i++) { this.data[i] = this.data[i + 1]; // 从后往前挪，直接将要删除的数字覆盖掉 } this.size--;}
获取顺序表长度
public int size() { return this.size;}
清空顺序表
public void clear() { this.size = 0;}
删除所有的key
如果我们想要删除顺序表中所有的key，如何做？
法一：我们可以将第一次出现的key删除完之后再继续搜索若有，则删除，没有则删除完毕
public void removeAll(int key) { for (int i = 0; i < this.size; i++) { if (this.search(key) != -1) { remove(key); } else { return; } }}法二：我们可以转变以下思路，不直接删除key，而是重新创建一个数组，将源数组中不是key的值复制到新数组，再让原数组的引用指向新数组，间接完成删除操作
public void removeAllPlus(int key) { int[] newData = new int[this.data.length]; // 新数组长度应该和源数组长度相同 int j = 0; for (int i = 0; i < this.size; i++) { if (this.data[i] != key) { newData[j] = this.data[i]; j++; } } this.data = newData; this.size = j;}注意：在元素复制完之后要改变源数组的引用，并改变顺序表的size
法三：我们既然可以通过复制的方式实现间接删除操作，那么我们可以想着将原数组就当成目标数组，即两个指针，一个数组
public void removeAllPlusPlus(int key) { int dest = 0; for (int src = 0; src < this.size; src++) { if (this.data[src] != key) { this.data[dest] = this.data[src]; dest++; } } this.size = dest;}到此这篇关于Java数据结构顺序表从零基础到精通进阶的文章就介绍到这了,更多相关Java 顺序表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。