精华内容
下载资源
问答
  • 链表冒泡排序

    2021-05-20 22:28:39
    对创建的链表使用冒泡排序进行降序排序,输出排序后的链表。 说明:程序中不可见数组、容器,否则计0分。 输入 测试次数t 每组测试数据格式为: 数据个数n n行,每行一个字符串 输出 对每组测试数据,输出字符串...

    题目

    题目描述

    根据输入,采用尾插法创建链表。对创建的链表使用冒泡排序进行降序排序,输出排序后的链表。
    说明:程序中不可见数组、容器,否则计0分。

    输入

    测试次数t
    每组测试数据格式为:
    数据个数n
    n行,每行一个字符串

    输出

    对每组测试数据,输出字符串按字典降序排序后的链表。各组输出间以空行分隔。

    示例输入

    2
    4
    shenzhen
    nanjing
    beijing
    wuhan
    6
    china
    brazil
    germany
    philippines
    switzerland
    singapore

    示例输出

    wuhan
    shenzhen
    nanjing
    beijing

    switzerland
    singapore
    philippines
    germany
    china
    brazil

    代码

    #include<iostream>
    #include<string>
    using namespace std;
    
    class node
    {
    public:
    	string name;
    	node* next;
    	node() {next = nullptr;}
    };
    
    class link
    {
    public:
    	node* head;
    	int len;
    	link() {
    		len = 0;
    		head = new node();
    	}
    	void insert(string n) {
    		node* tmp = new node();
    		tmp->name = n;
    		node* q = head;
    		while (q->next != 0) q = q->next;
    		q->next = tmp;
    	}
    	void sort() {
    		for (int i = 0; i < len-1; i++) {//len-1次
    			node* q = head;
    			for (int j = 0; j < len - 1 - i; j++) {
    				node* t1 = q->next;
    				node* t2 = t1->next;
    				if (t2->name.compare(t1->name) > 0) {//tmp后于q
    					node* tt = t2;
    					t1->next = t2->next;
    					t2->next = t1;
    					q->next = tt;
    				}
    				q = q->next;
    			}
    		}
    	}
    	void print() {
    		node* p = head->next;
    		while (p != 0) {
    			cout << p->name << endl;
    			p = p->next;
    		}
    	}
    };
    
    int main()
    {
    	int n;
    	cin >> n;
    	while (n--) {
    		link ll;
    		cin >> ll.len;
    		int t = ll.len;
    		for (int i = 0; i < t; i++) {
    			string tmp;
    			cin >> tmp;
    			ll.insert(tmp);
    		}
    		ll.sort();
    		ll.print();
    		cout << endl;
    	}
    	return 0;
    }
    
    展开全文
  • 给一个简单的数组冒泡排序算法和程序c语言链表冒泡排序,注释应写具体。不要在别处粘贴代码过来。我想实习的是交换的是它们的指针域也就是每个节点而不是结点后面的数据。C/C++ codestruct Node{int data;struct ...

    ef51c0f380615533401969f5c2f3a35f.png

    给一个简单的数组冒泡排序算法和程序c语言链表冒泡排序,注释应写具体。不要在别处粘贴代码过来。我想实习的是交换的是它们的指针域也就是每个节点而不是结点后面的数据。

    C/C++ code

    8de716c77aa003f164b6fb1791bd377a.png

    struct Node

    {

    int data;

    struct Node * pNext;

    };

    假设里面已经定义好了节点,也生成了一个链表出来了(带有头结点的),现在他们即使帮我排序的代码跟算法要写具体。

    ------解决方案--------------------

    c5b9642cf2bf0cd195ff1fd956c029d4.png

    你还不如在网上搜一下源码快!

    ------解决方案--------------------

    在那些帖子里早已回答了

    50af78e18659b79d5a213449406e90b3.png

    那代码也需要是可以的,你只必须顺序就把排序的部分取起来

    可以直接用的

    ------解决方案--------------------

    5b26e0369ca13289125a46347a609577.png

    C/C++ code

    /**功能:求链表长度(头结点不计算)*参数:链表首地址*返回值:链表结点数*/int length(linklist head){int len = 0;if(head == NULL)return 0;head = head->next;while(head != NULL){++len;head = head->next;}return len;}/**功能:判断两个结点的数据大小*参数:两个结点的地址*返回值:firstNode中数据大于secondNode中数据返回1*firstNode中数据等于secondNode中数据返回0*firstNode中数据小于secondNode中数据返回-1*/int nodeCompare(linklist firstNode, linklist secondNode){if(firstNode->data > secondNode->data)return 1;else if(firstNode->data == secondNode->data)return 0;else if(firstNode->data < secondNode->data)return -1;return -2;}/**功能:链表排序(带头结点)*参数:链表首地址**/void listSort(linklist head){linklist pre, mid, tai;int i, j;int len = length(head);if(head == NULL || head->next == NULL)return;for(i = 0; i < len - 1; ++i){pre = head;mid = head->next;tai = mid->next;for(j = 0; j < len - i - 1; ++j){if(nodeCompare(mid, tai) == 1){pre->next = mid->next;mid->next = tai->next;tai->next = mid;}pre = pre->next;mid = pre->next;tai = mid->next;}}}

    ------解决方案--------------------

    C/C++ code

    void listSort(linklist head){linklist pre, mid, tai;int i, j;int len = length(head);if(head == NULL || head->next == NULL)return;for(i = 0; i < len - 1; ++i){//每次排序都是从头结点开始,共len次pre = head; //记录前一个节点mid = head->next;//记录中间节点tai = mid->next;//记录尾节点for(j = 0; j < len - i - 1; ++j){if(nodeCompare(mid, tai) == 1){//如果成立pre->next = mid->next;//将pre后面的两个节点交换位置mid->next = tai->next;//即pre的next的指向他的下下个节点,tai->next = mid;//他的下节点成为他的下下节点c语言链表冒泡排序,其他不变}pre = pre->next;//循环遍历后面的结点mid = pre->next;tai = mid->next;}}}

    本文来自电脑杂谈,转载请注明本文网址:

    http://www.pc-fly.com/a/jisuanjixue/article-137386-1.html

    展开全文
  • java排序链表冒泡排序Java Sorting is one of the many aspects of java interview questions. In this post, we will see java bubble sort example and write a program for bubble sort. Java排序是Java面试问题...

    java排序链表冒泡排序

    Java Sorting is one of the many aspects of java interview questions. In this post, we will see java bubble sort example and write a program for bubble sort.

    Java排序是Java面试问题的众多方面之一。 在这篇文章中,我们将看到Java冒泡排序示例并编写一个冒泡排序程序。

    Bubble sort is also known as the exchange sort. It is the simplest algorithm for sorting numbers.

    冒泡排序也称为交换排序。 这是最简单的数字排序算法。

    气泡排序算法 (Bubble Sort Algorithm)

    • In bubble sort, the array of integers is traversed from index 0 to length-1.

      在冒泡排序中,整数数组从索引0遍历到length-1。
    • The value at 0th position is compared with the value at 1st position and if the later is small, it’s swapped.

      将第0位的值与第1位的值进行比较,如果后者较小,则将其交换。
    • The comparison is moved from the 0th index to length-1 index so that after the first iteration, the last index has the biggest value.

      比较从第0个索引移到第1个长度索引,因此在第一次迭代之后,最后一个索引具有最大的值。
    • The same process is repeated again from 0th to length-1 index. After (length-1) iteration, the array is sorted.

      从0th到length-1索引再次重复相同的过程。 在(length-1)迭代之后,对数组进行排序。
    • In worst-case, the complexity of bubble sort is O(n2) and in best-case, the complexity of bubble sort is Ω(n).

      在最坏情况下,冒泡排序的复杂度为O(n2),在最坏情况下,冒泡排序的复杂度为Ω(n)。

    Java中的冒泡排序 (Bubble Sort in Java)

    Here is the implementation of Bubble Sort in Java program.

    这是Java程序中的冒泡排序的实现。

    import java.util.Arrays;
    
    public class BubbleSort {
    
    	public static void main(String args[]) {
    		int arr[] = { 5,4,3,2,1 };
    		int arr1[] = { 1,2,3,4,5 };
    		System.out.println("Array after sorting in ascending order:"+Arrays.toString(bubbleSortAscending(arr)));
    		System.out.println("Array after sorting in descending order:"+Arrays.toString(bubbleSortDescending(arr1)));
    	}
    	
    	public static int[] bubbleSortAscending(int[] arr){
    		int temp;
    		for(int i=0; i < arr.length-1; i++){
    			
    			for(int j=1; j < arr.length-i; j++){
    				if(arr[j-1] > arr[j]){
    					temp=arr[j-1];
    					arr[j-1] = arr[j];
    					arr[j] = temp;
    				}
    			}
    			//check that last index has highest value in first loop,
    			// second last index has second last highest value and so on
    			System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr));
    		}
    		return arr;
    	}
    	
    	public static int[] bubbleSortDescending(int[] arr){
    		int temp;
    		for(int i=0; i < arr.length-1; i++){
    			
    			for(int j=1; j < arr.length-i; j++){
    				if(arr[j-1] < arr[j]){
    					temp=arr[j-1];
    					arr[j-1] = arr[j];
    					arr[j] = temp;
    				}
    			}
    			//check that last index has highest value in first loop,
    			// second last index has second last highest value and so on
    			System.out.println("Array after "+(i+1)+"th iteration:"+Arrays.toString(arr));
    		}
    		return arr;
    	}
    
    }

    The above program is for sorting in ascending as well as descending order using bubble sort algorithm.

    上面的程序用于使用冒泡排序算法按升序和降序进行排序。

    Output of the above program is:

    上面程序的输出是:

    Array after 1th iteration:[4, 3, 2, 1, 5]
    Array after 2th iteration:[3, 2, 1, 4, 5]
    Array after 3th iteration:[2, 1, 3, 4, 5]
    Array after 4th iteration:[1, 2, 3, 4, 5]
    Array after sorting in ascending order:[1, 2, 3, 4, 5]
    Array after 1th iteration:[2, 3, 4, 5, 1]
    Array after 2th iteration:[3, 4, 5, 2, 1]
    Array after 3th iteration:[4, 5, 3, 2, 1]
    Array after 4th iteration:[5, 4, 3, 2, 1]
    Array after sorting in descending order:[5, 4, 3, 2, 1]

    As we can see that in every iteration, the last index is getting sorted and it takes (array length – 1) iterations for sorting.

    正如我们看到的那样,在每个迭代中,最后一个索引将被排序,并且需要(数组长度– 1)次迭代才能进行排序。

    GitHub Repository. GitHub Repository中签出完整的示例和更多排序算法实现。

    翻译自: https://www.journaldev.com/557/bubble-sort-java

    java排序链表冒泡排序

    展开全文
  • 链表冒泡排序和二路归并排序冒泡排序二路归并排序 冒泡排序 struct ListNode{ int val; ListNode * next; } ListNode * sort(ListNode * head) { ListNode *p1,*p2; //这里假设头节点存着链表长度 如果没有可以...

    链表冒泡排序和二路归并排序

    冒泡排序

    struct ListNode{
    	int val;
    	ListNode * next;
    }
    
    ListNode * sort(ListNode * head)
    {
    	ListNode *p1,*p2; //这里假设头节点存着链表长度 如果没有可以先一遍循环得到链表长度
    	for(int i = 0; i < head->val - 1; i++)
    	{
    		p1 = head->next;
    		p2 = p1->next;
    		for(int j = 0; j < head->val - 1 - i; j++)
    		{
    			if(p1->val > p2->val)
    			{
    				int temp = p1->val;
    				p1->val = p2->val;
    				p2->val = temp;
    			}
    			p1 = p1->next;
    			p2 = p2->next;
    		}
    	}
    	return head;
    }
    

    二路归并排序

    struct ListNode{
    	int val;
    	ListNode *next;
    }
    
    ListNode * sort(ListNode *head)
    {
    	if(head == NULL || head->next == NULL)
    		return head;
    	ListNode *slow = head,*fast = head->next;
    	while(fast != NULL || fast->next != NULL)	
    	{
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    	ListNode *mid = slow->next;
    	slow->next = NULL;
    	ListNode *leftHead = sort(head);
    	ListNode *rightHead = sort(mid);
    	return merage(leftHead,rightHead);
    }
    
    ListNode *merage(ListNode* p1,ListNode *p2)
    {
    	ListNode * head, * p;
    	if(p1->val > p2->val)
    	{
    		head = p2;
    		p2 = p2->next;
    	}
    	else{
    		head = p1;
    		p1 = p1->next;
    	}
    	p = head;
    	while(p1 != NULL || p2 != NULL)
    	{
    		if(p1->val > p2->val)
    		{
    			p->next = p2;
    			p2 = p2->next;
    		}
    		else
    		{
    			p->next = p1;
    			p1 = p1->next;
    		}
    		p = p->next;
    	}
    	if(p1 != NULL)
    		p->next = p1;
    	if(p2 != NULL)
    		p->next = p2;
    	return head;
    }
    
    展开全文
  • 我也是小白一枚~,最近接触数据结构做到了一个关于多项式相加的问题,但是输出的多项式x的幂次都是无规律性的,这就让我开始想到刚开始我们学的冒泡排序,根据冒泡排序的原理,我实现了链表冒泡排序。 本质上来说:普通的...
  • 链表冒泡排序,可以通过修改节点值和交换节点两种方法,下面给出交换节点的方法。#include#includestruct Node{int data;Node *next;};int createlist(Node **p,int i);int pop_sort(Node *p);int main(){int i=0;...
  • 我试图对一个自实现的双链接列表进行排序,但是它似乎无休止地迭代,我不确定我做错了什么。任何帮助都将不胜感激。public void sortLine() {Module current = this.getLeftMostModule();Module next = this....
  • 链表排序是链表有序合并的前提,所以就放在一起...链表冒泡排序, /** * 链表冒泡排序 * 排序思路: * 逐个节点进行排序 * 把当前节点和下个节点的值进行比较,根据结果处理 * 主要是更换了节点的值 * ...
  • //创建单链表通过链表里面的随机值Num来进行排序,通过链表中的ID来确定不是值的兑换排序 //黄色是第一次运行的,随机值NUM,从小到大的ID //红色是排序过后,NUM排序成功,ID对应着数值 //下面是源码,可以运行; //...
  • C++链表冒泡排序

    千次阅读 2015-07-15 21:23:18
    #include ...//别问我为什么要写链表冒泡排序,操蛋操蛋操蛋。 struct Node { int data; Node *next; Node(int d = int()) :data(d), next(NULL){} }; class List { public: List(int a[], i
  • 一、python实现链表冒泡排序 - 冒泡排序的概念:冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直至没有反序的记录为止。因为按照该算法,每次比较会将当前未排序的记录序列中...
  • //此程序是面对和我一样面对冒泡指针不知所措的同志们的一个简单程序 //在网上看的大多青涩难懂 我在这里给大家生动形象了一下 大神就看看不吭气,真的帮住到同志们才是真的好 #include using namespace std; struct...
  • 废话不多说,直接上排序函数吧 void sort_list(struct node* head) { struct node* pre, * p, * q; struct node* tail = NULL; if (head) { while (head->next != tail)//传入的是带头节点的链表,为了简便...
  • //链表创建 while(num!=-1){ insertEnd2(&lastPtr,num); scanf("%d",&num); } len = getSize(headPtr); //长度 bubbleSort(headPtr,len); //冒泡 printf("The new list is:") ; ...
  • 链表冒泡排序总结(两种方法,第二种更简单)

    千次阅读 热门讨论 2019-04-05 09:59:10
    在大一上学期,我们学了冒泡排序,选择排序,插入排序等等,而今天主要详解一下链表冒泡排序的问题。(边看代码,边讲解) 首先,回顾一下,什么叫做冒泡排序冒泡排序是一种时间复杂度在n的平方下的排序;每次...
  • C语言单向链表冒泡排序

    千次阅读 2019-01-05 12:03:42
    如题,复习期末时敲的,感觉敲的有点复杂 /* typedef struct List{ int i; struct List* next;...next==NULL) //如果链表为空或只有一个节点,直接返回 return head; if(head-&gt;next-&gt;...
  • 实现单链表的冒泡排序
  • 冒泡排序的核心是从头开始相邻数据两两比较,如果要升序,前比后大则交换,下面用图讲解链表交换指针域的原理。 代码实现: node* bubble_sort(node *head){ node *tail=NULL,*q,*p=(node*)malloc(sizeof(node)); ...
  • C语言链表冒泡排序

    2012-02-12 12:29:27
    给一个简单的链表冒泡排序算法和程序,注释要写详细。不要在别处粘贴代码过来。我想实习的是交换的是他们的指针域也就是每个结点而不是结点里面的数据。 struct Node { int data; struct Node * pNext; }; ...
  • 双向链表冒泡排序

    千次阅读 2011-06-22 09:56:00
    /* * ===================================================================================== * * Filename: doublelink.c * * Description: bubble use double linklist * * Ve

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,647
精华内容 12,258
关键字:

链表冒泡排序