数据结构与算法之美总结（数组、链表、栈、队列、递归、排序及二分）

**数据结构与算法之美总结**

在计算机科学中，数据结构和算法是两个基本概念，它们共同构成了编程的基础。数据结构是指组织和存储数据的方式，而算法则是指解决问题或完成任务所遵循的步骤序列。在本文中，我们将总结一些常见的数据结构和算法，包括数组、链表、栈、队列、递归、排序及二分。

**1. 数组**

数组是一种线性数据结构，它由一系列连续的元素组成，每个元素都有一个唯一的索引或下标。数组是最基本也是最常用的数据结构之一。

c//例子：创建并初始化一个整型数组int arr[5] = {1,2,3,4,5};

**2. 链表**

链表是一种非线性数据结构，它由一系列的结点组成，每个结点都包含一个值和一个指向下一个结点的引用。链表可以动态地增加或减少结点。

c//例子：创建并初始化一个整型链表struct Node {
 int data;
 struct Node* next;
};

int main() {
 struct Node head = {1, NULL};
 struct Node* p = &head;

 // 创建链表 for (int i =2; i <=5; i++) {
 struct Node* newNode = malloc(sizeof(struct Node));
 newNode->data = i;
 newNode->next = NULL;
 p->next = newNode;
 p = newNode;
 }

 return0;
}

**3. 栈**

栈是一种后进先出的数据结构，它遵循 LIFO（Last In First Out）原则。栈的元素可以通过 push 和 pop 操作添加或删除。

c//例子：创建并初始化一个整型栈typedef struct {
 int* data;
 int top;
 int capacity;
} Stack;

int main() {
 Stack stack = {malloc(5 * sizeof(int)), -1,5};

 // push元素 for (int i =0; i < 5; i++) {
 stack.data[++stack.top] = i;
 }

 // pop元素 while (stack.top >=0) {
 printf("%d ", stack.data[stack.top--]);
 }
 free(stack.data);

 return0;
}

**4. 队列**

队列是一种先进先出的数据结构，它遵循 FIFO（First In First Out）原则。队列的元素可以通过 enqueue 和 dequeue 操作添加或删除。

c//例子：创建并初始化一个整型队列typedef struct {
 int* data;
 int front;
 int rear;
 int capacity;
} Queue;

int main() {
 Queue queue = {malloc(5 * sizeof(int)), -1, -1,5};

 // enqueue元素 for (int i =0; i < 5; i++) {
 queue.data[++queue.rear] = i;
 }

 // dequeue元素 while (queue.front <= queue.rear) {
 printf("%d ", queue.data[queue.front++]);
 }
 free(queue.data);

 return0;
}

**5. 递归**

递归是一种编程技术，它允许函数调用自身以解决问题或完成任务。递归通常用于处理树形结构或其他递归关系。

c//例子：计算斐波那契数列的第 n 项int fibonacci(int n) {
 if (n <=1) return n;
 else return fibonacci(n -1) + fibonacci(n -2);
}

**6. 排序**

排序是一种算法，用于将数据按一定顺序排列。常见的排序算法包括冒泡排序、选择排序、插入排序等。

c//例子：使用冒泡排序对整型数组进行排序void bubbleSort(int arr[], int n) {
 for (int i =0; i < n -1; i++) {
 for (int j =0; j < n - i -1; j++) {
 if (arr[j] > arr[j +1]) {
 // swap(arr[j], arr[j +1]);
 int temp = arr[j];
 arr[j] = arr[j +1];
 arr[j +1] = temp;
 }
 }
 }
}

**7. 二分**

二分是一种算法，用于在有序数组中快速找到目标元素。二分通常用于实现查找、插入或删除等操作。

c//例子：使用二分查找对整型数组进行查找int binarySearch(int arr[], int n, int target) {
 int left =0;
 int right = n -1;

 while (left <= right) {
 int mid = left + (right - left) /2;

 if (arr[mid] == target) return mid;
 else if (arr[mid] < target) left = mid +1;
 else right = mid -1;
 }

 return -1; // 未找到目标元素}

以上就是本文对数据结构和算法的总结。这些概念是编程的基础，理解它们对于编写高效、可靠且易于维护的代码至关重要。