1.线性表的基本概念
线性结构又称线性表，线性表是最简单也是最常用的一种数据结构。
回顾：线性结构有且只有一个根结点和一个叶子结点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构。
2.线性表的分类
线性表分为顺序存储结构和链式存储结构。
顺序存储结构是用一组地址连续的存储单元依次存储线性表中的各个元素，逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。特点：①元素所占的存储空间必须连续。
②元素在存储空间的位置是按逻辑顺序存放的（比如从大到小、从小到大）。
链式存储结构不要求存储空间连续，数据元素之间的关系使用“链”来连接。链式存储结构可分为：单链表、循环链表、双向链表。3.线性表的插入运算
在第i个元素之前插人一个新元素的步骤如下：
步骤一：把原来第i个节点至第n个节点依次往后移一个元素位置。
步骤二：把新节点放在第i个位置上。
步骤三：修正线性表的节点个数。
在第三个元素前插入元素在最坏情况下，即插入元素在第一个位置，线性表中所有元素均需要移动。
4.线性表的删除运算
删除第i个位置的元素的步骤如下：
步骤一：把第i个元素之后不包括第i个元素的n-i个元素依次前移一个位置；
步骤二：修正线性表的结点个数。
删除第三个元素在最坏情况下，即删除元素在第一个位置，线性表中所有元素均需要移动。
5.线性链表（线性表链式存储结构中的单链表）
在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。
在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。
补充说明：这里的一个结点存储两个内容（数据域、指针域）。数据域存储数据内容；指针域指向直接后继（下一个结点）的地址，因为只能指向一个，即只有一个直接后继。因为一个结点只能有一个指针指向它，所以只有一个直接前驱（上一个结点）。
线性链表的形象表示形式（字母为数据域，·为指针域）：
线性链表练习题
1.下列叙述中正确的是（）
A.在链表中，如果每个结点有两个指针域，则该链表一定是线性结构
B.在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构
C.在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构
D.在链表中，如果有两个结点的同一个指针域的值相等，则该链表定是非线性结构
——————
2.下列叙述中正确的是（）
A.链表只能是非线性结构
B.链表可以是线性结构也可以是非线性结构
C.对分查找也适用于有序链表
D.快速排序也适用于线性链表
——————
答案与解析见下期哦~
上期解答
1.下列叙述中正确的是（C）
A.只有一个根结点，且只有一个叶子结点的数据结构一定是线性结构
B.所有数据结构必须有终端结点（即叶子结点）
C.没有根结点或没有叶子结点的数据结构一定是非线性结构
D.所有数据结构必须有根结点
A项没有满足每个结点最多有一个直接前驱和一个直接后继（线性结构：有且只有一个根结点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构），故A错。空指针没有结点，也就没有终端结点，故B错。根结点为起始结点，叶子结点为终端结点；没有根结点或没有叶子结点的数据结构为空指针，为非线性结构，故C正确。空指针没有结点，也就没有根结点，故B错。——————
2.下列叙述中错误的是（A）
A.非线性结构中至少有一个根结点
B.有一个以上根结点的必定是非线性结构
C.有一个以上叶子结点的必定是非线性结构
D.非线性结构中可以没有根结点与叶子结点
空指针没有结点，为非线性结构，故A错。线性结构有且只有一个根结点，故B正确。线性结构有且只有一个叶子结点，故C正确。空指针没有任何结点，为非线性结构，故D正确。文章中如有错误，欢迎批评指出
更多文档资料，请