5、队列

队列：队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。

与栈结构不同的是，队列的两端都"开口"，要求数据只能从一端进，从另一端出，如图 1 所示：

通常，称进数据的一端为 "队尾"，出数据的一端为 "队头"，数据元素进队列的过程称为 "入队"，出队列的过程称为 "出队"。

不仅如此，队列中数据的进出要遵循 "先进先出" 的原则，即最先进队列的数据元素，同样要最先出队列。

拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。

此时如果将元素 3 出队，根据队列 "先进先出" 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。

栈和队列不要混淆，栈结构是一端封口，特点是"先进后出"；而队列的两端全是开口，特点是"先进先出"。

因此，数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。

如下示例：

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
int enQueue(int *a, int rear, int data){
    a[rear] = data;
    rear++;
    return rear;
}
void deQueue(int *a, int front, int rear){
    //如果 front==rear，表示队列为空
    while (front != rear) {
        printf("出队元素：%d\n", a[front]);
        front++;
    }
}
int main() {
    int a[100];
    int front, rear;
    //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址
    front = rear = 0;
    //入队
    rear = enQueue(a, rear, 1);
    rear = enQueue(a, rear, 2);
    rear = enQueue(a, rear, 3);
    rear = enQueue(a, rear, 4);
    //出队
    deQueue(a, front, rear);
    system("PAUSE");//结束不退出
}

6、散列表（哈希表）

散列表：散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，
这样就可以不用进行比较操作而直接取得所查记录。

构造散列函数考虑的因素：

执行速度
关键字长度
散列表大小
关键字的分布情况
查找频率

根据元素集合的特性构造

要求一：n 个数据原仅占用 n 个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小
要求二：无论用什么方法储存，目的都是尽量均匀地存放元素，以避免冲突

解决冲突的办法：

直接定址法
(取关键字的某个线性函数值为散列地址：f (key) = a*key + b )
简单、均匀也不会有冲突但需要事先知道关键字的排布，适合表较小且连续的情况
数字分析法
平方取中法
折叠法
除留取余法
Hash(key) = key % p (p 是整数)，设表长为 m ，取 p <= m 且为质数
随机数法

结构：

#define MAXSIZE 1000
#define NULLKEY -65535
typedef struct
{
    int* elem;  //数据元素存储基址，数组
    int size;  //元素个数
}HashTable;
int m = 0;//散列表表长

散列表的创建：

void IniHashTable(HashTable* H)
{
    int i;
    m = MAXSIZE;
    H->size = m;
    H->elem = (int*)malloc(m* sizeof(int));
    for (i = 0; i < m; i++)
    {
        H->elem[i] = NULLKEY;
    }
}

散列函数：

根据不同的情况改变算法

int Hash(int key)
{
    return key % m;  //除留取余法
}

插入元素：

void InsertHash(HashTable* H, int key)
{
    int addr = Hash(key);  //求散列地址
    while (H->elem[addr] != NULLKEY)  //不为空则冲突
    {
        addr = (addr + 1) % m;  //开放地址法的线性探测
    }
    H->elem[addr] = key;  //发现有空位后插入
}

查找元素：

int Search(HashTable* H, int key)
{
    int addr = Hash(key);  //求散列地址
    while (H->elem[addr] != key)  //不为空则冲突
    {
        addr = (addr + 1) % m;   //开放地址法的线性探测
        if (H->elem[addr] == NULLKEY || addr == Hash(key))
        {
            return false;
        }
    }    
    return true;
}

7、二叉树

二叉树：二叉树是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。
二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

二叉排序树要么是空二叉树，要么具有如下特点：

二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
二叉排序树的左右子树也要求都是二叉排序树；

例如，图 1 就是一个二叉排序树：

使用二叉排序树查找关键字

二叉排序树中查找某关键字时，查找过程类似于次优二叉树，在二叉排序树不为空树的前提下，首先将被查找值同树的根结点进行比较，会有 3 种不同的结果：

如果相等，查找成功；
如果比较结果为根结点的关键字值较大，则说明该关键字可能存在其左子树中；
如果比较结果为根结点的关键字值较小，则说明该关键字可能存在其右子树中；

实现函数为：（运用递归的方法）

BiTree SearchBST(BiTree T,KeyType key){
    //如果递归过程中 T 为空，则查找结果，返回NULL；或者查找成功，返回指向该关键字的指针
    if (!T || key==T->data) {
        return T;
    }else if(key<T->data){
        //递归遍历其左孩子
        return SearchBST(T->lchild, key);
    }else{
        //递归遍历其右孩子
        return SearchBST(T->rchild, key);
    }
}

使用二叉排序树在查找表中做查找操作的时间复杂度同建立的二叉树本身的结构有关。即使查找表中各数据元素完全相同，但是不同的排列顺序，构建出的二叉排序树大不相同。

例如：查找表 {45，24，53，12，37，93} 和表 {12，24，37，45，53，93} 各自构建的二叉排序树图下图所示：

使用二叉排序树实现动态查找操作的过程，实际上就是从二叉排序树的根结点到查找元素结点的过程，所以时间复杂度同被查找元素所在的树的深度（层次数）有关。

为了弥补二叉排序树构造时产生如图 5 右侧所示的影响算法效率的因素，需要对二叉排序树做“平衡化”处理，使其成为一棵平衡二叉树。

更多详情点击二叉排序树（二叉查找树）及C语言实现

8、跳表

跳表：跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。

跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn)。跳表的空间复杂度是 O(n)。

不过，跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

详细见：跳表C语言实现详解

9、图

图：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。

使用图结构表示的数据元素之间虽然具有“多对多”的关系，但是同样可以采用顺序存储，也就是使用数组有效地存储图。

使用数组存储图时，需要使用两个数组，一个数组存放图中顶点本身的数据（一维数组），另外一个数组用于存储各顶点之间的关系（二维数组）。

存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。

不同类型的图，存储的方式略有不同，根据图有无权，可以将图划分为两大类：图和网。

图，包括无向图和有向图；

网，是指带权的图，包括无向网和有向网。

存储方式的不同，指的是：在使用二维数组存储图中顶点之间的关系时，如果顶点之间存在边或弧，在相应位置用 1 表示，反之用 0 表示；

如果使用二维数组存储网中顶点之间的关系，顶点之间如果有边或者弧的存在，在数组的相应位置存储其权值；反之用 0 表示。

结构代码表示：

#define MAX_VERtEX_NUM 20                   //顶点的最大个数
#define VRType int                          //表示顶点之间的关系的变量类型
#define InfoType char                       //存储弧或者边额外信息的指针变量类型
#define VertexType int                      //图中顶点的数据类型
typedef enum{DG,DN,UDG,UDN}GraphKind;       //枚举图的 4 种类型
typedef struct {
    VRType adj;                             //对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        //弧或边额外含有的信息指针
}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];
typedef struct {
    VertexType vexs[MAX_VERtEX_NUM];        //存储图中顶点数据
    AdjMatrix arcs;                         //二维数组，记录顶点之间的关系
    int vexnum,arcnum;                      //记录图的顶点数和弧（边）数
    GraphKind kind;                         //记录图的种类
}MGraph;

例如，存储图 1 中的无向图（B）时，除了存储图中各顶点本身具有的数据外，还需要使用二维数组存储任意两个顶点之间的关系。

由于（B）为无向图，各顶点没有权值，所以如果两顶点之间有关联，相应位置记为 1 ；反之记为 0 。构建的二维数组如图 2 所示。

在此二维数组中，每一行代表一个顶点，依次从 V1 到 V5 ，每一列也是如此。比如 arcs[0][1] = 1 ，表示 V1 和 V2 之间有边存在；而 arcs[0][2] = 0，说明 V1 和 V3 之间没有边。

对于无向图来说，二维数组构建的二阶矩阵，实际上是对称矩阵，在存储时就可以采用压缩存储的方式存储下三角或者上三角。

通过二阶矩阵，可以直观地判断出各个顶点的度，为该行（或该列）非 0 值的和。例如，第一行有两个 1，说明 V1 有两个边，所以度为 2。

存储图 1 中的有向图（A）时，对应的二维数组如图 3 所示：

更多详情点击图的顺序存储结构（包含C语言实现）

10、Trie树

Trie树：又称单词查找树，Trie树，字典树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），

所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

如下代码，定义结构体、初始化Trie树、插入、查找、删除：

#define _CRT_SECURE_NO_WARNINGS  //避免scanf报错
#include <stdio.h>
#define MAX 26    //26个字母
#define SLEN 100   //节点中存储的字符串长度
//Trie结构体定义
struct Trie
{
    struct Trie *next[MAX];
    char s[SLEN];      //节点处存储的字符串
    int isword;         //节点处是否为单词
    char val;           //节点的代表字符
} *root;
//初始化Trie树
struct Trie *init()
{
    struct Trie *root = (struct Trie *)malloc(sizeof(struct Trie));
    int i;
    for (i = 0; i < MAX; i++)
    {
        root->next[i] = NULL;
    }
    root->isword = 0;
    root->val = 0;
    return root;
}
//按照指定路径path 插入字符串 s
void insert(char path[], char s[])
{
    struct Trie *t, *p = root;
    int i, j, n = strlen(path);
    for (i = 0; i < n; i++)
    {
        if (p->next[path[i] - 'a'] == NULL)
        {
            t = (struct Trie *)malloc(sizeof(struct Trie));
            for (j = 0; j < MAX; j++)
            {
                t->next[j] = NULL;
                t->isword = 0;
            }
            t->val = path[i];
            p->next[path[i] - 'a'] = t;
        }
        p = p->next[path[i] - 'a'];
    }
    p->isword = 1;
    strcpy(p->s, s);
}
//按照指定路径 path 查找
char *find(char path[], int delflag)
{
    struct Trie *p = root;
    int i = 0, n = strlen(path);
    while (p && path[i])
    {
        p = p->next[path[i++] - 'a'];
    }
    if (p && p->isword)
    {
        p->isword = delflag;
        return p->s;
    }
    return NULL;
}
//删除整棵Trie树
void del(struct Trie *root)
{
    int i;
    if (!root)
        return;
    for (i = 0; i < MAX; i++)
    {
        if (root->next[i])
            del(root->next[i]);
        free(root->next[i]);
    }
}