数据结构——顺序表-创新互联
- 顺序表类型定义
- 数组定义
- C++的动态存储分配
- C++中的参数传递
- 操作算法中补充内容
- 顺序表基本操作
- 算法1 线性表L的初始化
- 算法2 顺序表的取值
- 算法3 顺序表的查找
- 算法4 顺序表的插入(时间复杂度为O(n))
- 算法5 顺序表的删除(时间复杂度为O(n))
- 顺序存储分析
typedef char ElemType; //定义为char
typedef struct{ElemType data[];
int length;
}SqList; // 顺序表类型
数组定义// 数组静态分配
typedef struct{ElemType data[MaxSize];
int length;
}SqList; //顺序表类型
// 数组动态分配
typedef struct{ElemType *data;
int length;
}SqList; //顺序表类型
SqList L;
L.data = (ElemType*)malloc(sizeof(ElemType)*MaxSize);
内存分配函数(需要加载头文件
- malloc(m)函数,开辟m字节长度的地址空间,并返回这段空间的首地址。
- sizeof(x)运算,计算变量x的长度。
- free(p),释放指针p所指变量的存储空间,即彻底删除一个变量。
new 类型名T (初值列表)
// 功能:申请用于存放T类型对象的内存空间,并依初值列表赋初值
// 结果值:
// 成功:T类型的指针,指向新分配的内存
// 失败:0 (NULL)
delete 指针P
// 功能:释放指针p所指向的内存,p必须是new操作的返回值。
C++中的参数传递- 函数调用时传送给形参表的实参必须与形参的类型、个数、顺序一致。
- 参数传递的两种方式:传值&传地址。
// 函数结果状态代码
# define OK 1
# define ERROR 0
# define INFEASIBLE -1
# define OVERFLOW -2
// Status是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
// 销毁线性表L
void DestroyList(SqList &L){if(L.elem) delete L.elem;
}
// 清空线性表L
void ClearList(SqList &L){L.length = 0;
}
// 求线性表的长度
int GetLength(SqList L){return(L.length);
}
// 判断线性表L是否为空
int IsEmpty(SqList L){if(L.length==0) return 1;
else return 0;
}
顺序表基本操作
算法1 线性表L的初始化Status IniList Sq(sqList &L){L.elem = new ElemType[MAXSIZE]; // 分配空间
if(!L.elem) exit(OVERFLOW); // 分配失败
L.length = 0; // 空表长度为0
return OK;
算法2 顺序表的取值int GetElem(SqList L, int i, ElemType &e){if(i<1||i>L.length) return ERROR; // 判断是否合理
e = L.elem[i-1]; // i-1的单元存储着第i个数据
return OK;
算法3 顺序表的查找平均查找长度ASL(Average Search Length):为确定记录在表中的位置,需要与给定值进行比较的关键字的个数的期望值。对含有n个记录的表,查找成功时:
A
S
L
=
∑
i
=
1
n
P
i
C
i
ASL = \sum_{i=1}^{n}P_iC_i
ASL=i=1∑nPiCi
// 在L中查找与指定值e相同的数据元素的位置
int LocateElem(SqList L, ElemType e){for(i=0; i
算法4 顺序表的插入(时间复杂度为O(n))Status ListInsert_Sq(SqList &L, int i, ElemType e){if(i<1||i>L.length+1) return ERROR; // i值不合法
if(L.length == MAXSIZE) return ERROR; // 存储空间已满
for(j=L.length-1; j>=i-1; j--)
L.elem[j+1] = L.elem[j]; // 插入位置及之后的元素后移
L.elem[i-1] = e;
L.length++;
return OK;
算法5 顺序表的删除(时间复杂度为O(n))Status ListDelete_Sq(SqList &L, int i){if(i<1||i>L.length) return ERROR; // i值不合法
if(L.length == MAXSIZE) return ERROR; // 存储空间已满
for(j=i; j>=L.length-1; j++)
L.elem[j-1] = L.elem[j]; // 插入位置及之后的元素后移
L.length--;
return OK;
顺序存储分析- 查找、插入、删除算法的平均时间复杂度:O(n)
- 查找、插入、删除算法的空间复杂度:O(1),没有用辅助空间
- 优点:存储密度大(结点本身所占存储量/结点结构所占存储量);随机存取。
- 缺点:插入、删除元素时需要移动大量数据;浪费存储空间;静态存储不能自由扩充数据元素的个数。
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
文章标题:数据结构——顺序表-创新互联
标题URL:http://scyanting.com/article/djsish.html