精华内容
下载资源
问答
  • 长度为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;
    }

     

    展开全文
  • typedef struct { int len; type data[MAX]; }sqList; int delsameele3(sqList *a,type x) { //每遍历一个元素时都考虑其向前移动...//删除后的顺序k上的元素总等于按顺序不等于x的i位置的元素 // a->len=k; }
    typedef struct
    {   int len;
        type data[MAX];
    }sqList;
    int delsameele3(sqList *a,type x) 
    { //每遍历一个元素时都考虑其向前移动的位数 
        int k=0;
        for(int i=0;i<a->len;i++)
        if(a->data[i]!=x)
           a->data[i-k]=a->data[i];
        else k++; 
        a->len-=k;//否则最后的k个元素将重复出现,也符合定义 
        return 0;
    //  方法二:
    //   for(int i=0;i<a->len;i++)
    //     if(a->data[i]!=x)
    //        a->data[k++]->data[i];//删除后的顺序表k上的元素总等于按顺序不等于x的i位置的元素
    //        a->len=k;        
    }
    
    展开全文
  • 如果一个有序数组,你想插入一个数据,还需要把其后所有元素往后移一位。 那么有没有一个比较好的数据结构可以实现简单便捷的插入操作呢? 那就是链表,链表由两个部分组成,前面的部分数据部分,用来存储...

        如果在一个有序数组中,你想插入一个数据,还需要把其后所有元素往后移一位。

        那么有没有一个比较好的数据结构可以实现简单便捷的插入操作呢?

        那就是链表,链表由两个部分组成,前面的部分为数据部分,用来存储数据,后面的部分为指针部分,用来指向下一个结点,链表的数据结构就很好地解决了插入麻烦的问题。(本文只介绍尾插法)只需要让前一个结点的指针指向要插入的数据,让插入的数据的指针,指向上一个结点原本指向的结点即可!

        下面是代码的实现:
        

    #define _CRT_SECURE_NO_WARNINGS 1
    
    #include <stdio.h>
    #include <stdlib.h>
    
    /*
    * 本程序是对于有序链表插入操作的练习
    * 郭文峰
    * 2018/9/30
    */
    
    struct node
    {
    	int data;
    	struct node *next;
    };
    
    int main(void)
    {
    	struct node *head = NULL;
    	struct node *p = NULL;
    	struct node *q = NULL;
    	struct node *t = NULL;
    
    	int i = 0;
    	int a = 0;
    	int n = 0;
    
    	//输入n的值,代表链表有几个元素
    	scanf("%d", &n);
    	for (i = 1; i <= n; i++)
    	{
    		scanf("%d", &a);
    
    		//动态申请一个内存来存储下一个结点,并用临时指针p指向这个结点
    		p = (struct node *)malloc(sizeof(struct node));
    		p->data = a;
    		p->next = NULL;
    
    		//用尾插法插入临时指针p指向的结点
    		if (head == NULL)
    		{
    			head = p;
    
    		}
    		else
    		{
    			q->next = p;
    		}
    
    		q = p;//让q指向此结点
    
    	}
    
    	//输入带插入的值
    	scanf("%d", &a);
    	//从头指针开始遍历
    	t = head;
    	while (t != NULL)
    	{
    		if (t->next->data > a)
    		{
    			p = (struct node *)malloc(sizeof(struct node));
    			p->data = a;
    			p->next = t->next;
    			t->next = p;
    			break;//插入即完毕,退出循环
    		}
    		t = t->next;
    	}
    
    	//输出所有结点
    	t = head;
    	while (t != NULL)
    	{
    		printf("%d   ", t->data);
    		t = t->next;
    	}
    
    	system("pause");
    
    	return 0;
    
    }

     

    展开全文
  • printf("初始状态顺序长度: ()\n"); scanf("%d", &n); printf("请输入你要创建的顺序:\n"); for (int i = 0; i < n; i++){ scanf("%d", &L.elem[i]); //存入的值从数组0开始 L.length++; } } bool ...

    刚开始学数据结构,还费了很多的时间才做完这个实验0.0

    #include<stdio.h>
    #include<stdlib.h>    //malloc函数头文件
    #define false 0
    #define true 1
    #define LIST_INIT_SIZE  100
    #define LISTINCREMENT 10
    typedef struct{
    	int *elem;
    	int length;    //当前长度 
    	int listsize;//当前分配的存储容量 
    }SqList;
    
    bool InitList(SqList &L){  //数据表的创建
    	L.listsize = LIST_INIT_SIZE;
    	L.elem = (int *)malloc(L.listsize*sizeof(int));     //给顺序表创建动态空间
    	if (!L.elem){ //存储分配失败 
         return	false;
    	}
    	L.length = 0;
    	return true;
    }
    
    void InPut(SqList &L){
    	int n;
    	printf("初始状态顺序表的长度: (<100)\n");
    	scanf("%d", &n);
    	printf("请输入你要创建的顺序表:\n");
    	for (int i = 0; i < n; i++){
    		scanf("%d", &L.elem[i]);   //存入的值从数组0开始
    		L.length++;
    	}
    }
    
    bool ListInsert(SqList &L, int i, int e){
    	if(i<1 || i>(L.listsize+1) ){
    		return false;
    	}
    	if(L.length>=L.listsize){
    		SqList M; 
    		M.elem=(int *)realloc(L.elem , (L.listsize + LISTINCREMENT)*sizeof(int)); 
    		if(!M.listsize) return false;
    		L.elem=M.elem;
    		L.listsize+= LISTINCREMENT;
    	}
    	for(int j=L.length-1;j>=i-1;j--){
    		L.elem[j + 1] = L.elem[j];
    	} 
    	L.length+=1;
    	L.elem[i-1]=e;
    	return true;
    }
    
    void ListTraverse(SqList &L){
    	for(int i=0;i<L.length;i++){
    		printf("%d, ",L.elem[i]);
    	}
    }
    
    int main(){
    	int p;
    	int y_num;
    	SqList L;
    	InitList(L);
    	InPut(L);//输入时就是非递减的
    	printf("请输入要插入的整数:\n");
    	scanf("%d",&y_num);
    	for(p=0;p<L.length;p++){
    		if(y_num<=L.elem[p]){
    			p=p+1;//0.0
    			ListInsert(L,p,y_num);
    			break;
    		}
    	}
    	if(y_num>L.elem[L.length-1]){
    		ListInsert(L,L.length+1,y_num);
    	}
    	ListTraverse(L);
    	return 0;
    } 
    

     

    展开全文
  • 直接上代码 ...#define LIST_INIT_SIZE 10//顺序存储空间的初始分配量 #define LISTINCREMENT 5// 顺序存储空间的分配增量 #define OVERFLOW 0 #define ok 1 typedef struct{ int *element;//...
  • 实验目的 熟悉将算法转换成程序代码的过程,了解...(1)非递减有序的顺序表中插入一个元素x,保持顺序表有序性               #include&lt;stdio.h&gt; #include&lt;stdlib.h&g...
  • 设顺序a的数据元素递增有序,试设计一个算法,将x插入到顺序的适当位置,以保持该有序性
  • //将两个有序链表并一个有序链表算法,该程序也可以cFree环境运行。 // c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> // malloc()等 #include<limits.h> //...
  • 已知顺序表中的元素依值递增有序排列,要求将x插入到顺序的适当位置上,使得插入操作后的顺序仍保持有序性。 # include <stdio.h> # include <stdlib.h> # define initsize 20//初始分配量 # define...
  • 有序表

    万次阅读 2018-03-03 10:25:05
    一、有序表的定义所谓有序表,是指这样...若以顺序、单链表存储有序表,会发现基本运算算法只有ListInsert()算法与前面对应的运算有所差异,其余都是相同的。有序顺序的ListInsert()算法如下:void ListInsert...
  • 转自:... ...   ...2个有序数组求合并后的位数 ...第一步:假设两个有序数组(已经各自排序完成了)长度相等,试写函数找出两个数组合并后的位数。 第二步:假设两个有序数组长度不等,一样的
  • 已知长度为n的线性表A采用顺序存储结构,请写一尽可能高效的算法,删除线性表所有值item的数据元素 直接上代码 void DeleteItem (Sqlist *L,int item) { int i=0,j=0,count=0; for(i=0;i<L->length;) ...
  • 其中n为查找表中元素个数 Pi查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n Ci是找到第i个元素的比较次数。 举例: 长度为10的,采用顺序查找法,平均查找长度ASL是? 如果一定可以找到的: ...
  • 插入之前先找到插入的位置; 将插入位置后面的数据往后移动; 完整的代码 #include&lt;stdio.h&gt; 2 #include&lt;stdlib.h&gt; 3 4 #define LIST_INIT_SIZE 100 5 #define LISTINCREMENT 10 ...
  • C语言:向一个有序数组插入一个数据,保持数组的有序性。 #include <stdio.h> //向一个有序数组插入一个元素,重新实现有序,并输出。 int main() { //注意数组a目前只有10个元素,元素64的下标9. int...
  • 有序链表的插入

    千次阅读 2017-11-07 20:28:21
    已知一个递增有序链表L(带头结点,元素整数),编写程序将一个新整数插入到L,并保持L的有序性。 其中单链表的类型定义参考如下: typedef int elementType; typedef struct lnode { elementType data; ...
  • 1. #include &lt;stdio.h&gt; void main(){ /* 输出数组各元素*/ int i,key,loc; int a[10]={1,3,6,9,10,15,16,22,30}; for(i=0;i&lt;9;i++){ printf("...\n\nPlease...
  • 顺序有序表查找顺序查找定义:从线性表的第一个(或最后一个)数据元素开始,逐个进行数据元素关键字和给定值的比较,若某个数据元素的关键字和给定值相等则查找成功;如果直到最后一个(或第一个)数据元素,...
  • 线性表--有序表

    千次阅读 2018-08-09 22:40:23
    有序表-逻辑结构 所谓有序表,是指这样的线性表,其中所有元素以递增或递减方式有序排列。...若以顺序存储有序表,会发现基本运算算法只有ListInsert()算法与前面的顺序对应的运算有所差异,...
  • 已知顺序表中的元素依值递增有序排列,要求删除表中所有值相同的多余元素(使得操作后的顺序表中所有元素的值均不相同) # include <stdio.h> # include <stdlib.h> # define initsize 20//初始分配量 ...
  • 有序线性表从大到小排列,西安插入一个数,插入后的线性表依然是有序线性表。 代码如下: #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define Max 100 // 定义数组的最大长度 typedef ...
  • 对于长度为n的顺序L,编写一个算法,该算法删除线性表的所有值X的元素。 要求:时间复杂度O(n) 空间复杂度O(1) 算法思路: 方法一:用K记录LX的元素的个数,即需要保存的元素的个数,边扫描边...
  • 线性表 线性表是最简单也是最常用的一种数据结构。 逻辑结构 线性表定义:线性表是具有相同特性的数据元素的一个有限序列。...设序列第i(i表示逻辑序号)个元素ai(1≤i≤n),则线性表的一般表示:  ...
  • n有序集合的合并,我最低的时间复杂度只能降到O(n^2),水平不够,不能再优化了。 先说说我的思想: 输入要求已经说明了,我必须要先保存这n个集合,包括集合的长度以及元素,显然是一个二维数组,第一维存放长度...
  • Redis有序集合 zset 的底层实现——跳跃skiplist Redis简介 Redis是一个开源的内存的数据结构存储系统,它可以用作:数据库、缓存和消息中间件。 它支持多种类型的数据结构,如字符串(Strings),散列...
  • 有序表的查找——折半查找分析

    千次阅读 2020-06-03 21:31:59
    二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用数组向量作为的存储结构,不能使用链表,不妨设有序表是递增有序的。 2、二分查找的基本思想 二分查找的基本思想是:(设R[low…high]是当前的...
  • 做到一道求 哈希查找成功与查找不成功 情况下平均查找长度的计算问题,迷惑了好一会,这里总结下来: ...地址空间0~16的散列区,对以下关键字序列构造两个哈希: {Jan, Feb, Mar, Apr, May, June,
  • 不善于解释,代码下面,function函数是主要实现的函数,希望能帮到你#include<malloc.h> #include<assert.h> #include<stdio.h> #define SUCCESS 1 #define FAIL 0 #define Elemtype int #...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 96,068
精华内容 38,427
关键字:

在长度为n的有序性表中进行