文章

6

粉丝

0

获赞

1

访问

18090

头像
顺序表
数据结构
发布于2021年4月5日 22:02
阅读数 3926

定义

顺序表使用一组地址连续的存储单元,依次存储线性表中的数据元素,使得逻辑上相邻的两个元素在物理位置上也相邻

当做数组来思考与使用。

大致为这个样子:

线性表顺序存储描述为:

#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int lenght;
}Sqlist;

优缺点

随机访问快,因为地址连续,可通过地址直接访问。
插入删除慢,因为需要移动大量元素,所以慢。

 

顺序表的操作

只需要掌握插入、删除、查找

1.插入

 

 

bool ListInsert(SqList &L,int i,ElemType e){
	if(i<1 || i>L.length + 1)
		return false;
	if(L.length >= MaxSize)
		return false;

	for(int j = L.length;j>=i;j--){
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;
	L.length++;
	return true;
}
第一步,判断插入的位置对不对,不可小于1,因为1是最开始的位置;不可大于长度 +1,因为最后一个元素所在位置为长度最大处,但插入时可以插入到最后一个元素的后面,所以插入位置最大为长度 +1。
第二步,数组是否满了,满了就无法插入新元素了,即判断数组长度是否大于空间长度,如图,共有8个空间,判断length是否大于等于8。
第三步,后移元素,给插入的元素腾出空间。
第四步,插入元素,长度 +1。

注意点:
数组下标从0计数,插入的时候要位置 -1。
L.data[i-1] = e;
当插入位置为1,赋值时是data[0]的值被改变。

平均情况下,插入一个结点要移动 n/2 个 元素。

因此时间复杂度为O(n)

 

2.删除

 

 

bool ListDelete(SqList &L,int i,int &e){
	if(i<1 || i> L.length)
		return false;
	e = L.data[i-1];
	for(int j=i;j<L.length;j++){
		L.data[j-1] = L.data[j];
	}
	L.length --;
	return true;
}
第一步,判断位置是否越界,即是否符合要求。
第二步,取出要删除的元素。
第三步,前移元素,填充被删除元素留下的空间。
第四部,长度 -1。

平均情况下删除一个节点需要移动 (n-1)/2 个元素。

因此时间复杂度为 O(n)

3.按值查找

int LocateElem(SqList L,ElemType e){
	int i;
	for(i = 0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;
	return 0;
}
注意点:
使用for循环遍历,一个个匹配,直到找到值。
返回值时要注意,元素下标 i+1 为位置。

平均情况下查找一个节点需要比较 (n+1)/2 个元素。

因此时间复杂度为 O(n)



登录后发布评论

暂无评论,来抢沙发