由 n (n≥0) 个数据元素 (a1, a2, ..., an) 构成的有限序列。记作:L = (a1, a2, ..., an) 。a1——首元素,an——尾元素。
表的长度(表长)——线性表中数据元素的数目。
空表——不含数据元素的线性表(表长为0)。
对于L = (a1, a2, ...,ai-1, ai ,ai+1, ..., an)
ADT List
{ 数据对象:D = { ai | ai∈ElemSet,i = 1, 2, ..., n, n>=0 }
数据关系:R1 = { <ai-1, ai > | ai-1, ai∈D, i = 1, 2, ..., n }
基本操作:
......
} ADT List
说明:
顺序分配: (a1, a2, ..., an) 顺序存储结构的一般形式
b 表示表的首/基地址
p 表示1个数据元素所占存储单元的数目
例1:分别定义元素所占空间、表长、尾元素的位置
#define maxleng 100 { ElemType la[maxleng+1]; int length; //当前长度 int last; //an的位置 }
例2:元素所占空间和表长合并为C语言的一个结构类型:
#define maxleng 100 typedef struct { ElemType elem[maxleng]; int length; //表长 } Sqlist; Sqlist La;
其中:typedef——别名定义,Sqlist——结构类型名,La——结构类型变量名,La.length——表长,La.elem[0]——a1,La[La.length-1]——an
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 100 typedef struct { ElemType *elem; //存储空间基地址 int length; int listsize; //当前分配的存储容量 以 sizeof(ElemType)为单位 } Sqlist; Sqlist Lb;
假设:线性表的首地址为 b,每个数据元素占 p 个存储单元,则表中任意元素 (1<=i<=n)的存储地址是:LOC(i) = LOC(1) + (i - 1) * p = b + (i - 1) * p,(1<=i<=n)
在线性表L = (a1, a2, ...,ai-1, ai ,ai+1, ..., an)中的第 i 个元素前插入元素 x
移动元素下标范围:i - 1 ~ n - 1 或 i - 1 ~ L.length - 1
Status Insert(Sqlist *L, int i, ElemType e) { if(i<1||i>L.length+1) return ERROR; //i值不合法 if(L.length>=maxleng) return OVERLOW; //溢出 for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; //向后移动元素 L.elem[i-1]=e; //插入新元素 L.length++; // 长度变量增1 return OK; }
基本思想:
int Insert(Sqlist &L, int i, ElemType e) { int j; if(i<1||i>L.length+1) return ERROR; //i的合法取值为1至n+1 if(L.length>=L.listsize) //溢出时扩充 { ElemType *newbase; newbase=(ElemType *)realloc(L.elem, L.listsize+LISTINCREMENT*sizeof(ElemType)); if(newbase==NULL) return OVERFLOW; L.elem=newbase; L.length+=LISTINCREMENT; } //向后移动元素,空出第i个元素的分量elem[i-1] for(j=L.length-1;j>=i-1;j--) L.elem[j+1]=L.elem[j]; L.elem[i-1]=e; //新元素插入 L.length++; //线性表长度加1 return OK; }
在 (a1, a2, ...,ai-1, ai ,ai+1, ..., an) 中 ai 之前插入新元素 e (1<=i<=n)
当插入点为 | 1 | 2 | ... | i | ... | n | n+1 |
需移动元素个数 | n | n-1 | ... | n-i+1 | ... | 1 | 0 |
假定 Pi 是在各位置插入元素的概率,且 P1 = P2 = ... = Pn = Pn+1 = 1/(n+1)
则插入一个元素时移动元素的平均值是:
int delete(Sqlist *L, int i) { if(i<1||L->length) { printf("not exits"); return ERROR; } else for(j=i;j<=L->length-1;j++) L->elem[j-1]=L->elem[j]; L->length--; return OK; }
基本思想:
被删除元素位置 | i=1 | 2 | ... | i | ... | n |
需要移动元素个数 | n-1 | n-2 | ... | n-i | ... | 0 |
假定 qi 是在各位置插入元素的概率,且 q1 = q2 = ... = qn = qn+1 = 1/n
则删除一个元素时移动的平均值是:
原文:https://www.cnblogs.com/tronysh/p/11694266.html