精华内容
下载资源
问答
  • C++,单链表选择排序.rarC++,单链表选择排序.rarC++,单链表选择排序.rar
  • 单链表选择排序

    2015-05-24 21:12:00
    单链表有多种排序的方法,今天先来说下用选择排序给一个单链表排序。 先来复习下什么是选择排序吧。选择排序,第一次用第一个值与其他值比较,找到最大的交换;第二次循环到第二个值,以此类推到最后一个值,此时,...

    单链表有多种排序的方法,今天先来说下用选择排序给一个单链表排序。

    先来复习下什么是选择排序吧。选择排序,第一次用第一个值与其他值比较,找到最大的交换;第二次循环到第二个值,以此类推到最后一个值,此时,就已经有序。

    int main()
    {
        int temp,k;
        int i,j;
        int a[5]={1,2,3,4,5};
        for(i=0;i<5;i++)                        //外层循环用来改变第一个比较的值
        {
            k=i;                                //k表示当前最大值的下标
            for(j=i+1;j<5;j++)                    //内层循环用来比较第一个值和剩下的其他值
            {
                if(a[i]<a[j])
                    k=j;                        //如果找到大的,记录下标
            }
            temp=a[k];                            //交换当前比较的第一个值和最大值
            a[k]=a[i];
            a[i]=temp;
        }
        for(i=0;i<5;i++)
        {
            printf("%d",a[i]);
        }
    }

    其实单链表的排序也和这个差不多,只不过需要记录找到最值的前面一个结点信息,好了,直接看代码吧。

     1 struct list *sort(struct list *head)
     2 {
     3     struct list *p;
     4     struct list *phead=NULL;                    //phead为新的有序链表表头
     5     struct list *q;
     6     struct list *tail;                        //tail表示有序链表表尾
     7     struct list *p_min;
     8     while(head!=NULL)                        //最外层的循环条件为无序链表不为空
     9     {
    10         for(p=head,q=head;q->next!=NULL;q=q->next)        //p即为快速排序法中的第一个值,用q->next来循环链表寻找最小的值
    11         {
    12             if(q->next->data<p->data)            //寻找最小值
    13             {
    14                 p_min=q;                //如果找到,用p_min记录它的前一个结点,q->next的前一个结点为q
    15                 p=q->next;                //用p记录最小的结点
    16             }
    17         }
    18         if(phead==NULL)                        //如果有序链表为空的话,将最小的结点插入表头
    19         {
    20             phead=p;
    21             tail=p;                        //表尾也为最小结点
    22         }
    23         else                            //如果不为空
    24         {
    25             tail->next=p;                    //表尾指向最小的结点
    26             tail=p;                        //新的结点变为表尾
    27         }
    28         if(p==head)                        //如果找的的最小结点为无序链表的表头
    29         {
    30             head=head->next;                //将表头直接指向下一个结点
    31         }
    32         else
    33         {
    34             p_min->next=p->next;                //否则在原链表中删掉最小的结点(此时就用到了最小结点的前驱)
    35         }
    36     }
    37     if(phead!=NULL)                            //有序链表创建完成之后,将其表尾指向为NULL
    38     {
    39         tail->next=NULL;
    40     }
    41 
    42     return phead;
    43 }

    转载于:https://www.cnblogs.com/kingos/p/4526480.html

    展开全文
  • 单链表选择排序算法

    2012-10-01 19:44:28
    单链表选择排序算法,包括带头结点和不带头结点的算法,对大家帮助很大。
  • C++单链表选择排序

    2007-12-18 06:01:44
    C++单链表选择排序, 这个程序我已经不记得是不是我自己写的了,呵呵,放上来供初学者参考.
  • 2021-03-15:手写代码:单链表选择排序。 福大大 答案2021-03-15: 遍历链表,找出最小元素,链表里删除最小元素,最小元素放在需要返回的链表里。 代码用golang编写,代码如下: package main import "fmt" func ...

    2021-03-15:手写代码:单链表选择排序。

    福大大 答案2021-03-15:

    遍历链表,找出最小元素,链表里删除最小元素,最小元素放在需要返回的链表里。

    代码用golang编写,代码如下:

    package main
    
    import "fmt"
    
    func main() {
        //head := &ListNode{Val: 4}
        //head.Next = &ListNode{Val: 2}
        //head.Next.Next = &ListNode{Val: 1}
        //head.Next.Next.Next = &ListNode{Val: 3}
    
        head := &ListNode{Val: -1}
        head.Next = &ListNode{Val: 5}
        head.Next.Next = &ListNode{Val: 3}
        head.Next.Next.Next = &ListNode{Val: 4}
        head.Next.Next.Next.Next = &ListNode{Val: 0}
    
        cur := head
        for cur != nil {
            fmt.Print(cur.Val, "\t")
            cur = cur.Next
        }
        fmt.Println()
    
        head = SelectSort(head)
    
        cur = head
        for cur != nil {
            fmt.Print(cur.Val, "\t")
            cur = cur.Next
        }
        fmt.Println()
    }
    
    //Definition for singly-linked list.
    type ListNode struct {
        Val  int
        Next *ListNode
    }
    
    //选择排序
    func SelectSort(head *ListNode) *ListNode {
        if head == nil || head.Next == nil {
            return head
        }
    
        //有换头的可能,所以新增一个虚拟头节点
        preAns := &ListNode{}
        preAnsEnd := preAns
        preHead := &ListNode{Next: head}
    
        //选择
        var pre, cur, preSel, sel *ListNode
        for preHead.Next != nil {
            pre, cur = preHead, preHead.Next
    
            //默认选中第1个节点
            preSel, sel = pre, cur
    
            //选最小的,从第2个节点开始
            pre, cur = cur, cur.Next
            for cur != nil {
                if cur.Val < sel.Val {
                    preSel, sel = pre, cur
                }
                pre, cur = cur, cur.Next
            }
    
            //选中的节点放在答案里
            preAnsEnd.Next = sel
    
            //原链表删除选中的节点
            preSel.Next = sel.Next
    
            //尾指针指向Next
            preAnsEnd = preAnsEnd.Next
        }
    
        //虚拟头节点的Next指针就是需要返回的节点
        return preAns.Next
    }
    

    执行结果如下:
    图片


    力扣148. 排序链表
    评论

    展开全文
  • 算法思想: 每次选择最大的或者最小的 进行尾插或者头插。本例选择每次找到最小的数进行尾插 void SelectSort(LNode *p){ if(p->next==NULL||p->next->next==NULL) //若链表为空或者链表中只有一个...

    算法思想: 每次选择最大的或者最小的 进行尾插或者头插。本例选择每次找到最小的数进行尾插

     void SelectSort(LNode *&head){
    
      	if(head->next==NULL||head->next->next==NULL)  //若链表为空或者链表中只有一个元素 返回
    		return ;
    
    	LNode *s=(LinkList)malloc(sizeof(LNode)); //重新分配一个头节点
    	LNode *cur;  //内层循环游标节点
    	LNode *min;	 // 存储最小值的节点
    	LNode *pre;	 //游标节点的前驱节点
    	s->next=head>next;
    	head->next=NULL;
    	LNode *r=head; //尾节点
    	while(s->next){ //如果当前“被选择的”链表还存在元素
    		pre=s;  //最小值节点的前驱节点 避免断链
    		cur=s->next; //游标节点
    		min=cur;  //默认最小值节点为第一个节点
    
    		while(cur->next){
    			if(cur->next->data<min->data){
    				pre=cur;
    				min=cur->next;
    			}
    
    			cur=cur->next;
    		}
    		pre->next=min->next; //解链
    		min->next=r->next;  //尾插新的最小节点
    		r->next=min;
    		r=min;
    	}
    	r->next=NULL;	//尾节点指空
      }
    
    展开全文
  • c语言 单链表 选择排序+归并排序

    千次阅读 2012-10-09 21:29:15
    指针完全不会用了,为了面试,写写~~   #include #include #include #include using namespace std; struct node{ int data; node * next; }; node *creat(){ struct node *head, *tail, *p;...

    指针完全不会用了,为了面试,写写~~

     

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    struct node{
        int data;
        node * next;
    };
    node *creat(){
        struct node *head, *tail, *p;
        head = NULL;
        tail = NULL;
        p = NULL;
        int aa, bb;
        while( scanf("%d", &aa) && aa!= 0){ // 输入为0时停止
            p = (struct node *)malloc(sizeof(struct node));
            p->data = aa;
            if( head == NULL){
                head = p;
                tail = head;
            }
            else {
                tail->next = p;
                tail = p;
            }
        }
        tail->next = NULL;
        return head;
    }
    node *merge_sort(node *l1, node *l2){ 
        node *tmp1, *tmp2, *tmp, *head, *tail;
        if( l1->data <= l2->data){
            head = l1;
            tmp1 = l1->next;
            tmp2 = l2;
        }
        else{
            head = l2;
            tmp1 = l1;
            tmp2 = l2->next;
        }
        tail = head;
        while(1){
            if( tmp1 == NULL){
                tail = tail->next = tmp2;
                break;
            }
            if( tmp2 == NULL){
                tail = tail->next = tmp1;
                break;
            }
            if( (tmp1->data) <= (tmp2->data)){
                tail = tail->next = tmp1;
                tmp1 = tmp1->next;
            }
            else{
                tail = tail->next = tmp2;
                tmp2 = tmp2->next;
            }
        }
        return head;
    }
    void print(node * tmp){
        while( tmp != NULL){
            cout<<tmp->data<<"  ";
            tmp = tmp->next;
        }
        printf("\n");
    }
    void sort(node *p){
        node *head, *tail, *tmp1, *tmp2;
        int aa;
        for( tmp1 = p; tmp1!= NULL; tmp1 = tmp1->next){
            for( tmp2 = tmp1->next; tmp2!= NULL; tmp2= tmp2->next){
                if( tmp1->data >= tmp2->data){
                    aa = tmp1->data;
                    tmp1->data = tmp2->data;
                    tmp2->data = aa;
                }
            }
        }
    }
    int main(){
    	freopen("1.txt", "r", stdin);
        node *l1, *l2 , *tmp;
        l1 = creat();
        l2 = creat();
        sort(l1);
        sort(l2);
        tmp = merge_sort(l1, l2);
        print(tmp);
        //l2 = creat();
    	return 0;
    }
    


     

    展开全文
  • 单链表排序(选择排序)

    千次阅读 2006-12-31 14:03:00
    经典算法--单链表选择排序第一种: #include #include typedef struct node{ int data; struct node *next; }*Linklist,Node; Linklist creat(int n) {Linklist head,r,p; int x,i; head=(Node*)malloc(si
  • 单链表合并排序

    2014-07-09 22:43:46
    单链表合并排序
  • 单链表快速排序

    2017-11-03 09:36:05
    大学或者考研时数据结构单链表快速排序问题,数据结构的基础代码。
  • 单链表排序是单链表的常见编程任务之一,也是面试中经常出现的题目。单链表排序的关键是交换算法,需要额外考虑。选择排序是比较直观的排序算法之一,这里就使用选择排序实现单链表的排序。 如果需要对选择排序复习...
  • 单链表插入排序

    2021-01-16 17:07:53
    单链表插入排序(15分) 单链表插入排序 ###目的: 掌握单链表的应用和插入排序的思想。 ###内容: 编写一个函数insertion_sort,对一个无序单链表采用插入排序的方式,将其按递增方式排序,构成有序单链表。系统后台...
  • 单链表排序

    2021-06-03 09:41:09
    给定一个无序单链表,实现单链表排序(按升序排序)。 示例1 输入: [1,3,2,4,5] 返回值: {1,2,3,4,5} 分析 第一种:直接插入排序,不同与数组的直接插入排序,链表的直接排序从前往后寻找插入位置。 public ...
  • 在链结构上实现简单选择排序 简单选择排序思想 对链表遍历的第i趟,就找到第i小的元素与第i个位置的元素进行交换,直至n-1趟后全部排序完成 设计三个指针,一个指向编号为i的节点,一个指向当前节点值最小的结点...
  • 单链表排序

    2019-12-21 15:18:13
    今天在对单链表排序时发现了一些问题,之前总是直接交换节点数据,但是这不是真正的链式排序,真正意义的链式排序是通过交换节点实现的 起初我想通过脱链和插入节点来实现这个排序,思想是没错的,但是测试时发现...
  • 单链表排序单链表

    2018-05-08 19:45:23
    package list; public class SortedSinglyList&lt;T extends Comparable&... * 构造空排序单链表 */ public SortedSinglyList() { super(); // 直接调用单链表的构造方法,构造一个空的单链表 ...
  • 单链表选择排序

    千次阅读 2017-11-08 10:14:01
    //单链表选择排序 public class SelectSortList{ //单链表节点的定义 public static class Node{ public int value; public Node next; public Node(int data) { this.value=
  • 单链表冒泡排序

    2017-07-11 08:09:04
    一. 题目如题.代码请到我的代码库中下载 Point2Offer二.... * 单链表冒泡排序 * @author dingding * Date :2017-7-3 12:25 */ public class SortLink { public static void main(String[] args) { test1();
  • https://leetcode.com/problems/sort-list/ https://leetcode.com/problems/sort-list/discuss/46807/Quick-sort-Merge-sort-Python ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,708
精华内容 13,883
关键字:

单链表选择排序