赞
踩
描述顺序存储结构的三个属性:
实现代码:
#define MAXSIZE 20
typedef int ElemType; //ElemType类型根据实际情况而定,这里假设为int
typedef struct {
ElemType data[MAXSIZE]; //数组用来储存数据元素,最多为MAXSIZE
int length; //线性表当前长度
}SqList;
Notes:
数组长度与线性表长度的区别:数组长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的(也可以实现动态分配数组,不过会带来性能上的损耗);线性表长度是线性表中数据元素的个数,随着插入和删除操作的进行,是变化的,任意时刻线性表的长度应小于等于数组长度。
思路:
1.若插入位置不合理,抛出异常
2.若线性表长度大于等于数组长度,则抛出异常或动态增加容量
3.从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移一个位置
4.将要插入的元素填入位置i处
5.表长加1
代码如下:
//初始条件:顺序线性表L已存在,1<=i<=ListLength(L) //操作结果:在L中第i个位置前插入新的元素e,L的长度加1 int ListInsert(SqList *L, int i, int e) { int k; if (L->length == MAXSIZE) //顺序线性表已满 return 0; if (i<1 || i>L->length + 1) //当i不在范围内时 return 0; if (i <= L->length) { //若插入数据的位置不在表尾 for (k = L->length - 1; k >= i - 1; k--) //将要插入位置后的数据元素向后挪一位 L->data[k + 1] = L->data[k]; } L->data[i - 1] = e; //将新元素插入 L->length++; return 1; }
思路:
1.如果删除位置不合理,抛出异常
2.取出删除元素
3.从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置
4.表长减1
代码如下:
//初始条件:顺序线性表L已存在,1<=i<=ListLength(L) //操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 Status ListDelete(SqList *L, int i, int *e) { int k; if (L->length == 0) //线性表为空 return 0; if (i<1 || i>L->length) //删除位置不正确 return 0; *e = L->data[i - 1]; if (i < L->length) { //将删除位置后继元素前移 for (k = i; k < L->length; k++) L->data[k - 1] = L->data[k]; } L->length--; return 1; }
删除和插入的平均时间复杂度:O(n)
线性表的顺序存储结构的优缺点:
优点:无须为表示表中元素之间的逻辑关系而增加额外的存储空间;可以快速地存取表中任意位置的元素。
缺点:插入和删除需要移动大量元素;当线性表的长度变化较大时,难以确定存储空间的容量;造成存储空间的“碎片”。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。