第2章 线性表new.ppt

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

1、*翟音数据结构*近4周上课内容第2章线性表第3章栈和队列第4章字符串线性结构若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（a1,a2,……,an）线性结构的定义：（逻辑、存储和运算）*线性结构的特点：①只有一个首结点和尾结点；②除首尾结点外，其他结点只有一个直接前驱和一个直接后继。线性结构表达式：（a1,a2,……,an）线性结构包括线性表、堆栈、队列、字符串、数组、广义表等等，其中，最典型、最常用的是线性表简言之，线性结构反映结点间的逻辑关系是一对一的*第2章

2、线性表1.了解线性结构的特点2.掌握顺序表的定义、查找、插入和删除3.掌握链表的定义、查找、插入和删除4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合教学目标*2.1线性表的概念(ADT)2.2线性表的顺序表示和实现(顺序表)2.3线性表的链式表示和实现(链表)2.4线性表实现方法的比较教学内容*（a0,a1,…ai-1，ai,ai＋1，…,an-1）线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点

3、2.1线性表的概念2.1.1线性表的抽象数据类型*例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级041810205于春梅女1804级计算机1班041810260何仕鹏男2004级计算机2班041810284王爽女1904级计算机3班041810360王亚武男1804级计算机4班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性*templateclasslist{//线性表类模板list，模板参数Tvoi

4、dClear();//置空线性表boolisEmpty();//线性表为空时，返回trueboolappend(constTvalue);//尾附函数，在表尾加新元素value，表长加1boolinsert(constintp,constTvalue);//插入函数，在位置p上插入元素value，表长加1booldelete(constintp);//删除函数，删去位置p上的元素，表长减1boolgetValue(constintp,T&value);//读取，返回位置p的元素值到变量value中boolsetValue(…)//用val

5、ue修改位置p的元素值boolgetPos(…)//把值为value的元素位置返回到变量p中}；线性表的抽象数据类型的定义模板是C++的软件复用的功能之一，此处定义的是模板类T通常是代表要处理的数据元素的类型2.1.2线性表的存储结构*●线性表的存储结构主要有两类：（1）顺序表——定长存储结构（数组）（2）链表——变长存储结构（指针）*2.1.3线性表运算分类（1）创建线性表的一个实例。（2）线性表的析构函数~list()，消除线性表实例并释放所占空间。（3）获取有关当前线性表的信息，包括由内容寻找位置、由位置读取元素内容等，不改变线性表

6、的内容。（4）访问线性表并改变线性表的内容或结构；例如更新制定元素内容、添加元素、删除元素、清空线性表等。（5）辅助管理操作，例如求表的当前长度等。*线性表的顺序表示又称为顺序存储结构或顺序映像。简言之，逻辑上相邻，物理上也相邻顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组a[n]来实现。顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。2.2线性表的顺序表示和实现（顺序表）2.2.1顺序表的类定义*元素n-1……..元素i……..元素1元素0LoLo+mLo+i*mLo+（n-1)*m存

7、储地址存储内容Loc(元素i)=Lo+i*m顺序存储*TempateClassarrList：publicList{private:T*aList;//T类型的指针，存储线性表实例intmaxSize;//实例的最大长度intcurLen;//实例的当前长度intposition;//当前处理位置public:arrList(constintsize){maxSize=size;aList=newT[maxSize];curLen=position=0;}~arrList(){delete[]aList;}boolA

8、ppend(constTvalue){aList[position]=value;position++;curLen++;}};顺序表的类定义*2.2.2顺序表的运算实现查找-又称为检索（根据