精华内容
下载资源
问答
  • 题目: 对一行数组有四种操作: ...此处采用数组模拟链表实现 对于第四种操作,可以用一个变量去判断是否翻转,如果翻转的话,只需要把原来的左右指针交换即可。 注意交换的时候,两个数字相邻和两个数字...

    题目:

    对一行数组有四种操作:

    1.把数字x放到数字y的左边

    2.把数子X放到数字Y的右边

    3.交换X和Y的位置

    4.把所有数字翻转顺序

    思路:

    如果用数组的话,明显第四个操作就会明显超时。所以采用链表。用链表模拟一下就行。此处采用数组模拟链表实现

    对于第四种操作,可以用一个变量去判断是否翻转,如果翻转的话,只需要把原来的左右指针交换即可。

    注意交换的时候,两个数字相邻和两个数字不相邻是两种不同的方式。

    代码:

    /*by kzl*/
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<vector>
    
    using namespace std;
    const int maxx = 1e5+500;
    const int INF = 0x3f3f3f3f;
    typedef long long LL;
    
    int n,m,a,x,y;
    int lnext[maxx],rnext[maxx];
    long long sum = 0;
    void init()
    {
        for(int i=1; i<=n; i++)rnext[i] = i+1,lnext[i] = i-1;
        rnext[0] = 1;lnext[0] = n;rnext[n] = 0;
        sum = 0;
    }
    
    void one(int l[],int r[],int x,int y){
        if(l[y]==x)return;
        l[r[x]] = l[x]; //把X从列表中删除
        r[l[x]] = r[x];
    
        r[l[y]] = x;//将x插入到y左侧
        l[x] = l[y];
        r[x] = y;
        l[y] = x;
    }
    
    void two(int l[],int r[],int x,int y){
        if(r[y]==x)return;
        l[r[x]] = l[x]; //把X从列表中删除
        r[l[x]] = r[x];
        //将x插入到y右侧
        l[r[y]] = x;
        r[x] = r[y];
        r[y] = x;
        l[x] = y;
    }
    
    void three(int l[],int r[],int x,int y){
        if(r[y]==x)swap(x,y);
        if(r[x]==y){
            r[x] = r[y];
            l[r[y]] = x;
            l[y] = l[x];
            r[l[x]] = y;
            r[y] = x;
            l[x] = y;
            return ;
        }
        int cc = r[x],dd = l[x];
        l[r[y]] = x;r[l[y]] = x;
        r[x] = r[y];l[x] = l[y];
        l[cc] = y;r[dd] = y;
        r[y] = cc;l[y] = dd;
    }
    
    void getsum(int ne[]){
        for(int i = ne[0],j=1;i!=0;i = ne[i],j++){
            if(j&1&&i<=n)sum+=i;
        }
    }
    
    int main()
    {
        int num = 1;
        while(scanf("%d%d",&n,&m)!=EOF)
        {
            init();
            int flag = 0;
            for(int i=0; i<m; i++)
            {
                scanf("%d",&a);
                if(a==1) //move box X to the left to Y
                {
                    scanf("%d%d",&x,&y);
                    if(flag==0)
                    {
                        one(lnext,rnext,x,y);
                    }
                    else one(rnext,lnext,x,y);
                }
                else if(a==2)
                {
                    scanf("%d%d",&x,&y);
                    if(flag==0)
                    {
                        two(lnext,rnext,x,y);
                    }
                    else two(rnext,lnext,x,y);
                }
                else if(a==3)
                {
                    scanf("%d%d",&x,&y);
                    if(flag==0)
                    {
                        three(lnext,rnext,x,y);
                    }
                    else three(rnext,lnext,x,y);
                }
                else if(a==4)
                {
                    flag = flag^1;
                }
            }
            if(flag==0)getsum(rnext);
            else getsum(lnext);
            printf("Case %d: %lld\n",num++,sum);
        }
        return 0;
    }
    
    

    可优化:

    以上代码可以有以下优化:

    1.连接两个节点的操作可以写成一个函数,节省代码。

    2.对于4操作,因为因为他只影响了1,2的顺序,而且1,2操作相对来说正好关于4操作对称,所以翻转之后的1操作实际就是之前的2操作。而不必要翻转指针。

    展开全文
  • 数组是申请的一块连续的内存空间,并且是在编译阶段就要确定空间大小的,同时在运行阶段是不允许改变的,所以它不能够随着需要的改变而增加或减少空间大小,所以数据量大的时候,有可能超出了已申请好的数组上限,...

    1.链表与数组的区别

    2.链表的创建以及链表的静态添加

    3.链表的动态添加(头插法)

    1.链表与数组的区别:

    谈到链表与数组的区别,可以从几个不同的角度来谈,

    首先从逻辑结构上说,两者都是数据结构的一种,但存在区别,

    数组是申请的一块连续的内存空间,并且是在编译阶段就要确定空间大小的,同时在运行阶段是不允许改变的,所以它不能够随着需要的改变而增加或减少空间大小,所以当数据量大的时候,有可能超出了已申请好的数组上限,产生数据越界,或者是数据量很小,对于没有使用的数组空间,造成内存浪费。

    链表则是动态申请的内存空间,并不像数组一样需要事先申请好大小,链表是现用现申请就OK,根据需求动态的申请或删除内存空间,对于的是增加或删除数据,所以比数组要灵活。

    再从物理存储即内存分配上分析,

    数组是连续的内存,对于访问数据,可以通过下标直接读取,时间复杂度为O(1),而添加删除数据就比较麻烦,需要移动操作数所在位置后的所有数据,时间复杂度为O(N)。

    链表是物理上非连续的内存空间,对于访问数据,需要从头便利整个链表直到找到要访问的数据,没有数组有效,但是在添加和删除数据方面,只需要知道操作位置的指针,很方便可以实现增删,教数组比较灵活有效率。

    所以综合以上,对于快速访问数据,不经常有添加删除操作的时候选择数组实现,而对于经常添加删除数据,对于访问没有很高要求的时候选择链表。

    2.链表的创建以及链表的静态添加:
    来看看一个链表是怎么生成的以及它的静态添加代码:

    #include<stdio.h>
    
    
    struct Link
    {
            int a;
    
            char c;
    
            struct Link *next;//在结构体中加入一个指针,为生成一个链表做准备
    };
    
    
    int main()
    {
            struct Link t1 = {100,'a',NULL};
            								//静态给两个结构体赋值
            struct Link t2 = {200,'b',NULL};
    
            t1.next = &t2;//将结构体1中的指针指向结构体2,这样一个简易链表就产生了
    
            printf("use t1 go to input t2\n");
    
            printf("t1:%d %c t2:%d %c\n",t1.a,t1.c,(t1.next)->a,(t1.next)->c);
    
            return 0;
    }
    
    

    在这里插入图片描述
    可以看到,通过结构体t1输出了t2中的值,这就是一个链表,将结构体t1和t2关联了起来

    然后我们再来看看链表的遍历:

    #include<stdio.h>
    
    
    struct Link
    {
            int a;
    
            char c;
    
            struct Link *next;
    };
    
    
    void printLink(struct Link *p)//不直接用t1来访问t2,而是通过指针的移动来遍历链表,从而输出两个结构体中的数据
    {
            while(p != NULL){
                    printf("%d %c\n",p->a,p->c);
                    p = p->next;
            }
    }
    
    int main()
    {
            struct Link t1 = {100,'a',NULL};
    
            struct Link t2 = {200,'b',NULL};
    
            t1.next = &t2;
    
            printLink(&t1);
    
            return 0;
    }
    
    

    在这里插入图片描述
    通过这种方式也能实现对链表中数据的访问,毫无疑问,这种方式更为的简洁,尤其是当链表中元素很多的时候,采用这种遍历的方法尤为的重要。

    3链表的动态添加(头插法):
    静态添加显得有些呆滞,大部分时候我们还是需要动态输入数据,因为这里来介绍一种动态添加的方法即头插法.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    struct Link
    {
            int a;
    
            char c;
    
            struct Link *next;
    };
    
    
    void printLink(struct Link *p)//将头插法后的链表中的数据以遍历的方式打印出来
    {
            while(p != NULL){
                    printf("%d %c\n",p->a,p->c);
                    p = p->next;
            }
    }
    
    
    struct Link* insertFromHead(struct Link *p)//封装的头插法函数
    {
            struct Link *new;
    
            while(1){
                    new = (struct Link*)malloc(sizeof(struct Link));
    
                    printf("plaese input number and letter\n");
    
                    scanf("%d",&new->a);
    
                    getchar();//吸收scanf中的回车
    
     				scanf("%c",&new->c);
    
                    if(new->a<=0){	
                            printf("You input a error data\n");
                            return p;
                    }								//以用户输入小于零的数来终止头插法,大家也可以根据自己的习惯来设计
    
                    if(p == NULL){
                            p = new;
                    }else{
                            new->next = p;
                            p = new;
                    }
            }
            return p;
    }
    
    int main()
    {
            struct Link *head = NULL;
    
            head = insertFromHead(head);
    
            printLink(head);
    
            return 0;
    }
                                                               
    

    在这里插入图片描述
    可以看到当我输入0的时候,程序自动终止了,并且先输入的数据排在链表的后面,这也体现了头插法的特点,好了,关于链表的介绍就到这里了,希望能对学习链表的你们有所帮助。

    展开全文
  • 链表数组的区别

    2018-09-28 11:06:42
    首先分别介绍一下链表数组链表的特性是在中间任意位置添加删除元素的都非常的快,不需要移动其它的元素。通常链表每一个元素都要保存一个指向下一个元素的指针(单链表)。双链表的话每个元素即要保存到下一个...

    转https://blog.csdn.net/sunjiangangok/article/details/69943631
    链表和数组都可用来存放指定的数据类型。
    首先分别介绍一下链表和数组。
    链表的特性是在中间任意位置添加删除元素的都非常的快,不需要移动其它的元素。通常链表每一个元素都要保存一个指向下一个元素的指针(单链表)。双链表的话每个元素即要保存到下一个元素的指针,还要保存一个上一个元素的指针。循环链表则把最后一个元素中保存下一个元素指针指向第一个元素。 数组是一组具有相同类型和名称的变量的集合。这些变量称为数组的元素,每个数组元素都有一个编号,这个编号叫做下标,我们可以通过下标来区别这些元素。数组元素的个数有时也称之为数组的长度。
    数组是将元素在内存中连续存放,由于每个元素占用内存相同,所以你可以通过下标迅速访问数组中任何元素。但是如果你要在数组中增加一个元素,你需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果你想删除一个元素,你同样需要移动大量元素去填掉被移动的元素。 链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。如果你要访问链表中一个元素,你需要从第一个元素开始,一直找到你需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了, 只要修改元素中的指针就可以了。
    从上面的比较你可以看出,如果你的应用需要快速访问数据,很少或不插入和删除元素,你就应该用数组;相反, 如果你的应用需要经常插入和删除元素你就需要用链表数据结构了。然后你自己可以想一想什么样的应用用链表合适。 C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。  
    链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。
    A 从逻辑结构来看
    A-1. 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数,出现溢出现象;当数据减少时,造成内存浪费。数组中插入、删除数据项时,需要移动其它数据项。 A-2. 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。
    B 从内存存储来看
    B-1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
    B-2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦.
    前面说的是单向链表和静态数组,下面简单介绍一下双向链表和动态数组。 动态数组其实比较简单,就是一个长度可以根据实际情况改变的数组。我们如果要查找某一个动态数组中的元素,可以通过get()方法来查找,只要知道该元素下标就可以了。
    双向链表存放的除了本来的数据外,还有其前驱和后驱结点。 在动态数组中,如果我们要在某一个位置添加或者删除一个元素,剩下的每个元素都要相应地往前或往后移动。如果该动态数组中的元素很多,那么,每当我们添加或删除一个元素后,需要移动的元素就非常多,因此,效率就比较低。 双向链表效率就高多了。
    如果我们要在某一个位置添加一个元素,例如,要在1,3之间插入5。本来1是指向3,3也指向1的。现在,只需要将5放到1和3之间,同时让5向前指向1,向后指向3,并且让1从3指向5,让3从1指向5就可以了。如果该链表中元素非常多,我们只需做这个操作就可以了,并不需要移动剩下的元素。 所以,双向链表在添加和删除元素上的效率要比动态数组高很多。java中系统同时提供了双向链表(LinkedList)和动态数组(ArrayList)两种机制。并且,Java中有一个叫ListIterator的迭代器。该迭代器不仅可以向后迭代元素,还能向前迭代,而且还有add()来在某一位置添加元素,十分方便。不过查找效率的话就反过来了,是动态数组的效率比双向链表的效率高,因为你只要提供元素的下标即可。


    本文来自 sunjiangangok 的CSDN 博客 ,全文地址请点击:https://blog.csdn.net/sunjiangangok/article/details/69943631?utm_source=copy

    展开全文
  • 链表数组的区别

    2017-02-07 20:25:59
    1.数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,...2.链表恰好相反,链表中的元素在内存中不是顺序存储的,而是
    1.数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少或不插入和删除元素,就应该用数组。
    2.链表恰好相反,链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

    C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在实际应用中,用户使用数组之前有时无法准确确定数组的大小,只能将数组定义成足够大小,这样数组中有些空间可能不被使用,从而造成内存空间的浪费。链表是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要时可以用new分配内存空间,不需要时用delete将已分配的空间释放,不会造成内存空间的浪费。

      (1) 从逻辑结构角度来看
         a, 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费。
         b,链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项)
      (2)从内存存储角度来看
         a,(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。

         b, 链表从堆中分配空间, 自由度大但申请管理比较麻烦.

    总结:

    数组元素连续存放在栈空间,可通过下标快速访问,空间大小需先定义,且元素增删麻烦。

    链表空间存放在堆空间,通过遍历访问元素,增删容易,但空间的申请管理麻烦。

    展开全文
  • 78 链表数组的区别

    2014-10-17 21:39:39
    78.链表数组的区别在哪里? 分析:主要在基本概念上的理解。 但是最好能考虑的全面一点,现在公司招人的竞争可能就在细节上产生,谁比较仔细,谁获 ...1数组静态分配内存,链表动态分配内存; 数组必须事先定
  • c语言-链表VS数组

    2019-09-22 19:12:59
    数组链表的区别 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,...
  • 链表是动态分配内容在内存中不连续,单双链表一致,双链表有两个指针prov,next ,prov指向上一个节点,next指向下一个节点,理论上同样的数据量双向链表的查询速度比单链表快,双向链表可以使用二分查找法,最多查找...
  • 静态链表实现与操作(C语言实现)

    千次阅读 2014-06-04 17:01:23
    没关系,我们有静态链表,其本质就是用采用数组的方式实现单链表的功能。 1,静态链表其实是单链表的另一种实现方式 2,静态链表实现“媒介”不是指针而是数组 3,静态链表主要用于不支持指针的程序设计语言中 4,静态...
  • 2、静态链表 二、具体实现 1、要有一个全局的结构体数组 2、让CursorSpace数组中的单元代替malloc和free的职能 Ⅰ.malloc的模拟实现 Ⅱ.free的模拟实现 三、其他操作 一、概述 1、动态链表 以前学习的...
  • [转]链表数组

    2011-06-22 10:54:35
     数组定义需要给出数组元素个数,系统在编译为用户分配一块地址连续的存储空间  C++语言中可以用数组处理一组数据类型相同的数据,但不允许动态定义数组的大小,即在使用数组之前必须确定数组的大小。而在...
  • 数组链表的区别 数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要...
  • 链表数组的优缺点

    千次阅读 2017-02-17 17:01:47
    是一种常见的数据组织形式,它采用动态分配内存的形式实现。需要可以用new分配内存空间,不需要用delete将已分配的空间释放,不会造成内存空间的浪费。 A 从逻辑结构来看 A-1. 数组必须事先定义固定...
  • 链表数组(转)

    千次阅读 2012-08-29 14:13:15
    链表和数组一样是一种数据结构。   数组是将元素在内存中连续存放,由于每个元素占用内存相同,所以可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个...
  • 静态链表 C实现

    万次阅读 多人点赞 2013-09-27 14:38:18
    0:实现静态链表的方法 定义一个较大的结构数组作为备用结点空间(即存储池)。申请结点,每个结点应含有两个域:data域和cursor域。data域用来存放结点的数据信息,此时的cursor域不在是指针而是游标指示器,...
  • 静态链表 c语言实现

    2016-12-28 15:05:34
    转载自:http://blog.csdn.net/jiuyueguang/article/details/12090569 目录(?)[+] ...0:实现静态链表的方法 定义一个较大的结构数组作为备用结点空间(即存储池)。申请结点,每个结点应含有两个域:
  • python 实现静态链表

    2021-07-10 08:21:09
    静态链表在没有指针的语言中用数组实现,用一组地址连续的存储单元来存放数据(数组就是顺序表),用数组的下标来代替地址,要理解静态链表,你就先要把数组看做一个内存空间,数组下标就是这个空间的地址。...
  • 以前学习的各种链表都是由指针实现的,链表中结点的分配和回收(即释放)都是由系统提供的标准函数malloc和free动态实现的,故称之为动态链表。... 用游标实现链表,其方法是:定义一个较大的结构数组作为
  • 以前学习的各种链表都是由指针实现的,链表中结点的分配和回收(即释放)都是由系统提供的标准函数malloc和free动态实现的,故称之为动态链表。... 用游标实现链表,其方法是:定义一个较大的结构数组作为
  • 静态链表解析

    2021-04-24 09:57:05
    对于需要实现链表结构,但又不支持指针的语言(如:Basic、Fortran),则可以通过采用数组结构模拟出链表来,相比采用动态内存分配的链表结构,该结构称为静态链表(也称为 “游标实现法” )。 1 结构 首先,涉及...
  • 静态数组实现队列(C语言)

    千次阅读 2009-06-22 17:54:00
    概念:队列,FIFO(First in, first out),排队买票,先排的先买,插队的拉出去TJJ实现:用静态数组实现,比起用链表实现来说,短小精悍,但无法动态更改队列的大小。基本原理:两个变量front rear,作为数组的的...
  • 数组代替指针来描述链表叫做静态链表静态链表是为了给没有指针的高级语言设计的一种实现单链表能力的方法。首先让数组的元素都由两个数据域组成,data和cur,即数组的每一个下标都对应一个data和一个cur。 2....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 49,482
精华内容 19,792
关键字:

当静态链表采用数组实现时