数据结构与算法c语言代码

关于数据结构与算法的C语言代码实现
链表 (Linked List)
链表是一种线性数据结构，其中每个节点由一个数据项和指向下一个节点的引用组成。
#include <stdio.h>
#include <stdlib.h>

// 定义单向链表结点
struct Node {
int data;
struct Node* next;
};

// 创建新节点
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

// 插入到链表头部
void insertAtHead(struct Node** head, int newData) {
struct Node* newNode = createNode(newData);
newNode->next = *head;
*head = newNode;
}
登录后复制
此段代码展示了如何定义并操作简单的单向链表[^1]。
栈 (Stack)
栈遵循后进先出原则(LIFO)，可以使用数组或链表来实现。这里展示基于数组的简单栈实现：
#define MAX_SIZE 100

int stack[MAX_SIZE];
int top = -1;

// 压栈操作
void push(int item) {
if (top >= MAX_SIZE - 1) {
printf("Stack Overflow\n");
return;
}
stack[++top] = item;
}

// 出栈操作
int pop() {
if (top < 0) {
printf("Stack Underflow\n");
return -1;
} else {
return stack[top--];
}
}
登录后复制
这段程序实现了基本的压栈和弹栈功能。
排序算法：快速排序 (Quick Sort)
快速排序是一个高效的分治法排序算法，在平均情况下具有O(n log n)的时间复杂度。
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);

for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(&amp;arr[i], &amp;arr[j]);
}
}
swap(&amp;arr[i + 1], &amp;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); // 右边子数组
}
}
登录后复制
上述代码提供了完整的快速排序函数以及辅助方法partition()用于分割数组。