数据结构

空间复杂度

时间复杂度

---

表

形如 的表，我们说，这个表的大小是。我们称大小为 0 的表为空表 (empty list)。 对于除空表外的任何表，我们说后继(或继之后) 并称() 前驱()。表中的第一个元素是，最后一个元素是。

数组 Array

数组就是一种线性表，物理结构为顺序存储，是大多数语言内置的基本数据类型。

// 定义数据元素
typedef struct {
	int id;
	char name[30];
	char sex; // man->m, woman->w
	unsigned int age;
} Node;
 
Node array[5];

优点

• 构建非常简单
• 能在 O(1) 的时间里根据数组的下标（index）查询某个元素

缺点

• 构建时必须分配一段连续的较大的空间，容易造成浪费
• 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间（其中，n 是元素的个数）
• 删除和添加某个元素时，同样需要耗费 O(n) 的时间

链表 Linked List

链表是链式存储结构的线性表。

单链表（singlelist）

struct Node {
	ElementType data;
	struct Node next;
};
 
typedef struct Node *PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
 

双链表

栈

Last In First Out 先进先出

栈是限定仅在表尾进行插入和删除操作的线性表。

插入 → 入栈 → 压栈 删除 → 出栈 → 弹栈

队列

队列是只能在一端进行插入操作，在另一端进行删除操作的线性表。

串（字符串）string

树 tree