资源描述：
《自考数据结构导论--02142第二章-线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章 线性表1第2章线性表2.1线性表的基本概念2.2线性表的顺序存储2.3线性表的链接存储2.4其它运算在单链表上的实现2.5其它链表2.6顺序实现与连接实现的比较2.7小结23本章总述本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现；另外，简单介绍了串这种特殊的线性表的运算和存储实现。线性表是一种最简单最常见的数据结构4本章重点线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。本章难点单链表上的算法设计。5字母表(A,B,C,D….Z)数字表(0,1,2,3,4,5,6,7,8,9)1001张三
2、08信管1班1985.1.12008.9.1xxxxxxxxx1002李四08信管1班1986.2.12008.9.1xxxxxxxxx1003王五08信管1班1986.3.12008.9.1xxxxxxxxx学生名单6问题：线性结构的特点？72.1线性表的基本概念线性表是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。①数据元素的个数n定义为表的长度,n=0时称为空表，记作（）或 ②将非空的线性表（n＞0）记作：L=（a1，a2，…，an） ③数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以
3、不同。8线性表的基本术语：起始结点、终端结点、直接前驱、直接后继线性表长度，空表L=（a1，a2，…，an）注意：线性表中只有一个起始结点，一个终端结点，起始结点没有直接前驱，有一个直接后继。终端结点有一个直接前驱，没有直接后继。除此二结点外，每个结点都有且只有一个直接前驱和一个直接后继。9线性表的逻辑结构特征对于非空的线性表: ①有且仅有一个起始结点a1，没有直接前驱，有且仅有一个直接后继a2；②有且仅有一个终端结点an，没有直接后继，有且仅有一个直接前驱an-1；③其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前驱ai-
4、1和一个直接后继ai+1。10线性表的基本运算1，初始化Initiate(L)2，求表长度Length(L)3，取表元Get(L,i)4，定位Locate(L,x)5，插入Insert(L,x,i)6，删除Delete(L,i)区分引用型和加工型操作112.2线性表的顺序实现定义顺序表是线性表的顺序存储存储结构，即以一段连续内存存放的线性表此时，内存的顺序性体现了数据间的逻辑关系线性表中相邻的结点在存储结构中仍相邻12假定有一组数据，数据间有顺序：1210578564532887111此处数据间的顺序即表示数据间的逻辑关系即线性关系
5、，这一组数据为线性表01234567891112105785645328871线性表的顺序存储结构1301234567891112105785645328871假设已知a1地址为Loc(a1)，每个数据占c个单元则计算ai地址Loc(ai)=Loc(a1)+c*(i-1)a1a2a3a4a5a6a7a8a9a1014此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表0123456789顺序存储线性表时，需要存储：存储单元大小、数据个数线性表大小：10线性表长度：7所存放数据的类型:MaxSizeLengthData
6、Type121057856453215a1a2an01length-112n内存data数组下标元素序号maxsize-1备用空间顺序表的结构体定义#definemaxsize100typedefstruct{datatypedata[maxsize];intlength;}Seqlist;SeqlistL；问题：L有什么成员？16附讲：结构体结构体是一种构造数据类型用途：把不同类型的数据组合成一个整体-------自定义数据类型引入结构体的好处：加强数据项之间的联系如学生的基本信息，包括学号、姓名、性别、年龄、班级、成绩等数据项。
7、这些数据项描述了一个学生的几个不同侧面。nonamesexageclassnograde独立的变量表示：数据项之间无关联nonamesexageclassnograde结构体变量表示：数据项为一个整体charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩171、结构体类型的定义struct结构体类型名{数据类型名1成员名1；数据类型名2成员名2；……数据类型名n成员名n；}；struct是
8、关键字,不能省略合法标识符可省:无名结构体成员类型可以是基本型或构造型以分号;结尾例1：structStudent_Info{charno[9];//学号charname[20];//姓名charsex;//性别unsignedint
