# DataStructureProgrammingUsingC

**Repository Path**: cqjtu_rory/data-structure-programming-using-c

## Basic Information

- **Project Name**: DataStructureProgrammingUsingC
- **Description**: c语言实现各种数据结构与算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2020-09-12
- **Last Updated**: 2022-02-28

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 简述
复习备考时加深算法理解时所写，记之以念，或为后来人些许借鉴，水平有限望斧正。
main.c多为测试头文件算法的测试代码。

每个逻辑结构的代码结构最初的构想是使用面向对象的思想进行实现，后来越写越觉得不太妥，
还是把这种事交给c++吧。对于测试函数的结构也有改进，从原来的命名混乱到后来的使用宏
进行封装使得代码更简洁，也更可读。

某些逻辑结构的物理结构并没有实现，一方面当然是lazy啦，另方面是考虑到时间有限，只挑了
自己薄弱的和觉得重要的进行实现。

### 图--graph
使用邻接矩阵作为存储结构，采用面向对象的设计思想，在图结构体的内部封装函数指针来表示成员函数。
已完成的算法有
* Prim算法
* Dijkstra算法

### 查找--search 
* 折半查找的递归算法

### 排序--sort
* 插入排序
    * 直接插入排序
    * 希尔排序
        
        一般教材对于子表的排序是交叉进行，即先排序子表一的第一个元素，然后排序子表二的第一个元素，然后排序子表一的第二个的元素...。
        而本算法是次序进行，先排序子表一的所有元素，然后排序子表二的所有元素，然后...
* 交换排序
    * 冒泡排序
 
* 快速排序
    * 递归快排
    * 利用栈实现的迭代快排
        
        在百万级数据规模下，比递归快排平均大概慢0.1s
     
### 顺序栈--stack
* 顺序栈

    main.c中编写了一揽子括号匹配检查算法

### 链式栈与栈的应用--linkedstack
这部分的代码直接把以前上数据结构用c++写的代码拿过来了。
* 栈的应用
    * 括号匹配检验(带纠错标记)
    * 中缀表达式转后缀表达式
    * 计算后缀表达式
    * 反转字符串

    
### 队列--queue
* 顺序循环队列

### 串的匹配--string
* 暴力匹配算法(简单匹配)
* KMP算法
* 优化的KMP算法

### 二叉树--binarytree
* 线索二叉树

### 编程题--programming
做编程题真题时觉得有必要验算代码结果的题