精华内容
下载资源
问答
  • 链式存储中在第i个位置插入或删除的时间复杂度

    千次阅读 多人点赞 2016-12-05 21:12:05
    通过二者的定义不难看出,顺序存储在查找时的时间复杂度为O(1),因为它的地址是连续的,只要知道首元素的地址,根据下标可以很快找到指定位置的元素,而对与插入和删除操作由于可能要在插入前或

    计算机的数据存储(物理结构)中有两种基本的方式:顺序存储链式存储。顺序存储指的是用一段地址连续的存储单元依次存储数据;而链式存储中数据元素可以散乱的存储到存储单元中,每一个数据元素中包含数据项和下一个元素的存储地址。

    通过二者的定义不难看出,顺序存储在查找时的时间复杂度为O(1),因为它的地址是连续的,只要知道首元素的地址,根据下标可以很快找到指定位置的元素,而对与插入和删除操作由于可能要在插入前或删除后对元素进行移动,所以顺序存储的时间复杂度为O(n)。链式存储的特性则正好相反,在查找时需要从头元素逐个寻找,因此查找的时间复杂度为O(n),而对于插入和删除操作,由于只需要变更数据元素中下一元素的存储地址即可,因此时间复杂度为O(1)

    表面上看上面的说法没有什么问题,但其实在日常的使用中,比如要在数据集合的第i个位置插入或删除一个元素,要完成这样一个动作,使用顺序存储需要查找到元素然后执行插入或删除,时间复杂度为O(1)+O(n)=O(n);而链式存储同样需要先查找到元素然后在插入或删除,时间复杂度为O(n)+O(1)=O(n)

    所以说链式存储插入和删除的时间复杂度为O(1)的前提应该是已知元素当前的位置,否则实现在第i个位置插入或删除一个元素,顺序存储和链式存储的时间复杂度是一样的,都是O(n).

    展开全文
  • 对长度为n的顺序表L,编写一个时间复杂度O(n),空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素。 算法思想: 一步:从前往后扫描顺序表,用k纪录当前值为x的数据元素的个数 二步:如果扫描...

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

    算法思想:
    第一步:从前往后扫描顺序表,用k纪录当前值为x的数据元素的个数
    第二步:如果扫描的当前元素的值为x,则k++;如果扫描的当前元素的值不为x,则将此当前元素向前移动k位
    代码:

    void Del_x_k(Sqlist &L,ElemType x) {
    	int k = 0;		//用k纪录值为x的数据元素的个数
    	for (int i = 0; i < L.length; i++) {
    		if (L.data[i] == x)
    			k++;
    		else
    			L.data[i - k] = L.data[i];//当前元素前移k个位置
    	}
    	L.length = L.length - k;//顺序表的长度-k
    }
    

    结语

    如果你喜欢我写的文章,欢迎来踩我个人搭建的博客~
    ChengNing’s Blog

    展开全文
  • 首先确定顺序表L中的第一个值为x元素位置i,然后依次检查L.data[i+1]~L.data[L.length-1]中每个元素L.data[j](i+1<=j<L.length),若L.data[j]!=x,则将L.data[j]存入L.data[i]中,并令i增1。最后顺序表长度为...

    解法一:

    首先确定顺序表L中的第一个值为x的元素位置i,然后依次检查L.data[i+1]~L.data[L.length-1]中每个元素L.data[j](i+1<=j<L.length),若L.data[j]!=x,则将L.data[j]存入L.data[i]中,并令i增1。最后顺序表长度为i。算法如下:

     

    void delall(Sqlist *l,int x)
    {
    	int i=0,j;
    	while(i<l->length && l->data[i]!=x)
    		i++;
    	for(j=i+1;j<l->length;j++)
    		if(l->data[j]!=x)
    		{
    			l->data[i++]=l->data[j];
    		}
    		l->length=i;
    }
    本算法只扫描一次顺序表,即将值为x的元素前移一次,其时间复杂度为O(n)

     

     

    解法二:

    从头开始扫描顺序表L,用k记录下元素值等于x的元素个数,对于不等于x的元素,前移k个位置,这种算法复杂度为O(n),其中n为顺序表的长度,算法如下:

     

    void delall(Sqlist *l,int x)
    {
    	int i=0,j=0;
    	while(i<l->length)
    	{
    		if(l->data[i]==x)
    			j++;//j记录被删记录的个数
    		else
    			l->data[i-j]=l->data[i];//前移j个位置
    		i++;
    	}
    	l->length-=j;
    }

     

    转载于:https://www.cnblogs.com/gxt-/p/5887268.html

    展开全文
  • 思路:统计不等于x个数,边统计边把当前元素放在k位置上,最后修改表长度 public static void del(List list,int p){ int k=0; for(int i=0;i();i++){ if(list.get(i)!=p){ list.set(k, list....

    思路:统计不等于x的个数,用k记录不等于x的元素的个数。边统计边把当前元素放在第k个位置上,最后修改表的长度

    public static void del(List<Integer> list,int p){
    		int k=0;		
    		for(int i=0;i<list.size();i++){
    			if(list.get(i)!=p){
    				list.set(k, list.get(i));
    				k++;
    			}
    		}
    		
    		for(int i=list.size()-1;i>=k;i--){
    			list.remove(i);
    		}
    	}

    延伸:改变判断条件,可以删除[x,y]之间的所有元素。

    补充:打印list的三种方法

    第一种:

    for(int i=0;i<list.size();i++){

    System.out.println(list.get(i));

    }

    第二种:

    Iterator <Integer> it=list.iterator();

    while(it.hasNext()){

    System.out.println(it.next());

    }

    第三种:

    System.out.println(list);


    展开全文
  • 链表尽管不需要移动元素,只用改变指针关系,但是要插入或删除第i个节点,必须先找到第i-1个节点,复杂度为o(n)。 总体完成一次操作,大家都是o(n)的复杂度,为什么教材和网路上都说,要频繁删除插入操作时,选链表...
  • 线性表: 顺序存储结构(用一段连续地址存储) 存、读第i个位置元素,O(1) ... 插入/删除O(n)——不清楚第i个元素指针位置时,但是已知时为O(1),对于频繁插入/删除有效率优势 静态链表(用数
  • 上一节我讲了冒泡排序,插入排序,选择排序这三种排序算法,我们的时间复杂度都是O(n^2),比较高,适合小规模数据的排序...我们可以借鉴这思想,来解决非排序的问题,比如:如何在O(n)的时间复杂度内查找一无序数...
  • get(index) 根据下标查询,顺序存储知道首个元素的地址,其他的位置很快就能确定,时间复杂度为O(1) 链式存储,从首个元素开始查找,直到查找到 i个位置,时间复杂度为O(n) add(E) 直接尾部添加,时间复杂度O(1...
  • 假设线性表长度为n 查找 查找特定元素x,最好情况是第一个位置就找到,最坏情况是最后一个位置找到。   总比较次数是:1+2+…+n,即n(n+1)2\...在第i个位置插入数据x,共有(n+1)(n+1)(n+1)个插入位置; 插...
  • 为了方便描述过程,假定一线性表...1、进入循环,当遇到item元素时,不做任何处理,否则将指针i指向值赋予指针j位置,且指针j右移 2、循环终止,最终将线性表index等于j-1位置。(最后一步index位置,看i
  • 接上一篇文章继续分析 线性表——顺序表——时间复杂度计算    在之前的文章中的示例1和示例2中,我们通过观察可以发现,当...   假设pip_i是在第i个元素之前插入一个元素的概率,则在长度为n的线性表中插入一个元
  • 求助:最近,发现了一种新数组排序方法,初测其速度是快速排序法近50倍,想知道有没有市场价值,时间复杂度能计算出来吗?请各位大神赐教! 下面,为了便于区别说明将这新方法暂且称之占位排序法; 用javascript...
  • 3 //缺点,比起线性表,找出第i个元素很困难,时间复杂度为o(n),线性表只要直接下标获取,时间复杂度为O(1) 4 //优点,单链表插入和删除时非常方便时间复杂度为o(1),线性表插入和删除最后情况是...
  • 3.对长度为n顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)算法,该算法删除线性表中所有值为x数据元素。 /** * 删除线性表中所有值为x数据元素 * */ void deleteXElem(SqList *List, ElemType x) {...
  • 数据元素本身连续存储,每个元素所占的存储单元大小固定相同,元素的下标是其逻辑地址,而元素存储的物理地址(实际内存地址)可以通过存储区的起始地址Loc(e0)加上逻辑地址(第i个元素)与存储单元大小(c)的...
  • 顺序表插入、删除平均移动次数

    千次阅读 2020-12-03 23:46:05
    目录 一、插入操作 二、删除操作 三、总结 ... 最坏情况:删除表头元素(即i-1),需移动除个元素所有元素,时间复杂度为0(n)。 平均情况:。解释如下: 三、总结 无论插入还是删除,需要移动
  • L,i,e) 在第i个位置插入元素e; 1.找到第2个结点, 2.用malloc申请一个新结点, 将第3个新结点7插入后面 3.对指针进行修改, 如果是有头结点,可以把头结点看成第0个结点,适用于上面三步 时间复杂度: 插到头结点后面O(1...
  • 顺序存储结构线性表各种算法一、删除操作1、删除第i个元素开始k个元素 一、删除操作 虽说顺序存储结构不适合删除操作,但是有时候为了追求时间复杂度和空间复杂度最优,还是颇有难度。 1、删除第i个元素开始...
  • 2.2.3试题6-10

    2018-10-27 23:31:22
    6.在n个元素的线性表的数组表示中,以下时间复杂度为: (1).访问第i个结点(1&...删除第i个结点的时间复杂度为O(n); (4).在第i个结点后插入一个结点(1&lt;=i&lt;=n)的时间复杂度为O(n); 7.输出...
  • 顺序表删除第i个元素要将后n-i个元素前移,可以将前面元素后移再改变起始地址吗?这样删除第一个元素时间复杂度为O(1)(虽然总不变)</p>
  • 第i个元素: 起始位置+(i-1)*偏移量 时间复杂度 :数组随机访问元素时间复杂度O(1):常数时间复杂度 线性存储:每个元素都有一个前驱元素,一个后续元素 2、链表 链表是线性存储数据结构,跟数组不同在于,...
  • ArrayList从0到1

    2020-06-30 12:43:13
    插入删除元素的时间复杂度为O(n),求表长以及增加元素,取 i 元素的时间复杂度为O(1) 1.ArrayList的数据结构 //使用一Object数组进行存储 transient Object[] elementData; //数组元素的大小 private int...
  • 编写一链表

    2015-12-05 23:13:56
    (1)编写一个程序,其功能是:从顺序表的第i个位置开始,删除k个元素。 (2)编写一个程序,其功能是:在一个非递减顺序表中,删除所有值相等多余元素,要求时间复杂度为O(n),空间复杂度为O(1)。
  • 线性表 线性表又分为顺序储存和...删除顺序表的第 i 个元素时,需要移动 n - i 个元素; 插入到 i 个位置时,需要移动 n - i + 1个元素。 顺序表有静态分配与动态分配,这里记录最常用动态分配 #include<stdlib
  • 大数据技术与应用资源库 主讲人章万静 数据结构C语言版 ...空间复杂度评估执行程序所需存储空间可以估算出程序对计算机内存使用程度 试题分析 2在一个长度为n顺序表中删除第i个元素需要向前移动 n-i 个元素 答案
  • 链表是一种顺序存取结构,按位置访问链表中第i个元素时,只能从表头开始依次向后遍历链表,直到找到第i个位置上元素,时间复杂度为O(n), 即取值操作效率低。但在确定插入或删除的位置后,插入或删除操作无需移动...
  • 各种线性表比较

    2017-07-06 13:31:00
    (1)存取速度快:随机存取结构,存取第i个元素所花的时间与i无关,与表长无关,即时间复杂度为O(1) (2)存储密度高:存储空间的利用率高,顺序表的空间几乎全用来存储数据,只有一小点存储长度值。 缺点 ...
  • 从头开始找,找到第i个元素为止。这个算法复杂度取决于i位置。最坏情况下时间复杂度是O(n). 单链表插入操作 单链表的删除操作

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 136
精华内容 54
关键字:

删除第i个元素的时间复杂度