2.1线性表的定义 线性表的其他表示方式 1、二元组表示 L=<D,S>,其中:D={a,a2,a3, S={R}R={<a1,a2>,≤a2,a3>,<a3,a4>…<an1,an>} 2、图形表示 a1 a2 ai ai ai. an 顶点:表示数据 边:表示是数据间的顺序结构关系
第 6 页 2.1.1 线性表的定义 1、 二元组表示 L = < D,S >，其中：D = { a1， a2， a3，, ...， an } S = {R} R = {< a1 , a2 > , <a2 ,a3 >, < a 3 ,a4 > … < an-1 , an> } 线性表的其他表示方式: 2、图形表示 顶点：表示数据 边：表示是数据间的顺序结构关系 a1 a2 ai-1 ai ai+1 an
212线性表的基本操作 1.初始化线性表 L InitLis&L) 2.销毁线性表 L Destory List(&L) 3.清空线性表 L ClearlList(&L) 4.求线性表L的长度 ListLength(L) 5判断线性表L是否为空 ListEmpty(L) 6获取线性表L中的某个数据元素内容 GetElen(Ll&e) 7.检索值为e的数据元素 LocateELem(Le) 8.返回线性表L中cur_e的直接前驱元素 Prior elem( Lcur e&pree) 9.返回线性表L中cure的直接后继元素 ExteEm(L,cure,& next e) 10.在线性表L中插入一个数据元素 ListInsert(&Lle) (sis ListLength (L)+1) 11.删除线性表L中第个数据元素 List Delete(&L,&e) sis ListLength(L) 12输出线性表L中的每个数据元素 ListTraverse(L)
第 7 页 2.1.2 线性表的基本操作 1. 初始化线性表L InitList(&L) 2. 销毁线性表L DestoryList(&L) 3. 清空线性表L ClearList(&L) 4. 求线性表L的长度 ListLength(L) 5. 判断线性表L是否为空 ListEmpty(L) 6. 获取线性表L中的某个数据元素内容 GetElem(L,i,&e) 7. 检索值为e的数据元素 LocateELem(L,e) 8. 返回线性表L中cur_e的直接前驱元素 PriorElem(L,cur_e,&pre_e) 9. 返回线性表L中cur_e的直接后继元素 NextElem(L,cur_e,&next_e) 10. 在线性表L中插入一个数据元素 ListInsert(&L,i,e) (1≦i≦ ListLength(L)+1) 11. 删除线性表L中第i个数据元素 ListDelete(&L,i,&e) (1≦i≦ ListLength(L)) 12. 输出线性表L中的每个数据元素 ListTraverse(L)
212线性表的基本操作 说明: 1、上面列出的操作,只是线性表的一些常用 的基本操作; 2、不同的应用,基本操作可能是不同的; 3、线性表的复杂操作可通过基本操作实现;
第 8 页 2.1.2 线性表的基本操作 说明: 1、上面列出的操作，只是线性表的一些常用 的基本操作； 2、不同的应用，基本操作可能是不同的； 3、线性表的复杂操作可通过基本操作实现；
212线性表的基本操作 【例2-1】假设线性表L=(2356,8976,18)i=3x=56y=88, 则对L的一组操作及结果如下 ◆ ListLength(L); ∥果为5 ◆ GetElem(L,j,e) ∥e的值为89 ◆ Priorelem(L,x,&pre_x)/pex的值为23 ◆ Nextelem(L,x,& next x)∥/ next x的值为89 ◆ Locateelem(L1,x) ∥结果为2 ◆ ListInser(&L,iy)W所得结果为(23,56,88,89,76,18) ◆ ListDelete(&L,i+1,&e)∥所得结果为(23,56,.88,76,18) e的值为89
第 9 页 2.1.2 线性表的基本操作 【例2-1 】假设线性表L=(23,56,89,76,18),i=3,x=56,y=88, 则对L的一组操作及结果如下： ◆ListLength(L); ◆GetElem(L,i,e) ◆PriorElem(L,x,&pre_x) ◆NextElem(L,x,&next_x) ◆LocateElem(L,x) ◆ListInsert(&L,i,y) ◆ListDelete(&L,i+1,&e) //结果为5 //e的值为89 //pre_x的值为23 //next_x的值为89 //结果为2 //所得结果为(23,56,88,89,76,18) //所得结果为(23,56,88,76,18) e的值为89
212线性表的基本操作 【例2-2】利用两个线性表La和Lb分别表示两个集合A和 B,现要求一个新的集合A=AUB。 【分析】这个问题相当于对线性表作如下操作: 扩大线性表La,将存在于线性表Lb中而不存在于线性表La中 的数据元素插入到线性表La中去。 【具体步骤】 (1)从线性表Lb中取得一个数据元素; (2)依该数据元素的值在线性表La中进行查访; (3)若线性表La中不存在和其值相同的数据元素,则将从Lb中 删除的这个数据元素插入到线性表La中; (4)重复以上操作直至Lb为空表
第 10 页 2.1.2 线性表的基本操作 【例2-2 】利用两个线性表La和Lb分别表示两个集合A和 B，现要求一个新的集合A=A∪B。 【分析 】这个问题相当于对线性表作如下操作： 扩大线性表La，将存在于线性表Lb中而不存在于线性表La中 的数据元素插入到线性表La中去。 【具体步骤 】 （1）从线性表Lb中取得一个数据元素； （2）依该数据元素的值在线性表La中进行查访； （3）若线性表La中不存在和其值相同的数据元素，则将从Lb中 删除的这个数据元素插入到线性表La中； （4）重复以上操作直至Lb为空表