数据结构与算法第二章 线性表
顺序表：将线性表中元素相继存放在连续的存储空间中
特点：各表项逻辑顺序与物理顺序一致，可随机访问
顺序表顺序查找/插入（插在某元素前方或末尾）/删除数据的平均比较/移动/移动次数（此时元素为\(n\)个）
查找成功\(\displaystyle \frac{n+1}{2}\),失败\(n\),插入\(\displaystyle \frac{n}{2}\),删除\(\displaystyle \frac{n-1}{2}\)。
连续存储方式（顺序表）优点：存储利用率高（无额外指针开销，数据元素紧密排列，空间利用率高），存取速度快；缺点：插入、删除效率低，空间分配不灵活（需预先分配固定大小空间，可能导致空间浪费或溢出）
链式存储方式（链表）优点：可适应表的动态增长和减小（链表空间是动态申请、释放的，能有效利用存储空间，按需分配。），结点可不连续存储，插入、删除效率高；缺点：存储密度低（需额外指针存储空间），存取效率低（只能从表头开始顺序访问元素，无法随机存取）
链表
链表类定义（复合方式）
friend：友元类 一个类A的友元类B中的所有成员函数都可以访问A中的成员变量，包括private
链表类定义（嵌套方式）
链表类定义（继承方式）
链表插入/删除节点：
记first为链表的第一个节点。
链表插入结点：
最前端插入（插入非空表第一个结点前/插入空表）：
newnode->link=first//将新结点的指针指向当前第一个结点
first=newnode//将新结点设为新结点
中间/尾部插入（将newnode插入current与其后继间）
newnode->link=current->link//新结点的指针指向current后继
current->link=newnode//current后继指向新结点
链表删除结点：
最前端删除：
del=first,del=first->link,delete del
在链表中间或尾部删除（删除结点为current前驱）：
del=current->link;current->link=del->link;delete del`
//若记删除结点为current，不便处理
带表头结点（first仅表示表头，指向链表第一个结点，链表为空则指向NULL）的单链表：
统一空表与非空表操作
循环链表（普通循环链表与带表头的循环链表）：
1 2 | |
双向链表
静态链表
为数组中每一个元素附加一个链接指针，就形成静态链表结构。
静态链表每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。
处理时中可以不改变各元素的物理位置，只要重新链接就能改变这些元素的逻辑顺序。
它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。
多项式的存储（链表）
使用线性表的缺点：插入和删除时项数可能有较大变化，因此要移动大量数据不利于多个多项式的同时处理
使用链表的优点：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素
三个变量：系数/指数/指针域
例题：
一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。
（A）单链表（B）单循环链表（C）带尾指针的单循环链表（D）带头结点的双循环链表
本题提示
关键在C/D判断，需要注意：删除某个结点需要找到其前驱，C明显找前驱效率低，故选D
静态链表中指针表示的是（数组下标）
静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关（错）本质是链式结构，需要遍历。