《2线性表(福建教师招考信息技术算法和程序部分)1193.pptx》由会员分享，可在线阅读，更多相关《2线性表(福建教师招考信息技术算法和程序部分)1193.pptx（103页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 线形表数据结构数据结构3/25/20232 2数据结构数据结构1 1、线性表线性表(Linear List)(Linear List)：定义：定义：定义：定义：由由由由n(n0)n(n0)n(n0)n(n0)个数据元素个数据元素个数据元素个数据元素(结点结点结点结点)a)a)a)a1 1 1 1，a a a a2 2 2 2，a a a an n n n组成的有限序列。记组成的有限序列。记组成的有限序列。记组成的有限序列。记作：作：作：作：L=(a L=(a L=(a L=(a1 1 1 1，a a a a2 2 2 2，aaaai-1i-1i-1i-1，a a a ai i i i，
2、a a a ai+1i+1i+1i+1，aaaan n n n)其中数据元素的个数其中数据元素的个数其中数据元素的个数其中数据元素的个数n n n n定义为表的长度。当定义为表的长度。当定义为表的长度。当定义为表的长度。当n=0n=0n=0n=0时称为空表，常时称为空表，常时称为空表，常时称为空表，常常将非空的线性表常将非空的线性表常将非空的线性表常将非空的线性表(n0)(n0)(n0)(n0)这里的数据元素这里的数据元素这里的数据元素这里的数据元素a a a ai i i i(1in)(1in)(1in)(1in)只是一个只是一个只是一个只是一个抽象的符号，其具体含义在不同的情况下可以不同。
3、抽象的符号，其具体含义在不同的情况下可以不同。抽象的符号，其具体含义在不同的情况下可以不同。抽象的符号，其具体含义在不同的情况下可以不同。例例例例1 1 1 1、26262626个英文字母组成的字母表个英文字母组成的字母表个英文字母组成的字母表个英文字母组成的字母表 （A A A A，B B B B，C C C C、Z Z Z Z）例例例例2 2 2 2、某校从、某校从、某校从、某校从1978197819781978年到年到年到年到1983198319831983年各种型号的计算机拥有量的变化情年各种型号的计算机拥有量的变化情年各种型号的计算机拥有量的变化情年各种型号的计算机拥有量的变化情况。
4、况。况。况。（6 6 6 6，17171717，28282828，50505050，92929292，188188188188）数据结构数据结构3/25/20233 3数据结构数据结构例例例例3 3 3 3、学生健康情况登记表如下：、学生健康情况登记表如下：、学生健康情况登记表如下：、学生健康情况登记表如下：例例例例4 4 4 4、一副扑克的点数、一副扑克的点数、一副扑克的点数、一副扑克的点数 （2 2 2 2，3 3 3 3，4 4 4 4，J J J J，Q Q Q Q，K K K K，A A A A）姓姓姓姓 名名名名学学学学 号号号号性性性性 别别别别年龄年龄年龄年龄 健康情况健康情况
5、健康情况健康情况王小林王小林王小林王小林790631790631 男男男男 18 18 健康健康健康健康陈陈陈陈 红红红红790632790632 女女女女 20 20 一般一般一般一般刘建平刘建平刘建平刘建平790633790633 男男男男 21 21 健康健康健康健康张立立张立立张立立张立立790634790634 男男男男 17 17 神经衰弱神经衰弱神经衰弱神经衰弱.数据结构数据结构3/25/20234 4数据结构数据结构线性表线性表 元素及元素之间的关系为线性元素及元素之间的关系为线性线性：线性：线性：线性：（1 1 1 1）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节
6、点）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节点）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节点）有且仅有一个开始节点（该节点只有一个后继节点，没有前趋节点）（2 2 2 2）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）有且仅有一个结束节点（该节点只有一个前趋节点，没有后继节点）（3 3 3 3）除首节点，其余节点有且仅有一个前趋）除首节点，其余节点有且仅有一个前趋）除首节点，其余节点有且仅有一个前趋）除首节点，其余节点有且仅有一个前
7、趋k1k2k3k4k1k2k3（4 4 4 4）除尾节点，其余节点有且仅有一个后继）除尾节点，其余节点有且仅有一个后继）除尾节点，其余节点有且仅有一个后继）除尾节点，其余节点有且仅有一个后继数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。数据结构数据结构3/25/20235 5数据结构数据结构线性表的类型定义线性表的类型定义抽象数据类型线性表的定义抽象数据类
8、型线性表的定义 ADT List 数据对象数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,aiD,i=2,.,n 基本操作基本操作：初始化初始化 InitList(&L)操作结果：构造一个空的线性表L。结构销毁结构销毁 DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。引用型操作引用型操作 ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。数据结构数据结构3/25/20236 6
9、数据结构数据结构ADT ListADT ListGetElem(L,i,GetElem(L,i,&e)e)初始条件：线性表初始条件：线性表L L已存在，已存在，1iLengthList(L)1iLengthList(L)操作结果：用操作结果：用e e返回返回L L中第中第i i个元素的值。个元素的值。LocateElem(L,e,compare()LocateElem(L,e,compare()初始条件：线性表初始条件：线性表L L已存在，已存在，compare()compare()是元素判定函数。是元素判定函数。操作结果：返回操作结果：返回L L中中第第第第1 1个个个个与与e e满足满足满
10、足满足关系关系 compare()compare()的元素的位序。若这样的的元素的位序。若这样的元素不存在，则返回值为元素不存在，则返回值为0 0。PriorElem(L,cur_e,PriorElem(L,cur_e,&pre_e)pre_e)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：若操作结果：若cur_ecur_e是是L L的元素，但不是第一个，则用的元素，但不是第一个，则用pre_e pre_e 返回它的前驱，返回它的前驱，否则操作失败，否则操作失败，pre_epre_e无定义。无定义。NextElem(L,cur_e,NextElem(L,cur_e,&next
11、_e)next_e)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：若操作结果：若cur_ecur_e是是L L的元素，但不是最后一个，则用的元素，但不是最后一个，则用next_enext_e返回它的后继，返回它的后继，否则操作失败，否则操作失败，next_enext_e无定义。无定义。ListTraverse(L,visit()ListTraverse(L,visit()初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：操作结果：依次依次依次依次对对L L的每个元素调用函数的每个元素调用函数 visit()visit()。一旦。一旦visit()visit()失
12、败，则操作失失败，则操作失败。败。数据结构数据结构3/25/20237 7数据结构数据结构ADT ListADT List 加工型操作加工型操作加工型操作加工型操作 ClearList(ClearList(&L)L)初始条件：线性表初始条件：线性表L L已存在。已存在。操作结果：将操作结果：将L L重置为空表。重置为空表。PutElem(L,i,PutElem(L,i,&e)e)初始条件：线性表初始条件：线性表L L已存在，已存在，1iLengthList(L)1iLengthList(L)操作结果：操作结果：L L中第中第i i个元素赋值同个元素赋值同e e的值。的值。ListInsert(
13、ListInsert(&L,i,e)L,i,e)初始条件：线性表初始条件：线性表L L已存在，已存在，1iLengthList(L)+11iLengthList(L)+1 操作结果：在操作结果：在L L的第的第i i个元素之前插入新的元素个元素之前插入新的元素e e，L L的长度增的长度增1 1。ListDelete(ListDelete(&L,i,L,i,&e)e)初始条件：线性表初始条件：线性表L L已存在且非空，已存在且非空，1iLengthList(L)1iLengthList(L)操作结果：删除操作结果：删除L L的第的第i i个元素，并用个元素，并用e e 返回其值，返回其值，L
14、L的长度减的长度减1 1。ADT ADT List List 数据结构数据结构3/25/20238 8数据结构数据结构举例举例 假设线性表假设线性表L=(23,56,89,76,18),i=3,x=56,y=88,L=(23,56,89,76,18),i=3,x=56,y=88,则对则对L L的一组操作及结果如下：的一组操作及结果如下：ListLength(L)ListLength(L)/所得结果为所得结果为5 5GetElem(L,i,&e)GetElem(L,i,&e)/所得结果为所得结果为8989PriorElem(L,PriorElem(L,x x,&pre_e),&pre_e)/所得
15、结果为所得结果为2323NextElem(L,NextElem(L,x x,&next_e),&next_e)/所得结果为所得结果为8989LocateElem(L,x,equalLocateElem(L,x,equal)/所得结果为所得结果为2 2ListInsert(&L,i,y)/ListInsert(&L,i,y)/所得结果为所得结果为(23,56,88,89,76,18)(23,56,88,89,76,18)ListDelete(&L,i+1,&e)ListDelete(&L,i+1,&e)/所得结果为所得结果为(23,56,88,76,18)89(23,56,88,76,18)89
16、数据结构数据结构3/25/20239 9数据结构数据结构 如何实现线性表的其它操作如何实现线性表的其它操作例例例例2-1 2-1 利用两个线性表利用两个线性表利用两个线性表利用两个线性表LALA和和和和LBLB分别表示两个集合分别表示两个集合分别表示两个集合分别表示两个集合A A和和和和B B，现要求一个新的集合，现要求一个新的集合，现要求一个新的集合，现要求一个新的集合A=AA=AB B。设计思想：设计思想：扩大线性表扩大线性表LALA，将存在于线性表，将存在于线性表LBLB中而不存在中而不存在于线性表于线性表LALA中的数据元素插入到线性表中的数据元素插入到线性表LALA中去。中去。分下列
17、三步进行：分下列三步进行：1 1从线性表从线性表LBLB中依次取得每个数据元素中依次取得每个数据元素;2 2依值在线性表依值在线性表LALA中进行查访中进行查访;3 3若不存在，则插入之。若不存在，则插入之。数据结构数据结构3/25/20231010数据结构数据结构A=ABA=AB算法描述：算法描述：算法描述：算法描述：/将所有在线性表将所有在线性表将所有在线性表将所有在线性表LbLbLbLb中但不在中但不在中但不在中但不在LaLaLaLa中的数据元素插入到中的数据元素插入到中的数据元素插入到中的数据元素插入到LaLaLaLa中中中中void Union(List&Lavoid Union(L
18、ist&Lavoid Union(List&Lavoid Union(List&La，List Lb)List Lb)List Lb)List Lb)/求线性表的长度求线性表的长度求线性表的长度求线性表的长度 La-len=ListLength(La);La-len=ListLength(La);La-len=ListLength(La);La-len=ListLength(La);Lb-len=ListLength(Lb);Lb-len=ListLength(Lb);Lb-len=ListLength(Lb);Lb-len=ListLength(Lb);for(i=1;i=Lb-len;i+
19、)for(i=1;i=Lb-len;i+)for(i=1;i=Lb-len;i+)for(i=1;i=Lb-len;i+)/取取取取LbLbLbLb中第中第中第中第i i i i个数据元素赋给个数据元素赋给个数据元素赋给个数据元素赋给e e e e GetElem(Lb GetElem(Lb GetElem(Lb GetElem(Lb，i i i i，e);e);e);e);/La/La/La/La中不存在和中不存在和中不存在和中不存在和 e e e e 相同的数据元素，则插入之相同的数据元素，则插入之相同的数据元素，则插入之相同的数据元素，则插入之 if(!LocateElem(La if(
20、!LocateElem(La if(!LocateElem(La if(!LocateElem(La，e e e e，equal)equal)equal)equal)ListInsert(LaListInsert(LaListInsert(LaListInsert(La，+La-en+La-en+La-en+La-en，e);e);e);e);/Union/Union/Union/Union数据结构数据结构3/25/20231111数据结构数据结构A=ABA=AB时间复杂度分析：时间复杂度分析：GetElemGetElemGetElemGetElem取遍取遍取遍取遍LbLbLbLb表元素需表元
21、素需表元素需表元素需Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)次；次；次；次；循环体内的循环体内的循环体内的循环体内的LocateLocateLocateLocate操作平均需操作平均需操作平均需操作平均需ListLength(La)ListLength(La)ListLength(La)ListLength(La)次次次次最坏情况为：最坏情况为：最坏情况为：最坏情况为：ListLength(La)ListLength(La)ListLength(La)ListLeng
22、th(La)总的时间复杂度：总的时间复杂度：总的时间复杂度：总的时间复杂度：O ListLength(Lb)*ListLength(La)O ListLength(Lb)*ListLength(La)O ListLength(Lb)*ListLength(La)O ListLength(Lb)*ListLength(La)数据结构数据结构3/25/20231212数据结构数据结构例例 2-1-2 2-1-2已知一个非纯集合已知一个非纯集合已知一个非纯集合已知一个非纯集合 B B B B，试构造集合，试构造集合，试构造集合，试构造集合A A A A，要求集合，要求集合，要求集合，要求集合A A
23、A A中只中只中只中只包含集合包含集合包含集合包含集合B B B B中所有值不相同的数据元素。中所有值不相同的数据元素。中所有值不相同的数据元素。中所有值不相同的数据元素。设计思想：设计思想：设计思想：设计思想：解法一：解法一：同上例，分别以线性表同上例，分别以线性表LALA和和LBLB表示集合表示集合A A和和B B，则首先初，则首先初始化线性表始化线性表LALA为空表，之后的操作和例为空表，之后的操作和例2-12-1完全相同。完全相同。解法二：解法二：仍以线性表表示集合。只是求解之前先对线性表仍以线性表表示集合。只是求解之前先对线性表LBLB中的中的数据元素进行排序，即线性表数据元素进行排
24、序，即线性表LBLB中的数据元素依其值从中的数据元素依其值从小到大有序排列，则值相同的数据元素必相邻。则上述小到大有序排列，则值相同的数据元素必相邻。则上述操作中的第二步就不需要进行从头至尾的查询。操作中的第二步就不需要进行从头至尾的查询。数据结构数据结构3/25/20231313数据结构数据结构A=BA=Bvoid purge(List&La,List Lb)void purge(List&La,List Lb)/已知线性表已知线性表已知线性表已知线性表LbLb中的数据元素依值非递减有序排列，现构造线性表中的数据元素依值非递减有序排列，现构造线性表中的数据元素依值非递减有序排列，现构造线性表
25、中的数据元素依值非递减有序排列，现构造线性表LaLa，/使使使使LaLa中只包含中只包含中只包含中只包含LbLb中所有值不相同的数据元素中所有值不相同的数据元素中所有值不相同的数据元素中所有值不相同的数据元素 InitList InitList（LaLa）；）；）；）；/初始化初始化初始化初始化LaLa为空表为空表为空表为空表 La_len=ListLength(La);La_len=ListLength(La);Lb_len=ListLength(Lb);/Lb_len=ListLength(Lb);/求线性表的长度求线性表的长度求线性表的长度求线性表的长度 for(i=1;i=Lb_len
26、;i+)for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/GetElem(Lb,i,e);/取取取取LbLb中第中第中第中第i i个数据元素赋给个数据元素赋给个数据元素赋给个数据元素赋给e e if(ListEmpty(La)|!equal(enif(ListEmpty(La)|!equal(en，e)e)ListInsert(La,+La_len,e);ListInsert(La,+La_len,e);/La/La中不存在和中不存在和中不存在和中不存在和 e e 相同的数据元素，相同的数据元素，相同的数据元素，相同的数据元素，则插入之则插入之则插入之则插入之 en=e
27、;/enen=e;/en，LaLa中的已插入元素中的已插入元素中的已插入元素中的已插入元素 /for /for/purge/purge数据结构数据结构3/25/20231414数据结构数据结构A=BA=B时间复杂度分析：时间复杂度分析：时间复杂度分析：时间复杂度分析：GetElemGetElemGetElemGetElem取遍取遍取遍取遍LbLbLbLb表元素需表元素需表元素需表元素需Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)Lb_len=ListLength(Lb)次；次；次；次；解法一解法一解法一解法一:循
28、环体内的循环体内的循环体内的循环体内的LocateLocateLocateLocate操作平均需操作平均需操作平均需操作平均需ListLength(Lb)ListLength(Lb)ListLength(Lb)ListLength(Lb)次次次次故时间复杂度为：故时间复杂度为：故时间复杂度为：故时间复杂度为：O(ListLength O(ListLength O(ListLength O(ListLength2 2 2 2(LB)(LB)(LB)(LB)；解法二的时间复杂度：解法二的时间复杂度：解法二的时间复杂度：解法二的时间复杂度：循环体内的基本操作与表长无关循环体内的基本操作与表长无关循环
29、体内的基本操作与表长无关循环体内的基本操作与表长无关故时间复杂度为：故时间复杂度为：故时间复杂度为：故时间复杂度为：O(ListLength(Lb)O(ListLength(Lb)O(ListLength(Lb)O(ListLength(Lb)数据结构数据结构3/25/20231515数据结构数据结构C=AB C=AB 例例例例2-2 2-2 2-2 2-2 巳知线性表巳知线性表巳知线性表巳知线性表LALALALA和线性表和线性表和线性表和线性表LBLBLBLB中的数据元素按值非中的数据元素按值非中的数据元素按值非中的数据元素按值非递减有序排列，现要求将递减有序排列，现要求将递减有序排列，现要
30、求将递减有序排列，现要求将LALALALA和和和和LBLBLBLB归并为一个新的线性归并为一个新的线性归并为一个新的线性归并为一个新的线性表表表表LCLCLCLC，且，且，且，且LCLCLCLC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。设计思想：设计思想：1、LC为空表，用来存放LA和LB的元素2、表LA和LB的元素逐一进行比较取小者放入表LC中3、插入表LA或表LB中剩余的元素数据结构数据结构3/25/20231616数据结构数据结构算法描述：算法描述：/已知线性表已知线性表已知线性表已知线性表LaLa和和和和Lb
31、Lb中的元素按值非递中的元素按值非递中的元素按值非递中的元素按值非递 减排列。减排列。减排列。减排列。/归并归并归并归并LaLa和和和和LbLb得到新的线性表得到新的线性表得到新的线性表得到新的线性表 Lc Lc，LcLc的元素也按值非递减排列。的元素也按值非递减排列。的元素也按值非递减排列。的元素也按值非递减排列。void MergeList(List La,List Lb,List&Lc)void MergeList(List La,List Lb,List&Lc)InitList(Lc);InitList(Lc);i=j=1;i=j=1;k=0;k=0;La_len=ListLength
32、(La);La_len=ListLength(La);Lb_len=ListLength(Lb);Lb_len=ListLength(Lb);whilewhile(i=La_len)&(j=Lb_len)(i=La_len)&(j=Lb_len)/La/La和和和和LbLb均非空均非空均非空均非空 GetElem(La,i,ai);GetElem(Lb,j,bj);GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)if(ai=bj)ListInsert(Lc,+k,ai);ListInsert(Lc,+k,ai);+i;+i;else else ListIn
33、sert(Lc,+k,bj);ListInsert(Lc,+k,bj);+j;+j;数据结构数据结构3/25/20231717数据结构数据结构C=AB C=AB whilewhile (i=La_len)(i=La_len)GetElem(La,i+,ai);GetElem(La,i+,ai);ListInsert(Lc,+k,ai);ListInsert(Lc,+k,ai);while while(j=Lb_len)(j=Lb_len)GetElem(Lb,j+,bj);GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);ListInsert(Lc,+k,bj);/
34、MergeList /MergeList 数据结构数据结构3/25/20231818数据结构数据结构C=AB C=AB 时间复杂度分析：时间复杂度分析：时间复杂度分析：时间复杂度分析：vv 该算法中包含了三个该算法中包含了三个WHILEWHILE语句，其中，第一个处语句，其中，第一个处理了某一张表的全部元素和另一张表的部分元素；后理了某一张表的全部元素和另一张表的部分元素；后两个两个WHILEWHILE循环只可能有一个执行，用来完成将未归并循环只可能有一个执行，用来完成将未归并到到LCLC中的余下部分元素插入到中的余下部分元素插入到LCLC中。中。“插入插入”是估量是估量归并算法时间复杂度的基
35、本操作，其语句频度为：归并算法时间复杂度的基本操作，其语句频度为：LENGTHLENGTHLENGTHLENGTH（LALALALA）+LENGTH+LENGTH+LENGTH+LENGTH（LBLBLBLB）vv 该算法的时间复杂度为：该算法的时间复杂度为：O O O O（LENGTHLENGTHLENGTHLENGTH（LALALALA）+LENGTH+LENGTH+LENGTH+LENGTH（LBLBLBLB）vv 若若LALA和和LBLB的元素个数为同数量级的元素个数为同数量级n n，则该算法的时，则该算法的时 间复杂度为间复杂度为:O(O(O(O(n)n)n)n)数据结构数据结构3/
36、25/20231919数据结构数据结构线性表的顺序表示和实现线性表的顺序表示和实现一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构一、线性表的顺序存储结构顺序表：顺序表：顺序表：顺序表：线性表的顺序存储结构线性表的顺序存储结构把线性表的结点按逻辑顺序（把线性表的结点按逻辑顺序（顺序）依次存放在一组地址顺序）依次存放在一组地址连续连续连续连续的存储单元里。的存储单元里。1 1、线性表的地址计算：、线性表的地址计算：、线性表的地址计算：、线性表的地址计算：假设线性表的每个元素需占用假设线性表的每个元素需占用 l l 个存储单元，并以所占的个存储单元，并以所占的第一个单元的存
37、储地址作为数据元素的存储位置（首地址）。第一个单元的存储地址作为数据元素的存储位置（首地址）。则线性表中第则线性表中第i+1i+1个数据元素的存储位置个数据元素的存储位置LOC(aLOC(a i+1 i+1)和第和第i i个个数数据元素的存储位置据元素的存储位置LOC(aLOC(ai i)之间满足下列关系：之间满足下列关系：LOC(aLOC(a i+1 i+1)=LOC(a)=LOC(a i i)+)+l l线性表的第线性表的第i i个数据元素个数据元素aiai的存储位置为：的存储位置为：LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+()+(i i-1)*-1)*l l数据结
38、构数据结构3/25/20232020数据结构数据结构存储示意：存储示意：数据结构数据结构3/25/20232121数据结构数据结构线性表的顺序存储线性表的顺序存储用数组实现线性表（顺序存储、顺序表）用数组实现线性表（顺序存储、顺序表）线性表元素：线性表元素：a1、a2、a3、a4.数组元素：数组元素：a0、a1、a2、a3线性关系：线性关系：线性关系：线性关系：a1a2a3a4数组下标大小数组下标大小数组下标大小数组下标大小注意：注意：C C语言中的数组下语言中的数组下标从标从“0”“0”开始，因此，开始，因此，若若L L是是SqlistSqlist类型的顺序类型的顺序表，则表中第表，则表中第
39、i i个元素是个元素是l.datai-1l.datai-1。数据结构数据结构3/25/20232222数据结构数据结构ElemType*getElem(int pos);/若1=pos=cursize,则返回指示第pos个元素/的位置;否则返回NULL int Location(ElemType&e);/返回其值和e所指元素值相同的数据元素在线性/表中的序号，若不存在这样的数据元素，则返回0 /modification void clearList(void);Status putElem(int pos,const ElemType&e);/若1=pos=cursize,则修改线性表中第po
40、s个数/据元素的值，并且返回OK;否则不进行修改并返/回ERROR Status Insert(int pos,const ElemType&e);/若1=pos=cursize+1,则插入元素e在线性表/中第pos个数据元素之前，并且返回OK;否则不/进行插入并返回ERROR Status*Delete(int pos,ElemType&e);/若1=pos MAXLISTSIZE)?MAXLISTSIZE:size;elemPtr=new ElemType size;cursize=0;数据结构数据结构3/25/20232626数据结构数据结构插入示意：插入示意：数据结构数据结构3/25/
41、20232727数据结构数据结构插入运算插入运算插入运算插入运算uu问题描述问题描述问题描述问题描述以以以以a1a1开始的线性表中开始的线性表中开始的线性表中开始的线性表中在第在第在第在第i i个元素前插入一个新元素个元素前插入一个新元素个元素前插入一个新元素个元素前插入一个新元素new_nodenew_node。a1a2ai-1aiana1a2ai-1newnodeai+1aianai+1数据结构数据结构3/25/20232828数据结构数据结构插入运算插入运算从从ai开始向后移动开始向后移动从从an开始向前每个元素向后移一格开始向前每个元素向后移一格a1a2ai-1aiai+1.anaia
42、iaiaia1a2ai-1aiai+1ananai+1aifor(j=i;j L.length;j+)for(j=i;j i;j-)for(j=L.length;j i;j-)L.elem j+1 =L.elem j;L.elem j+1 =L.elem j;newnode数据结构数据结构3/25/20232929数据结构数据结构算法思想算法思想：进行合法性检查，1=i=n+1；利用线性表是否已满；将第n个至第i个元素逐一后移一个单元；在第i个位置处插入新元素；将表的长度加1。数据结构数据结构3/25/20233030数据结构数据结构Status ListInsert_Sq(Sqlist&LS
43、tatus ListInsert_Sq(Sqlist&L，int i int i，ElemType e)ElemType e)/在顺序线性表在顺序线性表L L中第中第 i i 个位置之前插入新的元素个位置之前插入新的元素e e/i /i 的合法值为的合法值为 1 1 i ListLength_Sq(L)i ListLength_Sq(L)+1 +1 if(i L.length+1)if(i L.length+1)return ERROR;/ireturn ERROR;/i值不合法值不合法if(L.length=L.ListSize)if(L.length=L.ListSize)exit(ove
44、rflow);exit(overflow);for(i=L.length-1;i=I-1;i-)for(i=L.length-1;i=I-1;i-)L.elemi+1=L.elemi;L.elemi+1=L.elemi;L.elemI-1=x;L.elemI-1=x;l.length+;l.length+;数据结构数据结构3/25/20233131数据结构数据结构删除示意：删除示意：数据结构数据结构3/25/20233232数据结构数据结构anai删除运算删除运算删除运算删除运算uu问题描述：删除第问题描述：删除第问题描述：删除第问题描述：删除第i i个元素个元素个元素个元素uu算法实现分析算
45、法实现分析算法实现分析算法实现分析a1a2aianai1a1a2ai1ai+1ananai+1数据结构数据结构3/25/20233333数据结构数据结构删除运算删除运算算法实现分析算法实现分析uu从从从从anan开始向前逐个元素向前移动开始向前逐个元素向前移动开始向前逐个元素向前移动开始向前逐个元素向前移动uu从从从从ai1开始向后逐个元素向前移动开始向后逐个元素向前移动开始向后逐个元素向前移动开始向后逐个元素向前移动a1a2ai+1aianai-1anananfor(i=L.length-1;i i;i-)for(i=L.length-1;i i;i-)L.elem i-1 =L.elem
46、i;L.elem i-1 =L.elem i;a1a2ai-1aiai+1 anfor(i=i;i L.length-1;i+)for(i=i;i L.length-1;i+)L.elem i =L.elem i+1;L.elem i =L.elem i+1;数据结构数据结构3/25/20233434数据结构数据结构算法思想：算法思想：进行合法性检查，进行合法性检查，i i是否满足是否满足1=i=n1=i=n；判线性表是否已空，判线性表是否已空，v.last=0v.last=0；将第将第i+1i+1至第至第n n个元素逐一向前移一个位置；个元素逐一向前移一个位置；将表的长度减将表的长度减1 1
47、。数据结构数据结构3/25/20233535数据结构数据结构Status ListDelete_Sq (SqList&L,int i,ElemType&e)/ListDelete_Sqfor(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移被删除元素之后的元素左移-L.length;/表长减表长减1 1return OK;算法时间复杂度算法时间复杂度为为:O(ListLength(L)p=&(L.elemi-1);/p 为被删除元素的位置为被删除元素的位置e=*p;/被删除元素的值赋给被删除元素的值赋给 eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置
48、if(i L.length)return ERROR;/删除位置不合法删除位置不合法元素左移元素左移数据结构数据结构3/25/20233636数据结构数据结构考虑移动元素的平均情况考虑移动元素的平均情况:假设删除第 i 个元素的概率为 ,则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值移动元素次数的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值移动元素的期望值为：数据结构数据结构3/25/20233737数据结构数据结构p21 18 30 75 42 56 8721 18 30 75L.length-10ppq8756p=&(L.elemi-1
49、);q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)p数据结构数据结构3/25/20233838数据结构数据结构 int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/在顺序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素，/若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0/LocateElem_Sq O(ListLength(L)算法的算法的时间复杂度时间复杂
50、度为：为：i=1;/i i 的初值为第的初值为第 1 1 元素的位序元素的位序p=L.elem;/p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;(*compare)(*p+,e)利用顺序表类实现线性表的其它操作利用顺序表类实现线性表的其它操作数据结构数据结构3/25/20233939数据结构数据结构例如：顺序表23 75 41 38 54 62 17L.elemL.length=7L.listsizee=38pppppi 1