第2章线性表精选PPT.ppt

《第2章线性表精选PPT.ppt》由会员分享，可在线阅读，更多相关《第2章线性表精选PPT.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章线性表第1页，此课件共17页哦22.1 线性表的定义和运算 2.1.1 线性表的定义线性表的定义：定义：定义：线性表线性表L是由是由n个元素个元素a1，a2，an组成的组成的 有限有限 序列序列。记作记作 L=（a1，a2，an）其中其中n=0为为表长度表长度；n=0时时L为为空表空表，记作，记作L=（）（）表中元素表中元素ai的含义：在不同的场合有不同的含义。的含义：在不同的场合有不同的含义。但是，在同一表中，元素类型相同。但是，在同一表中，元素类型相同。例例：字母表（：字母表（A，B，C，D，Z）；）；数字表（数字表（0，1，2，3，4，9）；）；2014年每月天数（年每月天数（31

2、,28,31,30,31,30,31,31,30,31,30,31）;成绩表中，每个元素就是一个人的成绩信息。成绩表中，每个元素就是一个人的成绩信息。线性表的特性线性表的特性：除第一个元素外，其他元素有且仅有一个直接前趋（前驱）；除第一个元素外，其他元素有且仅有一个直接前趋（前驱）；除最后一个元素外，其他元素有且仅有一个直接后继。除最后一个元素外，其他元素有且仅有一个直接后继。逻辑结构和运算逻辑结构和运算第2页，此课件共17页哦32.1 线性表的定义和运算2.1.2 线性表的运算线性表的运算线性表有如下线性表有如下基本运算基本运算：(1)初始化：初始化：将线性表设置为空将线性表设置为空 (2)

3、求长度：求长度：返回线性表中的元素个数。返回线性表中的元素个数。(3)按序号取元素：按序号取元素：从线性表中取出指定序号的元素。从线性表中取出指定序号的元素。前提：存在该元素。否则，应当如何处理？前提：存在该元素。否则，应当如何处理？(4)按值查找元素：按值查找元素：在线性表中查找给定值的元素所在的位置。在线性表中查找给定值的元素所在的位置。若不存在，应如何给出相关信息？若不存在，应如何给出相关信息？(5)插入：插入：在线性表中给定的位置（序号）插入给定值的元素。在线性表中给定的位置（序号）插入给定值的元素。(6)删除：删除：删除线性表中指定序号的元素。删除线性表中指定序号的元素。前提：存在该

4、元素。否则，应当如何处理？前提：存在该元素。否则，应当如何处理？第3页，此课件共17页哦2.1 线性表的定义和运算设立运算是否正常的类型设立运算是否正常的类型error_code，正常时返回正常时返回success,否则返回错误类型，否则返回错误类型，如如overflow,underflow,rangeerror等。等。第4页，此课件共17页哦52.1 线性表的定义和运算线性表运算的线性表运算的C+描述描述-封装类封装类 class list public:list();int length()const;error_code get_element (const int i,elementt

5、ype&x)const;int locate(const elementtype x)const;error_code insert (const int i,const elementtype x);error_code delete_element(const int i);private:/定义其它成员 ;运算运算：(1)初始化：初始化：(2)求长度：求长度：(3)按序号取元素：按序号取元素：(4)按值查找元素：按值查找元素：(5)插入：插入：(6)删除：删除：?第5页，此课件共17页哦62.2 顺序表2.2.1 存储结构：存储结构：o讨论：讨论：n假设有一个足够大的存储空间（数组）假设

6、有一个足够大的存储空间（数组）data,用于存储线性表的元素。用于存储线性表的元素。n则将线性表中的元素依次存储到数组中则将线性表中的元素依次存储到数组中-顺序存储方式，顺序存储方式，n由此得到顺序表由此得到顺序表。n如下图所示：如下图所示：o其中，设置一个计数变量其中，设置一个计数变量count，以记录表中的元素个数。，以记录表中的元素个数。o将数组将数组data和和count作为类作为类list的数据成员。的数据成员。a1a2an01n-1maxlen-1datancount顺序表存储结构顺序表存储结构第6页，此课件共17页哦72.2 顺序表由此得到类由此得到类list如下如下：class

7、 listpublic:list();int length()const;error_code get_element(const int i,elementtype&x)const;int locate(const elementtype x)const;error_code insert(const int i,const elementtype x);error_code delete_element(const int i);private:elementtype datamaxlen;int count;list第7页，此课件共17页哦82.2 顺序表2.2.2 顺序表的运算实现：顺

8、序表的运算实现：n初始化：初始化：list:list()count=0;n求长度：求长度：int list:length()const return count;n 按序号取元素：按序号取元素：error_code list:get_element(const int i,elementtype&x)const if(i count)return rangeerror;x=datai 1;return success;第8页，此课件共17页哦92.2 顺序表n按值查找元素按值查找元素：int list:locate(const elementtype x)const for(i=0;i len

9、gth();i+)if(datai=x)return(i+1);return 0;第9页，此课件共17页哦102.2 顺序表n插入运算插入运算：分析：首先要注意，在表中插入元素的分析：首先要注意，在表中插入元素的条件条件：顺序表不满；顺序表不满；序号正确：范围在序号正确：范围在 1 n+1之间之间 插入插入操作的步骤操作的步骤包括：包括：ai an后移：后移：如何实现？如何实现？填入填入x；count+；01n-1 ai a1a2anmaxlen-1datancount顺序表结构顺序表结构 x第10页，此课件共17页哦112.2 顺序表插入算法插入算法：error_code list:inse

10、rt(const int i,const elementtype x)if(count=maxlen)return overflow;if(i length()+1)return rangeerror;for(j=count;j=i;j-)dataj=data j 1;datai 1=x;count+;return success;/溢出溢出/插入序号错插入序号错/向后移动元素向后移动元素aian第11页，此课件共17页哦122.2 顺序表n删除运算：删除运算：分析：在线性表中删除元素的分析：在线性表中删除元素的条件条件是：是：表不空；存在指定序号的元素。表不空；存在指定序号的元素。删除的删除

11、的操作步骤操作步骤：将后面的元素将后面的元素ai+1an前移前移 count-;由此得算法如下：由此得算法如下：error_code list:delete_element(const int i)if(length()=0)return underflow;if(i length()return rangeerror;for(j=i+1;j=length();j+)dataj-2=dataj-1;count-;return success;/向前移动元素向前移动元素ai+1an：/删除序号错删除序号错第12页，此课件共17页哦132.2 顺序表o分析：分析：插入算法：插入算法：在在i分别为分

12、别为 1,2,n+1 时，元素移动的次数分别为时，元素移动的次数分别为 n,n-1,0。在等概率的情况下，每插入一个元素平均移动在等概率的情况下，每插入一个元素平均移动 (n+1)n/2/(n+1)=n/2次次删除算法：删除算法：在在i分别为分别为 1,2,n时，元素移动的次数分别为时，元素移动的次数分别为 n-1,n-2,0。在等概率的情况下，每删除一个元素平均移动在等概率的情况下，每删除一个元素平均移动 (n-1)n/2/n=(n-1)/2次次结论结论：n较大时，大量移动元素，耗时。较大时，大量移动元素，耗时。解决的方法解决的方法：考虑不移动元素的存储结构。：考虑不移动元素的存储结构。第1

13、3页，此课件共17页哦2.2 顺序表2.2.3 顺序表的应用：顺序表的应用：o例例1：假设顺序表：假设顺序表A、B分别表示一个集合，设计算法以判断集合分别表示一个集合，设计算法以判断集合A是否是否是集合是集合B的子集，并分析算法的时间性能。的子集，并分析算法的时间性能。思路：思路：依次对依次对A中的每个元素，判断是否在中的每个元素，判断是否在B中出现（中出现（双重循环双重循环）14bool subset(list A,list B)int ia,ib;elementtype x,y;bool suc;for(ia=0;iaA.length();ia+)A.get_element(ia+1,x)

14、;ib=0;suc=false;while(ibdataib:ib+dataia=dataib:ia+;ib+;dataiadataib:搜索失败搜索失败15bool subset(list A,list B)int ia=0,ib=0;elementtype x,y;while(iaA.length()&iby)ib+;else return(false);if(ia=A.length()return true;else return false;时间复杂度时间复杂度：O(|A|+|B|)第15页，此课件共17页哦2.2 顺序表n例例3：设计算法将递增有序顺序表：设计算法将递增有序顺序表A、

15、B中的元素值合并为一个递增有序顺序表中的元素值合并为一个递增有序顺序表C，并要求时间尽可能少。，并要求时间尽可能少。dataiadataib:将将B中当前元素插入中当前元素插入C表中表中,ib+;16void merge_list(list A,list B,list&C)int ia=0,ib=0,ic=1;elementtype x,y;while(iaA.length()&iby)C.insert(ic,y);ic+;ib+;elseC.insert(ic,x);ic+;ia+;while(iaA.length()A.get_element(ia+1,x);C.insert(ic,x);

16、ic+;ia+;while(ibB.length()B.get_element(ib+1,y);C.insert(ic,y);ic+;ib+;第16页，此课件共17页哦2.2 顺序表o习题：1.递增有序顺序表A、B分别表示一个集合，设计算法求解A=A-B，并分析其时间性能。2.假设递增有序顺序表A、B分别表示一个集合，设计算法求解C=AB，并分析其时间性能。3.假设顺序表L中的元素按从小到大的次序排列，设计算法以删除表中的重复的元素，并要求时间尽可能少。对顺序表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9)模拟执行本算法，统计移动元素的次数。17第17页，此课件共17页哦