算法与数据结构 第二章线性表课件.ppt

《算法与数据结构 第二章线性表课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构（第二章线性表）12.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,28,31,30,31,30,31,31,30,31,30,31）;成绩表中，每个元素就是一个人的成绩信息。线性表的特性：除第一个元素外，其他元

2、素有且仅有一个直接前趋（前驱）；除最后一个元素外，其他元素有且仅有一个直接后继。逻辑结构和运算22.1线性表的定义和运算2.1.2线性表的运算线性表有如下基本运算：(1)初始化：将线性表设置为空(2)求长度：返回线性表中的元素个数。(3)按序号取元素：从线性表中取出指定序号的元素。前提：存在该元素。否则，应当如何处理？(4)按值查找元素：在线性表中查找给定值的元素所在的位置。若不存在，应如何给出相关信息？(5)插入：在线性表中给定的位置（序号）插入给定值的元素。(6)删除：删除线性表中指定序号的元素。前提：存在该元素。否则，应当如何处理？32.1线性表

3、的定义和运算设立运算是否正常的类型error_code，正常时返回success,否则返回错误类型，如overflow,underflow,rangeerror等。2.1线性表的定义和运算线性表运算的C++描述----封装类classlist{public:list();intlength()const;error_codeget_element(constinti,elementtype&x)const;intlocate(constelementtypex)const;error_codeinsert(constinti,constelementt

4、ypex);error_codedelete_element(constinti);private:……//定义其它成员};运算：(1)初始化：(2)求长度：(3)按序号取元素：(4)按值查找元素：(5)插入：(6)删除：??????52.2顺序表2.2.1存储结构：讨论：假设有一个足够大的存储空间（数组）data,用于存储线性表的元素。则将线性表中的元素依次存储到数组中----顺序存储方式，由此得到顺序表。如下图所示：其中，设置一个计数变量count，以记录表中的元素个数。将数组data和count作为类list的数据成员。…a1a2an…01n-1

5、maxlen-1datancount顺序表存储结构62.2顺序表由此得到类list如下：classlist{public:list();intlength()const;error_codeget_element(constinti,elementtype&x)const;intlocate(constelementtypex)const;error_codeinsert(constinti,constelementtypex);error_codedelete_element(constinti);private:elementtypedata[ma

6、xlen];intcount;};list72.2顺序表2.2.2顺序表的运算实现：初始化：list::list(){count=0;}求长度：intlist::length()const{returncount;}按序号取元素：error_codelist::get_element(constinti,elementtype&x)const{if(i<=0i>count)returnrangeerror;x=data[i–1];returnsuccess;}82.2顺序表按值查找元素：intlist::locate(constelementtypex

7、)const{for(i=0;i

8、noverflow;if(i<1i>length()+1)returnrangeerror;f