# 数据结构作业

**Repository Path**: jiao001/data-structure-assignment

## Basic Information

- **Project Name**: 数据结构作业
- **Description**: No description available
- **Primary Language**: C
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2024-10-28
- **Last Updated**: 2026-09-01

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 数据结构作业

数据结构课程的完整作业代码集，使用 C / C++ 实现了线性表、链表、字符串（BF/KMP 算法）等核心数据结构。

## 项目简介

本仓库收录了数据结构课程各章节的课后作业和实验代码，涵盖线性表（顺序表 / 链表）、串的模式匹配（BF / KMP 算法）等经典主题。每个作业独立成一个 VS 工程，包含完整的实现与测试。

## 技术栈

- **语言**：C 语言 / C++
- **开发环境**：Visual Studio 2022
- **编译器**：MSVC (v143)
- **覆盖主题**：线性表、链表、串、排序算法

## 快速开始

### 环境要求

- Windows 操作系统
- Visual Studio 2019 及以上版本

### 运行方式

1. 克隆仓库
   ```bash
   git clone https://gitee.com/jiao001/data-structure-assignment.git
   ```

2. 进入对应的作业目录，使用 Visual Studio 打开 `.sln` 解决方案文件

3. 选择 x64 Debug 配置，点击运行

### 命令行编译（可选）

```bash
# 使用 MSVC
cl /EHsc test.c

# 或使用 GCC
gcc test.c -o test
```

## 目录结构

```
data-structure-assignment/
│
├── 数据结构国庆作业/                              # 线性表与链表相关作业
│   ├── 第二章/                                    # 第二章：线性表
│   │   ├── List.c                                 # 链表实现
│   │   └── 第二章.sln
│   │
│   ├── DeleteSeqlist/                             # 删除顺序表中的元素
│   │   ├── DeletsSeqlist.c
│   │   └── DeleteSeqlist.sln
│   │
│   ├── ListDelete/                                # 链表删除
│   │   ├── ListDelete.c
│   │   └── ListDelete.sln
│   │
│   ├── MergeList/                                 # 合并两个有序链表
│   │   ├── MergeList.c
│   │   └── MergeList.sln
│   │
│   ├── SortList/                                  # 链表排序
│   │   ├── SortList.c
│   │   └── SortList.sln
│   │
│   ├── 链表作业/
│   │   └── 链表/                                  # 链表综合作业（C++）
│   │       ├── List.h                             # 链表头文件
│   │       ├── List.cpp                           # 链表实现
│   │       └── test.cpp                           # 测试程序
│   │
│   ├── 数据结构/                                   # 综合测试
│   │   ├── test.c
│   │   └── 数据结构.sln
│   │
│   ├── test2/                                     # 测试工程 2
│   │   ├── test3.cpp
│   │   └── test2.sln
│   │
│   └── 作业/                                      # 综合作业
│       ├── test2.c
│       └── 作业.sln
│
├── 串（第四章）/                                   # 第四章：串的模式匹配
│   └── test/
│       ├── test01.c                               # 串基本操作测试
│       ├── test02.c                               # 串匹配测试
│       ├── test03.c                               # 串操作进阶
│       ├── test04Brute-Force 算法.c               # BF 暴力匹配算法
│       ├── test05KMP 算法.c                       # KMP 模式匹配算法
│       └── test01.sln
│
├── .vs/                                           # VS 缓存目录
└── README.md
```

## 作业说明

### 第二章：线性表

| 作业 | 文件 | 功能 |
|------|------|------|
| **链表实现** | `第二章/List.c` | 单链表的基本操作（增删改查） |
| **顺序表删除** | `DeleteSeqlist/` | 从顺序表中删除指定元素 |
| **链表删除** | `ListDelete/` | 删除链表中符合条件的节点 |
| **有序链表合并** | `MergeList/` | 将两个递增有序链表合并为一个有序链表 |
| **链表排序** | `SortList/` | 对链表进行排序 |
| **链表综合作业** | `链表作业/链表/` | 使用 C++ 类封装链表，包含完整实现 |

### 第四章：串的模式匹配

| 作业 | 文件 | 算法 |
|------|------|------|
| **串基本操作** | `test01~03.c` | 字符串的创建、拼接、截取等 |
| **BF 暴力匹配** | `test04Brute-Force 算法.c` | 时间复杂度 O(n×m) |
| **KMP 算法** | `test05KMP 算法.c` | 时间复杂度 O(n+m)，需构建 next 数组 |

## 核心算法

### BF 暴力匹配（Brute-Force）

```
朴素的模式匹配算法：
- 从主串的第 i 个位置开始，与模式串逐个字符比较
- 遇到不匹配则 i 回溯，模式串从头开始
- 时间复杂度：O(n × m)
```

### KMP 算法

```
改进的模式匹配算法：
- 通过 next 数组记录模式串的最长公共前后缀
- 匹配失败时利用 next 数组跳过不必要的比较
- 时间复杂度：O(n + m)
- 核心：构建 next / nextval 数组
```

### 链表操作

```c
typedef struct LNode {
    int data;               // 数据域
    struct LNode *next;     // 指针域
} LNode, *LinkList;
```

| 操作 | 说明 | 时间复杂度 |
|------|------|-----------|
| `InitList` | 初始化链表 | O(1) |
| `GetElem` | 按位查找 | O(n) |
| `LocateElem` | 按值查找 | O(n) |
| `ListInsert` | 指定位置插入 | O(n) |
| `ListDelete` | 指定位置删除 | O(n) |
| `MergeList` | 合并有序链表 | O(n + m) |

## 学习要点

- **线性表**：顺序存储 vs 链式存储的优缺点对比
- **链表**：头插法、尾插法建表，指针操作注意事项
- **串匹配**：BF 算法的回溯思想，KMP 算法的 next 数组构建
- **算法分析**：时间复杂度与空间复杂度分析

## 许可证

本项目仅供学习交流使用。