数据结构与算法线性表ppt课件.ppt

《数据结构与算法线性表ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、·线性表的定义及ADT·线性表的顺序存储结构·线性表的链接存储结构·单向循环链表·双链表、双向循环链表·一元多项式的加法目录第二章线性表1、线性表的定义及ADT1、线性结构的定义：空或者只有一个结点。或者1、存在唯一的一个被称之为”第一个“的结点。2、存在唯一的一个被称之为”最后一个“的结点。3、除第一个结点之外，每个结点均只有一个前驱结点。4、除最后一个结点之外，每个结点均只有一个后继结点。分为以下几大类：·线性表：进通过它们之间的相对位置，确定它们之间的相互关系的线性结构。e.g:序列：a1、a2、a3…………………an-1、an·分类表

2、·时间有序表·频率有序表·序列2、结点或数据元素：结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。如：学生登记表中的每个学生结点，由学号、姓名、性别、系别……等构成。存放在外存中的结点通常称之为记录。1、线性表的定义及ADT3、线形表List的ADTADT2.1:线性表List的ADTElement:{xi

3、xiElemSet,i=1,2,3,……n,n>0}或Φ;ElemSet为结点集合。Relation:{

4、xi,xi+1ElemSet,i=1,2,3,……n-1},x1为首结点，xn为尾结点。Operations:

5、Constructor前提:无或指定List的规模。结果:分配相应空间及初始化。Clear前提:无。结果：删除表List中的所有结点并进行初始化。IsEmpty前提：无结果：表List为空返回True，否则返回False。IsFull前提：无结果：表List为满返回True，否则返回False。1、线性表的定义及ADT3、线形表List的ADTLength前提：无结果：返回表List中的结点个数。Get前提：表List非空且已知结点序号无结果：返回相应结点的数据值。Prior前提：表List非空，已知结点序号且该结点非首结点。结果：返回其直接前驱结点的序号。Ne

6、xt前提：表List非空，已知结点序号且该结点非尾结点结果：返回其直接后继结点的序号。Find前提：表List非空，已知结点的数据值。结果：查找成功，返回相应结点序号，否则返回查找失败标志Insert前提：已知待插入的数据值以及插入位置。结果：插入具有该数据值的结点，表List的结点个数增大1。Delete前提：表List非空，已知被删结点的数据值。结果：首先查找相应结点，查找成功则删除该结点，表List的结点个数将减少1。否则返回删除失败标志。2、线性表的顺序存储结构1、物理存储位置的计算：·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表。·设第一个结点

7、的存储地址为LOC(a0),余类推。设每个结点占用L个单元。则：an－1ai-1a1a0aiLOC(ai)=LOC(ai-1)+L=LOC(ai-2)+2L=LOC(ai-i)+i*L=LOC(a0)+i*L·随机存取：访问任何一个数据元素或结点花费同样多时间。2、线性表的顺序存储结构templateclassSeqList{private:ElemType*elem;//顺序表存储数组，存放实际的数据结点。intlength;//顺序表中的结点个数，亦称表的长度。intMaxSize;//顺序表的的最大可能的长度。public:S

8、eqList(intInitSize);//构造函数~SeqList();//析构函数voidClear();//清空顺序表boolIsEmpty()const{return(length==0);}//表为空返回TRUE,否则返回FALSE。boolIsFull()const{return(length==MaxSize)};//表是否已经满，满则返回TRUE，否则FALSE。intLength()const;//表的长度ElemTypeGet(inti)const;//返回第i个结点的值intNext(inti)const;//若第i个结点的直接后继结点存在

9、，返回其下标，//否则返回0intPrior(inti)const;//若第i个结点的直接前驱结点存在，返回其下标，//否则返回0intFind(ElemTypee);//返回值等于e的结点的序号，无则返回02、线性表的顺序存储结构templateclassSeqList{………………….intFind(ElemTypee);//返回值等于e的结点的序号，无则返回0intInsert(inti,constElemType&e);//在第i个位置上插入新的结点（值为e），并//使原来的第i个结点至最后一个结点的序号依次加1。//插入成

10、功返回1，否则为0int