复习了一些数据结构的东西,打算把常用的数据结构都实现一下,慢慢来,慢慢来 顺序表是用一组地址连续的存储单元依次存储线性表的数据元素。这里一般考虑的是有序的顺序表。因为如果C语言实现这种数据结构可以使用指针, 在JAVA中没有指针,用 对象,并且是用一种动态的数组ArrayList可以实现,但是没有用,增加内存方面不知道有什么比较好的解决方案。编码比较水,勤加练习~~
public class SqList {
//顺序线性表
private int length;
private int listSize;
private int incrementSize;
private int[] elem;//存储整型数据的一维数组
public SqList(int[] elem,int listSize,int incrementSize){
/*this.elem = elem;
this.length = length;
this.length = this.elem.length;
this.listSize = listSize;
this.incrementSize = incrementSize;*/
//这个地方貌似不能这样写
this.listSize = listSize;
this.elem = new int[this.listSize];//开辟空间的大小
this.length = elem.length;
for(int i=0;i<length;i++){
this.elem[i]=elem[i];
}
this.incrementSize = incrementSize;
}
public SqList(int listSize,int incrementSize ){
this.elem =new int[listSize];
this.length = this.elem.length;
this.listSize = listSize;
this.incrementSize = incrementSize;
}
public int getLength() {
return length;
}
public void setLength(int length) {
this.length = length;
}
public int getListSize() {
return listSize;
}
public void setListSize(int listSize) {
this.listSize = listSize;
}
public int getIncrementSize() {
return incrementSize;
}
public void setIncrementSize(int incrementSize) {
this.incrementSize = incrementSize;
}
public int[] getElem() {
return elem;
}
public void setElem(int[] elem) {
this.elem = elem;
}
public void increment(){
}
}
下面就是对顺序表的查找、插入、删除、逆置、比较、元素互换、折半查找插入等基本方法
package SqList_Operator;
import java.text.MessageFormat;
public class SqlList_Tool {
//在有序顺序表上查找
public static int localElem(SqList l,int elem){
int index=0;
int i=0;
while(i<l.getElem().length&&l.getElem()[i++]!=elem);
if(i<l.getLength()){
index = i;
}
return index;
}
//在顺序表上插入
public static void listInsert(SqList l,int elem){
//在插入之前还要先判断当前的存储空间是否已满
//在插入之前先打印出来原有的顺序表
SqlList_Tool.printSq(l);
if(l.getLength()>=l.getListSize()){
l.increment();
}
int j =l.getLength()-1;
while(l.getElem()[j]>elem&&j>=0){
l.getElem()[j+1]=l.getElem()[j];
j--;
}
if(j>=0){
l.getElem()[j+1]=elem;
l.setLength(l.getLength()+1);
}
System.out.print("插入之后的顺序表为:");
SqlList_Tool.printSq(l);
}
public static int listDelete(SqList l,int i){
int elem;
//存在一个元素移动的过程,i之后的元素都要向前移动一个位置
elem = l.getElem()[i-1];
for(int j=i;j<l.getLength();j++){
l.getElem()[j]=l.getElem()[j+1];
}
l.setLength(l.getLength()-1);
SqlList_Tool.printSq(l);
return elem;
}
//两个顺序表比较
public static int compareList(SqList l1,SqList l2){
int j=0;
while(j<l1.getLength()&&j<l2.getLength()){
if(l1.getElem()[j]>l2.getElem()[j])return 1;
else if(l1.getElem()[j]<l2.getElem()[j])return -1;
else j++;
}//比如l1已经遍历完成,就不能判断了,就从列表的长度上得出结果
if(l1.getLength()==l2.getLength())
return 0;
else if(l1.getLength()<l2.getLength())return -1;
else return 1;
}
public static void exchangel(SqList l,int m,int n){
//将l1中前m个元素与后n个元素互换
int temp;
for(int k=0;k<n;k++){
temp = l.getElem()[m+k];
for(int j=m+k-1;j>=k;j--){
l.getElem()[j+1]=l.getElem()[j];
}
l.getElem()[k]=temp;
}
SqlList_Tool.printSq(l);
}
//在递增有序的顺序表中插入一个元素,首先要查询待插入元素的位置,因为顺序表元素递增有序,采用折半查找法
public static void insertMiddel(SqList sq,int num,int elem){
int low =0;
int high = num-1;
//num为顺序表中元素的个数
int middle = 0;
while(low<=high){
middle =(low+high)/2;
if(sq.getElem()[middle]==elem){
low = middle+1;
break;
}else if(sq.getElem()[middle]>elem){
high = middle-1;
}else{
low = middle+1;
}
}
//因为要进行插入,则将middle之后的
for(int i=num;i>=low;i--){
sq.getElem()[i+1] = sq.getElem()[i];
}
sq.getElem()[middle]=elem;
SqlList_Tool.printSq(sq);
}
public static void printSq(SqList l){
System.out.print("目前顺序表的长度为"+l.getLength());
System.out.println();
for(int i=0;i<l.getLength();i++){
System.out.print(MessageFormat.format("在顺序表第{0}个位置的元素为{1}", i+1,l.getElem()[i]));
System.out.println();
}
}
}
再接再厉,吼吼^O^