数据结构(c语言版)课件_第二章_线性表_(严蔚敏、吴伟民编_清华大学出版社)

第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列niaaaa,,,,21如例英文字母表（A,B,C,…..Z)是一个线性表例学号姓名年龄001张三18002李四19………………数据元素特征：元素个数n—表长度，n=0空表1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继元素同构，且不能出现缺项2.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1typedefintDATATYPE;#defineM1000DATATYPEdata[M];例typedefstructcard{intnum;charname[20];charauthor[10];charpublisher[30];floatprice;}DATATYPE;DATATYPElibrary[M];备用空间数据元素不是简单类型时,可定义结构体数组或动态申请和释放内存DATATYPE*pData=(DATATYPE*)malloc(M*sizeof(DATATYPE));free(pData);插入定义：线性表的插入是指在第I（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表niiaaaaa,,,,1,21变成长度为n+1的线性表niiaaxaaa,,,,,1,21需将第i至第n共（n-i+1)个元素后移算法Ch2_1.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：11)1(niiinPEisnOnTninnEisnPnii112)1(1111则若认为删除定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表niiaaaaa,,,,1,21变成长度为n-1的线性表niiaaaaa,,,,11,21需将第i+1至第n共（n-i)个元素前移算法Ch2_2.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：niideinQE1)(nOnTninnEnQnidei121)(11则若认为故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针实现typedefstructnode{datatypedata;structnode*link;}JD;JD*h,*p;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域生成一个JD型新结点：p=(JD*)malloc(sizeof(JD));系统回收p结点：free(p)线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^单链表的基本运算查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL算法描述While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为nnOnTpabxs算法评价插入：在线性表两个数据元素a和b间插入x，已知p指向as-link=p-link;p-link=s;1OnT算法描述算法评价算法描述pabc1OnT算法评价删除：单链表中删除b，设p指向ap-link=p-link-link;nOnT动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法描述算法评价h头结点an^0h头结点an-10an^a2…...h头结点an-10an^ha1a2头结点an^…...0Ch2_3.ch头结点0^单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-link=NULL循环链表p或p-link=Hhh空表双向链表（doublelinkedlist）单链表具有单向性的缺点结点定义typedefstructnode{datatypeelement;structnode*prior,*next;}JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp-prior-next=p=p-next-proir;bcaPvoiddel_dulist(JD*p){p-prior-next=p-next;p-next-prior=p-prior;free(p);}删除算法描述算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;voidins_dulist(JD*p,intx){JD*s;s=(JD*)malloc(sizeof(JD));s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;}算法描述算法评价：T(n)=O(1)xSbaP插入2.4线性表的应用举例一元多项式的表示及相加一元多项式的表示：nnnxPxPxPPxP2210)(),,,,(210nPPPPP可用线性表P表示200001000231)(xxxS但对S(x)这样的多项式浪费空间一般emmnxPxPxPxPee2121)(其中为非零系数）（iPemee210用数据域含两个数据项的线性表表示emPePePm，，，，，2121其存储结构可以用顺序存储结构，也可以用单链表单链表的结点定义typedefstructnode{intcoef,exp;structnode*next;}JD;coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A703198517^-1B81227-98^-1C70111227517^一元多项式相加设p,q分别指向A,B中某一结点，p,q初值是第一结点比较p-exp与q-expp-expq-exp:p结点是和多项式中的一项p后移,q不动p-expq-exp:q结点是和多项式中的一项将q插在p之前,q后移,p不动p-exp=q-exp:系数相加0：从A表中删去p,释放p,q，p,q后移0：修改p系数域,释放q，p,q后移直到p或q为NULL若q==NULL，结束若p==NULL，将B中剩余部分连到A上即可运算规则q-1pa703198517^-1pb81227-98^ppreq-1pa703198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppreq=NULL-1pa7011198517^-1pb81227-98^ppre-1pa70111227517^Ch2_7.c算法描述