第一节 - 线性表定义和基本运算
发布时间：2020-09-20 10:27来源：未知
第一节 线性表定义和基本运算
一、线性表的逻辑定义
1、线性表定义
线性表(Linear_List)是一种典型的线性结构结构，它是由n个数据元素(结点)a1，a2，…，an组成的有限序列。其中，数据元素的个数n为表的长度。当n为零时称为空表，非空的线性表通常记为(a1，a2，…，ai-1，ai，ai+1，…，an)
2、线性表的特征
对于一个非空的线性表：
①有且仅有一个称为开始元素的a1，它没有前趋，仅有一个直接后继a2；
②有且仅有一个称为终端元素的an，它没有后继，仅有一个直接前趋；
③其余元素ai(2≤i≤n-1)称为内部元素，它们都有且仅有一个直接前趋ai-1和一个直接后继ai+1。
二、线性表的基本运算
(1)置空表 InitList(L)，构造一个空的线性表L。
(2)求表长ListLength(L)，返回线性表L中元素个数，即表长。
(3)取表中第i个元素GetNode(L，i)，若1≤i≤ListLength(L)，则返回第i个元素ai。
(4)按值查找LocateNode(L，x)，在表L中查找第一个值为x的元素，并返回该元素在表L中的位置，若表中没有元素的值为x，则返回0值。
(5)插入InsertList(L，i，x)，在表L的第i元素之前插入一个值为x的新元素，表L的长度加1。
(6)删除DeleteList(L，i)，删除表L的第i个元素，表L的长度减1。
实际遇到的复杂运算可以由有各种基本运算组合实现。
