ch2线性表.ppt

《ch2线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、内容提要了解线性表的定义。掌握线性表的顺序存储结构、链式存储结构以及相关的基本操作算法描述。了解双向链表存储结构。第二章线性表Knowledge第二章线性表线性结构是一个数据元素的有序（次序）集。线性结构的特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱，称为直接前驱（ImmediatePredecessor）。除最后一个外，集合中的每个数据元素均只有一个后继，称为直接后继（ImmediateSuccessor）。2.1

2、线性表的类型定义一、定义：一个线性表是n个数据元素的有限序列例：英文字母表（A,B,C,…..Z)是一个线性表例：数据元素二、线性表的特征：元素个数n称为表长度，n=0，称为空表1

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

4、ai－1,aiD,i=1,2,...,n}基本操作：&符号说明函数参数是引用型I

5、nitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)PutElem(&L,i,e)LocateElem(L,e)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit())}⑴线性表初始化：InitList(&L)；—构造一个空的线性表L，即表的初始化。⑵求线性表的长

6、度：ListLength(L)；—返回线性表中数据元素的个数，即表长。⑶取表中元素：GetElem(L,i,&e)；—取线性表L中的第i个结点，要求1≤i≤ListLength(L)⑷插入操作：ListInsert(&L,i,e)；—在线性表L的第i个位置上插入一个值为e的数据元素。(5)删除操作：ListDelete(&L,i,&e)；—在线性表L中删除位序为i的数据元素。⑹按值查找：LocateElem(L,e)；—在L中查找值为e的结点，并返回该结点在L中的位置。若L中有多个结点的值和e相同，则返回首次找到的结点位置；若L

7、中没有结点的值为e，则返回一个特殊值(如零)表示查找失败。课后思考：应用基本操作实现删除线性表La中大于e的所有数据元素：DelElems(&L,e)CopyList(La,&Lb){//应用基本操作：实现CopyList(La,&Lb)InitList(Lb)；LenA=ListLength(La);for(i=1;i<=LenA;i++){GetElem(La,i,e);ListInsert(Lb,i,e);}}课堂练习：应用基本操作实现CopyList(La,&Lb)例1:设计求A=A∪B的算法分析：建立线性表La、Lb分

8、别表示集合A和B，将Lb中存在而La中不存在的元素e插入La中，因此，本算法的基本操作是查找(比较)。算法思想：1.从Lb中依次取得每个元素eGetElem(Lb,i,e)2.判断该元素e是否在La中存在LocateElem(La,e)3.若不存在，则将元素e插入到La中ListInsert(La,i,e)基于逻辑结构的算法描述：voidUnion(&La,Lb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);

9、if(!LocateElem(La,e))ListInsert(La,++La_len,e);}}例2：巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。算法思想：1、初始化：设LC为空表，设置变量i，j的初值为1，分别指向LA，LB的第一个DE，设K表示LC的表长，初值为0Init_List(LC)2、当i≤Length_List(LA)&&j≤Length_List(LB)判断：若i所指元素≤j所指元素，则将i所指元素插入在LC的k+1前

10、(即LC的表尾)，且i、k的值分别+1;否则，将j所指元素插入在LC的k+1前(即LC的表尾)，且j、k的值分别+1;3、重复2，直到某个表LA或LB的元素插入完毕；4、将未插入完的表LA或LB的余下元素，依次插入LC中。2.2线性表的顺序表示和实现一、顺序表（