C语言程序设计(下)：数据结构应用实例

# 1. 介绍数据结构的基本概念

### 1.1 数据结构的定义与特点

数据结构是指数据元素之间的关系和操作的集合。它是计算机科学中的一个重要概念，用于组织和存储数据，提供高效的访问和操作方式。数据结构的特点包括以下几个方面：
- 数据元素之间的逻辑关系
- 数据的存储与操作方式
- 数据结构的效率与性能

在C语言中，数据结构可以通过结构体来表示。结构体是一种用户自定义的数据类型，可以包含多个不同类型的变量，用于表示实际问题中的复杂结构。

### 1.2 数据结构在C语言中的应用

C语言是一种底层语言，对于数据结构的定义和操作提供了基本的支持。在C语言中，可以使用数组、链表、栈、队列等基本数据结构来存储和处理数据。这些数据结构可以用于解决各种实际问题，比如存储和检索大量数据、实现算法和程序的功能等。

### 1.3 基本数据结构：数组、链表、栈、队列等

1.3.1 数组（Array）
数组是一种连续的数据结构，它能够存储多个相同类型的数据元素。数组的特点包括以下几个方面：
- 定长：数组在定义时需要指定长度，长度不可改变。
- 连续存储：数组中的元素在内存中是连续存储的，可以通过下标访问和修改元素。
- 快速访问：由于元素的连续存储，通过下标可以快速访问到指定位置的元素。

在C语言中，数组的声明和定义如下：

int numbers[5]; // 声明一个整型数组，长度为5

1.3.2 链表（Linked List）
链表是一种非连续的数据结构，它由多个节点组成，每个节点包含数据和一个指向下一个节点的指针。链表的特点包括以下几个方面：
- 动态长度：链表的长度可以动态增加和删除。
- 随机访问：通过遍历链表的方式访问元素，不能直接通过下标访问。
- 灵活插入和删除：由于链表的动态性，插入和删除元素的操作比数组更灵活。

在C语言中，链表的定义和操作如下：

// 定义链表节点
struct Node {
    int data; // 数据
    struct Node* next; // 指向下一个节点的指针
};

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

1.3.3 栈（Stack）
栈是一种先进后出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。栈的特点包括以下几个方面：
- 后进先出：最后插入的元素先被删除。
- 只能在栈顶操作：只能在栈顶进行元素的插入和删除。

在C语言中，可以使用数组和链表来实现栈的功能。

1.3.4 队列（Queue）
队列是一种先进先出（FIFO）的数据结构，只能在队尾进行插入操作，在队头进行删除操作。队列的特点包括以下几个方面：
- 先进先出：最先插入的元素先被删除。
- 只能在队尾插入，队头删除：只能在队尾进行元素的插入，队头进行元素的删除。

在C语言中，可以使用数组和链表来实现队列的功能。

以上是数据结构的基本概念和C语言中常用的数据结构，接下来我们将深入学习和应用这些数据结构。

# 2. C语言中的数据结构和指针

在C语言中，数据结构和指针密切相关，指针可以很方便地操作数据结构，也可以通过指针来实现各种数据结构。本章将深入探讨数据结构的定义、声明和指针与数据结构的关系，以及如何使用指针处理数据结构的相关知识。

### 2.1 数据结构的定义和声明
在C语言中，数据结构可以通过结构体（struct）来定义和声明。结构体是一种用户自定义的数据类型，可以包含多个不同类型的成员。

#### 场景
假设我们需要定义一个学生的数据结构，包括学生的姓名、年龄和学号。我们可以通过结构体来定义这个数据结构。

#### 代码示例（C语言）：

#include <stdio.h>

// 定义学生的结构体
struct Student {
    char name[20];
    int age;
    int id;
};

int main() {
    // 声明一个学生结构体变量
    struct Student stu1;

    // 初始化学生数据
    strcpy(stu1.name, "Alice");
    stu1.age = 20;
    stu1.id = 2021001;

    // 输出学生信息
    printf("学生姓名：%s，年龄：%d，学号：%d\n", stu1.name, stu1.age, stu1.id);

    return 0;
}

#### 代码解析：
- 首先使用 `struct` 关键字定义了一个名为 `Student` 的结构体，包含了姓名、年龄和学号三个成员变量。
- 在 `main` 函数中声明了一个名为 `stu1` 的学生结构体变量。
- 使用 `strcpy` 函数给 `stu1` 的姓名赋值为 "Alice"，并分别给年龄和学号赋值。
- 最后输出学生的信息。

#### 代码总结：
通过结构体可以方便地定义和组织多个不同类型的数据，使得数据结构更加灵活，便于管理和操作。

### 2.2 指针与数据结构的关系
指针是C语言中的一个重要概念，它与数据结构有着密切的关系。通过指针，可以更灵活地操作数据结构。

#### 场景
在上面的学生数据结构的基础上，我们可以通过指针来操作学生数据，比如动态分配内存，构建链表等。

#### 代码示例（C语言）：

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

struct Student {
    char name[20];
    int age;
    int id;
};

int main() {
    // 声明一个指向学生结构体的指针
    struct Student *ptr_stu;

    // 动态分配内存
    ptr_stu = (struct Student *)malloc(sizeof(struct Student));

    // 初始化学生数据
    strcpy(ptr_stu->name, "Bob");
    ptr_stu->age = 21;
    ptr_stu->id = 2021002;

    // 输出学生信息
    printf("学生姓名：%s，年龄：%d，学号：%d\n", ptr_stu->name, ptr_stu->age, ptr_stu->id);

    // 释放内存
    free(ptr_stu);

    return 0;
}

#### 代码解析：
- 首先声明了一个指向 `Student` 结构体的指针 `ptr_stu`。
- 使用 `malloc` 函数动态分配了内存空间，然后通过指针 `ptr_stu` 来初始化学生数据。
- 最后输出学生信息，并且通过 `free` 函数释放了之前分配的内存空间。

#### 代码总结：
通过指针，我们可以动态地管理数据结构，更加灵活地操作数据。

### 2.3 使用指针处理数据结构
指针的灵活性使得我们可以通过指针来处理各种数据结构，比如链表、树等复杂的数据结构。

#### 场景
接下来，我们将通过指针来构建一个简单的链表数据结构，并对链表进行操作。

#### 代码示例（C语言）：

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

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

int main() {
    // 构建链表
    struct Node *head = NULL;
    struct Node *second = NULL;
    struct Node *third = NULL;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

    // 遍历链表并输出
    struct Node *ptr = head;
    while (ptr != NULL