前面顺序表的补充（复杂度，未实现的算法，空间扩展）（基于c语言）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了前面顺序表的补充（复杂度，未实现的算法，空间扩展）（基于c语言），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2059字，纯文字阅读大概需要3分钟。

内容图文

0.对于顺序表中的n个元素，如果在下标i的位置之前插入一个元素，则需要将后面n-i个元素向后移动一位；如果是删除下标为i处的元素，则是则需要将后面n-i-1个元素向前移动一位。如果说在i的位置插入和删除的概率为p1i，p2i，插入平均移动数：Σ（n-i）p1i；删除平均移动数：Σ（n-i-1）p2i；然后又假设每一点删除和插入的概率相同，则p1i = 1/（n+1），p2i = 1/n。（一开始看到书上这么写我还在想为什么是n+1不是n，然后又看了看插入的实现，发现是插入的下标是从0到n变化的，当为n的时候就是在末尾加上一个数。所以是n+1）然后求和得到时间代价都是O（n）级别。也就是说顺序表对于处理经常要插入和删除的数据会比较吃力，这也是为后面引出链表做铺垫，历史的车轮总是向前的嘛。

1.顺序表的扩展：在前面实现插入的方法时，我们会判断palist->n >= palist->MAXNUM；就是判断里面的数据有没有超过我们规定的数据数量。在那个程序中，我们会打印出OVERFLOW，然后退出。那我们又有一种扩展的方法，从而容纳更多的数据。

//原先代码
print("OVERFLOW!!!");
return 0;

//更改为
pos = (DataType *)malloc(sizeof(DataType)*2*MAXNUM);
if (pos == NULL){
    printf("OVERFLOW!!!");
    return 0;    
}
for (int q=0; q<palist->MAXNUM; q++){
    pos[q] = palist->element[q];
}//将已经满了的数据装进新申请的空间
free(palist->element)//释放palist->element申请的内存
palist->element = pos//将指向顺序表的指针指向新建的内存区域
return 1;

2.另一个插入方法int insertPost_seq(PSeqList palist,int p,DataType x){}

　　在palist所指的顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。

int insertPost_seq(PSeqList palist,int p,DataType x){
    if (palist->n >= palist->MAXNUM){
        printf("OVERFLOW!!");
        return 0;  
    }  //插入的两个退出条件
    if (p<0 || p>n){
        printf("WRONGNUM");
        return 0;
    }
    for (int q=palist->n-1;q>p;q--){
        palist->element[q+1] = palist->element[q];
    }
    palist->element[p+1] = x;
    palist->n = palist->n + 1;
    return 1;
}

3.另一种删除方式，前面的已经将根据下标删除给出，这一个是给出值删除顺序表中对应的值（只删除第一个遇到的相同的）。利用前面的定位方法。

int deleteV_seq(PSeqList palist,DataType x){
    int q = locate_seq(palist,x);
    if(q == -1){
        printf("NOTFIND");
        return 0;
    }
    delete_seq(palist,q);
　　 return 1;
}

-1:顺序表到此为止，后续会给出老师布置的顺序表的作业以及相应代码。

内容总结

以上是互联网集市为您收集整理的前面顺序表的补充（复杂度，未实现的算法，空间扩展）（基于c语言）全部内容，希望文章能够帮你解决前面顺序表的补充（复杂度，未实现的算法，空间扩展）（基于c语言）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---