精华内容
下载资源
问答
  • //将两个有序链表并为一个有序链表算法,该程序也可以cFree环境运行。 // c1.h (程序名) #include<string.h> #include<ctype.h> #include<malloc.h> // malloc()等 #include<limits.h> //...
    //将两个有序链表并为一个有序链表算法,该程序也可以cFree环境运行。
    // c1.h (程序名)
    #include<string.h>
    #include<ctype.h>
    #include<malloc.h> // malloc()等
    #include<limits.h> // INT_MAX等
    #include<stdio.h> // EOF(=^Z或F6),NULL
    #include<stdlib.h> // atoi()
    //#include<io.h> // eof()
    #include<math.h> // floor(),ceil(),abs()
    //#include<process.h> // exit()
    
     
    
    // 函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    // #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行,退出时用,0正常结束,非0非正常终止
    typedef int Status; // Status是函数的类型,其值是函数结果状态代码,如OK等
    typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
    
     
    
    typedef int ElemType;
    
     
    
    
    // c2-2.h 线性表的单链表存储结构
    typedef struct LNode
    {
    ElemType data;
    struct LNode *next;
    }LNode,*LinkList;;
    // 另一种定义LinkList的方法
    
     
    // bo2-2.cpp 单链表线性表(存储结构由c2-2.h定义)的基本操作(12个)
    Status InitList(LinkList &L)
    { // 操作结果:构造一个空的线性表L
    L=(LinkList)malloc(sizeof(LNode)); // 产生头结点,并使L指向此头结点
    if(!L) // 存储分配失败
    exit(OVERFLOW);
    L->next=NULL; // 指针域为空
    return OK;
    }
    
     
    
    Status DestroyList(LinkList &L)
    { // 初始条件:线性表L已存在。操作结果:销毁线性表L
    LinkList q;
    while(L)
    {
    q=L->next;
    free(L);
    L=q;
    }
    return OK;
    }
    
     
    
    Status ClearList(LinkList L) // 不改变L
    { // 初始条件:线性表L已存在。操作结果:将L重置为空表
    LinkList p,q;
    p=L->next; // p指向第一个结点
    while(p) // 没到表尾
    {
    q=p->next;
    free(p);
    p=q;
    }
    L->next=NULL; // 头结点指针域为空
    return OK;
    }
    
     
    
    Status ListEmpty(LinkList L)
    { // 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE
    if(L->next) // 非空
    return FALSE;
    else
    return TRUE;
    }
    
     
    
    int ListLength(LinkList L)
    { // 初始条件:线性表L已存在。操作结果:返回L中数据元素个数
    int i=0;
    LinkList p=L->next; // p指向第一个结点
    while(p) // 没到表尾
    {
    i++;
    p=p->next;
    }
    return i;
    }
    
     
    
    Status GetElem(LinkList L,int i,ElemType &e) // 比较j和i并后指移指针p算法
    { // L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
    int j=1; // j为计数器
    LinkList p=L->next; // p指向第一个结点
    while(p&&j<i) // 顺指针向后查找,直到p指向第i个元素或p为空
    {
    p=p->next;
    j++;
    }
    if(!p||j>i) // 第i个元素不存在
    return ERROR;
    e=p->data; // 取第i个元素
    return OK;
    }
    
     
    
    int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
    { // 初始条件: 线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)
    // 操作结果: 返回L中第1个与e满足关系compare()的数据元素的位序。
    // 若这样的数据元素不存在,则返回值为0
    int i=0;
    LinkList p=L->next;
    while(p)
    {
    i++;
    if(compare(p->data,e)) // 找到这样的数据元素
    return i;
    p=p->next;
    }
    return 0;
    }
    
     
    
    Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
    { // 初始条件: 线性表L已存在
    // 操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,
    // 返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE
    LinkList q,p=L->next; // p指向第一个结点
    while(p->next) // p所指结点有后继
    {
    q=p->next; // q为p的后继
    if(q->data==cur_e)
    {
    pre_e=p->data;
    return OK;
    }
    p=q; // p向后移
    }
    return INFEASIBLE;
    }
    
     
    
    Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
    { // 初始条件:线性表L已存在
    // 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,
    // 返回OK;否则操作失败,next_e无定义,返回INFEASIBLE
    LinkList p=L->next; // p指向第一个结点
    while(p->next) // p所指结点有后继
    {
    if(p->data==cur_e)
    {
    next_e=p->next->data;
    return OK;
    }
    p=p->next;
    }
    return INFEASIBLE;
    }
    
     
    
    Status ListInsert(LinkList L,int i,ElemType e) // 算法:在带头结点的单链表线性表L中,删除第i个元素,并由e返回其值。不改变L
    { // 在带头结点的单链线性表L中第i个位置之前插入元素e
    int j=0;
    LinkList p=L,s;
    while(p&&j<i-1) // 寻找第i-1个结点
    {
    p=p->next;
    j++;
    }
    if(!p||j>i-1) // i小于1或者大于表长
    return ERROR;
    s=(LinkList)malloc(sizeof(LNode)); // 生成新结点
    s->data=e; // 插入L中
    s->next=p->next;
    p->next=s;
    return OK;
    }
    
     
    
    Status ListDelete(LinkList L,int i,ElemType &e) // 算法:从空表的初始状态起,依次建立各元素结点,并逐个插入链表,不改变L
    { // 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
    int j=0;
    LinkList p=L,q;
    while(p->next&&j<i-1) // 寻找第i个结点,并令p指向其前趋
    {
    p=p->next;
    j++;
    }
    if(!p->next||j>i-1) // 删除位置不合理
    return ERROR;
    q=p->next; // 删除并释放结点
    p->next=q->next;
    e=q->data;
    free(q);
    return OK;
    }
    
     
    
    Status ListTraverse(LinkList L,void(*vi)(ElemType))
    // vi的形参类型为ElemType,与bo2-1.cpp中相应函数的形参类型ElemType&不同
    { // 初始条件:线性表L已存在
    // 操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败
    LinkList p=L->next;
    while(p)
    {
    vi(p->data);
    p=p->next;
    }
    printf("\n");
    return OK;
    }
    
     
    
    void CreateList(LinkList &L,int n) // 算法:从表尾到表头逆向建立单链表的算法,其时间复杂度为O(n)
    { // 逆位序(插在表头)输入n个元素的值,建立带表头结构的单链线性表L
    int i;
    LinkList p;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL; // 先建立一个带头结点的单链表
    printf("请输入%d个数据\n",n);
    for(i=n;i>0;--i)
    {
    p=(LinkList)malloc(sizeof(LNode)); // 生成新结点
    scanf("%d",&p->data); // 输入元素值
    p->next=L->next; // 插入到表头
    L->next=p;
    }
    }
    
     
    
    void CreateList2(LinkList &L,int n)
    { // 正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表
    int i;
    LinkList p,q;
    L=(LinkList)malloc(sizeof(LNode)); // 生成头结点
    L->next=NULL;
    q=L;
    printf("请输入%d个数据\n",n);
    
    for(i=1;i<=n;i++)
    {
    p=(LinkList)malloc(sizeof(LNode));
    scanf("%d",&p->data);
    q->next=p;
    q=q->next;
    }
    p->next=NULL;
    }
    
     
    
    void MergeList(LinkList La,LinkList &Lb,LinkList &Lc)// 算法
    { // 已知单链线性表La和Lb的元素按值非递减排列。
    // 归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列
    LinkList pa=La->next,pb=Lb->next,pc;
    Lc=pc=La; // 用La的头结点作为Lc的头结点
    while(pa&&pb)
    if(pa->data<=pb->data)
    {
    pc->next=pa;
    pc=pa;
    pa=pa->next;
    }
    else
    {
    pc->next=pb;
    pc=pb;
    pb=pb->next;
    }
    pc->next=pa?pa:pb; // 插入剩余段
    free(Lb); // 释放Lb的头结点
    Lb=NULL;
    }
    
     
    
    void visit(ElemType c) // ListTraverse()调用的函数(类型要一致)
    {
    printf("%d ",c);
    
     
    
    }
    
     
    
    int main()
    {
    setbuf(stdout,NULL);
    int n=5;
    LinkList La,Lb,Lc;
    printf("按非递减顺序, ");
    CreateList2(La,n); // 正位序输入n个元素的值
    printf("La="); // 输出链表La的内容
    ListTraverse(La,visit);
    printf("按非递增顺序, ");
    CreateList(Lb,n); // 逆位序输入n个元素的值
    printf("Lb="); // 输出链表Lb的内容
    ListTraverse(Lb,visit);
    MergeList(La,Lb,Lc); // 按非递减顺序归并La和Lb,得到新表Lc
    printf("Lc="); // 输出链表Lc的内容
    ListTraverse(Lc,visit);
    }


     

    1.线性链表

    线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素ai与其直接后续数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像,称为结点(node)。它包括两个域:其中存储数据元素的信息域称为数据域;存储直接后继的存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个结点链结成一个链表,即为线性表

    (a1,a2,…..,an)

     

    的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表。

    用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,因此,这种存储结构为非顺序映像或链式映像。单链表可由头指针惟一确定,在C语言中可用“结构指针”来描述:

    typedef struct LNode{

        ElemType data;

        struct LNode *next;

     

    } LNode,*LinkList;

     

    2.循环链表

    循环链表(circular linked list)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。从表中任一结点出发均可找到表中其他结点。

    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。但有的时候,若在循环链表中设立尾指针而不设头指针,可使某些操作简化。

    例如:将两个线性表合并成一个表时,仅需将一个表的表尾和另一个表的表头相接。

     

    3.双向链表

    以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表头指针出发。换句话说,在单链表中,NextElem的执行时间为O(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表(double linked list),即在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋,在C语言中的可描述如下:

    typedef struct DuLNode{

        ElemType data;

        struct DuLNode *prior;

        struct DuLNode *next;

     

    } DuLNode,*DuLinkList;

     

     

    演示1:

    算法:将两个有序链表并为一个有序链表(该程序的代码,可以放在cFree环境中运行) 

      假设头指针为La和Lb是单链表分别线性表La和Lb的存储结构,现要归并La和Lb得到单链表Lc,按照MergeList的思想,需设立3个指针pa,pb和pc,其中pa和pb分别指向La表和Lb表中当前待比较插入的结点,而pc指向Lc表中当前最后一个结点,若pa->data≤pb->data,则将pa所指结点链接到pc所指结点之后,否则将pb所指结点链接到pc所指结点之后。显然,指针的初始状态为:当La和Lb为非空表时,pa和pb分别指向La和Lb表中的第一个结点,否则为空;pc指向空表Lc中的头结点。由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个为空时,说明有一个表的元素已归并完,则只要将另一个表的剩余段链接在pc所指结点之后即可。

    提示:在归并两个链表为一个链表时,不需要另建新表的结点空间,而只需将原来两个链表中结点之间的关系解除,重新按元素值非递减的关系将所有结点链接成一个链表即可。

     

    1.线性链表

    线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。因此,为了表示每个数据元素ai与其直接后续数据元素ai+1之间的逻辑关系,对数据元素ai来说,除了存储其本身的信息之外,还需存储一个指示直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像,称为结点(node)。它包括两个域:其中存储数据元素的信息域称为数据域;存储直接后继的存储位置的域称为指针域。指针域中存储的信息称为指针或链。n个结点链结成一个链表,即为线性表

    (a1,a2,…..,an)

     

    的链式存储结构。又由于此链表的每个结点中只包含一个指针域,故又称线性链表或单链表。

    用线性链表表示线性表时,数据元素之间的逻辑关系是由结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像,则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,因此,这种存储结构为非顺序映像或链式映像。单链表可由头指针惟一确定,在C语言中可用“结构指针”来描述:

    typedef struct LNode{

        ElemType data;

        struct LNode *next;

     

    } LNode,*LinkList;

     

    2.循环链表

    循环链表(circular linked list)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。从表中任一结点出发均可找到表中其他结点。

    循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针。但有的时候,若在循环链表中设立尾指针而不设头指针,可使某些操作简化。

    例如:将两个线性表合并成一个表时,仅需将一个表的表尾和另一个表的表头相接。

     

    3.双向链表

    以上讨论的链式存储结构的结点中只有一个指示直接后继的指针域,由此,从某个结点出发只能顺指针往后寻查其他结点。若要寻查结点的直接前趋,则需从表头指针出发。换句话说,在单链表中,NextElem的执行时间为O(1),而PriorElem的执行时间为O(n)。为克服单链表这种单向性的缺点,可利用双向链表(double linked list),即在双向链表的结点中有两个指针域,其一指向直接后继,另一指向直接前趋,在C语言中的可描述如下:

    typedef struct DuLNode{

        ElemType data;

        struct DuLNode *prior;

        struct DuLNode *next;

     

    } DuLNode,*DuLinkList;

     

     

    演示1:

    算法:将两个有序链表并为一个有序链表(该程序的代码,可以放在cFree环境中运行) 

      假设头指针为La和Lb是单链表分别线性表La和Lb的存储结构,现要归并La和Lb得到单链表Lc,按照MergeList的思想,需设立3个指针pa,pb和pc,其中pa和pb分别指向La表和Lb表中当前待比较插入的结点,而pc指向Lc表中当前最后一个结点,若pa->data≤pb->data,则将pa所指结点链接到pc所指结点之后,否则将pb所指结点链接到pc所指结点之后。显然,指针的初始状态为:当La和Lb为非空表时,pa和pb分别指向La和Lb表中的第一个结点,否则为空;pc指向空表Lc中的头结点。由于链表的长度为隐含的,则第一个循环执行的条件是pa和pb皆非空,当其中一个为空时,说明有一个表的元素已归并完,则只要将另一个表的剩余段链接在pc所指结点之后即可。

    提示:在归并两个链表为一个链表时,不需要另建新表的结点空间,而只需将原来两个链表中结点之间的关系解除,重新按元素值非递减的关系将所有结点链接成一个链表即可。

    展开全文
  •  将a[0……n-1]看成是n个长度为1的有序序列,然后进行两两归并,得到n/2(向上取整)个长度为2(最后一个有序序列的长度可能1)的有序序列,再进行两两归并,得到n/4(向上取整)个长度为4(最后一个有序序列的长度...

    归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表,即二路归并

    二路归并的排序基本思想是:

           将a[0……n-1]看成是n个长度为1的有序序列,然后进行两两归并,得到n/2(向上取整)个长度为2(最后一个有序序列的长度可能为1)的有序序列,再进行两两归并,得到n/4(向上取整)个长度为4(最后一个有序序列的长度可能小于4)的有序序列……直到得到一个长度为n的有序序列

    归并排序每趟产生的有序区只是局部有序的,也就是说在最后一趟排序结束前,所有元素并不一定归位了

    每次从两个段中取出一个元素进行关键字的比较,将较小者放入c[ ]中,最后将各段余下的部分直接复制到c[ ]中

    #include<stdio.h>
    #include<iostream>
    using namespace std;
    //a[]、b[]为需要合并的两个数组,c为合并后的新数组,n为a[]的长度,m为b[]的长度
    void merge(int a[],int b[],int c[],int n,int m){
    	int i=0,j=0,k=0;//i为a[]的下标,j为b[]的下标,k为c[]的下标	
    	//在a[]和b[]均未扫描完时循环
    	while(i<n && j<m){
    		if(a[i]<=b[j])
    		   c[k++]=a[i++];
    		else
    		   c[k++]=b[j++];
    	}
    	//如果a[]还有剩余,则将余下部分赋值过去
    	while(i<n){
    	   c[k++]=a[i++];
    	}
    	//如果b[]还有剩余,则将余下部分赋值过去
    	while(j<m){
    	   c[k++]=b[j++];
    	}
    }
    int main(){
      int n,m;//n为a[]的长度,m为b[]的长度
       //初始化
      //数组a[]
      cout<<"n:";
      cin>>n;
      int *a=new int[n];
      cout<<"输入"<<n<<"个数的第一个有序列表:";
      for(int i=0;i<n;i++){
         cin>>a[i];
      }
      //数组b[]
      cout<<"m:";
      cin>>m;
      int *b=new int(m);
      cout<<"输入"<<m<<"个数的第二个有序列表:";
      for(int i=0;i<m;i++){
         cin>>b[i];
      }
      int *c=new int(n+m);//c为合并后的数组
     //归并两个有序列表
      merge(a,b,c,n,m);
      //输出
      cout<<"合并后为:"; 
      for(int i=0;i<n+m;i++){
        cout<<c[i]<<" ";
      }
      cout<<endl;
    }

     

    展开全文
  • 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。中允许有重复的数据。 void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )...

    将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

    void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) 
    {//合并链表La和Lb,合并后的新表使用头指针Lc指向
      pa=La->next;  pb=Lb->next; 
      //pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点
      Lc=pc=La; //用La的头结点作为Lc的头结点 
      Lc->next=NULL;
      while(pa||pb )
    {//只要存在一个非空表,用q指向待摘取的元素
        if(!pa)  {
    	q=pb;
    	pb=pb->next;
    	}
    //La表为空,用q指向pb,pb指针后移
        else if(!pb)  {
    	q=pa;  
    	pa=pa->next;
    	} 
    //Lb表为空,用q指向pa,pa指针后移
        else if(pa->data<=pb->data)  {
    	q=pa;  
    	pa=pa->next;
    	}
    //取较小者(包括相等)La中的元素,用q指向pa,pa指针后移
        else {
    	q=pb;  
    	pb=pb->next;
    	}
    //取较小者Lb中的元素,用q指向pb,pb指针后移
         q->next = Lc->next; 
    	  Lc->next = q;   
    //将q指向的结点插在Lc 表的表头结点之后
        }
        delete Lb;             //释放Lb的头结点
    } 


    展开全文
  •  写一个函数SortedMerge函数,该函数有两个参数,都是递增的链表,函数的功能就是合并这两个递增的链表为一个递增的链表,SortedMerge的返回值是新的链表。新链表由前两个链表按元素递增顺序合并而成,也就是说它...
    问题定义:
            写一个函数SortedMerge函数,该函数有两个参数,都是递增的链表,函数的功能就是合并这两个递增的链表为一个递增的链表,SortedMerge的返回值是新的链表。新链表由前两个链表按元素递增顺序合并而成,也就是说它不会创建新的元素。
    比如:这里有两个链表,分别是
    list1: 5->10->15
    list2: 2->3->20
    SortedMerge函数返回一个指向新链表的指针,新链表应该是如下这样的:2->3->5->10->15->20

        程序需要考虑如下情况:两个链表(函数参数)都有可能为空,也可能其中一个链表已经遍历完了,另一个链表还有很多元素。


    使用递归:

     合并操作是非常适合用递归来完成的一类操作,递归实现将会比迭代实现更加清晰且易于理解。尽管如此,你可能也不愿意使用递归来实现这个操作,因为递归方法所使用的栈空间与链表的长度成正比。
    /*Using Recursion*/  
    struct node* SortedMerge(struct node* a, struct node* b)  
    {  
        struct node* result = NULL;  
          
        /*Base cases*/  
        if(a == NULL)  
            return (b);  
        else if(b == NULL)  
            return (a);  
      
        /*Pick either a or b, and recur */  
        if(a->data <= b->data)  
        {  
            result = a;  
            result->next = SortedMerge(a->next, b);  
        }  
        else  
        {  
            result = b;  
            result->next = SortedMerge(a, b->next);  
        }  
        return (result);  
    }  


    展开全文
  • 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。中不允许有重复的数据。 #include #include typedef struct list { int data; struct...
  • 将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。中允许有重复的数据。 #include #include typedef struct list { int data; ...
  • = nil { //node1当前节点的值时把node1接在 current的后面并将node1指针往后移,node2类似 if node1.Data 某一个为空时,直接把另一个链表续在current指针之后 if node1 == nil { current.Next = node2 } if ...
  • 问题描述:将两个有序(升序)表合并成一个新的有序表,并由函数返回结果顺序表。分析:首先,按顺序不断取下两个顺序表表头较小的节点存入新的顺序表中。然后,看哪个表还有剩余,将剩下的部分加到新的顺序表后面。...
  • 将12数画成完全二叉树,第层有1、第二次2、第三层4,第四层只有5。 二分查找时: 第层需要比较1次 ...则平均查找长度:(1+2*2+3*4+4*5)/12 = 37/12 = 3.0833 即 A、3.1 ...
  • 题目:设计算法将两个有序表合并成一个新的有序表 思想:双指针比较,头插法进入链表C 代码展示: void Merge(A a,B b,LinkList &L) { int i = 0; int j = 0; while(i<a.length && j<b.length)...
  • 1. 在每一个链表中取出第一个值,然后把它们放在一个大小N的数组里,然后把这个数组当成heap建成小(大)根堆。此步骤的时间复杂度O(N):N个数构建一个堆的复杂度是O(N) 2. 取出堆中的最小值(也是数组的第一个值)...
  • 最坏的情况就是交叉的...则楼上所给的第一个例子:第一步:1和2比,1小作为新节点,p移至3。第二步,3和2比,2小作为新节点,q移至4。第三步,3和4比,3小,p移至5。第四步,5和4比,4小,q移至6。第五步,5和6比,...
  • 将两个有序顺序表合并为一个新的有序表,并由函数返回结果顺序表。实际过程中应该不断取下两个顺序表表头较小的结点存在新的顺序表中,然后,将其中某个表中的剩余数据直接加到新的顺序表后面。 二 代码实现 /*...
  • 最多的比较次数是当两个有序表的数据刚好是插空顺序的时候 比如, 1 3 5 2 4 6 设两个指针分别p.q。 先把第二个序列中的第一个元素2和第一个序列依次比较,需要比较2次(和1,3比较),第二个元素4需要比较2次...
  • 有序表

    万次阅读 2018-03-03 10:25:05
    有序表的定义所谓有序表,是指这样的线性表,其中所有元素以递增或递减方式有序排列。为了简单,假设有序表元素是以递增方式排列。从中看到,有序表和线性表中元素之间的逻辑关系相同,其区别是运算实现的不同。...
  • 2020王道课后习题P18,综合应用题7:将两个有序的顺序合并为一个新的有序的顺序。算是一个经典算法了,我辈这种就没法改写了,就是直接套下来的,毕竟是抱着各位大佬的大腿,那就看代码,还是VS2013中实现的: ...
  • 有序表的顺序查找分析

    千次阅读 多人点赞 2016-10-24 15:41:24
    一般线性表的顺序查找,有序表的二分查找,基于索引的分块查找等都是有独特特征的查找方式,但是有种查找夹在一般线性表和有序下的二分查找中间,很容易被忽视,因此提出来单独讨论。这查找就是:有序表的顺序...
  • 1.若对表中元素先进行排序(字典序),构成有序表,并求其在等概率的情况下,对此有序表查找成功时的平均查找长度; 2.按表中元素的顺序依次插入生成颗二叉排序树(初始空),并求其在等概率的情况下...
  • 合并两个有序表

    千次阅读 2018-01-28 21:48:22
    如有有序表A,B: A:1 2 4 5 5 B:2 3 3 6 7 1.开始 i 指向 A的开头元素(即1),同理 j 指向 B开头元素(2) 2.A[i] 和 B[j] 中对比,选较小的放入新表C中 #include #include #define LIST_INIT_S
  • 有序表查找

    千次阅读 2017-11-09 12:35:59
    有序表的定义  有序表:对于以数组方式存储的数据,如果已经按其关键字值的大小顺序排列好,则称为有序数组或有序表。因此,使用有序表查找的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表...
  • 如有错误的地方还请斧正 emm.....涉及到的重要知识点: 引用: void Creat_LinkList(LinkList &...L2)都涉及到一个点:“引用” 第一个函数的参数LinkList &L有必要说明一下,在链表操作中经常在函数参...
  • 将两无序数组合并为有序链表

    千次阅读 2006-10-19 10:44:00
    实现思想:把两无序的数组首先排序,然后再按照链表结构把它们分别构造好,然后再把两个有序链表合并。int const array1_size = 5;//数组1的长度int const array2_size = 7;//数组2的长度//链表结构体typedef ...
  • 有序表的索引顺序结构查找次数分析@(算法学习) 为了提高查找效率,65025元素的有序顺序表建立索引顺序结构,在最好情况下查找到表中已有元素,平均需要执行(B)次关键字比较。 A. 10 B. 14 C. 20 D. ...
  • 从第一个结点开始进行比较,当两个链表La和Lb均到达表尾结点时,依次摘取其中较小者重新链接在Lc的最后。如果两个中的元素相等,只摘取La中的元素,删除Lb中的元素,这样确保合并后中无重复的元素。当...
  • 有序表的查找

    千次阅读 2015-11-14 10:28:02
    大小均n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的() 查找失败的情况下,无序表查找需要更长, ...
  • 将俩有序顺序合并为一个新的有序顺序,并返回结果 输入: 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...
  • 个有序链表的合并(JAVA)

    千次阅读 2019-03-14 14:34:29
    单链表主类 参考单链表反转中的主类代码 ...直到有一个链表移动结束,再将另一个链表的剩余部分追加到新链表的链尾。 代码 public SinglyLinkedList&amp;lt;T&amp;gt; mergeSorted(SinglyLinkedLi...
  • LeetCode 图解 | 21.合并两个有序链表

    千次阅读 2020-01-17 12:15:00
    点击上方蓝字设星标下面开始今天的学习~今天分享的题目来源于 LeetCode 上第 21 号问题:合并两个有序链表。题目描述将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接...
  • 数据结构—有序表的合并

    千次阅读 多人点赞 2019-06-21 11:51:44
    1.有序表合并 问题描述:已知线性表La 和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。 例如: La=(1 ,7, 8) Lb=(2, 4, 6, 8, 10, 11) ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 154,305
精华内容 61,722
关键字:

对一个长度为10的有序表