1线性表的顺序存储结构顺序表 typedef struct ElemType elem MaxSizel; 存放顺序表元素 int length 存放顺序表的长度 3 Sqlist
1.线性表的顺序存储结构—顺序表 typedef struct { ElemType elem[MaxSize]; /*存放顺序表元素*/ int length; /*存放顺序表的长度*/ } SqList;
顺序表基本运算的实现 插入数据元素算法:元素移动的次数不仅与表 长n有关;插入一个元素时所需移动元素的平均次数 n/2。平均时间复杂度为O(n)
顺序表基本运算的实现 插入数据元素算法：元素移动的次数不仅与表 长n有关 ；插入一个元素时所需移动元素的平均次数 n／2。平均时间复杂度为O(n)
删除数据元素算法:元素移动的次数也与 表长n有关。删除一个元素时所需移动元素的 平均次数为m-1)/2。删除算法的平均时间复杂 度为O(n)
删除数据元素算法:元素移动的次数也与 表长n有关 。删除一个元素时所需移动元素的 平均次数为(n-1)/2。删除算法的平均时间复杂 度为O(n)
例2.1】设计一个算法,将x插入到一个有序 (从小到大排序)的线性表(顺序存储结构)的适当 位置上,并保持线性表的有序性
【例2.1】 设计一个算法，将x插入到一个有序 （从小到大排序）的线性表（顺序存储结构）的适当 位置上，并保持线性表的有序性
/void Insert(SqList &A, ElemType x) int i=0,j; while(i<a length & aselemi]<x)i++; for gj=Alength-1;j>=i;j-o) A.elemj1=Aelemi; Aeleni=x; Alength++
void Insert(SqList &A,ElemType x) { int i=0,j; while (i<A.length && AS.elem[i]<x) i++; for (j=A.length-1;j>=i;j--) A.elem[j+1]=A.elem[j]; A.elem[i]=x; A.length++; }