22.1线性表的顺序顺序存储 ◆线性表的顺序存储是指在内存中用地址连续的一块存 储空间顺序存放线性表的各元素,用这种存储形式存储 的线性表称其为顺序表。 ◆设a1的存储地址为LoC(a1),每个数据元素占d个存储 地址,则第i个数据元素的地址为: Loc(ai=Loca)+(i-1*d lsIs ◆从结构性上考虑,通常将data和|as封装成一个结构 作为顺序表的类型: typedef struct i datatype data[MAXSIZE t last Seqlist; 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 2.2.1 线性表的顺序顺序存储 线性表的顺序存储是指在内存中用地址连续的一块存 储空间顺序存放线性表的各元素，用这种存储形式存储 的线性表称其为顺序表。 设 a１的存储地址为Loc(a１)，每个数据元素占d个存储 地址，则第i个数据元素的地址为： Loc(ai )=Loc(a１)+(i-1)*d 1≤I≤n 从结构性上考虑，通常将 data 和 last 封装成一个结构 作为顺序表的类型： typedef struct { datatype data[MAXSIZE]; int last; } SeqList;
222顺序表上基本运算的实现 1.顺序表的初始化 顶序表的初始化即构造一个空表,对表是一个加工型 的运算,因此,将L设为指针参数,首先动态分配存储空 间,然后,将表中ast指针置为-1,表示表中没有数据 元素。算法如下: SeqList * init seqlisto { Seqlist料; L=malloc( sizeof(seqList)) L->|ast=-1 return l; 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 2.2.2 顺序表上基本运算的实现 ⒈ 顺序表的初始化 顺序表的初始化即构造一个空表，对表是一个加工型 的运算，因此，将 L设为指针参数，首先动态分配存储空 间，然后，将表中 last 指针置为－1，表示表中没有数据 元素。算法如下： SeqList *init_SeqList( ) { SeqList *L; L=malloc(sizeof(SeqList)); L->last=-1; return L; }
2插入运算 4线性表的插入是指在表的第个位置上插入一个值为x的新 素,算法如下 int Insert_ SeqList(SeqList *L, int i, datatype x) i int j if (L->last== MAXSIZE-1) printi("表满") return(-1);}*表空间已满,不能插 f(i<1‖|i>L->last2)/*检查插入位置的正确性* { printf(("位置错"; return(0);} forG=L->last; j>=i-1; j-) L->datalj+1=L->datall;/ *结点移动* L->data i-1]=X; /*新元素插入* L->ast+;/*s仍指向最后元素* return(1);/*插入成功,返回* 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 8 ⒉插入运算 线性表的插入是指在表的第i个位置上插入一个值为 x 的新 元素，算法如下： int Insert_SeqList(SeqList *L，int i，datatype x) { int j; if (L->last == MAXSIZE－1) { printf(＂表满＂); return(-1); } /*表空间已满，不能插 入*/ if (i<1 || i>L->last+2) /*检查插入位置的正确性*/ { printf(＂位置错＂); return(0); } for(j=L->last; j>=i-1; j--) L->data[j+1]=L->data[j]; /* 结点移动 */ L->data[i-1]=x; /*新元素插入*/ L->last++; /*last仍指向最后元素*/ return (1); /*插入成功，返回*/ }
插入算法的时间性能分析 ◆顺序表上的插入运算,时间主要消耗在了数据的移动上, 在第价个位置上插入x,从a1到an都要向下移动一个位置, 共需要移动n-1+1个元素,而1的取值范围为:1sks n+1,即有n+1个位置可以插入。设在第个位置上作插入 的概率为P,则平均移动数据元素的次数: 设:P=1/(n+1),即为等概率情况,则: n+1 n+1 pic (n-i+1) n ◆这说明:在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为O(n) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 9 插入算法的时间性能分析 顺序表上的插入运算，时间主要消耗在了数据的移动上， 在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置， 共需要移动 n－i＋1个元素，而 i 的取值范围为 ：1≤ i≤ n+1，即有 n＋1个位置可以插入。设在第i个位置上作插入 的概率为Pi，则平均移动数据元素的次数： 设：Pi=1/ (n+1) ，即为等概率情况，则： 这说明：在顺序表上做插入操作需移动表中一半的数据 元素。显然时间复杂度为Ｏ(n)。 + = = − + 1 1 E ( 1 ) n i i n i p n i
3删除运算 线性表的删除运算是指将表中第i个元素从线性表中去掉, 算法如下: int Delete Seqlist(seqlist *L; t i cint i int ji f(<1||>L->ast1)/检查空表及删除位置的合法性考 prnt("不存在第个元素" return(O); forG=i; j<=L->last;j++) L->data-1]=L-> data;/*向上移动* L->last return (1: /*删除成功* 2021年1月21日 数据结构讲义 10
2021年1月21日 数据结构讲义 10 ⒊删除运算 线性表的删除运算是指将表中第 i 个元素从线性表中去掉， 算法如下： int Delete_SeqList(SeqList *L;int i) { int j; if(i<1 || i>L->last+1) /*检查空表及删除位置的合法性*/ { printf (＂不存在第i个元素＂); return(0); } for(j=i; j<=L->last; j++) L->data[j-1]=L->data[j]; /*向上移动*/ L->last--; return(1); /*删除成功*/ }