精华内容
下载资源
问答
  • JAVA LinkList插入排序

    千次阅读 2011-11-10 10:04:59
    编程实现链表: ...链表中的信息按学生成绩的高-->低进行排序;  3.如果输入的学生信息中,学号重复,则仅更新学生成绩,不添加新的节点。   import java.util.Scanner; public class TestLink {
      
    

     

    编程实现链表:

          要求:1.循环输入学生学号和成绩。并将学生信息加入到链表中;

                      2.链表中的信息按学生成绩的高-->低进行排序;

                      3.如果输入的学生信息中,学号重复,则仅更新学生成绩,不添加新的节点。

     

    import java.util.Scanner;

    public class TestLink {

     // 测试主函数
     public static void main(String[] args) {
      LinkList list = new LinkList();
      Scanner sc = new Scanner(System.in);
      String ask = "";
      do {
       System.out.print("请录入学号:");
       int no = sc.nextInt();
       System.out.print("请录入成绩:");
       int num = sc.nextInt();
       Student s = new Student(no, num);
       list.addAndSet(s);// 调用方法.将学生信息擦人链表

       System.out.println("是否继续Y/N");
       ask = sc.next();
      } while (ask.equals("Y") || ask.equals("y"));

      System.out.println("排序前学生成绩一览:");
      list.listAll();// 输出学生信息

      // 对学生成绩进行排序.(按成绩高-->低)
      list.bubbleSort();

      System.out.println("\n排序后学生成绩一览:");
      list.listAll();// 输出学生信息

     }
    }

     

     

    /**
     * 学生类
     */
    class Student {
     private int no;
     private int num;

     public Student(int no, int num) {
      super();
      this.no = no;
      this.num = num;
     }

     public int getNo() {
      return no;
     }

     public void setNo(int no) {
      this.no = no;
     }

     public int getNum() {
      return num;
     }

     public void setNum(int num) {
      this.num = num;
     }
    }

     

     

    /**
     * 链表结点类
     */
    class Node {
     private Student student;
     private Node next; // 链表结点的指针域,指向直接后继结点

     public Node() {
      next = null;
     }

     public Node(Student student, Node next) {
      this.student = student;
      this.next = next;
     }

     public Student getStudent() {
      return student;
     }

     public void setStudent(Student student) {
      this.student = student;
     }

     public Node getNext() {
      return this.next;
     }

     public void setNext(Node next) {
      this.next = next;
     }
    }

     

     

    /**
     * 链表类
     */
    class LinkList {
     private Node head = null; // 头结点指针
     private int size = 0;

     public LinkList() {
      head = new Node();
      size = 0;
     }

     public Node getHead() {
      return this.head;
     }

     public void setHead(Node head) {
      this.head = head;
     }

     public int getSize() {
      return this.size;
     }

     public boolean isEmpty() {
      return (size == 0);
     }

     

     // 插入/修改 学生对象
     public boolean addAndSet(Student stu) {
      Node node;
      // 判断链表是否为空;如果为空则在表头插入
      if (size == 0) {
       // 定义一个新的节点,并将将新结点的指针指向链表的首结点
       node = new Node(stu, this.head.getNext());
       // 把节点插入到head后,设置新结点为链表的首结点
       this.head.setNext(node);
       // 链表长度加1
       size++;
       return true;
      }
      
    // 当链表不为空时候,判断是否有重复的学号.有则替换.无则在结尾插入.
      else {
       Node n;
       for (n = head; n.getNext() != null; n = n.getNext()) {
        // 学号相同.更新学生成绩
        if (n.getNext().getStudent().getNo() == stu.getNo()) {
         n.getNext().getStudent().setNum(stu.getNum());
         return true;
        }
       }
       // 如果学号不同,在链表结尾插入
       Node temp = head;
       while (null != temp.getNext()) {
        temp = temp.getNext();
       }
       node = new Node(stu, temp.getNext());
       temp.setNext(node);
       size++;
       return true;
      }

     }

     

     // 控制台输出链表所有内容
     public void listAll() {
      for (Node curr = head.getNext(); curr != null; curr = curr.getNext()) {
       System.out.print("\n学号: " + curr.getStudent().getNo() + "\t");
       System.out.print("成绩: " + curr.getStudent().getNum() + "\t");
      }
      System.out.println("");
     }

     

     // 链表冒泡排序方法.学生成绩进行排序.(按成绩高-->低)
     public void bubbleSort() {
      Node p, q;
      Student temp;
      for (p = head.getNext(); p.getNext() != null; p = p.getNext()) {
       for (q = head.getNext(); q.getNext() != null; q = q.getNext()) {
        if (q.getStudent().getNum() < q.getNext().getStudent().getNum()) {
         temp = q.getStudent();
         q.setStudent(q.getNext().getStudent());
         q.getNext().setStudent(temp);
        }
       }
      }
     }
    }

     

     

    内容可以直接拉入IDE中.右键运行.

    展开全文
  • // ListSort.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include "iostream"using namespace std;typedef struct _node{ int data; struct _node *next;...

    // ListSort.cpp : Defines the entry point for the console application.
    //

    #include "stdafx.h"
    #include "iostream"
    using namespace std;
    typedef struct _node
    {
     int data;
       struct _node *next;
    }Node;


    int _tmain(int argc, _TCHAR* argv[])
    {
     int arr[]={12,34,1,89,6,56,45,2,31};
     Node* head=new Node();
     Node* p=head;
     for(int i=0;i<9;i++)
     {
      Node* n=(Node*)malloc(sizeof(Node));
      n->data=arr[i];
      n->next=NULL;
      p->next=n;
      p=p->next;
     }
    head=head->next;

    Node* temp=head->next;
    head->next=NULL;

    while(temp)
    {
       Node* p=temp->next;
      for(Node *t=head;t!=NULL;t=t->next)
      {
       if(temp->data>t->data&&t->next!=NULL&&(t->next)->data>temp->data)
       {
        temp->next=t->next;
           t->next=temp;
        break;
       }
       else if(temp->data>t->data&&t->next==NULL)
       {
        t->next=temp;
        temp->next=NULL;
        break;
       }
       else if(temp->data<t->data)
       {
        temp->next=head;
        head=temp;
        break;
       }  
      }
      temp=p;
     
    }
     while(head)
     {
      cout<<head->data<<" ";
      head=head->next;
     }
     cin.get();
     return 0;
    }

     

    展开全文
  • 因为自己写程序栽在这个问题上了,所以就手写+...1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法 代码如下: #include #include struct LinkNode { int data; LinkNode *pNext; LinkNode(in

    因为自己写程序栽在这个问题上了,所以就手写+机试的敲了一下,虽然很小心,但是机试的时候依然写出了bug,所以发这篇帖子算是让自己长长记性吧。

    问题如下:

    1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法

    代码如下:

    #include <stdio.h>
    #include <stdlib.h>
    
    struct LinkNode
    {
    	int data;
    	LinkNode *pNext;
    
    	LinkNode(int _data)
    	{
    		data = _data;
    		pNext = NULL;
    	}
    };
    
    LinkNode* MergeLink(LinkNode *pLeftLink, LinkNode *pRightLink)
    {
    	LinkNode *ph = NULL, *p = NULL;
    
    	while (pLeftLink && pRightLink)
    	{
    		if(pLeftLink->data < pRightLink->data)
    		{
    			if(ph == NULL)
    			{
    				ph = p = pLeftLink;
    				pLeftLink = pLeftLink->pNext;
    			}
    			else
    			{
    				p->pNext = pLeftLink;
    				p = p->pNext;
    				pLeftLink = pLeftLink->pNext;
    			}
    
    		}
    		else
    		{
    			
    			if(ph == NULL)
    			{
    				ph = p = pRightLink;
    				pRightLink = pRightLink->pNext;
    			}
    			else
    			{
    				p->pNext = pRightLink;
    				p = p->pNext;
    				pRightLink = pRightLink->pNext;
    			}
    		}
    	}
    	
    	p->pNext = (pLeftLink == NULL) ? pRightLink : pLeftLink;
    
    	return ph;
    }
    
    LinkNode *MergeSort(LinkNode *pHead, int len)
    {
    	if(len == 1)
    	{
    		pHead->pNext = NULL;
    		return pHead;
    	}
    
    	//当时这里就写出了bug,我是先运算了MergeSort(pHead, len/2),然后用那个phead来求pRightStart
    	LinkNode *pRightStart = pHead;
    	for(int i = 0;i < len / 2; i++)
    	{
    		pRightStart = pRightStart->pNext;
    	}
    
    	LinkNode *pLeftHalf = MergeSort(pHead, len/2);
    	LinkNode *pRightHalf = MergeSort(pRightStart, len - len/2);
    
    	LinkNode *pMergedLink = MergeLink(pLeftHalf, pRightHalf);
    	return pMergedLink;
    
    }
    void PrintAll(LinkNode *pHead)
    {
    	int i = 1;
    	while(pHead)
    	{
    		printf("%d ", pHead->data);
    		pHead = pHead->pNext;
    
    		if(i++ % 20 == 0)
    		{
    			printf("\n");
    		}
    
    	}
    }
    int main()
    {
    	LinkNode *pHead = NULL;
    	LinkNode *pCurrent = NULL;
    
    	int flags[300] = {0};
    	for(int i = 0; i < 10; )
    	{
    		int num = rand()%300;
    		if(flags[num])
    		{
    			continue;
    		}
    		else
    		{
    			flags[i] = 1;
    			i++;
    
    			LinkNode *pNewNode = new LinkNode(num);
    			if(pHead == NULL)
    			{
    				pHead = pCurrent = pNewNode;
    			}
    			else
    			{
    				pCurrent->pNext = pNewNode;
    				pCurrent = pCurrent->pNext;
    			}
    		}
    		
    	}
    
    	PrintAll(pHead);
    	printf("\n\n\n");
    	pHead = MergeSort(pHead, 10);
    	PrintAll(pHead);
    
    
    
    	return 0;
    }


     

    展开全文
  • 将一个单链表进行处理后...将原始链表逐个查询,插入新链表,在插入的同时对链表进行排序。时间复杂度O(n*n) public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); ...

    将一个单链表进行处理后,所得结果为一有序链表

    Solution:

    将原始链表逐个查询,插入新链表,在插入的同时对链表进行排序。时间复杂度O(n*n)

    public ListNode insertionSortList(ListNode head) {
             
            ListNode dummy = new ListNode(0);
             
            while (head != null) {
                ListNode node = dummy;
                while (node.next != null && node.next.val < head.val) {
                    node = node.next;
                }
                ListNode temp = head.next;
                head.next = node.next;
                node.next = head;
                head = temp;
            }
    
            return dummy.next;
        }

     

    转载于:https://www.cnblogs.com/dreamtaker/p/8519984.html

    展开全文
  • java中ArrayList和LinkList的区别

    千次阅读 2019-07-09 15:39:27
    java中ArrayList和LinkList的区别 1.首先我们说下ArrayList和LinkList各是基于什么原理实现的...也就是说,每一次对数组大小进行更改的时候,数组内部会进行重新排序,按照元素的下标顺序重新排序,数组下班是从0开...
  • ArrayList和LinkList区别

    2016-08-17 18:33:00
    ArrayList和LinkList区别 前者是数组的数据结构,后者是链表的数据结构 前者应用于排序和查找,后者应用于插入删除 转载于:https://www.cnblogs.com/zhaozhaozhang/p/5781151.html...
  • java集合之LinkList解析

    千次阅读 2017-09-13 17:36:58
    同时它也实现了Queue队列,Deque栈的实现,使得我们可以进行双向队列的实现,上一节java集合之ArrayList解析中说过ArrayList查询效率比较高,添加和删除集合中的元素效率比较低,而LinkList正好相反.LinkList组织结构图 ...
  • ArrayList与linkList区别

    2017-03-29 10:55:34
    1 ArrayList是实现了基于动态数组的数据结构,这种...linkList是基于链表的数据结构。它采用的是将对象放在独立的空间里,而且每个空间还保存对下一个空间的索引,但是缺点就是查询非常不方便,要从第一个索引开始。
  • LinkList、ArrayList、Vector的区别

    千次阅读 2014-10-29 09:10:42
    首先所以下ArrayList与LinkList的区别:
  • 1.使用C++封装一个链表类LinkList

    千次阅读 2014-12-07 00:07:23
    使用C++封装一个链表类LinkList。写出相应一个测试用例 链表需要提供 添加 修改删除 除重 合并 排序创建 销毁等接口。 不能调用库函数或者使用STL等类库 题目延伸***********逆置链表********** ...
  • 单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。 如果需要对选择排序复习...
  • 排序算法有非常多种,如我们最常用的快速排序和堆排序等算法,这些算法需要对序列中的数据进行比较,因为被称为基于比较的排序。 基于比较的排序算法是不能突破O(NlogN)的。简单证明如下: N个数有N!个可能的排列...
  • 在Java中,ArrayList就是由数组为基础结构创建的,而LinkList是由节点对象而构成的。由于Array的下标特性,ArrayList查找、更新元素值的性能好;对于LinkLIst,其添加或删除元素的性能好。链表根据功能特点可以分为...
  • Linklist O(nlogn) sort

    2014-07-03 18:10:48
    O(nlogn)属于性能较优的排序算法,但是用在链表确实要注意很多,它不支持高效的随机访问,所以需要
  • 数据结构试验-Linklist

    千次阅读 2012-10-14 22:12:30
    第三次作业单链表,简单写的(VS2010)。...#include "linklist.h" int main() { elemtype data; linklist lk; initlinklist(&lk); push_back(lk,'a'); push_back(lk,'b'); push_back(lk,'c'); pus
  • 用c/c++自己动手实现一个链表LinkList

    千次阅读 2018-10-08 15:47:46
    排序复杂度也极大 所以适合插入删除频繁的程序。 实现思想 自建基本的节点数据结构 明确基本操作:初始化、插入、删除、按位置查找、按值查找等等 实现代码 注:vs2008 // LinkList.cpp : Defines the entry ...
  • LinkList<E> myList = new LinkList<E>; E 是一种具体类型 2. 迭代器 // 这里的 E 必须指明具体类型 // 可以是一个类 Iterator<E> iter = myList.iterator(); while(iter.hasNext()) { // 这里...
  • 排序算法有非常多种,如我们最常用的快速排序和堆排序等算法,这些算法需要对序列中的数据进行比较,因为被称为基于比较的排序。 基于比较的排序算法是不能突破O(NlogN)的。简单证明如下: N个数有N!个可能的...
  • 链表排序

    2014-10-12 14:53:38
    链表冒泡排序#include #include typedef struct LNode{ int data; struct LNode* next; }LNode,*LinkList; LinkList createList(LinkList L) { L = (LinkList)malloc(sizeof(LNode)); LNode *r=L,*s;
  • 选择排序:第一层遍历每一个数,第二层从当前位置直到末尾,一直寻找比当前数更大(更小)的值,找到则交换对应位置上的数,未找到则退出第二层,继续第一层的遍历。时间复杂度O(N*N)#include<stdio.h> void swap...
  • 能点进来这文章的肯定对链表有所...class LinkList { private: Node* first; public: LinkList(); LinkList(int a[], int n); ~LinkList() {}; void insert(Node* a, Node* b);//把结点b插入结点a之后 void swa
  • 1. 索引和指针排序:因为元素的数量或者数据量巨大等原因,我们不希望频繁移动要排序的元素。因此,不移动元素的排序方法是维持一个索引数组或者索引指针,而排序的目标就是重排索引数组或指针。 2. 链表排序排序...
  • 单链表排序之冒泡排序

    万次阅读 多人点赞 2016-06-07 12:26:42
    ***单链表排序之冒泡排序*** /* 前段时间刚学会几种排序方法,最近学习了单链表,就用来试试,本篇链表的排序方法讲述的是 单链表的冒泡排序;(注意:请仔细看准节点结构体的包装和头指针的包装再阅读以下代码...
  • 主要介绍了插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序,并分析了他们的时间复杂度和空间复杂度。
  • Road to Coder _LinkList

    2018-04-12 02:17:00
    mergeLinkList(LinkList LA, LinkList LB, int len); // 合并链表 void Reverse(LinkList L); // 头插法逆置 void Divide(LinkList L); int main() { LinkList head; LinkList LB; int i; head ...
  • 单链表LinkList定义与操作

    千次阅读 2017-03-28 10:58:01
    //合并两个非递减顺序排序的单链表 //实质上是对表链的指针导向进行更改形成一条新的路线 //相比列表的合并的优点为:时间复杂度差不多,但是空间复杂度却更小,几乎不用多余空间 //时间复杂度取决于两个表的表长,...
  • 单链表排序

    2015-10-29 17:53:08
    单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。 如果需要对选择排序...
  • 单链表排序之选择排序(赞)

    万次阅读 多人点赞 2012-07-08 15:36:46
    单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。 如果需要对选择排序复习...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,897
精华内容 4,358
关键字:

linklist排序