资源描述：
《数据结构 C语言版 教学课件 作者 严蔚敏 李冬梅 吴伟民 第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、*李冬梅数据结构*北京林业大学信息学院近3周 上课 内容第2章线性表第3章栈和队列第4章串、数组和广义表线性结构若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。可表示为：（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的直接后继下标，是元素的序号，表示元素在表中
3、的位置n为元素总个数，即表长空表线性终点2.1线性表的类型定义*北京林业大学信息学院例1分析26个英文字母组成的英文表（A,B,C,D,……,Z）学号姓名性别年龄班级041810205于春梅女1804级计算机1班041810260何仕鹏男2004级计算机2班041810284王爽女1904级计算机3班041810360王亚武男1804级计算机4班：：：：：例2分析学生情况登记表数据元素都是记录;元素间关系是线性数据元素都是字母;元素间关系是线性同一线性表中的元素必定具有相同特性*北京林业大学信息学院线性表的基本操作1.初始化线性表LInitList(L
4、)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)抽象数据类型的定义为*北京林业大学信息学院2.2线性表的顺序表示和实现线性表的顺序表示又称为顺序存储结构或顺序映像。简言之，逻辑上相
5、邻，物理上也相邻顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素，可通过数组V[n]来实现。顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。*北京林业大学信息学院元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储*北京林业大学信息学院#defineMAXSIZE100//最大长度typedefstruct{ElemType*elem;//指向数据元素的基地址intlength;//线性表的当前长度}SqList；
6、顺序表的类型定义数据结构基本运算操作有：查找、插入、删除*北京林业大学信息学院malloc(m)：开辟m字节长度的地址空间，并返回这段空间的首地址sizeof(x)：计算变量x的长度free(p)：释放指针p所指变量的存储空间，即彻底删除一个变量补充：C语言的动态分配函数（）*北京林业大学信息学院new类型名T（初值列表）功能：申请用于存放T类型对象的内存空间，并依初值列表赋以初值结果值：成功：T类型的指针，指向新分配的内存失败：0（NULL）int*p1=newint;或int*p1=newint(10);delete指针P功能：
7、释放指针P所指向的内存。P必须是new操作的返回值deletep1;补充：C++的动态存储分配*北京林业大学信息学院函数调用时传送给形参表的实参必须与形参在类型、个数、顺序上保持一致参数传递有两种方式传值方式（参数为整型、实型、字符型等）传地址参数为指针变量参数为引用类型参数为数组名补充：C++中的参数传递*北京林业大学信息学院voidmain(){floata,b;cin>>a>>b;swap(a,b);cout<voidswap(floatm,floatn){floatt
8、emp;temp=m;m=n;n=temp;}传值方式把实参的值传送给函数局部工作区相应的副本
