精华内容
下载资源
问答
  • 使用单链表的简单选择排序

    千次阅读 2020-04-11 18:01:20
    单链表简单选择排序算法 单链表的存储结构和创建单链表 1、 单链表的结构: typedef struct list { int data; struct list * next; }list,*linklist; 2、 单链表的创建: void create(linklist &L,int n)...

    单链表简单选择排序算法

    单链表的存储结构和创建单链表

    1、

    单链表的结构:

    typedef struct list
    {
    	int data;
    	struct list * next;
    }list,*linklist;
    

    2、

    单链表的创建:

    void create(linklist &L,int n)
    {
    	int i;
    	linklist p;
    	L = (linklist)malloc(sizeof(list));
    	L->next = NULL;
    	for(i=0;i<n;i++)
    	{
    		p = (linklist)malloc(sizeof(list));
    		scanf("%d",&p->data);
    		p->next = L->next;
    		L->next = p;
    	}
    }
    

    3、

    点链表的打印:

    void show(linklist L)
    {
    	linklist p;
    	p = L->next;
    	while(p)
    	{
    		printf("%d\t",p->data);
    		p = p->next;
    	}
    }
    

    简单选择排序

    简单选择排序步骤

    简单选择排序:

    1⃣️ 设待排序的记录放在数组r[1…n]中。第一趟从r[1]开始,通过n-1次比较,从n个记录中选出关键字中选出关键字最小的记录,记为r[k],交换r[1]和r[k]。*

    2⃣️ 第二趟从r[2]开始,通过n-2次比较,从n-1个记录中选出关键字最小的记录,记为r[k],交换r[2]和r[k]。

    3⃣️ 依次类推,第i趟从r[i]开始,通过n-i次比较,从n-i+1个记录中选出关键字最小的记录,记为r[k],交换r[2]和r[k]。

    4⃣️ 经过n-1趟,排序完成。

    简单选择排序思想

    从头到尾进行扫描,找到最小的放在第一个位置,在从第二个位置进行第二次扫描,找到最小的,放在第二个位置,依次扫描,直到全部有序

    用单链表实现简单选择排序

    实现代码:

    //
    //  main.c
    //  Sorting_algorithm_design_questions_01
    //
    //  Created by Neil Xie on 2020/4/11.
    //  Copyright © 2020 Neil Xie. All rights reserved.
    //
    
    #include<stdio.h>
    #include<stdlib.h>
    #define Maxsize 20
    
    typedef struct{
        int key;
    }RedType;
    
    typedef struct{
        RedType r[Maxsize+1];
        int length;
    }SqList;
    
    typedef struct Node{
        int date;
        struct Node *next;
    }node,*List;
    //创建单链表
    
    List creat_list(int n)
    {
        int i=0;
        List head,L,temp;
        head=(List)malloc(sizeof(node));
        head->next=NULL;
        temp=head;
        for(;i<n;i++){
            L=(List)malloc(sizeof(node));
            L->next=NULL;
            printf("Please input the date:");
            scanf("%d",&L->date);
            temp->next=L;
            temp=L;
        }
        return head;
     }
     
    List getmin(List L){//取得从指针L开始的链表中记录的最小值
        List min;
        min=L;
        while(L->next){
            if(min->date>(L->next->date)){
                min=L->next;
            }
            L=L->next;
        }
        
        return min;//返回较小值的指针
    }
    
    void selectsort(List head)//简单选择排序--单链表
    {
        List j,i=head->next;
        int temp;
        for(;i->next!=NULL;i=i->next){
            j=getmin(i);
            if(i->date!=j->date){
                temp=i->date;
                i->date=j->date;
                j->date=temp;
            }
        }
    }
    //输出单链表
    
    void printf_list(List head){
        List p=head->next;
        while(p){
            printf("%3d",p->date);
            p=p->next;
        }
    }
    
    int main(){
        List head;
        SqList L;
        L.length=10;
        int n;
        printf("___用单链表实现简单选择排序___\n\n");
        printf("请输入元素个数:");
                scanf("%d",&n);
                head=creat_list(n);
                printf_list(head);
                printf("\n");
                selectsort(head);
                printf_list(head);
                printf("\n");
        
        return 0;
    }
    
    

    代码运行结果

    ___用单链表实现简单选择排序___
    
    请输入元素个数:5
    Please input the date:45
    Please input the date:23
    Please input the date:74
    Please input the date:18
    Please input the date:9
     45 23 74 18  9
      9 18 23 45 74
    Program ended with exit code: 0
    
    展开全文
  • 方法一:不进行任何断链插入操作,找到目标节点之后,只是交换data值,这个思路很简单,与简单选择排序的思路一摸一样。 编程注意事项: min不能标记最小值,应该要标记最小值对应链表节点 LinkList create...

    方法一:不进行任何断链插入操作,找到目标节点之后,只是交换data值,这个思路很简单,与简单选择排序的思路一摸一样。


    编程注意事项:

    min不能标记最小值,应该要标记最小值对应的链表节点

    LinkList createLink(LinkList L) {
    	cout << "尾插法创建单链表:"<<endl;
    	int a;
    	L = (LinkList)malloc(sizeof(LinkNode));
    	L->next = NULL;
    	LinkNode *p=L,*r = L;
    	while (true)
    	{
    		cin >> a;	
    		p = (LinkList)malloc(sizeof(LinkNode));
    		p->data = a;
    		r->next = p;
    		r = p;
    		if (cin.get() == '\n')break;
    	}
    	r->next = NULL;
    	return L;
    }
    
    void printList(LinkList L) {
    	LinkNode *p = L->next;
    	while (p)
    	{
    		cout << p->data << " ";
    		p = p->next;
    	}
    }
    
    LinkList sortList(LinkList L) {
    	LinkNode* p = L->next;
    	LinkNode* q;
    	LinkNode* min;
    	int temp;
    	while (p)
    	{
    		min = p;//有序序列中的最后位置元素节点
    		q = p->next;
    		while (q)
    		{
    			if (min->data > q->data)min=q;
    			q = q->next;//寻找无序序列中的最小值节点
    		}
    
    		if (min!= p) {//交换data值
    			temp = min->data;
    			min->data = p->data;
    			p->data = temp;
    		}
    		p = p->next;
    	}
    	return L;
    }
    
    int main() {
    	//基于单链表的简单选择排序
    	LinkList L=NULL;
    	L=createLink(L);
    	L = sortList(L);
    	cout << endl;
    	printList(L);
    }

    但是,再一次审题:在基于单链表表示的待排序关键字序列上进行简单选择排序,题目想要我们有断链插入操作,而不是直接修改data值,因此,还需要思考另一种方法。

    方法二:

    思路:每一趟找到未排序序列中的最大值,然后把最大值用头插法插入入新的单链表的首部,既然有插入和删除节点的操作,所以必然需要有指针来标记前驱节点,我们引入两个前驱:pre代表遍历的时候的前驱,pre_max代表目标最大值的前驱。

    编程注意事项:

    1.在存储了单链表的第一个节点之后,马上把头结点断开,为新的单链表做准备,很多关于单链表的题目都有这个步骤:断开头结点!!否则指针绝对会出错。

    2.只有在未排序序列的首部节点已经是最大值节点的时候才需要移动外循环的标记指针,具体可以看下图的实现过程。


    LinkList sortList02(LinkList L) {
    	//每次找到最大的插入到链表的最前端
    	LinkNode* h = L->next;
    	LinkNode* max, *p, *pre, *pre_max;
    	L->next = NULL;
    	while (h)
    	{
    		max=p= h;
    		pre =pre_max = NULL;
    		while (p)
    		{
    			if (p->data > max->data) {
    				pre_max = pre;
    				max = p;
    			}
    				pre = p;
    				p = p->next;
    	
    		}
    		//将max插入到头结点之后,并保持单链表链接
    		if (max == h) h = h->next;		
    		else 
    			pre_max->next = max->next;
    
    		max->next = L->next;
    		L->next = max;	
    	}
    
    	return L;
    }

     

    展开全文
  • 单链表为存储结构实现简单选择排序的算法
  • 单链表的选择排序

    2019-10-09 07:23:04
     本文是左程云老师所著的《程序员面试代码指南》第二章中“单链表的选择排序”这一题目的C++复现。  本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。  感谢...

    【说明】:

      本文是左程云老师所著的《程序员面试代码指南》第二章中“单链表的选择排序”这一题目的C++复现。

      本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。

      感谢左程云老师的支持。

    【题目】:

      给定一个无序单链表的头节点 head,实现单链表的选择排序。

      要求:额外的空间复杂读为 O(1)。

     【思路】:

      解法:选择排序

    【编译环境】:

      CentOS6.7(x86_64)

      gcc 4.4.7

     【实现】:

      实现及测试代码:

      1 /*
      2  *文件名:list_sort.cpp
      3  *作者
      4  *摘要:单链表的选择排序
      5  */
      6 
      7 #include <iostream>
      8 
      9 using namespace std;
     10 
     11 class Node
     12 {
     13 public:
     14     Node(int data)
     15     {
     16         value = data;
     17         next = NULL;
     18     }
     19 public:
     20     int value;
     21     Node *next;
     22 };
     23 
     24 Node* getSmallestPreNode(Node *head)    //获取未排序链表中最小节点的前一个节点
     25 {
     26     Node *smallPre = NULL;
     27     Node *small = head;
     28     Node *pre = head;
     29     Node *cur = head->next;
     30     while(NULL != cur)
     31     {
     32         if(cur->value < small->value)
     33         {
     34             smallPre = pre;
     35             small = cur;
     36         }
     37         pre = cur;
     38         cur = cur->next;
     39     }
     40     return smallPre;
     41 }
     42 
     43 Node* selectionSort(Node *head)
     44 {
     45     Node *tail = NULL;    //已排序部分的尾部
     46     Node *cur = head;     //未排序部分的头部
     47     Node *smallPre = NULL;
     48     Node *small = NULL;
     49     while(NULL != cur)
     50     {
     51         small = cur;
     52         smallPre = getSmallestPreNode(cur);
     53         if(NULL != smallPre)
     54         {
     55             small = smallPre->next;
     56             smallPre->next = small->next;
     57         }
     58         cur = cur == small ? cur->next : cur;
     59         if(NULL == tail)
     60             head = small;
     61         else
     62             tail->next = small;
     63         tail = small;
     64     }
     65     return head;
     66 }
     67 
     68 //打印链表
     69 void printList(Node *head)
     70 {
     71     while(NULL != head)
     72     {
     73         cout << head->value << " ";
     74         head = head->next;
     75     }
     76     cout << endl;
     77 }
     78 
     79 int main()
     80 {
     81     Node *head = NULL;
     82     Node *ptr = NULL;
     83     
     84     for(int i =8;i>0;i--)//构造链表
     85     {
     86         if(NULL == head)
     87         {    
     88             head = new Node(i);
     89             ptr = head;
     90             continue;
     91         }
     92         ptr->next = new Node(i);
     93         ptr = ptr->next;    
     94     }
     95     cout << "Before sorted:" << endl;
     96     printList(head);
     97     cout << "After sorted:" << endl;
     98     head = selectionSort(head);
     99     printList(head);
    100     return 0;
    101 }
    View Code

     

    注:

      转载请注明出处;

      转载请注明源思路来自于左程云老师的《程序员代码面试指南》。

    转载于:https://www.cnblogs.com/PrimeLife/p/5440463.html

    展开全文
  • 在链结构上实现简单选择排序 简单选择排序思想 对链表遍历第i趟,就找到第i小元素与第i个位置元素进行交换,直至n-1趟后全部排序完成 设计三个指针,一个指向编号为i节点,一个指向当前节点值最小结点...

    在链结构上实现简单选择排序

    简单选择排序思想
    对链表遍历的第i趟,就找到第i小的元素与第i个位置的元素进行交换,直至n-1趟后全部排序完成

    1. 设计三个指针,一个指向编号为i的节点,一个指向当前节点值最小的结点,一个进行访问
    2. 对链表进行遍历,每遍历一次进行元素的交换,直至排序完成
    void simpleSort(LinkList &L){//简单选择排序 
    	if(!L->next) return;//单链表为空 
    	LNode *p=L->next;//指向首元结点 
    	LNode *min,*q;//min指向每趟最小值结点 
    	while(p->next){
    		q=p->next;
    		min=p;
    		while(q){
    			if(q->data<min->data){
    				min=q;
    			}
    			q=q->next;
    		}
    		if(min->data!=p->data){//数据不一则交换 
    			int temp=min->data;
    			min->data=p->data;
    			p->data=temp;
    		}
    		p=p->next;
    	}
    	p=L->next;
    
    }
    

    经典的错误,标准的零分
    在进行数据交换时,我对指针进行了交换

    	while(q)
    		if(q->data<min->data)
    			min=q;
    		if(min!=p)
    		{
    			temp=p;
    			p=min;
    			min=temp;
    		}
    
    展开全文
  • 单链表的选择排序 题目描述 给定一个无序单链表,实现单链表的选择排序(按升序排序)。 思路 读取链表的数值到集合,用集合排序,生成新的链表。 import java.util.*; public class Solution { public ListNode ...
  • 题目:以实验 1.2 的带表头结点单链表为存储结构,编写程序实现单链表的非递减排序。 部分代码: 带表头结点单链表的非递减排序...//简单选择排序:每次选择min的排到前面 Status Order(HeaderList *h){ Node *s1...
  • //以单链表为储存结构实现简单选择排序的算法。 void Algo(LinkList *L) { LinkList r,s,pre,p; s=(*L)->next; //s 指向链表第一个结点 (*L)->next=NULL; while(s) { SelectMinPtr(s,&pre,&p);...
  • 思路:因时间复杂度要求为O(N*logN),简单排序(时间复杂度为O(N*N))均不可用,故可以考虑归并排序的思想,归并排序对数组操作空间复杂度为O(n),但对链表为O(1),因为每次只在merge函数中创建了一个辅助链表头...
  • 简单的,但是要注意一点,找到当前最小值,是否是在总链表尾部。 import java.util.Scanner; public class Main{ public static class Node{ int val; Node next = null; public Node(int val){ this...
  • C语言单链表实现选择排序

    千次阅读 2019-03-12 12:00:27
    链表实现选择排序有两种方法,一种是交换节点内数据,比较简单。我这里使用是第二种方法,交换节点。 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #...
  • 简单选择排序(C++单链表实现)

    千次阅读 2018-12-14 22:36:17
    1、将整个记录序列划分为有序区和无序区,初始时有序区为空,无序区含有待排序所有记录。 2、在无序区中选取关键码最小记录,将它与无序区中第一个记录交换,使得有序区扩展了一个记录,同时无序区减少了一个记录...
  • 单链表的排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问。故书中把待排序的链表拆分为2个子链表。为了简单起见,选择链表的第一个节点作为基准,然后进行比较...
  • 单链表的快速排序

    2013-07-08 14:53:59
    单链表的排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问。故书中把待排序的链表拆分为2个子链表。为了简单起见,选择链表的第一个节点作为基准,然后进行比较...
  • 单链表排序

    万次阅读 多人点赞 2017-09-03 20:38:22
    交换节点:插入排序,冒泡排序,简单选择排序 交换数据:快速排序初始化:#include #include #include <stdbool.h>//节点结构 struct node { int val; struct node * next; }; typedef str
  • 关于选择排序 正文 题目一 判断一个数据序列是否构成一个小根堆 前提需知,一个“堆”是一颗“完全二叉树”(编号从1…n完全二叉树存储结构数列) 故利用以下性质解题: 当i>1时,结点i双亲结点为i/2(向...
  • 单链表快速排序

    2013-07-22 16:40:19
    单链表的排序和数组的快排序基本思想相同,同样是基于划分,但是又有很大的不同:单链表不支持基于下标的访问。故书中把待排序的链表拆分为2个子链表。为了简单起见,选择链表的第一个节点作为基准,然后进行比较...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 216
精华内容 86
关键字:

单链表的简单选择排序