已知长度为n的线性表A采用顺序存储结构，请写一个时间复杂度为O（n）、空间复杂度为O（1）的算法，该算法可删除线性表中所有值为item的数据元素。

谁借莪１个温暖的怀抱￠ 2022-09-12 04:50 162阅读 0赞

#include "stdio.h"
    #include "malloc.h"
    #include "stdlib.h"
    typedef int dataType;
    typedef struct {
    	int data[100];//数据
    	int length;//长度
    }SeqList;
    
    SeqList *init();
    void fill(SeqList *L);
    void show(SeqList *L);
    void delSeqList(SeqList *L,int i);
    void destorylist(SeqList *L);
    
    //主函数
    int main(){
    	SeqList *L;
    	int e;
    	L=init();
    	fill(L);
    	show(L);
    	printf("\n你要进行删除的数据的值为：");
    	scanf("%d",&e);
    	printf("进行删除表中所有值位%d的数据\n",e);
    	delSeqList(L,e);
    	show(L);
    	destorylist(L);
    }
    //初始化表格
    SeqList *init()
    {
    	SeqList *L;
    	//申请空间
    	L=(SeqList *)malloc(sizeof(SeqList));
    	//长度为0
    	L->length=0;
    	return L;
    }
    //内容填充
    void fill(SeqList *L)
    {
    	int i=0;
    	printf("以下开始填充内容\n");
    	printf("数组的数量：");
    	scanf("%d",&L->length);
    	while(i<L->length)
    	{
    			printf("第【%d】位：",i);
    			scanf("%d",&L->data[i]);
    			i++;
    	}
    }
    	
    //展示表格
    void show(SeqList *L)
    {
    	int i;
    	//依次展示数组内容
    	for(i=0;i<L->length;i++)
    	    printf("第[%d]位为%d   ",i,L->data[i]);
    }
    //销毁表
    void destorylist(SeqList *L)
    {
    	free(L);//释放空间
    }
    
    //删除所有值为e的数据
    void delSeqList(SeqList *L,int e)
    {
      int j = 0,i=0;
        for(; i<L->length;i++)
        {
    		//如果不等于就按顺序排下去，等于就不执行
    		if(L->data[i] != e)
            {
                L->data[j] = L->data[i];
                j++;
            }
        }
        L->length = j;
    }

**时间复杂度**为O(n)：说明只能用依次循环。

O(1)是最低的**空间复杂度**，也就是耗耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 表示该程序所占用的空间和所用数据量无关。

**空间复杂度：一个算法在运行过程中临时占用的存储空间的度量。**

**代码思路：**

原本是想先寻找目标值，将数组依次向前覆盖，但发现如果有多个跟目标值一样的数，算法会出错。后来进行更改，发现完善之后，算法的时间复杂度会是O(n2)。

然后就想到把不是目标值的数，全部重新排到数组中，去除目标值，时间复杂度便成为了O(n)。

**输出**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_20_color_FFFFFF_t_70_g_se_x_16][]

**输入**

6
    2
    3
    2
    6
    2
    5

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA546L6ZmI6ZSL_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8bfaae9ebeff4268b02647547a2bb92b.png