【蓝桥杯-筑基篇】数据结构基础

﹏ヽ暗。殇╰゛Y 2024-04-20 07:51 75阅读 0赞

> ?系列专栏:[蓝桥杯][Link 1]
> 
> ?个人主页:[个人主页][Link 2]

**目录**

1.ArrayList 动态数组

2.链表LinkedList

3.栈Stack

4.队列Queue

5.集合HashSet——去重

6.HashMap——存放键值对

7.TreeSet - 带排序的集合

--------------------

### 1.ArrayList 动态数组 ###

ArrayList 是 Java 中的一个类，它实现了 List 接口，是一个动态数组。它可以自动扩容、支持泛型、支持随机访问等特性。

动态数组是一种可以自动调整大小的数组。当数组满了之后，动态数组会自动扩容，以容纳更多的元素。相比于普通的数组，动态数组的容量是可以动态调整的，因此更加灵活和方便。

ArrayList 的常用方法包括：

*  add(E e)：向列表的末尾添加一个元素。
 *  add(int index, E element)：在列表的指定位置插入指定元素。
 *  get(int index)：返回列表中指定位置的元素。
 *  set(int index, E element)：用指定元素替换列表中指定位置的元素。
 *  remove(int index)：删除列表中指定位置的元素。
 *  size()：返回列表中的元素数。

import java.util.ArrayList;
    
    public class ArrayListExample {
        public static void main(String[] args) {
            ArrayList<String> list = new ArrayList<String>();
            list.add("apple");
            list.add("banana");
            list.add("orange");
            System.out.println("List size: " + list.size()); // 输出：List size: 3
            System.out.println("Element at index 1: " + list.get(1)); // 输出：Element at index 1: banana
            list.remove(1);
            System.out.println("List size after removing element at index 1: " + list.size()); // 输出：List size after removing element at index 1: 2
        }
    }

### 2.链表LinkedList ###

Java中的链表是一种数据结构，它由节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表。

在Java中，可以使用Java集合框架提供的LinkedList类来实现链表。LinkedList类实现了List接口和Deque接口，因此它既可以作为列表使用，也可以作为队列或栈使用。LinkedList类内部实现了链表的操作，例如添加、删除、插入和遍历等。

使用LinkedList类时，需要注意以下几点：

1.  LinkedList类是线程不安全的，如果需要在多线程环境下使用，可以使用并发包中的ConcurrentLinkedDeque类。
2.  操作LinkedList时，需要考虑链表的头和尾部。在头部添加元素可以使用addFirst()方法，在尾部添加元素可以使用addLast()方法。
3.  遍历LinkedList时，可以使用Iterator或foreach循环。在使用Iterator时，需要在循环体中调用next()方法获取下一个元素。
4.  LinkedList类还提供了一些其他的方法，例如getFirst()、getLast()、removeFirst()和removeLast()等，可以根据实际需求选择使用。

下面是一个简单的示例代码，演示如何使用LinkedList类实现链表：

import java.util.LinkedList;
    
    public class LinkedListDemo {
        public static void main(String[] args) {
            LinkedList<String> list = new LinkedList<>();
            list.add("hello");
            list.add("world");
            list.add("java");
            System.out.println(list);
    
            list.addFirst("first");
            list.addLast("last");
            System.out.println(list);
    
            list.removeFirst();
            list.removeLast();
            System.out.println(list);
    
            for (String s : list) {
                System.out.println(s);
            }
        }
    }

输出结果：

[hello, world, java]
    [first, hello, world, java, last]
    [hello, world, java]
    hello
    world
    java

**例题：约瑟夫环模拟**

import java.util.*;
    
    public class LinkedListDemo {
    
        public static void main(String[] args) {
            int n = 7; // 约瑟夫环总人数
            int m = 3; // 数到第几个人出圈
            LinkedList<Integer> list = new LinkedList<>();
            for (int i = 1; i <= n; i++) {
                list.add(i);
            }
            System.out.println("初始链表：" + list);
            int count = 0;
            int index = 0;
            while (list.size() > 1) {
                int num = list.get(index);
                count++;
                if (count == m) {
                    list.remove(index);
                    System.out.println("出圈的人：" + num);
                    count = 0;
                } else {
                    index++;
                }
                if (index >= list.size()) {
                    index = 0;
                }
            }
            System.out.println("剩余的人：" + list.get(0));
        }
    
    }

运行结果：

初始链表：[1, 2, 3, 4, 5, 6, 7]
    出圈的人：3
    出圈的人：6
    出圈的人：2
    出圈的人：7
    出圈的人：5
    出圈的人：1
    剩余的人：4

说明：

1.  首先创建一个LinkedList对象，用来存放约瑟夫环中的人；
2.  循环添加n个人到链表中；
3.  如果链表中还有人，则继续循环；
4.  每次数到第m个人，就将该人从链表中移除，并输出该人的编号；
5.  如果链表中的当前位置已经是最后一个元素，则将当前位置重置为0；
6.  最终剩下的一个人即为约瑟夫环的胜利者。

### 3.栈Stack ###

栈（Stack）是一种线性数据结构，它支持在一端进行插入和删除操作，这一端被称为栈顶。栈遵循先进后出（Last In First Out，LIFO）的原则，即最后进栈的元素最先出栈，而最先入栈的元素最后出栈。

1.  push(Object element): 将元素压入栈顶
2.  pop(): 弹出栈顶元素并返回，如果栈为空则抛出异常
3.  peek(): 返回栈顶元素但不弹出，如果栈为空则抛出异常
4.  empty(): 判断栈是否为空
5.  search(Object element): 查找元素在栈中的位置，如果不存在则返回-1

public static void main(String[] args) {
            Stack<String> stack = new Stack<>();
            stack.push("Java");
            stack.push("Python");
            stack.push("C++");
            stack.push("JavaScript");
            System.out.println("栈: " + stack);
            System.out.println("栈顶元素: " + stack.peek());
            stack.pop();
            System.out.println("弹出元素后的栈: " + stack);
        }

栈: [Java, Python, C++, JavaScript]
    栈顶元素: JavaScript
    弹出元素后的栈: [Java, Python, C++]

### 4.队列Queue ###

Java中的Queue接口是一个队列数据结构的抽象表示。它定义了以下方法：

1.  add(E e): 将元素e添加到队列末尾，如果队列已满则抛出异常。
2.  offer(E e): 将元素e添加到队列末尾，如果队列已满则返回false。
3.  remove(): 返回队列头部元素并将其从队列中删除，如果队列为空则抛出异常。
4.  poll(): 返回队列头部元素并将其从队列中删除，如果队列为空则返回null。
5.  element(): 返回队列头部元素但不删除，如果队列为空则抛出异常。
6.  peek(): 返回队列头部元素但不删除，如果队列为空则返回null。

此外，Queue接口还继承了Collection接口中的一些方法，如size()、isEmpty()、contains(Object o)等。

public static void main(String[] args) {
            Queue<String> queue = new LinkedList<>();
    
            // 向队列中添加元素
            queue.add("John");
            queue.add("Brad");
            queue.add("Angelina");
            queue.add("Julia");
    
            System.out.println("队列中的元素: " + queue);
           
    
            // 从队列中删除元素
            String name = queue.remove();
            System.out.println("删除的元素: " + name);
    
            System.out.println("删除元素后队列中的元素: " + queue);
    
            // 访问队列中的元素
            String element = queue.peek();
            System.out.println("队列头部的元素: " + element);
    
            // 队列的大小
            int size = queue.size();
            System.out.println("队列的大小: " + size);
        }

队列中的元素: [John, Brad, Angelina, Julia]
    删除的元素: John
    删除元素后队列中的元素: [Brad, Angelina, Julia]
    队列头部的元素: Brad
    队列的大小: 3

### 5.集合HashSet——去重 ###

HashSet是Java集合框架中的一种实现，它基于哈希表实现，能够快速地查找、插入和删除元素，其常用方法如下：

1.  add(Object o)：将指定元素添加到集合中，**如果该元素已经存在于集合中，则不会再次添加。**
2.  remove(Object o)：从集合中移除指定元素。
3.  size()：返回集合中元素的数量。
4.  clear()：清空集合中的所有元素。
5.  contains(Object o)：判断集合中是否包含指定元素。
6.  isEmpty()：判断集合是否为空。
7.  toArray()：将集合转化为数组。
8.  iterator()：返回集合的迭代器，用于遍历集合中的所有元素。

除了以上常用方法外，HashSet还有一些其他方法，如：

1.  hashCode()：返回该集合的哈希码值。
2.  equals(Object o)：判断该集合是否与指定对象相等。
3.  retainAll(Collection c)：从集合中保留指定集合中包含的元素，其余元素将被移除。
4.  removeAll(Collection c)：从集合中移除指定集合中包含的元素。
5.  containsAll(Collection c)：判断集合是否包含指定集合中的所有元素。
6.  addAll(Collection c)：将指定集合中的所有元素添加到该集合中。

总之，HashSet提供了丰富的方法来操作集合中的元素，具有高效、快速的特点。

public static void main(String[] args) {
            HashSet<String> set = new HashSet<String>();
            set.add("element1");
            set.add("element2");
            set.add("element3");
            set.add("element1");
            System.out.println(set);
    
            set.remove("element2");
            System.out.println(set);
    
            System.out.println("元素1是否在集合中？ " + set.contains("element1"));
    
            System.out.println("集合大小: " + set.size());
    
            set.clear();
            System.out.println(set);
    
            System.out.println("集合是否为空？ " + set.isEmpty());
        }

[element1, element2, element3]
    [element1, element3]
    元素1是否在集合中？ true
    集合大小: 2
    []
    集合是否为空？ true

### 6.HashMap——存放键值对 ###

HashMap 是 Java 中的一个集合类，它用来存储键值对。它实现了 Map 接口，可以存储不同类型的键和值，并且允许 null 值。在 HashMap 中，键是唯一的，值可以重复。

HashMap 中最常用的方法包括：

*  put(key, value)：将键值对添加到 HashMap 中。
 *  get(key)：获取指定键对应的值。
 *  remove(key)：删除指定键对应的键值对。
 *  containsKey(key)：判断 HashMap 是否包含指定的键。
 *  keySet()：返回 HashMap 中所有键组成的 Set 集合。

public static void main(String[] args) {
            // 创建一个名为capitalCities的HashMap对象
            HashMap<String, String> capitalCities = new HashMap<String, String>();
    
            // 添加键和值（国家，城市）
            capitalCities.put("England", "London");
            capitalCities.put("Germany", "Berlin");
            capitalCities.put("Norway", "Oslo");
            capitalCities.put("USA", "Washington DC");
    
            // 通过使用键访问值
            System.out.println("英格兰的首都是 " + capitalCities.get("England"));
    
            // 删除一个键和值
            capitalCities.remove("Norway");
    
            // 打印键
            System.out.println("键: " + capitalCities.keySet());
    
            // 检查一个键是否在HashMap中
            System.out.println("capitalCities是否包含Norway作为键？ " + capitalCities.containsKey("Norway"));
        }

英格兰的首都是 London
    键: [USA, England, Germany]
    capitalCities是否包含Norway作为键？ false

**getOrDefault 是 Map 接口提供的一个方法，用于获取 Map 中指定键对应的值，如果该键不存在，则返回一个默认值：**

getOrDefault(Object key, V defaultValue);

其中，key 表示要获取的键，defaultValue 表示默认值。如果 Map 中存在 key，则返回该 key 对应的值；否则，返回 defaultValue。

**示例：**

Map<String, Integer> map = new HashMap<>();
    map.put("apple", 1);
    map.put("banana", 2);
    map.put("orange", 3);
    
    // 获取存在的键对应的值
    int value1 = map.getOrDefault("apple", 0); // 返回 1
    int value2 = map.getOrDefault("banana", 0); // 返回 2
    
    // 获取不存在的键对应的默认值
    int value3 = map.getOrDefault("pear", 0); // 返回 0

注意：getOrDefault 方法只是获取 Map 中指定键对应的值，不会修改 Map 中的数据。如果需要修改 Map 中的数据，请使用 put 方法。

### 7.TreeSet - 带排序的集合 ###

TreeSet 是 Java 中的一个集合类，它实现了 SortedSet 接口，可以存储元素，并按照元素的自然顺序或指定的比较器顺序进行排序。

TreeSet 的主要方法包括：

1.  add(E e)：将指定的元素添加到集合中。
2.  clear()：从集合中移除所有元素。
3.  contains(Object o)：判断集合是否包含指定的元素。
4.  first()：返回集合中的第一个元素。
5.  last()：返回集合中的最后一个元素。
6.  remove(Object o)：从集合中移除指定的元素。
7.  size()：返回集合中的元素个数。
8.  toArray()：将集合转换为数组。

使用 TreeSet 时，需要注意以下几点：

1.  TreeSet 中的元素必须实现 Comparable 接口，或者在创建 TreeSet 时提供一个 Comparator 比较器。
2.  TreeSet 中的元素必须是可比较的，否则将抛出 ClassCastException 异常。
3.  TreeSet 中的元素不允许为 null 值，否则将抛出 NullPointerException 异常。
4.  TreeSet 中的元素是按照元素的自然顺序或指定的比较器顺序进行排序的。

public static void main(String[] args) {
    		    TreeSet<String> treeSet = new TreeSet<String>();
    		    treeSet.add("apple");
    		    treeSet.add("orange");
    		    treeSet.add("banana");
    		    treeSet.add("cool");
    		    treeSet.add("dodo");
    		    
    		    System.out.println(treeSet);
    		  }

[apple, banana, cool, dodo, orange]

[Link 1]: https://blog.csdn.net/javascript_tsj/category_12167433.html
[Link 2]: https://blog.csdn.net/Javascript_tsj?type=blog