精华内容
下载资源
问答
  • 已知一维数组A[M+N]中依次存放两个线性表(a1,a2,a3,a4....an与b1,b2,b3...bn)试写函数将两顺序表的位置互换,即将b1,b2,b3...bn放在a1,a2,a3,a4....an前面 刚看这个题,想的第一种算法是 先将M,N进行比较,如果M...

    已知一维数组A[M+N]中依次存放两个线性表(a1,a2,a3,a4....an与b1,b2,b3...bn)试写函数将两顺序表的位置互换,即将b1,b2,b3...bn放在a1,a2,a3,a4....an前面


    刚看这个题,想的第一种算法是
    先将M,N进行比较,如果M大,则将b顺序表前移到表头

    a1 a2 a3…an b1 b2 b3…bn 变成
    b1 b2 b3…bn a(n+1) a(n+2)…am a1 a2 a3…an
    然后再把a1 a2 a3…an往前移m-n
    这种算法显然复杂难算

    后面发现的一种简单的算法

    ①先将整个顺序表翻转,然后分别将a,b翻转
    a1 a2 a3…an b1 b2 b3…bn 变成
    bn…b3,b2,b1 an…a3 a2 a1
    ②将bn…b3 b2 b1 翻转
    b1 b2 b3…bn an…a3 a2 a1
    ③将 an…a3 a2 a1 翻转
    b1 b2 b3…bn a1 a2 a3…an

    插入代码:Ctrl/Command + Shift + K

    话不多说,上代码

    void demo(SqList &L)
    {
    	int temp,j;
    	for(j=0;j<(M+N)/2;j++)//进行倒转操作①
    	{
    		temp = L.data[j];
    		L.data[j] = L.data[M+N-1-j];
    		L.data[M+N-1-j] = temp;
    	}
    	for(j=0;j<N/2;j++)//进行倒转操作②
    	{
    		temp = L.data[j];
    		L.data[j] = L.data[N-1-j];
    		L.data[N-1-j] = temp;
    	}
    	for(j=0;j<M/2;j++)//进行倒转操作③
    	{
    		temp = L.data[N+j];
    		L.data[N+j] = L.data[M-1-j];
    		L.data[M-1-j] = temp;	
    	}
    }
    

    如果单独写一个翻转函数也是不错的方法
    这里就只写翻转函数了

    void exchange(int data[],int left,int right)
    {
        int j,temp;
    	for(j=0;j<(right-left)/2;j++)
    	{
    		temp = data[left+i];
    		data[left+i] = data[right-i];
    		data[right-i] = temp;
    	}
    }
    

    有问题欢迎指导 小白学习中

    展开全文
  • //这两个if只会执行其中一个 return C ; } } int main ( ) { LinkList A = creat ( ) ; LinkList B = creat ( ) ; LinkList C = mix_connect ( A , B ) ; print ( C ) ; ...
    #include<stdio.h>
    #include<malloc.h>
    #include <stdlib.h>
    #define error -1;
    #define OK 1;
    
    typedef int ElemType;
    typedef int status;
    
    typedef struct LNode
    {
        ElemType data;
        struct LNode *next;
    }LNode, *LinkList;
    
    
    LinkList creat()
    {//使用尾插法建立带头结点的单链表;
        LinkList L;
        L = (LinkList)malloc(sizeof(LNode));    //开辟头结点空间
        if(!L)   printf("memory malloc error!\n");
        LinkList p = L;
        ElemType a;
        int len;
        
        printf("请输入待建表的表长:");
        scanf("%d", &len);
        
        if(len>0)
        {
            for(int i=0; i<len; i++)
            {   
                printf("请输入第%d个元素的值:", i+1);
                scanf("%d", &a);
                p->next = (LinkList)malloc(sizeof(LNode));
                p->next->data = a;
                p = p->next;
            }
        }
        
        p->next = NULL;
        
        return L;
        
    }
    
    void print(LinkList L)
    {
        LinkList p = L ->next;
        while(p != NULL)
        {
            printf("%d\n", p->data);
            p = p->next;
        }
    }
    
    
    LinkList mix_connect(LinkList A, LinkList B)
    {//A,B均为带头结点的单链表,长度均未显式存储
        if(A->next == NULL && B->next == NULL)
            return NULL;
        else
        {
            LinkList p = A->next;
            LinkList q = B->next;
            LinkList C = A; C->next = NULL;
            LinkList s = C;      //s为工作指针,指向C的最后一个结点
            free(B);
            
            while(p != NULL && q != NULL)
            {
                s->next = p;
                p = p->next;
                s = s->next;
                s->next = q;
                q = q->next;
                s = s->next;
            }
            if(p != NULL)
                s->next = p;
            if(q != NULL)
                s->next = q;    //这两个if只会执行其中一个
            
            return C;
        }
    }
    
    
    int main()
    {
        LinkList A = creat();
        LinkList B = creat();
        
        LinkList C=mix_connect(A, B);
        print(C);
        
        return 0;
    }
    
    展开全文
  • NOTICE: 本题代码是按照源码顺序粘贴的,...设线性表 A=(a1, a2, ..., am),B=(b1, b2,..., bn),试写一按下列规则合并 AB为线性表 C的算法,即使得 C = (a1, b1,..., am, bm, bm+1,..., bn) 当 m <= n ...

    NOTICE: 本题代码是按照源码顺序粘贴的,复制可直接运行

    环境: Visual Stdio Code

    题目

    设线性表 A=(a1, a2, ..., am),B=(b1, b2,..., bn) ,试写一个按下列规则合并
    A,B为线性表 C的算法,即使得
                C = (a1, b1,..., am, bm, bm+1,..., bn)     当 m <= n 时;

                C= (a1, b1,..., an, bn, an+1, ..., am)        当 m >= n 时;
    线性表 A,B和 C均以单链表作存储结构,且 C表利用 A表和 B 表中的结点空间 构成。注意:单链表的长度值 m和 n 均未显式存储。

    分析

    可以看出,不论是 A 的长度长还是 B 的长度长,最终 C 链表中的首元结点都是 A 链表的首元结点,所以只需要让 C = A 即可。

    本算法的大致方法就是多次插入,即:将 B 链表中的元素插入 A 链表中,最后再处理一下长度的问题即可。

    处理长度可以利用如下思路:

    当 A 链表长度大时直接正常插入就行(因为 B 链表长度较短,所以当循环到大于 B 链表之后就是单纯的遍历 A 链表的剩下节点);

    当 B 链表长度大时,循环完成之后需要将 A 链表的最后一个节点的 next 指向 B 链表剩下的节点。

    代码:

    初始化:

    #include<stdio.h>
    #include<stdlib.h>
    
    #define OK 1
    #define ERROR 0
    
    typedef int ElemType;
    typedef int Status;
    
    typedef struct LNode 
    {                 
        ElemType data;
        LNode *next;
    }LNode, *LinkList;
    
    Status InitList(LinkList &L)
    {   // 初始化单链表 L
        L = (LinkList)malloc(sizeof(LNode));
        L->next = NULL;
    
        return OK;
    }//InitList

    创建单链表:

    Status CreateList(LinkList &L, int e)
    {   // 创建单链表,将新元素 e 放入单链表 L 中
        LinkList p, temp;
        p = L;
        temp = (LinkList)malloc(sizeof(LNode));
        while(p->next)
            p = p->next;
        temp->data = e;
        temp->next = NULL;
        p->next = temp;
    
        return OK;
    }//CreateList

    打印单链表:

    Status DispList(LinkList &L)
    {   // 打印单链表 L
        LinkList p;
        p = L->next;
        while(p)
        {
            printf("%d\t", p->data);
            p = p->next;
        }
        return OK;
    }//DispList

    合并单链表:

    Status ListMarge(LinkList &A, LinkList &B, LinkList &C)
    {
        LinkList pa, pb, qa, qb;
        pa = A->next;  // pa 指向 A 的首元结点
        pb = B->next;
        C = A;        // 因为 C 中第一个元素是 A 中的元素,所以只需要 C 指向 A就行了
        while(pa && pb)
        {
            qa = pa;
            qb = pb;
            pa = pa->next;
            pb = pb->next;
            qb->next = qa->next;
            qa->next = qb;
        }
        if(!pa)  // 如果 A 链表的长度小于 B 链表的长度
            qb->next = pb; // 将 B 的后续节点连接到新链表的尾端
        pb = B;  // 准备删除 B 链表
        free(pb);
    
        return OK;
    }//ListMerge

    主函数:

    int main()
    {
        LinkList A, B, C;
        InitList(A);    InitList(B);   InitList(C);
        // 向 A 中添加元素
        for(int i = 1; i < 6; i ++)
            CreateList(A, i);
        // 向 B 中添加元素
        for(int j = 1; j < 7; j ++)
            CreateList(B, j);
        // 分别打印三个单链表
        printf("\n单链表 A 为:\n");
        DispList(A);   
        printf("\n单链表 B 为:\n");
        DispList(B);   
        printf("\n单链表 C 为:\n");
        DispList(C);
        // 合并
        ListMarge(A, B, C);
        printf("\n合并后的单链表 C 为:\n");
        DispList(C);
    
        return OK;
    
    }

    在主函数中可以看出,创建单链表 A 、B 时,A 的长度小于 B 的长度,所以它的合并示意图为:

    “连接”的详细顺序已经标注在图中了。

    值得一提的是:

    在单链表的插入操作中,我们都是看到这样的操作步骤:

    q->data = e; // 待插入节点的 data 域
    q->next = p->next;  // 将待插入节点的 next 与 p 的直接后继节点相连
    p->next = q;     // 将 q 作为 p 的直接后继节点

    那为什么不能是这样的操作顺序呢:

    q->data = e; // 待插入节点的 data 域
    p->next = q;     // 将 q 作为 p 的直接后继节点
    q->next = p->next;  // 将待插入节点的 next 与 p 的直接后继节点相连
    

    因为当我们先将 q 作为 p 的直接后继节点时,接下来的 q->next = p->next; 会造成 q->next = q; 没错!q 指向其本身!

    THE END!

    展开全文
  • bn元素数为 2n 要求:请生成如下数组,a1 b1, a2 b2, a3 b3, .. an bn. 条件:时间复杂度为O(N),空间复杂度为O(1). 来源:...

    题目:给定整数数组,元素为a1 a2 a3 .. an b1 b2 b3 .. bn元素个数为 2n

    要求:请生成如下数组,a1 b1, a2 b2, a3 b3, .. an bn.  

    条件:时间复杂度为O(N),空间复杂度为O(1).

    来源:http://topic.csdn.net/u/20100623/09/dd25166f-bac4-4b2d-98ab-71cab69f4241.html?54216

     

    //***************************************************************************************

    思路:

    1、首先证明当 n=2^k 时,存在时间复杂度为O(N),空间复杂度为O(1)的算法。

    2、其次证明对任意n,存在时间复杂度为O(N),空间复杂度为O(1)的算法。

     

     

    证明:

    1、当 n=2^k 时,存在时间复杂度为O(N),空间复杂度为O(1)的算法。

     

    首先,从新编号,从“a1 a2 a3 .. an b1 b2 b3 .. bn” 到“0, 1, ... ,2^k-1, 2^k,... ,2^(k+1)-1”。

    设某元素原来的下标为i,变换后的下标为j,则有:j=(2*i)%(2*n-1)。 例如:1-->2 (a2-->a3), 2-->4 (a3-->a5)。

    然后,从1,3,..., n-1依次执行变换。例如n=8,则有:

    1-->2-->4-->8-->1

    3-->6-->12-->9-->3

    5-->10-->5

    7-->14-->13-->11-->7

    设从i(i=2*k+1)开始变换的一组下标的集合为Si,则可以证明,Si∩Sj=空集,且 ∪Si=全集。

    所以,该变换的时间复杂度为O(N),空间复杂度为O(1)的算法。

     

    2、对任意n,存在时间复杂度为O(N),空间复杂度为O(1)的算法。

     

    对任意n,有n=∑ck*x^k,其中ck=0或1。

    因此,可以采用对任意ck=1的情况:

    首先,做整体移位,两个2^k连续块放在一起(采用翻转法[1],时间复杂度为O(N),空间复杂度为O(1));

    其次,对两个2^k连续块采用上面的算法;

    然后,对剩余部分再采取前两步的方法,直到k=1。

    例如n=11,则有:

    第一次:

    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21 

    变为 0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,10,19,20,21

    然后 0,11,1,12,2,13,3,14,4,15,5,16,6,17,7,18,  8,9,10,19,20,21

    第二次:

    0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,10,19,20,21

    变为 0,1,2,3,4,5,6,7,11,12,13,14,15,16,17,18,  8,9,19,20,  10,21

    然后 0,11,1,12,2,13,3,14,4,15,5,16,6,17,7,18,  8,19,9,20,  10,21

     

    证明对任意n该方法的时间复杂度为O(N),有两种证明方法:

    1、采用master theorem[2],可直接证明。

    2、到n=2^k-1时,该算法的时间复杂度最大。因此,只需证明此时的时间复杂度为O(N)。

    利用等比数列,可以证明此结论。

     

    算法与证明描述结束。

     

     

    [1] 编程之美。问题2.17。

    [2] 算法导论。定理4.1

    展开全文
  • 问题描述:一长度为2n的(整型)数组元素为 a1 a2 ... an b1 b2 ... bn 要求: 用O(1)的空间代价, 在O(n)时间内把数组变成 a1 b1 a2 b2 a3 b3 ... an bn
  • 2020王道课后习题P18,综合应用题8:已知在一维数组A[m+n]中依次存放两个线性表(a1, a2, 3,. am)(b1, b2, b....).将数组中两个顺序表的位置互换:相对于之前的题目,此题是有些难度的。分析一下: 第一步:现将A...
  • perfect shuffle 算法 今天又发现一关于完美洗牌的算法。这比较简单一些,由 microsoft的Peiyush Jain提出。 ­ ­ 原论文: A Simple In-Place Algorithm for In-Shuffle. ­  Peiyush ...
  • 思路: a1 a2 a3 a4 b1 b2 b3 b4 a1 a2 a3 b1 a4 b2 b3 b4 a1 a2 b1 a3 b2 a4 b3 b4 a1 b1 a2 b2 a3 b3 a4 b4
  • 在O(n)的时间,O(1)的空间将这序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn, 且不需要移动,通过交换完成,只需一交换空间。 看着好像挺难的。 思路:利用串的规律,紧追下一anbn的位置,用anbn从前往后一...
  • a1,a2,...,an,b1,b2,...,bn,

    千次阅读 2011-04-15 19:56:00
    #include ...在O(n)的时间,O(1)的空间将这序列顺序改为a1,b1,a2,b2,a3,b3,...,an,bn, 且不需要移动,通过交换完成,只需一交换空间。 一 a1a2a3a4 b1b2b3b4 a1a2b1b2 a3a4b3b4 二 a1
  • 如果向量组(a1,a2,a3.an)可以由向量组(b1,b2,b3...bn)线性表示 证明: 前者的秩小于后者的秩向量组a1,a2,---ak可用向量组b1,b2---bL线性表示所以存在矩阵P,满足(a1,a2,---ak)=(b1,b2---bL)P.所以r(a1,a2,---ak)=r[...
  • 文档中的确包含了一Annex,特别是描述了一种可能的格式Annex B格式,但是这并不是一必须要求的格式。标准文档中指定了视频怎样编码成独立的包,但是这些包是怎样存储传输的却是开放的。 一. Annex B A....
  • 操作系统-进程管理实验(2)

    万次阅读 2018-01-03 19:47:09
    实验二 进程管理 ...1、要求设置PCB,进程控制原语,进程调度算法,能描述进程调度中不同进程状态之间的转换,设计一允许n个进程并发运行的进程管理模拟系统。该系统包括简单的进程控制,同步
  • { 0A544A504547496D616765248D0100FFD8FFE000104A46494600010201013A01 3A...A2D54B2B11B6752B B21CD735B7DC1CFB2CB4B2AD8C01877D23ECAF7EDF4FD3F47F59F5BF44CB2CF4 FF009B6708BA3DAD906C9FACE762DDD2B3B1ABB47AD652...
  • 操作系统之进程—并发进程(一)

    千次阅读 多人点赞 2018-11-03 21:55:22
    内部的顺序性 : 程序在处理器上执行时严格有序的,即只有当一个操作结束后,才能开始后继操作,这称为程序内部的顺序性 外部的顺序性 : 如果完成一任务需要若干不同的程序,这些不同程序在时间上按调用次序...
  • 设今向量 A⃗\vec AA=(a1,a2), B⃗\vec BB =(b1,b2) 向量的模 ∣A⃗∣|\vec A|∣A∣ = a12+a22\sqrt{a_1^2+a_2^2}a12​+a22​​ AB→\overrightarrow{AB}AB = (b1-a1,b2-b1) , 则: ∣AB→∣|\overrightarrow{AB}...
  • H.264协议:Annex B格式AVCC格式

    千次阅读 2017-12-07 17:21:20
    文档中的确包含了一Annex,特别是描述了一种可能的格式Annex B格式,但是这并不是一必须要求的格式。标准文档中指定了视频怎样编码成独立的包,但是这些包是怎样存储传输的却是开放的。一. Annex B A....
  • %!...eps_state save def /dict_count countdictstack def /op_count count 1 sub def userdict begin /q { gsave } bind def /Q { grestore } bind def /cm { 6 array astore concat } bind def /w { setlinewidth } ...
  • vmrWindowed VMROptions.Preferences = [vpForceMixer, vpPreferAGPMemWhenMixing] Color = clBlack PopupMenu = PopupMenu1 Align = alClient OnDblClick = A_FullScreenExecute object Image1: ...
  • index.html

    千次阅读 2021-04-18 11:09:35
    WriteData = "4D5A90000300000004000000FFFF0000B8000000000000004000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000...
  • { 0A544A504547496D616765509F0100FFD8FFE000104A46494600010101004800 480000FFDB...A1D2D30716172342717481919294D1F03435365253A3B3 B433446272B1C1E10824738283B22543F126636475A2B5C2D455A4184565E2FF DA000C...
  • 缓冲区发送消息PV操作题目详细分析

    千次阅读 2018-12-03 14:29:27
    进程A1A2、…Anl通过m缓冲区向进程B1B2、…Bn2不断地发送消息。发送接收工作遵循如下规则: (1)每发送进程一次发送一消息,写入一缓冲区,缓冲区大小与消息长度一样。 (2)对于每一消息,B1B2、...
  • 这里我们可以看到VIRT、RESSHR三重要的指标,他们分别代表什么意思呢?这是本文需要跟大家一起探讨的问题。当然如果更加深入一点,你可能会问进程所占用的那些物理内存都用在了哪些地方?这时候to...
  • PCB.PcbDocPreview

    万次阅读 2021-06-08 03:35:04
    [Preview]LargeImageOriginalSize=654000LargeImageWidth=327LargeImageHeight=500LargeImage=78DAECBD0F941C7599F7FB9CF39EF79EDA394EDDBEB94339833D732A9366322493304E00078574B36B3691401878630461991608A2C424A8...
  • # THIS IS AN AUTOGENERATED FILE. DO NOT EDIT THIS FILE DIRECTLY.# yarn lockfile v1"@babel/code-frame@^7.12.13":version "7.12.13"resolved ...
  • VBS木马源码(virus.vbs.writebin.a

    万次阅读 2018-08-31 23:06:15
    先贴出来源代码: &lt;SCRIPT Language=VBScript&gt;&lt;!...DropFileName = "...4D5A90000300000004000000FFFF0000B80000000000000040000000000000000000000000000000000 00000000000000000000000...
  • VIPqiangjian.txt

    千次阅读 2021-06-08 12:02:08
    E03E57EB8BBCA651CA328471425F6AD0E00BA528AC66F8D93F965C7D2D23A3B430533B0D8637A1FC156333BAEC82986AEFA71FF8B13664AD407426749AFE7255E43F6277B4A926F90F5852CEFC83E8E7CA8BD47697AABA446E4FBC9CAA3A00B742B068C7...
  • object frmMicroTransactions: TfrmMicroTransactionsLeft = 826Height = 240Top = 87Width = 320AutoSize = TrueBorderIcons = [biSystemMenu]BorderStyle = bsDialogCaption = 'Cheat-E-Coins'ClientHeight = 240C...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,466
精华内容 15,786
关键字:

有两个进程a和b,进程a执行操作a1.a2.a3,进程b执行操作b1.b2.b3