zenm自己做网站,装修的app哪个最好,设计类网站模板,linux做网站教程注意#xff1a;该文章摘抄之百度#xff0c;仅当做学习笔记供小白使用#xff0c;若侵权请联系删除#xff01; 什么是数据结构#xff1f; 数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 结构包括逻辑结构和物… 注意该文章摘抄之百度仅当做学习笔记供小白使用若侵权请联系删除 什么是数据结构 数据结构是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 结构包括逻辑结构和物理结构。 数据的逻辑结构包括4种 (1)集合数据元素之间除了有相同的数据类型再没有其他的关系 (2)线性结构数据元素之间是一对一的关系 —— 线性表、栈、队列 (3)树形结构数据元素之间是一对多的关系 (4)图状结构数据元素之间是多对多的关系。 物理结构包括顺序存储结构和链式存储结构。 解释一下顺序存储与链式存储 顺序存储结构是用一段连续的存储空间来存储数据元素可以进行随机访问访问效率较高。 链式存储结构是用任意的存储空间来存储数据元素不可以进行随机访问访问效率较低。 头指针和头结点的区别 头指针是指向第一个节点存储位置的指针具有标识作用头指针是链表的必要元素无论链表是否为空头指针都存在。 头结点是放在第一个元素节点之前便于在第一个元素节点之前进行插入和删除的操作 头结点不是链表的必须元素可有可无头结点的数据域也可以不存储任何信息。 线性结构的特点 (1)集合中必存在唯一的一个第一个元素 (2)集合中必存在唯一的一个最后的元素 (3)除最后元素之外其它数据元素均有唯一的后继 (4)除第一元素之外其它数据元素均有唯一的前驱。 数组和链表的区别 从逻辑结构来看数组的存储长度是固定的它不能适应数据动态增减的情况。 链表能够动态分配存储空间以适应数据动态增减的情况并且易于进行插入和删除操作。 从访问方式来看数组在内存中是一片连续的存储空间可以通过数组下标对数组进行随机访问访问效率较高。 链表是链式存储结构存储空间不是必须连续的可以是任意的访问必须从前往后依次进行访问效率较数组来说比较低。 如果从第i个位置插入多个元素对于数组来说每一次插入都需要往后移动元素每一次的时间复杂度都是O(n) 而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)其余的插入和删除操作时间复杂度均为O(1)提高了插入和删除的效率。 单链表结构和顺序存储结构的区别 当进行插入和删除操作时顺序存储结构每次都需要移动元素总的时间复杂度为O(n) 而链式存储结构确定i位置的指针后其时间复杂度仅为O(1)。 由于顺序存储结构需要进行预分配存储空间所以容易造成空间浪费或者溢出。 链式存储结构不需要预分配存储空间元素个数不受限制。 栈和队列的区别 队列是允许在一段进行插入另一端进行删除的线性表对于进入队列的元素按“先进先出”的规则处理在表头进行删除在表尾进行插入。 栈是只能在表尾进行插入和删除操作的线性表。 对于插入到栈的元素按“后进先出”的规则处理插入和删除操作都在栈顶进行。 由于进栈和出栈都是在栈顶进行所以要有一个size变量来记录当前栈的大小 当进栈时size不能超过数组长度size1出栈时栈不为空size-1。 介绍一下深度优先搜索和广度优先搜索是如何实现的 深度优先搜索 (1)访问起始点v0 (2)若v0的第一个邻接点没有被访问过则深度遍历该邻接点 (3)若v0的第一个邻接点已经被访问则访问其第二个邻接点进行深度遍历重复以上步骤直到所有节点都被访问过为止 广度优先搜索 (1)访问起始点v0 (2)依次遍历v0的所有未访问过得邻接点 (3)再依次访问下一层中未被访问过得邻接点重复以上步骤直到所有的顶点都被访问过为止 各种排序算法(各方法如何实现要会用语言描述) 内部排序包括插入排序、选择排序、交换排序、归并排序、基数排序。 其中插入排序包括直接插入排序、折半插入排序、希尔排序 选择排序包括简单选择排序堆排序 交换排序包括冒泡排序、快速排序。 (1)直接插入排序(稳定)基本思想为将序列分为有序部分和无序部分从无序部分依次选择元素与有序部分比较找到合适的位置将原来的元素往后移将元素插入到相应位置上。时间复杂度为O(n^2),空间复杂度为O(1) (2)折半插入排序(稳定)基本思想为设置三个变量low high mid令mid(lowhigh)/2,若a[mid]key,则令highmid-1, 否则令lowmid1,直到lowhigh时停止循环对序列中的每个元素做以上处理找到合适位置将其他元素后移进行插入。 比较次数为O(nlog2n),但是因为要后移因此时间复杂度为O(n^2),空间复杂度为O(1)。 优点是比较次数大大减少。 (3)希尔排序(不稳定)基本思想为先将序列分为若干个子序列对各子序列进行直接插入排序 等到序列基本有序时再对整个序列进行一次直接插入排序。 优点是让关键字值小的元素能够很快移动到前面且序列基本有序时进行直接插入排序时间效率会提升很多空间复杂度为O(1)。 (4)简单选择排序(不稳定)基本思想为将序列分为2部分 每经过一趟就在无序部分找到一个最小值然后与无序部分的第一个元素交换位置。 优点是实现简单缺点是每一趟只能确定一个元素的位置时间效率低。时间复杂度为O(n^2)空间复杂度为O(1)。 (5)堆排序(不稳定)设有一个任意序列k1,k2,…,kn当满足下面特点时称之为堆让此序列排列成完全二叉树 该树具有以下特点该树中任意节点均大于或小于其左右孩子此树的根节点为最大值或者最小值。 优点是对大文件效率明显提高但对小文件效率不明显。时间复杂度为O(nlog2n),空间复杂度为O(1)。 (6)冒泡排序(稳定)基本思路为每一趟都将元素进行两两比较并且按照“前小后大”的规则进行交换。 优点是每一趟不仅能找到一个最大的元素放到序列后面而且还把其他元素理顺如果下一趟排序没有发生交换则可以提前结束排序。 (7)快速排序(不稳定)基本思路为在序列中任意选择一个元素作为中心比它大的元素一律向后移动比它小的元素一律向前移动 形成左右两个子序列再把子序列按上述操作进行调整直到所有的子序列中都只有一个元素时序列即为有序。 优点是每一趟不仅能确定一个元素时间效率较高。时间复杂度为O(nlog2n),空间复杂度为O(log2n). (8)归并排序(稳定)基本思想为把两个或者两个以上的有序表合并成一个新的有序表。 时间复杂度为O(nlogn),空间复杂度和待排序的元素个数相同。
