学了这么久,也该写点笔记了:)
定义
由n(n>=0)个数据特性相同的元素构成的有限序列称为线性表,(n=0)的时候称为空表。
一个数据元素可以是简单的一个数据,一个符号,也可以是复杂的若干个数据项的组合
顺序表
线性表的顺序存储结构又被称为顺序表。
顺序存储表示:用一组地址连续的存储单元一次存储线性表的数据元素的方式,具有顺序存储的特点(数据间的逻辑关系和物理关系是一致的)
实例
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <stdio.h> #include <stdlib.h>
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10
typedef struct { ElemType * elem; int length; int listsize } SqList;
Statys InitList_Sq(Sqlist& L) { L.elem=(ElemType*)malloc(List_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsieze=LIST_INIT_SIZE; return ok; }
ListInsert_Sq(SqList &L,int i,ElemType e) { if(i<1||i>L.ength+1) return ERROER;
if(L.length>=L.listsize){ newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase)exit(PVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for(p=&(L.elem[L.length-1];p>=q;--p) *(p+1)=*p; *q=e; L.length++; return ok; }
ListDelete_Sq(SqList &L,int i,ElemType &e) { if(i<1||i>L.ength) return ERROR ; p=&(L.elem[i-1]); e=*p;被删元素的值赋给e; q=L.elem+L.length-1; for(++p;p<=q;++p) *(p-1)=*p;
L.length--;
}
|
复杂度分析
线性表的顺序操作,分析其插入操作,显然,每次操作都会把后面的n-i+1
个元素进行位移,
从数字直觉来看,时间复杂度期望是n/2;
几何直觉上来看,是个三角形,平均下来也确实是n/2;
删除操作是(n-1)/2
别问,这就是直觉!
总的来说,时间复杂度就是O(n)
p u b l i c
2024/11/03 10:00:25
L I C E N S E