408 DS

第1章 绪论

常见复杂度排序：$O(1)<O(log_2n)<O(n)<O(nlog_2n)<O(n^2)<O(n!)<O(n^n)$

时间复杂度：常规的直接数一下暴力，循环最好想一下展开的量级关系

第2章 线性表

线性表示一种逻辑结构

顺序表

随机查找、顺序存储形式。

分配（动态）：L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);

链表

非随机读取，不支持随机查找、链式存储结构，节点空间可以动态申请和释放。

单链表

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

双链表

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

操作

插入（头插法单链表）

LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;

插入（尾插法单链表）

LNode *s = (LNode *)malloc(sizeof(LNode));
s->data.= x;
r->next = s;
r = s; // 这里指向了新的表尾节点

双链表插入（p结点之后插入s）

s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;

几个时间复杂度

顺序表

• 插入：表尾 $O(1)$、表头 $O(n)$
• 删除：平均为 $O(n)$
• 查找：$O(n)$

第3章 栈、队列和数组

栈

先进后出（FILO）、后进先出（LIFO）

顺序栈

动态顺序栈，动态一维数组来存储

#define Stacksize 50
typedef int ElemType;
typedef struct Sqstack {
  ElemType *bottom, *top;
  int Stacksize;
} Sqstack, *SqStack;

静态顺序栈

#define MaxSize 50
typedef int ElemType;
typedef struct Sqstack {
  ElemType data[MaxSize];
  int top;
} Sqstack, *SqStack;

入栈：先进指针，再进入元素 ++(S.top); S.data[S.top] = x;

链栈

typedef struct LNode {
  ElemType data;
  struct LNode *next;
} LNode;

入栈头插法、出栈头出法

队列

先进先出（FIFO）

第4章 串

第5章 数与二叉树

第6章 图

第7章 查找

第8章 排序