最近需要复习数据结构和算法，数据结构曾经上课好好学过的，不过现在很多都忘记了，所以决定专门开个专题给数据结构和算法，以防止自己再忘记的时候捡不起来。
今天复习顺序表(Sequential List)，顺序表是按照顺序储存数据的线性表：
顺序表的优点
- 简单：用数组即可实现
- 省空间：我们不需要利用额外的空间去储存结点间的逻辑关系
- 按照序号可以随机去访问结点
顺序表缺点
- 处理增加删除很费劲！平均移动大约表中一半的元素，因此对长度较长的顺序表进行增加删除效率低。
- 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
实例：
首先我们需要准备数据，数据是到时候存放在表中的。
Data.java
package model;
//这是一个结点 有key和name作为变量
public class Data {
String key; //键
String name; //名字
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Data(String key, String name) {
super();
this.key = key;
this.name = name;
}
@Override
public String toString() {
return "Data [key=" + key + ", name=" + name + "]";
}
}
然后就可以开始设计顺序表了，我注释已经写的详细的不得了。
SLType.java
package model;
import java.util.Iterator;
//这是顺序表，注意此处Data类型是在model包中我们自定义的，不是系统的。
public class SLType {
static final int MAXLEN=100;
Data[] ListData = new Data[MAXLEN+1]; //数组中存的是我们自己定义的Data类型，设置了数组最长长度
int ListLen; //表中已存的结点数
/**
* 初始化顺序表
* @param SL 初始化的表
*/
public void SLInit(SLType SL){
SL.ListLen=0; //初始化为空表
}
/**
* 将一条数据插入到表中
* @param SL 表主体，代表我们要向哪个顺序表插入数据
* @param n 插入的位置
* @param data 插入表中的数据本体
* @return 0代表插入失败 1代表插入成功
*/
public int InsertToSL(SLType SL,int n,Data data){
//先判断表是否已经满了
if (SL.ListLen>=MAXLEN) {
System.err.println("此顺序表已经满了！");
return 0;
}
//判断插入位置不合理 一是小于一，二是位置比表本身的长度还长
if (n<1||n>SL.ListLen-1) {
System.err.println("插入数据位置有错误！");
return 0;
}
System.out.println(n);
System.out.println(SL.ListLen);
//将表中的数据向后移
for (int i = SL.ListLen; i >= n; i--) {
//往后挪
SL.ListData[i+1] = SL.ListData[i];
}
//如果是想用i++这种方式的话，会比较麻烦
// int length = SL.ListLen;
// for(int i=n; i<=SL.ListLen; i++){
// SL.ListData[length-i+n+1] =SL.ListData[length-i+n];
// }
//这里给空出来的这个位置赋值，填充上传进来的data
SL.ListData[n] = data;
SL.ListLen++;
return 1;
}
/**
* 向尾部添加结点
* @param SL 顺序表
* @param data 被添加的结点
* @return 1为成功 0为失败
*/
public int AddSL(SLType SL,Data data){
//先判断表是否已经满了
if (SL.ListLen>=MAXLEN) {
System.err.println("此顺序表已经满了！");
return 0;
}
SL.ListData[++SL.ListLen]=data;
return 1;
}
/**
* 删除表中的数据元素
* @param SL 表
* @param n 删除的结点序号
* @return
*/
public int SLDelete(SLType SL,int n){
//判断删除位置不合理 一是小于一，二是位置比表本身的长度还长
if (n<1||n>SL.ListLen+1) {
System.err.println("删除数据位置有错误！");
return 0;
}
//这里把表中的数据向前移动
for(int i =n;i<SL.ListLen;i++){
SL.ListData[i]=SL.ListData[i+1];
}
SL.ListLen--;
return 1;
}
/**
* 根据序号返回 结点
* @param SL 表
* @param n 序号
* @return
*/
public Data FindSLByNum(SLType SL,int n){
if (n<1||n>SL.ListLen+1) {
System.err.println("查询数据位置有错误！");
return null;
}
return SL.ListData[n];
}
/**
* 根据key关键字，查找结点的位置
* @param SL 表
* @param key 键
* @return i位置，0为没找到
*/
public int SLFindByCont(SLType SL,String key){
for(int i = 1;i<SL.ListLen;i++){
if (SL.ListData[i].key.compareTo(key)==0) {
return i;
}
}
return 0;
}
/**
* 查询表中所有结点数据
* @param SL
*/
public void ShowAllSL(SLType SL){
for (int i = 1; i < SL.ListLen+1; i++) {
System.out.println(SL.ListData[i].key+":"+SL.ListData[i].name);
}
}
}
好的，这俩写完了，就可以开始测试了，我把我的测试也写上好啦~
Test.java
package test;
import model.Data;
import model.SLType;
public class Test {
public static void main(String[] args) {
SLType SL = new SLType();
//初始化
SL.SLInit(SL);
//添加数据
Data d1 = new Data("001", "张三");
Data d2 = new Data("002", "李四");
Data d3 = new Data("003", "哈哈");
System.out.println("添加数据结果:"+SL.AddSL(SL,d1));
System.out.println("添加数据结果:"+SL.AddSL(SL,d2));
System.out.println("添加数据结果:"+SL.AddSL(SL,d3));
// //显示所有
// SL.ShowAllSL(SL);
//插入数据
// Data d4 = new Data("666","我是插入数据");
// System.out.println("插入数据结果："+SL.InsertToSL(SL, 2, d4));
// //显示所有
// SL.ShowAllSL(SL);
//删除数据
// System.out.println("删除数据结果："+SL.SLDelete(SL, 2));
// SL.ShowAllSL(SL);
//查找数据：根据序号查
// System.out.println(SL.FindSLByNum(SL, 2));
//查找序号：通过key
// System.out.println(SL.SLFindByCont(SL, "002"));
}
}
这就完成了，顺序表可以说是最简单的了，可写的时候还是遇到了很多问题，越简单的东西写起来越容易出问题，真的让我体会到，学过的东西还是时而复习一下比较好。
网友评论