文章
7
粉丝
84
获赞
30
访问
156.0k
1. 数据结构是研究计算机的操作对象的逻辑结构和物理结构以及在结构上定义的操作,逻辑结构包括线性结构和非线性结构,物理结构包括顺序结构、链式结构、索引结构和散列结构。
2. 时间复杂度:时间复杂度是指执行算法所需的计算工作量,所以将算法中基本操作的运行次数作为时间复杂度的度量,比如循环的层数和递归的深度等。
3. 算法:算法是对特定问题求解步骤的一种描述,是一系列输入转换为输出的计算步骤。算法的五个特性:输入、输出、有穷性、确定性、可行性。
4. 循环和递归:递归代码简单清晰,便于检查正确性,但递归有时可能会出现堆栈溢出的现象,执行效率较低;循环执行效率高,但不一定能解决所有问题,有时候可以用递归解决的问题不一定能用循环解决。
5. 贪心算法、动态规划以及分治法:贪心算法是自顶向下的算法,但它不从整体角度考虑而是考虑局部最优解,因此贪心算法得到的结果不一定是全局最优的;动态规划是自底向上的算法,将一个大问题分解成有重复的小问题,并把一些问题的解记录下来,这样可以减少重复计算,在求解子问题的过程中不断保留最优解,丢弃其他局部解,最后得到答案;分治法也是将一个大问题分解成若干个小问题,不过这些小问题和大问题有相同的结构,通过递归解决小问题,再合并结果成为大问题的解。
6. 在链表中设置头结点:作用是为了链表操作时,可以对空表、非空表以及对首元素结点进行统一处理。
7. 数组和链表的区别:数组的长度是固定的,不能适应数据动态增减的情况,即数组的大小一旦定义就不能改变。链表的长度是可以任意变化的,可以适应数据动态增减的情况,且可以方便插入删除数据。数组在内存中是连续存储的,因此可以利用下标索引进行访问,链表是链式存储结构,只能通过线性方式进行访问。
8. 静态链表:用数组来代替指针,来表述单链表,数组元素包含两个数据域,第一个数据域存放数据,第二个数据域存放后继元素在数组中的下标。
9. 循环链表的优点:从任一结点出发都可访问到表中的所有结点。
10. 栈和队列:栈和队列都是受限制的线性表,其中栈是只有一端可以插入和删除,可以进行插入和删除的一端称为栈顶,另一端称为栈底;队列是可以一端进行插入,另一端进行删除。
11. 共享栈:利用栈底位置的相对不变性,可以让两个顺序栈共享一个一维数组空间,将两个栈的栈底分别...
登录后发布评论
不戳