数据结构(c++),顺序表,单链表。课件.ppt

《数据结构(c++),顺序表,单链表。课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表线性表的定义线性表的顺序表示线性表的链式表示一元多项式的运算2.1线性表的类型定义线性表定义：n个数据元素的有限序列。(A,B,C,......,X,Y,Z)(a1,a2,...,ai-1,ai,ai+1,...,an-1,an)线性表的逻辑特性：线性表中的所有数据元素，其数据类型是一致的；数据元素在表中的位置只取决于它们自己的序号，数据元素之间的相对位置是线性的基本术语直接前驱：ai-1针对ai直接后继：ai+1,线性表的长度：是指线性表中数据元素的个数，n=0时为空表。位序：下标i是数据元素ai，在线性表中的位序。线性表抽象

2、数据类型的定义(逻辑结构)ADTList{数据对象:D={ai

3、aiElemSet,i=1,2,...,n,n0}数据关系:R1={

4、ai-1,aiD,i=1,2,...,n}基本操作：&符号说明函数参数是引用型InitList(&L)ListLength(L)DestroyList(&L)GetElem(L,i,&e)ClearList(&L)LocateElem(L,e)ListEmpty(L)PriorElem(L,cur_e,&pre_e)ListInsert(&L,i,e)ListDelete(&L,i,&

5、e).......}模板形式的线性表抽象类templateclassList{public:virtualboolIsEmpty()const=0;//判断是否空表virtualintLength()const=0;//求表长virtualvoidClear()=0;//置表为空virtualboolGetElem(ElemType&,int)const=0;//表中取值virtualboolSetElem(constElemType&,int)=0;//表中存值virtualintLocateElem(con

6、stElemType&)const=0;//查找符合条件的数据元素virtualintLocatePrior(constElemType&)const=0;//查找符合条件的数据前驱virtualintLocateNext(constElemType&)const=0;//查找符合条件的数据后继virtualboolInsert(constElemType&,int)=0;//表中第i个位置插入virtualboolAppend(constElemType&)=0;//表尾位置插入virtualboolDelete(ElemType&,in

7、ti)=0;//表中删除第i个数据元素virtualvoidTraverse(void(*visit)(constElemType&))const=0;//线性表的遍历};线性表的存储结构顺序存储的线性表，叫顺序表链式存储的线性表，叫链表2.2线性表的顺序表示和实现顺序表的概念用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的特点是：逻辑关系上相邻的两个元素在物理位置上也相邻。顺序表是随机存取的存储结构：可以随机存取（所需时间相同）表中任一元素，因为它的存储位置可用一个简单、直观的公式（位序的线性函数）来表示。存储地址内存状态元素序

8、号空闲aaaa12in:::::::bb+Lb+(i-1)Lb+(n-1)Lb+(maxlen-1)L12in线性表的顺序存储结构示意图数据元素ai的存储位置（内存地址）：（不同于位序i）Loc(ai)=Loc(ai-1)+LLoc(ai)=Loc(a1)+(i-1)*LLoc(ai)是ai在内存中的第一个字节的地址。L是一个元素的字节数。例如：整型线性表存储在内存中的地址是C000，表中的第7个元素的存储地址是C000+4*6=C018模板形式定义的顺序表类templateclassSqList:public

9、List{public:SqList(intm=0);//构造函数SqList(constSqList&);//拷贝构造函数~SqList();//析构函数boolIsEmpty()const{returnlen<=0;}//判断顺序表是否为空表intLength()const{returnlen;}//求表长voidClear(){len=0;}//置顺序表为空表boolGetElem(ElemType&,int)const;//表中取值boolSetElem(constElemType&,int)

10、;//表中存值intLocateElem(constElemType&)const;//查找表中符合条件的数据元素intLocatePrior(constElemType&)co