资源描述：
《严蔚敏数据结构课件02：线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加2.1线性表的类型定义线性结构的特点：在数据元素的非空有限集中，1）有且仅有一个开始结点；2）有且仅有一个终端结点；3）除第一个结点外，集合中的每个数据元素均有且只有一个前驱；4）除最后一个结点外，集合中的每个数据元素均有且只有一个后继。线性序列：线性结构中的所有结点按其关系可以排成一个序列，记为(a1,…,ai,ai+1,…an)2.1线性表的类型定义1.线性表1）线性表是n(n≥0)个数据元素的有限序列。2）线性表是一种最常用且最简单的
2、数据结构。含有n个数据元素的线性表是一个数据结构：List=(D,R)其中：D={ai
3、ai∈D0,i=1,2,…n,n≥0}R={N},N={
4、ai-1,ai∈D0,i=2,3,…n}D0为某个数据对象——数据的子集特性：均匀性，有序性（线性序列关系）2.1线性表的类型定义1.线性表3）线性表的长度及空表线性表中数据元素的个数n（n≥0）定义为线性表的长度当线性表的长度为0时，称为空表。ai是第i个数据元素，称i为ai在线性表中的位序。2.线性表的基本操作p19~p201）InitList(&L)初始化，构造一个空的线性表2）ListL
5、ength(L)求长度,返回线性表中数据元素个数3）GetElem(L,i,&e)取表L中第i个数据元素赋值给e4）LocateElem(L,e)按值查找，若表中存在一个或多个值为e的结点，返回第一个找到的数据元素的位序，否则返回一个特殊值。5）ListInsert(&L,i,e)在L中第i个位置前插入新的数据元素e，表长加1。6）ListDelete(&L,i,&e)删除表中第i个数据元素，e返回其值，表长减1。线性表的基本操作举例例2-1求A=A∪BP20算法2.1时间复杂度：LocateElem()执行次数O(ListLength(A)*ListLe
6、ngth(B))（分析回答为什么是lb_ben*la-ben）例2-2合并LA和LB到LC中P20-21算法2.2时间复杂度：ListInsert()执行次数O(ListLength(LA)+ListLength(LB))分析回答2.2线性表的顺序表示和实现1.顺序表—线性表的顺序存储结构1）在计算机内存中用一组地址连续的存储单元依次存 储线性表中的各个数据元素。2）假设线性表的每个元素需占用L个存储单元，并以所占的第一个单元的存储地址作为数据元素的起始存储位置，则线性表中第i+1个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai
7、)之间满足下列关系：Loc(ai+1)=Loc(ai)+L一般来说，线性表的第i个元素ai的存储位置为：Loc(ai)=Loc(a1)+(i-1)*L其中Loc(a1)是线性表的第一个数据元素a1的存储位置，通常称作线性表的起始位置或基地址。1.顺序表—线性表的顺序存储结构3）线性表的顺序存储结构示意图——p22图2.2用“物理位置”相邻来表示线性表中数据元素之间的逻辑关系。根据线性表的顺序存储结构的特点，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以，线性表的顺序存储结构是一种随机存取的存储结构。结构体结构体结构体是一种构造数据类
8、型用途：把不同类型的数据组合成一个整体-------自定义数据类型结构体类型定义struct[结构体名]{类型标识符成员名；类型标识符成员名；…………….}；成员类型可以是基本型或构造型struct是关键字,不能省略合法标识符可省:无名结构体例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};namenumsexagescoreaddr2字节2字节20字节1字节4字节30字节……..结构体类型定义描述结构的组织形式,不分配内存结构体类型定义的作用域例stru
9、ctstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};structstudentstu1,stu2;9.2结构体变量的定义先定义结构体类型，再定义结构体变量一般形式：struct结构体名{类型标识符成员名；类型标识符成员名；…………….}；struct结构体名变量名表列；例#defineSTUDENTstructstudentSTUDENT{intnum;charname[20];charsex;intage;floatscore;charaddr[30];};STUD
10、ENTstu1,stu2;定义结构体类型的同时定义结构体变量一般形
