C语言数据结构与算法基础

# 第一章：C语言基础回顾

## 1.1 C语言基础语法

C语言作为一种结构化的、面向过程的程序设计语言，其基础语法是学习该语言的第一步。下面我们将回顾C语言的基础语法，包括变量定义、数据类型、运算符、控制流语句等，并结合例子进行说明。

### 变量定义

在C语言中，变量需要先声明后使用，声明变量的格式为`类型 变量名`，例如：

int a; // 声明一个整型变量a
float b; // 声明一个浮点型变量b
char c; // 声明一个字符型变量c

### 数据类型

C语言提供了丰富的数据类型，包括基本数据类型和派生数据类型。基本数据类型包括整型、浮点型、字符型等，而派生数据类型包括数组、指针、结构体、联合体等。

int age = 25; // 声明并初始化一个整型变量
float salary = 5000.50; // 声明并初始化一个浮点型变量
char gender = 'M'; // 声明并初始化一个字符型变量

### 控制流语句

C语言中的控制流语句包括if语句、switch语句、for循环、while循环等，用于控制程序的执行流程。

int num = 10;
if(num > 5) {
    printf("num大于5\n");
} else {
    printf("num不大于5\n");
}

int option = 2;
switch(option) {
    case 1:
        printf("选择了选项1\n");
        break;
    case 2:
        printf("选择了选项2\n");
        break;
    default:
        printf("没有匹配的选项\n");
}

for (int i = 0; i < 5; i++) {
    printf("%d ", i);
}

int j = 0;
while (j < 5) {
    printf("%d ", j);
    j++;
}

## 第二章：数据结构与算法概述
2.1 数据结构的基本概念
2.2 线性表
2.3 树与图
2.4 查找与排序算法
2.5 算法复杂度分析
### 第三章：线性表

#### 3.1 数组和链表
在C语言中，数组和链表是两种常见的线性表数据结构。数组是一种静态数据结构，其元素在内存中是连续存储的，通过下标可以高效地访问元素。链表是一种动态数据结构，其元素在内存中不一定是连续存储的，通过指针来连接各个元素，在插入和删除操作中更加灵活高效。

#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建链表
Node* createLinkedList(int arr[], int size) {
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = arr[0];
    head->next = NULL;
    Node* current = head;
    
    for (int i = 1; i < size; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;
        current->next = newNode;
        current = current->next;
    }
    
    return head;
}

#### 3.2 栈与队列
栈和队列是基于数组或链表实现的常见数据结构。栈具有后进先出（LIFO）的特点，可以通过数组或链表实现。而队列具有先进先出（FIFO）的特点，同样可以通过数组或链表实现。

// 定义栈
#define MAX_SIZE 100
typedef struct Stack {
    int data[MAX_SIZE];
    int top;
} Stack;

// 定义队列
#define MAX_SIZE 100
typedef struct Queue {
    int data[MAX_SIZE];
    int front, rear;
} Queue;

#### 3.3 线性表的应用实例
线性表在实际编程中有着广泛的应用，比如实现数据结构的存储、遍历、搜索等操作，以及解决各种实际问题。其中，链表常用于动态管理内存空间，栈常用于表达式求值，队列常用于调度算法等场景。

以上是关于C语言中线性表的简要介绍，接下来我们将深入学习线性表的操作和应用。

**此为伪代码示例，未经实际编译，仅供参考。**
## 第四章：树与图

### 4.1 二叉树

在C语言中，我们可以使用结构体来表示二叉树节点，每个节点包括数据域和指向左右子节点的指针。以下是一个简单的二叉树结构的定义和基本操作的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 二叉树节点结构定义
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 二叉树的前序遍历
void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(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("前序遍历结果：");
    preorderTraversal(root);

    return 0;
}

运行结果：

前序遍历结果：1 2 4 5 3

通过以上代码，我们实现了一个简单的二叉树结构，并进行了前序遍历操作。这展示了C语言中二叉树基本操作的实现方式。

### 4.2 图的表示与遍历

C语言中，我们可以使用邻接矩阵或邻接表来表示图。邻接矩阵是一个二维数组，表示节点之间的连接关系；邻接表则是一个数组，每个元素指向一