衡阳外贸网站设计,宁波网站开发建设公司,三亚百度推广公司电话,wordpress 导入数据库结构文章目录 选择合适的数据结构数组链表栈队列树图哈希表 选择合适的算法实践和项目 #x1f389;欢迎来到数据结构学习专栏~实践和项目#xff1a;解决实际问题时#xff0c;选择合适的数据结构和算法 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒#x1f379;✨博客主页#xff1a;IT… 文章目录 选择合适的数据结构数组链表栈队列树图哈希表 选择合适的算法实践和项目 欢迎来到数据结构学习专栏~实践和项目解决实际问题时选择合适的数据结构和算法 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒✨博客主页IT·陈寒的博客该系列文章专栏数据结构学习其他专栏Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习文章作者技术和水平有限如果文中出现错误希望大家能指正 欢迎大家关注 ❤️ 在计算机科学中数据结构和算法是两个非常重要的概念。数据结构是用来存储和组织数据的方式而算法则是解决特定问题的步骤和操作。在实际应用中选择合适的数据结构和算法对于提高程序的效率和解决实际问题的能力至关重要。
选择合适的数据结构
在计算机科学中数据结构和算法是两个非常重要的概念。数据结构是用来存储和组织数据的方式而算法则是解决特定问题的步骤和操作。在实际应用中选择合适的数据结构和算法对于提高程序的效率和解决实际问题的能力至关重要。
数据结构的选择取决于具体的问题和场景。以下是一些常见的情况和对应的数据结构 数组
数组是一种线性数据结构它存储连续的元素并可以通过索引直接访问。由于数组在内存中是连续存储的因此访问数组元素的速度非常快。当需要快速访问元素时数组是一种非常合适的数据结构。
下面是一个使用数组的示例代码片段
# 创建一个包含10个整数的数组
arr [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]# 访问数组中的元素
print(arr[0]) # 输出1
print(arr[5]) # 输出6链表
链表是一种非连续的数据结构它由一系列节点组成每个节点包含一个指向下一个节点的指针。链表适用于需要动态分配内存的情况因为可以在运行时动态地添加或删除节点。
下面是一个使用链表的示例代码片段
public class Node {int value;Node next;public Node(int value) {this.value value;this.next null;}
}public class LinkedList {private Node head;public void add(int value) {Node newNode new Node(value);if (head null) {head newNode;} else {Node current head;while (current.next ! null) {current current.next;}current.next newNode;}}public void remove(int value) {if (head null) {return;}if (head.value value) {head head.next;return;}Node current head;while (current.next ! null current.next.value ! value) {current current.next;}if (current.next ! null) {current.next current.next.next;}}
}栈
栈是一种后入先出FILO的数据结构。它遵循“先进后出”LIFO的原则即最后一个插入的元素是第一个被删除的元素。栈适用于需要先入后出FILO的数据处理。例如后入先出的队列就可以用栈来实现。
下面是一个使用栈的示例代码片段
stack []
stack.append(1) # 插入元素1
stack.append(2) # 插入元素2
print(stack.pop()) # 删除并返回元素2输出2
print(stack.pop()) # 删除并返回元素1输出1队列
队列是一种先入先出FIFO的数据结构。它遵循“先进先出”FIFO的原则即第一个插入的元素是第一个被删除的元素。队列适用于需要先入先出FIFO的数据处理。例如操作系统的任务调度就可以用队列来实现。
下面是一个使用队列的示例代码片段
queue []
queue.append(1) # 插入元素1
queue.append(2) # 插入元素2
print(queue.pop(0)) # 删除并返回元素1输出1
print(queue.pop(0)) # 删除并返回元素2输出2树
树是一种层次结构由节点和连接节点的边组成。树中的每个节点可能有多个子节点根节点没有父节点。树适用于需要层次结构和快速查找的情况。例如文件系统就是用树来存储文件的。
下面是一个使用树的示例代码片段
class TreeNode:def __init__(self, value):self.value valueself.children []self.parent Noneself.is_root Falseself.is_leaf Falseself.level Nonedef add_child(self, child):child.parent selfchild.is_root Falsechild.level self.levelif not self.children:self.is_root Truechild.parent selfself.children.append(child)def get_root(node):if node.is_root:return nodeelse:return node.parent.get_root(node)图
图是一种无限制的数据结构由节点和连接节点的边组成。图中的节点和边可以带有权重或其他属性。图适用于需要表示复杂关系的情况。例如社交网络就可以用图来表示。
下面是一个使用图的示例代码片段
class Graph:
def __init__(self):
self.nodes set()
self.edges {}def add_node(self, node):
self.nodes.add(node)
self.edges[node] []def add_edge(self, from_node, to_node, weight1):
if from_node not in self.nodes or to_node not in self.nodes:
raise ValueError(Both nodes need to be in graph)
self.edges[from_node].append((to_node, weight))
self.edges[to_node].append((from_node, weight))哈希表
哈希表是一种数据结构它使用哈希函数将键映射到桶中并在每个桶中存储相应的值。哈希表适用于需要快速查找键值对应关系的情况。例如字典查找就可以用哈希表来实现。
下面是一个使用哈希表的示例代码片段
class HashTable:
def __init__(self):
self.table {}def put(self, key, value):
hash_key hash(key) % len(self.table)
bucket self.table[hash_key]
for i, kv in enumerate(bucket):
if kv[0] key:
bucket[i] ((key, value))
return True
return False选择合适的算法
算法的选择同样取决于具体的问题和场景。以下是一些常见的情况和对应的算法
排序算法适用于需要对大量数据进行有序处理的情况。例如冒泡排序、快速排序、归并排序等。
冒泡排序这是一种简单的排序算法它重复地遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
def bubble_sort(arr):n len(arr)for i in range(n):for j in range(0, n-i-1):if arr[j] arr[j1] :arr[j], arr[j1] arr[j1], arr[j]return arr快速排序这是一种分治的排序算法。它将一个数组分成两个子数组然后对子数组进行递归排序。 def quick_sort(arr):if len(arr) 1:return arrpivot 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)搜索算法适用于需要在大量数据中查找特定元素的情况。例如线性搜索、二分搜索等。
线性搜索这是一种简单的搜索算法它遍历整个数组比较每个元素与目标元素如果匹配则返回该元素。
def linear_search(arr, x):for i in range(len(arr)):if arr[i] x:return ireturn -1二分搜索这是一种高效的搜索算法它只在排序的数组中搜索并且搜索过程是对称的。它首先检查中间元素如果中间元素是要搜索的元素则搜索过程结束。如果中间元素大于要搜索的元素则在数组的左半部分继续搜索。相反如果中间元素小于要搜索的元素则在数组的右半部分继续搜索。
def binary_search(arr, low, high, x):if high low:mid (high low) // 2if arr[mid] x:return midelif arr[mid] x:return binary_search(arr, low, mid - 1, x)else:return binary_search(arr, mid 1, high, x)else:return -1图算法适用于需要处理图形结构的情况。例如最短路径算法Dijkstra、Bellman-Ford等、最小生成树算法Kruskal、Prim等。
这里以Dijkstra的最短路径算法为例Dijkstra算法是一个用于解决给定节点到图中所有其他节点的最短路径问题的算法。它假设所有的边权重都是正数。
def dijkstra(graph, start_vertex):D {v:float(infinity) for v in graph} D[start_vertex] 0 queue [(0, start_vertex)] while queue: current_distance, current_vertex min(queue, keylambda x:x[0]) queue.remove((current_distance, current_vertex)) if current_distance D[current_vertex]: continue for neighbor, weight in graph[current_vertex].items(): old_distance D[neighbor] new_distance current_distance weight if new_distance oldDistance: D[neighbor] newDistance queue.append((newDistance, neighbor)) return D #returns dictionary of shortest distances from start node to every other node in the graph. 动态规划算法适用于需要解决复杂问题且问题的子问题也具有独立性时的情况。例如背包问题、最长公共子序列问题等。 以背包问题为例背包问题是一种典型的动态规划问题其目标是在给定背包容量和物品重量及价值的情况下选择一系列物品装入背包以使得背包中的总价值最大。 def knapsack(weights, values, W):n len(weights)dp [[0 for _ in range(W1)] for _ in range(n1)]for i in range(1, n1):for w in range(1, W1):if weights[i-1] w:dp[i][w] max(dp[i-1][w], dp[i-1][w-weights[i-1]] values[i-1])else:dp[i][w] dp[i-1][w]return dp[n][W]分治算法适用于可以将大问题分解为若干个小问题的情况。例如归并排序、快速排序等。
这里以归并排序为例归并排序是一种分治算法它将一个数组分成两个子数组然后对子数组进行递归排序最后将两个已排序的子数组合并成一个已排序的数组。 def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result []i j 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result.extend(left[i:])result.extend(right[j:])return result贪心算法适用于问题的最优解可以通过一系列局部最优的选择来达到全局最优的情况。例如霍夫曼编码、最小生成树等。 这里以霍夫曼编码为例霍夫曼编码是一种用于数据压缩的贪心算法。它通过为每个频繁出现的字符创建一个尽可能短的编码来工作。在编码过程中每个字符的编码是根据前一个字符的编码来确定的。 class HuffmanNode:def __init__(self, freq, charNone):self.freq freq self.char char self.left None self.right None self.huff None def __cmp__(self, other): if(other None): return -1 if(self.freq other.freq): return 0 elif(self.freq other.freq): return 1 else: return -1 def build_heap(arr): n len(arr) for i in range(n//2 - 1, -1, -1): heapify(arr, n, i) def heapify(arr, n, i): smallest i left 2*i 1 right 2*i 2 if left n and arr[smallest].freq arr[left].freq: smallest left if right n and arr[smallest].freq arr[right].freq: smallest right if smallest ! i: arr[i], arr[smallest] arr[smallest], arr[i] # swap heapify(arr, n, smallest) # call heapify for the smallest element at root. def huffman_encode(arr): arr_min None # to store the minimum frequency object heap [] # to store the heap minimum at the root of heap. //创建最小堆根节点为最小值。 //将数组转化为最小堆。 build_heap(heap) for item in arr: heap.append(item) build_heap(heap) //删除重复的元素 arr_min heap[0] //将频率最小的元素移除 heap.remove(arr_min) //添加到 huffman tree 中 if arr_min.charif arr_min.char None:arr_min heap[0]heap.remove(arr_min)tree.add_node(arr_min)
else:tree.add_node(arr_min)heap.remove(arr_min)# The function to print the binary tree.
def print_binary_tree(root):if root is not None:print_binary_tree(root.left)print(root.data, end )print_binary_tree(root.right)# The main function to find the Huffman编码 of a string.
def find_huffman_encoding(text):# Create a frequency table for all characters in the text.char_freq {}for char in text:char_freq[char] char_freq.get(char, 0) 1# Create a priority queue to store the nodes of the Huffman tree.# The priority of a node is defined by the sum of the frequencies# of its two children.pq []for char, freq in char_freq.items():pq.append((freq, char))heapq.heapify(pq)# Create an empty Huffman tree and add the nodes to it in a way# that maintains the property that the priority of a node is# defined by the sum of the frequencies of its two children.while len(pq) 1:left heapq.heappop(pq)right heapq.heappop(pq)merge_node HuffmanNode(left[0] right[0], None)merge_node.left HuffmanNode(left[0], left[1])merge_node.right HuffmanNode(right[0], right[1])heapq.heappush(pq, merge_node)# The last element in the priority queue is the root of the Huffman tree.root pq[-1]# Now, we can build the Huffman encoding by traversing the Huffman tree.huff_enc []print_binary_tree(root)print(Huffman encoding for text: )
huff_enc.reverse() # reverse the list because the traversal is in reverse order.
print(huff_enc)这个Python程序通过创建一个优先级队列在Python中使用heapq实现来存储每个字符的频率然后通过合并频率最低的两个节点来构建霍夫曼树。一旦构建了霍夫曼树就可以使用简单的遍历来为输入字符串生成霍夫曼编码。
实践和项目
选择合适的数据结构和算法是解决实际问题的重要步骤。以下是一些实践和项目可以帮助你锻炼和应用所学知识
参与开源项目许多开源项目都涉及到复杂的数据结构和算法。参与这些项目的开发和维护可以帮助你了解如何在实际应用中选择和实现数据结构和算法。 参加算法竞赛许多大型的算法竞赛如ACM、Google Code Jam等都提供了大量的难题和挑战。通过解决这些难题你可以更深入地理解和应用各种数据结构和算法。 构建自己的项目选择一个实际问题并尝试用数据结构和算法来解决它。例如你可以尝试实现一个基于哈希表的字典查找系统或者实现一个基于二分搜索的查找引擎。 总之通过参与实践和项目你可以更深入地了解各种数据结构和算法的应用场景和优劣性从而提高你的程序设计和问题解决能力。 结尾 ❤️ 感谢您的支持和鼓励 您可能感兴趣的内容 【Java面试技巧】Java面试八股文 - 掌握面试必备知识目录篇【Java学习路线】2023年完整版Java学习路线图【AIGC人工智能】Chat GPT是什么初学者怎么使用Chat GPT需要注意些什么【Java实战项目】SpringBootSSM实战打造高效便捷的企业级Java外卖订购系统【数据结构学习】从零起步学习数据结构的完整路径
