线性表的类型定义、顺序表示和实现.pptx

第2章线性表线性表是一种最简单的线性结构。什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：在数据元素的非空有限集中，①存在惟一的一个被称做"第一个"的数据元素；②存在惟一的一个被称做"最后一个"的数据元素；③除第一个之外，集合中的每个数据元素均只有一个前驱；④除最后一个之外，集合中的每个数据元素均只有一个后继。这里的"有序"仅指在数据元素之间存在一个"领先"或"落后"的次序关系，而非指数据元素"值"的大小可比性。比较典型的线性结构：线性表、栈、队列、串等。2.1线性表的类型定义2.1.1线性表的定义说明：2.1.2线性表的抽象数据类型2.1.3操作举例voidunionList(SqList&la,SqListlb){intlbSize=getSize(lb);ElemTypee;for(inti=1;i<=lbSize;++i){e=getElem(lb,i);if(!locateElem(la,e,equal))insertElem(la,e,la.size+1);}}intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}2.2线性表的顺序表示和实现2.2.1线性表的顺序表示第i个元素的地址线性表的顺序存储结构示意图用C++语言描述的顺序表类型如下所示：sqlist.hboolinitList(SqList&L,intms);voidclearList(SqList&L);intgetSize(SqListL);boolisEmpty(SqListL);boolisFull(SqListL);voidtraverList(SqListL,void(*visit)(ElemType&));ElemType&getElem(SqListL,intpos);intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType));intfindList(SqListL,ElemTypee);boolinsertElem(SqList&L,ElemTypee,intpos);booldeleteElem(SqList&L,intpos);boolcreateList(SqList&L,intn,void(*visit)(ElemType&));2.2.2线性表顺序存储结构上的基本运算sqlist.cpp⑵删除线性表的所有元素，使之成为空表在顺序存储方式下实现此操作只要将线性表的长度置0即可。voidclearList(SqList&L){L.size=0;}⑶检查线性表是否为空boolisEmpty(SqListL){returnL.size==0;}⑷获取表元素的个数intgetSize(SqListL){returnL.size;}⑸检查线性表是否已满boolisFull(SqListL){returnL.size==L.maxSize;}⑺遍历线性表遍历一个线性表就是从线性表的第一个元素起，按照元素之间的逻辑顺序，依次访问每一个元素，并且每个元素只被访问一次，直到访问完所有元素为止。voidtraverList(SqListL,void(*visit)(ElemType&)){for(inti=0;i<L.size;++i)visit(L.list[i]);cout<<endl;}如要依次输出每个元素的值，visit()的实参可定义如下：voidprint(ElemType&e){cout<<"id:"<<e.id<<"age:"<<e.age<<endl;}⑻查找线性表中满足给定条件的元素intlocateElem(SqList&L,ElemTypee,int(*compare)(ElemType,ElemType)){for(inti=0;i<L.size;++i)if(compare(L.list[i],e)==1)returni+1;return0;}如要查找与e的相等（某对应成员的值相等）的元素，则compare()的实参可定义如下：intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}⑼向线性表中的指定位置插入一个元素原表：a1，a2，…，ai-1，ai，ai+1，…，an插入后的表：a1，a2，…，ai-1，b，ai，ai+1，…，an①ai-1和ai逻辑关系发生变化；②因逻辑相邻的数据元素物理位置上也相邻，因此，除非i=n+1，否则必须将原表中位置n，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，在该位置上插入新结点b。booli