数据结构是计算机科学中的基本概念，用于组织和存储数据，以便高效地进行访问和修改。常见的数据结构包括数组、链表、栈、队列、树和图等。本文将介绍几种常见的数据结构及其在C语言中的实现。
🧑 博主简介：现任阿里巴巴嵌入式技术专家，15年工作经验，深耕嵌入式+人工智能领域，精通嵌入式领域开发、技术管理、简历招聘面试。CSDN优质创作者，提供产品测评、学习辅导、简历面试辅导、毕设辅导、项目开发、C/C++/Java/Python/Linux/AI等方面的服务，如有需要请站内私信或者联系任意文章底部的的VX名片（ID：gylzbk）
💬 博主粉丝群介绍：① 群内初中生、高中生、本科生、研究生、博士生遍布，可互相学习，交流困惑。② 热榜top10的常客也在群里，也有数不清的万粉大佬，可以交流写作技巧，上榜经验，涨粉秘籍。③ 群内也有职场精英，大厂大佬，可交流技术、面试、找工作的经验。④ 进群免费赠送写作秘籍一份，助你由写作小白晋升为创作大佬。⑤ 进群赠送CSDN评论防封脚本，送真活跃粉丝，助你提升文章热度。有兴趣的加文末联系方式，备注自己的CSDN昵称，拉你进群，互相学习共同进步。
C语言数据结构详解：数组、链表、栈、队列、树和图等的设计与实现
1. 引言2. 数组（Array）2.1 数组的定义和初始化
3. 链表（Linked List）3.1 单链表的定义和实现
4. 栈（Stack）4.1 栈的定义和实现
5. 队列（Queue）5.1 队列的定义和实现
6. 树（Tree）6.1 二叉树的定义和实现
7. 图（Graph）7.1 邻接矩阵表示图
8. 结论9. 参考文献
1. 引言
数据结构是计算机科学中的基本概念，用于组织和存储数据，以便高效地进行访问和修改。常见的数据结构包括数组、链表、栈、队列、树和图等。本文将介绍几种常见的数据结构及其在C语言中的实现。
2. 数组（Array）
数组是一种线性数据结构，用于存储相同类型的元素。数组中的元素在内存中是连续存储的，可以通过索引访问。
2.1 数组的定义和初始化
#include
int main() {
int arr[5] = {1, 2, 3, 4, 5}; // 定义并初始化数组
for (int i = 0; i < 5; i++) {
printf("%d ", arr[i]); // 访问数组元素
}
printf("\n");
return 0;
}
3. 链表（Linked List）
链表是一种线性数据结构，由一系列节点组成。每个节点包含数据和指向下一个节点的指针。链表的优点是插入和删除操作效率高，缺点是随机访问效率低。
3.1 单链表的定义和实现
#include
#include
// 定义链表节点结构
struct Node {
int data;
struct Node* next;
};
// 在链表头部插入新节点
void push(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// 打印链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d -> ", node->data);
node = node->next;
}
printf("NULL\n");
}
int main() {
struct Node* head = NULL;
push(&head, 1);
push(&head, 2);
push(&head, 3);
push(&head, 4);
printf("Linked list: ");
printList(head);
return 0;
}
4. 栈（Stack）
栈是一种线性数据结构，遵循后进先出（LIFO）的原则。栈的基本操作包括入栈（push）、出栈（pop）和获取栈顶元素（top）。
4.1 栈的定义和实现
#include
#include
// 定义栈节点结构
struct StackNode {
int data;
struct StackNode* next;
};
// 创建新节点
struct StackNode* newNode(int data) {
struct StackNode* stackNode = (struct StackNode*)malloc(sizeof(struct StackNode));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
// 判断栈是否为空
int isEmpty(struct StackNode* root) {
return !root;
}
// 入栈操作
void push(struct StackNode** root, int data) {
struct StackNode* stackNode = newNode(data);
stackNode->next = *root;
*root = stackNode;
printf("%d pushed to stack\n", data);
}
// 出栈操作
int pop(struct StackNode** root) {
if (isEmpty(*root)) {
return -1;
}
struct StackNode* temp = *root;
*root = (*root)->next;
int popped = temp->data;
free(temp);
return popped;
}
// 获取栈顶元素
int peek(struct StackNode* root) {
if (isEmpty(root)) {
return -1;
}
return root->data;
}
int main() {
struct StackNode* root = NULL;
push(&root, 10);
push(&root, 20);
push(&root, 30);
printf("%d popped from stack\n", pop(&root));
printf("Top element is %d\n", peek(root));
return 0;
}
5. 队列（Queue）
队列是一种线性数据结构，遵循先进先出（FIFO）的原则。队列的基本操作包括入队（enqueue）、出队（dequeue）和获取队头元素（front）。
5.1 队列的定义和实现
#include
#include
// 定义队列节点结构
struct QueueNode {
int data;
struct QueueNode* next;
};
// 定义队列结构
struct Queue {
struct QueueNode *front, *rear;
};
// 创建新节点
struct QueueNode* newNode(int data) {
struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
temp->data = data;
temp->next = NULL;
return temp;
}
// 创建空队列
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
// 入队操作
void enqueue(struct Queue* q, int data) {
struct QueueNode* temp = newNode(data);
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
// 出队操作
int dequeue(struct Queue* q) {
if (q->front == NULL) {
return -1;
}
struct QueueNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
int dequeued = temp->data;
free(temp);
return dequeued;
}
int main() {
struct Queue* q = createQueue();
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
printf("%d dequeued from queue\n", dequeue(q));
printf("%d dequeued from queue\n", dequeue(q));
return 0;
}
6. 树（Tree）
树是一种层次数据结构，由节点组成。每个节点包含一个数据元素和若干子节点。常见的树结构包括二叉树、二叉搜索树、平衡二叉树等。
6.1 二叉树的定义和实现
#include
#include
// 定义二叉树节点结构
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 创建新节点
struct TreeNode* newNode(int data) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = data;
node->left = node->right = NULL;
return node;
}
// 前序遍历
void preorder(struct TreeNode* node) {
if (node == NULL) {
return;
}
printf("%d ", node->data);
preorder(node->left);
preorder(node->right);
}
// 中序遍历
void inorder(struct TreeNode* node) {
if (node == NULL) {
return;
}
inorder(node->left);
printf("%d ", node->data);
inorder(node->right);
}
// 后序遍历
void postorder(struct TreeNode* node) {
if (node == NULL) {
return;
}
postorder(node->left);
postorder(node->right);
printf("%d ", node->data);
}
int main() {
struct TreeNode* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
printf("Preorder traversal: ");
preorder(root);
printf("\n");
printf("Inorder traversal: ");
inorder(root);
printf("\n");
printf("Postorder traversal: ");
postorder(root);
printf("\n");
return 0;
}
7. 图（Graph）
图是一种复杂的数据结构，由节点（顶点）和边组成。图可以是有向图或无向图。常见的图表示方法包括邻接矩阵和邻接表。
7.1 邻接矩阵表示图
#include
#include
// 定义图结构
struct Graph {
int numVertices;
int** adjMatrix;
};
// 创建图
struct Graph* createGraph(int vertices) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph->adjMatrix[i] = (int*)malloc(vertices * sizeof(int));
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
return graph;
}
// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1; // 无向图
}
// 打印图
void printGraph(struct Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
printf("Vertex %d: ", i);
for (int j = 0; j < graph->numVertices; j++) {
printf("%d ", graph->adjMatrix[i][j]);
}
printf("\n");
}
}
int main() {
struct Graph* graph = createGraph(5);
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);
return 0;
}
8. 结论
数据结构是计算机科学中的基本概念，通过合理选择和使用数据结构，可以提高程序的性能和效率。本文介绍了几种常见的数据结构，包括数组、链表、栈、队列、树和图，并提供了它们在C语言中的实现。通过掌握这些数据结构，可以在实际编程中灵活应用这些知识来解决各种数据存储和处理问题。
9. 参考文献
《数据结构与算法分析》—— Mark Allen WeissC语言标准库文档
通过本文的介绍，希望您对C语言中的数据结构有了更全面的了解，并能够在实际编程中灵活应用这些知识来解决数据存储和处理问题。