【数据结构】线性表的定义和基本操作

阅读本文，需要对C语言的知识有所掌握，参考我的C语言合集。

C语言合集

1. 线性表的定义和基本操作

说明：定义注重的是逻辑结构，而基本操作注重运算。

注：数据结构的三要素——逻辑结构、数据的运算、存储结构（物理结构）。

存储结构不同，运算的实现方式也不同。

2. 线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时线性表为一个空表。

L=(a1,a2,…,ai-1,ai,ai+1,…,an)

注意：

• 线性表中元素个数n，称为线性表的长度。当n=0时，为空表。
• a1是唯一的“第一个”数据元素，称为表头元素；an是唯一的“最后一个”数据元素，称为表尾元素。
• ai-1为ai的直接前驱，ai+1为ai的直接后继。
• 位序从1开始，区别于数组下标从0开始。

特点：

• 表中元素的个数是有限的。
• 表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间。
• 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序。

3. 线性表的基本操作

InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。

DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。

ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

LocateElem(L,e)：按值查找。在表L中查找具体给定关键字e的元素。

GetElem(L,i)：按位查找。获取表L中第i个位置的元素的值。

Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。

PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。

Empty(L)：判空操作。若L为空表，返回true，否则返回false。

说明：

1. 在后面的实战中，就会使用这些函数做具体的操作。
2. 修改之前需要先查找。
3. &符号的使用在C语言合集中有讲解。

4. 小结