当前位置：首页 > news >正文

250217-数据结构

news 2025/2/22 16:34:10

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 顺序表（数组实现）

数据存储在连续的内存空间里；

优点：访问快；

缺点：插入删除效率低；动态扩容成本高（需复制整个数组）

手搓顺序表；

动态扩容
检查索引合法性
在末尾添加元素
在指定位置增加元素
删除元素
- 后面元素的前移来覆盖欲删除元素，达到删除效果（这样数组末尾会多出一个无用元素）（比如从索引 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属性。