精华内容
下载资源
问答
  • 长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法 该算法删除线性表中所有值x的数据元素 /*对长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法 该算法删除...

    题目要求:

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

    /*对长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法
    该算法删除线性表中所有值为x的数据元素*/
    #include <iostream>
    #include <cstring>
    #include<math.h>
    #define MAXSIZE 20
    #define ElemType int//不加分号
    using namespace std;
    typedef struct {
    	ElemType data[MAXSIZE];
    	int length;
    }SqList;
    bool InitList(SqList &L) {
    	memset(L.data, 0, sizeof(L));
    	if (!L.data)
    		exit(0);
    	L.length = 0;
    	return true;
    }
    void CreateList(SqList &L, int n) {
    	for (int i = 0;i<n;i++) {
    		cin >> L.data[i];
    		L.length++;
    	}
    }
    bool DeleteX(SqList &L,ElemType e) {//推荐做法,更容易想
    	//注释部分的做法没有达到空间复杂度为o(1),也不会满足时间复杂度要求
    	/*int x[MAXSIZE];
    	int j=-1;
    	memset(x, 0, sizeof(x));*/
    	int k=0;//用k来记录所有值不是x的元素的下标,边扫描边统计k,并将不等于x的元素向前移动k个位置,最后修改L的长度
    	for (int i = 0;i <L.length;i++) {
    		if (L.data[i] != e) {
    			/*j++;
    			x[j] = i;*/
    			L.data[k] = L.data[i];
    			k++;
    		}
    		
    	} 
    	L.length = k;
    	return true;
    }
    void DeleteX2(SqList &L, ElemType e) {
    	int k = 0, i = 0;//用k来记录等于x的元素的个数,边扫描L边统计k,并将不等于x的元素前移k个位置,最后修改L的长度
    	while (i<L.length)
    	{
    		if (L.data[i] == e)
    			k++;//用k来记录等于x的元素的个数,边扫描L边统计k
    		else
    			L.data[i - k] = L.data[i];//将不等于x的元素前移k个位置
    		i++;
    	}
    	L.length -= k;//修改L的长度
    }
    void PrintList(SqList L) {
    	cout << "表中元素分别为";
    	for (int i = 0;i<L.length;i++)
    		cout << L.data[i] << "  ";
    	cout << endl;
    }
    int main() {
    	SqList L;
    	InitList(L);
    	int n = 0;
    	cout << "请输入要创建的表的长度:" << endl;
    	cin >> n;
    	cout << "请依次输入各个元素:(用空格隔开)" << endl;
    	CreateList(L, n);
    	cout << "请输入想要删除元素的值(即x的值):" << endl;
    	ElemType e;
    	cin >> e;	
    	DeleteX2(L,e);
    	PrintList(L);
    	return 0;
    }

     

    展开全文
  • 在顺序表个位置插入一元素9,实现顺序表插入的基本操作,输出顺序表中所有元素 #include&lt;iostream&gt; using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef...

    题目

    在顺序表中第五个位置插入一个元素9,实现顺序表插入的基本操作,输出顺序表中所有元素

    #include<iostream>
    
    using namespace std;
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
    typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型
    
    #define MAXSIZE 100			//顺序表可能达到的最大长度
    
    typedef struct {
    	ElemType *elem; //存储空间的基地址
    	int length; //当前长度
    } SqList;
    
    Status InitList(SqList &L) { //初始化创建顺序表	
    	L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
    	if (!L.elem)
    		exit(OVERFLOW); //存储分配失败退出		
    	cout<<"初始化表中元素个数:";
    	int n;
    	cin>>n;
    	cout<<"creat SqList:";  //在初始化中创建表
    	for(int i = 0; i < n; i++){
    		cin>>L.elem[i];
    	}
    	L.length = n; //空表长度为0
    	return OK;
    }
    
    void input(SqList L){//输出表 
    	ElemType i = 0;
    	while(L.length != i){
    		cout<<L.elem[i]<<" ";
    		i++;
    	}
    	cout<<endl;
    }
    
    Status ListInsert(SqList &L, int i, ElemType e) { //顺序表的插入
    	//在顺序表L中第i个位置之前插入新的元素e
    	//i值的合法范围是1<=i<=L.length+1
    	if ((i < 1) || (i > L.length + 1))
    		return ERROR; //i值不合法
    	if (L.length == MAXSIZE)
    		return ERROR; //当前存储空间已满
    	for (int j = L.length - 1; j >= i - 1; j--)
    		L.elem[j + 1] = L.elem[j]; //插入位置及之后的元素后移
    	L.elem[i - 1] = e; //将新元素e放入第i个位置
    	++L.length; //表长增1
    	return OK;
    }
    
    int main()
    {
    	SqList a;	
    	InitList(a);
    	input(a);//输出顺序表 
    	ListInsert(a,5,9); 
    	input(a);//输出顺序表 
    	return OK;
    }
    

    参考资料:
    《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民

    展开全文
  • //已知顺序表L的长度为n,试编写算法实现在顺序表中删除值elem的数据元素 //(其中n与elem从键盘输入) # include <iostream> # include <stdio.h> # include <stdlib.h> using namespace std; ...

    //已知顺序表L的长度为n,试编写算法实现在顺序表中删除值为elem的数据元素
    //(其中n与elem从键盘输入)

    # include <iostream>
    # include <stdio.h>
    # include <stdlib.h>
    using namespace std;
    const maxn = 1000 + 10;
    
    typedef struct node
    {
    	int *arr;
    	int length;
    	int maxsize;
    }sqlist;
    
    void createsqlist(sqlist &L)
    {
    	L.arr = (int*)malloc(maxn * sizeof(int));
    	L.length = 0;
    	L.maxsize = maxn;
    }
    
    void insqlist(sqlist& L, int n)
    {
    	int *p;
    	printf("请依次输入数字创建一个顺序表:\n");
    
    	for(p = L.arr; p<L.arr + n; p++)
    	{
    		scanf("%d", p);
    	}
    
    	L.length = n;
    }
    
    void outsqlist(sqlist L)
    {
    	int *p;
    	printf("顺序表的元素为:\n");
    
    	for(p = L.arr; p<L.arr+L.length; p++)
    	{
    		printf("%d ", *p);
    	}
    
    	printf("\n");
    }
    
    void deletesqlist(sqlist& L, int elem)
    {
    	int i = 0; 
    	
    	while(i<L.length && L.arr[i] != elem)
    	{
    		i++;
    	}
    
    	for(int j = i+1; j<L.length; j++)
    	{
    		if(L.arr[j] != elem)
    		{
    			L.arr[i++] = L.arr[j];
    		}
    	}
    
    	L.length = i;
    }
    
    int main()
    {
    	//加速c++输入输出流
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    
    
    	sqlist L;
    	createsqlist(L);
    	int n, elem;
    	
    	printf("请输入n个元素: \n");
    	scanf("%d", &n);
    	insqlist(L, n);
    
    	printf("请输入删除的元素值:\n");
    	scanf("%d", &elem);
    	deletesqlist(L, elem);
    	outsqlist(L);
    
    	return 0;
    }
    
    展开全文
  • 在顺序表中删除指定位置i=5)的元素,实现顺序表的删除的基本操作,输出顺序表中所有元素 #include&lt;iostream&gt; using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef ...

    题目

    在顺序表中删除指定位置(i=5)上的元素,实现顺序表的删除的基本操作,输出顺序表中所有元素

    #include<iostream>
    
    using namespace std;
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。
    typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型
    
    #define MAXSIZE 100			//顺序表可能达到的最大长度
    
    typedef struct {
    	ElemType *elem; //存储空间的基地址
    	int length; //当前长度
    } SqList;
    
    Status InitList(SqList &L) { //初始化创建顺序表	
    	L.elem = new ElemType[MAXSIZE]; //为顺序表分配一个大小为MAXSIZE的数组空间
    	if (!L.elem)
    		exit(OVERFLOW); //存储分配失败退出		
    	cout<<"初始化表中元素个数:";
    	int n;
    	cin>>n;
    	cout<<"creat SqList:";  //在初始化中创建表
    	for(int i = 0; i < n; i++){
    		cin>>L.elem[i];
    	}
    	L.length = n; //空表长度为0
    	return OK;
    }
    
    void input(SqList L){//输出表 
    	ElemType i = 0;
    	while(L.length != i){
    		cout<<L.elem[i]<<" ";
    		i++;
    	}
    	cout<<endl;
    }
    
    Status ListDelete(SqList &L, int i) { //顺序表的删除
    	//在顺序表L中删除第i个元素,并用e返回其值
    	//i值的合法范围是1<=i<=L.length
    	if ((i < 1) || (i > L.length))
    		return ERROR; //i值不合法
    	for (int j = i; j < L.length; j++)
    		L.elem[j - 1] = L.elem[j]; //被删除元素之后的元素前移
    	--L.length; //表长减1
    	return OK;
    }
    
    int main()
    {
    	SqList a;	
    	InitList(a);
    	input(a);//输出顺序表 
    	ListDelete(a,5);
    	input(a);//输出顺序表 
    	return OK;
    }
    

    参考资料:
    《数据结构 C语言版 第2版》严蔚敏 李冬梅 吴伟民

    展开全文
  • /*对长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素*/ #define MAXSIZE 50 typedef int ElemType; typedef struct{ ElemType data[MAXSIZE]; int ...
  • 数据结构线性表/顺序表新增:在第i个位置插入元素e(动态表+静态表)
  • 题目:长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 思想: 记录等于X的值的个数i,遇到不是X的位置就把值放到前面i个位置上 代码展示: #...
  • 长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 算法思想: 一步:从前往后扫描顺序表,用k纪录当前值x的数据元素的个数 二步:如果扫描...
  • typedef struct { int len; type data[MAX]; }sqList; int delsameele3...{ //每遍历一元素时都考虑其向前移动的位数 int k=0; for(int i=0;i&lt;a-&gt;len;i++) if(a-&gt;data[i]!=x) a-...
  • 数据结构删除顺序表第i个元素

    千次阅读 2021-03-10 23:11:50
    数据结构删除顺序表第i个元素 #include <stdio.h> #define MaxSize 10 typedef struct { int data[MaxSize]; int length; }sqlist; sqlist L; bool listdelete(sqlist& l, int i, int& e) { if ...
  • 解法:用K记录顺序表L中不等于X的元素数,
  • 问题描述:将两有序顺序表合并新的有序顺序表,并有函数返回结果顺序表。要求时间复杂度O(n) 算法设计思想:首先,按顺序取两个顺序表表头较小的结点存入新的线性表中直到某一表遍历完;然后将还有剩余...
  • 算法设计思想:用k记录顺序表中不等于x的元素数,即需要保存的元素数,边扫描L边统计k,并将不等于x的元素放在L.data[k]中,最后修改L的长度。 代码及结果: #include<stdio.h> #include "线性表的...
  • 问题描述:长度为n顺序表L,编写一时间复杂度O(n),空间复杂度O(1)的算法,该算法删除线性表中所有值x的数据元素。 解决思想: 这问题一复杂的解决方法是依次遍历顺序表,遇到值x的元素就删除,...
  • 已知顺序表中的元素依值递增有序排列,要求将x插入到顺序表的适当位置上,使得插入操作后的顺序表仍保持有序性。 # include <stdio.h> # include <stdlib.h> # define initsize 20//初始分配量 # define...
  • #include using namespace std; class arrList{ ...//顺序表的当前长度 public: int maxSize;//顺序表的实例的最大长度 void set(const int size){ maxSize=size; aList=new int[maxSize
  • 将两个顺序表位置互换

    千次阅读 2018-09-10 22:17:18
    这里使用了书的一种不借用辅助数组的算法,先将两个顺序表整体逆置,两个顺序表位置正好互换过来但是两表内的元素顺序被弄反,所以分别对两个顺序表进行一次整体逆置即可,代码如下: #include&amp;...
  • 将俩有序顺序表合并新的有序顺序表,并返回结果 输入: 3 3 1 2 3 4 5 6 输出 1 2 3 4 5 6 输入: 3 3 3 3 4 4 5 5 输出: 3 4 5 思路: 简单比较两数组大小, 由于有序, 1.如果结果数组当前存储和a...
  • 数据结构-顺序表基本操作的实现(含全部代码)

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构...L,int n) 参数:顺序表L,顺序表长度n 功能:创建长度顺序表 时间复杂度:O(n) InitList(SqList &...
  • 顺序表的存储结构如下: typedef struct { ElemType *elem; int length; int listsize; }SqList; 顺序表的初始化如下: void InitList_Sq(SqList &L) { //构造一空的线性表L L.elem = (ElemType...
  • 该程序实现了一个顺序表的基本操作: int InitList_Sq(); //初始化线性表 void CreateSqList(); //创建线性表 void ListInsert(); //向线性表中插入值 void ListDelete(); //删除顺序表中的数据元素 void Print...
  • #include<stdio.h> #define N 100 typedef struct { int data[N]; int last; }Array; void Create(Array *L,int m); void Print(Array *L); v...
  •  使用二分查找有序数组a[n]中查找一元素x的时间复杂度()。 A. O(n) B. O(n2n^2) C. O(logn) D. O(nlogn) 分析:  一般这种情况问的都是最坏情况下的时间复杂度,二分查找每次对半,假设需要m次迭代查询...
  • eg:顺序表A:1 3 5 7 顺序表B:2 4 6 8 合并后的表C:8 7 6 5 4 3 2 1 **思路:**从后往前遍历顺序表A和B,如果当前A表的数大于等于B表的数,则将A表的数存入C,A的元素下标往前移一位,否则,将B表的数存入C表,B...
  • 首先应该创建一个顺序表,从键盘输入数据; 显示顺序表 插入之前先找到插入的位置; 将插入位置后面的数据往后移动; 完整的代码 #include&lt;stdio.h&gt; 2 #include&lt;stdlib.h&gt; 3 4 #...
  • 建立简单顺序链表,初学者简单易懂。   #include&lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;malloc.h&gt; using namespace std; struct student { int num; struct ...
  • 顺序表a中的数据元素递增有序,试设计一算法,将x插入到顺序表的适当位置,以保持该表的有序性。
  • 假设链表L有n个元素,如果这n个元素中每一元素被访问的概率都相同,则访问到第i个元素所前移的指针的平均次数: Average = (1+2+3+......+n)/n = n(1+n)/2/n = n/2 + 1/2 所以,访问第i个元素的平均时间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 233,080
精华内容 93,232
关键字:

在长度为n的顺序表的第i个位置上