C语言代码实现数据结构与算法

简介: 以上代码中,哈希表使用链表解决哈希冲突,每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值,insert函数用于向哈希表中插入一个键值对,若当前位置为空,则直接插入;否则,将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值,若存在则返回其值,否则返回-1。

动态数组(Dynamic Array)
动态数组是一种可以自动调整大小的数组,具有可变长度。在C语言中,可以使用指针和内存动态分配函数(如malloc和realloc)实现动态数组。

以下是一个简单的动态数组实现示例代码:

include

include

typedef struct {
int *arr;
int size;
int capacity;
} dynamic_array;

void init(dynamic_array da, int capacity) {
da->arr = (int
)malloc(capacity * sizeof(int));
da->size = 0;
da->capacity = capacity;
}

void append(dynamic_array da, int value) {
if (da->size == da->capacity) {
da->capacity
= 2;
da->arr = (int )realloc(da->arr, da->capacity sizeof(int));
}
da->arr[da->size++] = value;
}

void print(dynamic_array *da) {
for (int i = 0; i < da->size; i++) {
printf("%d ", da->arr[i]);
}
printf("\n");
}

int main() {
dynamic_array da;
init(&da, 10);
append(&da, 1);
append(&da, 2);
append(&da, 3);
print(&da);
free(da.arr);
return 0;
}
以上代码中,动态数组通过结构体实现,其中arr指向实际存储元素的数组,size表示当前数组中的元素个数,capacity表示数组最多可以容纳的元素个数。init函数用于初始化动态数组,append函数用于在数组末尾添加元素,如果数组容量不足,则动态扩展数组容量。print函数用于打印数组中的元素。在程序结束前,需要释放动态分配的内存。

链表(Linked List)
链表是一种常见的数据结构,它由一组节点组成,每个节点包含一个值和一个指向下一个节点的指针。在C语言中,可以通过定义结构体来实现链表。

以下是一个简单的链表实现示例代码:

include

include

typedef struct node {
int data;
struct node *next;
} node;

void insert(node *head, int value) {
node
new_node = (node )malloc(sizeof(node));
new_node->data = value;
new_node->next =
head;
*head = new_node;
}

void print(node *head) {
while (head) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}

int main() {
node *head = NULL;
insert(&head, 3);
insert(&head, 2);
insert(&head, 1);
print(head);
return 0;
}
以上代码中,链表通过定义结构体来实现,其中data表示节点存储的值,next表示指向下一个节点的指针。insert函数用于在链表头部插入节点,print函数用于打印链表中的元素。在程序结束前,需要释放动态分配的内存

栈(Stack)
栈是一种后进先出(LIFO)的数据结构,它可以通过数组或链表实现。在C语言中,可以使用数组实现栈。

以下是一个简单的栈实现示例代码:

include

define MAX_SIZE 10

typedef struct {
int arr[MAX_SIZE];
int top;
} stack;

void init(stack *s) {
s->top = -1;
}

void push(stack *s, int value) {
if (s->top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
s->arr[++s->top] = value;
}

int pop(stack *s) {
if (s->top == -1) {
printf("Stack Underflow!\n");
return -1;
}
return s->arr[s->top--];
}

int peek(stack *s) {
if (s->top == -1) {
printf("Stack Underflow!\n");
return -1;
}
return s->arr[s->top];
}

int main() {
stack s;
init(&s);
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", peek(&s));
return 0;
}
以上代码中,栈通过结构体实现,其中arr表示存储栈元素的数组,top表示栈顶元素的下标。init函数用于初始化栈,push函数用于将元素入栈,如果栈已满则报错,pop函数用于将栈顶元素出栈,如果栈为空则报错,peek函数用于查看栈顶元素,但不将其出栈。在程序结束前,不需要显式释放内存。

队列(Queue)
队列是一种先进先出(FIFO)的数据结构,它也可以通过数组或链表实现。在C语言中,可以使用数组实现队列。

以下是一个简单的队列实现示例代码:

include

define MAX_SIZE 10

typedef struct {
int arr[MAX_SIZE];
int front;
int rear;
} queue;

void init(queue *q) {
q->front = 0;
q->rear = -1;
}

void enqueue(queue *q, int value) {
if (q->rear == MAX_SIZE - 1) {
printf("Queue Overflow!\n");
return;
}
q->arr[++q->rear] = value;
}

int dequeue(queue *q) {
if (q->front > q->rear) {
printf("Queue Underflow!\n");
return -1;
}
return q->arr[q->front++];
}

int peek(queue *q) {
if (q->front > q->rear) {
printf("Queue Underflow!\n");
return -1;
}
return q->arr[q->front];
}

int main() {
queue q;
init(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("%d\n", dequeue(&q));
printf("%d\n", peek(&q));
return 0;
}
以上代码中,队列通过结构体实现,其中arr表示存储队列元素的数组,front和rear分别表示队列头和队列尾元素的下标。init函数用于初始化队列,enqueue函数用于将元素入队,如果队列已满则报错,dequeue函数用于将队头元素出队,如果队列为空则报错,peek函数用于查看队头元素,但不将其出队。在程序结束前,不需要显式释放内存。

二叉树(Binary Tree)
二叉树是一种树形结构,其中每个节点最多有两个子节点,分别为左子节点和右子节点。在C语言中,可以使用结构体和指针实现二叉树。

以下是一个简单的二叉树实现示例代码:

include

include

typedef struct node {
int value;
struct node left;
struct node
right;
} node;

node create_node(int value) {
node
new_node = (node*) malloc(sizeof(node));
new_node->value = value;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}

void inorder_traversal(node *root) {
if (root == NULL) {
return;
}
inorder_traversal(root->left);
printf("%d ", root->value);
inorder_traversal(root->right);
}

int main() {
node *root = create_node(1);
root->left = create_node(2);
root->right = create_node(3);
root->left->left = create_node(4);
root->left->right = create_node(5);
inorder_traversal(root);
return 0;
}
以上代码中,二叉树通过结构体实现,其中value表示节点的值,left和right分别表示左子节点和右子节点。create_node函数用于创建新节点,并返回指向该节点的指针。inorder_traversal函数用于中序遍历二叉树,即先遍历左子树,再遍历根节点,最后遍历右子树。在程序结束前,需要显式释放二叉树中所有节点的内存。

快速排序(Quick Sort)
快速排序是一种常用的排序算法,其基本思想是通过选定一个基准元素,将待排序序列划分为两个子序列,其中一个子序列的所有元素均小于等于基准元素,另一个子序列的所有元素均大于等于基准元素,然后对两个子序列分别进行递归排序,最终将整个序列排序。

以下是一个简单的快速排序实现示例代码:

include

void swap(int a, int b) {
int temp = a; a = b; b = temp;
}

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quick_sort(arr, low, pivot - 1);
quick_sort(arr, pivot + 1, high);
}
}

int main() {
int arr[] = {5, 1, 9, 3, 7, 4, 8, 2, 6};
int n = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
以上代码中,快速排序通过递归实现,其中partition函数用于选取基准元素,并将序列划分为两个子序列。具体地,选择最右边的元素为基准元素,使用i和j两个指针扫描整个序列,若arr[j]小于基准元素,则将其与arr[i+1]交换,并将i加1,最终将基准元素交换到i+1处。quick_sort函数用于递归排序子序列,直到整个序列有序。在程序结束前,不需要显式释放内存。

广度优先搜索(Breadth-First Search)
广度优先搜索是一种图遍历算法,其基本思想是从图中某个顶点开始,依次访问其所有邻居节点,然后再访问邻居节点的所有邻居节点,直到图中所有节点都被访问为止。在C语言中,可以使用队列实现广度优先搜索。

以下是一个简单的广度优先搜索实现示例代码:

include

include

define MAX_N 100 // 最大节点数

// 邻接表结点
typedef struct node {
int val;
struct node* next;
} Node;

// 邻接表
typedef struct graph {
Node* head[MAX_N];
int n; // 节点总数
} Graph;

// 队列结构体
typedef struct queue {
int data[MAX_N];
int head, tail;
} Queue;

// 初始化邻接表
void init(Graph* G, int n) {
G->n = n;
for (int i = 0; i < n; i++) {
G->head[i] = NULL;
}
}

// 添加无向边
void add_edge(Graph G, int u, int v) {
Node
node = (Node*)malloc(sizeof(Node));
node->val = v;
node->next = G->head[u];
G->head[u] = node;

node = (Node*)malloc(sizeof(Node));
node->val = u;
node->next = G->head[v];
G->head[v] = node;

}

// 初始化队列
void init_queue(Queue* Q) {
Q->head = Q->tail = 0;
}

// 入队
void enqueue(Queue* Q, int val) {
Q->data[Q->tail++] = val;
}

// 出队
int dequeue(Queue* Q) {
return Q->data[Q->head++];
}

// 判断队列是否为空
int is_empty(Queue* Q) {
return Q->head == Q->tail;
}

// 广度优先搜索
void bfs(Graph* G, int start) {
Queue Q;
int visited[MAX_N] = {0}; // 标记是否已访问过
init_queue(&Q);
enqueue(&Q, start);
visited[start] = 1;

while (!is_empty(&Q)) {
    int cur = dequeue(&Q);
    printf("%d ", cur);

    Node* p = G->head[cur];
    while (p != NULL) {
        if (!visited[p->val]) {
            visited[p->val] = 1;
            enqueue(&Q, p->val);
        }
        p = p->next;
    }
}

}

// 主函数
int main() {
Graph G;
int n, m; // n为节点数,m为边数
scanf("%d%d", &n, &m);
init(&G, n);

for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add_edge(&G, u, v);
}

bfs(&G, 0);  // 从0节点开始进行广度优先搜索

return 0;

}
以上是一个使用邻接表实现的BFS示例代码,其中使用了一个队列结构体,用于存储需要进行扩展的节点。首先将起始节点加入队列中,并标记为已访问过,然后不断从队列中取出一个节点,将其相连的未访问过的邻居节点加入队列,直到队列为空为止。这样遍历的过程就是一个层层扩展的过程,因此BFS也被称为“宽度优先搜索”。

上面的代码实现了一个简单的BFS算法,它可以接受从标准输入读入的图的描述,以及起始节点,然后打印出从起始节点开始的BFS遍历结果。其中,节点使用0~n-1的整数表示,图的描述使用每行两个整数u和v表示一条无向边。

二叉查找树(Binary Search Tree)
二叉查找树是一种基于二分查找的数据结构,它具有以下性质:

左子树上所有节点的值均小于它的根节点的值
右子树上所有节点的值均大于它的根节点的值
左右子树都是二叉查找树
以下是一个简单的二叉查找树实现示例代码:

include

include

typedef struct node {
int value;
struct node left;
struct node
right;
} Node;

void insert(Node *root, int value) {
if (
root == NULL) {
root = (Node)malloc(sizeof(Node));
(root)->value = value;
(
root)->left = NULL;
(root)->right = NULL;
} else {
if (value < (
root)->value) {
insert(&((root)->left), value);
} else {
insert(&((
root)->right), value);
}
}
}

void inorder_traversal(Node *root) {
if (root != NULL) {
inorder_traversal(root->left);
printf("%d ", root->value);
inorder_traversal(root->right);
}
}

int main() {
Node *root = NULL;
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 4);
insert(&root, 6);
insert(&root, 8);
inorder_traversal(root);
return 0;
}
以上代码中,二叉查找树使用递归实现。insert函数用于向二叉查找树中插入一个节点,若当前节点为空,则将新节点插入;否则,根据当前节点的值和待插入节点的值大小关系,递归调用insert函数。inorder_traversal函数用于中序遍历二叉查找树,即先遍历左子树,然后访问根节点,最后遍历右子树。在程序结束前,需要显式释放内存。

哈希表(Hash Table)
哈希表是一种基于哈希函数实现的数据结构,它具有快速查找和插入的特点。在C语言中,可以使用数组和链表来实现哈希表。

以下是一个简单的哈希表实现示例代码:

include

include

define TABLE_SIZE 10

typedef struct node {
int key;
int value;
struct node *next;
} Node;

Node *hash_table[TABLE_SIZE];

int hash(int key) {
return key % TABLE_SIZE;
}

源码参考:http://www.huayukouye.com/sitemap.html

void insert(int key, int value) {
int index = hash(key);
Node new_node = (Node)malloc(sizeof(Node));
new_node->key = key;
new_node->value = value;
new_node->next = NULL;
if (hash_table[index] == NULL) {
hash_table[index] = new_node;
} else {
Node *current = hash_table[index];
while (current->next != NULL) {
current = current->next;
}
current->next = new_node;
}
}

int search(int key) {
int index = hash(key);
Node *current = hash_table[index];
while (current != NULL) {
if (current->key == key) {
return current->value;
}
current = current->next;
}
return -1;
}

int main() {
insert(1, 10);
insert(11, 20);
insert(21, 30);
printf("%d\n", search(1));
printf("%d\n", search(11));
printf("%d\n", search(21));
return 0;
}
以上代码中,哈希表使用链表解决哈希冲突,每个链表节点包含一个键值对。hash函数用于计算键值对应的哈希值,insert函数用于向哈希表中插入一个键值对,若当前位置为空,则直接插入;否则,将新节点插入到链表末尾。search函数用于在哈希表中查找指定键值的值,若存在则返回其值,否则返回-1。

这些常用的C语言数据结构、算法和功能代码示例,涵盖了常见的数据结构和算法,能够满足许多实际应用的需求。需要注意的是,在实际使用时,需要根据具体情况进行优化和改进,以适应不同的应用场景。

相关文章
|
15小时前
|
算法 C语言
KMP算法(C语言实现)
KMP算法(C语言实现)
5 0
|
4天前
|
C语言
C语言扫雷代码(蹦蹦炸弹)(下)
C语言扫雷代码(蹦蹦炸弹)(下)
4 0
|
5天前
|
算法 C语言 人工智能
|
5天前
|
机器学习/深度学习 算法 API
【Paddle】PCA线性代数基础 + 领域应用:人脸识别算法(1.1w字超详细:附公式、代码)
【Paddle】PCA线性代数基础 + 领域应用:人脸识别算法(1.1w字超详细:附公式、代码)
9 0
|
5天前
|
算法 C语言
【C语言】求最小新整数(贪心算法)
【C语言】求最小新整数(贪心算法)
10 1
|
5天前
|
算法 C语言
C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
C语言易混淆、简单算法、结构体题目练习、常见关键字总结
|
5天前
|
算法 编译器 API
C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
C语言易混淆、简单算法、结构体题目练习、常见关键字总结
|
5天前
|
算法 关系型数据库 C语言
卡尔曼滤波简介+ 算法实现代码(转)
卡尔曼滤波简介+ 算法实现代码(转)
20 4
|
5天前
|
运维 算法
基于改进遗传算法的配电网故障定位(matlab代码)
基于改进遗传算法的配电网故障定位(matlab代码)
|
5天前
|
算法 调度
基于多目标粒子群算法冷热电联供综合能源系统运行优化(matlab代码)
基于多目标粒子群算法冷热电联供综合能源系统运行优化(matlab代码)