精华内容
下载资源
问答
  • 平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),假设一个应用须要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择优先级队列 能够使用有序链表来实现有序链表插入排序:...

    有序链表:

    按关键值排序。

    删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。

    插入时须要比較O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),

    假设一个应用须要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择

    优先级队列 能够使用有序链表来实现

    有序链表的插入排序:

    对一个无序数组,用有序链表来排序,比較的时间级还是O(N^2)

    复制时间级为O(2*N),由于复制的次数较少,第一次放进链表数据移动N次,再从链表拷贝到数组,又是N次

    每插入一个新的链结点,不须要复制移动数据。仅仅须要改变一两个链结点的链域

    import java.util.Arrays;

    import java.util.Random;

    /**

    * 有序链表 对数组进行插入排序

    * @author stone

    */

    public class LinkedListInsertSort> {

    private Link first;//首结点

    public LinkedListInsertSort() {

    }

    public boolean isEmpty() {

    return first == null;

    }

    public void sortList(T[] ary) {

    if (ary == null) {

    return;

    }

    //将数组元素插入进链表,以有序链表进行排序

    for (T data : ary) {

    insert(data);

    }

    //

    }

    public void insert(T data) {// 插入 到 链头, 以从小到大排序

    Link newLink = new Link(data);

    Link current = first, previous = null;

    while (current != null && data.compareTo(current.data) > 0) {

    previous = current;

    current = current.next;

    }

    if (previous == null) {

    first = newLink;

    } else {

    previous.next = newLink;

    }

    newLink.next = current;

    }

    public Link deleteFirst() {//删除 链头

    Link temp = first;

    first = first.next; //变更首结点,为下一结点

    return temp;

    }

    public Link find(T t) {

    Link find = first;

    while (find != null) {

    if (!find.data.equals(t)) {

    find = find.next;

    } else {

    break;

    }

    }

    return find;

    }

    public Link delete(T t) {

    if (isEmpty()) {

    return null;

    } else {

    if (first.data.equals(t)) {

    Link temp = first;

    first = first.next; //变更首结点,为下一结点

    return temp;

    }

    }

    Link p = first;

    Link q = first;

    while (!p.data.equals(t)) {

    if (p.next == null) {//表示到链尾还没找到

    return null;

    } else {

    q = p;

    p = p.next;

    }

    }

    q.next = p.next;

    return p;

    }

    public void displayList() {//遍历

    System.out.println("List (first-->last):");

    Link current = first;

    while (current != null) {

    current.displayLink();

    current = current.next;

    }

    }

    public void displayListReverse() {//反序遍历

    Link p = first, q = first.next, t;

    while (q != null) {//指针反向,遍历的数据顺序向后

    t = q.next; //no3

    if (p == first) {// 当为原来的头时,头的.next应该置空

    p.next = null;

    }

    q.next = p;// no3 -> no1 pointer reverse

    p = q; //start is reverse

    q = t; //no3 start

    }

    //上面循环中的if里。把first.next 置空了, 而当q为null不运行循环时,p就为原来的最且一个数据项,反转后把p赋给first

    first = p;

    displayList();

    }

    class Link {//链结点

    T data;//数据域

    Link next; //后继指针,结点链域

    Link(T data) {

    this.data = data;

    }

    void displayLink() {

    System.out.println("the data is " + data.toString());

    }

    }

    public static void main(String[] args) {

    LinkedListInsertSort list = new LinkedListInsertSort();

    Random random = new Random();

    int len = 5;

    Integer[] ary = new Integer[len];

    for (int i = 0; i < len; i++) {

    ary[i] = random.nextInt(1000);

    }

    System.out.println("----排序前----");

    System.out.println(Arrays.toString(ary));

    System.out.println("----链表排序后----");

    list.sortList(ary);

    list.displayList();

    }

    }打印

    ----排序前----

    [595, 725, 310, 702, 444]

    ----链表排序后----

    List (first-->last):

    the data is 310

    the data is 444

    the data is 595

    the data is 702

    the data is 725

    展开全文
  • 题目:给定一个整数num,如何在节点有序的环形链表插入一个节点值为num的节点,并保证这个环形链表依然有序。(假如链表是升序) 解决思路: 1.如果链表为空,则开辟一个节点,让后让他自己指向自己,然后返回该...

    题目:给定一个整数num,如何在节点有序的环形链表中插入一个节点值为num的节点,并保证这个环形链表依然有序。(假如链表是升序)

    解决思路:
    1.如果链表为空,则开辟一个节点,让后让他自己指向自己,然后返回该节点。
    2.如果链表不为空,分为三种情况:
    a.如果插入的节点的值是在环形链表最大值和最小的闭区间范围之内,即在链表[min,max]里面,那么先找到要插入的位置,然后插入。
    在这里插入图片描述
    b.如果插入的节点的值大于链表最后一个值,那么插入的位置就直接是最后一个节点的后面,然后让他指向头结点,最后返回头结点。
    在这里插入图片描述
    c.如果插入的节点小于链表的第一个节点,也就是小于最小的一个节点,那么插入的位置还是链表的最后一个节点的后面,然后让他指向头结点,最后返回新插入的节点。
    在这里插入图片描述

    有了方法,代码就比较好写了。

    typedef struct node
    {
    	DataType data;
    	struct node *p_next;
    }Node ,*PNode;
    
    PNode InsertInCircle(PNode head,DataType data)//插入一个节点在有序链表中,并且插入之后链表有序
    {
    	//1.如果环形链表是空,则将该节点插入,返回该节点
    	if (head == NULL)
    	{
    		PNode pCur = NULL;
    		pCur = (PNode)malloc(sizeof(Node));
    		pCur->data = data;
    		pCur->p_next = pCur;
    		return pCur;
    	}
    	else
    	{
    		//2.先找到只要插入的位置
    		pCur = head->p_next;
    		PNode pPre = head;
    		while (pCur != head)
    		{
    			//a.插入位置在链表内
    			if (pPre->data <= data && pCur->data >= data)
    			{
    				PNode pNode = (PNode)malloc(sizeof(Node));
    				pNode->data = data;
    				pPre->p_next = pNode;
    				pNode->p_next = pCur;
    				return head;
    			}
    			pPre=pPre->p_next;
    			pCur = pCur->p_next;
    		}
    		//.出循环,说明此时data是链表中最大或者是最小的节点
    		//此时pCur==head
    		PNode pNode = (PNode)malloc(sizeof(Node));
    		pNode->data = data; 
    		pPre->p_next = pNode;
    		//b.比头结点小
    		pNode->p_next = pCur;
    		if (data < head->data)
    			return pNode;
    		else
    			//比头结点大
    			return head;
    	}
    }
    

    结果:
    测试的链表有5个节点,分别是1->2->3->4->5->1(最后的1是多打印了一次原链表只有一个值为1的节点)…
    1.当链表为空
    在这里插入图片描述
    2.插入值为1的节点
    在这里插入图片描述
    3.插入值为2的节点
    在这里插入图片描述
    4.插入值为5的节点
    在这里插入图片描述
    5.插入值为6的节点

    在这里插入图片描述
    测试及源代码下载:源代码

    展开全文
  • 有序插入建立链表 C语言实现

    千次阅读 2016-01-13 13:24:49
    实现代码/*有序插入建立链表 C语言实现*/#include #include<stdlib.h>/*定义一个linklist结构体类型*/ typedef struct linklist { int data; struct linklist *next; }list, *plist;/*按从小到大顺序插入*/ void ...

    实现代码

    /*有序插入建立链表 C语言实现*/
    
    #include<stdio.h>
    #include<stdlib.h>
    
    /*定义一个linklist结构体类型*/
    typedef struct linklist
    {
        int data;
        struct linklist *next;
    }list, *plist;
    
    /*按从小到大顺序插入*/
    void order_insert_list(plist *head,int number)
    {
        plist p_new = (plist)malloc(sizeof(list));
        plist pre = NULL;           /* pre指针作为temp指向next前的备份 */
        p_new->data = number;       /* 赋予新值给新结点 */
        p_new->next = NULL;         
    
        plist temp = (plist)malloc(sizeof(list));
        temp = *head;  /*每次插入前从链表头开始的位置*/
    
        /*首位空结点赋初值*/
        if (NULL == *head)
        {
            *head = p_new;
            return;
        }
    
        /*若新data比头结点小,头结点前插入*/
        if (p_new->data < temp->data)
        {
            p_new->next = temp; 
            *head = p_new;
            return;
        }
        else
        {
            while (NULL != temp)
            {   
                if (p_new->data >= temp->data)/* 新结点对当前结点data比较 */
                {
                    pre = temp;     
                    temp= temp->next;/*当前结点后移,直至5(比如1 2 3 5 插入4)的位置*/
                    continue;
                }
                else
                {
                    p_new->next = temp;/* 插入新结点 */
                    pre->next = p_new; /* temp的前一个的位置的next指向新结点p_new */
                    break;
                }           
            }
            if (NULL == temp)/* 当temp最终为尾结点时,说明新元素data最大,将结点作为尾结点 */
            {
                p_new->next = NULL;
                pre->next = p_new;   /* temp的前一个的位置的next指向新结点p_new */
            }
        }
    }
    
    void print_list(plist head)
    {
        plist elem = head; 
        while (elem != NULL)
        {
            printf("%d ", elem->data);
            elem = elem->next;
        }
        printf("\n");
    }
    
    void main()
    {
        int number;
        plist head;     /*定义表头*/
        head = NULL;
    
        printf("input some numbers:\n");
        scanf("%d", &number);
        while (number != -1) /*输入-1终止*/
        {
            order_insert_list(&head,number);
            scanf("%d", &number);
        }
    
        print_list(head);/*打印输出*/
    
        system("pause");
    }

    运行结果:

    这里写图片描述

    展开全文
  • 看到一道面试题: typedef struct node { int value; struct node* next;...//实现有序双向链表插入和删除 int insert1(S_LIST_NODE* _list, int value); int delete1(S_LIST_NODE* _list, int value...

    看到一道面试题:

    typedef struct node
    {
    int 			value;
    struct node*	next;
    struct node*	prev;
    } S_LIST_NODE;
    //实现有序双向链表的插入和删除
    int insert1(S_LIST_NODE* _list, int value);
    int delete1(S_LIST_NODE* _list, int value);
    

    删除我就不写了,正好回顾一下lambda的递归写法,如有不妥请评论直接指出。谢谢。

    废话不多时上代码:

    //有序双向链表
    int insert1(S_LIST_NODE * _list, int value)
    {
    	node *temp = _list;
    	function<void(node*)> lb = [&](node *_left)
    	{
    		if (_left==nullptr)
    		{
    			S_LIST_NODE *right = new S_LIST_NODE();
    			right->value = value;
    			right->prev = temp;
    			right->next = nullptr;
    
    			temp->next = right;
    			return;
    		}
    		if (_left->value < value)
    		{
    			temp = _left;
    			lb(_left->next);
    		}
    		else
    		{
    			S_LIST_NODE *left = new S_LIST_NODE();
    			left->value = value;
    			left->prev = temp;
    			left->next = _left;
    
    			temp->next = left;
    			_left->prev = left;
    		}
    	};
    	lb(temp->next);
    	return 1;
    }
    

    调用方式:

    	S_LIST_NODE * temp = new S_LIST_NODE();
    	insert1(temp, 1);
    	insert1(temp, 2);
    	insert1(temp, 16);
    	insert1(temp, 3);
    	insert1(temp, 6);
    	insert1(temp, 10);
    

    递归lambda就需要使用是std::function保存lambda了。其他的没有什么特别之处,好久没写递归,还是思考了一晚上写出来的。有时间复习一下双递归的OJ赛题吧~~。

    展开全文
  • 双向链表——有序双向链表插入节点
  • 编写在非递减有序链表插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表 #include<bits/stdc++.h> #define RESULT int #define OK 1 #define ERROR 0 using namespace std; ...
  • 有序链表插入问题

    千次阅读 2012-10-30 01:45:13
    这里只讨论双链表(Doubly Linked List),更具体的说是有序链表插入问题。 所谓双链表,就是链表中每个节点含两个节点类型的指针,一个指向下一个节点,另外一个指向上一个节点。 链表节点数据结构定义如下: ...
  • fun函数:把形参x的值放入一个新结点并插入链表中,使插入的各个数据域的数据仍保持递增有序。 1 #include <stdio.h> 2 #include <stdlib.h> 3 #define N 8 4 typedef struct lis...
  • 注意:有序循环链表插入后,需要保持原来的顺序 /* * $filename: MyCircularLinkedList.java,v $ * $Date: 2014-3-10 $ * Copyright (C) ZhengHaibo, Inc. All rights reserved. * This software is Made by ...
  • #ifndef CYCLICLIST_H_ #define CYCLICLIST_H_ #include using namespace std; class CyclicList { public: /* public标示外部代码可见 */ struct node { int dat;... * 向循环单链表中插入新元素
  • 有序链表插入

    千次阅读 2017-11-07 20:36:28
    7-1 有序链表插入(20 分) 已知一个递增有序链表L(带头结点,元素为整数),编写程序将一个新整数插入到L中,并保持L的有序性。其中单链表的类型定义参考如下: typedef int elementType; typedef ...
  • 在做链表插入时,保证链表中的值是有序的,比如从小到大,依次递增。 以下是今天写的一段代码的修改版。 typedef struct Node{ int value; Node *next; } Node; typedef struct NodeHead{ int counter...
  • 双向链表有序插入

    热门讨论 2020-03-04 19:53:47
    今天无意间翻开了数据结构,忽然扫到了双向链表,就想着重新把代码码一遍练练手。三两分钟就写完了,运行时就尴尬了。发现没有输出。 于是我就debug了一下,就发现,每次插入的元素的pre竟然是元素本身经过调试后,...
  • 题目:将值为value的节点node插入有序环形链表中(头节点head) 思路: 分以下情况: (1)head==null,即链表为空,那么node.next=next,返回node。 (2)链表不为空,pre=head,cur=head.next;两个同步向后找,...
  • 有序链表插入函数

    2019-06-16 21:43:04
    创建一个节点 ...调用有序链表插入函数: //插入到一个有序链表。函数的参数是一个指向链表根指针的指针,以及一个需要插入的新值 result=sll_insert(&root,12); 插入函数1 #include <st...
  • 某电器商场仓库中一批电视机,按其价格从低到高的次序构成了一个循环链表,表中的每个元素指出了价格、数量和链指针三个域。现在新到m台价格为h元的电视机入库。试编写出仓库电视机链表增加电视机的算法 typedef ...
  • 有序链表的实现

    2020-12-26 11:06:39
    插入操作(将一个数据元素插入有序的双链表中,插入之后链表仍然有序,输入数据为0表示插入操作结束) 按值删除节点(考虑有重复值的情况) 双链表的遍历操作 双链表的析构 输入 输入链表中的元素,根据输入元素,...
  • 链表有序插入

    2013-11-18 20:34:00
    链表有序插入 从小到大排序 根据指针获取当前id,并设置前指针,方便操作: // test1107.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "...
  • 给定一个环形单链表的头节点,和一个num值,生成一个新节点插入到原链表中。保证环形链表从头节点开始到最后一个节点是非降序排序。 解题方法1 比如,环形链表为 1 2 2 3 5 5 7 当num=3,新节点应该插入到第四个...
  • 有序链表插入元素时,最好设置两个指针,一前一后, cur指针负责比较大小,pre指针负责定位插入位置的前驱。 #include using namespace std;typedef struct TNode { int data; struct TNode *next; }TNode;...
  • 在一个有序(按非递减顺序)的链表插入一个元素为x的结点,使插入后的链表仍然有序链表数据域为整型数,初始时输入6个元素)。 程序运行示例如下: 输入数组6个元素的值。 12 23 34 45 56 67 此链表各个结点的数据...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,217
精华内容 1,686
关键字:

有序插入链表