石油大学软件技术基础 ch21线性表课件.ppt

数据结构L=(D,R),其中D={a,b,c,d},如取R={<a,b>,<b,c>,<c,d>},则在该结构中数据元素之间是1对1联系的,即为线性关系,把这种特点的数据结构称为线性数据结构。第二章线性数据结构线性结构特点:在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前驱除最后一个外,(A,B,C,…..Z)是一个线性表定义:一个线性表是具有相同类型的n个数据元素的有限序列。例数据元素学号姓名年龄001张三18002李四19………………在日常生活中,学生学籍表、职工档案表、图书馆书目表、医院病历表、库存账目表等都可称为线性表。:元素个数n为表的长度,n=0空表1<i<n时ai的直接前驱是ai-1,a1无直接前驱ai的直接后继是ai+1,an无直接后继元素同构,且不能出现缺项数据元素在表中的位置只取决于它自身的序号。(a1,a2,……,ai-1,ai,ai+1,……,an)4一、顺序表:定义:用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法:LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中:L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点:实现逻辑上相邻—物理地址相邻实现随机存取实现:表示方式:(1)数组类型表示:数组中的分量下标即为元素在线性表中的序号。这里需要声明:C语言中,数组下标从0开始。datatype为抽象数据类型,可用int,float,double,char或结构体类型代替。如:typedefintdatatype;length为顺序表当前长度二、顺序存储线性表#defineMAX100//常量定义datatypedata[MAX];intlength;6a1a2an01n-112n内存V数组下标元素序号M-1typedefintdatatype;#defineM1000datatypedata[M];intn;typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}datatype;datatypelibrary[M];intlength;备用空间数据元素不是简单类型时,可定义结构体数组首地址起始地址基地址7表示方式:(2)将length与data封装在一起,单独定义一种顺序表类型—用结构体建立例#defineMAX100typedefstruct{intdata[MAX];intlength;}SeqList;SeqListp,q;=2;[0]=91;[1]=82;=10;[0]=93;[1]=78;……SeqList即为顺序表类型,可用该类型建立很多顺序表。二、顺序存储线性表用变量方式定义两个顺序表p和q8表示方式:(2)将length与data封装在一起,单独定义一种顺序表类型—用结构体建立例#defineMAX100typedefstruct{intdata[MAX];intlength;}SeqList;二、顺序存储线性表SeqList*s;/*s为指向某个顺序表的指针*/s=(SeqList*)malloc(sizeof(SeqList));/*动态申请内存*/(*s).length=10;//顺序表的表长用(*s).length或s->length表示s->data[0]=87;s->data[9]=91;表中数据元素的存储空间为s->data[0]~s->data[s->length-1]用指针方式定义一个顺序表s:9三、顺序表的操作顺序表的建立问题描述:建立一个线性表(a1,a2,...,an),长度为n。建立过程:先输入线性表长度n的值,然后依据n值,输入n个数据元素,创建出一个顺序表。10