数据结构

1 链表

链表可以存储多个值，它的特点是将数据与指标配对，以及指向下一条数据的内存位置。

在链表中，数据存储在内存中分散的位置，所以每个数据只能通过前面的指标访问。

添加数据只需要将上一个数据的指向新数据，新数据再指向下一个。

链表分为单向链表、双向链表、环形链表和静态链表。

静态链表就是用连续内存保存链表数据，同时有指向下一个地址的参数。

使用场景：表长难以预估，经常要增加删除元素

package main
import "fmt"
/**
    链表的实现
 */
type Node struct {
    data int
    next *Node
}
func main() {
    n3 := &Node{data: 3, next: nil}
    n2 := &Node{data: 2, next: n3}
    n1 := &Node{data: 1, next: n2}
    head := &Node{data: 0, next: n1}
    walkNode(head)
}
func walkNode(node *Node) {
    fmt.Println("node.data=", node.data)
    if node.next == nil {
        return
    }
    walkNode(node.next)
}

1.2 线性表

零个或多个数据元素的有限序列。
它是序列，一个连着一个。
有两种实现方式：数组和链表。
操作：增删改查。
根据元素查索引，根据索引查元素。

package main
import "fmt"
/**
    顺序表
    用数组实现
 */
const initLen = 10 // 默认长度为10
type SqList struct {
    data [initLen]int     // 用数组保存
    Length int           // 存值的长度
}
func NewSqList() *SqList {
    return &SqList{}
}
// AddElement 添加元素
func (s *SqList) AddElement(e int) int {
    // 判断数组越界
    if s.Length >= len(s.data) {
        panic("数组满了")
    }
    s.data[s.Length] = e
    s.Length++
    return 0
}
// 重写打印方法
func (s SqList) String() string {
    var d []int
    for i := 0; i < s.Length; i++ {
        d = append(d, s.data[i])
    }
    return fmt.Sprintf("data->%v, length->%d", d, s.Length)
}

2 数组

数组可以存储多个值，通过索引访问。

数组中的数据存储在连续位置的存储器中。

添加元素时，要确保数组末尾有额外空间，然后一个一个移动数据，腾出要添加的位置；删除元素则相反，先删除元素，移动数据填补空白区域，最后删除额外的空间。

总结：

数组查找很快，通过索引直接找到，但是增加和删除很慢，需要移动其他数据位置。

表长可预估，查询操作较多。

3 栈

就想往一个盒子里放CD，先进后出。

可以用数组实现，也可以用链表实现。

栈用一个辅助指针。

4 队列

类似排队，先进先出。

栈和队列的本质也是数组，不过增加了约束条件。

队列用两个辅助指针。一个指向头，一个指向尾。

判断空和满，可以使用辅助变量或者。

双端队列，可以从两端插入和删除。

5 哈希表

以key和value组成键值对，然后准备一个数组，将键值对的哈希值取数组长度的余，放入数组中，如果有相同的余数，则放入列表里，这样可以快速访问数据，不过要谨慎使用。

6 堆

堆是一种树形结构，并在实现 优先队列 时使用。

优先队列可以按任意顺序添加数据，取出时选择最小值。

过程：

1. 添加的数字放在末尾；
2. 如果父类数字比较大，则子类与父类互换；
3. 以此类推，直到不发生替换；
4. 取出数字时，从最上面的数字取出；
5. 将结尾的数字移动到顶部；
6. 重新开始比较子类与父类，直到不发生替换为止

使用堆可以快速取出最小的数据，但是无法执行在树中间取出数据的操作。

7 二叉树查找

二叉树有两个属性：第一个是所有节点都比左子树大，第二个是所有节点都比右子树小。

添加节点：从顶端节点开始，逐个比较，放到合适位置。

删除节点：

1. 如果没有子节点直接删除；
2. 如果有一个子节点，移动子节点到删除的位置；
3. 有两个子节点，可以从左子树中找最大的节点移动到删除的位置，也可以找右子树最小值。

一直保持良好平衡的二叉树称为 自平衡二叉树 ，能保持搜索效率。

8 集合

一种不允许重复元素的数据结构。

这也是和数组最大的区别。所以它的插入比一般的数组慢。

9 串

即字符串，由零个或者多个字符组成的有限序列。

字符串的比较：

从第一个字符开始往后依次对比其ASCII码。

中文根据Unicode比较大小。

举例：

char a[] = "哎bc";
char b[] = "呀bc";
int c = strcmp(a, b);
printf("compare a and b:%d\n", c);

匹配字符子串的算法：KPM算法。

10 树

树是n个结点的有限集。n>=0。

树的遍历：前序遍历、中序遍历、后序遍历和层序遍历。

• 前序遍历：根->左->右
• 中序遍历：左->根->右
• 后序遍历：左->右-根

根据根节点位置来区分。

完全二叉树

每层都满足 2^n-1 函数。

可以用顺序存储结构(一维数组)或者链式存储结构。

一般用后者，前者浪费空间。

二叉树的表示

typedef char ElemType;
typedef struct BitNode
{
    ElemType data;
    struct BitNode *lchild, *rchild;
} BitNode, *BiTree;

创建二叉树用前序遍历。

遍历二叉树

// 二叉树遍历
#include <stdio.h>
typedef char ElemType;
typedef struct BitNode
{
    ElemType data;
    struct BitNode *lchild, *rchild;
} BitNode, *BiTree;
// 前序：A，B，C
// 中序：B，A，C
// 后序：B，C，A
void bianli(BitNode *tree)
{
    if (tree->lchild != NULL)
    {
        bianli(tree->lchild);
    }
    if (tree->rchild != NULL)
    {
        bianli(tree->rchild);
    }
    // 根节点位置
    if (tree != NULL)
    {
        printf("data=%c\n", tree->data);
    }
}
int main(int argc, char const *argv[])
{
    BitNode right1 = {'C', NULL, NULL};
    BitNode left1 = {'B', NULL, NULL};
    BitNode root = {'A', &left1, &right1};
    bianli(&root);
    return 0;
}

线索二叉树

• 若无左子树，则将左指针指向其前驱节点；
• 若无右子树，则将右指针指向其后继节点；

// 线索二叉树
#include <stdio.h>
typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild; // 左右子树
    int ltag, rtag; // 左右标志位，0表示指向子节点，1表示指向前后继节点
} ThreadNode, *ThreadTree;
void InThread(ThreadTree &p, ThreadNode &pre) {
    if (p!=NULL) {
        InThread(p->lchild, pre);
    }
    if (p->lchild==NULL) {
        p->lchild = &pre;
        p->ltag = 1;
    }
    if (&pre!=NULL && pre.rchild != NULL) {
        pre.rchild = p;
        pre.rtag = 1;
    }
    pre = *p;
    InThread(p->rchild, pre);
}

哈夫曼树

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。

在构建哈弗曼树时，要使树的带权路径长度最小，只需要遵循一个原则，那就是：权重越大的结点离树根越近。

利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。哈夫曼编码可以有效的压缩数据。

11.图

多对多逻辑关系数据的结构。

图的存储结构：

邻接矩阵

用一个一维数组存储图的顶点，一个二维数组(即邻接矩阵)存储图中的边或者弧的信息。

不过比较浪费空间。

通常，图更多的是采用链表存储，具体的存储方法有 3 种，分别是邻接表、邻接多重表和十字链表。

邻接表

邻接表存储图的实现方式是，给图中的各个顶点独自建立一个链表，用节点存储该顶点，用链表中其他节点存储各自的临界点。

但是非常不方便同时计算出度和入度。

十字链表

十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。

• tailvex：用于存储以首元节点为弧尾的顶点位于数组中的位置下标；
• headvex：用于存储以首元节点为弧头的顶点位于数组中的位置下标；
• hlink 指针：用于链接下一个存储以首元节点为弧头的顶点的节点；
• tlink 指针：用于链接下一个存储以首元节点为弧尾的顶点的节点；
• info 指针：用于存储与该顶点相关的信息，例如量顶点之间的权值；

代码

#define  MAX_VERTEX_NUM 20
#define  InfoType int//图中弧包含信息的数据类型
#define  VertexType int
typedef struct ArcBox{
    int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
    struct ArcBox *hlik,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
    InfoType *info;//存储弧相关信息的指针
}ArcBox;
typedef struct VexNode{
    VertexType data;//顶点的数据域
    ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
    int vexnum,arcnum;//记录图的顶点数和弧数
}OLGraph;
int LocateVex(OLGraph * G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; i++) {
        if (G->xlist[i].data==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i>G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构建十字链表函数
void CreateDG(OLGraph *G){
    //输入有向图的顶点数和弧数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->xlist[i].data));
        G->xlist[i].firstin=NULL;
        G->xlist[i].firstout=NULL;
    }
    //构建十字链表
    for (int k=0;k<G->arcnum; k++) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        //确定v1、v2在数组中的位置下标
        int i=LocateVex(G, v1);
        int j=LocateVex(G, v2);
        //建立弧的结点
        ArcBox * p=(ArcBox*)malloc(sizeof(ArcBox));
        p->tailvex=i;
        p->headvex=j;
        //采用头插法插入新的p结点
        p->hlik=G->xlist[j].firstin;
        p->tlink=G->xlist[i].firstout;
        G->xlist[j].firstin=G->xlist[i].firstout=p;
    }
}

邻接多重表

邻接多重表存储无向图的方式，可看作是邻接表和十字链表的结合。同邻接表和十字链表存储图的方法相同，都是独自为图中各顶点建立一张链表，存储各顶点的节点作为各链表的首元节点，同时为了便于管理将各个首元节点存储到一个数组中。

注意，邻接多重表仅适用于存储无向图或无向网。