C/C++『数据结构』

引言

1.数据结构

什么是数据结构？数据结构就是相互之间存在的一种或者多种特定关系的数据元素集合。

2.数据结构的分类

按照视点不同分成逻辑结构和物理结构两种：

2.1 逻辑结构

逻辑结构是值数据对象中各个数据元素之间的相互关系。其大致可分为一下四种：

集合结构：集合结构当中数据元素除同属一个集合外它们之间没任何关系。
线性结构：线性结构当中数据元素之间是一对一关系。
树形结构：树形结构当中数据元素之间存在一对多的层次关系。
图形结构：图形结构当中数据元素之间存在多对多关系。

2.2 物理结构

物理结构是指数据的逻辑结构在计算机当中的存储形式。其大致可分为一下两种：

顺序存储结构

顺序存储结构是把数据元素存放在地址连续的存储单元中，其数据间的逻辑关系与物理关系保持一致。

链式存储结构

链式存储结构是把数据元素存在任意存储单元中。其存储单元可以连续也可以不连续。这就意味着数据存在哪里并不重要，只要用一个指针存储地址信息便能查找到它。

分类介绍

数据结构按照存储结构可大致分为：

线性表，具体的还可细分为顺序表（可近似理解为数组）、链表、栈和队列、串；
树结构，包括普通树，二叉树，线索二叉树等；
图结构。

1.线性表

线性表是什么？线性表就是由零个或者多个数据元素组成的有限序列。其各元素依次排列，每个元素的前面和后边有且仅有一个元素与之相邻（首元素和尾元素除外）。

注：线性表不只有一种存储结构，它包含了顺序存储结构和链式存储结构两种表述方式，是顺序表和链表的统称。作为特殊的线性表，栈和队列同样有顺序存储结构和链式存储结构两种表述方式

顺序表：是线性表的顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素。顺序表结构的底层实现借助的是数组，可以把顺序表近似等价为数组。

注：数据结构是研究数据存储方式的，它囊括的都是各种存储结构，而数组只是各种编程语言中的基本数据类型，并不属于数据结构的范畴。

链表：是线性表的链式存储结构，即用一组任意的存储单元存储线性表的数据结构。
栈和队列：栈和队列是特殊的线性表，因为它们对线性表的数据元素进出做出明确要求。栈是限定仅在表尾进行插入删除操作的线性表，又称为后进先出（LIFO）的线性表；而队列则是限定在表的一端进行插入操作，表的另一端进行删除操作的线性表，队列又称为先进先出（FIFO）的线性表。
串：又叫字符串，是由另个或者多个多个字符组成的有限序列。

2.树结构

树（Tree）是 n（n≥0）个节点的有限集。树结构是典型的一对多关系。

当 n = 0 时称为空树；

当 n ≠ 0 时的非空树中：

有且仅有一个特定的节点称为根节点（Root）；
当 n > 1 时，其余节点可以分割成若干个互不相交的子集，其每个集合本身也为一棵树，这棵树便是根的子树（SubTree）。

特别的，当所有的节点的子集都不超过两个时称为二叉树。

特别的，堆是特殊的二叉树，即堆是完全二叉树。

3.图结构

图是由定点的有穷非空集合与顶点之间边的集合组成，通常可表示为 G(V,E) ，其中 G 表示一个图，V 表示 G 当中定点的集合，E 表示 G 当中边的集合。图结构是典型的多对多关系。

4.顺序表、树、图的关系

线性表可以没有数据元素，称空表；树可以没有结点，称空树；而图当中不能没有顶点，因此图必须是有穷非空的。

存储类型	数据元素名称	相邻数据元素关系
线性表	元素 (Element)	线性关系
树	结点 (Node)	层次关系
图	顶点 (Vertex)	边（边集可以为空）

一.顺序表（数组）

顺序表（SeqList）：是线性表的顺序存储结构，用一段地址连续的存储单元依次存储线性表的数据元素。顺序表结构的底层实现借助的是数组。顺序表的C++代码实现可参考如下链接：顺序表（SeqList）的初始化、增、删、查、改等

二.链表

链表（Linked List）：是线性表的链式存储结构，用一组任意的存储单元存储线性表的数据结构。

常用的链表建立方式：

头插法（逆序建立链表）
尾插法（正序建立链表）

2.1 单链表

结点定义

// 结点定义
typedef int SLTData; // 定义单链表数据域类型
typedef struct SLTNode
{
    SLTData data;  // 数据域
    SLTNode *next; // 指针域
} SListNode;

创建单链表结点

// 创建单链表结点
SListNode *SLTNode_Create(SLTData x)
{
    SListNode *newNode = (SListNode *)malloc(sizeof(SListNode));
    if (newNode == NULL)
    {
        perror("内存申请失败");
        return;
    }
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

插入操作

// 插入	头插，尾插，指定pos前插，指定pos后插
// 单链表头插法
void SLT_PushFront(SListNode **pphead, SLTData x)
{
    assert(pphead);
    SListNode *newnode = SLTNode_Create(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

// 单链表尾插法
void SLT_PushBack(SListNode **pphead, SLTData x)
{
    assert(pphead); // 断言，验证pphead的合法性
    SListNode *newnode = SLTNode_Create(x);
    // 1.链表为空
    if (*pphead == NULL)
    {
        *pphead = newnode;
        // 不需要让newnode->next=NULL,在SLTNode_Create函数中已经进行过此操作
    }
    // 2.链表不为空
    else
    {
        // 找到链表的尾巴tail
        SListNode *tail = *pphead;
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

// 单链表在指定pos前插入
void SLTInsertFront(SListNode **pphead, SListNode *pos, SLTData x)
{
    assert(pphead);
    assert(pos);

    SListNode *newnode = SLTNode_Create(x);
    // 头插
    if ((*pphead)->next == pos)
    {
        newnode->next = *pphead;
        *pphead = newnode;
    }
    // 非头插
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
            assert(prev->next);
        }
        newnode->next = pos;
        prev->next = newnode;
    }
}

// 单链表在指定pos后插入
void SLTInsertBack(SListNode *phead, SListNode *pos, SLTData x)
{
    assert(pos);
    SListNode *cur = phead;
    // 防止pos传错了
    while (cur != pos)
    {
        cur = cur->next;
        assert(pos);
    }
    SListNode *newnode = SLTNode_Create(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

删除操作

// 删除  头删，尾删，在指定pos删
// 单链表头删法
void SLT_PopFront(SListNode **pphead)
{
    assert(pphead);
    assert(*pphead);
    SListNode *cur = *pphead;
    *pphead = (*pphead)->next;
    free(cur);
    cur = NULL;
}

// 单链表尾删法
void SLT_PopBack(SListNode **pphead)
{
    assert(pphead);
    assert(*pphead);
    // 1.链表只有一个元素
    // 2.链表有两个及两个以上的元素
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SListNode* tail = *pphead;
        while (tail->next->next)
        {
        tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

// 删除某个结点
void SLT_PosErase(SListNode **pphead, SListNode *pos)
{
    assert(pphead);
    assert(pos);
    // 头删

    if (*pphead == pos)
    {
        SListNode *cur = *pphead;
        *pphead = (*pphead)->next;
        free(cur);
        cur = NULL;
    }
    // 非头删
    else
    {
        SListNode *prev = *pphead;
        while (prev->next != pos)
        {
            prev = prev->next;
            assert(prev->next);
        }
        prev->next = pos->next;
        free(pos);
    }
}

修改操作

// 单链表结点修改
void SLT_Alter(SLTNode *phead, SLTNode *pos, SLTData x)
{
    SLTNode *cur = phead;
    while (cur != pos)
    {
        cur = cur->next;
        assert(cur);
    }
    pos->data = x;
}

查找操作

// 单链表结点查找
SListNode *SLT_Search(SListNode *phead, SLTData x)
{
    SListNode *cur = phead;
    while (cur)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

单链表打印

// 打印单链表
void SLT_Print(SListNode *phead)
{
    SListNode *cur = phead;
    while (cur)
    {
        cout << "%d->" << cur->data; // 打印当前结点
        cur = cur->next;             // 指针指向下一个节点
    }
    cout << "NULL" << endl;
    // 最后打印出来的效果如同 1->2->3->4->NULL
}

单链表销毁

// 销毁链表
void SLT_Destory(SListNode **pphead)
{
    assert(pphead);
    SListNode *cur = *pphead;
    while (cur)
    {
        SListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    *pphead = NULL;
}

2.2 双向链表

2.3 循环链表

2.4 静态链表

三.栈

栈（Stack）：是限定仅在表尾进行插入删除操作的线性表。栈是一种后进先出的线性表，称为 LIFO 。

3.1 栈的顺序存储结构

栈基本参数的定义

由于静态容量的栈结构实际上并不实用，因此下面主要实现动态容量的顺序栈。

// 定义顺序栈的参数
typedef int Stack_DataType; // 栈中元素类型重命名为int

// 静态容量栈结构
#define Stack_Capacity 20 // 栈容量设定
struct Stack
{
    Stack_DataType st[Stack_Capacity]; // 定长数组
    int top;                           // 记录栈顶位置
} Static_SeqStack;

// 动态容量栈结构
typedef struct Stack
{
    Stack_DataType *st; // 指向动态开辟的数组
    int top;            // 记录栈顶位置
    int capacity;       // 栈容量设定
} Dynamic_SeqStack;

栈的初始化

// 初始化栈
void Stack_Init(DynamicStack *dst)
{
    assert(dst);
    dst->a = NULL;
    dst->top = -1;
    dst->capacity = 0;
}

栈的销毁

// 销毁栈
void Stack_Destroy(DynamicStack *dst)
{
    assert(dst);

    if (dst->a)
    {
        free(dst->a);
    }
    dst->a = NULL;
    dst->top = -1;
    dst->capacity = 0;
}

入栈操作

// 入栈
void Stack_Push(DynamicStack *dst, Stack_DataType x)
{
    assert(dst);
    if (dst->top == dst->capacity - 1) // 检查栈空间是否满了
    {
        // 如果栈原始容量为0，新容量设为4，否则设为原始容量的2倍
        int newcapacity = (dst->capacity == 0) ? 4 : (dst->capacity) * 2;
        // 扩容至新容量
        Stack_DataType *temp = (Stack_DataType *)realloc(dst->a, newcapacity * sizeof(Stack_DataType));
        if (temp == NULL)
        {
            perror("申请内存失败");
            exit(-1);
        }
        dst->a = temp;
        // 更新容量
        dst->capacity = newcapacity;
    }
    dst->top++;           // 栈顶指针加一
    dst->a[dst->top] = x; // 将新增元素放入栈顶空间
}

出栈操作

// 出栈
void Stack_Pop(DynamicStack *dst)
{
    assert(dst);
    assert(dst->top != -1); // 栈不能为空

    dst->top--; // 栈顶指针减一
}

检测栈是否为空

// 检测栈是否为空，如果为空返回true，否则返回NULL
bool Stack_isEmpty(DynamicStack *dst)
{
    assert(dst);
    return dst->top == -1;
}

获取栈中有效元素个数

// 获取栈中有效元素个数
int Stack_Size(DynamicStack *dst)
{
    assert(dst);
    return dst->top + 1;
}

获取栈顶元素

// 获取栈顶元素
Stack_DataType Stack_Top(DynamicStack *dst)
{
    assert(dst);
    assert(!Stack_isEmpty(dst)); // 栈不能为空

    return dst->a[dst->top];
}

3.2 栈的链式存储结构

由于栈只允许在表尾进行插入和删除元素操作。可以将单链表的尾部作为栈底，头部作为栈顶，方便插入和删除（进栈头插，出栈头删），这样头指针 head 和栈顶指针 top 就合二为一。

栈的基本参数定义

// 定义链式栈的参数
typedef int LinkStack_DataType; // 队列中元素类型重命名为int
// 定义链式栈的链表结点
typedef struct LinkStackNode
{

    LinkStack_DataType data; // 数据域
    LinkStackNode *next;     // 指针域
} *LinkStackPtr;

// 定义栈的链式结构
typedef struct LinkStack
{
    LinkStackNode *top;          // 栈顶结点(表示整个链表的内存初始地址)
    LinkStack_DataType capacity; // 栈容量
} LinkStack;

链式栈的初始化

// 初始化链式栈
LinkStack *LinkStack_Init()
{
    LinkStack *mystack = (LinkStack *)malloc(sizeof(LinkStack));
    mystack->capacity = 0;
    LinkStackNode *newNode = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    newNode->next = NULL;
    mystack->top = newNode;
    return mystack;
}

链式栈的摧毁

// 摧毁链式栈
void LinkStack_Destory(LinkStack *ls)
{
    assert(ls);
    LinkStackNode *cur = ls->top;
    while (cur)
    {
        LinkStackNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(ls);
    ls = NULL;
}

入栈操作

// 入栈操作
void LinkStack_Push(LinkStack *mystack, LinkStack_DataType data)
{
    // 创建一个临时结点
    LinkStackNode *newNode = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    newNode->data = data;
    newNode->next = mystack->top->next;
    mystack->top->next = newNode;
    mystack->capacity++;
}

出栈操作

// 出栈操作
void LinkStack_Pop(LinkStack *mystack)
{
    if (mystack->capacity == 0)
    {
        cout << "无法出栈";
    }
    else
    {
        // 创建一个临时结点
        LinkStackNode *newNode = mystack->top->next;
        mystack->top->next = newNode->next;
        newNode = NULL;
        free(newNode);
        mystack->capacity--;
    }
}

判断栈是否为空

// 判断栈是否为空
bool LinkStack_isEmpty(LinkStack *mystack)
{
    return (bool)!mystack->capacity;
}

获取栈顶元素

// 获取栈顶元素
int LinkStack_Top(LinkStack *mystack)
{
    if (mystack->capacity == 0)
    {
        return -1;
    }
    return mystack->top->next->data;
}

获取栈中有效元素个数

// 获取栈中有效元素个数
int LinkStack_Size(LinkStack *mystack)
{
    assert(mystack);
    return mystack->capacity;
}

3.3 栈的应用

栈可应用于递归和四则运算

注：递归和迭代的区别

递归：要解决一个问题，递归的思想是将这一问题通过递推式转换成另一小范围的表示，通过层层递归到达解决一个递归尽头的问题，然后层层返回解决这一问题

迭代：要解决一个问题，迭代的思想是初始条件，通过初始条件以及一个递推式一次一次迭代，最终解决这一问题

四.队列

队列（Queue）：是限定表的一端进行插入操作，表的另一端进行删除操作的线性表。队列是一种先进先出的线性表，称为 FIFO 。

队列的顺序结构

入队操作，不需要移动任何元素，时间复杂度为O(1)

出队操作，所有元素需要往前移动，时间复杂度为O(N)

队列的链式结构

首先我们定义两个指针，队头指针指向第一个节点，队尾指针指向尾节点

入队操作（尾插），时间复杂度为O(1)

出队操作（头删），时间复杂度为O(1)

4.1 队列的顺序存储结构

顺序队列的定义

// 定义顺序队列的参数
typedef int Queue_DataType; // 队列中元素类型重命名为int

// 静态容量队列结构
#define Queue_Capacity 20 // 队列容量设定
typedef struct StaticSeqQueue
{
    Queue_DataType *base; // 队列基地址
    int front;            // 记录队首
    int rear;             // 记录队尾
} SeqQueue;

初始化顺序队列

// 初始化顺序队列
void SeqQueue_Init(SeqQueue *dQ)
{
    // 为顺序队列开辟存储空间
    dQ->base = (Queue_DataType *)malloc(sizeof(Queue_DataType) * Queue_Capacity);
    assert(dQ->base != NULL);
    // 初始化时，队头和队尾都在0位置
    dQ->front = dQ->rear = 0;
}

入队操作

// 入队操作
void SeqQueue_Push(SeqQueue *sQ, Queue_DataType x)
{
    // 判断队列是否还有存储空间
    if (sQ->rear >= Queue_Capacity)
        return;
    // 如果还有存储空间，将数据入队
    sQ->base[sQ->rear++] = x;
}

出队操作

// 出队
void SeqQueue_pop(SeqQueue *sQ)
{
    // 判断队列中的元素是否为空
    if (sQ->front == sQ->rear)
        return;
    // 如果队列中的元素不为空，进行出队操作
    sQ->front++;
}

队列容量和队首元素的访问

// 获取队列元素个数
int SeqQueue_Capacity(SeqQueue *sQ)
{
    //也可以将Capacity字段直接整合到队列结构体中
    // 将尾指针位置减去头指针的位置就是队列中元素的个数
    return (sQ->rear - sQ->front);
}

// 获取队首元素
void SeqQueue_Front(SeqQueue *sQ, Queue_DataType *v)
{
    // 判断队列中的元素是否为空
    if (sQ->front == sQ->rear)
        return;
    // 如果队列中的元素不为空，取出队头元素
    *v = sQ->base[sQ->front];
}

打印顺序队列的元素

// 打印顺序队列中的元素
void SeqQueue_Print(SeqQueue *sQ)
{
    // 遍历队头到队尾中的每个元素，并将其打印输出
    for (int i = sQ->front; i < sQ->rear; ++i)
    {
        cout << sQ->base[i] << " ";
    }
    cout << endl;
}

队列的清空与销毁

// 清空队列
void SeqQueue_Clear(SeqQueue *sQ)
{
    // 将队头指针和队尾指针都重置为0
    sQ->front = sQ->rear = 0;
}

// 销毁队列
void SeqQueue_Destroy(SeqQueue *sQ)
{
    // 释放队列的存储空间
    free(sQ->base);
    // 将队列空间的位置指针置空
    sQ->base = NULL;
}

4.2 队列的链式存储结构

链式队列结点定义

// 队列的定义

typedef int Queue_DataType; // 队列中元素类型重命名为int

// 定义队列链式结点
typedef struct QueueNode
{
    Queue_DataType data;    // 节点数据
    struct QueueNode *next; // 节点指针
} QueueNode;

// 定义队列的链式结构
typedef struct QueuePtr
{
    QueueNode *phead; // 队头指针
    QueueNode *ptail; // 队尾指针
} LinkQueue;

判定队列是否为空

// 检查队列是否为空，若为空返回true，否则返回false
bool Queue_isEmpty(LinkQueue *pQ)
{
    assert(pQ);
    return pQ->phead == NULL && pQ->ptail == NULL;
}

链式队列的初始化

// 初始化队列
void Queue_Init(LinkQueue *pQ)
{
    assert(pQ);
    // 队列为空
    pQ->phead = pQ->ptail = NULL;
}

链式队列的销毁

// 销毁队列
void Queue_Destroy(LinkQueue *pQ)
{
    assert(pQ);

    QueueNode *cur = pQ->phead;
    while (cur) // 遍历链式队列
    {
        QueueNode *next = cur->next;
        free(cur);
        cur = next;
    }
    cur = NULL;
    pQ->phead = pQ->ptail = NULL; // 队列为空
}

链式队列的入队操作

// 入队（尾插法）
void Queue_Push(LinkQueue *pQ, Queue_DataType x)
{
    assert(pQ);

    QueueNode *newnode = (QueueNode *)malloc(sizeof(QueueNode)); // 动态申请一个节点
    if (newnode == NULL)
    {
        perror("动态申请失败");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL; // 尾节点next指针置空

    if (pQ->phead == NULL) // 队列为空
    {
        pQ->phead = newnode;
    }
    else // 队列不为空
    {
        pQ->ptail->next = newnode;
    }
    pQ->ptail = newnode; // 更新队尾指针
}

链式队列的出队操作

// 出队（头删法）
void Queue_Pop(LinkQueue *pQ)
{
    assert(pQ);
    assert(!Queue_isEmpty(pQ)); // 队列不能为空

    if (pQ->phead == pQ->ptail) // 队列中只有一个节点
    {
        free(pQ->phead);
        pQ->phead = pQ->ptail = NULL;
    }
    else
    {
        QueueNode *next = pQ->phead->next; // 记录头节点的直接后继
        free(pQ->phead);                   // 释放头节点
        pQ->phead = next;                  // 更新队头指针
    }
}

链式队列元素个数统计

// 获取队列元素个数
// 如果会频繁调用此接口函数，可以在QueuePtr结构体中加一个size字段记录数据个数
int Queue_Size(LinkQueue *pQ)
{
    assert(pQ);
    int size = 0;
    QueueNode *cur = pQ->phead;
    while (cur) // 遍历链表
    {
        size++;
        cur = cur->next;
    }
    return size;
}

链式队列的访问

// 链式队列元素查询
// 获取队头元素
Queue_DataType QueueFront(LinkQueue *pQ)
{
    assert(pQ);
    assert(!Queue_isEmpty(pQ)); // 队列不能为空

    return pQ->phead->data;
}

// 队列为空是获取不了队尾元素的
// 获取队尾元素
Queue_DataType QueueBack(LinkQueue *pQ)
{
    assert(pQ);
    assert(!Queue_isEmpty(pQ)); // 队列不能为空

    return pQ->ptail->data;
}

4.3 循环队列

循环队列就是将正常的队列的队首与队尾相连形成一个循环。同普通队列一样，循环队列依然存在顺序存储结构与链式存储结构，本文便不作更多代码阐述。

注意：

循环队列中，tail 永远指向最后一个元素的下一个位置；

循环队列中，永远要多开一个存储空间。

五.串（字符串）

串（String）：是由另个或者多个多个字符组成的有限序列，又称字符串。零个字符的串称为空串，可直接用 “” 表示。

注：区分 char[]（或者char *）与 string：

char[]（char *）是一组 char 类型字符变量组成的，它就是一个数组，每个单元里面放一个字符数据；

string 是一个整体，以字符 ‘\0’ 作为分隔标识结尾，而且它还有很多类函数可以调用使用。

C++中有大量的字符串操作函数：

//复制字符串 s2 到字符串 s1
strcpy(s1, s2);

//连接字符串 s2 到字符串 s1 的末尾
strcat(s1, s2);

//返回字符串 s1 的长度
strlen(s1);

//如果 s1 和 s2 是相同的，则返回 0
//如果 s1<s2 则返回值小于 0
//如果 s1>s2 则返回值大于 0
strcmp(s1, s2);

//返回一个指针，指向字符串 s1 中字符 ch 的第一次出现的位置
strchr(s1, ch);

//返回一个指针，指向字符串 s1 中字符串 s2 的第一次出现的位置
strstr(s1, s2);

5.1 串的顺序存储结构

串的顺序存储结构就是将所有字符数据元素保存在一个数组当中并以“\0”来表示字符串的结束。注意，字符串的长度加“\0”的长度不应当超过定义数组本身的长度。

5.2 串的链式存储结构

串的链式存储结构与链式表是相似的，由于串的结构中每个数据元素都是一个字符。

六.树

树（Tree）：是 n（n≥0）个节点的有限集。树结构是典型的一对多关系。

当 n = 0 时称为空树；

当 n ≠ 0 时的非空树中：

有且仅有一个特定的节点称为根节点（Root）；
当 n > 1 时，其余节点可以分割成若干个互不相交的子集，其每个集合本身也为一棵树，这棵树便是根的子树（SubTree）。

七.堆（完全二叉树）

堆（Heap）：堆本质上就是一棵完全二叉树。与内存管理的堆区不同，这儿是说的是一种数据结构。

7.1 堆的结构性质

堆一般使用数组来实现，即利用数组的索引来表示节点之间的关系。因此堆具有如下性质：

根节点索引一般为 0 ；
对于堆中任意非根节点 i ，它的左孩子节点为 2 i + 1 ，右孩子节点为 2 i + 2 ，父节点为 ( i - 1 ) / 2 ；
每个节点的左右子树也都必须是一个堆；
小堆不是升序，大堆不是降序。

堆的实现参考如下链接：堆（Heap）

八.哈希

哈希（Hash）：哈希表，又称为散列表，是根据码值访问的数据结构。哈希表的码就是数组的索引下标，然后通过码下标就可以直接访问数组中的数据元素。

C++ 中的哈希集合为 unordered_set，可以查找元素是否在集合中。如需同时存储键和值，则就要用 unordered_map 。

8.1 哈希函数设计原则

哈希函数的设计原则：

哈希函数的定义域必须包括需要存储的全部关键码，有m个地址的散列表的值域在 0 到 m-1 之间
哈希函数所计算的地址能均匀分布在整个空间中且尽量简单

8.2 常见哈希函数

常见的哈希构造函数：

直接寻址法
取关键字的某个线性函数为哈希函数：H a s h ( k e y ) = A ∗ k e y + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
场景：适合查找比较小且连续的情况
除留余数法
设哈希表中允许的地址数为 m ，取一个不大于 m 且最接近或者等于m的质数 p 作为除数，
然后按照哈希函数：H a s h ( k e y ) = k e y % p ( p < = m ) 将关键码转换成哈希地址
平方取中法
假设关键字为 1234 ，对它平方就是 1522756 ，抽取中间的 3 位 277 作为哈希地址；再比如关键字为 4321 ，对它平方就是 18671041 ，抽取中间的 3 位 671（或710）作为哈希地址。平方取中法比较适合：不知道关键字的分布，而位数又不是很大的情况。
折叠法
折叠法是将关键字从左到右分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。
随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即 H a s h ( k e y ) = r a n d o m ( k e y )，其中 random 为随机数函数。
如果关键字由多位字符或者数字组成，就可以考虑抽取其中的两位或者多位作为该关键字对应的哈希地址，在取法上尽量选择变化较多的位，避免冲突发生。

注：哈希函数设计越精妙，就越不容易产生哈希冲突，尽管如此依然无法完全避免哈希冲突。

九.图

图（Graph）：是由定点的有穷非空集合与顶点之间边的集合组成，通常可表示为 G(V,E) ，其中 G 表示一个图，V 表示 G 当中定点的集合，E 表示 G 当中边的集合。图结构是典型的多对多关系。更详细的内容可参照如下链接：图(Graph)

图的类型包括：有向图、无向、简单图、完全图（简单完全图）、多重图。

9.1 图的存储

图的任意两个顶点之间都可能存在联系，因此图无法用较为简单的顺序存储结构表示。而多重链表的方式，要么浪费众多存储单元，要么操作不方便。因此诞生如下五种图的存储结构：邻接矩阵，邻接表，十字链表，邻接多重表，边集数组。

邻接矩阵：存储方式是用两个数组来表示图。一个一维数组存储顶点信息，一个二维数组存储图中边的信息；
邻接表：存储方式是用一个一维数组存储顶点信息，图中每个顶点形成的邻接点构成一个线性表（由于邻接点个数不定，则用单链表存储）；
十字链表：是邻接表与逆邻接表结合形成的；
邻接多重表：是针对有向图的邻接表处理；
边集数组：由两个一维数组构成。一个存储顶点信息，一个存储边的信息。而这个边的数组每个数据元素由一条边的起点下标（Begin）、终点下标（End）、权重（Weight）组成。

9.2 图的遍历

图的遍历通常是从某一顶点出发访问遍所有其余顶点，且使每个顶点仅被访问一遍。对于图的遍历，为了避免陷入回路的死循环，通常采用如下两种访问方式：

深度优先遍历（Depth_First_Search）：简称 DFS 搜索算法。具体操作为：从图中某一个顶点 v 出发访问此顶点，然后从 v 的为被访问的邻接点出发深度优先遍历图，直到图中所有和 v 有路径想通的顶点都被访问到。若图中有未被访问，则另外选取未曾访问的顶点出发重复如上操作直至图中所有顶点均被访问到。
广度优先遍历（Breadth_First_Search）：简称 BFS 搜索算法，此种遍历方式类似于树的层序遍历。

#C/C++

C/C++『数据结构』

http://example.com/2022/04/27/C常见面试题_数据结构/

作者

DustWind

发布于

2022年4月27日

许可协议

C/C++『查找算法』上一篇

C/C++『概念理解』下一篇