数据结构-线性表顺序存储


学了这么久,也该写点笔记了:)

定义

由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;//空表长度为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]);//q为插入位置
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 ;//i不合法
p=&(L.elem[i-1]);//p为被删元素的位置
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)