大话数据结构学习笔记-线性表(一)

术语

定义:由零个或多个数据元素的有限序列

长度:线性表中元素的个数称为线性表的长度

空表:当线性表长度为0时，称为空表

位序:数据元素在线性表中的位置称为该元素的位序

抽象数据类型

ADT 线性表
Data
	线性表的数据对象集合为{a1,a2,……an},每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
	InitList(out L):初始化操作，建立一个空的线性表L。
	ListEmpty(in L,out result):若线性表为空，返回true，否则返回false。
	ClearList(in L):将线性表清空。
	GetElem(in L,in i,out e):将线性表L中的第i个位置元素返回给e。
	LocateElem(in L,in e，out i):在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。
	ListInsert(in L,in i,in e):在线性表L中的第i个位置插入新元素e。
	ListDelete(in L,in i,out e):删除线性表L中第i个位置元素，并用e返回其值。
	ListLength(in L,out length):返回线性表L的元素个数。
	...其他操作（如并集、交集、差集、连接两个线性表等等）
EndADT

接口定义（基于.net 6.0）

namespace DataStructLearning.List;

public interface IList<T>
{
    /// <summary>
    /// 初始化一个空的线性表
    /// </summary>
    /// <returns>空线性表</returns>
    IList<T> Init();
    /// <summary>
    /// 判断线性表是否为空
    /// </summary>
    /// <returns>为空时返回true，否则返回false</returns>
    bool Empty();
    /// <summary>
    /// 清空线性表
    /// </summary>
    void Clear();
    /// <summary>
    /// 获取指定位置的元素（从1开始）
    /// </summary>
    /// <param name="i">待获取元素的位置</param>
    /// <returns>获取到的元素</returns>
    T GetElem(int i);
    /// <summary>
    /// 定位某个元素
    /// </summary>
    /// <param name="e">要定位的元素</param>
    /// <returns>如果查找成功，则返回该元素在线性表中的位置，否则返回0</returns>
    int LocateElem(T e);
    /// <summary>
    /// 将指定元素插入到线性表
    /// </summary>
    /// <param name="e">待插入元素</param>
    void Insert(T e);
    /// <summary>
    /// 删除指定位置的元素
    /// </summary>
    /// <param name="i">待删除的元素位置</param>
    /// <returns>删除元素的值</returns>
    T Delete(int i);
    /// <summary>
    /// 获取线性表的长度
    /// </summary>
    /// <returns>线性表的长度</returns>
    int Length();
}