插入算法思路
- 检查输入，如果插入位置不合理，抛出异常
- 检查数组，如果线性表的长度大于等于数组长度，则抛出异常或动态增加容量
- 遍历后移，从最后一个元素开始向前遍历到第i个位置，分别将他们都向后移动一个位置
- 插入数据，将要插入的数据填入i处
- 表长加1，插入了一个元素，一定要增加线性表的长度
/**
* 在线性表中的第location个位置插入新元素value
* @Param lineList 目标线性表
* @param location 目标位置
* @param value 插入的元素值
*/
public static void elementInsert(LineList lineList,int location,int value){
//检查线性表是否已满
if(lineList.length==LineList.MAXSIZE){
System.out.println("线性表已满");
return;
}
//检查插入数据的位置是否合法
if(location < 1 || location > lineList.length){
System.out.println("插入数据的位置不合法");
return;
}
//若插入的元素不在表尾部，先将元素后移一位
if(location < lineList.length){
for (int i = lineList.length-1; i >= location - 1; i --) {
lineList.date[i+1] = lineList.date[i];
}
}
//插入元素
lineList.date[location - 1] = value;
lineList.length++;
System.out.println("在线性表第"+location+"个位置成功插入"+value);
return;
}
删除算法的思路
-
检查输入，如果删除位置不合理，抛出异常
-
删除数据，取出删除的元素
-
遍历前移，从删除元素位置开始遍历到最后一个元素，分别将他们都向前移动一个位置
-
表长减1：删除了元素，不减表长会出错
/**
* 删除线性表第location个位置元素,并用value返回其值
* @param lineList 目标线性表
* @param location 要删除的位置
* @Return 删除的值
*/
public static int elementDelete(LineList lineList,int location){
int value = 0;
//检查输入是否合法
if (location < 1 || location > lineList.length){
System.out.println("想要删除数据的位置不合法");
return 0;
}
//删除数据
value = lineList.date[location-1];
lineList.date[location-1] = 0;
//删除的位置不是最后一位，将后后面的元素前移
if (location<lineList.length){
for (int i = location-1; i < lineList.length; i++) {
lineList.date[i] = lineList.date[i+1];
}
}
lineList.length--;
System.out.println("删除的数据为"+value);
return value;
}
C语言转换到java
- c语言中的结构体可以理解为类的定义
- 由于java中的对象为引用类型，所以可以用由类生成的对象作为参数，虽然存在差异，可以一定程度上来代替指针的效果。
LineList 类
public class LineList {
final static int MAXSIZE = 20;
int[] date;
int length;
LineList(){
date = new int[MAXSIZE];
length = 0;
}
}
注意：如果想初始化一个不为空的链表，采用下面这个方法是不可行的。
//此方法初始化会出现数组越界
// LineList(int[] data){
// this.date = new int[MAXSIZE];
// this.date = data; //在这里会重新将线性表存储位置，更新为新传入的数组，而不是初始化的数组，无法插入元素
// length = data.length;
// }
这是我一开始用来初始化一个非空线性表的初始化函数
//将会出现数组越界。此方法初始化会导致线性表的长度，为用来初始化的数组data的长度，导致无法插入数据
// public static LineList initList(int[] data){
// LineList lineList = new LineList(data);
// return lineList;
// }
这样写就相当于重新将线性表存到新给的数组中，而新给的数组是满的。例如：{1,2,3},再插入数据到线性表是数组溢出，会报错的。
初始化线性表方法
/**
* 初始化一个空的线性表
* @return lineList 返回一个空的线性表
*/
public static LineList initList(){
LineList lineList = new LineList();//创建一个空的线性表
return lineList;
}
/**
* 初始化一个不为空的线性表
* @param data 传入线性表的数据
* @return 返回一个不为空的线性表
*/
public static LineList initList(int[] data){
LineList lineList = new LineList();//创建一个空的线性表
for (int i = 0; i < data.length; i++) {//这样一个个赋值才不会让数组的存储位置发生改变
lineList.date[i] = data[i];
}
lineList.length = data.length;
return lineList;
}
打印线性表
/**
* 打印线性表
* @param linkList 输入要打印的线性表
*/
public static void printList(LineList linkList){
System.out.print("打印线性表:");
for(int i = 0;i < linkList.length;i++){
System.out.print(linkList.date[i]+" ");
}
System.out.println();
}
清空线性表
/**
* 清空线性表
* @param lineList 要清空的线性表
*/
public static void listClear(LineList lineList){
for (int i = 0; i < lineList.length; i++) {
lineList.date[i] = 0;
}
lineList.length = 0;
}
按位置查找元素
/**
* 将先线性表中的第location个位置的元素返回
* @param lineList 目标线性表线性表
* @param location 要获取的位置
* @return
*/
public static int getElement(LineList lineList, int location){
int value;
//检查要获取的元素是否存在
if(location > lineList.length){
System.out.println("线性表的第"+location+"个位置不存在");
return 0;
}else {
value = lineList.date[location-1];
System.out.println("线性表的第"+location+"个位置的元素为"+value);
return value;
}
}
按值查找元素
/**
* 在线性表中查询与给定值value相等的元素。
* 如果查询成功,返回该元素在表中的序号。
* 否则返回0，表示失败
* ===没有实现多个值相同的查询，这里只返回第一个匹配到的值==
* @param lineList
* @param value
* @return 返回元素的位置
*/
public static int elementLocate(LineList lineList,int value){
for (int i = 0; i < lineList.length; i++) {
if(value == lineList.date[i]){
return i+1;
}
}
return 0;
}
[复制链接]
发表于 2021-3-23 21:02
