1. 线性表
线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。常见的线性表:顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物 理上存储时,通常以数组和链式结构的形式存储。
顺序表:
链表:
2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成 数据的增删查改。
2.1 顺序表底层的实现
2.1.1 打印顺序表
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.println(this.elem[i]+" ");
}
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.display();
}
}
2.1.2 在数组末尾新增元素
思路:1. 判断数组是否已满,若满的话,需要进行扩容;
2. 其次在数组末尾插入新增元素。
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void add(int data){
if (this.usedSize == this.elem.length){
int[] elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
this.elem[this.usedSize]=data;
this.usedSize++;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.display();
sqList.add(1);
sqList.display();
}
}
2.1.3 在pos位置新增元素
思路:1. 首先需要判断pos位置的合法性,即pos不能小于0或者pos不能大于usedSize;
2. 判断数组是否已满,若已满则需要扩容;
3. 最后将pos位置及其后面的元素向后面挪动,将pos位置腾出来,然后再将指定元素放入到pos位置
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public void add(int pos,int val){
if (pos <0 || pos >this.usedSize){
System.out.println("所输入的pos位置不合法,请重新输入!");
}
if (this.usedSize == this.elem.length){
int[] elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
for (int i = this.usedSize-1; i >=pos ; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos]=val;
this.usedSize++;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
sqList.add(2,4);
sqList.display();
}
}
2.1.4 判断是否包含某个元素
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public boolean contains(int find){
for (int i = 0; i < this.usedSize; i++) {
if (find == this.elem[i]){
return true;
}
}
return false;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
boolean ret = sqList.contains(5);
System.out.println(ret);
}
}
2.1.5 查找某个元素的位置
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public int indexOf(int toFind){
for (int i = 0; i < this.usedSize; i++) {
if (toFind == this.elem[i]){
return i;
}
}
return -1;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
int tmp = sqList.indexOf(4);
System.out.println(tmp);
}
}
2.1.6 获取pos位置的元素
思路:1. 首先判断pos位置的合法性,即pos不能小于0或者pos不能>=usedSize;
2. 判断顺序表是否为空;
3. 最后在获取pos位置的元素。
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public int get (int pos){
if (pos < 0 || pos >= this.usedSize){
System.out.println("pos的位置不合法,请重新输入!");
}
if (this.usedSize == 0){
System.out.println("顺序表为空!");
}
return this.elem[pos];
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
int a = sqList.get(3);
System.out.println(a);
}
}
2.1.7 给 pos 位置的元素设为 value
思路:1. 首先判断pos位置的合法性,即pos不能小于0或者pos不能>=usedSize;
2. 判断顺序表是否为空;
3. 最后在获取pos位置的元素。
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public int set (int pos,int data){
if (pos < 0 || pos >= this.usedSize){
System.out.println("pos的位置不合法,请重新输入!");
}
if (this.usedSize == 0){
System.out.println("顺序表为空!");
}
return this.elem[pos]=data;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
int ret =sqList.set(2,8);
System.out.println(ret);
}
}
2.1.8 删除第一次出现的关键字key
思路:1. 首先判断顺序表是否为空;
2. 需要找到关键字key的下标;
3.用key的下标后面的数一次往前面覆盖。
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public int look(int key){
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == key){
return i;
}
}
return -1;
}
public void remove(int key){
if (this.usedSize == 0){
System.out.println("顺序表为空!");
}
int indexOf = look(key);
if(indexOf < 0 ){
System.out.println("查无此数");
}
for (int j = indexOf; j < this.usedSize-1; j++) {
this.elem[j] = this.elem[j+1];
}
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
sqList.remove(2);
sqList.display();
}
}
2.1.9 获取顺序表长度
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public int size(){
return this.usedSize;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
int ret = sqList.size();
System.out.println(ret);
}
}
2.1.10 清空顺序表
有两种情况:1. 如果顺序表里面存的是是基本数据类型:直接让this.usedSize=0.
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public void clear(){
this.usedSize = 0;
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
sqList.clear();
sqList.display();
}
}
2. 如果数组里面存的是引用数据类型:遍历顺序表,给每个值都赋值给null。
class SqList{
public int[] elem ;
public int usedSize;
public static final int DEFAULT_SIZE = 10;
public SqList() {
this.elem = new int[DEFAULT_SIZE];
}
public void display(){
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
public void clear(){
for (int i = 0; i < this.usedSize; i++) {
this.elem[i] = null;
}
}
}
public class ArrayList {
public static void main(String[] args) {
SqList sqList = new SqList();
sqList.add(1);
sqList.add(2);
sqList.add(3);
sqList.add(4);
sqList.add(5);
sqList.display();
sqList.clear();
sqList.display();
}
}



