线性表是什么？
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表的基本操作
1）MakeEmpty(L) 这是一个将L变为空表的方法
2）Length（L） 返回表L的长度，即表中元素个数
3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）
4）Prior（L，i） 取i的前驱元素
5）Next（L，i） 取i的后继元素
6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置
7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置
8）Delete（L，p） 从表L中删除位置p处的元素
9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false
10）Clear（L）清除所有元素
11）Init（L）同第一个，初始化线性表为空
12）Traverse（L）遍历输出所有元素
13）Find（L，x）查找并返回元素
14）Update（L，x）修改元素
15）Sort（L）对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址
这里只实现上述的核心部分功能
线性表基本操作的实现
首先，在java中秉持着面向对象的原则，定义初始的成员变量
public class MyLinearList{
// 用数组来实现线性表
// 定义成员变量
private Object[] elementList;
private int size=0;//线性表初始长度为0
private int capacity=10;//默认线性表容量为10
//定义构造方法，初始化线性表容量
//根据用户指定容量来生成指定长度的线性表
public MyLinearList(int capacity) {
this.capacity = capacity;
elementList =new Object[capacity];
}
//默认的线性表长度为10
public MyLinearList() {
elementList = new Object[capacity];
}
}
然后在接口中定义我们对线性表的基本操作
package day01线性表;
public interface MyList {
/**
* 添加元素
* @param element
*/
void add(Object element);
/**
* 在指定位置插入元素
* @param target
* @param element
*/
void add(int target,Object element);
/**
* 根据元素的值来删除
* @param element
*/
void delete(Object element);
/**
* 根据索引来删除元素
* @param index
*/
void delete(int index);
/**
* 根据指定的target索引位置来更新元素
* @param traget
* @param element
*/
void update(int traget,Object element);
/**
* 返回某一元素第一次在线性表中出现的位置
* @param element
* @return
*/
int indexOf(Object element);
/**
* 返回在指定target位置的元素
* @param target
* @return
*/
Object elementAt(int target);
/**
* 取指定索引位置元素的前驱元素
* @param index
* @return
*/
Object elementPrior(int index);
/**
* 取指定索引位置元素的后继元素
* @param index
* @return
*/
Object elementNext(int index);
}
接着用类去实现这一接口，重写其中的全部方法，因为有一些操作，使用静态方法更便捷，所以接口中只是部分的基础操作，线性表的增删改查。
线性表的增加元素–实现代码
@Override
public void add(Object element) {
//如果当前元素长度大于线性表的容量则选择扩容
if(size>=capacity){
capacity+=1;
Object[] newArr = new Object[capacity];
//将之前的元素复制到新的线性表newArr中
for (int i = 0; i < size; i++) {
newArr[i] = elementList[i];
}
//用新的扩容以后的newArr来当作新的线性表的地址
elementList = newArr;
}
elementList[size++] = element;
}
@Override
public void add(int target, Object element) {
//指定位置插入元素，则需要考虑右移元素
if(size>=capacity){
capacity+=1;
Object[] newArr = new Object[capacity];
//将之前的元素复制到新的线性表newArr中
for (int i = 0; i < size; i++) {
newArr[i] = elementList[i];
}
//用新的扩容以后的newArr来当作新的线性表的地址
elementList = newArr;
//将元素右移
for (int i = capacity-1; i >target; i--) {
elementList[i] = elementList[i-1];
}
elementList[target] = element;
size+=1;
}else{
for (int i = capacity-1; i >target; i--) {
elementList[i] = elementList[i-1];
}
elementList[target] = element;
size+=1;
}
}
线性表的查找元素–实现代码
@Override
public int indexOf(Object element) {
//如果可以在线性表中找到对应的元素的值，则返回索引，否则返回-1表示要找的元素不存在
for (int i = 0; i < size; i++) {
if(elementList[i].equals(element)){
return i;
}
}
return -1;
}
@Override
public Object elementAt(int target) {
if (target>capacity-1){
System.out.println("访问的索引已经越界!");
return null;
}
return elementList[target];
}
@Override
public Object elementPrior(int index) {
if(index>size-1||index-1<0){
return -1;
}
return elementList[index-1];
}
@Override
public Object elementNext(int index) {
if(index+1>size-1){
return -1;
}
return elementList[index+1];
}
线性表的删除元素–实现代码
@Override
public void delete(Object element) {
int index = indexOf(element);
if(index>=0){
delete(index);
}
}
@Override
public void delete(int index) {
//线性表删除涉及到删除某一元素，需要将其后面的元素进行左移操作
elementList[index]=null;
for (int i = index; i <= size-index; i++) {
elementList[i] = elementList[i+1];
}
size-=1;
}
线性表的修改元素–实现代码
@Override
public void update(int traget, Object element) {
elementList[traget] =element;
}
线性表的其他操作-遍历清空，求线性表长度-实现代码
//清空线性表内容
public static void clearList(MyLinearList myLinearList) {
myLinearList.size =0;
}
//线性表是否为空
public static boolean isEmpty(MyLinearList myLinearList) {
if(myLinearList.size==0){
return true;
}
return false;
}
//输出当前线性表容量
public static void listLength(MyLinearList myLinearList) {
System.out.println("当前线性表容量为:"+ myLinearList.capacity);
}
//输出当前线性表长度
public static void listSize(MyLinearList myLinearList) {
System.out.println("当前线性表中不为空的元素个数为:"+ myLinearList.size);
}
//重写toString方法
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elementList[i]+(i==size-1?"":","));
}
stringBuilder.append("]");
return stringBuilder.toString();
}
//线性表遍历输出
public static void listPrint(MyLinearList myLinearList){
System.out.println(myLinearList.toString());
}
main函数测试代码
public static void main(String[] args) {
//测试，首先生成一个长度为10 的线性表,并且使用add方法顺序插入10个元素
MyLinearList list = new MyLinearList();
list.add("one");
list.add("two");
list.add("three");
list.add(".");
list.add("A");
list.add("B");
list.add("D");
list.add("E");
list.add("F");
list.add("G");
listPrint(list);
//现在继续增加一个元素到list，看是否会扩容
list.add(11);
listPrint(list);
listLength(list);//长度扩容为20
System.out.println(list.indexOf("three"));
list.delete("three");
listPrint(list);
list.add("ok");
listPrint(list);
list.update(2,"!");
listPrint(list);
list.add(2,"?");
listPrint(list);
listSize(list);
System.out.println("index为2的前驱元素为:"+list.elementPrior(2));
System.out.println("index为5的后继元素为:"+list.elementNext(5));
clearList(list);
listPrint(list);
System.out.println(list.isEmpty(list));
}
完整代码
创建一个包，然后包里面分别创建接口和实现类，
MyList接口的全部代码
package day01线性表;
public interface MyList {
/**
* 添加元素
* @param element
*/
void add(Object element);
/**
* 在指定位置插入元素
* @param target
* @param element
*/
void add(int target,Object element);
/**
* 根据元素的值来删除
* @param element
*/
void delete(Object element);
/**
* 根据索引来删除元素
* @param index
*/
void delete(int index);
/**
* 根据指定的target索引位置来更新元素
* @param traget
* @param element
*/
void update(int traget,Object element);
/**
* 返回某一元素第一次在线性表中出现的位置
* @param element
* @return
*/
int indexOf(Object element);
/**
* 返回在指定target位置的元素
* @param target
* @return
*/
Object elementAt(int target);
/**
* 取指定索引位置元素的前驱元素
* @param index
* @return
*/
Object elementPrior(int index);
/**
* 取指定索引位置元素的后继元素
* @param index
* @return
*/
Object elementNext(int index);
}
MyLinearList的全部代码
package day01线性表;
public class MyLinearList implements MyList{
// 用数组来实现线性表
// 定义成员变量
private Object[] elementList;
private int size=0;//线性表初始长度为0
private int capacity=10;//默认线性表容量为10
//定义构造方法，初始化线性表容量
//根据用户指定容量来生成指定长度的线性表
public MyLinearList(int capacity) {
this.capacity = capacity;
elementList =new Object[capacity];
}
//默认的线性表长度为10
public MyLinearList() {
elementList = new Object[capacity];
}
@Override
public void add(Object element) {
//如果当前元素长度大于线性表的容量则选择扩容
if(size>=capacity){
capacity+=1;
Object[] newArr = new Object[capacity];
//将之前的元素复制到新的线性表newArr中
for (int i = 0; i < size; i++) {
newArr[i] = elementList[i];
}
//用新的扩容以后的newArr来当作新的线性表的地址
elementList = newArr;
}
elementList[size++] = element;
}
@Override
public void add(int target, Object element) {
//指定位置插入元素，则需要考虑右移元素
if(size>=capacity){
capacity+=1;
Object[] newArr = new Object[capacity];
//将之前的元素复制到新的线性表newArr中
for (int i = 0; i < size; i++) {
newArr[i] = elementList[i];
}
//用新的扩容以后的newArr来当作新的线性表的地址
elementList = newArr;
//将元素右移
for (int i = capacity-1; i >target; i--) {
elementList[i] = elementList[i-1];
}
elementList[target] = element;
size+=1;
}else{
for (int i = capacity-1; i >target; i--) {
elementList[i] = elementList[i-1];
}
elementList[target] = element;
size+=1;
}
}
@Override
public void delete(Object element) {
int index = indexOf(element);
if(index>=0){
delete(index);
}
}
@Override
public void delete(int index) {
//线性表删除涉及到删除某一元素，需要将其后面的元素进行左移操作
elementList[index]=null;
for (int i = index; i <= size-index; i++) {
elementList[i] = elementList[i+1];
}
size-=1;
}
@Override
public void update(int traget, Object element) {
elementList[traget] =element;
}
@Override
public int indexOf(Object element) {
//如果可以在线性表中找到对应的元素的值，则返回索引，否则返回-1表示要找的元素不存在
for (int i = 0; i < size; i++) {
if(elementList[i].equals(element)){
return i;
}
}
return -1;
}
@Override
public Object elementAt(int target) {
if (target>capacity-1){
System.out.println("访问的索引已经越界!");
return null;
}
return elementList[target];
}
@Override
public Object elementPrior(int index) {
if(index>size-1||index-1<0){
return -1;
}
return elementList[index-1];
}
@Override
public Object elementNext(int index) {
if(index+1>size-1){
return -1;
}
return elementList[index+1];
}
//清空线性表内容
public static void clearList(MyLinearList myLinearList) {
myLinearList.size =0;
}
//线性表是否为空
public static boolean isEmpty(MyLinearList myLinearList) {
if(myLinearList.size==0){
return true;
}
return false;
}
//输出当前线性表容量
public static void listLength(MyLinearList myLinearList) {
System.out.println("当前线性表容量为:"+ myLinearList.capacity);
}
//输出当前线性表长度
public static void listSize(MyLinearList myLinearList) {
System.out.println("当前线性表中不为空的元素个数为:"+ myLinearList.size);
}
//重写toString方法
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("[");
for (int i = 0; i < size; i++) {
stringBuilder.append(elementList[i]+(i==size-1?"":","));
}
stringBuilder.append("]");
return stringBuilder.toString();
}
//线性表遍历输出
public static void listPrint(MyLinearList myLinearList){
System.out.println(myLinearList.toString());
}
public static void main(String[] args) {
//测试，首先生成一个长度为10 的线性表,并且使用add方法顺序插入10个元素
MyLinearList list = new MyLinearList();
list.add("one");
list.add("two");
list.add("three");
list.add(".");
list.add("A");
list.add("B");
list.add("D");
list.add("E");
list.add("F");
list.add("G");
listPrint(list);
//现在继续增加一个元素到list，看是否会扩容
list.add(11);
listPrint(list);
listLength(list);//长度扩容为20
System.out.println(list.indexOf("three"));
list.delete("three");
listPrint(list);
list.add("ok");
listPrint(list);
list.update(2,"!");
listPrint(list);
list.add(2,"?");
listPrint(list);
listSize(list);
System.out.println("index为2的前驱元素为:"+list.elementPrior(2));
System.out.println("index为5的后继元素为:"+list.elementNext(5));
clearList(list);
listPrint(list);
System.out.println(list.isEmpty(list));
}
}
以上，就是线性表顺序存储的实现，小白萌新学习记录，各位大佬点个赞！数据结构陆续更新中！！！
