数据结构考试知识点总结——线性表
·
- 在顺序表中插入或者删除一个元素，平均需要移动表中一半的元素，具体移动的元素个数与表长和该元素在表中的位置有关。
- 线性表是具有相同特性的数据元素的一个有限序列。
- 线性表的三个特征：1.所有数据元素类型相同2.线性表是由有限个数据元素构成的3.线性表中数据元素是位置有关的
- 线性表中结点的集合是有限的，结点间的关系是一对一的。
- 顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。
- 顺序表逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻元素的物理位置不一定相邻。
- 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
- 在n个结点的单链表中要删除已知结点*p，须找到它的前驱结点的地址，其时间复杂度为O(n)。
- 链表的每个结点可包含多个指针域，分别存放多个指针，比如双向链表的结点可以包含两个指针。
- 链表的存储结构是无序。
- 链表的结点不会移动，只是指针内容改变。
- 顺序表适合随机存取，链表适于顺序存取。
- 顺序存储方式优点是存储密度大，但是插入、删除运算效率低。
- 链式存储的存储结构所占存储空间分两部分，一部分存放结点值， 另一部分存放表示结点间关系的指针。
- 线性表L在需不断对L进行删除插入的情况下适用于链式结构实现。
- 单链表的存储密度小于1。
- 顺序表的插入和删除算法的时间复杂度均为O(n)。
- 根据线性表链式结构中每一个结点包含的指针数，将线性表分为单链表与双链表。
- 链接存储利用引用来表示数据元素之间的逻辑关系。
- 线性表中，若经常要存取第i个数据元素及其前驱，则宜采用顺序表存储方式。
- 在单链表中，增加一个头结点的目的是为了方便运算的实现。
- 在链表中，若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，宜采用双向链表存储方式。
- 顺序表的存储密度等于1；单链表的存储密度小于1。
- 单链表将s节点插入p节点之后：s.next = p.next;p.next = s;
- 带头结点的单链表head为空的判定条件是head.next==null
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)