Java数据结构与基本算法之线性表
文章目录
1 数组
1.1 基本类型数组
例如:向一维数组做,插入,更新,替换,删除操作时:
// 声明一个数组
int[] scores = {1, 2, 3, 4, 5, 6};
// 1. 在数据尾部位置插入一个数字
scores = add(scores, 7);
public static int[] add(int[] array, int score) {
int[] tempArray = new int[array.length + 1];
for (int i = 0; i < array.length; i++) {
tempArray[i] = array[i];
}
tempArray[array.length] = score;
return tempArray;
}
// 2. 向一维数组任意位置(指定位置)修改一个数据,真实位置=要求位置-1
scores = update(scores, 7, 2);
public static int[] update(int[] arrary, int score, int index) {
arrary[index] = score;
return arrary;
}
// 3. 替换一个数字到指定位置
scores = insert(scores, 7, 2);//将75插入到索引为2的位置
public static int[] insert(int[] array, int score, int index) {
int[] tempArray = new int[array.length + 1];
for (int i = 0; i < array.length; i++) {
if (i < index) {
tempArray[i] = array[i];
} else {
tempArray[i + 1] = array[i];
}
}
tempArray[index] = score;
return tempArray;
}
// 4. 删除指定位置的数字
scores = delete(scores, 3);
public static int[] delete(int[] array, int index) {
int[] tempArray = new int[array.length - 1];
for (int i = 0; i < array.length; i++) {
if (i <= index) {
tempArray[i] = array[i];
} else {
tempArray[i - 1] = array[i];
}
}
return tempArray;
}
1.2 封装类型ArrayList数组
//声明初始接口方法
public interface List {
public void add(Object element);//添加元素
public Object get(int index);//获得元素
public Object set(int index,Object element);//修改元素
public Object remove(int index);//删除元素
public int size();//集合大小
}
//实现声明接口的数组
public class ArrayList implements List {
private int initCapacit = 20;//初始数组大小
private int size;//元素个数
private Object[] elementData;//数据数组对象
public ArrayList() {
elementData = new Object[initCapacit];
}
public ArrayList(int initCapacit) {
elementData = new Object[initCapacit];
this.initCapacit = initCapacit;
}
//添加元素
@Override
public void add(Object element) {
if (size < initCapacit) {
elementData[size] = element;
size++;
} else {
elementData = expandArray(elementData);
elementData[size] = element;
size++;
}
}
//扩充List对象数组大小
public Object[] expandArray(Object[] elementData) {
Object[] tempArray = new Object[elementData.length * 2];//每次扩充为原来的2倍大小
for (int i = 0; i < elementData.length; i++) {
tempArray[i] = elementData[i];
}
return tempArray;
}
//获得元素
@Override
public Object get(int index) {
return elementData[index];
}
//集合大小
@Override
public int size() {
return size;
}
//删除元素
@Override
public Object remove(int index) {
Object removeObj = elementData[index];
//删除元素后面的元素前移
for (int i = index; i < size; i++) {
elementData[i] = elementData[i + 1];
}
size--;
return removeObj;
}
//修改元素
@Override
public Object set(int index, Object element) {
elementData[index] = element;
return element;
}
Node p=head;
int i=0;
while (p.getNext()!=null && i<index){
p=p.getNext();
i++;
}
p.setData(element);
return element;
}
@Override
public Object remove(int index) {
Node p=head;
int i=0;
while (p.getNext()!=null && i<index){
p=p.getNext();
i++;
}
Node temp=p;//保存要删除的节点
p.getPrev().setNext(p.getNext());
p.getNext().setPrev(p.getPrev());
temp.setNext(null);
temp.setPrev(null);
size--;
return temp.getData();
}
}
2 链表
2.1 单链表
//单链表的结构,Node的自引用,next代表指针变量指向下一个节点
public class Node {
private String data;//节点数据
private Node next;//下一个节点
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
2.2 单循环链表
// 核心在于打印两次,头开始到尾,再从尾到头循环打印
public static void print(Node node) {
Node p = node;
Node startNode = node;
int circleCount = 0;//循环打印次数
while (circleCount < 2) {
//从头开始到尾,再从尾到头循环打印
String data = p.getData();
System.out.print(data + "→");
p = p.getNext();
if (p.getNext() == startNode) {
circleCount++;
}
}
String data = p.getData();
System.out.print(data + "\n\n");
}
2.3 双链表
// 双链表,prev和next两个指针变量 prev-data-next
class Node {
private String data;//结点数据
private Node prev;//上一个结点
private Node next;//下一个结点
public Node(String data, Node prev, Node next) {
this.data = data;
this.prev = prev;
this.next = next;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public Node getPrev() {
return prev;
}
public void setPrev(Node prev) {
this.prev = prev;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
2.4 双向循环链表
nt circleCount = 0;//循环打印次数
while (circleCount < 2) {
//从头开始直到尾结束,再从尾到头循环打印
String data = p.getData();
System.out.print(data + "->");
p = p.getNext();
if (p.getNext()==startNode){
circleCount++;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论