资源描述：
《第二章线性表1线性表定义及顺序存储ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构2.1线性表的类型定义第二章线性表2.2线性表的顺序表示和实现2.3线性表的链式表示和实现1.线性表的定义2.1线性表的类型定义A=(a1，a2，a3，......,an)数列：(25，12，78，34，100，88)99001张华女17……99002李军男18……99003王小明男17……99050刘末女19…………学号姓名性别年龄其他…………a1a2a3··a50a1a2a3a4a5a6字母表：(‘A’，‘B’，‘C’，……,‘X’,‘Y’,‘Z’)a1a2a3……a24a25a26数据文件：一个数据元素是一个整数一个数据元素是一个英文字母一个数据元素是
2、一个数据记录1.线性表的定义(逻辑结构)线性表是由n(n≥0)个数据元素a1，a2，......,an组成的一个有限序列。表中的每一个数据元素，除了第一个外，有且仅有一个前驱；除了最后一个外，有且仅有一个后继。即线性表或是一个空表，或可以表示成(a1,a2,…,ai,...,an)其中，ai(i=1,2,…,n)是属于数据对象的元素，通常也称为线性表中的一个结点。2.1线性表的类型定义设A=（a1,a2,...,ai-1,ai,ai+1,…,an)是线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素必须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1
3、是ai的直接前趋，ai+1是ai的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号。说明二元组表示L=，其中D={a1,a2,a3,...an} S={,,…}图示表示ai+1a1ai-1a2aian顶点：表示数据边：表示是数据间的顺序
4、结构关系2.线性表的其他表示方式3.线性表的抽象数据类型19页ADTList{数据对象：所有ai属于同一数据对象数据关系：所有ai存在次序关系，a1无前驱，an无后继基本操作：初始化操作InitList(&L)销毁操作DestroyList(&L)置空操作ClearList(&L)判空操作ListEmpty(L)……遍历操作ListTraverse(L,visit())}ADTList3.线性表的抽象数据类型如：由用户创建某结构体类型Employee，它是structNode的别名。typedefstructNode{charName[20];charSex;intAge
5、;floatMoney;}Employee;假设用两个线性表La和Lb分别表示两个集合A和B(线性表中的数据元素即为集合中的成员)，求一个新的集合A=AB∩例voidunion(List&La,ListLb){//将Lb中所有La中不存在的元素插到La中La_Len=ListLength(La);//求La长度Lb_Len=ListLength(Lb);//求Lb长度for(i=1;i<=Lb_Len;i++){GetElem(Lb,i,e);//取Lb中第i个元素，并用e返回if(!LocateElem(La,e,equal))//若La中不存在和e相等的值ListInsert(La,+
6、+La_Len,e);//将其插到La最后一个元素之后}}//union20页4.线性表的存储结构连续的存储空间——静态存储（数组）不连续的存储空间——动态存储（指针）游标(连续存储空间+动态管理思想)——静态链表游标：整型，其值为数组下标，用以表示指定元素的地址。4.线性表的存储结构如：线形表L(a,b,e)和线形表M(c,d,f)，L的值为5，而M的值为3。用游标的形式来实现:Soltelementnext0-61b92f03header74-05header106-47c88d29e010a1a1a2a3……and1d2d3……dn(a1，a2，a3，......,an)用一组地址连
7、续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。1.构造原理2.2线性表的顺序表示和实现长度为n的线性表：(a1，a2，a3，......,an)在计算机中的顺序存储结构如图：用一组地址连续的存储单元依次存储线性表中的数据元素，数据元素之间的逻辑关系通过元素的存储位置直接反映。2.2线性表的顺序表示和实现①在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示
