长度为n的顺序表L删除线性表中值为X的算法

  • 2019-06-29 13:38:52
  • 998 次阅读
  • 稿源:天马行空

长度为n的顺序表L,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为X的数据元素。

要求时间复杂度为O(n),这里隐藏着条件,排序算法不能使用,因为排序中最低时间复杂度为O(nlogn),这是大于题目中所给的要求为O(n)的条件。因此,我们要把排序算法排除在外,转而采用其它的方法。

(1)删除顺序表中值为X的算法一:

下面,博主画了一个线性表,用其举例。在线性表中有2值为X的字母。其实对于线性表来说就是个数组。

长度为n的顺序表L删除线性表中值为X的算法

题目中所给的长度为n的顺序表L,按照书上关于顺序表的定义,L.data就是数据的部分,L.length就是数组的长度,这两部分是一个结构体,共同构成了题目中的顺序表L。

现在,我们要在顺序表中删除值为X的元素,既然说为O(n)。可以采用遍历的方法。从数组头到尾一次遍历,并且设置两个变量分别为i和k。i表示实际的元素,其把所有的元素都能遍历到的;而k表示要留下的元素。
下面,就看看具体的代码实现。

void del_x_l(Sqlist &L,Elemtype x) {
	int k = 0; // 记录值不等于x的元素的个数,就是要留下的元素。
	for (i=0;i<L.length;i++)
		if(L.data[i] !=x) {
			L.data[k] = L.data[i]; // 下标对的元素值不等于x值就留下
			k++;// 不等于x的元素自增1
		}
		L.length = k;//顺序表长度L等于k
}

从代码中可以看出,经过前两轮的循环后,3和1都留已经留在的数组中。那么,接下来到了第三个位置k=2;i=2。可以发现X不满足if语句,就不会进入循环体中。因此,第三次的for循环,只会执行i++;而k不动,留在原先位置。至于i来到3位置,自然X元素就没有存入,相当于把X删掉了。

接下来i=3,k=2;发现第4个位置的元素不等于X,就可以进入到for循环中。这时data[2]=data[3],进而把原先k空下来的位置填补上2元素。在遍历的过程中k<=i,因为k是最终留下的元素个数,i是要遍历整个数组的元素。若数组中没有X,k和i会同步自增1,这时k=i.若数组中有X,k<i;因此,按照这样的流程遍历完,就会把值为X的元素删除,从做到让这些不等于X的元素往前紧凑填充。

最后让L.length=k。循序表的长度也就为k了。

最终删除x后的效果图:

Order table L with n length sitop algorithm with an x value in the linear table 02

(2)删除顺序表中值为X的算法二:

对于一个data!=x的元素而言,它需要前移的位数取决于在它之前有多少为满足data==x。

譬如,对于图中的数组而言,若删除第一个x,后面的2与3分别向左移动一位,若删除第二个X时,4要向左移动2位,相当前面删除了两个X。

因此,对于一个不等于X的元素向左移动多少为,取决于其左面有多少个要删除的X。假设用k记录X的个数,用i遍历第i位要留下的元素。留下的元素本来在第i位,删除X后,向左移动data[i-k]=data[i]位置,就是把留下的元素左移k位。

具体代码如下:

void del_x_2(Sqlist &L,Elemtype x) {
	int k = 0,i =0;  // k记录值等于x的元素。
	wihle (i<L.length)
		{
		if(L.data[i] ==x) 
			k++;
			else
			L.data[i-k] = L.data[i]; // 当前元素前移k个位置
			i++;
		}
		L.length -= k;//顺序表长度L递减
}
喜欢 0

文章评论 (0)

表情

大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头