下载掌阅APP，畅读海量书库
立即打开
本章主要讲解了线性表的相关概念及其两种存储方式，分别介绍了顺序表、单链表、循环链表和双链表的概念、基本操作及实例应用。通过本章的学习，应掌握的重点内容包括如下几点：
（1）线性表的顺序存储特点：在线性表的顺序存储结构中，是利用结点的存储位置来反映结点的逻辑关系，结点的逻辑次序与存储空间中的物理次序一致，因而只要确定了线性表中起始结点的存储位置，即可方便地计算出任一结点的存储位置，所以可以实现结点的随机访问。在顺序表中只需存放结点自身的信息，因此，存储密度大、空间利用率高。但在顺序表中，结点的插入、删除运算可能需要移动许多其他结点的位置，一些长度变化较大的线性表必须按照最大需要的空间分配存储空间，这些都是线性表顺序存储结构的缺点。
（2）线性表的链式存储特点：在线性表的链式存储结构中，结点之间的逻辑次序与存储空间中的物理次序不一定相同，是通过给结点附加一个地址域来表示结点之间的逻辑关系。所以，不需要预先按最大的需要分配存储空间。同时，链表的插入、删除运算只需修改地址域，而不需要移动其他结点。这是线性表链式存储结构的优点。它的缺点在于，每个结点中的指针域需要额外占用存储空间，因此，它的存储密度较小。另外，链式存储结构是一种非随机存储结构，查找任一结点都要从头指针开始，沿指针域逐个搜索，增加了某些算法的时间代价。
（3）将单链表加以改进可得到循环链表和双向链表。在循环链表中，所有的结点构成了一个环，所以从任一结点开始都可以扫描此线性表中的每个结点。双向链表既有指向直接后继的指针，又有指向直接前趋的指针，从而便于查找结点的前趋。
（4）线性表的运算及应用：其主要运算有查找、插入和删除等，本章介绍了线性表在不同存储方式下各种运算的实现方法及实例应用。