hello，大家好，我是程序员黎明 ,在上期我们已经学习了C语言的基础知识，本期我们将学习数据结构的知识点，它能帮助你更快、更好地解决问题。
数据结构的绪论
在计算机科学中，数据结构是一种组织、管理和存储数据的方式。合理使用数据结构可以极大地提升程序的效率。常见的数据结构包括线性表、链表、栈、队列、树、图等。
那接下来我们逐个学习一下数据结构的知识点。
线性表
线性表是一种最基础的数据结构，可以理解为一个元素的有序集合。线性表中的元素是按照顺序排列的，每个元素都有唯一的前驱和后继元素（除了第一个和最后一个元素）。
线性表可以用顺序存储（数组）和链式存储（链表）来实现。
（线性表的顺序存储实现）：
#include <stdio.h>
#define MAXSIZE 100 // 定义线性表最大长度
typedef struct {
int data[MAXSIZE]; // 存放元素的数组
int length; // 当前线性表的长度
} SqList;
void InitList(SqList *L) {
L->length = 0;
}
int ListInsert(SqList *L, int i, int e) {
if (i < 1 || i > L->length + 1 || L->length == MAXSIZE) {
return 0; // 插入位置不合法或线性表已满
}
for (int j = L->length; j >= i; j--) {
L->data[j] = L->data[j - 1];
}
L->data[i - 1] = e;
L->length++;
return 1;
}
void ListPrint(SqList *L) {
for (int i = 0; i < L->length; i++) {
printf("%d ", L->data[i]);
}
printf("\n");
}
int main() {
SqList L;
InitList(&L);
ListInsert(&L, 1, 10);
ListInsert(&L, 2, 20);
ListInsert(&L, 3, 30);
ListPrint(&L);
return 0;
}
单链表
单链表是一种链式存储结构。它由多个节点组成，每个节点包含一个数据域和一个指向下一个节点的指针。相比数组，单链表插入和删除操作效率更高，但访问元素时需要从头开始遍历。
（单链表的实现）：
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node, *LinkList;
void InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node)); // 创建头节点
(*L)->next = NULL; // 头节点指向NULL
}
int ListInsert(LinkList L, int i, int e) {
LinkList p = L;
int j = 0;
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || j > i - 1) {
return 0; // 插入位置不合法
}
LinkList s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return 1;
}
void ListPrint(LinkList L) {
LinkList p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
LinkList L;
InitList(&L);
ListInsert(L, 1, 10);
ListInsert(L, 2, 20);
ListInsert(L, 3, 30);
ListPrint(L);
return 0;
}
双向链表
双向链表与单链表的区别在于，每个节点除了有指向下一个节点的指针，还多了一个指向前一个节点的指针，这样可以在链表中实现双向遍历。
（双向链表的实现）：
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
void InitList(DLinkList *L) {
*L = (DLinkList)malloc(sizeof(DNode)); // 创建头节点
(*L)->prior = NULL;
(*L)->next = NULL;
}
int ListInsert(DLinkList L, int i, int e) {
DLinkList p = L;
int j = 0;
while (p != NULL && j < i - 1) {
p = p->next;
j++;
}
if (p == NULL || j > i - 1) {
return 0; // 插入位置不合法
}
DLinkList s = (DLinkList)malloc(sizeof(DNode));
s->data = e;
s->next = p->next;
if (p->next != NULL) {
p->next->prior = s;
}
s->prior = p;
p->next = s;
return 1;
}
void ListPrint(DLinkList L) {
DLinkList p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
DLinkList L;
InitList(&L);
ListInsert(L, 1, 10);
ListInsert(L, 2, 20);
ListInsert(L, 3, 30);
ListPrint(L);
return 0;
}
数组
数组是最常见的顺序存储结构，支持通过下标快速访问元素，但插入和删除操作效率较低，因为需要移动大量元素。
（数组的使用）：
#include <stdio.h>
int main() {
int arr[5] = {10, 20, 30, 40, 50}; // 定义数组
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]); // 遍历数组
}
printf("\n");
return 0;
}
栈
栈是一种先进后出的线性表，支持后进先出（LIFO）操作。栈的常见应用包括表达式求值、括号匹配等。
（栈的实现）：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int top;
} Stack;
void InitStack(Stack *S) {
S->top = -1;
}
int Push(Stack *S, int e) {
if (S->top == MAXSIZE - 1) {
return 0; // 栈满
}
S->data[++S->top] = e;
return 1;
}
int Pop(Stack *S, int *e) {
if (S->top == -1) {
return 0; // 栈空
}
*e = S->data[S->top--];
return 1;
}
int main() {
Stack S;
InitStack(&S);
Push(&S, 10);
Push(&S, 20);
Push(&S, 30);
int e;
Pop(&S, &e);
printf("Pop: %d\n", e); // 输出栈顶元素
return 0;
}
队列
队列与栈不同，它是一种先进先出的数据结构（FIFO），应用场景包括任务调度、广度优先搜索等。
（队列的实现）：
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct {
int data[MAXSIZE];
int front, rear;
} Queue;
void InitQueue(Queue *Q) {
Q->front = Q->rear = 0;
}
int EnQueue(Queue *Q, int e) {
if ((Q->rear + 1) % MAXSIZE == Q->front) {
return 0; // 队列满
}
Q->data[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAXSIZE;
return 1;
}
int DeQueue(Queue *Q, int *e) {
if (Q->front == Q->rear) {
return 0; // 队列空
}
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return 1;
}
int main() {
Queue Q;
InitQueue(&Q);
EnQueue(&Q
, 10);
EnQueue(&Q, 20);
EnQueue(&Q, 30);
int e;
DeQueue(&Q, &e);
printf("DeQueue: %d\n", e); // 输出队首元素
return 0;
}
串（字符串）
串，也称为字符串，是由零个或多个字符组成的有限序列，通常被看作是一种特殊的线性表。字符串在日常编程中非常常见，广泛应用于文本处理、数据传输、搜索等领域。字符串的长度是其包含字符的个数。
字符串通常支持一系列的操作，包括查找、替换、插入、删除等。这些操作对于处理文本数据非常有用。
在C语言中，字符串用字符数组来表示，并且字符串的结尾用特殊的字符 \0（空字符）标识。
1. 字符串的表示和输入输出
在C语言中，我们可以通过字符数组来表示一个字符串，并且可以使用 printf() 和 scanf() 函数来输入输出字符串。
字符串的声明和初始化：
#include <stdio.h>
int main() {
char str1[] = "Hello, World!"; // 初始化字符串
char str2[20]; // 声明一个字符数组，存储不超过20个字符的字符串
// 打印字符串
printf("str1: %s\n", str1);
// 输入字符串
printf("请输入一个字符串：");
scanf("%s", str2); // 注意：scanf遇到空格时会停止读取
// 输出输入的字符串
printf("你输入的字符串是: %s\n", str2);
return 0;
}
字符串的特点：
-
C语言中的字符串以字符数组形式存储，每个字符占一个字节。 -
字符串的末尾由 \0来标识，这个空字符不属于字符串内容，但它表示字符串的结束。
2. 字符串的基本操作
我们可以对字符串进行一些基本操作，比如查找子串、替换子串、插入子串等。C语言的标准库 string.h 中提供了一些常用的字符串操作函数。
常用的字符串操作函数：
-
strlen()：返回字符串的长度（不包括结尾的\0）。 -
strcpy()：将一个字符串复制到另一个字符串。 -
strcat()：将两个字符串连接起来。 -
strcmp()：比较两个字符串的大小。
3. 字符串长度计算（strlen）
我们可以使用 strlen() 函数来计算字符串的长度。
#include <stdio.h>
#include <string.h>
int main() {
char str[] = "Hello, World!";
int length = strlen(str); // 计算字符串长度
printf("字符串的长度为: %d\n", length);
return 0;
}
4. 字符串复制（strcpy）
strcpy() 函数用于将一个字符串复制到另一个字符数组中。目标字符数组需要有足够的空间来存储源字符串。
#include <stdio.h>
#include <string.h>
int main() {
char src[] = "Hello, World!";
char dest[20];
strcpy(dest, src); // 将src字符串复制到dest
printf("复制后的字符串是: %s\n", dest);
return 0;
}
5. 字符串拼接（strcat）
strcat() 函数用于将一个字符串连接到另一个字符串的末尾。
#include <stdio.h>
#include <string.h>
int main() {
char str1[20] = "Hello, ";
char str2[] = "World!";
strcat(str1, str2); // 将str2拼接到str1末尾
printf("拼接后的字符串是: %s\n", str1);
return 0;
}
6. 字符串比较（strcmp）
strcmp() 函数用于比较两个字符串的大小。如果两个字符串相等，返回0；如果第一个字符串大于第二个，返回正数；否则返回负数。
#include <stdio.h>
#include <string.h>
int main() {
char str1[] = "Hello";
char str2[] = "World";
int result = strcmp(str1, str2); // 比较字符串
if (result == 0) {
printf("两个字符串相等\n");
} else if (result > 0) {
printf("str1 大于 str2\n");
} else {
printf("str1 小于 str2\n");
}
return 0;
}
7. 字符串查找（strstr）
strstr() 函数用于在一个字符串中查找子串的位置，如果找到，返回子串在主串中的地址；如果找不到，返回 NULL。
#include <stdio.h>
#include <string.h>
int main() {
char str[] = "Hello, World!";
char subStr[] = "World";
char* pos = strstr(str, subStr); // 查找子串
if (pos) {
printf("子串 \"%s\" 在字符串中的位置为: %ld\n", subStr, pos - str);
} else {
printf("未找到子串 \"%s\"\n", subStr);
}
return 0;
}
8. 字符串替换
在C语言中，标准库没有直接提供字符串替换的函数，但我们可以通过查找子串的方式，手动实现替换功能。
字符串替换的简单实现：
#include <stdio.h>
#include <string.h>
void replaceSubStr(char* str, const char* oldSubStr, const char* newSubStr) {
char buffer[100];
char* pos = strstr(str, oldSubStr); // 查找子串
if (pos) {
int oldLen = strlen(oldSubStr);
int newLen = strlen(newSubStr);
// 拷贝旧子串之前的部分
strncpy(buffer, str, pos - str);
buffer[pos - str] = '\0';
// 连接新子串
strcat(buffer, newSubStr);
// 连接旧子串之后的部分
strcat(buffer, pos + oldLen);
// 将结果拷贝回原字符串
strcpy(str, buffer);
}
}
int main() {
char str[] = "Hello, World!";
printf("原字符串: %s\n", str);
replaceSubStr(str, "World", "C Language");
printf("替换后的字符串: %s\n", str);
return 0;
}
9. 字符串插入
类似于替换操作，插入操作可以通过手动实现。在插入时，我们需要找到插入位置，并将插入位置后的内容进行移动。
字符串插入的简单实现：
#include <stdio.h>
#include <string.h>
void insertSubStr(char* str, const char* subStr, int pos) {
char buffer[100];
int len = strlen(str);
// 拷贝插入位置之前的部分
strncpy(buffer, str, pos);
buffer[pos] = '\0';
// 连接要插入的子串
strcat(buffer, subStr);
// 连接插入位置之后的部分
strcat(buffer, str + pos);
// 将结果拷贝回原字符串
strcpy(str, buffer);
}
int main() {
char str[100] = "Hello, World!";
printf("原字符串: %s\n", str);
insertSubStr(str, "Beautiful ", 7);
printf("插入后的字符串: %s\n", str);
return 0;
}
总结
字符串在编程中是非常重要的数据结构，常见的操作包括计算长度、查找子串、复制、拼接、比较、替换、插入等。C语言提供了丰富的字符串处理函数，我们可以通过这些函数轻松进行字符串的各种操作。在处理字符串时，需注意数组的长度和空字符 \0，避免内存溢出和读取错误。
树和二叉树
树是一种层次结构的存储方式，用于表示具有层次关系的数据。二叉树是最常见的树结构之一，每个节点最多有两个子节点。
（二叉树的简单实现）：
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* CreateNode(int data) {
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
void PreOrder(TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}
}
int main() {
TreeNode *root = CreateNode(1);
root->left = CreateNode(2);
root->right = CreateNode(3);
root->left->left = CreateNode(4);
root->left->right = CreateNode(5);
printf("PreOrder Traversal: ");
PreOrder(root);
printf("\n");
return 0;
}
哈夫曼树
哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。它主要用于数据压缩，通过构建哈夫曼树来生成最优的哈夫曼编码，从而减少存储和传输的数据量。哈夫曼编码的特点是对出现频率高的字符使用短的编码，对频率低的字符使用较长的编码，这种变长编码方式保证了编码的总长度最小。
哈夫曼树的构建过程：
-
统计字符出现的频率。 -
将每个字符及其频率看作一棵单节点的二叉树，频率作为权值。 -
从这些单节点中选取两个权值最小的节点，构成一个新的二叉树，新的权值为两个权值之和。 -
重复第3步，直到所有节点被合并成一棵树。
哈夫曼编码的应用：
-
数据压缩：如ZIP文件压缩、图像压缩等。 -
编码优化：减少文件的传输和存储空间。
（哈夫曼树的简单实现）：
#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100
// 哈夫曼树的节点
struct MinHeapNode {
char data; // 存储字符
unsigned freq; // 字符的频率
struct MinHeapNode *left, *right; // 左右子树
};
// 最小堆，用于存储哈夫曼树的节点
struct MinHeap {
unsigned size; // 堆中当前的节点数
unsigned capacity; // 堆的容量
struct MinHeapNode** array; // 指向堆节点的指针数组
};
// 创建一个新的节点
struct MinHeapNode* newNode(char data, unsigned freq) {
struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
temp->data = data;
temp->freq = freq;
temp->left = temp->right = NULL;
return temp;
}
// 创建一个最小堆
struct MinHeap* createMinHeap(unsigned capacity) {
struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));
return minHeap;
}
// 交换两个堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {
struct MinHeapNode* t = *a;
*a = *b;
*b = t;
}
// 堆化过程，维持最小堆
void minHeapify(struct MinHeap* minHeap, int idx) {
int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;
if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
smallest = left;
if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
smallest = right;
if (smallest != idx) {
swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
minHeapify(minHeap, smallest);
}
}
// 检查堆大小是否为1
int isSizeOne(struct MinHeap* minHeap) {
return (minHeap->size == 1);
}
// 提取最小值节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {
struct MinHeapNode* temp = minHeap->array[0];
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeapify(minHeap, 0);
return temp;
}
// 插入一个新的节点
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {
++minHeap->size;
int i = minHeap->size - 1;
while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
minHeap->array[i] = minHeap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
minHeap->array[i] = minHeapNode;
}
// 创建一个最小堆，并对字符进行构建
struct MinHeap* buildMinHeap(char data[], int freq[], int size) {
struct MinHeap* minHeap = createMinHeap(size);
for (int i = 0; i < size; ++i)
minHeap->array[i] = newNode(data[i], freq[i]);
minHeap->size = size;
int n = minHeap->size - 1;
for (int i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
return minHeap;
}
// 打印哈夫曼编码
void printCodes(struct MinHeapNode* root, int arr[], int top) {
if (root->left) {
arr[top] = 0;
printCodes(root->left, arr, top + 1);
}
if (root->right) {
arr[top] = 1;
printCodes(root->right, arr, top + 1);
}
if (!(root->left) && !(root->right)) {
printf("%c: ", root->data);
for (int i = 0; i < top; ++i)
printf("%d", arr[i]);
printf("\n");
}
}
// 哈夫曼编码的主函数
void HuffmanCodes(char data[], int freq[], int size) {
struct MinHeapNode *left, *right, *top;
struct MinHeap* minHeap = buildMinHeap(data, freq, size);
while (!isSizeOne(minHeap)) {
left = extractMin(minHeap);
right = extractMin(minHeap);
top = newNode('$', left->freq + right->freq);
top->left = left;
top->right = right;
insertMinHeap(minHeap, top);
}
int arr[MAX_TREE_HT], top_index = 0;
printCodes(extractMin(minHeap), arr, top_index);
}
int main() {
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("Huffman Codes:\n");
HuffmanCodes(arr, freq, size);
return 0;
}
图
图是一种更为复杂的数据结构，用于表示一组对象之间的关系。图中的对象称为顶点，而顶点之间的连接称为边。根据边是否有方向，图可以分为有向图和无向图。
-
有向图：边有方向性，即从一个顶点指向另一个顶点。 -
无向图：边没有方向性，即边连接的两个顶点彼此可以互相到达。
图的表示方法：
-
邻接矩阵：使用一个二维数组来表示图，数组的行和列对应顶点，值表示边的权重。 -
邻接表：使用链表来表示每个顶点的相邻顶点，适合表示稀疏图。
常见的图算法包括：
-
**广度优先搜索 (BFS)**：用于遍历图的节点，常用于查找最短路径。 -
**深度优先搜索 (DFS)**：用于遍历图的节点，常用于检测连通性、生成树等。
（邻接表实现无向图及DFS遍历）：
#include <stdio.h>
#include <stdlib.h>
// 图的邻接表节点
struct AdjListNode {
int dest;
struct AdjListNode* next;
};
// 图的邻接表
struct AdjList {
struct AdjListNode *head;
};
// 图结构
struct Graph {
int V; // 顶点数
struct AdjList* array;
};
// 创建邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// 创建图
struct Graph* createGraph(int V) {
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
for (int i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
// 添加无向边
void addEdge(struct Graph
* graph, int src, int dest) {
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
// 深度优先搜索的递归函数
void DFSUtil(int v, int visited[], struct Graph* graph) {
visited[v] = 1;
printf("%d ", v);
struct AdjListNode* temp = graph->array[v].head;
while (temp) {
int connectedVertex = temp->dest;
if (!visited[connectedVertex]) {
DFSUtil(connectedVertex, visited, graph);
}
temp = temp->next;
}
}
// 深度优先搜索
void DFS(struct Graph* graph, int startVertex) {
int* visited = (int*) malloc(graph->V * sizeof(int));
for (int i = 0; i < graph->V; i++)
visited[i] = 0;
DFSUtil(startVertex, visited, graph);
}
// 打印图
void printGraph(struct Graph* graph) {
for (int v = 0; v < graph->V; ++v) {
struct AdjListNode* pCrawl = graph->array[v].head;
printf("\n 顶点 %d 的邻接表\n head", v);
while (pCrawl) {
printf(" -> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int main() {
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
printf("\nDFS Traversal starting from vertex 0:\n");
DFS(graph, 0);
return 0;
}
以上代码实现了一个无向图的邻接表表示，并且使用深度优先搜索（DFS）算法进行遍历。
查找
查找是从数据集中找到符合条件的元素的过程。根据不同的数据结构和需求，查找可以分为线性查找、二分查找等。选择合适的查找算法可以极大提高查找效率。
1. 线性查找（Linear Search）
线性查找是一种最简单的查找算法，它遍历整个数据集，逐一比较元素，直到找到目标元素。虽然简单，但效率较低，尤其是在大规模数据集上。
-
时间复杂度：O(n)，其中n是数组的大小。
线性查找的代码实现：
#include <stdio.h>
// 线性查找函数
int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // 找到元素，返回索引
}
}
return -1; // 未找到，返回-1
}
int main() {
int arr[] = { 2, 4, 0, 1, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 4;
int result = linearSearch(arr, n, x);
if (result != -1)
printf("元素 %d 在数组中的索引为: %d\n", x, result);
else
printf("数组中未找到元素 %d\n", x);
return 0;
}
2. 二分查找（Binary Search）
二分查找是一种效率较高的查找算法，但前提是数组必须是有序的。它的基本思想是将待查找的范围缩小为一半，重复这一过程直到找到目标元素。
-
时间复杂度：O(log n)，其中n是数组的大小。
二分查找的代码实现：
#include <stdio.h>
// 二分查找函数
int binarySearch(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == x)
return mid; // 找到元素，返回索引
if (arr[mid] < x)
low = mid + 1; // 继续在右半部分查找
else
high = mid - 1; // 继续在左半部分查找
}
return -1; // 未找到，返回-1
}
int main() {
int arr[] = { 1, 3, 5, 7, 9, 11, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 7;
int result = binarySearch(arr, 0, n - 1, x);
if (result != -1)
printf("元素 %d 在数组中的索引为: %d\n", x, result);
else
printf("数组中未找到元素 %d\n", x);
return 0;
}
排序
排序是将一组数据按照某种规则（如从小到大或从大到小）重新排列的过程。排序算法的选择对性能有很大影响，特别是当数据规模较大时。
1. 冒泡排序（Bubble Sort）
冒泡排序是一种简单的交换排序算法。它的基本思想是反复比较相邻的两个元素，如果顺序不对，就交换它们，直到没有元素需要交换为止。
-
时间复杂度：O(n²)。
冒泡排序的代码实现：
#include <stdio.h>
// 冒泡排序函数
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]) {
// 交换两个元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
int main() {
int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("冒泡排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
2. 快速排序（Quick Sort）
快速排序是基于分治法的排序算法。它通过选择一个基准（通常是数组中的一个元素），然后将数组分成两个部分，使得基准左边的元素都小于基准，右边的元素都大于基准。之后递归地对两个部分进行排序。
-
平均时间复杂度：O(n log n)。 -
最坏时间复杂度：O(n²)。
快速排序的代码实现：
#include <stdio.h>
// 交换函数
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
// 分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最右边的元素作为基准
int i = (low - 1); // i是比基准小的元素的索引
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++; // 将小于基准的元素交换到左边
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1); // 返回基准元素的最终位置
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 找到基准位置
quickSort(arr, low, pi - 1); // 递归排序左子数组
quickSort(arr, pi + 1, high); // 递归排序右子数组
}
}
int main() {
int arr[] = { 10, 7, 8, 9, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("快速排序后的数组: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
3. 归并排序（Merge Sort）
归并排序同样使用分治法的思想。它将数组一分为二，分别对两个部分进行排序，然后将排好序的部分合并成一个有序的数组。
-
时间复杂度：O(n log n)。 -
空间复杂度：O(n)。
归并排序的代码实现：
#include <stdio.h>
#include <stdlib.h>
// 合并两个有序数组
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 拷贝数据到临时数组
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 合并两个数组
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 拷贝剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序函数
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m); // 排序左半部分
mergeSort(arr, m + 1, r); // 排序右半部分
merge(arr, l, m, r); // 合并两个部分
}
}
int main() {
int arr[] = {
12, 11, 13, 5, 6, 7 };
int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("给定数组是: \n");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
mergeSort(arr, 0, arr_size - 1);
printf("\n归并排序后的数组: \n");
for (int i = 0; i < arr_size; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
总结
-
查找算法：适用于从一组数据中找到特定元素。线性查找简单直接，而二分查找适用于有序数组，效率更高。 -
排序算法：用于将数据按照某种顺序重新排列。冒泡排序简单但效率较低，快速排序和归并排序较为高效，适用于大规模数据的排序。
通过学习这些数据结构的代码，可以极大地提升程序的性能。在学习和使用数据结构时，理解它们的原理和使用场景是最重要的，这样才能学以致用。好了，本期的学习就到这里啦，我们下期不见不散！
