数据结构与算法之顺序表
【摘要】 本篇文章带大家认识数据结构与算法基础，顺序表（动态），所谓的顺序表本质就是数组，它的特点是物理结构与逻辑结构都是连续的，最大的优点就是能够随机访问，最大的缺点是空间有限，就算扩容，也有可能存在大量的内存浪费。描述代码：Java。
🍓1.顺序表基本理论
🍇1.1线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
本篇文章介绍的是最简单的数据结构——顺序表。
🍇1.2顺序表
🍅1.2.1概念与特点
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储。
- 动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用.
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.
静态顺序表：
class StaticSeq {
public int Maxsize;
int[] elem = new int[Maxsize];//数据域
public int size;//有效元素个数
public StaticSeq(int capacity) {
this.Maxsize = capacity;//构造方法，用来确定静态顺序表的容量
}
}
动态顺序表：
class DynamicSeq {
public int[] elem;//数据域引用
public int size;//有效元素个数
}
本篇文章将介绍动态顺序表增删查改的实现，静态顺序表不多赘述！
🍅1.2.2顺序表实现接口
//初始化顺序表
public void initSeqList(){
}
// 打印顺序表
public void display() {
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
}
public boolean isFull() {
}
public boolean isEmpty() {
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
}
// 查找某个元素对应的位置
public int search(int toFind) {
}
//顺序插入元素
public void seqAdd(int value) {
}
// 获取 pos 位置的元素
public int getPos(int pos) {
}
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
}
// 获取顺序表长度
public int size() {
}
// 清空顺序表
public void clear() {
}
🍓2.动态顺序表实践
🍇2.1动态顺序表基本结构
class DynamicSeq {
public int[] elem;//数据域引用
public int size;//有效元素个数
}
🍇2.2初始化
顺序表的本质是数组，要使用顺序表必须有一段初始的空间，我初始化顺序表时，为顺序表开辟了10个数据空间。
//初始化顺序表
public void initSeqList(){
this.elem = new int[10];
}
每次使用新的顺序表还需要自己构造对象调用初始化方法，太麻烦了，我们让顺序表在执行构造方法阶段就完成顺序表的初始化。
public class SeqList {
public int[] elem;
public int size;
public SeqList() {
this.initSeqList();
}
}
🍇2.3顺序插入数据
在最后一个有效元素后插入一个数据，当然，在此之前需要判断顺序表有没有满，如果满了需要先扩容再插入。判断顺序表满没满很简单，就看他的有效元素个数是否与数组长度相等，如果相等就代表顺序表满了。
//判断顺序表是否满
public boolean isFull() {
return this.size == this.elem.length;
}
//顺序插入元素
public void seqAdd(int value) {
if (this.elem == null) {
this.initSeqList();
}
if (this.isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);//扩容
}
this.elem[this.size] = value;
this.size++;
}
🍇2.4指定位置插入数据
这个与顺序插入很相似，只不过多了一个条件：在指定位置插入，那怎么解决这个问题？你不能直接接访问这个位置然后修改这个位置元素的值，这是修改，不是插入。由于顺序表的“指针”是指向最后一个元素的后一个空间，所以我们需要先将指定位置的数据以及后面的数据先全部往后移动一个位置，然后再将指定位置的值改为目标数据。假设需要在顺序表下标为3的位置插入一个数字22。
// 在 pos 位置新增元素
public void add(int pos, int data) {
if (this.elem == null) {
this.initSeqList();
}
if (pos < 0 || pos > this.size) {
System.out.println("插入位置非法！");
return;
}
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
for (int i = size - 1; i >= pos; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.size++;
}
🍇2.5打印顺序表
遍历大法就能搞定！
// 打印顺序表
public void display() {
for (int i = 0; i < this.size; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
🍇2.6判断顺序表中是否包含某数据
遍历顺序表，找到就返回。
🍅2.6.1判定是否包含某个元素
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int j : this.elem) {
if (j == toFind) {
return true;
}
}
return false;//循环走完，表示没找到
}
🍅2.6.2查找某个元素对应的位置
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;//循环走完，表示没找到
}
🍇2.7指定位置的值
先判断位置是否合理，再直接访问返回。
🍅2.7.1获取指定位置元素
// 获取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= this.size) {
System.out.println("位置非法！");
return -1;
}
return this.elem[pos];
}
🍅2.7.2修改指定位置元素
// 给 pos 位置的元素修改为 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.size) {
System.out.println("修改位置非法！");
return;
}
this.elem[pos] = value;
}
🍇2.8删除第一次出现的指定数据
首先判断顺序表是否为空，为空直接返回。如果顺序表不为空再遍历找到元素并删除。
//删除第一次出现的关键字key
public void remove(int toRemove) {
if (isEmpty()) {
System.out.println("顺序表为空！");
return;
}
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toRemove) {
for (int j = i; j < this.size - 1; j++) {
this.elem[j] = this.elem[j+1];
}
this.size--;
return;
}
}
System.out.println("未找到！");
}
🍇2.9获取有效元素个数
访问size的值即可。
// 获取顺序表长度
public int size() {
return this.size;
}
🍇2.10删除整个顺序表
这个要注意一件事，如果顺序表的数据是引用类型的，需要先将所有元素的值全部置位null再将size置为0。当然，如果是基本数据，直接将size置为0即可。
// 清空顺序表
public void clear() {
this.size = 0;
}
🍓3.源代码
🍇3.1动态顺序表实现代码
import java.util.Arrays;
class StaticSeq {
public int Maxsize;
int[] elem = new int[Maxsize];//数据域
public int size;//有效元素个数
public StaticSeq(int capacity) {
this.Maxsize = capacity;//构造方法，用来确定静态顺序表的容量
}
}
class DynamicSeq {
public int[] elem;//数据域引用
public int size;//有效元素个数
}
public class SeqList {
public int[] elem;
public int size;
public SeqList() {
this.initSeqList();
}
//初始化顺序表
public void initSeqList(){
this.elem = new int[10];
}
// 打印顺序表
public void display() {
for (int i = 0; i < this.size; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if (this.elem == null) {
this.initSeqList();
}
if (pos < 0 || pos > this.size) {
System.out.println("插入位置非法！");
return;
}
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
for (int i = size - 1; i >= pos; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.size++;
}
public boolean isFull() {
return this.size == this.elem.length;
}
public boolean isEmpty() {
return this.size == 0;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int j : this.elem) {
if (j == toFind) {
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;
}
//顺序插入元素
public void seqAdd(int value) {
if (this.elem == null) {
this.initSeqList();
}
if (this.isFull()) {
this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
}
this.elem[this.size] = value;
this.size++;
}
// 获取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= this.size) {
System.out.println("位置非法！");
return -1;
}
return this.elem[pos];
}
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= this.size) {
System.out.println("修改位置非法！");
return;
}
this.elem[pos] = value;
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
if (isEmpty()) {
System.out.println("顺序表为空！");
return;
}
for (int i = 0; i < this.size; i++) {
if (this.elem[i] == toRemove) {
for (int j = i; j < this.size - 1; j++) {
this.elem[j] = this.elem[j+1];
}
this.size--;
return;
}
}
System.out.println("未找到！");
}
// 获取顺序表长度
public int size() {
return this.size;
}
// 清空顺序表
public void clear() {
this.size = 0;
}
}
🍇3.2测试专用代码
public class Test {
public static void main(String[] args) {
SeqList sl = new SeqList();
for (int i = 0; i < 12; i++) {
sl.seqAdd(i+1);
}
sl.display();
System.out.println("------------");
sl.add(2,99);
sl.add(13,99);
sl.add(0,99);
sl.display();
System.out.println("------------");
System.out.println(sl.contains(78));
System.out.println(sl.contains(2));
System.out.println("------------");
System.out.println(sl.search(78));
System.out.println(sl.search(5));
System.out.println("------------");
System.out.println(sl.getPos(98));
System.out.println(sl.getPos(5));
System.out.println("------------");
sl.setPos(45, 88);
sl.display();
sl.setPos(1, 88);
sl.display();
System.out.println("------------");
sl.remove(99);
sl.display();
sl.remove(99);
sl.display();
sl.remove(99);
sl.display();
sl.remove(122);
sl.display();
System.out.println("------------");
System.out.println(sl.size);
System.out.println("------------");
sl.clear();
sl.display();
}
}
🍇3.3项目文件
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）