数据结构（c语言描述） 教学课件 作者 库波 第2章 线性表.ppt

数据结构(C#)主编: 、最基本、最常用的数据结构,线性结构的特点是数据元素之间存在一对一的线性关系。这种一对一的关系指的是数据元素之间的位置关系;除第一个数据元素外,其它数据元素前面都只有一个数据元素;除最后一个数据元素外,其它数据元素后面都只有一个元素。(List)是由n(n≥0)个相同类型的数据元素构成的有限序列。有限是指线性表中的每一个数据元素都有自己的位置;线性表中的数据元素都属于同一种类型。线性表通常记为(a1,a2,…,ai-1,ai,ai+1,…,an)ai-1为ai的直接前驱ai为ai+1的直接后继。除a1外,其余元素只有一个直接前驱除an外,其余元素只有一个直接后继。线性表的形式定义为:L=(D,R)其中:D是数据元素的有限集合,R是数据元素之间关系的有限集合。线性表的基本操作publicinterfaceIListDS<T>{intCount{get;};//求长度voidClear();//清空操作boolIsEmpty{get;};//判断线性表是否为空voidAppend(Titem);//附加操作voidInsert(Titem,inti);//插入操作TDelete(inti);//删除操作TGetElem(inti);//取表元intLocate(Tvalue);//按值查找}提取基接口所有数据结构都可定义为“由n(n≥0)个相同类型的数据元素构成的有限序列”,即都有求长度、清空和判断是否为空三种操作。将这三种操作提取到基接口IDS<T>:publicinterfaceIDS<T>{intCount{get;}//求长度voidClear();//清空操作boolIsEmpty{get;}//判断线性表是否为空}线性表的接口IListDS<T>的定义变为:publicinterfaceIListDS<T>:IDS<T>{voidAppend(Titem);//附加操作voidInsert(Titem,intindex);//插入操作TDelete(intindex);//删除操作TGetElem(intindex);//取表元intLocate(Tvalue);//按值查找},用这种方式存储的线性表叫顺序表,如图所示。顺序表的特点是表中相邻的数据元素在内存中存储位置也相邻。01…i-1ii+1…n-1…maxsize-1a1a2…ai-1aiai+1…an…↑last