Note

外观

数据结构 ​

逻辑结构 ​

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

物理结构 ​

  • 线性
  • 非线性

数组 ​

array

常用技巧 ​

  • 快慢指针
  • 指针碰撞

中位数计算 ​

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

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

链表 ​

组成 ​

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

单向链表 ​

链表

双向链表 ​

双向链表

循环链表 ​

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

跳跃表 ​

跳跃表跳跃表

头节点 ​

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

队列 ​

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

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

栈 ​

stack
是先进先出（FIFO, First-In-First-Out）的线性表。
img
可以使用链表或者数组来实现。

参考 ​

wiki-数组
wiki-链表