全部内容首先要定义一个数据表结构体
typedef struct{
int *data;
int maxlen;
int len;
}SqList;
int main(){
SqList L;
}
1.获得顺序表GetElem
获得元素操作
条件：1≤i≤线性表程度
#define OK 1
#define ERROR 0
typedef status int
status GetElem(SqList L,int i,ElemType *e){
if(L.length ==0 || i<1 || i>L.length){
return ERROR;
}
*e=L.data[i-1];//用e返回L中第i个元素的值
return OK;
}
2.插入操作
此处最好的状况就是直接在最后一个位置进行插入即最好的时间复杂度为O(1)因为不涉及元素的移动。
最坏的情况就是删除第一个位置或者插入第一个位置，因为后面所有元素都要进行移动所以时间复杂度为O(n)
可以看出时间复杂度还是O(n)
status insert(Sqlist &L,int i,ElemType e){ //i为位置,e为插入元素
int k;
if(L.len==maxlen) return ERROR;
if(i<1 || i>len+1) return ERROR;
if(i<=L.len){
for( k=L.len-1;k>=i-1;k--){
L.data[k+1] = L.data[k];
}
}
L.data[i-1]=e;
L.len ++;
return OK;
}
提示：
- 如果插入位置不合理抛出异常
- 线性表长度大于数组长度抛出异常 或者 动态扩容数组长度
- 从最后一个元素遍历到第i个位置把这些元素都向后移动一位，给插入点留出空位
- 把插入的元素填入i位置
- 表长+1
3.删除操作
相当于后面的元素向前移动 覆盖了前面内存空间的存储数据 自然对原数据达到了抹除的效果
void deleteElement(Sqllist &L, int i){
if(i<1 || i>L.len) return;
for(int j=i; j<L.len; j++){
L.data[j-1] = L.data[j];
}
L.len--;
}
优缺点总结
优点：
不用为表示表中元素的逻辑关系加更多的存储空间、可以快速取出表中任意位置的元素
缺点也很明显，Insert Delete操作时间平均复杂度较高，需要移动大量元素、线性表长度变化大很难确定存储空间容量、会造成储存空间的碎片
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。