摘要:前面的话本篇文章带大家认识数据结构与算法基础,顺序表动态,所谓的顺序表本质就是数组,它的特点是物理结构与逻辑结构都是连续的,最大的优点就是能够随机访问,最大的缺点是空间有限,就算扩容,也有可能存在大量的内存浪费。
⭐️前面的话⭐️
本篇文章带大家认识数据结构与算法基础,顺序表(动态),所谓的顺序表本质就是数组,它的特点是物理结构与逻辑结构都是连续的,最大的优点就是能够随机访问,最大的缺点是空间有限,就算扩容,也有可能存在大量的内存浪费。描述代码:Java。
?博客主页:未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创,CSDN首发!
?首发时间:?2021年11月10日?
✉️坚持和努力一定能换来诗与远方!
?参考书籍:?《趣学数据结构》,?《数据结构(C语言版)》,?《趣学算法》
?参考在线编程网站:?牛客网?力扣
博主的码云gitee,平常博主写的程序代码都在里面。
博主的github,平常博主写的程序代码都在里面。
?作者水平很有限,如果发现错误,一定要及时告知作者哦!感谢感谢!
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
本篇文章介绍的是最简单的数据结构——顺序表。
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为:
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致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;//有效元素个数}
本篇文章将介绍动态顺序表增删查改的实现,静态顺序表不多赘述!
//初始化顺序表 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() { }
class DynamicSeq { public int[] elem;//数据域引用 public int size;//有效元素个数}
顺序表的本质是数组,要使用顺序表必须有一段初始的空间,我初始化顺序表时,为顺序表开辟了10个数据空间。
//初始化顺序表 public void initSeqList(){ this.elem = new int[10]; }
每次使用新的顺序表还需要自己构造对象调用初始化方法,太麻烦了,我们让顺序表在执行构造方法阶段就完成顺序表的初始化。
public class SeqList { public int[] elem; public int size; public SeqList() { this.initSeqList(); }}
在最后一个有效元素后插入一个数据,当然,在此之前需要判断顺序表有没有满,如果满了需要先扩容再插入。判断顺序表满没满很简单,就看他的有效元素个数是否与数组长度相等,如果相等就代表顺序表满了。
//判断顺序表是否满 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++; }
这个与顺序插入很相似,只不过多了一个条件:在指定位置插入,那怎么解决这个问题?你不能直接接访问这个位置然后修改这个位置元素的值,这是修改,不是插入。由于顺序表的“指针”是指向最后一个元素的后一个空间,所以我们需要先将指定位置的数据以及后面的数据先全部往后移动一个位置,然后再将指定位置的值改为目标数据。假设需要在顺序表下标为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++; }
遍历大法就能搞定!
// 打印顺序表 public void display() { for (int i = 0; i < this.size; i++) { System.out.print(this.elem[i] + " "); } System.out.println(); }
遍历顺序表,找到就返回。
// 判定是否包含某个元素 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;//循环走完,表示没找到 }
先判断位置是否合理,再直接访问返回。
// 获取 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("未找到!"); }
访问size
的值即可。
// 获取顺序表长度 public int size() { return this.size; }
这个要注意一件事,如果顺序表的数据是引用类型的,需要先将所有元素的值全部置位null
再将size
置为0
。当然,如果是基本数据,直接将size
置为0
即可。
// 清空顺序表 public void clear() { this.size = 0; }
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++)<
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123037.html
面试旧敌之红黑树(直白介绍深入理解) - Android - 掘金 读完本文你将了解到: 什么是红黑树 黑色高度 红黑树的 5 个特性 红黑树的左旋右旋 指定节点 x 的左旋 右图转成左图 指定节点 y 的右旋左图转成右图 红黑树的平衡插入 二叉查找树的插入 插入后调整红黑树结构 调整思想 插入染红后... java 多线程同步以及线程间通信详解 & 消费者生产者模式 & 死锁 & Thread...
摘要:文章首发于公众号一件风衣在编程中,我们常使用一组有顺序的数据来表示某个有意义的数据,这种一组元素的序列的抽象,就是线性表,简称表,是很多复杂数据结构的实现基础,在中,和就可以看作是线性表的实现。 文章首发于公众号一件风衣(ID:yijianfengyi) 在编程中,我们常使用一组有顺序的数据来表示某个有意义的数据,这种一组元素的序列的抽象,就是线性表,简称表,是很多复杂数据结构的实现基...
摘要:前言这三个数据结构,相对于之前的来说比较常见,几乎都与线性表有关,很类似。销毁串,若串存在则将销毁掉。串的逻辑结构和线性表极为相似,区别仅在于串的数据对象限定为字符集。在基本操作上串和线性表有很大差别。 ...
摘要:不同链表是链式的存储结构数组是顺序的存储结构。从列表中,移除并返回特定位置的一项。返回列表中元素个数,与数组的属性类似。提示端优先使用以上的语法实现。不要忘记在最后返回新的头引用复杂度分析时间复杂度。假设是列表的长度,时间复杂度是。 这是第三周的练习题,原本应该先发第二周的,因为周末的时候,我的母亲大人来看望她的宝贝儿子,哈哈,我得带她看看厦门这座美丽的城市呀。 这两天我抓紧整...
摘要:文章目录前言堆的结构化定义堆堆的各种操作方法堆操作之初始化堆操作之销毁空间堆操作之入堆堆操作之出堆堆操作之判空堆操作之获取堆顶堆操作之获取大小堆结构练习获取前个最小或最大元素前言博主上一小节动图演示堆讲到了通过堆的特性 ...
阅读 2523·2021-11-16 11:45
阅读 2316·2021-11-11 16:54
阅读 2696·2021-10-08 10:05
阅读 1432·2021-09-26 10:19
阅读 1864·2021-09-13 10:28
阅读 2616·2021-09-08 10:46
阅读 1044·2021-09-08 09:36
阅读 1301·2021-09-07 10:13