精华内容
下载资源
问答
  • 将两个有序单链表合并为一个有序单链表

    千次阅读 多人点赞 2019-08-01 14:45:28
    将两个有序单链表合并为一个有序单链表 //完整代码段 #include<stdio.h> #include<stdlib.h> typedef struct LNode{ int data; struct LNode* next; }LNode; LNode* Createlist(int length)//尾插法...

    将两个有序单链表合并为一个有序单链表

    //完整代码段
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct LNode{
    	int data;
    	struct LNode* next;
    }LNode;
    
    LNode* Createlist(int length)//尾插法建立链表 
    {
    	LNode* L=(LNode*)malloc(sizeof(LNode));
    	L->next=NULL;
    	LNode* p=L;
    	for(int i=0;i<length;i++)
    	{
    		LNode* t=(LNode*)malloc(sizeof(LNode));
    		t->next=NULL;
    		scanf("%d",&t->data);
    		p->next=t;
    		p=t;
    	}
    	return L;
    }
    
    LNode* combine(LNode* La,LNode* Lb)//将Lb上元素合并到La上 
    {
    	LNode* pa=La->next;
    	LNode* pb=Lb->next;
    	LNode* q=La;//分别用三个指针标记两个表的三个位置
    	while(pa&&pb)
    	{
    		if(pa->data>pb->data)//pb指向的元素小于pa指向的元素,则将pb指向元素插入 
    		{
    			LNode* t=pb;
    			pb=pb->next;
    			t->next=pa;
    			q->next=t;
    			q=t; 
    		}
    		else//若pb指向元素不小于pa,则pa指向下一元素直到可以找到
    		{
    			q=q->next;pa=pa->next;
    		}
    	 }
    	 if(pb) q->next=pb;//如果pb指向的元素最后仍有大于La表元素的值
    	 return La; 
    }
    void scan(LNode* L)//遍历链表
    {
    	LNode* p=L->next;
    	while(p)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    int main()
    {
    	LNode* L1=Createlist(3);
    	LNode* L2=Createlist(3);
    	combine(L1,L2);
    	scan(L1);
    	return 0;
     } 
    
    展开全文
  • 数据结构:用C++实现两个有序单链表和成一个有序单链表,使用递归方法实现
  • 有序单链表

    2017-09-16 18:07:15
    由标题就可以知道,这篇博客我们使用的是在插入时就已经排好序的单链表. 我把它命名为 OrderedList ,这里我们从小到大排序,下面我们以此看一下它的主要方法与代码实现就好: 主要方法: insert():插入一个元素,...

    由标题就可以知道,这篇博客我们使用的是在插入时就已经排好序的单链表.

    我把它命名为 OrderedList ,这里我们从小到大排序,下面我们以此看一下它的主要方法与代码实现就好:

    主要方法:

    • insert():插入一个元素,并且保持链表有序
    /*插入节点*/
        @Override
        public void insert(int key) {
            if (root.next == null) {
                root.next = new LinkedNode(key);
            } else {
                LinkedNode p = root;
                while (true) {
                    if (p.next == null) {
                        p.next = new LinkedNode(key);
                        break;
                    } else if (p.next.key < key) {
                        p = p.next;
                    } else {
                        LinkedNode node = new LinkedNode(key);
                        node.next = p.next;
                        p.next = node;
                        break;
                    }
                }
    
            }
            count++;
        }


    • delete():删除末尾的元素,(最大的)
    @Override
        public int delete() {
            LinkedNode p = root;
            assert !isEmpty();
            while (p.next.next != null) {
                p = p.next;
            }
            int key = p.next.key;
            p.next = null;
            return key;
        }


    • popFirst():删除开头的元素(最小的)
    public int popFirst() {
            LinkedNode p = root;
            assert !isEmpty();
            int key = p.next.key;
            if (p.next.next != null) {
                p.next = p.next.next;
            } else {
                p.next = null;
            }
            return key;
        }


    • isEmpty():判断是否为空
    @Override
        public boolean isEmpty() {
            return root.next == null;
        }


    • removeAll():从小到大的输出元素,并且使得整个列表为空
    //将会从小到大的输出
        public int[] removeAll() {
            int[] arr = new int[count];
            int i = 0;
            while (!isEmpty()) {
                arr[i] = root.next.key;
                i++;
                root.next = root.next.next;
            }
            count = 0;
            return arr;
        }

    全部代码:

    package com.list;
    
    /**
     * 顺序链表:
     * 能够使得再插入时就满足从小到大的有序状态
     */
    public class OrderedList implements ILinkedList {
        private int count;//节点个数
        LinkedNode root;
        
        public int getCount() {
            return count;
        }
    
        /*插入节点*/
        @Override
        public void insert(int key) {
            if (root.next == null) {
                root.next = new LinkedNode(key);
            } else {
                LinkedNode p = root;
                while (true) {
                    if (p.next == null) {
                        p.next = new LinkedNode(key);
                        break;
                    } else if (p.next.key < key) {
                        p = p.next;
                    } else {
                        LinkedNode node = new LinkedNode(key);
                        node.next = p.next;
                        p.next = node;
                        break;
                    }
                }
    
            }
            count++;
        }
    
        @Override
        public int delete() {
            LinkedNode p = root;
            assert !isEmpty();
            while (p.next.next != null) {
                p = p.next;
            }
            int key = p.next.key;
            p.next = null;
            return key;
        }
    
        public int popFirst() {
            LinkedNode p = root;
            assert !isEmpty();
            int key = p.next.key;
            if (p.next.next != null) {
                p.next = p.next.next;
            } else {
                p.next = null;
            }
            return key;
        }
    
        @Override
        public boolean isEmpty() {
            return root.next == null;
        }
    
        //将会从小到大的输出
        public int[] removeAll() {
            int[] arr = new int[count];
            int i = 0;
            while (!isEmpty()) {
                arr[i] = root.next.key;
                i++;
                root.next = root.next.next;
            }
            count = 0;
            return arr;
        }
    
        public OrderedList() {
            root = new LinkedNode(1);
            count = 0;
        }
    }

    展开全文
  • 两个有序单链表合并成一个有序单链表的java实现 -- 仅作为备注, 便于自己回顾.

    仅作为备注, 便于自己回顾.

    import java.util.Arrays;
    
    /**
     * @author John Kenrinus Lee
     * @version 2016-10-20
     */
    public class MergeSort {
        public static class LinkedNode<V extends Comparable<V>> {
            public V value;
            public LinkedNode<V> next;
    
            public LinkedNode(V value) {
                this.value = value;
            }
            public LinkedNode(V value, LinkedNode<V> next) {
                this.value = value;
                this.next = next;
            }
        }
    
        public static <T extends Comparable<T>> LinkedNode<T> prepareSortedLinkedList(T...list) {
            Arrays.sort(list);
            LinkedNode<T> head = new LinkedNode<>(list[0]);
            LinkedNode<T> begin = head;
            for (int i = 1; i < list.length; i++) {
                begin.next = new LinkedNode<>(list[i]);
                begin = begin.next;
            }
            return head;
        }
    
        public static <T extends Comparable<T>> LinkedNode<T> cloneLinkedList(LinkedNode<T> head) {
            if (head == null) {
                return null;
            }
            LinkedNode<T> result = new LinkedNode<>(head.value);
            LinkedNode<T> clonedList = result;
            while (true) {
                head = head.next;
                if (head != null) {
                    clonedList.next = new LinkedNode<>(head.value);
                    clonedList = clonedList.next;
                } else {
                    break;
                }
            }
            return result;
        }
    
        public static <T extends Comparable<T>> void dumpLinkedList(LinkedNode<T> head) {
            while (true) {
                if (head != null) {
                    System.out.print(String.valueOf(head.value) + ' ');
                } else {
                    break;
                }
                head = head.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            LinkedNode<String> head11 = prepareSortedLinkedList("dump", "just", "found", "get");
            LinkedNode<String> head21 = cloneLinkedList(head11);
            dumpLinkedList(head11);
            System.out.println("-------------------------------------------");
            dumpLinkedList(head21);
            System.out.println("-------------------------------------------");
            LinkedNode<String> head12 = prepareSortedLinkedList("get", "zara", "yes", "but", "row", "ok", "another");
            LinkedNode<String> head22 = cloneLinkedList(head12);
            dumpLinkedList(head12);
            System.out.println("-------------------------------------------");
            dumpLinkedList(head22);
            // end prepare
            System.out.println("\n++++++++++++++++++++++++++++++++++++++++++\n");
            // start test
            LinkedNode<String> result1 = mergeSortedLinkedList1(head11, head12);
            dumpLinkedList(result1);
            System.out.println("-------------------------------------------");
            LinkedNode<String> result2 = mergeSortedLinkedList2(head21, head22);
            dumpLinkedList(result2);
        }
    
        /** recusive. return head node as ascending. will change parameters, non reentrant. */
        public static <T extends Comparable<T>> LinkedNode<T> mergeSortedLinkedList1(LinkedNode<T> a, LinkedNode<T> b) {
            LinkedNode<T> head;
            if (a == null) {
                return b;
            }
            if (b == null) {
                return a;
            }
            if (isFirstLessThanSecond(a.value, b.value)) {
                head = a;
                head.next = mergeSortedLinkedList1(a.next, b);
            } else {
                head = b;
                head.next = mergeSortedLinkedList1(a, b.next);
            }
            return head;
        }
    
        /** virtual node + loop. return head node as ascending. will change parameters, non reentrant. */
        public static <T extends Comparable<T>> LinkedNode<T> mergeSortedLinkedList2(LinkedNode<T> a, LinkedNode<T> b) {
            LinkedNode<T> header = null, head = null;
            if (a == null) {
                return b;
            }
            if (b == null) {
                return a;
            }
            while (true) {
                if (isFirstLessThanSecond(a.value, b.value)) {
                    if (head == null) {
                        header = head = a;
                    } else {
                        head.next = a;
                        head = head.next;
                    }
                    a = a.next;
                } else {
                    if (head == null) {
                        header = head = b;
                    } else {
                        head.next = b;
                        head = head.next;
                    }
                    b = b.next;
                }
                if (a == null) {
                    head.next = b;
                    break;
                } else if (b == null) {
                    head.next = a;
                    break;
                }
            }
            return header;
        }
    
        /**
         * 1. null is smallest;
         * 2. if first == null && second == null then return true;
         * 3. if first equals second then return false;
         */
        private static <T extends Comparable<T>> boolean isFirstLessThanSecond(T first, T second) {
            if (first == null) {
                return true;
            }
            if (second == null) {
                return false;
            }
            return first.compareTo(second) < 0;
        }
    }
    展开全文
  • 合并有序单链表

    2017-07-13 16:23:13
    合并有序单链表
  • 两个有序单链表归并为一个有序单链表//定义节点 struct ListNode { int m_nValue; ListNode* m_pNext; } ; ListNode* Merge(ListNode* pHead1,ListNode* pHead2) { if(pHead1 == NULL) return pHead2; if...

    两个有序单链表归并为一个有序单链表

    c代码:

    //定义节点
    struct ListNode
    {
        int m_nValue;
        ListNode* m_pNext;
     } ;
     ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
     {
        if(pHead1 == NULL)
        return pHead2;
        if(pHead2 == NULL)
        return pHead1;
    
        ListNode* pMergedHead = NULL;
        if(pHead1->m_nValue<pHead2->m_nValue)
        {
            pMergedHead = pHead1;
            pMergedHead->m_pNext = Merge(pHead1->m_pNext,pHead2);//递归建立
         }
         else
         {
            pMergedHead = pHead2;
            pMergedHead->m_pNext = Merge(pHead1,pHead2->m_pNext);
         }
         return pMergedHead;
     } 
    展开全文
  • ha,hb为带头结点的非递减有序单链表,利用原空间生成的非递减有序单链表
  • 两个非递减有序单链表合并为非递增有序单链表,不能增加新结点,可以增加新指针,不能利用循环链表,不能用顺序表,只能利用单链表本身的结点,通过改变指针的指向来获得结果。 #include #include #include #define ...
  • 【数据结构】 合并两个非递减有序单链表为一个A-B的非递减有序单链表 题目 实现两个单链表La和Lb的相减链表LC,LC的元素为LA中有但LB中没有的元素。LA和LB都为非递减有序链表 分析 LC是LA和LA的相减链表,即LC= ...
  • 这里我的思路就是:先将递减的链表反置(void reverse_list(List* l)函数), 然后, 通过比较反置后的链表最后一个元素和开始递增序列的第一个元素比较,如果小于,直接将原来递增链表连在其后即可 ...
  • 如何将两个有序单链表合并为一个有序单链表 public static LinkedList MergeLink(LinkedList link1, LinkedList link2) { LinkedListNode currentNodeOfLink1 = link1.First; LinkedListNode currentNo
  • 设ha和ha分别是两个带附加头结点的非递增有序单链表的表头指针,试设计一个函数将这两个有序单链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间切新的头结点为原来ha的头结点,不另外...
  • 两个有序单链表合成为一个有序单链表,自己写的代码运行出错, 弄了很久都没解决,是我的思路错了,还是代码细节出问题了?求大神帮忙 编译通过,但是运行是直接提示exe停止运行 ``` #include #include ...
  • 一、有序单链表插入结点 插入结点的过程其实就是一个遍历链表的过程,在遍历过程中判断是否到达尾结点以及判断待插入的数据大小和结点数据谁大,当然我我这里没有考虑特殊情况,比如插入的数据如果正好是最大或者...
  • 有序单链表去重

    2021-06-20 14:47:50
    根据程序提供的LNode结构,删除以h为头结点的有序单链表中的重复元素,并返回删除的元素构成的新单链表(保持原来表中的相对顺序)。 函数接口定义: LNode* DelR(LNode *h); 其中h为无附加表头的单链表的首结点...
  • 有序单链表去重 

    2021-01-16 17:02:06
    有序单链表去重(10分) 根据程序提供的LNode结构,删除以h为头结点的有序单链表中的重复元素,并返回删除的元素构成的新单链表(保持原来表中的相对顺序)。 函数接口定义: LNode* DelR(LNode *h); 其中`h`为无...
  • java实现合并两个有序的单链表,输出合并的新的有序单链表 新的链表不改变原来的链表的结构 package LinkedList; /* * 合并两个有序的单链表,输出的也为有序的链表 并且不改变原来两个链表的结构 * 这里就只在...
  • 建立有序单链表 & 单链表的反转操作 最近才知道比较主流的使用单链表方式为“head指针不指向数据,从head->next开始指向数据”,之前几个月写的都是按“直接从head开始指向数据”来写的。真·村网通…于是按...
  • 合并两个有序单链表

    2021-04-16 20:54:52
    编程实现将两个有序的单链表LA(含有m个节点)和LB(含有n个节点)合并成一个新的有序单链表LA,原有单链表LA和LB中的结点都按数据域值以非递减排列。
  • 实现两个有序单链表的合并。要求:随机创建两个单链表,实现单链表的排序,再对两个有序单链表进行合并。
  • java实现两个有序单链表合并

    万次阅读 多人点赞 2018-11-19 13:55:30
    本次分享的事两个有序单链表的合并, 遍历方法 递归 非递归 节点类 /** * @auther: lawt * @date: 2018/11/4 08 * @Description: 结点信息 */ public class Node { /** * 为了方便,这两个变量...
  • 实现两个有序单链表的合并。要求:随机创建两个单链表,实现单链表的排序,再对两个有序单链表进行合并。 ================================= 源代码 #include  using namespace std; template  class...
  • SDUT_有序单链表归并

    2018-03-12 10:02:19
    有序链表的归并Time Limit: 1000 ms Memory Limit: 65536 KiBSubmit StatisticProblem Description分别输入两个有序的整数序列(分别包含M和N个数据),建立两个有序的单链表,将这两个有序单链表合并成为一个大...
  • 学归并排序算法的时候,...顺便写个有序单链表的归并 /*有序数组的归并*/ function mergeArr(arr1, arr2) { var result = [], arr1_index = 0, arr2_index = 0; while(arr1_index arr2_index < arr2.lengt
  • 有序单链表合并
  • 实现有序单链表的定义,建立,遍历,插入,删除以及两个有序单链表的合并; 本资源包括需求分析,概要设计,详细设计,调试分析,测试结果和源代码

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 28,345
精华内容 11,338
关键字:

有序单链表