资源描述
1,第2章线性表,2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加,2,2.1线性表的类型定义,线性表的概念线性表的逻辑结构是具有相同类型的n个数据元素的有限序列:L=（D，R）其中R为D上的一个二元关系D=a1,a2,anR=|1in-1,aiD,有序对,ai(i=1,.，n)是属于某数据对象的元素，n为线性表的长度(n0)，n=0的表称为空表。,例英文字母表（A,B,C,.Z)是一个线性表,3,线性表的结构特点(1)所有数据元素ai在同一个线性表中必须是相同的数据类型；(2)在非空线性表中必存在唯一的一个称为“头”的元素；(3)在非空线性表中必存在唯一的一个称为“尾”的元素；(4)除“头”外，每个元素都有且只有一个前驱元素。(5)除“尾”外，每个元素都有且只有一个后继元素。,2.1线性表的类型定义,4,顺序存储结构（顺序表）用一组地址连续的存储单元依次存放线性表的数据元素，称为线性表的顺序存储结构。地址计算：设每个元素占L个单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)=LOC(ai)+L线性表的第i个数据元素ai的存储位置为LOC(ai)=LOC(a1)+（i-1）*LLOC(a1)通常称作线性表的起始位置或基地址。,2.2线性表的顺序表示和实现,5,特点：（1）逻辑上相邻的数据元素在物理上也相邻；（2）是顺序存储结构、随机存取数据元素。这种存储结构只要知道元素的序号，就很容易找到第i个数据元素，且无论序号i为何值，找到第i个元素所需时间相同。,2.2线性表的顺序表示和实现,6,表示方式：数组表示：注意：C语言中，数组下标从0开始。#defineMAX100/常量定义datatypedataMAX;intlength;,datatype为抽象数据类型，可用int,float,double,char或结构体类型代替。如：typedefintdatatype,length为顺序表当前长度,2.2线性表的顺序表示和实现,7,a1,a2,an,0,1,n-1,1,2,n,内存,数组下标,元素序号,Max-1,#defineMax100intdataMax;intn;,例typedefstructstudentintnum;charname20;intage;floatscore;datatype;#defineMax100datatypeclass1Max;intn;,数据元素不是简单类型时,可定义结构体数组,8,表示方式：将length与data封装在一起，单独定义一种顺序表类型用结构体建立。,例#defineMAX1000typedefstructintdataMAX;intlength;SeqList;,如何声明变量（顺序表）L？SeqListL;L.length=2;L.data0=91;L.data1=82;,SeqList即为顺序表类型，可用该类型建立很多顺序表。,思考：如何定义学生的顺序表？,2.2线性表的顺序表示和实现,9,#defineMAX1000typedefstructstudentintnum;charname20;intage;floatscore;stu;typedefstructListstudataMAX;intlength;SeqList;,如何定义学生的顺序表？,#defineMAX1000structstudentintnum;charname20;intage;floatscore;typedefstructListstructstudentdataMAX;intlength;SeqList;,SeqListclass;class.data0.num=9608066class.data0.age=18class.data0.score=99.5,2.2线性表的顺序表示和实现,10,表示方式：,用指针方式定义一个顺序表S：（参照C语言课本指向结构体变量的指针）SeqList*S;/*S为指向某个顺序表的指针*/S=(SeqList*)malloc(sizeof(SeqList);/*动态申请内存*/(*S).length=10;/*顺序表的表长或S-length表示*/S-data9=91;(*S).data9=91free(S);/*释放内存*/,表中数据元素的存储空间为S-data0S-dataS-n-1,例#defineMAX1000typedefstructintdataMAX;intlength;SeqList;,2.2线性表的顺序表示和实现,11,顺序表的操作建立顺序表1）问题描述：建立一个线性表(a1,a2,.，an)，长度为n。2）建立过程：先输入线性表长度n的值,然后依据n值输入n个数据元素，创建出一个顺序表。,2.2线性表的顺序表示和实现,12,3）voidCreatSList(Seqlist*L)/C创建顺序表函数intn,k;scanf(“%d”,建立顺序表,#defineMAX1000typedefstructintdataMAX;intn;SeqList;,swap(int*p1,int*p2)intp;p=*p1;*p1=*p2;*p2=p;,if(L.n0)printf(theListis:n);for(k=0;kn;j=i;j-)L-dataj=L-dataj-1;/后移,L-datai-1=x;,17,3）算法描述intInsertSList(SeqList*L,inti,datatypex)intj;if(L-n=MAX)/*若表满，无法插入*/printf(“Full);return0;if(iL-n+1)/*插入位置非法*/printf(nCantinsert!n);return0;for(j=L-n;j=i;j-)L-dataj=L-dataj-1;/*后移*/L-datai-1=x;/*在i位置处插入x*/L-n+;/*表长加1*/return1;/*插入成功，返回1*/,顺序表插入操作,18,删除1）问题描述：有线性表(a1,a2,.，an)，长度为n，要将第i个元素删除。2）删除过程：将第i+1至第n个元素依次向前移动一个位置，线性表的长度变为n-1。,2.2线性表的顺序表示和实现,19,.,a2,a1,an,.,ai+1,ai,0,1,i-1,i,n-1,将第I(序号)个元素删除,ai-1,.,a2,a1,alength,ai+1,ai,删除,for(j=i;jdataj);/交换两个元素i+;j-;,顺序表求逆（数据结构首尾倒置）,Swap(&(L-datai),&(L-dataj),2.2线性表的顺序表示和实现,22,运算的时间分析,在插入和删除运算中，时间主要消耗在移动元素上，所需移动的元素个数与线性表的长度n和被插入或删除的元素在线性表中的位置有关:在第i(i从1开始)个位置插入一新元素需移动n-i+1个元素,2.2线性表的顺序表示和实现,23,在等概率情况下，pi=1/(n+1)，则有：,运算的时间分析,我们来求平均性能。设pi是将一个元素插入在第i个位置的概率，则在长度为n的线性表中插入一个元素所需的平均移动次数为：,2.2线性表的顺序表示和实现,24,同理，删除时有：,在等概率情况下，qi=1/n，则有：,运算的时间分析,删除位置=1i-1n,2.2线性表的顺序表示和实现,25,从上述分析可以看出：无论是插入或删除一个元素，平均需要移动表中一半的元素，这在表长n较大时是相当可观的，因此这种存储结构仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。,运算的时间分析,2.2线性表的顺序表示和实现,26,顺序表的优缺点,顺序存储结构的优点1）可以随机存取表中任何一个元素；2）无须为表示表中元素间的逻辑关系而增加额外的存储空间。顺序存储结构的缺点1）插入和删除时需移动大量的元素；2）要求存放元素的存储单元连续；3）多个大小不一的线性表同时存在时会造成空间浪费；4）线性表的容量不易扩充。,2.2线性表的顺序表示和实现,
展开阅读全文