数据结构与算法基础（青岛大学-王卓）

插入操作

删除操作 有一定要注意第一个while 里面的条件是 p->next 不能是 p 若为p 会出现引用空指针的情况（比如说 该链表有6个元素 你要删除第7个 ）

j 与 p 的位置一一对应

!p用来排除 i 过大的情况

j > i用来排除 i 为0 -1 等非法情况

头插法

尾插法

循环链表

双向链表双向循环链表

插入操作

链表实现有序表的合并

多项式相加实现

需要人为输入各项的系数与指数但按排序输入

程序可自动排序

1. 建立一个链表
2. 找到第一个比输入值的指数小的节点 需要两个指针pre p while(p && s->指数 > p->指数) pre = p , p = p->next;
3. 插入

指数相等的情况

• 系数相加 判断是否为0

若是0： 两指针都向后移一位 并删除空间

若不为0： 系数相加至其中一个链表中 另一个链表的对应节点删除 两指针都移向下一位

• 不相等的情况参考上文有序链表的合并。

离散化算法参考：https://www.acwing.com/activity/content/code/content/5328352/

栈

顺序栈

清空栈 ： 空间还占用

销毁栈 ： 空间也删除掉

入栈 ：判断是否栈满 (top - base 是否为0)

压入栈 top指针上移一位

链栈 ：

入栈

出栈

递归 ：

队列

循环队列

核心是 有新元素入栈时 尾指针+1 % maxsize

如何判断循环队列 空 还是 满

由于空和满时头指针和尾指针都一样 需要先出另外的办法：

少用一个元素空间：

队列的初始化

循环队列求队列的长度 ：

循环队列入队：

1. 判断是否队满；
2. 新元素加入队尾；
3. 尾指针+1；

循环队列出队：

队列的链式表示

初始化：

销毁

入队

出队

须特判队列中只有一个元素的情况

因为这时尾指针也要修改