Java教程
HMJAVA数据结构与算法4【线性表】
本文主要是介绍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【线性表】的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
JavaMailSender是什么，怎么使用？-icode9专业技术文章分享11-15
-
JWT 用户校验学习：从入门到实践11-15
-
Nest学习：新手入门全面指南11-15
-
RestfulAPI学习：新手入门指南11-15
-
Server Component学习：入门教程与实践指南11-15
-
动态路由入门：新手必读指南11-15
-
JWT 用户校验入门：轻松掌握JWT认证基础11-15
-
Nest后端开发入门指南11-15
-
Nest后端开发入门教程11-15
-
RestfulAPI入门：新手快速上手指南11-15
-
Server Action入门：新手必读教程11-15
-
Server Component入门：新手必读教程11-15
-
抽离公共代码教程：简单易懂的入门指南11-15
-
动态路由教程：轻松入门与实战指南11-15
-
Restful API教程：入门与实践指南11-15
栏目导航
