HMJAVA数据结构与算法4【线性表】
2021/9/15 14:05:39
本文主要是介绍HMJAVA数据结构与算法4【线性表】，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1、顺序表
1.1 顺序表实现
package com.haifei.demo02linear;
import java.util.Iterator;
public class SequenceList <T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles = (T[])new Object[capacity];
this.N = 0;
}
//将线性表置空
public void clear(){
this.N = 0;
}
//判断当前线性表是否为空表
public boolean isEmpty(){
return N == 0;
}
//获取线性表长度
public int length(){
return N;
}
//获取线性表指定位置的元素
public T get(int i){
return eles[i];
}
//向线性表中追加元素t
public void insert(T t){
eles[N++] = t;
}
//在线性表索引i处插入元素t
public void insert(int i, T t){
//先把i索引处及其后面的元素依次向后移动一位
for (int index=N-1; index>i; index--){
eles[index] = eles[index-1];
}
//再将t元素添加到i索引处
eles[i] = t;
}
//删除线性表索引i处的元素，并返回该元素
public T remove(int i){
//记录索引i处的元素
T current = eles[i];
//索引i处后面的元素依次向前移动一位
for (int index=i; index<N-1; index++){
eles[index] = eles[index+1];
}
//元素个数-1
N--;
//返回已删除元素
return current;
}
//查照线性表中t元素第一次出现的位置
public int indexOf(T t){
for (int i=0; i<N; i++){
if (eles[i].equals(t)){
return i;
}
}
return -1; //线性表当前不存在t元素
}
}
View Code
package com.haifei.demo02linear.test;
import com.haifei.demo02linear.SequenceList;
public class Test01SequenceList {
public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(10);
//测试插入
sl.insert("姚明");
sl.insert("科比");
sl.insert("麦迪");
sl.insert(1,"詹姆斯");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为："+getResult); //詹姆斯
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是："+removeResult); //姚明
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length()); //0
}
}
View Code
1.2 顺序表遍历
package com.haifei.demo02linear;
import java.util.Iterator;
public class SequenceList <T> implements Iterable<T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles = (T[])new Object[capacity];
this.N = 0;
}
//将线性表置空
public void clear(){
this.N = 0;
}
//判断当前线性表是否为空表
public boolean isEmpty(){
return N == 0;
}
//获取线性表长度
public int length(){
return N;
}
//获取线性表指定位置的元素
public T get(int i){
return eles[i];
}
//向线性表中追加元素t
public void insert(T t){
eles[N++] = t;
}
//在线性表索引i处插入元素t
public void insert(int i, T t){
//先把i索引处及其后面的元素依次向后移动一位
for (int index=N; index>i; index--){
eles[index] = eles[index-1];
}
//再将t元素添加到i索引处
eles[i] = t;
//元素个数+1
N++;
}
//删除线性表索引i处的元素，并返回该元素
public T remove(int i){
//记录索引i处的元素
T current = eles[i];
//索引i处后面的元素依次向前移动一位
for (int index=i; index<N-1; index++){
eles[index] = eles[index+1];
}
//元素个数-1
N--;
//返回已删除元素
return current;
}
//查照线性表中t元素第一次出现的位置
public int indexOf(T t){
for (int i=0; i<N; i++){
if (eles[i].equals(t)){
return i;
}
}
return -1; //线性表当前不存在t元素
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
private class SIterator implements Iterator{//内部类
private int cusor;
public SIterator(){
this.cusor = 0;
}
@Override
public boolean hasNext() {
return cusor<N;
}
@Override
public Object next() {
return eles[cusor++];
}
}
}
View Code
package com.haifei.demo02linear.test;
import com.haifei.demo02linear.SequenceList;
public class Test01SequenceList {
public static void main(String[] args) {
//创建顺序表对象
SequenceList<String> sl = new SequenceList<>(10);
//测试插入
sl.insert("姚明");
sl.insert("科比");
sl.insert("麦迪");
sl.insert(1,"詹姆斯");
//测试遍历
for (String s : sl) {
System.out.println(s);
}
/*
姚明
詹姆斯
科比
麦迪
*/
System.out.println("========================");
//测试获取
String getResult = sl.get(1);
System.out.println("获取索引1处的结果为："+getResult); //詹姆斯
//测试删除
String removeResult = sl.remove(0);
System.out.println("删除的元素是："+removeResult); //姚明
//测试清空
sl.clear();
System.out.println("清空后的线性表中的元素个数为:"+sl.length()); //0
}
}
View Code
1.3 顺序表的容量可变
package com.haifei.demo02linear.test;
import com.haifei.demo02linear.SequenceList;
public class Test02SequenceList {
public static void main(String[] args) {
SequenceList<String> sl = new SequenceList<>(3);
sl.insert("张三");
sl.insert("李四");
sl.insert("王五");
// sl.insert("赵六"); //java.lang.ArrayIndexOutOfBoundsException: 3
}
}
View Code
package com.haifei.demo02linear;
import java.util.Iterator;
public class SequenceList <T> implements Iterable<T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles = (T[])new Object[capacity];
this.N = 0;
}
//将线性表置空
public void clear(){
this.N = 0;
}
//判断当前线性表是否为空表
public boolean isEmpty(){
return N == 0;
}
//获取线性表长度
public int length(){
return N;
}
//获取线性表指定位置的元素
public T get(int i){
return eles[i];
}
//向线性表中追加元素t
/*public void insert(T t){
eles[N++] = t;
}*/
public void insert(T t){
if (N == eles.length){ //扩容
resize(2 * eles.length);
}
eles[N++] = t;
}
//在线性表索引i处插入元素t
/*public void insert(int i, T t){
//先把i索引处及其后面的元素依次向后移动一位
for (int index=N-1; index>i; index--){
eles[index] = eles[index-1];
}
//再将t元素添加到i索引处
eles[i] = t;
}*/
/*public void insert(int i, T t){
//先把i索引处及其后面的元素依次向后移动一位
for (int index=N; index>i; index--){
eles[index] = eles[index-1];
}
//再将t元素添加到i索引处
eles[i] = t;
//元素个数+1
N++;
}*/
public void insert(int i, T t){
if (N == eles.length){ //扩容
resize(2 * eles.length);
}
//先把i索引处及其后面的元素依次向后移动一位
for (int index=N; index>i; index--){
eles[index] = eles[index-1];
}
//再将t元素添加到i索引处
eles[i] = t;
//元素个数+1
N++;
}
//删除线性表索引i处的元素，并返回该元素
/*public T remove(int i){
//记录索引i处的元素
T current = eles[i];
//索引i处后面的元素依次向前移动一位
for (int index=i; index<N-1; index++){
eles[index] = eles[index+1];
}
//元素个数-1
N--;
//返回已删除元素
return current;
}*/
public T remove(int i){
//记录索引i处的元素
T current = eles[i];
//索引i处后面的元素依次向前移动一位
for (int index=i; index<N-1; index++){
eles[index] = eles[index+1];
}
//元素个数-1
N--;
if (N < eles.length/4){ //缩容
resize(eles.length / 2);
}
//返回已删除元素
return current;
}
//查照线性表中t元素第一次出现的位置
public int indexOf(T t){
for (int i=0; i<N; i++){
if (eles[i].equals(t)){
return i;
}
}
return -1; //线性表当前不存在t元素
}
//根据参数newSize，重置eles的大小
public void resize(int newSize){
//定义一个临时数组，指向原数组
T[] temp=eles;
//创建新数组
eles=(T[])new Object[newSize];
//把原数组的数据拷贝到新数组
for(int i=0;i<N;i++){
eles[i]=temp[i];
}
}
@Override
public Iterator<T> iterator() {
return new SIterator();
}
private class SIterator implements Iterator{//内部类
private int cusor;
public SIterator(){
this.cusor = 0;
}
@Override
public boolean hasNext() {
return cusor<N;
}
@Override
public Object next() {
return eles[cusor++];
}
}
}
View Code
package com.haifei.demo02linear.test;
import com.haifei.demo02linear.SequenceList;
public class Test02SequenceList {
public static void main(String[] args) {
/*SequenceList<String> sl = new SequenceList<>(3);
sl.insert("张三");
sl.insert("李四");
sl.insert("王五");
// sl.insert("赵六"); //java.lang.ArrayIndexOutOfBoundsException: 3*/
//在SequenceList类中添加resize()以及对应插入删除配置后
SequenceList<String> sl = new SequenceList<>(3);
sl.insert("张三");
sl.insert("李四");
sl.insert("王五");
sl.insert("赵六"); //ok
}
}
View Code
1.4 顺序表的时间复杂度
1.5 Java中ArrayList实现
2、链表
2.1 单向链表
2.2 双向链表
2.3 链表的时间复杂度
2.4 链表翻转
2.5 快慢指针
2.6 循环链表
2.7 约瑟夫问题
3、栈
3.1 栈概述
3.2 栈实现
3.3 栈案例
4、队列
这篇关于HMJAVA数据结构与算法4【线性表】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES：转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发（ArkTS版）”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源，看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62（正式版本）去哪下载？
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀？
- 2024-05-09这种运行结果里的10.100000001，怎么能最快改成10.1？
