《线性表顺序表》PPT课件.ppt
1,第2章 线性表,2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现2.4 一元多项式的表示及相加,2,2.1 线性表的类型定义,线性表的概念 线性表的逻辑结构是具有相同类型的n个数据元素的有限序列:L=（D，R）其中R为D上的一个二元关系D=a1,a2,an R=|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）*L LOC(a1)通常称作线性表的起始位置或基地址。,2.2 线性表的顺序表示和实现,5,特点：（1）逻辑上相邻的数据元素在物理上也相邻；（2）是顺序存储结构、随机存取数据元素。这种存储结构只要知道元素的序号，就很容易找到第i个数据元素，且无论序号i为何值，找到第i个元素所需时间相同。,2.2 线性表的顺序表示和实现,6,表示方式：数组表示：注意：C语言中，数组下标从0开始。#define MAX 100/常量定义 datatype dataMAX;int length;,datatype为抽象数据类型，可用int,float,double,char 或结构体类型代替。如：typedef int datatype,length为顺序表当前长度,2.2 线性表的顺序表示和实现,7,a1,a2,an,0,1,n-1,1,2,n,内存,数组下标,元素序号,Max-1,#define Max 100int dataMax;int n;,例 typedef struct student int num;char name20;int age;float score;datatype;#define Max 100datatype class1Max;int n;,数据元素不是简单类型时,可定义结构体数组,8,表示方式：将length与data封装在一起，单独定义一种顺序表类型用结构体建立。,例#define MAX 1000 typedef struct int dataMAX;int length;SeqList;,如何声明变量（顺序表）L？SeqList L;L.length=2;L.data0=91;L.data1=82;,SeqList即为顺序表类型，可用该类型建立很多顺序表。,思考：如何定义学生的顺序表？,2.2 线性表的顺序表示和实现,9,#define MAX 1000 typedef struct student int num;char name20;int age;float score;stu;typedef struct List stu dataMAX;int length;SeqList;,如何定义学生的顺序表？,#define MAX 1000struct student int num;char name20;int age;float score;typedef struct List struct student dataMAX;int length;SeqList;,SeqList class;class.data0.num=9608066class.data0.age=18 class.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=91 free(S);/*释放内存*/,表中数据元素的存储空间为S-data0 S-data S-n-1,例#define MAX 1000 typedef struct int dataMAX;int length;SeqList;,2.2 线性表的顺序表示和实现,11,顺序表的操作 建立顺序表1）问题描述：建立一个线性表(a1,a2,.，an)，长度为n。2）建立过程：先输入线性表长度n的值,然后依据n值输入n个数据元素，创建出一个顺序表。,2.2 线性表的顺序表示和实现,12,3）void CreatSList(Seqlist*L)/C 创建顺序表函数 int n,k;scanf(“%d”,建立顺序表,#define MAX 1000 typedef struct int dataMAX;int n;SeqList;,swap(int*p1,int*p2)int p;p=*p1;*p1=*p2;*p2=p;,&(*L).datak,13,算法描述void PrintList(SeqList L)/C 输出顺序表函数结构体变量做函数参数 int k;if(L.n 0)printf(the List is:n);for(k=0;kL.n;k+)printf(%5d,L.datak);,输出顺序表,2.2 线性表的顺序表示和实现,14,/C 在主函数中调用顺序表建立函数和输出函数#define MAX 100typedef struct int dataMAX;int n;SeqList;void main()SeqList*L;L=(SeqList*)malloc(sizeof(SeqList);CreatSList(L);PrintList(*L);free(L);,调用主程序,2.2 线性表的顺序表示和实现,15,顺序表的操作,插入1）问题描述：有线性表(a1,a2,.，an)，长度为n，要在第i(i是序号并不是下标)个元素前（i-1与i个元素之间）插入一个新元素。2）插入过程：先将第i至第n个元素依次向后移动一个位置，然后将新元素插入在第i个位置上，线性表的长度变为n+1。,2.2 线性表的顺序表示和实现,16,x,for(j=L-n;j=i;j-)L-dataj=L-dataj-1;/后移,L-datai-1=x;,17,3）算法描述int InsertSList(SeqList*L,int i,datatype x)int j;if(L-n=MAX)/*若表满，无法插入*/printf(“Full);return 0;if(i L-n+1)/*插入位置非法*/printf(nCant insert!n);return 0;for(j=L-n;j=i;j-)L-dataj=L-dataj-1;/*后移*/L-datai-1=x;/*在i位置处插入x*/L-n+;/*表长加1*/return 1;/*插入成功，返回 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;j(*L).n;j+)(*L).dataj-1=(*L).dataj;/前移,2.2 线性表的顺序表示和实现,20,3）算法描述int DeleteSList(SeqList*L,int i)int j;if(i(*L).n)/*删除位置非法*/printf(nCant delete!n);return 0;else for(j=i;j(*L).n;j+)(*L).dataj-1=(*L).dataj;/*前移*/(*L).n-;/*表长减1*/return 1;/*删除成功，返回1*/,顺序表删除操作,2.2 线性表的顺序表示和实现,21,算法描述void Revers(SeqList*L)int i,j;i=0;/第一个元素位置 j=L-n-1；/最后元对应位置 while(idatai,L-dataj);/交换两个元素 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，则有：,运算的时间分析,删除位置=1 i-1 n,2.2 线性表的顺序表示和实现,25,从上述分析可以看出：无论是插入或删除一个元素，平均需要移动表中一半的元素，这在表长n较大时是相当可观的，因此这种存储结构仅适用于不经常进行插入和删除运算以及表中元素相对稳定的场合。,运算的时间分析,2.2 线性表的顺序表示和实现,26,顺序表的优缺点,顺序存储结构的优点1）可以随机存取表中任何一个元素；2）无须为表示表中元素间的逻辑关系而增加额外的存储空间。顺序存储结构的缺点1）插入和删除时需移动大量的元素；2）要求存放元素的存储单元连续；3）多个大小不一的线性表同时存在时会造成空间浪费；4）线性表的容量不易扩充。,2.2 线性表的顺序表示和实现,
