精华内容
下载资源
问答
  • 链表实现选择排序

    2020-10-22 15:03:01
    C++链表实现选择排序代码如下: #include<iostream> #include<stdio.h> using namespace std; int main() { struct node{ int data; struct node *link; };//定义节点数据类型 int nodeNum;//...

    C++链表实现选择排序代码如下:

    #include<iostream>
    #include<stdio.h>
    
    using namespace std;
    
    int main()
    {
        struct node{
            int data;
            struct node *link;
        };//定义节点数据类型
    
        int nodeNum;//输入待建链表节点总数
        printf("请输入所建链表节点总数:\n");
        scanf("%d",&nodeNum);
    
        int data;
        struct node *head,*p,*q;
        printf("请输入%d个int类型数据:\n",nodeNum);
        scanf("%d",&data);//扫描头结点
        head=new struct node;
        head->data=data;
        head->link=0;
        q=head;
        int i;
        for(i=1;i<nodeNum;i++){
            scanf("%d",&data);//扫描后续节点
            p=new struct node;
            p->data=data;
            p->link=0;
            q->link=p;
            q=q->link;
        }
    
        struct node *r;
        int t;
        for(p=head;p->link!=0;p=p->link){
            q=p;
            for(r=p->link;r!=0;r=r->link)
                if(q->data>r->data)
                    q=r;
            if(q!=p){
                t=q->data;
                q->data=p->data;
                p->data=t;
            }
        }//选择排序算法
    
        printf("排序结果为:\n");
        p=head;
        while(p!=0){
            printf("%d ",p->data);//输出
            p=p->link;
        }
    
        while(head!=0){
            p=head;
            head=head->link;
            delete p;
        }//释放节点
    
        return 0;
    }
    
    展开全文
  • 快速排序的基本思想:从序列当中选择一个基准数在这里我们选择序列当中第一个数作为基准数将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧重复步骤1.2,直到所有子集当中只有一个元素...

    快速排序的基本思想:

    从序列当中选择一个基准数

    在这里我们选择序列当中第一个数作为基准数

    将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧

    重复步骤1.2,直到所有子集当中只有一个元素为止。

    以【4,2,5,3,7,9,0,1】为例,我们来模拟一趟快排的过程。

    1、初始化时,i指向链表首元素4;j = i +1,指向2。基准数字为当前i 指向的数字:4。

    j

    4

    2

    5

    3

    7

    9

    0

    1

    i

    2、随后开始循环,j 当前指向2,因为2小于4,所以要把2移动到前面去。按照我们的算法步骤操作:

    i ++,首先 i 向后移动一位,指向2

    swap(i, j) ,随后交换 i、j 位置的值,这里面是2和2自己交换

    j ++,然后 j 向后移动一位,指向5

    执行一次交换后的结果如下:

    j

    4

    2

    5

    3

    7

    9

    0

    1

    i

    3、接下来,由于 j 指向的值5 大于4,直接跳过,执行j++,此时 j 指向3

    j

    4

    2

    5

    3

    7

    9

    0

    1

    i

    4、 j 指向的值为3,小于4,仿照步骤2,我们再次执行一次交换移动过程。

    i ++,首先 i 向后移动一位,指向5

    swap(i, j) ,随后交换 i、j 位置的值,这里面是5和3交换

    j ++,然后 j 向后移动一位,指向7

    交换后的结果如下:

    j

    4

    2

    3

    5

    7

    9

    0

    1

    i

    5、 j指向的值为7,大于4,所以直接跳过,执行 j++,j 指向9

    j

    4

    2

    3

    5

    7

    9

    0

    1

    i

    6、同理,j 指向的值为9,也大于4,跳过,执行 j++,j 指向0

    j

    4

    2

    3

    5

    7

    9

    0

    1

    i

    7、 j 指向的值为0,小于4,执行一次交换过程

    i ++,首先 i 向后移动一位,指向5

    swap(i, j) ,随后交换 i、j 位置的值,这里面是5和0交换

    j ++,然后 j 向后移动一位,指向1

    交换后的结果如下:

    j

    4

    2

    3

    0

    7

    9

    5

    1

    i

    8、 j 指向的值为1,小于4,我们再执行一次交换过程

    i ++,首先 i 向后移动一位,指向7

    swap(i, j) ,随后交换 i、j 位置的值,这里面是7和1交换

    j ++,然后 j 向后移动一位,已经超过了链表的长度,不再向后移动。

    交换后的结果如下:

    j

    4

    2

    3

    0

    1

    9

    5

    7

    i

    9、最后,交换当前 i指向的值1,和4。得到【1、2、3、0、4、9、5、7】,一趟排序结束。

    j

    1

    2

    3

    0

    4

    9

    5

    7

    i

    我们发现,4的左边都是小于4的数字,右边都是大于4的数字。

    接下来,对左边和右边分别排序,不断递归下去,直到元素全部有序。

    // 链表结点类

    class Node():

    def __init__(self, item=None):

    self.item = item // 数据域

    self.next = None // 指针域

    // 链表类,生成链表以及定义相关方法

    class LinkList():

    def __init__(self):

    self.head = None

    // 生成链表,这里使用list来生成

    def create(self, item):

    self.head = Node(item[0])

    p = self.head

    for i in item[1:]:

    p.next = Node(i)

    p = p.next

    // 遍历显示

    def print(self):

    p = self.head

    while p != None:

    print(p.item, end=' ')

    p = p.next

    print()

    // 根据索引取值

    def getItem(self, index):

    p = self.head

    count = 0

    while count != index:

    p = p.next

    count += 1

    return p.item

    // 根据索引设值

    def setItem(self, index, item):

    p = self.head

    count = -1

    while count < index-1:

    p = p.next

    count += 1

    p.item = item

    // 互换

    def swapItem(self, i, j):

    t = self.getItem(j)

    self.setItem(j, self.getItem(i))

    self.setItem(i, t)

    def quicksortofloop(self, left, right):

    if left < right:

    // 初始化

    i = left

    j = i+1

    start = self.getItem(i)

    // 大循环条件,j不能超过链表长度

    while (j <= right):

    // 如果 j 指向的值大于等于基准数字,直接跳过

    while (j <= right and self.getItem(j) >= start):

    j += 1

    // 否则,j 指向的值小于基准,则交换

    if (j <= right):

    i += 1

    self.swapItem(i, j)

    self.print()

    j += 1

    self.swapItem(left, i)

    self.quicksortofloop(left, i-1)

    self.quicksortofloop(i+1, right)

    if __name__ == "__main__":

    L = LinkList()

    L.create([4, 2, 5, 3, 7, 9, 0, 1])

    L.quicksortofloop(0, 7)

    L.print()

    4 2 5 3 7 9 0 1

    4 2 3 5 7 9 0 1

    4 2 3 0 7 9 5 1

    4 2 3 0 1 9 5 7

    1 0 3 2 4 9 5 7

    0 1 3 2 4 9 5 7

    0 1 2 3 4 9 5 7

    0 1 2 3 4 9 5 7

    0 1 2 3 4 7 5 9

    0 1 2 3 4 5 7 9

    参考:https://www.cnblogs.com/wuxinyan/p/8615127.html

    参考:https://blog.csdn.net/u010429424/article/details/77776731

    展开全文
  • C++实现链表选择排序算法C++实现链表选择排序算法完整源码(定义,实现,main函数测试) C++实现链表选择排序算法完整源码(定义,实现,main函数测试) #include <iostream> using namespace std; ...

    C++实现对链表的选择排序算法完整源码(定义,实现,main函数测试)

    #include <iostream>
    using namespace std;
    
    // node defined
    class node {
     public:
        int data;
        node *link;
        node(int d) {
            data = d;
            link = NULL;
        }
    };
    
    // printing the linked list
    void print(node *head) {
        node *current = head;
        while (current != NULL) {
            cout << current->data << " ";
            current = current->link;
        }
        cout << endl;
    }
    
    // creating the linked list with 'n' nodes
    node *createlist(int n) {
        node *head = NULL;
        node *t = NULL;
        for (int i = 0; i < n; i++) {
            node *temp = NULL;
            int num;
            cin >> num;
            temp = new node(num);
            if (head == NULL) {
                head = temp;
                t = temp;
                continue;
            }
            if (t->link == NULL)
                t->link = temp;
            t = temp;
        }
        return head;
    }
    
    // performing selection sort on the linked list in an iterative manner
    void my_selection_sort_linked_list(node *&head) {
        node *min = head;  // throughout the algorithm 'min' is used to denote the
        node *current =
            min->link;  // 'current' refers to the current node we are scanning
        node *previous = min;  //'previous' refers to the node that is previous to
                               // the current node
        node *temp =
            NULL;  
    
        while (
            min->link !=
            NULL)  // so that all the nodes are scanned or until there exists a node
        {
            // pick the first node from the unsorted part and assume that it is the
            // minimum and then start scanning from the next node
    
            while (current != NULL)  // suppose you choose the min node to be X,
                                     // then scan starts from the (X+1)th node until
                                     // its NULL. current = (X+1)th node and min = X
            {
                if (current->data < min->data)  // if the current node is smaller
                                                // than the presumed node 'min'
                {
                    if (temp == NULL)  // temp stays null for the first iteration,
                                       // therefore it symbolizes that we are
                                       // scanning for the first time
                    {
                        if (previous ==
                            min)  // if the 'previous' is pointing to the 'min' node
                        {
                            // Update the pointers
                            head = current;  // update the head pointer with the
                                             // current node
                            min->link = current->link;
                            current->link = previous;
                            min = current;
                            current = previous->link;
                        } else  // if the 'previous' is not pointing to the 'min'
                                // node
                        {
                            // Update the pointers
                            head = current;  // update the head pointer with the
                                             // current node
                            previous->link = current->link;
                            current->link = min;
                            min = current;
                            current = previous->link;
                        }
                    } else  // if 'temp' is not NULL, i.e., its not the 1st
                            // iteration
                    {
                        temp->link = current;
                        previous->link = current->link;
                        current->link = min;
                        min = current;
                        current = previous->link;
                    }
                } else  // if the current node is greater than min, just move the
                        // previous and the current pointer a step further
                {
                    previous = previous->link;
                    current = current->link;
                }
            }
    
            // update the pointers. Set 'temp' to the last node in the sorted part.
            // Make 'min' move a step further so that 'min' points to the 1st node
            // of the unsorted part start the iteration again
            temp = min;
            min = min->link;
            previous = min;
            current = min->link;
        }
    }
    
    int main() {
        node *head = NULL;
        int n;
        cout << "enter the no. of nodes : ";  // taking input from user about the
                                              // number of nodes in linked list
        cin >> n;
        if (n == 0)
            return 0;
        head = createlist(n);  // creating the list
        cout << "original list is : ";
        print(head);                          // printing the original linked list
        my_selection_sort_linked_list(head);  // applying selection sort
        cout << "sorted list is : ";
        print(head);  // printing the sorted linked list
        return 0;
    }
    
    展开全文
  • 因为在以前做过数组的选择排序,所以本来以为链表差不多,但是在实际操作的时候出现了很多问题。 1.首先是怎么交换位置,诚然,利用改变指针的指向可以交换节点,但是我觉得可以通过交换结构体的内容 代码,结构体...

    在实现学生成绩(存入很多类型数据,如学号,成绩,课程号等)排序的时候,要根据正序输出。因为在以前做过数组的选择排序,所以本来以为链表差不多,但是在实际操作的时候出现了很多问题。

    1.选择排序的原理就是在这里插入图片描述

    2.首先是怎么交换位置,诚然,利用改变指针的指向可以交换节点。但是我觉得可以通过交换结构体的内容,而不动节点本身。

    typedef struct student{
        int sno;
        char sname[10];
        char sex;
        char major[10];
    }Student;
    
    typedef struct course{
        int cno1;
        char cname1[20];
        int classHours1;
        int cno2;
        char cname2[20];
        int classHours2;
        int cno3;
        char cname3[20];
        int classHours3;
    }Course;
    
    typedef struct courseGrade{
        int sno;
        int cno1;
        int score1;
        int cno2;
        int score2;
        int cno3;
        int score3;
    }CourseGrade;
    
    
    typedef struct allInformation{
        struct student student;*student;
        struct course course;
        struct courseGrade courseGrade;
    }AllInformation;
    
    typedef struct linknode{
        AllInformation a;
        struct linknode *next;
    }LinkStNode;//重点,只需要交换'a'
    

    3.在初始化指向结构体的指针时需要赋值 ,否则就成为悬空指针,后果不可预知。

    4.第一个for循环对应被比较的指针的移动,第二个for循环对应第二个比较指针的移动。第一个,第二个循环的结束条件都是是pt2!=NULL;

    5.注意,指向结构的指针(最外层的结构名)指向内容时,用**‘->’。下层结构用‘.’** 翻译为“的”。

    6.一个关键点是,pt1的内容和pt2内容的交换。因为基本思路是不交换节点,只交换节点的内容(之所以结构的嵌套也是为了实现这个思路),所以需要一个p存储pt1的内容(如同所有交换数值的操作)。这个时候p不能是指针。
    LinkStNode *p=pt1;//这是错的 LinkStNode p; p.a=pt1->a;//这是对的
    因为,如果将这里将pt1赋值给p,相当于将pt1指针赋值给指针p,pt1变化,p也会变化,所以要把p变为结构体而不是指针。

    因此,此函数如下

    LinkStNode* SortList(LinkStNode* pHeadNode){
        LinkStNode* pt1=NULL;
        LinkStNode* pt2=NULL;
        
        
        
        for(pt1=pHeadNode->next,pt2=pt1->next;
            pt2!=NULL;
            pt1=pt1->next,pt2=pt1->next
            ){
            for(;pt2!=NULL;pt2=pt2->next){if ((pt1->a.student.sno)>(pt2->a.student.sno)){
                LinkStNode p;//LinkStNode*必须初始化时便赋
                p.a=pt1->a;
                pt1->a=pt2->a;
                pt2->a=p.a;}
            }
         
        }
        return pHeadNode;
        }//链表的选择排序
    
    

    还有需求没有实现,任重而道远。

    展开全文
  • 链表选择排序算法功能实现演示

    万次阅读 2020-05-02 11:58:28
    //选择排序 traverse_list(pHead); //遍历输出 while(true){} return 0; } //创建单链表 pNode create_list() { int len; //用来存放有效节点数 int i; int val; //存放用户临时输入的节点数据 //我们首先要先生成...
  • //链表带头结点,用的额外的节点有点多,6个; void LinkedList::SelectSort(){  LinkNode *ptr = head->link;  LinkNode *pre_ptr = head;  LinkNode *q = ptr->link;  LinkNode *pre_q...
  • 链表选择排序

    2020-12-30 09:02:21
    用c简单实现了一下链表选择排序~ #include<stdio.h> #include<malloc.h> typedef struct list{ int data; list* next; }*listd; void pr(listd head){ //选择排序 listd q,p,r; int s; for(p=...
  • python 单向链表实现快速排序

    千次阅读 2018-11-27 16:23:24
    python 单向链表实现快速排序 快速排序的基本思想: 从序列当中选择一个基准数 在这里我们选择序列当中第一个数作为基准数 将序列当中的所有数依次遍历,比基准数大的位于其右侧,比基准数小的位于其左侧 重复...
  • 链表实现直接选择排序

    千次阅读 2012-07-18 20:54:44
    Description: 用链表实现直接选择排序 Function List: find(); 寻找链表中最小的结点并返回 change();交换链表中指定结点的位置 sort(); 调用前两个函数实现功能 **********************************************...
  • 为了简单起见,选择链表的第一个节点作为基准,然后进行比较,比基准小得节点放入左面的子链表,比基准大的放入右边的子链表。在对待排序链表扫描一遍之后,左边子链表的节点值都小于基准的值,右边子链表的值都大于...
  • 插入,选择排序链表实现及快速,希尔,冒泡排序算法实现
  • 包含选择排序,插入排序,冒泡排序,快速排序以及归并排序等
  • mysort()为直接插入排序,mysort2()为直接选择排序; 对于直接选择排序,我一开始是直接交换的结点里的数据,这个虽然是程序简单化了,但这和一个数组还有区别吗?所以我又改了交换结点,当然这就要烦的多了,一个...
  • 选择排序 数组和链表的优缺点 链表的优势、 链表的问题 常见的数组和链表操作的运行时间 需要在中间插入元素时,数组和链表哪个更好呢? 数组和链表哪个用得更多呢 数组和链表习题 选择排序 python代码实现...
  • 本节书摘来自华章计算机《算法基础》一书中的第3章,第3.6节,作者:(美)罗德·斯蒂芬斯(Rod Stephens)著,更多章节内容可以访问云栖社区“华章计算机...下面的伪代码显示了选择排序算法的单向链表实现方法(默...
  • mysort()为直接插入排序,mysort2()为直接选择排序; 对于直接选择排序,我一开始是直接交换的结点里的数据,这个虽然是程序简单化了,但这和一个数组还有区别吗?所以我又改了交换结点,当然这就要烦的多了,一个有...
  • 目录插入排序选择排序归并排序 插入排序 leetcode 147 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ ...
  • 选择排序链表实现

    2013-09-09 19:48:10
    #include using namespace std; typedef struct Node { double data; struct Node *next; }*LinkList,LinkNode; void SelectSort(LinkList &L) //同样的错误犯了两次啊 借鉴啊 { LinkNode *h=L,*p,*q,*r,*s;
  • 这是根据数据结构书上讲的线性表的排序方法改写成链表,上面有简单的测试程序。
  • 用c语言实现链表排序,利用选择排序的思想,可以供大家学习。
  • 实验题目: 排序算法实现与比较  实验环境: Visual C++ 6.0    实验八: 实验目的和要求:熟悉多种排序算法,理解每种排序算法思想,掌握排序算法的基本设计方法,掌握排序算法时间复杂度和空间...
  • 本代码实现了单链表的创建(头插法与尾插法)、单链表的遍历、插入节点、删除节点、 判断表空表满、求表长度、选择算法排序等功能
  • C语言单链表实现选择排序

    千次阅读 2019-03-12 12:00:27
    链表实现选择排序有两种方法,一种是交换节点内的数据,比较简单。我这里使用的是第二种方法,交换节点。 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #...
  • 在前面的博客中,已经写了关于数组和链表选择排序、冒泡排序和插入排序。在这里,再次补充快速排序。快排的应用场景很多,其中面试中广泛使用的就是在无序数集中查找第K个大(或小)的数值。下面,我们来处理一下该...
  • 给定一个无序单链表,实现单链表的选择排序(按升序排序)。 输入描述: 第一行一个整数 n,表示单链表的节点数量。 第二行 n 个整数 val 表示单链表的各个节点。 输出描述: 在给出的函数内返回给定链表的头指针...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 933
精华内容 373
关键字:

链表实现选择排序