顺序表的基本操作:插入元素、删除元素和按值查找(顺序查找)[C语言实现]
我们在这里仅给出顺序表的插入操作、删除操作和按值查找的算法,其他基本操作的算法相对都比较简单,请读者自行思考。
注意:区别顺序表的位序和数组下标。理解为什么判断插入位置是否合法时if语句中用 length+1,而移动元素的for语句中只用length?
最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为O(1)。
最坏情况:在表头插入(即i=1),元素后移语句将执行n次,时间复杂度为O(n)。
平均情况:假设pi(pi=1/(n+1))是在第i个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为:
因此,线性表插入算法的平均时间复杂度为O(n)。
最好情况:删除表尾元素(即i=n),无须移动元素,时间复杂度为O(1)。
最坏情况:删除表头元素(即i=1),需要移动除第一个元素外的所有元素,时间复杂度为O(n)。
平均情况:假设Pi(Pi=1/n)是删除第i个位置上结点的概率,则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为:
因此,线性表删除算法的平均时间复杂度为O(n)。
如图2-2所示为一个顺序表在进行插入和删除操作的前、后状态,其数据元素在存储空间中的位置变化以及表长的变化。在图2-2 (a)中,元素移动是从后往前依次后移一个元素,在图2-2b中,元素移动是从前往后依次前移一个元素。
图2-2 顺序表的插入和删除
最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为O(1)。
最坏情况:查找的元素在表尾(或不存在时),需要比较n次,时间复杂度为O(n)。
平均情况:假设pi(pi=1/n)是查找的元素在第i个位置上的概率,则在长度为n的线性表中查找值为e的元素所需比较的平均次数为:
因此,线性表按值查找算法的平均时间复杂度为O(n)。
1) 插入操作
在顺序表L的第i (1<=L.length+1)个位置插入新元素e。如果i的输入不合法,则返回false,表示插入失败;否则,将顺序表的第i个元素以及其后的元素右移一个位置,腾出一个空位置插入新元素e,顺序表长度增加1,插入成功,返回true。bool ListInsert(SqList &L, int i, ElemType e){ //本算法实现将元素e插入到顺序表L中第i个位置 if ( i<1 || i>L.length+1 ) return false; // 判断i的范围是否有效 if(L.length>=MaxSize) return false; // 当前存储空间已满,不能插入 for (int j =L.length; j >=i; j--) // 将第i个位置及之后的元素后移 L.data[j]=L.data[j-l]; L.data[i-1]=e; //在位置i处放入e L.length++; //线性表长度加1 return true; }
注意:区别顺序表的位序和数组下标。理解为什么判断插入位置是否合法时if语句中用 length+1,而移动元素的for语句中只用length?
最好情况:在表尾插入(即i=n+1),元素后移语句将不执行,时间复杂度为O(1)。
最坏情况:在表头插入(即i=1),元素后移语句将执行n次,时间复杂度为O(n)。
平均情况:假设pi(pi=1/(n+1))是在第i个位置上插入一个结点的概率,则在长度为n的线性表中插入一个结点时所需移动结点的平均次数为:
因此,线性表插入算法的平均时间复杂度为O(n)。
2) 删除操作
删除顺序表L中第i (1<=i<=L.length)个位置的元素,成功则返回true,否则返回false,并将被删除的元素用引用变量e返回。bool ListDelete(SqList &L,int i, int &e){ //本算法实现删除顺序表L中第i个位置的元素 if(i<1 || i>L.length) return false; // 判断i的范围是否有效 e=L.data[i-1] ; // 将被删除的元素赋值给e for (int j=i; j<L.length; j++) //将第i个位置之后的元素前移 L.data[j-1]=L.data[j]; L.length--; //线性表长度减1 return true; }
最好情况:删除表尾元素(即i=n),无须移动元素,时间复杂度为O(1)。
最坏情况:删除表头元素(即i=1),需要移动除第一个元素外的所有元素,时间复杂度为O(n)。
平均情况:假设Pi(Pi=1/n)是删除第i个位置上结点的概率,则在长度为n的线性表中删除一个结点时所需移动结点的平均次数为:
因此,线性表删除算法的平均时间复杂度为O(n)。
如图2-2所示为一个顺序表在进行插入和删除操作的前、后状态,其数据元素在存储空间中的位置变化以及表长的变化。在图2-2 (a)中,元素移动是从后往前依次后移一个元素,在图2-2b中,元素移动是从前往后依次前移一个元素。
图2-2 顺序表的插入和删除
3) 按值查找(顺序查找)
在顺序表L中查找第一个元素值等于e的元素,并返回其下标。int LocateElem(SqList L, ElemType e){ //本算法实现查找顺序表中值为e的元素,如果查找成功,返回元素位序,否则返回0 int i; for(i=0;i<L.length;i++) if(L.data[i]==e) return i+1; // 下标为i的元素值等于e,返回其位号i+1 return 0; //退出循环,说明查找失败 }
最好情况:查找的元素就在表头,仅需比较一次,时间复杂度为O(1)。
最坏情况:查找的元素在表尾(或不存在时),需要比较n次,时间复杂度为O(n)。
平均情况:假设pi(pi=1/n)是查找的元素在第i个位置上的概率,则在长度为n的线性表中查找值为e的元素所需比较的平均次数为:
因此,线性表按值查找算法的平均时间复杂度为O(n)。