《线性表顺序表》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 100 int dataMax; int n;,例 typedef struct student int num; char name20; int age ; float score; datatype; #define Max 100 datatype 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 1000 struct student int num; char name20; int age ; float score; ; typedef struct List struct student dataMAX; int length; SeqList;,SeqList class; class.data0.num=9608066 class.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 100 typedef 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较大时是相当可观的，因此