§2
§21线性表的定义及其基本运算
线性表
线性表是
个数据元素（结点）a1，a2，，a
组成的有限序列。其中数据元素的个数
定义为表的长度。当
0时称为空表。线性表的常用的运算：（1）置空表。（2）求线性表L的长度。（3）取表中的第i个结点（4）按值查找。（5）插入：在表L的第i个位置上插入新的结点X。（6）删除：删除表L的第i个结点。线性表可采用两种存储结构：顺序存储和链式存储。§22线性表的顺序存储结构
它的特点是逻辑上相邻的结点其物理位置亦相邻，下标可以看成是结点的相对地址。运算：1插入用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须将表中位置
1i上的结点依次后移到位置
1
i1上腾出第i个位置，然后在该位置上插入新结点x。仅当插入位置i
1时，才无须移动结点，直接将x插入表的末尾。
2）删除在顺序表上实现删除运算也必须移动结点，才能反映出结点间逻辑关系的变化。仅当i
，才能简单地删除终端结点，无须移动结点；
3）取表S中的第i个结点直接以Si表示4查找须顺序取出表中元素逐一比较
f顺序表有如下优缺点：优点：（1）无须为表示结点间的逻辑关系而增加额外的存储空间；（2）可以方便地随机存取表中的任一结点。缺点：（1）插入和删除运算不方便，除表尾的位置外，在表的其它位置上进行插入和删除操作都必须移动大量的结点，其效率较低；（2）由于顺序表要求占用连续的存储空间，存储分配只能预先进行（静态分配），因此当表变化较大时，难以确定合适的存规模，若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用，若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。§23线性表的链式存储结构
从链接方式上可分为：单链表、循环链表和双链表。1）单链表2）循环链表3）双链表§231单链表基本运算
一、建立单链表建立链表就是要在表中逐一增加新的结点。为此，必须反复执行下列步骤：i）使用过程NEW，获得新的存储单元；ii）读入新结点分量的数据域iii）将指针向后推移，跟踪链表的增长到链表的长度满足要求为止。（1）头插法建表该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直至读入结束标志为止。
【练习1】：完成下面的程序逐个输入字符型数据，以为结束符，r