数据结构

---

逻辑结构

• 集合：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系
• 线性结构：数据结构中的元素存在一对一的相互关系
• 树形结构：数据结构中的元素存在一对多的相互关系
• 图形结构：数据结构中的元素存在多对多的相互关系

物理结构

• 线性
• 非线性

数组

常用技巧

• 快慢指针
• 指针碰撞

中位数计算

// 方法一，如果l和r很大，和可能会溢出
mid = (l+r)/2;
// 方法二，先减法，再加
mid = l + (r-l)/2;
// 方法三，运用移位
mid = l + (r -l) >> 1;

//假设数组范围[l,r]，l <= r
//则 l <= mid
//实际使用时，注意`边界`。

链表

组成

typedef struct list{
    int data;  //数据域
    struct list *next; //指针域
};

单向链表

双向链表

循环链表

表中最后一个节点的指针指向头节点。

跳跃表

头节点

在链表第一个节点之前附设一个节点，叫做头节点

队列

是一种先进先出（FIFO, First-In-First-Out）的线性表。

队列只允许在后端（称为rear）进行插入操作，
在前端（称为front）进行删除操作。
通常用链表或者数组来实现。
还有双向队列和循环队列

栈

stack
是先进先出（FIFO, First-In-First-Out）的线性表。

可以使用链表或者数组来实现。

参考

wiki-数组
wiki-链表