王道考研数据结构第一章知识点总结

**王道考研数据结构第一章知识点总结**

**1.1 算法的定义和分类**

算法是指解决一个问题所遵循的一系列步骤或操作。根据算法的输入输出特征，可以将算法分为两类：

* **确定性算法**:对于同样的输入，算法总是能得到相同的输出。
* **非确定性算法**:对于同样的输入，算法可能得到不同的输出。

**1.2 算法的时间和空间复杂度**

算法的时间复杂度是指算法执行所需的时间量，而空间复杂度是指算法所占用的存储空间。常见的时间复杂度包括：

* **O(1)**:表示算法的时间复杂度为常数，不随输入大小变化。
* **O(log n)**:表示算法的时间复杂度与输入大小的对数成正比。
* **O(n)**:表示算法的时间复杂度与输入大小成线性关系。
* **O(n log n)**:表示算法的时间复杂度为输入大小的乘积。
* **O(n^2)**:表示算法的时间复杂度为输入大小的平方。

常见的空间复杂度包括：

* **O(1)**:表示算法所占用的存储空间为常数，不随输入大小变化。
* **O(log n)**:表示算法所占用的存储空间与输入大小的对数成正比。
* **O(n)**:表示算法所占用的存储空间与输入大小成线性关系。

**1.3 递归和迭代**

递归是指函数或过程在其自身上调用自己，以解决一个问题。迭代则是指通过反复执行一系列操作来解决一个问题。

递归的优点包括：

* **简洁**:递归可以使代码更加简洁和易于理解。
* **高效**:递归可以避免重复计算，从而提高算法的效率。

递归的缺点包括：

* **风险**:递归可能导致栈溢出或其他问题。
* **性能**:递归可能比迭代慢，因为每次调用都需要创建一个新的函数栈帧。

迭代的优点包括：

* **安全**:迭代不会导致栈溢出或其他问题。
* **高效**:迭代可以避免重复计算，从而提高算法的效率。

迭代的缺点包括：

* **复杂**:迭代可能使代码更加复杂和难以理解。
* **低效**:迭代可能比递归慢，因为每次循环都需要创建一个新的函数栈帧。

**1.4 数组和链表**

数组是指一组连续的内存单元，用于存储相同类型的数据。链表则是指一组非连续的内存单元，通过指针连接起来。

数组的优点包括：

* **高效**:数组可以快速访问任何元素。
* **低内存开销**:数组通常需要较少的内存开销。

数组的缺点包括：

* **固定大小**:数组的大小是固定的，不可改变。
* **插入和删除困难**:在数组中插入或删除一个元素可能会导致其他元素的位置发生变化。

链表的优点包括：

* **动态大小**:链表的大小可以根据需要动态调整。
* **插入和删除容易**:在链表中插入或删除一个元素只需改变相应指针的值即可。

链表的缺点包括：

* **低效**:链表可能比数组慢，因为每次访问都需要通过指针找到相应元素。
* **高内存开销**:链表通常需要较多的内存开销。

**1.5 栈和队列**

栈是指一个后进先出的数据结构，遵循 LIFO（Last-In-First-Out）原则。队列则是指一个先进先出的数据结构，遵循 FIFO（First-In-First-Out）原则。

栈的优点包括：

* **高效**:栈可以快速访问任何元素。
* **低内存开销**:栈通常需要较少的内存开销。

栈的缺点包括：

* **固定大小**:栈的大小是固定的，不可改变。
* **插入和删除困难**:在栈中插入或删除一个元素可能会导致其他元素的位置发生变化。

队列的优点包括：

* **动态大小**:队列的大小可以根据需要动态调整。
* **插入和删除容易**:在队列中插入或删除一个元素只需改变相应指针的值即可。

队列的缺点包括：

* **低效**:队列可能比栈慢，因为每次访问都需要通过指针找到相应元素。
* **高内存开销**:队列通常需要较多的内存开销。

**1.6例题**

#例题1：实现一个函数，计算两个链表的长度class Node:
 def __init__(self, data):
 self.data = data self.next = Nonedef get_length(head):
 length =0 while head is not None:
 length +=1 head = head.next return length#例题2：实现一个函数，合并两个有序链表class Node:
 def __init__(self, data):
 self.data = data self.next = Nonedef merge_two_lists(head1, head2):
 if head1 is None:
 return head2 elif head2 is None:
 return head1 else:
 if head1.data < head2.data:
 head1.next = merge_two_lists(head1.next, head2)
 return head1 else:
 head2.next = merge_two_lists(head1, head2.next)
 return head2#例题3：实现一个函数，判断两个链表是否相等class Node:
 def __init__(self, data):
 self.data = data self.next = Nonedef is_equal(head1, head2):
 while head1 is not None and head2 is not None:
 if head1.data != head2.data:
 return False head1 = head1.next head2 = head2.next return True