250217-数据结构
1. 定义
数据结构是数据的存储结构,即数据是按某些结构来存储的,比如线性结构,比如树状结构等。
2. 学习意义
数据结构是服务于算法的,为了实现算法的高效计算,所以将数据按特定结构存储。比如使用快速插入或删除的算法时,使用链表这种数据结构算法会更高效。
3.分类
判定某种数据结构的优劣是根据大O时间复杂度来判断的。
T(n)表示代码执行的时间; n表示数据规模的大小; f(n) 表示程序执行完毕后执行全部计算次数的总和,因为这是一个公式, 所以用f(n)来表示。公式中的O,表示代码的执行时间T(n)与f(n)表达式成正比。
复杂度分析法则
1)单段代码看高频:比如循环。
2)多段代码取最大:比如一段代码中有单循环和多重循环,那么取多重循环的复杂度。
3)嵌套代码求乘积:比如递归、多重循环等
4)多个规模求加法:比如方法有两个参数控制两个循环的次数,那么这时就取二者复杂度相加。
时间复杂度分析
- 只关注循环执行次数最多的一段代码
- 加法法则:总复杂度等于量级最大的那段代码的复杂度
- 乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
复杂度分析的4个概念
1.最坏情况时间复杂度:代码在最坏情况下执行的时间复杂度。
2.最好情况时间复杂度:代码在最理想情况下执行的时间复杂度。
3.平均时间复杂度:代码在所有情况下执行的次数的加权平均值。
4.均摊时间复杂度:在代码执行的所有复杂度情况中绝大部分是低级别的复杂度,个别情况是高级别复杂度且发生具有时序关系时,可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。
3.1 线性结构
3.1.1 顺序表(数组实现)
数据存储在连续的内存空间里;
优点:访问快;
缺点:插入删除效率低;动态扩容成本高(需复制整个数组)
使用场景:
-
元素随机访问频繁的场景
- 数组型数据存储:如学生成绩管理系统中存储学生的成绩,每个学生的成绩可以看作是顺序表中的一个元素,通过学生的编号作为索引可以快速访问到某个学生的成绩,方便进行成绩的查询、统计等操作。
- 数据可视化中的数据存储:在图形绘制、图表展示等数据可视化场景中,经常需要存储大量的数值数据,如折线图的横坐标和纵坐标数据、柱状图的高度数据等,使用顺序表可以快速定位到每个数据点,便于进行图形的绘制和更新。
-
元素数量相对稳定的场景
- 学校课程表管理:学校的课程安排在一个学期内通常是相对稳定的,课程的数量和顺序不会频繁变动。可以将课程信息存储在顺序表中,每个元素代表一门课程,包括课程名称、上课时间、上课地点等信息,便于按照课程的顺序进行课程表的展示和查询。
- 企业员工基本信息管理:企业员工的基本信息,如员工编号、姓名、职位等,在一段时间内相对固定。使用顺序表存储这些信息,可以方便地根据员工编号进行快速查询和管理,而且由于员工数量不会频繁变动,不会导致顺序表频繁进行插入和删除操作。
-
需要顺序存储和遍历数据的场景
- 文本处理中的字符存储:在文本编辑器、编译器等文本处理软件中,字符通常是按照顺序依次存储的。可以将文本中的字符存储在顺序表中,方便进行字符的遍历、查找、替换等操作,例如查找某个特定的单词、替换文本中的某个字符等。
- 简单队列的实现:队列是一种先进先出的数据结构,顺序表可以用来实现简单的队列。在一些场景中,如任务调度系统中的任务队列、消息系统中的消息队列等,任务或消息按照顺序依次进入队列,使用顺序表可以方便地进行入队和出队操作,虽然在中间插入和删除元素效率较低,但对于只在队头和队尾进行操作的队列来说,顺序表是一种简单有效的实现方式。
-
作为其他数据结构的底层实现
- 栈的实现:栈是一种后进先出的数据结构,通过顺序表可以很容易地实现栈的操作。可以将顺序表的一端作为栈顶,另一端作为栈底,通过在栈顶进行元素的插入和删除操作来实现栈的功能,如函数调用栈的实现,就可以基于顺序表来完成。
- 堆的实现:堆是一种特殊的数据结构,常用于实现优先队列等。堆通常可以使用顺序表来存储元素,利用顺序表的随机访问特性,可以快速地定位到堆中的每个节点,方便进行堆的插入、删除和调整操作。
-
数据排序和搜索的场景
- 小型数据集的排序:对于一些规模较小的数据集合,使用顺序表存储数据并进行排序是一种简单有效的方法。由于顺序表支持随机访问,许多排序算法(如冒泡排序、插入排序、选择排序等)可以直接在顺序表上进行操作,而且在数据量较小的情况下,这些排序算法的效率通常可以满足需求。
- 有序数据的二分查找:当顺序表中的数据是有序的时,可以使用二分查找算法进行快速搜索。二分查找算法的时间复杂度为 O (log n),能够在较短的时间内找到目标元素,例如在一个按照学号排序的学生信息顺序表中,使用二分查找可以快速找到指定学号的学生信息。
手搓顺序表;
- 动态扩容
- 检查索引合法性
- 在末尾添加元素
- 在指定位置增加元素
- 删除元素
- 后面元素的前移来覆盖欲删除元素,达到删除效果(这样数组末尾会多出一个无用元素)(比如从索引 2 开始,把后面的元素依次向前移动一位。也就是将索引 3 的元素(值为 4)移到索引 2 的位置,将索引 4 的元素(值为 5)移到索引 3 的位置。其实是索引 4 的元素被复制到了索引 3 的位置,而索引 4 的位置仍然保留着之前的值,但这个值现在已经没有实际意义,成了 “无用” 元素。)
- 建立一个新数组,把保留下来的元素复制过去
- 替换指定位置元素
- 查询元素
- 获取元素数量
- 打印数组所有元素
下面实例中属性都被封装起来了,方法里的功能性方法比如增加元素、查看元素是公开的,但是检查是否合法、动态扩容的方法也都被封装起来了。
public class ArraysStructure
{
public static void main(String[] args)
{
ArraysDemo arr=new ArraysDemo();
int[] a={1,2,3,4,5,6,7,8,9,10,11};
for(int i:a)
{
arr.add(i);
}
System.out.println("数组指定位置元素"+arr.get(3));
System.out.println("数组的元素个数"+arr.size());
System.out.println("数组的容量"+arr.getCapacity());
arr.insert(3,100);
arr.replace(4,200);
System.out.println("数组指定位置元素"+arr.get(3));
System.out.print("删元素之前:");
arr.printArray();
arr.deleteElement(3);
System.out.print("删元素之后:");
arr.printArray();
System.out.println("数组的元素个数"+arr.size());
System.out.println("数组的容量"+arr.getCapacity());
}
}
//总的来说,下面定义的类实现了动态数组、检查合法、添加元素、查询元素、获取元素数量三个功能
class ArraysDemo
{
private static final int DEFAULT_CAPACITY=10; //初始数组容量;
private int[] arr; //声明数组变量
private int size; //当前元素数量
public ArraysDemo() //构造函数,初始化数组
{
arr=new int[DEFAULT_CAPACITY];
size=0;
}
//确保数组容量足够
private void ensureCapacity(int minCapacity)
{
if(minCapacity>arr.length)
{
//扩容为原来的1.5倍
int newCapacity=DEFAULT_CAPACITY+(DEFAULT_CAPACITY>>1);
int[] newArray=new int[newCapacity];
System.arraycopy(arr,0,newArray,0,size); //旧数组数据复制到新数组
arr=newArray;
System.out.println("扩容为原来的1.5倍");
}
else
{
// System.out.println("数组剩余容量为"+(arr.length-minCapacity));
}
}
public void add(int num) //添加元素
{
//首先检查是否需要扩容
ensureCapacity(size+1);
arr[size++]=num;
}
public int get(int index) //获取指定位置的元素
{
checkIndex(index); //检查索引是否合法
return arr[index];
}
public void checkIndex(int index) //检查索引是否合法
{
if(index<0 || index>=size)
{
throw new IndexOutOfBoundsException("index"+index+",size"+size);
}
}
public int size() //获取元素数量
{
return size;
}
public int getCapacity() //获取数组容量
{
return arr.length;
}
public void replace(int a,int b) //指定索引位置替换元素
{
checkIndex(a);
arr[a]=b;
}
public void insert(int a,int b) //指定索引位置插入元素
{
if(size>0)
{
ensureCapacity(size+1);
checkIndex(a);
for(int i=size;i>a;i--)
{
arr[i]=arr[i-1];
}
arr[a]=b;
size++;
}
else
{
arr[a]=b;
}
}
public void printArray() //打印数组元素
{
for(int i:arr)
{
System.out.print(i+"");
}
}
// public void deleteElement(int index) //元素前移覆盖方式
// {
// checkIndex(index);
// for (int i = index; i < size - 1; i++)
// {
// arr[i] = arr[i + 1];
// }
// size--;
// }
public void deleteElement(int index) //新建数组删除方式
{
checkIndex(index);
int[] newArr=new int[arr.length-1];
for(int i=0,j=0;i<size;i++)
{
if(i!=index)
{
newArr[j++]=arr[i];
}
}
size--;
arr=newArr;
}
}
/*输出
扩容为原来的1.5倍
数组指定位置元素4
数组的元素个数11
数组的容量15
数组指定位置元素100
删元素之前:123100200567891011000
删元素之后:123200567891011000
数组的元素个数11
数组的容量14*/
该例还有一个细节,以int[] arr=new int[n]创建的arr对象可以arr.length查看数组的总容量,然而若以ArraysDemo arr=new ArraysDemo()创建的arr对象,查看arr.length就会报错,说该类未声明length属性。
3.1.2 链表
优点:增删方便。
缺点:查询不便。
使用场景:
-
数据的动态插入和删除
- 操作系统进程调度:操作系统需要动态地创建、销毁和调度进程。链表可以方便地将新进程插入到就绪队列或阻塞队列中,也能快速地将完成的进程从队列中删除,而不需要像数组那样移动大量元素。
- 文本编辑器:在文本编辑器中,当用户在文本中间插入或删除字符时,使用链表可以高效地处理这些操作。每个字符可以看作是链表中的一个节点,插入或删除字符只需要修改相应节点的指针,而不需要移动大量的文本内容。
-
实现栈和队列
- 函数调用栈:在程序执行过程中,函数的调用和返回是通过栈来实现的。链表可以用来实现栈的数据结构,函数调用时将相关信息(如函数参数、返回地址等)压入栈顶,函数返回时从栈顶弹出这些信息。
- 消息队列:在消息系统中,消息通常会被放入队列中等待处理。链表可以作为消息队列的底层实现,新消息可以在队列尾部插入,处理消息时从队列头部取出,符合先进先出的原则。
-
图的邻接表表示
- 社交网络分析:在社交网络中,用户之间的关系可以用图来表示。使用链表可以方便地存储和操作这些关系。例如,可以为每个用户创建一个链表,链表中的节点表示该用户的邻居节点,这样可以高效地查找某个用户的所有邻居,以及添加或删除用户之间的关系。
- 导航系统:在导航系统中,地图上的地点和道路可以用图来表示。通过链表实现的邻接表可以存储图的结构信息,方便进行路径搜索、最短路径计算等操作。
-
内存管理
- 动态内存分配:在操作系统的内存管理中,链表可以用来管理空闲内存块。当程序申请内存时,操作系统可以从空闲内存块链表中找到合适的内存块分配给程序;当程序释放内存时,操作系统将释放的内存块插入到空闲内存块链表中。
- 垃圾回收:在一些编程语言的垃圾回收机制中,链表可以用来记录已经分配的内存对象。垃圾回收器可以遍历链表,标记和回收不再被使用的内存对象,以释放内存空间。
-
多项式表示
- 计算机代数系统:在计算机代数系统中,需要对多项式进行各种运算,如加法、乘法、求导等。用链表表示多项式,每个节点可以存储多项式的一项的系数和指数,方便进行多项式的运算和操作。
- 信号处理:在信号处理中,有时需要对信号进行多项式拟合或滤波等操作。使用链表表示多项式可以方便地对多项式进行操作和计算,从而实现信号处理的功能。
手搓链表如下:
- 末尾添加数据
- 修改指定位置数据
- 查找数据
- 删除数据
- 打印链表
- 判断链表是否为空
public class LinkedListDemo
{
public static void main(String[] args)
{
MyLinkedList<Integer> a=new MyLinkedList<>();
a.add(1);
System.out.println("打印该链表:"+a.toString());
a.add(2);
System.out.println("打印该链表:"+a.toString());
System.out.println("查找元素:"+a.get(1));
a.replace(1,299);
System.out.println("打印该链表:"+a.toString());
a.remove(1);
System.out.println("打印该链表:"+a.toString());
}
}
//定义节点类
class Node<T>
{
T data; //节点存储的数据
Node<T> next; //指向下一节点的引用
public Node(T data)
{
this.data=data;
this.next=null;
}
}
//定义链表类
class MyLinkedList<T>
{
private Node<T> head; //定义头节点
Node<T> tail; //定义尾节点
private int size; //定义链表节点个数
public MyLinkedList()
{
this.head=null;
this.tail=null;
this.size=0;
}
public int size() //获取链表的大小
{
return size;
}
public boolean isEmpty() //判断链表是否为空
{
return size==0;
}
public void add(T data) //在链表末尾添加元素
{
Node<T> newNode=new Node<>(data);
if(isEmpty()) //链表是否为空
{
head=newNode;
tail=newNode;
}
else
{
tail.next=newNode;
tail=newNode;
}
size++;
}
public T get(int index) //查找指定索引位置的数据
{
if(size<0 || index>=size)//检查索引越界
{
throw new IndexOutOfBoundsException("index"+index+",size"+size);
}
Node<T> current=head;
for(int i=0;i<index;i++)
{
current=current.next;
}
return current.data;
}
private void checkIndex(int index)//检查索引越界
{
if(size<0 || index>=size)
{
throw new IndexOutOfBoundsException("index"+index+",size"+size);
}
}
public T remove(int index) //删除节点
{
checkIndex(index);
T removeData;
if(index==0) //是否删除头节点;
{
removeData=head.data;
head=head.next;
if(head==null) //是否为空链表
{
tail=null;
}
}
else //删除中间节点
{
Node<T> previus=head;
for(int i=0;i<index-1;i++)
{
previus=previus.next;
}
Node<T> current=previus.next;
removeData=current.data;
previus.next=current.next;
if(current==tail) //把current.next=null作为判断语句同样成立。
{
tail=previus;
}
}
size--;
return removeData;
}
// public void replace(int index,T data)//替换指定索引的数据(更麻烦的替换方式:使用替换节
//点的方式)
// {
// checkIndex(index);
// Node<T> newNode=new Node<>();
// newNode.data=data;
// if(index==0)
// {
// newNode.next=head.next;
// head=newNode;
// }
// else
// {
// Node<T> previous=head;
// for(int i=0;i<index-1;i++)
// {
// previus=previus.next;
// }
// Node<T> current=previus.next;
// previus.next=newNode;
// if(current==tail)
// {
// tail=newNode;
// }
// else
// {
// newNode.next=current.next;
// }
// }
// }
public void replace(int index,T data)//替换指定索引的数据
{
Node<T> current=head;
for(int i=0;i<index;i++)
{
current=current.next;
}
current.data=data;
}
@Override
public String toString() //打印链表
{
StringBuilder result=new StringBuilder();
result.append("[");
Node<T> current=head;
while(current!=null)
{
result.append(current.data);
if(current.next!=null)
{
result.append(", ");
}
current=current.next;
}
result.append("]");
return result.toString();
}
}
上述例子中,删除节点这块的逻辑是:
- 删除头节点(考虑该链表是否只有一个节点);
- 删除非头节点(考虑该节点是否是最后一个节点);
3.1.3 栈
使用数组实现的栈;
栈的操作一般是出栈、入栈(仅限于栈顶)、查询栈顶元素、查询是否为空,不包括查找指定位置元素、替换指定位置元素、在指定位置增加元素,因为这不符合栈的设计初衷。
优点:增删方便(出入栈,不论多少元素,O(1)复杂度);
缺点:栈顶外的查改增不便。
使用场景:
计算机系统层面
1. 函数调用栈
- 原理:在程序执行过程中,当调用一个函数时,系统会将当前的执行上下文(包括局部变量、返回地址等信息)压入栈中。当函数执行完毕后,系统从栈中弹出这些信息,恢复之前的执行状态,继续执行后续代码。
- 示例:在一个包含多个嵌套函数调用的程序中,比如函数
A
调用函数B
,函数B
又调用函数C
。当调用C
时,A
和B
的执行上下文会依次压入栈中;当C
执行完返回B
时,C
的上下文出栈;B
执行完返回A
时,B
的上下文出栈。
2. 中断处理
- 原理:当计算机系统接收到中断信号时,需要暂停当前正在执行的程序,转去处理中断事件。此时,系统会将当前程序的执行状态(如寄存器的值等)压入栈中,处理完中断后,再从栈中弹出这些信息,恢复原程序的执行。
- 示例:在操作系统中,当硬件设备(如鼠标、键盘)发出中断请求时,系统会将当前进程的状态保存到栈中,然后执行相应的中断服务程序,处理完后恢复原进程的状态继续执行。
编译器与解释器方面
1. 表达式求值
- 原理:栈可用于处理各种表达式,如中缀表达式转后缀表达式(逆波兰表达式)以及后缀表达式的求值。在处理过程中,运算符和操作数按照特定规则入栈和出栈,从而完成表达式的计算。
- 示例:对于中缀表达式
3 + 4 * 2
,转换为后缀表达式3 4 2 * +
后,使用栈进行求值。扫描后缀表达式,遇到操作数入栈,遇到运算符则从栈中弹出相应操作数进行计算,并将结果入栈,最终栈顶元素即为表达式的值。
2. 语法分析
- 原理:在编译器的语法分析阶段,栈可以用来检查代码的语法结构是否正确,例如检查括号的匹配情况。在扫描代码时,遇到左括号入栈,遇到右括号则从栈中弹出一个左括号进行匹配。
- 示例:对于代码
{ (a + b) * [c - d] }
,扫描过程中,左括号{
、(
、[
依次入栈,遇到右括号]
、)
、}
时,分别与栈顶的左括号进行匹配,若匹配成功则弹出栈顶元素,若不匹配则说明语法错误。
算法与数据处理领域
1. 回溯算法
- 原理:回溯算法通过尝试所有可能的解决方案来解决问题。在搜索过程中,栈可以用来记录搜索路径,当搜索到某个节点发现无法继续前进时,通过出栈操作回溯到上一个节点,继续尝试其他路径。
- 示例:在迷宫寻路问题中,从起点开始,每走一步将当前位置压入栈中,当遇到死路时,从栈中弹出当前位置,回溯到上一个位置继续探索其他方向。
2. 深度优先搜索(DFS)
- 原理:深度优先搜索是一种用于遍历或搜索树或图的算法。在搜索过程中,使用栈来记录待访问的节点,优先沿着一条路径尽可能深地访问节点,直到无法继续,然后回溯。
- 示例:在遍历一个图时,从起始节点开始,将其入栈,然后访问栈顶节点的未访问邻接节点并将其入栈,重复此过程,直到栈为空。
实际应用程序中
1. 浏览器的前进后退功能
- 原理:浏览器使用两个栈来实现前进和后退功能。当用户访问一个新页面时,将该页面的 URL 压入后退栈;当用户点击后退按钮时,将后退栈的栈顶元素弹出并压入前进栈;当用户点击前进按钮时,将前进栈的栈顶元素弹出并压入后退栈。
- 示例:用户依次访问页面 A、B、C,此时后退栈为
[A, B, C]
,前进栈为空。用户点击后退按钮,后退栈弹出C
并将其压入前进栈,此时后退栈为[A, B]
,前进栈为[C]
。
2. 文本编辑器的撤销和重做功能
- 原理:与浏览器的前进后退功能类似,文本编辑器使用两个栈来实现撤销和重做操作。每次用户进行一次操作(如输入、删除等),将该操作记录压入撤销栈;当用户执行撤销操作时,将撤销栈的栈顶元素弹出并压入重做栈;当用户执行重做操作时,将重做栈的栈顶元素弹出并压入撤销栈。
手搓数组实现的栈
实现功能:
- 入栈操作(动态扩容)
- 出栈操作(防止内存泄漏)
- 返回栈顶元素
- 获取栈元素数量
- 检查栈是否为空
public class StackDemo
{
public static void main(String[] args)
{
MyStack<String> myStack=new MyStack<>();
// myStack.pop();
myStack.push("你好");
System.out.println(myStack.getSize());
myStack.push("早安");
System.out.println(myStack.getSize());
}
}
class MyStack<T>
{
private static final int STACK_CAPACITY=3;
private T[] myStack;
int top; //栈顶索引
// int size;
@SuppressWarnings("unchecked")
public MyStack()
{
myStack=(T[]) new Object[STACK_CAPACITY];
// myStack[++top]=data;
top=-1;
}
public void push(T data) //入栈
{
if(top==myStack.length-1)
{
// throw new IndexOutOfBoundsException("栈已满,无可进空间");
resize(2*STACK_CAPACITY);
}
myStack[++top]=data;
}
public T pop() //出栈
{
if(top==-1)
{
throw new IndexOutOfBoundsException("栈已空,无可出元素");
}
T peek=myStack[top];
myStack[top--]=null;
if(top>0 && top==myStack.length/4)
{
resize(myStack.length/2);
}
return peek;
}
public int getSize() //获取栈元素数量
{
return top+1;
}
public T getElement() //获取栈顶元素
{
if(top==-1)
{
throw new IndexOutOfBoundsException("栈已空,无可出元素");
}
return myStack[top];
}
@SuppressWarnings("unchecked") //注解抑制在创建泛型数组时的java警告
//也可以使用ArrayList,支持泛型类,同时也是java的动态数组
public void resize(int capacity)
{
if(capacity>STACK_CAPACITY)
{
T[] newStack=(T[]) new Object[capacity];
for(int i=0;i<top;i++)
{
newStack[i]=myStack[i];
}
myStack=newStack;
}
else
{
System.out.println("输入大小不合法:小于原来容量");
}
}
}
3.1.4 队列
3.2 树状结构
文中关于时间和空间复杂度的内容引自该文,原文链接:https://blog.csdn.net/ityqing/article/details/82838524。