你准备好开始了吗？我认为你还没有准备好，这意味着你必须做十个标准的俯卧撑，然后冷静下来，喝一口水，我喝咖啡，这有助于提高你的注意力。要知道这部分内容有点枯燥，这样的准备是必要的。
[En]
Are you ready to start? I don’t think you’re ready, which means you have to do ten standard push-ups, then calm down, have a sip of water, and I drink coffee, which helps to improve your concentration. To know that this part of the content is a little boring, such preparation is necessary.
概念全背
- 数据是信息的载体，是计算机能够识别、存储和处理的所有符号的总称。
[En]
data is the carrier of information, the general name of all symbols that can be recognized, stored and processed by a computer.*
- 数据项是具有独立含义的识别单位，是数据不可分割的最小单位。
[En]
A data item is an identification unit with an independent meaning and the smallest unit in which data is indivisible.*
- 数据元素是数据的基本单位。
[En]
data elements are the basic units of data.*
- 数据对象是具有相同属性的数据元素的集合。
[En]
A data object is a collection of data elements with the same properties.*
- 数据结构是彼此具有一个或多个关系的数据元素的集合。
[En]
A data structure is a collection of data elements that have one or more relationships with each other.*
- 逻辑结构：数据元素之间的关系称为逻辑结构
- 存储结构：最常用的是顺序存储和链式存储
- 数据的运算：运算是对数据的处理
空间复杂性是指算法从头到尾运行所需的存储量。
[En]
Space complexity refers to the amount of storage required for the algorithm to run from start to finish.
空间复杂度是指算法的时间消耗。
[En]
Space complexity refers to the time consumption of the algorithm.
数据结构是研究非数值程序设计中计算机的运行对象及其之间的计算方法和运算的一门学科。
[En]
Data structure is a subject that studies the operating objects of computers and the calculation methods and operations between them in non-numerical programming.
算法必须是可行的、有限的和确定性的。
[En]
The algorithm must be feasible, finite and deterministic.
不管这是否正确，这是非常痛苦的，但别担心，第一章已经结束了。如果会考还有其他未被选中的问题，那就看运气了。
[En]
It’s very painful whether it’s right, but don’t worry, the first chapter is over. If there are other unselected questions in the HKCEE, it depends on luck.
见微知著，识人心智。
说实话，你不必读它。
[En]
To tell you the truth, you don’t have to read it.
概念全背，不要有侥幸心理
递归是过程或函数直接或间接调用自身的方法。
[En]
Recursion is a method in which a procedure or function calls itself directly or indirectly.
递归方法只需要少量的代码来描述求解问题过程中需要的重复计算，大大减少了程序的代码量。递归的能力在于用有限的语句定义无限的对象集。
[En]
The recursive method only needs a small amount of code to describe the repeated calculations needed in the process of solving the problem, which greatly reduces the amount of code of the program. The ability of recursion lies in defining an infinite set of objects with finite statements.
当递归算法所涉及的数据定义形式是递归时，递归算法通常可以转化为递归算法，递归边界条件可以作为递归边界条件。
[En]
When the data definition form involved in the recursive algorithm is recursive, the recursive algorithm can usually be transformed into a recursive algorithm, and the recursive boundary condition can be used as the recursive boundary condition.
public class HanoiY {
void Move(char chSour, char chDest) {
System.out.println("Move the top plate of" + chSour + " to " + chDest);
}
void Hanoi(int n, char a, char b, char c) {
if (n == 1) {
Move(a, c);
} else {
Hanoi(n - 1, a, c, b);
this.Move(a, c);
Hanoi(n - 1, b, a, c);
}
}
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
HanoiY hanoi = new HanoiY();
hanoi.Hanoi(n, 'a', 'b', 'c');
}
}
递归的优点：结构清晰，可读性强，易于用数学归纳法证明算法的正确性。
[En]
The advantages of recursion: clear structure, strong readability, and easy to use mathematical induction to prove the correctness of the algorithm.
递归的缺点：递归算法运行效率低，耗时长，占用大量存储空间。
[En]
The disadvantage of recursion: the running efficiency of recursive algorithm is low, it takes a long time and takes up a lot of storage space.
递归算法是直接或间接调用自己的算法的过程。
[En]
A recursive algorithm is a process that calls its own algorithm directly or indirectly.
import java.util.Scanner;
public class FinalSalary{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
System.out.print("请输入要求的哪一年工资：");
int n = input.nextInt();
//方法一：递推（迭代）
int salary = 1500;
for(int i = 1 ; i < n ; i++){
salary *= 1.1;
}
System.out.println("第"+n+"年的工资为：" + salary);
System.out.println("第"+n+"年的工资为："+ Salary(n));
}
//方法二：递归
public static int Salary(int n){
if(n == 1){
return 1500;
}else{
return (int)(Salary(n - 1) * 1.1);
}
}
}
public static DLinkList(LinkList L) {
DLinkList H;
DLinkNode rear, s;
LinkNode p;
H = new DLinkList();
rear = H.Head;
p = L.Head.next;
while (p) {
s = new LinkList(Null);
s.data = p.data;
s.next = rear.next;
s.prior = rear;
rear.next = s;
H.Head.prior = s;
rear = s;
p = p.next;
}
return H;
}
天命靡常，唯德是辅。
概念背诵
顺序存储的优点：方法简单，有各种高级语言的数组类型，易于实现。不需要增加存储开销来表示节点之间的逻辑关系。顺序表具有根据元素序号随机存取的特点。
[En]
The advantages of sequential storage: the method is simple, there are array types in various high-level languages, and it is easy to implement. There is no need to increase the storage overhead to represent the logical relationship between nodes. The sequence table has the characteristic of random access according to the sequence number of elements.
链式存储的优点：在顺序表中插入和删除时，不需要多次移动元素，因此效率很高。无需提前分配足够的存储空间，大量存储不会空闲或溢出。
[En]
The advantage of chain storage: when inserting and deleting in the sequence table, there is no need to move elements many times, so it is efficient. There is no need to allocate enough storage space in advance, and a large amount of storage will not be idle or overflow.
非空的循环单链表head的尾节点满足 p.next==head
循环队列的优点：克服了伪溢出现象，充分利用了向量空间(删除元素后的空间仍然可以使用，最大限度地利用了空间)，有效利用了资源。
[En]
The advantages of circular queue: overcome the false overflow phenomenon, make full use of the vector space (the space after deleting elements can still be used, maximize the use of space) and make effective use of resources.
如何判断循环队列的空满度
[En]
How to judge the emptiness and fullness of a circular queue
方法之一是附设一个存储队中元素个数的变量，如num。num=0，对空，num=MAXSIZE，队满。
另一种方法是少用一个元素空间，(rear+1)%MAXSIZE==front。队满
当上帝是一条走失的狗时，他没有什么可担心的。
[En]
The Lord has nothing to worry about when he is a lost dog.
快把朕扶起来。
概念全部要背
- 一颗非空二叉树的第i层上最多有 2^i-1^ 个节点
- 一颗深度为k的二叉树中，最多具有2^k^-1个节点
- 对于一颗非空的二叉树，若叶子节点数为n~0~,度数为2的节点数为n~2~,则有n~0~=n~2~+1。
只添加一些不存在的空节点，以完整的二叉树的形式，然后按顺序存储。
[En]
Only add some empty nodes that do not exist, make it in the form of a complete binary tree, and then store it sequentially.
Original: https://blog.51cto.com/u_15226631/5551244
Author: Feyncode
Title: 数据结构的几个小问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/504407/
转载文章受原作者版权保护。转载请注明原作者出处！