定义在数据的逻辑结构上的,但其实现则有赖于所采用的存储结构。因此,采用不同的存储结构,会对线性表上的处理实现产生直接的影响。Р本章主要介绍以下几个方面的内容:Р线性表的基本知识;?线性表的顺序存储实现;?线性表的链式存储实现(单链表、双链表、循环链表);?线性表的具体应用举例。Р2.1 线性表的基本知识Р所谓“线性表”,是由具有相同类型的有限多个数据元素组成的一个有序序列。?若把一个线性表取名为L,里面有n(n≥0)个元素,每个元素用ai(1≤i≤n)表示, 下标代表该元素在线性表中的位置,那么可以把线性表L记为:АL = (a1 , a2, …, ai, ai+1, …, an−1, an )Р线性表中数据元素的个数n,称为线性表的“长度”。当n=0时,表示线性表中不包含任何元素,称其为“空表”。若线性表L为空,则记为L =()或L = Ø。在线性表中,对任意一对相邻结点ai和ai+1 (1≤i≤n−1),称ai为ai+1的“直接前驱”,称ai+1为ai的“直接后继”。Р图2-1 相邻结点间的关系Р如果线性表中元素的值与它的位置之间存在联系,那么称这种线性表为“有序线性表”;如果线性表中元素的值与它的位置之间没有特殊的联系,那么称这种线性表为“无序线性表”。Р由于线性表的元素间具有线性关系,因此一个非空线性表的特点是:?有且仅有一个起始结点a1,它没有直接前驱,只有一个直接后继a2;?有且仅有一个终端结点an,它没有直接后继,只有一个直接前驱an−1;?其余结点ai(2≤i≤n−1)都有且仅有一个直接前驱ai−1和一个直接后继ai+1。Р对于一个线性表,可以根据需要在其上定义各种操作处理。经常要求的处理有:?创建一个新的线性表,或删除一个已经存在的线性表;?使线性表增长(即插入一个元素)、使线性表缩短(删除一个元素),增长或缩短后元素间仍将保持线性关系;
全文预览
