精华内容
下载资源
问答
  • 将两个单链表合并成一个有序单链表 思路:因为链表可以由结点轻松构造,所以首先需要创建单链表的元素,然后选择构造方式构造单链表,本代码为后插构造单链表。然后有了链表,怎么合并为一个有序单链表。大体可以先...

    3.10
    4.将两个单链表合并成一个有序单链表

    由于以前初学c++时所写的代码不堪入目,不符合规范性,完整性和鲁棒性,于是今日重写其核心算法以警示自己。

    Node* Merge(Node p1Head, Node p2Head)
    {
    	if(p1Head == nullptr)
    		return p2Head;
    	if(p2Head == nullptr)
    		return p1Head;
    	
    	Node* pMergedHead=nullptr;
    	
    	if(p1Head->info<p2Head->info)
    	{
    		pMergedHead=p1Head;
    		pMergedHead->next=Merge(p1Head->next,p2Head);
    	}
    	else
    	{
    		pMergedHead=p2Head;
    		pMergedHead->next=Merge(p1Head,p2Head->next)
    	}
    	return pMergedHead;
    }
    

    思路:因为链表可以由结点轻松构造,所以首先需要创建单链表的元素,然后选择构造方式构造单链表,本代码为后插构造单链表。然后有了链表,怎么合并为一个有序单链表。大体可以先尝试排序构造的每个单链表,然后再在合并的时候进行有序比较排列即可。

    #include<stdlib.h>
    #include<stdio.h>
    #include<iostream>
    typedef struct Node {
     
     int info;
    
     struct Node *next;
    
    }*List;
    void creatList(List *head,int n) {
    
     int i;
    
     List p,q;
    
     *head = (List)malloc(sizeof(struct Node));
    
     (*head)->next = NULL;
    
     q = *head;
    
     for ( i = 0; i < n; i++)
    
     {
    
      p = (List)malloc(sizeof(struct
    Node));
    
      cin >> p->info;
    
      p->next = q->next;
    
      q->next = p;
    
      p = q;
    
     }
    
    }
    int List_length(List a);
    
    void maopaosort(List p) {
    
     List la, lb;
    
     int n = List_length(p);
    
     int i, j,temp;
    
     for ( i = 0,la=p->next; i < n;
    i++,la=la->next)
    
     {
    
      for ( j = i+1,lb=la->next; j
    < n; j++,lb=lb->next)
    
      {
    
       if
    (la->info>lb->info)
    
       {
    
        temp
    = la->info;
    
        la->info
    = lb->info;
    
        lb->info
    = temp;
    
       }
    
      }
    
     }
    
    }
    int List_length(List a) {
    
     int i=0;
    
     List p;
    
     p = a->next;
    
     while (p != NULL)
    
     {
    
      ++i;
    
      p = p->next;
    
     }
    
     return i;
    
    }
    void outputlist(List head) {
    
     List p;
    
     p = head->next;
    
     while (p!=NULL)
    
     {
    
      cout << p->info
    << " ";
    
      p=p->next;
    
     }
    
    }
    void merge(List l1, List l2, List *l3) {
    
     List p1,p2, p3;
    
     *l3 = l1;
    
     p1 = l1->next;
    
     p2 = l2->next;
    
     p3 = *l3;
    
     while (p1!=NULL&&p2!=NULL)
    
     {
    
      if (p1->info >
    p2->info) {
    
       p3->next=
    p2;
    
       p2 =
    p2->next;
    
       p3 =
    p3->next;
    
      }
    
      else
    
      {
    
       p3->next =
    p1;
    
       p1 =
    p1->next;
    
       p3 =
    p3->next;
    
      }
    
    }  
    
     if (p1 != NULL) {
    
      p3->next= p1;
    
     }
    
     else
    
     {
    
      p3->next= p2;
    
     }
    
    }
    int main() {
    
     List a, b, c;
    
     creatList(&a, 5);
    
     maopaosort(a);
    
     //outputlist(a);
    
     creatList(&b, 4);;
    
     maopaosort(b);
    
     //outputlist(b);
    
     merge(a, b, &c);
    
     //cout << endl;
    
     outputlist(c);
    
    }
    
    展开全文
  • 两个有序单链表合成为一个有序单链表,自己写的代码运行出错, 弄了很久都没解决,是我的思路错了,还是代码细节出问题了?求大神帮忙 编译通过,但是运行是直接提示exe停止运行 ``` #include #include ...
  • /*链表*/ #include typedef struct node {  int data; ... struct node *next;.../*后插法创建单链表*/ void hou_create(Listlink *head,int n) {  int i;  Listlink p,q;  *head=(Listlin

    /*链表*/
    #include <stdlib.h>

    typedef struct node
    {
        int data;
        struct node *next;
    }*Listlink;

    /*后插法创建单链表*/
    void hou_create(Listlink *head,int n)
    {
        int i;
        Listlink p,q;
        *head=(Listlink )malloc(sizeof(struct node));
        (*head)->next=NULL;/*建立头结点*/
        q=*head;
        for(i=0;i<n;i++)
        {
           p=(Listlink)malloc(sizeof(struct node));
           scanf("%d",&(p->data));

           p->next=q->next;
           q->next=p;
           q=p;
        }

    }

    /*将两个递增单链表合并为一个递增的单链表*/
    void merge(Listlink la,Listlink lb,Listlink *lc)

    {
        Listlink pa,pb,pc;
        *lc=la;                        /*合并后的链表头结点使用a链表的*/

        pa=la->next;
        pb=lb->next;
        pc=*lc;

        while(pa!=NULL&&pb!=NULL)
        {
           if(pa->data<pb->data)
           {
              pc->next=pa;
              pa=pa->next;
              pc=pc->next;
           }
           else
           {
              pc->next=pb;
              pb=pb->next;
              pc=pc->next;
           }
        }
        if(pa!=NULL)pc->next=pa;
        else         pc->next=pb;
    }

    void print_list(Listlink head)
    {
         Listlink p;
         p=head->next;
         while(p!=NULL)
         {
           printf(" %d",p->data);
           p=p->next;
         }
    }

    main()

    {

       Listlink la,lb,lc;

       puts("houcha:");
       hou_create(&lb,10);
       puts("houcha:");
       hou_create(&la,10);

       merge(la,lb,&lc);
       print_list(lc);
       getch();


    }

    展开全文
  • 单链表的基本操作 包括 :链表的创建(头插法,尾插法),链表的遍历,两个单调递增的链表合并为一个单调递增的链表,两个单调递增的链表合并为一个单调递减的链表   #include #include using namespace std;...

    单链表的基本操作   包括 :链表的创建(头插法,尾插法),链表的遍历,两个单调递增的链表合并为一个单调递增的链表,两个单调递增的链表合并为一个单调递减的链表

     

    #include <cstdlib>
    #include <iostream>
    using namespace std;
    
    //定义单链表的接点
    typedef struct Node{
            int data;
            struct Node * next;
            }Nodes; 
    //将两个单调递增链表合并成一个 单调递增链表
    void merge(Node * a,Node * b,Node * &c){
         Node * p=a->next;//永远指向a的最小的接点
         Node * q=b->next; //永远指向b的最小的接点
         Node * r;//永远指向c的最后一个接点
         c=a; //使用a的头结点
         c->next=NULL;
         free(b);//释放b的头结点
         r=c;//当前c的最后一个接点 也是它的第一个接点
         
         while(p!=NULL && q!=NULL){
                 if((p->data)>(q->data)){
                      r->next=q; q=q->next;
                      r=r->next;
                      }
                 else{
                      r->next=p; p=p->next;
                      r=r->next;
                      }
                 } 
          if(p!=NULL) r->next=p;//将a的剩余接点 添加到c的后面 
          if(q!=NULL) r->next=q;//将b的剩余接点 添加到c的后面 
         } 
         
    //将两个单调递增的单链表合并成一个  单调递减的单链表
     void mergeDown(Node * a,Node * b,Node * &c){
         Node * p=a->next;//永远指向a的最小的接点
         Node * q=b->next; //永远指向b的最小的接点
         Node * r;//即将插入的接点 
         c=a; //使用a的头结点
         c->next=NULL;
         free(b);//释放b的头结点
         
         while(p!=NULL && q!=NULL){
                 if((p->data)>(q->data)){
                      r=q; q=q->next;
                      r->next=c->next;
                      c->next=r; 
                      }
                 else{
                      r=p; p=p->next;
                      r->next=c->next;
                      c->next=r;
                      }
                 } 
          while(p!=NULL){//将a的剩余接点 添加到c的后面 
                       r=p; p=p->next;
                      r->next=c->next;
                      c->next=r;
                      }
          while(q!=NULL){//将b的剩余接点 添加到c的后面 
                      r=q;q=q->next;
                      r->next=c->next;
                      c->next=r;
                      }
         } 
    //创建链表   尾插法 
    void createList(Node * &node ,int data[],int length){
         Node * p;//指向最后一个接点 
         Node * q;//指向新创建的接点
         //创建头结点
         node=(Node *)malloc(sizeof(Node));
         node->next=NULL;
         
         p=node; 
         int i;
         for(i=1;i<=length;i++){
                 q=(Node *)malloc(sizeof(Node));
                 q->data=data[i];
                 p->next=q;
                 p=q;
               }     
                p->next=NULL;
         } 
    
    //创建链表  头插法
    void createListHead(Node * &node ,int data[],int length){
           Node * q;//指向新创建的接点
           
           //创建头结点
         node=(Node *)malloc(sizeof(Node));
         node->next=NULL;
         
          int i;
         for(i=length;i>=1;i--){
                 q=(Node *)malloc(sizeof(Node));
                 q->data=data[i];
                 q->next=node->next;
                 node->next=q;
               }     
         } 
     
    //遍历单链表
    void showList(Node * node){
         Node * p;//指向当前遍历的接点
         if(node!=NULL)
         p=node->next;
         while(p!=NULL){
                 printf("%d-->",p->data);
                 p=p->next;
                 } 
         } 
    
    
    
    int main(int argc, char *argv[])
    {
        Node * node=NULL;
        Node * node2=NULL;
         Node * node3=NULL;
        int data[11];
         int data2[11];
        int i;
        for(i=1;i<=10;i++){
                      data[i]=i*i  ;         
                          }
        for(i=1;i<=10;i++){
                      data2[i]=i ;         
                          }
        int length=10;
        createList(node ,data,length);
        createListHead(node2 ,data2,length);
        showList(node);
        printf("\n");
        showList(node2);
        printf("\n");
        mergeDown(node,node2,node3); 
        showList(node3);
        
        system("PAUSE");
        return EXIT_SUCCESS;
    }
    


     

    展开全文
  • 通过冒泡排序进行单链表的有序插入,并将这两个有序单链表合并成一个有序单链表,使用两个单链表的原有空间进行合并,将生成的有序单链表输出显示
  • C语言:有序单链表创建

    千次阅读 2018-12-16 16:59:01
    如何创建一个带头结点的有序单链表? 链表在创建的时候就把它创建成有序的会显得专业许多(雾), 而不是先创建无序链表再排序; 拿一道典型例题举个栗子,相信你们都见过这道题; Problem Description 输入N个...

    如何创建一个带头结点的有序的单链表?

    链表在创建的时候就把它创建成有序的会显得专业许多(雾),
    而不是先创建无序链表再排序;
    拿一道典型例题举个栗子,相信你们都见过这道题;

    Problem Description
    输入N个无序的整数,建立一个有序链表,链表中的结点按照数值非降序排列,输出该有序链表。
    Input
    第一行输入整数个数N;
    第二行输入N个无序的整数。
    Output
    依次输出有序链表的结点值。
    Sample Input
    6
    33 6 22 9 44 5
    Sample Output
    5 6 9 22 33 44
    Hint
    不得使用数组!

    那么思路是什么呢?
    我们可以再输入新的结点时逐个进行查找与插入操作,这样建立的就是有序的链表啦

    #include<stdio.h>
    struct node
    {
     int data;
     struct node * next;
    };
    struct node * sort(struct node * p,int x)
    {
     struct node *ph,*pte,*paf;
     ph=p;
     pte = (struct node *)malloc(sizeof(struct node));
     pte->data = x;pte->next = NULL;
     while (p->next)
     {
      paf = p->next;
      if (paf->data >= x)
      {
       pte->next = p->next;
       p->next = pte;
       return ph;
      }
      p = p->next;
     }
     pte->next = p->next;
     p->next = pte;
     return ph;
     //while外表示的是创建第一个结点和最后一个结点时的情况
     //大小排序为p<pte<=paf
    }
    void list(struct node *p)
    {
     p = p->next;
     while (p)
     {
      printf("%d ", p->data);
      p = p->next;
     }
    }
    int main()
    {
     struct node *ph;
     ph = (struct node *)malloc(sizeof(struct node));
     ph->next = NULL;
     int n, i, x;
     scanf("%d", &n);
     for (i = 0;i < n;i++)
     {
      scanf("%d", &x);
      ph = sort(ph, x);
     }
     list(ph);
     getchar();
     getchar();
     return 0;
    }
    

    鸣谢这位V家厨(https://www.cnblogs.com/luoxiaoyi/p/9726720.html)

    展开全文
  • 这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、...
  • 创建一个临时的头节点,头节点每次指向headA 或者 headB较小的节点 当headA->data 比headB->data小的时候,headA的当前节点加入临时头节点,同时headA指针向后移动;否则headB加入临时头节点,同时headB指针向...
  • 带头单链表的创建、打印和释放见博客 一:单链表的创建、打印和释放 1. 递归方式实现 思路:如果两个结点... * 递归实现两个有序单链表的合并 * @param[in] pNode1 NODE_t * :单链表的第一个有效结点 * @pa...
  • Codeup问题 F: 算法2-25 有序单链表删除重复元素 题目地址 ...根据一个递增的整数序列构造有序单链表,删除其中的重复元素 输入 输入包括多组测试数据,每组测试数据占一行,第一个为大于等...
  • 1、Java实现单链表 ...链表; public class SingleLinkedList&... //创建一个头结点方便进行操作 private Node head=new Node(); //用于记录链表中的结点个数 int size; //给指定位置添加元素 public boolean add...
  • 2、创建一个新的头节点head,先赋值为空 3、比较两个单链表节点的值的大小,值小的就放在新的链表的末尾 3.1、如果是链表1的节点的值更小,就把该值放在新的链表尾部,链表1指向下一位,链表2保持不变,两个参数分别...
  • 如何使用c语言合并两个有序单链表 基本思路: 创建新的头结点,使用while循环依次比较两个链表的值,并改变next的指向,破环原来两个链表的结构,当其中一个链表的指针域为NULL时循环结束,并使指针指向另一个...
  • JAVA合并两个有序单链表,合并之后的链表依然有序 思路:利用第三个单链表,先将其中一个链表连接至链表3,再遍历另外一个链表,将其节点按顺序连接到链表3上。 package linkedlist; public class ...
  • /** * @author carry_C * @date 2020/5/30 - 14:13 * 要求:合并两个有序单链表,合并之后的链表依然有序 */ public class SingleLinkedListDemoTest1 { ... //创建一个单链表 SingleLinkedList2 singleLin
  • 创建两个递增的整数单链表,然后将其合并成一个新链表,合成后的链表依然保持递增有序 #include <stdio.h> #include <math.h> #include<string.h> #include<malloc.h> #include<stdlib.h...
  • 实现如下有序单链表创建数据结构: typedef struct NODE { int value; struct NODE *link; } Node; 版本: int ssl_inset(Node *current, int new_value) { Node *previous; Node *new_node; ...
  • #include #include struct node //声明结构体类型名 ...//指向下一个结点的指针 }; struct node *create_slist()//建立单链表的函数,返回的是头结点 {  int x;  struct node *head,*s,*r;
  • 链表:链表是一个有序的列表;是以节点的方式存储的,是链式存储;其中每一个节点包含data域,next域,next域指向下一个节点;链表的各个节点不一定是连续存放的;链表分带有头节点的链表和没有头节点的链表,根据...
  • 个单链表的交集

    千次阅读 2018-03-28 17:21:41
    条件:必须为两个有序单链表算法思想:首先创建一个头结点,什么都不存放。 再对两个单链表进行逐个比较,出口条件为指向两个单链表的指针都不为空。(1)如果相等,创建一个结点,将数值存入,两个单链表的指针都...
  • 创建:先创建一个head头节点不存放具体的数据,作用:就是表示单链表的头。然后添加一个节点直接加入到链表最后。 遍历:通过一个临时变量,帮助遍历整个单链表。 public class SingleLinkedListDemo { public ...
  • 单链表的实现: 描述 定义单链表类,创建带头结点...输入一组数据,以尾插法的形式创建单链表(0表示输入结束)(构造第一个链表) 输入一组数据,以头插法的形式创建单链表(0表示输入结束)(构造第二个链表) ...
  • 、解决方法:确保两个单链表不为空,且二者皆有序(若无序,则先进行排序)创建新的单链表,并比较原本两个单链表数据大小,较小者置于新单链表中逐步将两个单链表的数据置于新单链表中,直至二者为空二、程序代码...
  • 设计一个算法,将A和B归并成一个按元素值递减有序的链表C, C由A和B中的结点组成。 #include<stdio.h> #include<stdlib.h> typedef struct LNode { int data; struct LNode *next; }LNode; void ...
  • 单链表真题演练

    2020-07-14 18:20:54
    1.将两个有序单链表合并成一个有序单链表 public class MergeSingleLinkList { public static void main(String[] args) { //创建两个单链表 //链表1 Node node1_4 = new Node(289); Node node1_3 = new Node...
  • 首先需要一个节点类,命名为Node,这里的属性我设置的为public,如果有序要也可以设置为private,并提供响应的getter和setter方法即可: class Node{//节点类 public int node;//存放节点的序号,你也可以在后面写...
  • 单链表

    2020-10-27 20:47:28
    创建一个hear头节点(头结点不存放数据,仅仅作为当前链表的入口;head 字段的值不能改变,一旦改变,就丢失了整个链表的入口,我们也就无法通过 head 找到链表了;头结点是为了操作的统一与方便而设立的,放在

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 225
精华内容 90
关键字:

创建一个有序单链表