资源描述:
《数据结构chap2顺序表.ppt》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第二章线性表第2章线性表第3章栈和队列第4章串第5章数组和广义表线性结构若结构是非空有限集,则有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为:(a1,a2,……,an)线性结构的定义:(逻辑、存储和运算)*线性结构的特点:①只有一个首结点和尾结点;②除首尾结点外,其他结点只有一个直接前驱和一个直接后继。线性结构表达式:(a1,a2,……,an)线性结构包括线性表、堆栈、队列、字符串、数组等等,其中,最典型、最常用的是线性表简言之,线性结构反映结点间的逻辑关系是一对一的*第2章线性表
2、1.了解线性结构的特点2.掌握顺序表的定义、查找、插入和删除3.掌握链表的定义、查找、插入和删除4.能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合教学目标*2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4线性表的应用教学内容*(a1,a2,…ai-1,ai,ai+1,…,an)线性表的定义:用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标,是元素的序号,表示元素在表中的位置n为元素总个数,即表长空表线性终点2.1线性表的类型定义*例1分析
3、26个英文字母组成的字母表(A,B,C,D,……,Z)例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性*抽象数据类型线性表的定义为:ADTList{数据对象:D={ai
4、ai∈ElemSet,i=1,2,...,n,n≥0}{称n为线性表的表长;称n=0时的线性表为空表。}数据关系:R1={
5、ai-1,ai∈D,i=2,...,n}{设线性表为(a1,a2,...,ai,...,an),称i为ai在线性表中的位序。}*线性表的基本操作1
6、.初始化线性表LInitList(L)2.销毁线性表LDestoryList(L)3.清空线性表LClearList(L)4.求线性表L的长度ListLength(L)5.判断线性表L是否为空IsEmpty(L)6.获取线性表L中的某个数据元素内容GetElem(L,i,e)7.检索值为e的数据元素LocateELem(L,e)8.在线性表L中插入一个数据元素ListInsert(L,i,e)9.删除线性表L中第i个数据元素ListDelete(L,i,e)}ADTList*2.2线性表的顺序表示和实现线性表的顺序表示又称为顺序
7、存储结构或顺序映像。简言之,逻辑上相邻,物理上也相邻顺序存储方法:用一组地址连续的存储单元依次存储线性表的元素,可通过数组V[n]来实现。顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。*元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+(n-1)*m存储地址存储内容Loc(元素i)=Lo+(i-1)*m顺序存储随机存取的存储结构*顺序表的类型定义数据结构基本运算操作有:查找、插入、删除typedefstruct{}SqList;//俗称顺序表#defineLIST_INI
8、T_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量//(以sizeof(ElemType)为单位)*malloc(m):开辟m字节长度的地址空间,并返回这段空间的首地址sizeof(x):计算变量x的字节长度free(p):释放指针p所指变量的存储空间,即彻底删除一个变量补充:C语言的动态分配函数()*函数调用时传送给形参
9、表的实参必须与形参在类型、个数、顺序上保持一致参数传递有两种方式传值方式(参数为整型、实型、字符型等)传地址参数为指针变量参数为引用类型参数为数组名补充:C++中的参数传递*voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<voidswap(floatm,floatn){floattemp;temp=m;m=n;n=temp;}传值方式把实参的值传送给函数的形参中,函数使用这个形参执行必要的功能。函数修改的是形参
10、的值,实参的值不变*传地址方式--指针变量作参数voidmain(){floata,b,*p1,*p2;cin>>a>>b;p1=&a;p2=&b;swap(p1,p2);cout<v