目录
一：线性表
????????线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构，也就说是连续的一条直线。下图直观地显示了几种常见的线性表。
二：顺序表
2.1顺序表的定义
????????顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。?
2.2顺序表的实现
? ? ? ? 顺序表的实现容易处理。
????????根据顺序表的定义，在创建一个顺序表时，我们至少需要两个成员，一个用于是存储元素的数组，一个是数组中已储存的元素个数。当我们进行增删查改等操作时，就是通过比较数组中已储存元素的个数与数组长度的大小，来判断操作位置是否合法，或是否需要进行数组的扩容等。
? ? ? ? 接下来，我们就以尽可能严谨且简单的宗旨，实现一个顺序表。
? ? ? ? ?我们仅需要创建两个类，一个MyArraylist，我会在这里书写顺序表实现的逻辑；一个TestDemo，主要用于对代码逻辑进行测试。
MyArraylist.java
package sqlist;
import java.util.Arrays;
public class MyArraylist {
public int[] elem;//数组
public int usedSize;//数组中元素的个数
private static final int DEDAULT_SIZE = 4;//初始化时开辟的空间
public MyArraylist() {
this.elem = new int[DEDAULT_SIZE];//初始化
}
public void display() {
//说白了就是打印
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i]);
System.out.print(" ");
}
System.out.println();
}
public boolean isFull(){
return (usedSize-elem.length)==0;
}
//默认在数组最后新增
public void add(int data) {
//1.判断是否满，满->进行扩容->设计了isFull()函数，返回值为boolean
if(isFull()){
this.elem = Arrays.copyOf(this.elem, (int) (1.5*elem.length));
}
//2.不满，进行插入
elem[usedSize] = data;
usedSize++;
}
public boolean checkPos(int pos){
if(pos < 0||pos >= usedSize){
System.out.println("下标位置不合法!");
return false;
}else{
return true;
}
}
//在pos位置新增元素
public void add(int pos, int data) {
//1.判断下标是否合法->设计了checkPos()函数
//2.判断数组是否满了
//3.插入元素（覆盖）
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, (int) (1.5*this.elem.length));
}
if(checkPos(pos)){
for (int i = usedSize; i >pos; i--) {
elem[i] = elem[i-1] ;
}
elem[pos] = data;
this.usedSize++;
}
}
//判断是否包含某个元素
public void contains(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(toFind == elem[i]){
System.out.println("包含这个元素！");
return;
}
}
System.out.println("不包含这个元素！");
}
//查找某个元素对应的位置
public int indexOf(int toFind) {
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind){
return i;
}
}
return -1;
}
//
//获取pos位置的元素
public int get(int pos) {
if(checkPos(pos)){
return elem[pos];
}else{
return -1;
}
}
//
//给pos位置的元素设置为value
public void set(int pos, int value) {
if(checkPos(pos)){
elem[pos] = value;
}
}
//
//删除第一次出现的关键字key
public void remove(int key) {
int currentSize = usedSize;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == key){
for (int j = i; j < usedSize-1; j++) {
elem[j] = elem[j+1];
}
this.usedSize--;
}
}
if(currentSize ==usedSize){
System.out.println("该元素不存在，无法删除！");
}
}
//
//获取顺序表长度
public int size() {
return this.usedSize;
}
//
//清空顺序表
public void clear() {
this.usedSize = 0;
}
}
TestDemo.java
package sqlist;
public class TestDemo {
public static void main(String[] args) {
MyArraylist list = new MyArraylist();
list.add(1);
list.add(2);
list.add(1,3);
list.add(2,4);
list.add(3,23);
list.display();
list.remove(3);
list.display();
System.out.println(list.indexOf(2));
list.contains(23);
list.clear();
list.display();
}
}
2.3具体分析及部分操作详解
MyArraylist.java
2.3.1判断顺序表是否已满
//判断顺序表是否已满
public boolean isFull(){
return (usedSize-elem.length)==0;
}? ? ? ? ?在判断顺序表是否已满时，我们很自然地会想到使用if()...else...式的选择结构，其实我们只需直接返回(usedSize-elem.length)==0这个布尔表达式的结果。
2.3.2在pos位置新增元素
//判断顺序表是否已满
public boolean isFull(){
return (usedSize-elem.length)==0;
}
//判断下标合法性
public boolean checkPos(int pos){
if(pos < 0||pos >= usedSize){
System.out.println("下标位置不合法!");
return false;
}else{
return true;
}
}
//在pos位置新增元素
public void add(int pos, int data) {
//1.判断下标是否合法->设计了checkPos()函数
//2.判断数组是否满了
//3.插入元素（覆盖）
if (isFull()) {
this.elem = Arrays.copyOf(this.elem, (int) (1.5*this.elem.length));
}
if(checkPos(pos)){
for (int i = usedSize; i >pos; i--) {
elem[i] = elem[i-1] ;
}
elem[pos] = data;
this.usedSize++;
}
}? ? ? ? 要想在一个位置新增元素，至少需要满足两个条件：
- 顺序表未满；
- 该位置合法。
????????所以我们先使用ifFull()函数判断数组是否已满，如果返回值为true，则进行扩容，这里选择的是1.5倍扩容，用到了Arrays.copyOf()方法。如果你忘记了该方法，没关系，只需参考这篇博客：
(9条消息) Arrays.copyOf() 用法_qq_25131363的博客-CSDN博客_arrays.copyof用法
https://blog.csdn.net/qq_25131363/article/details/85001414? ? ? ? 完成了该检验，我们还需检验新增元素的位置是否合法，使用checkpos函数，合法的位置，其下标应处于? [0,usedSize）区间。
? ? ? ? 在pos位置插入元素，那么原顺序表中该位置及其后的元素全部需要后移一位。如果从前向后移动，那么位置靠后的元素会被覆盖，这不是我们所希望的；所以这里的for循环从数组(顺序表)最后一个元素开始，循环使前一个元素的值覆盖后一元素的值，直到原先pos位置的元素也被后移；这时就可以将要插入的元素放在pos位置了。最后，别忘了将数组有效元素的个数usedSize+1。
2.3.3删除第一次出现的关键字key
//删除第一次出现的关键字key
public void remove(int key) {
int currentSize = usedSize;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == key){
for (int j = i; j < usedSize-1; j++) {
elem[j] = elem[j+1];
}
this.usedSize--;
}
}
if(currentSize ==usedSize){
System.out.println("该元素不存在，无法删除！");
}
}? ? ? ? 删除一个元素本身并不难，只需遍历数组，查找第一次出现key的位置，而后将该位置之后的元素统一向前移动一位，usedSize-1，则会通过覆盖实现删除目的。
? ? ? ? 值得注意的是，无论数组中是否存在关键字key，最终都会跳出for循环，那究竟是删除了元素后跳出了for循环，还是未找到key，跳出了for循环呢？我暂时想到两种思路，一种思路是在一开始保存一份usedSize的值，当for循环结束后，再与现在的usedSize进行比较；另一种思路是将函数的返回值设置为int，成功删除则返回1，否则返回-1，最后根据返回值判断是否完成了删除。
2.3.4清空顺序表
//清空顺序表
public void clear() {
this.usedSize = 0;
}
}? ? ? ? 当数组元素为整型时，只需将usedSize置0，这样有效个数变为0，相当于清空了顺序表。
? ? ? ? 如果数组元素是引用类型呢？那就得一个一个置为空：
如果是引用数据类型 得一个一个置为空 这样做才是最合适的
for (int i = 0; i < this.usedSize; i++) {
this.elem[i] = null;
}
this.usedSize = 0;TestDemo.java
?
? ? ? ? 测试任务就更加容易了，只需创建一个list对象，然后实现MyArraylist.class中的所有功能即可。在此不做赘述。
三：ArrayList（重点）
3.1ArrayList简介
在集合框架中，ArrayList是一个普通的类，实现了List接口，具体框架图如下：
? ? ? ? 我们也可查看ArrayList的源码：
? ? ? ? ?通过框架图和源码，我们得到如下结论：
【注意】
1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问；
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的；
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的；
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList；
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表。
3.2ArryList使用
3.2.1ArryList的构造
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(1);//往数组的最后一个位置存元素
arrayList.add(2);
arrayList.add(3);
arrayList.add(4);
System.out.println(arrayList);
System.out.println("=============");
//使用其他的集合 来构造当前的list
ArrayList<Integer> arrayList2 = new ArrayList<>(arrayList);
arrayList2.add(23);
arrayList2.add(24);
System.out.println(arrayList2);
ArrayList<Integer> arrayList3 = new ArrayList<>(15);
}运行结果如下：
? ? ? ? 前面我们讲过，集合框架就是一大堆的集合类，这些类是java官方帮我们封装好的一些数据结构，即我们用到某个数据结构时，直接用java提供的对应的集合类即可。
????????当我们写出??ArrayList<Integer> arrayList = new ArrayList<>();??这样一行代码时，就相当于拥有了一个顺序表！这个顺序表，就包含我们前面在ArrayList.class中实现的所有功能！同时，我们还可以使用其他的集合，来构造当前的list，如arrayList2所示；在构造list时可以指定容量，如arrayList3所示。以上，就是ArrayList的三大构造！接下来，我会通过分析源码，较为深入地理解这三种构造方法。
不带参数的构造方法：
?
【总结】：
1.如果仅调用不带参数的构造方法，数组长度默认是0；
2.只有第一次add时，数组长度才变成了10；
3.grow()是1.5倍扩容。
带一个参数的构造方法：
?指定顺序表初始容量的构造方法：
? ? ? ? 以上就是三大构造方法！
3.2.2ArrayList常见操作
具体示例如下：
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,23);
arrayList.add(3,23);
arrayList.add(4,23);
System.out.println(arrayList);
//从后往前找 的第一个23这个元素
int index = arrayList.lastIndexOf(new Integer(23));
System.out.println(index);
arrayList.remove(new Integer(23));
ArrayList<Integer> arrayList2 = new ArrayList<>();
arrayList2.addAll(arrayList);
arrayList2.add(19);
System.out.println(arrayList2);
}?运行结果如下：
? ? ? ? ?依我所见，需要注意的是以下两个方法：
????????第一个是remove()方法，我们需要传入一个Object类型的对象，而在实例中，因为每个元素都是Integer类型的，所以不能直接将元素传入，而要通过new Integer(23)传入元素。
? ? ? ? 第二个是sulList()方法，注意其返回值为一个List<>对象，<>为具体的数据类型，具体实例如下：
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0,1);
arrayList.add(1,2);
arrayList.add(2,3);
arrayList.add(3,4);
arrayList.add(4,5);
System.out.println(arrayList); //1,2,3,4,5
System.out.println("===============");
List<Integer> list = arrayList.subList(1,3);//[2,3)
System.out.println(list);//2,3
System.out.println("=================");
list.set(0,77);
System.out.println(list); //77,3
System.out.println("原来的list"+ arrayList); //1,77,3,4,5
}?运行结果如下：
????????有趣的是，当我们修改截取出来的数组中的元素时，原来数组中相应位置的内容也发生了改变。这说明截取函数是在本身进行截取，而没有开辟新的内存。图解如下：
?3.2.3ArrayList的遍历
方法一：直接sout输出
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, 1);
arrayList.add(1, 2);
arrayList.add(2, 3);
arrayList.add(3, 4);
arrayList.add(4, 5);
System.out.println(arrayList);
}运行结果如下：
?这说明ArrayList或者其父类，一定是重写了toString()方法的。
方法二：fori循环
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, 1);
arrayList.add(1, 2);
arrayList.add(2, 3);
arrayList.add(3, 4);
arrayList.add(4, 5);
for (int i = 0; i < arrayList.size(); i++) {
System.out.print(arrayList.get(i)+" ");
}
System.out.println();
}运行结果如下：
?方法三：foreach循环
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, 1);
arrayList.add(1, 2);
arrayList.add(2, 3);
arrayList.add(3, 4);
arrayList.add(4, 5);
for (Integer x : arrayList) {
System.out.print(x +" ");
}运行结果如下：
?方法四：使用迭代器
public class TestDemo {
public static void main(String[] args) {
ArrayList<Integer> arrayList = new ArrayList<>();
arrayList.add(0, 1);
arrayList.add(1, 2);
arrayList.add(2, 3);
arrayList.add(3, 4);
arrayList.add(4, 5);
Iterator<Integer> it = arrayList.iterator();
while (it.hasNext()) {
System.out.print(it.next()+" ");
}
System.out.println();
System.out.println("===============");
Iterator<Integer> it2 = arrayList.listIterator();
while (it2.hasNext()) {
System.out.print(it2.next()+" ");
}
}
运行结果如下：
?这两种使用迭代器的方法，本质上都是一样的。
四：练习
4.1杨辉三角
? ? ? ? ?进入此题，这个函数头就就具有一定的研究价值了，这本质上是一个二维数组，如图所示：
? ? ? ? 首先我们要明确，在具体实现过程中，我们要把杨辉三角看成一个直角三角形。其每一行的元素具有如下规律：
? ? ? ? 所以对于每一行，我们的思路是：先添加第一个元素——1，再添加中间的元素，最后添加最后一个元素——1。由于第一行只有一个元素，所以我们进行单独处理，仅添加一个‘1’即可。其后的每行在for循环中实现。因为在计算中间元素的值时，需要用到前一行元素，所以我们先用一个?List<Integer>类型的变量存储前一行。
? ? ? ? 整个题目的代码如下：
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> ret = new ArrayList<>();
List<Integer> one = new ArrayList<>();
one.add(1);
ret.add(one);
//i 代表每一行
for (int i = 1; i < numRows; i++) {
List<Integer> curRow = new ArrayList<>();
//这一行开始的1
curRow.add(1);
//这一行中间的元素
List<Integer> preRow = ret.get(i-1);//存储前一行的信息
//j 代表这一行的每个元素
for (int j = 1; j < i ; j++) {
int x = preRow.get(j) + preRow.get(j-1);
curRow.add(x);
}
//j == i 这一行最后的1
curRow.add(1);
//这一行搞定后，整体添加到ret中
ret.add(curRow);
}
return ret;
}
}4.2扑克牌
? ? ? ? 那年杏花微雨，三位滑稽老铁齐聚一堂，计划来两局扑克牌。现在我们就要简单实现一个牌局。明确一下我们的需求：
? ? ? ? 欲得一副扑克牌，首先需要创建一个扑克牌类。通过简单分析可知，花色和牌面两个属性可以唯一地确定一副扑克牌。
?????????所以我们在创建Card类时，只需设置这两个属性即可。其次，提供通用的Getter And Setter方法，以便从类的外部访问到这两个属性。重写ToString()方法，方便将扑克牌显示输出。
? ? ? ? Step1：创建扑克类
class Card{
private String suit; //花色
private int rank; //牌面
public Card(String suit, int rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() {
return suit;
}
public void setSuit(String suit) {
this.suit = suit;
}
public int getRank() {
return rank;
}
public void setRank(int rank) {
this.rank = rank;
}
@Override
public String toString() {
return "[ " + suit+" "+rank+" ]";
}
}? ? ? ? Step2：买牌。把每一张牌看成一个元素，那么可以将所有的牌放在一个顺序表中。通过嵌套循环，设置每一张牌的花色和牌面。具体代码如下：
public static final String[] suits ={"?","?","?","?"};
//买牌
public static List<Card> buyCard(){
List<Card> desk = new ArrayList<>();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 13; j++) {
String suit = suits[i];
Card card = new Card(suit,j+1);
desk.add(card);
}
}
return desk;
}? ? ? ? Step3：洗牌。经过循环赋值之后，desk顺序表中已经放置了52张扑克牌，但它们是遵循严格顺序的，所以我们还需要进行“洗牌”的操作。我们的思路是，通过顺序表中元素的交换实现洗牌。为体现随机性，每次循环都将当前下标的元素和顺序表中的任一元素进行交换，在这里我们采用生成随机数的方法。当循环结束时，意味着顺序表中的每一个元素都进行了至少一次的随机交换，也就达到了我们洗牌的目的。具体代码如下：
private static void swap(List<Card> cardList,int i,int j) {
Card tmp = cardList.get(i);
cardList.set(i,cardList.get(j));
cardList.set(j,tmp);
}
public static void shuffle(List<Card> mydesk){
for (int i = mydesk.size()-1; i > 0 ; i--) {
Random random = new Random(); //生成一个随机数
int index = random.nextInt(i);
swap(mydesk,i,index);
}
}? ? ? ? Step4：在主函数中，我们实现轮流发牌的功能。所有的牌组成一个元素较多的顺序表，而每位玩家拿到的牌又可以看作是一个元素较少的顺序表。发牌就是将牌从总的顺序表中删除，轮流添加到每一个“小的顺序表”当中。具体代码如下：
public static void main(String[] args) {
List<Card> cardList = buyCard();
System.out.println("买牌："+cardList);
shuffle(cardList);
System.out.println("洗牌："+cardList);
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<Card> hand3 = new ArrayList<>();
List<List<Card>> hands = new ArrayList<>();
hands.add(hand1);
hands.add(hand2);
hands.add(hand3);
// 5个人 轮流揭牌5张 i=0就是第一次
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
//每次揭牌都去获取 cardList的0下标的数据【删除】
Card card = cardList.remove(0);
List<Card> hand = hands.get(j);
hand.add(i,card);//这里使用add 不能是set
/*hands.get(j).add(card);*/
}
}
System.out.println("第1个人的牌："+hand1);
System.out.println("第2个人的牌："+hand2);
System.out.println("第3个人的牌："+hand3);
System.out.println("剩余的牌："+cardList);
}? ? ? ? 整体展示实现“扑克牌”的全部代码：
package TestCard;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
class Card{
private String suit; //花色
private int rank; //牌面
public Card(String suit, int rank) {
this.suit = suit;
this.rank = rank;
}
public String getSuit() {
return suit;
}
public void setSuit(String suit) {
this.suit = suit;
}
public int getRank() {
return rank;
}
public void setRank(int rank) {
this.rank = rank;
}
@Override
public String toString() {
return "[ " + suit+" "+rank+" ]";
}
}
public class TestCard {
public static final String[] suits ={"?","?","?","?"};
//买牌
public static List<Card> buyCard(){
List<Card> desk = new ArrayList<>();
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 13; j++) {
String suit = suits[i];
Card card = new Card(suit,j+1);
desk.add(card);
}
}
return desk;
}
private static void swap(List<Card> cardList,int i,int j) {
Card tmp = cardList.get(i);
cardList.set(i,cardList.get(j));
cardList.set(j,tmp);
}
public static void shuffle(List<Card> mydesk){
for (int i = mydesk.size()-1; i > 0 ; i--) {
Random random = new Random(); //生成一个随机数
int index = random.nextInt(i);
swap(mydesk,i,index);
}
}
public static void main(String[] args) {
List<Card> cardList = buyCard();
System.out.println("买牌："+cardList);
shuffle(cardList);
System.out.println("洗牌："+cardList);
List<Card> hand1 = new ArrayList<>();
List<Card> hand2 = new ArrayList<>();
List<Card> hand3 = new ArrayList<>();
List<List<Card>> hands = new ArrayList<>();
hands.add(hand1);
hands.add(hand2);
hands.add(hand3);
// 5个人 轮流揭牌5张 i=0就是第一次
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 3; j++) {
//每次揭牌都去获取 cardList的0下标的数据【删除】
Card card = cardList.remove(0);
List<Card> hand = hands.get(j);
hand.add(i,card);//这里使用add 不能是set
/*hands.get(j).add(card);*/
}
}
System.out.println("第1个人的牌："+hand1);
System.out.println("第2个人的牌："+hand2);
System.out.println("第3个人的牌："+hand3);
System.out.println("剩余的牌："+cardList);
}
}
? ? ? ? 运行结果如下:
? ? ? ? 以上就是顺序表的全部内容！?
