使用Python和C++的写数据结构和算法
- 1.数据结构和算法简介
- 2.数据结构
- 2.1 堆栈
- 2.2 队列
- 2.3 散列表
- 2.4 二叉树
- 2.5 线性搜索
- 2.6 二进制搜索
- 2.7 递归
- 2.8 递归二进制搜索
- 2.9 QuickSort
- 2.10 Fizzzbuzz算法
- 2.11 计数排序
- 2.12 合并排序
- 2.13 插入排序
- 2.14 选择排序
数据结构和算法是计算机科学的主题，无论您对编程的哪个方面感兴趣，每个程序员都应该知道。人们相信，如果你对数据结构和算法有很好的了解，那么你就知道设计算法和编写好代码的基础。这就是为什么编码面试中的大多数问题都基于数据结构和算法的概念。在本文中，我将带您完成关于使用Python和C++编程语言写数据结构和算法。
1.数据结构和算法简介
数据结构可以定义为用于存储和组织数据的元素，算法可以定义为解决问题所需的一系列步骤。数据结构和算法的概念有助于我们有效和高效地解决问题。
通过实现数据结构的概念，创建了一种良好的算法，使算法能够有效地管理数据。在任何计算机科学任务中，我们都需要了解数据结构和算法的概念，以设计更好的算法来解决复杂问题。在下一节中，我将带您了解一些您应该知道的最重要的数据结构和算法：
2.数据结构
2.1 堆栈
堆栈是几乎所有编程语言中常用的抽象数据类型。堆栈是一种模拟现实世界堆栈的数据结构，如卡片、盘子堆栈等。以下是如何使用Python实现堆栈的方法：
class Stack:def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
l = len(self.items)-1
return self.items[l]
def size(self):
return len(self.items)
2.2 队列
队列是一种数据结构，我们从后面插入项目，然后从前面删除项目。它遵循先入先出的数据结构原则。您可以将Queues数据结构想象成排队等待购买演出门票的人。在这里，第一个排队的人是第一个买第一张票的人，依此类推。因此，我们可以说，计算机科学中的队列数据结构模拟了实际队列。以下是如何使用Python实现队列的方法：
class queue:def __init__(self):
self.items = []
def is_empty(self):
return self.items == []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
2.3 散列表
散列表就像Python中的字典，它们是数据结构，用于以键和值格式存储和检索大量数据。散列表基于散列的概念，它提供了一种在复杂的时间和空间中高效存储和检索数据的方法。以下是如何使用Python实现散列表的方法：
class hashtable:def __init__(self, items):
self.bucket_size = len(items)
self.buckets = [[] for i in range(self.bucket_size)]
self.assign_buckets(items)
def assign_buckets(self, items):
for key, value in elements:
hash_value = hash(key)
index = hash_value % self.bucket_size
self.buckets[index].append((key, value))
def get_value(self, input_keys):
hash_value = hash(input_keys)
index = hash_value % self.bucket_size
bucket = self.buckets[index]
for key, value in bucket:
if key == input_keys:
return(value)
2.4 二叉树
二叉树是一种通用而强大的数据结构，看起来像一棵真正的树。它包含连接图中的节点，其中每个节点都有一个父节点和一个按特定顺序的子节点。二叉树由节点组成，每个节点都包含一个左右指针和一个数据项。它还有一个指向树中最顶部节点的根指针。左右指针指向两侧的小子树。它还有一个空树，代表一个没有元素的二叉树。以下是如何使用C++实现二叉树的方法：
using namespace std;
typedef struct binary_tree_node{
int v;
struct binary_tree_node *left;
struct binary_tree_node *right;
}
BTNode;
BTNode *create_binary_tree_node(int v){
BTNode *p = new BTNode;
if(p != NULL){
p->v = v;
p->left = NULL;
p->right = NULL;
}
return p;
}
void create_balanced_bin_tree(BTNode **root, int arr[], int start, int end){
if(start <= end){
int mid = (start + end + 1) / 2;
*root = create_binary_tree_node(arr[mid]);
create_balanced_bin_tree(&((*root)->left), arr, start, mid - 1);
create_balanced_bin_tree(&((*root)->right), arr, mid + 1, end);
}
}
void print_binary_tree(BTNode *root){
if(root != NULL){
cout << root->v;
print_binary_tree(root->left);
cout << endl;
print_binary_tree(root->right);
cout << endl;
}
}
int main(int argc, char* argv[])
{
int arr[30];
for(int i = 0; i < 30; i ++){
arr[i] = i;
}
BTNode *root = NULL;
create_balanced_bin_tree(&root, arr, 0, 29);
print_binary_tree(root);
return 0;
}
2.5 线性搜索
线性搜索是最基本和最有用的算法之一，它通过数据结构依次移动以找到相应的值，这就是它也被称为顺序搜索算法的原因。将线性搜索算法视为通过智能手机上的联系人列表找到方法。线性搜索从开始，从阅读每个名字开始，直到你找到你要找的东西。以下是如何使用Python实现线性搜索或顺序搜索的方法：
def sequential_search(list_, n):for i in list_:
if i == n:
break
return True
2.6 二进制搜索
二元搜索也称为半间隔搜索，是一种用于计算机系统查找值在排序数组中位置的算法。在二进制搜索算法中，列表被拆分为两半，然后在每半中搜索。在实现二进制搜索算法时，需要注意的一件事是，在运行算法之前，必须对列表进行排序。以下是如何使用Python实现二进制搜索的方法：
def search(list, n):l = 0
u = len(list) - 1
while 1 <= u:
mid = (l + u) // 2
if list[mid] == n:
return True
else:
if list[mid] < n:
l = mid + 1
else:
u = mid - 1
return False
list = [1, 3, 4, 7, 8, 9, 10, 45, 50, 90, 100, 150, 600, 1000]
n = 90
if search(list, n):
print("Found")
else:
print("Not Found")
2.7 递归
在编程中，递归是对同一方法的方法调用。换句话说，递归方法是自称为的方法。在递归中，您唯一的任务是简化原始问题，或在简化没有必要或不可能时直接解决。以下是如何使用C++实现递归的方法：
int get_term_fib(int n){if (n == 0)
return 0;
if (n == 1)
return 1;
return get_term_fib(n - 1) + get_term_fib(n - 2);
}
2.8 递归二进制搜索
递归是指通过将复杂问题分解为更小的问题，然后逐步解决问题来解决问题。二进制搜索意味着通过反复将搜索间隔分为两半来查找排序数组中的项目，递归二进制搜索意味着将整个二进制搜索过程细分为较小的问题。简而言之，二进制搜索的递归解决方案称为递归二进制搜索。以下是如何使用Python实现递归二进制搜索的方法：
def rec_binarySearch(target, sequence, first, last):if first > last:
return False
else:
mid = (last + first) // 2
if sequence[mid] == target:
return True
elif target < sequence[mid]:
return rec_binarySearch(target, sequence, first, mid-1)
else:
return rec_binarySearch(target, sequence, mid + 1, last)
2.9 QuickSort
快速排序是一种排序算法，它选择一个项目并重新排列数组，形成两个分区，以便项目下方的所有项目都先出现，上面的所有项目之后。然后，该算法递归用于各个部分，直到它获得排序列表。以下是如何使用C++实现快速排序算法的方法：
using namespace std;
void swap(int arr[], int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
int partition(int arr[], int l, int r){
int pivot = arr[r];
int i = l - 1;
for(int j = l; j < r; j++){
if(arr[j] < pivot){
i++
swap(arr, i, j);
}
}
swap(arr, i + 1, r);
return i+1;
}
void quicksort(int arr[], int l, int r){
if(l < r){
int pi = partition(arr, l, r);
quicksort(arr, l, pi-1);
quicksort(arr, pi+1, r);
}
}
int main(){
int arr[5]={5, 4, 3, 2, 1};
quicksort(arr, 0, 4);
for(int i=0; i<5; i++){
cout<<arr[i]<<" ";
}cout<<endl;
return 0;
}
2.10 Fizzzbuzz算法
FizzBuzz算法是编码面试中最喜欢的问题之一。Fizz和Buzz是指3和5的倍数。这个编码问题在数字3和5中很受欢迎，但您可能可以看到更复杂的数字，但解决这个问题的逻辑将保持不变。以下是如何使用C++实现fizzbuzz算法的方法：
using namespace std;
int main(){
for(int i = 1; i<=20; i++){
if(i % 3 == 0 && i % 5 == 0){
cout<<"FizzBuzz"<<endl;
}
else if(i % 3 == 0){
cout<<"Fizz"<<endl;
}
else if(i % 5 == 0){
cout<<"Buzz"<<endl;
}
else{
cout<<i<<endl;
}
}
return 0;
}
2.11 计数排序
计数排序的时间复杂性优于其他排序技术。计数排序算法的工作原理是查找数组中每个唯一元素的数量。然后计算每个元素在排序数组中的位置。计数排序的唯一限制是它仅限于小正整数。以下是如何使用C++实现计数排序算法的方法：
using namespace std;
void countsort(int arr[], int n){
int k = arr[0];
for(int i = 0; i < n; i++){
k = max(k, arr[i]);
}
int count[k] = {0};
for(int i = 0; i < n; i++){
count[arr[i]]++;
}
for(int i = 1; i <= k; i++){
count[i]+=count[i-1];
}
int output[n];
for(int i=n-1; i>=0; i--){
output[--count[arr[i]]] = arr[i];
}
for(int i=0; i<n; i++){
arr[i] = output[i];
}
}
int main(){
int arr[] = {1, 3, 2, 3, 4, 1, 6, 4, 3};
countsort(arr, 9);
for(int i=0; i<9; i++){
cout<<arr[i]<<" ";
}
return 0;
}
2.12 合并排序
合并排序是基于分而治之技术的排序算法。它的工作原理是将数组分为两半，然后以排序方式组合它们。合并排序是一种整洁的算法，因为它是排序自己的排序。这意味着按合并排序只需要很少的比较和交换；相反，它依赖于一种与快速排序略有不同的分而分赢策略。以下是如何使用C++实现合并排序的方法：
using namespace std;
void merge(int arr[], int l, int mid, int r){
int n1 = mid - l + 1;
int n2 = r - mid;
int a[n1];
int b[n2];
for (int i = 0; i < n1; i++){
a[i] = arr[l + i];
}
for (int i = 0; i < n2; i++){
b[i] = arr[mid + 1 + i];
}
int i = 0;
int j = 0;
int k = 1;
while (i < n1 && j < n2){
if (a[i] < b[j]){
arr[k] = a[i];
k++; i++;
}
else{
arr[k] = b[j];
k++; j++;
}
}
while (i < n1){
arr[k] = a[i];
k++; i++;
}
while (j < n2){
arr[k] = b[j];
k++; j++;
}
}
void mergeSort(int arr[], int l, int r){
if (l < r){
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
}
int main(){
int arr[]={5, 4, 3, 2, 1};
mergeSort(arr, 0, 4);
for(int i=0; i<5; i++){
cout<<arr[i]<<" ";
}
cout<<endl;
return 0;
}
2.13 插入排序
插入排序算法维护排序项的集合和要排序的项目集合。在程序中实现插入排序时，该算法将排序和未排序的集合保持在同一序列结构中。以下是如何使用C++实现插入排序算法的方法：
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
for(int i = 0; i < n; i ++){
cin>>arr[i];
}
for(int i = 1; i < n; i++){
int current = arr[i];
int j = i - 1;
while (arr[j]>current && j >= 0){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = current;
}
for(int i = 0; i < n; i++){
cout<<arr[i]<<" ";
}cout<<endl;
}
2.14 选择排序
选择排序是一种排序算法，特别是就地比较排序。该算法将输入数组分为两部分：已在数组开始（左）从左到右构建的已排序项子列表，以及占据数组其余部分的剩余待排序项子数组。以下是如何使用C++实现选择排序算法的方法：
using namespace std;
int main(){
int n;
cin>>n;
int arr[n];
for (int i = 0; i < n; i++){
cin>>arr[i];
}
for (int i = 0; i < n; i++){
for (int j = i+1; j<n; j++){
if (arr[j] < arr[i]){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
for (int i = 0; i < n; i++){
cout<<arr[i]<<" ";
}cout<<endl;
}