-
有序链表插入 java_Java 实现有序链表
2021-02-28 12:41:37平均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
-
有序环形链表插入节点
2019-01-18 16:13:37题目:给定一个整数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"); }
运行结果:
-
有序双向链表插入 lambda、function 用法
2019-04-17 12:14:04看到一道面试题: 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赛题吧~~。
-
数据结构——11 有序双向链表中插入节点
2016-08-18 17:08:57双向链表——有序双向链表中插入节点 -
【8555】编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向...
2019-09-25 00:05:46编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表 #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),更具体的说是有序双链表的插入问题。 所谓双链表,就是链表中每个节点含两个节点类型的指针,一个指向下一个节点,另外一个指向上一个节点。 链表节点数据结构定义如下: ... -
C语言:有序递增链表的插入问题。
2019-03-12 16:43:00fun函数:把形参x的值放入一个新结点并插入链表中,使插入的各个数据域的数据仍保持递增有序。 1 #include <stdio.h> 2 #include <stdlib.h> 3 #define N 8 4 typedef struct lis... -
重温数据结构:有序循环链表的插入
2014-03-11 10:43:27注意:有序循环链表插入后,需要保持原来的顺序 /* * $filename: MyCircularLinkedList.java,v $ * $Date: 2014-3-10 $ * Copyright (C) ZhengHaibo, Inc. All rights reserved. * This software is Made by ... -
单向循环链表的有序插入 对单向循环链表head插入元素 链表保持有序
2014-07-01 21:32:37#ifndef CYCLICLIST_H_ #define CYCLICLIST_H_ #include using namespace std; class CyclicList { public: /* public标示外部代码可见 */ struct node { int dat;... * 向循环单链表中插入新元素 -
有序链表的插入
2017-11-07 20:36:287-1 有序链表的插入(20 分) 已知一个递增有序链表L(带头结点,元素为整数),编写程序将一个新整数插入到L中,并保持L的有序性。其中单链表的类型定义参考如下: typedef int elementType; typedef ... -
保证值有序的链表插入算法
2014-04-23 22:24:00在做链表插入时,保证链表中的值是有序的,比如从小到大,依次递增。 以下是今天写的一段代码的修改版。 typedef struct Node{ int value; Node *next; } Node; typedef struct NodeHead{ int counter... -
双向链表有序插入
2020-03-04 19:53:47今天无意间翻开了数据结构,忽然扫到了双向链表,就想着重新把代码码一遍练练手。三两分钟就写完了,运行时就尴尬了。发现没有输出。 于是我就debug了一下,就发现,每次插入的元素的pre竟然是元素本身经过调试后,... -
环形有序链表插入节点
2017-07-13 16:00:26题目:将值为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... -
在有序循环链表中插入新结点
2020-09-23 15:28:10某电器商场仓库中一批电视机,按其价格从低到高的次序构成了一个循环链表,表中的每个元素指出了价格、数量和链指针三个域。现在新到m台价格为h元的电视机入库。试编写出仓库电视机链表增加电视机的算法 typedef ... -
有序双链表的实现
2020-12-26 11:06:39插入操作(将一个数据元素插入到有序的双链表中,插入之后链表仍然有序,输入数据为0表示插入操作结束) 按值删除节点(考虑有重复值的情况) 双链表的遍历操作 双链表的析构 输入 输入链表中的元素,根据输入元素,... -
链表的有序插入
2013-11-18 20:34:00链表的有序插入 从小到大排序 根据指针获取当前id,并设置前指针,方便操作: // test1107.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include "... -
2-19有序环形链表中插入新节点
2020-02-29 16:19:55给定一个环形单链表的头节点,和一个num值,生成一个新节点插入到原链表中。保证环形链表从头节点开始到最后一个节点是非降序排序。 解题方法1 比如,环形链表为 1 2 2 3 5 5 7 当num=3,新节点应该插入到第四个... -
往有序链表的插入元素使原链表依旧有序
2017-09-12 18:56:34在有序链表中插入元素时,最好设置两个指针,一前一后, cur指针负责比较大小,pre指针负责定位插入位置的前驱。 #include using namespace std;typedef struct TNode { int data; struct TNode *next; }TNode;... -
在一个有序(按非递减顺序)的链表中插入一个元素为x的结点,使插入后的链表仍然有序(链表数据域为整型数,...
2021-02-18 16:13:02在一个有序(按非递减顺序)的链表中插入一个元素为x的结点,使插入后的链表仍然有序(链表数据域为整型数,初始时输入6个元素)。 程序运行示例如下: 输入数组6个元素的值。 12 23 34 45 56 67 此链表各个结点的数据...