数据结构 考研(数据结构考研真题)-考研网
数据结构 考研(数据结构考研真题)-考研网
数据结构 考研,数据结构考研真题
一、数据结构
1.1 常见的数据结构——栈
1.1.1 栈的特点:先进后出(存进去的元素,要在后它后面的元素依次取出后,才能取出该元素)
1.1.2 栈的常用名词:
压栈:就是存元素。把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。
弹栈:就是取元素。把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。
1.1.3 栈的图示:
1.2 常见的数据结构——队列
1.2.1 队列的特点:先进先出(存进去的元素,要在后它前面的元素依次取出后,才能取出该元素)
1.2.2 队列的图示:
1.3 常见的数据结构——数组
1.3.1 数组的特点:查询快,增删慢
1.4 常见的数据结构——链表
1.4.1 链表的特点:查询慢,增删快
1.4.2 链表的结构:链表由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
1.5 常见的数据结构——红黑树
1.5.1 概念: 二叉树是每个结点不超过2的有序树,简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。 二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点,两边被称作“左子树”和“右子树”,红黑树本身就是一颗二叉查找树。
1.5.2 二叉树图
示:
1.5.3 红黑树的约束:
1. 节点可以是红色的或者黑色的
2. 根节点是黑色的
3. 叶子节点(特指空节点)是黑色的
4. 每个红色节点的子节点都是黑色的
5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同
1.5.4 红黑树的特点:查询速度特别快,查找叶子元素最少和最多次数不多于二倍
二、 list集合
2.1 java.util.list接口继承自collection接口,是单列集合的一个重要分支,习惯性地会将实现了list接口的对象称为list集合。
2.2 list接口特点:
1. 它是一个元素存取有序的集合。
2. 它是一个带有索引的集合,通过索引就可以精确的操作集合中的元素(与数组的索引是一个道理)
3. 集合中可以有重复的元素,通过元素的equals方法,来比较是否为重复的元素。
2.3 list接口常用方法:
public void add(int index, e element) : 将指定的元素,添加到该集合中的指定位置上。 public e get(int index) :返回集合中指定位置的元素。
public e remove(int index) : 移除列表中指定位置的元素, 返回的是被移除的元素。 public e set(int index, e element) :用指定元素替换集合中指定位置的元素,返回值的更新前的元素。
三、 list的子类
3.1 java.util.arraylist集合数据存储的结构是数组结构。元素增删慢,查找快,由于日常开发中使用最多的功能为查询数据、遍历数据,所以arraylist是最常用的集合。
3.2 java.util.linkedlist 集合数据存储的结构是链表结构。方便元素添加、删除的集合。
3.2.1 linkedlist常用方法:
public void addfirst(e e) :将指定元素插入此列表的开头。
public void addlast(e e) :将指定元素添加到此列表的结尾。
public e getfirst() :返回此列表的第一个元素。
public e getlast() :返回此列表的最后一个元素。
public e removefirst() :移除并返回此列表的第一个元素。
public e removelast() :移除并返回此列表的最后一个元素。
public e pop() :从此列表所表示的堆栈处弹出一个元素。
public void push(e e) :将元素推入此列表所表示的堆栈。
public boolean isempty() :如果列表不包含元素,则返回true。
四、set接口
4.1 java.util.set接口和java.util.list接口一样,同样继承自collection 接口,它与 collection 接口中的方 法基本一致,并没有对 collection 接口进行功能上的扩充,只是比 collection 接口更加严格了。
4.2 set接口特点:
1、set接口中元素无序
2、set接口中元素不能重复
3、set集合取出元素的方式可以采用迭代器和增强for
4.3 java.util.hashset是set接口的一个实现类,它所存储的元素是不可重复的,并且元素都是无序的(即存取顺序不一致)。java.util.hashset底层的实现其实是一个 java.util.hashmap支持。
4.3.1 hashset是根据对象的哈希值来确定元素在集合中的存储位置,因此具有良好的存取和查找性能。保证元素唯一性的方式依赖于:hashcode与equals方法。
4.3.2 hashset集合存储数据的结构(哈希表):哈希表是由数组+链表+红黑树实现的,如下图所示:
保证hashset集合元素的唯一, 其实就是根据对象的hashcode和equals方法来决定的。如果我们往集合中存放自定义的对象,那么保证其唯一, 就必须复写hashcode和equals方法建立属于当前对象的比较方式。
4.4 hashset存储自定义类型元素:给hashset中存放自定义类型元素时,需要重写对象中的hashcode和equals方法,建立自己的比较方式,才能保证hashset集合中的对象唯一
4.4.1 重写hashcode和equals方法代码实现如下:
4.5 可变参数:如果我们定义一个方法需要接受多个参数,并且多个参数类型一致,我们可以对其简化成如下格式:
修饰符 返回值类型 方法名(参数类型 形参名){ }
用在参数上,称之为可变参数
4.5.1 使用举例:
public static int getsum(int arr) {}
4.5.2 注意事项:如果在方法书写时,这个方法拥有多参数,参数中包含可变参数,可变参数一定要写在参数列表的末尾位置。
五、collections
5.1 java.utils.collections 是集合工具类,用来对集合进行操作。部分方法如下:
public static boolean addall(collection c, t elements) :往集合中添加一些元素。
public static void shuffle(list list) 打乱顺序 :打乱集合顺序。
public static void sort(list list) :将集合中元素按照默认规则排序。
public static void sort(list list,comparator ) :将集合中元素按照指定规则排
序。
数据结构 考研(数据结构考研真题)
未经允许不得转载:考研网 » 数据结构 考研(数据结构考研真题)
赞 (0) 打赏