线性表-概述

2020-01-19 本文已影响0人风紧扯呼

前言

线性表是一种简单的线性结构。线性表的主要操作特点是可以在任意位置插入和删除一个数据元素。线性表可以用顺序存储结构和链式存储结构存储。用顺序存储结构实现的线性表称做顺序表，用链式存储结构实现的线性表称做链表。链表主要有单链表、循环链表和双向循环链表三种。

线性表-概述
 线性表(一)——顺序表
 线性表(二)——单链表的表示和实现
 线性表(三)——双向链表的表示和实现

线性结构的特点是，除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据和一个后继数据元素。线性表是一种可以在任意位置进行插入和删除数据元素操作的、由n( $n\ge 0$ )个相同类型数据元素组成的线性结构。线性表是一种最简单的线性结构。

抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合，而类型是一组值的集合。因此线性表的抽象数据类型主要包括两个方面：数据集合和该数据集合上的操作结合。

线性表的数据集合可以表示为 $a_0,a_1,a_2,···,a_{n-1}$ ，没个数据元素的数据类型都是抽象数据元素的数据类型DataType。

初始化ListInitiate(L)：初始化线性表L。
求当前数据元素个数ListLength(L)：函数返回线性表L的当前数据元素个数。
插入数据元素ListInsert(L,i,x)：在线性表L的第i个数据元素前插入数据元素x，插入成功返回1，插入失败返回0。插入成功的条件为： $0\leq i \leq ListLength(L)$ 。若 $i=0$ ，表示在 $a_0$ 前插入数据元素x；若 $i=ListLength(L)-1$ 表示在 $a_{n-1}(n=ListLength(L))$ 前插入数据元素x；若 $i=ListLength(L)$ 表示在 $a_{n-1}$ 后插入数据元素x。
删除数据元素ListDelete(L,i,x)：删除线性表L的第i个数据元素，所删除的数据元素由输出参数x带回，删除成功返回1，删除失败返回0。删除成功的条件为： $0\leq i \leq ListLength(L)-1$ 。
取数据元素ListGet(L,i,x)：线性表L的第i个数据元素，所取的数据元素由输出参数x带回，取元素成功返回1，失败返回0。取元素成功的条件为： $0 \leq i \leq ListLength(L)-1$ 。