数据结构的算法编程通常涉及以下步骤:
确定数据结构的类型和实现方式
选择合适的数据结构,如数组、链表、栈、队列、树等。
确定数据结构的实现方式,例如使用数组还是链表来实现特定功能。
定义算法的输入和输出参数
明确算法需要处理的输入数据,可能是数据结构中的某些元素或者整个数据结构。
定义算法的输出结果,例如计算结果、排序后的数据结构等。
确定算法的实现方式
根据算法的目的和输入输出参数,选择合适的算法实现方式。
编写代码实现算法,注意代码的结构和可读性。
测试和优化
对算法进行测试,确保其正确性和效率。
根据测试结果对算法进行优化,提高性能。
排序算法
快速排序
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
```
冒泡排序
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
```
搜索算法
二分搜索
```python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([1, 2, 3, 4, 5], 3))
```
链表操作
删除头结点
```python
class ListNode:
def __init__(self, data=0, next=None):
self.data = data
self.next = next
def delete_front(head):
if head is None:
return None
new_head = head.next
del head
return new_head
示例链表: 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
new_head = delete_front(head)
打印新链表: 2 -> 3 -> 4 -> 5
current = new_head
while current:
print(current.data, end=" -> ")
current = current.next
print("None")
```
树结构
二叉树的前序遍历