数据结构-学习笔记(一)
结构程序：（算法）+（数据结构）面向对象的程序=（算法+数据结构）?四种基本结构：集合，线性结构，树形结构，图状结构/网状结构?逻辑结构、物理结构(存储结构)逻辑结构：集合、线性结构、树状结构、网状结构物理结构：循序结构和链式结构?赋值形式：交换赋值，数组赋值，条件赋值算法：有穷性，确定性，可行性，输入，输出?线性表-顺序存储结构顺序表特点：1.逻辑结构与存储结构一致2.访问每个元素的时间相等3.随机存取?一维数组静态存储结构：编译时内存分配空间动态存储结构：什么时候用，什么时候分配?java举例：静态初始化：?int[] a = {1,2,3}动态初始化：?int[] a = new int[3];?for(int i=0;i<3;i++)｛?????a[i] = i+1;}优点：随机读取,时间复杂度为O(1),空间利用率高;缺点：是进行插入和删除操作时比较麻烦,时间复杂度为O(n),同时容量受限制,需要事先确定容量大小,容量过大浪费空间资源,过小不能满足使用要求,会产生溢出问题,虽然可以扩容,但是需要耗时间的;?线性表-链式存储结构用一组任意的存储单元存储线性表物理结构不反映逻辑结构不可以随机存取，但插入和删除方便需要两个域：一个表示数据本身，一个表示数据元素间的先后关联->一个结点结点中表示关联的部分为指针域，内部存放指针或链。n个结点链接成一个链表?优点：插入和删除非常简单,前提条件是知道操作位置,时间复杂度是O(1),但如果不知道操作位置则要定位元素,时间复杂度也是O(n),还有一个很大的优点是没有容量的限制,可以在使用过程中动态的分配内存空间,不用担心溢出的问题;缺点：它不能实现随机读取,同时空间利用率不高.