顺序表的查找、插入、删除

顺序表的查找、插入、删除

查找、插入与删除

按值查找：在顺序表中从头查找结点值等于给定值x的结点

int Find（seqlist&L，datatype x）
{for（i=0;i<L.n;i++){if(L.data[i]==x)return i;}return -1;
}

查找算法性能分析
查找概率相等：p=1/n；
ACN=（1+2+3+…+n）/n=(1+n)/2;
查找不成功：数据比较n次。
插入新元素

bool insert(seqlist&L,datatype x,int i)
{if(L.n==L.maxsize)return false;if(i<1||i>=L.n)return false;int j;for(j=L.n-1;j>=i-1;j--){L.data[j+1]=L.data[j];}L.data[i-1]=x;L.n++;return true;
}

插入时平均移动元素个数AMN=（n+n-1+…+1)/(n+1）=n/2;

删除表元素

bool remove(seqlist&L,int i,datatype&x)
{//删除第i个元素并返回值 int j;if(L.n>0&&i>0&&i<=L.n){x=L.data[i-1];for(j=i-1;j<L.n;j++){L.data[j]=L.data[j+1];}L.n--;return true;}elsereturn false;
}

删除时平均移动元素个数AMN=（n-1+n-2+…+1)/n=(n-1)/2