精华内容
下载资源
问答
  • 单向链表排序

    2019-02-15 17:19:42
    一、冒泡排序简述 1、概念 冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。  它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...

    一、冒泡排序简述

    1、概念

    冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
      它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。

    2、实例分析

    以数组为例进行说明:
      数组a[4] = {4,3,2,1}

    从前向后依次比较两个元素的大小,如果顺序错误就交换它们。经过这样一轮,最大的元素就被交换到了数组的顶端,好像是最大的元素“浮”上去一样。经过这样一轮,最后的一个元素的已经确定。a[4] = {3,2,1,4}

    再次重复上边的操作,只不过因为上一轮最后一个元素已经确定,所以这一次比较的终点(以此为界,不能超过此界)就是上一轮的最后一个元素。也就是,第二轮的比较中,数组最后一个元素没有参与比较。第二轮比较中的最后一个元素是倒数第二个元素。经过这样一轮比较,倒数第二个元素也被确定。a[4] = {2,1,3,4}

    重复这样的操作,直到数组的第二个元素被确定。因为除了第一个元素外,所有的元素都被锁定,所以第一个元素实际上也被确定。到此为止,排序完成。a[4] = {1,2,3,4}

    3、冒泡排序的关键
    <1> 每经过一轮的排序,一个最大的元素被“浮”到对应的位置。随之,下一次比较的终点也需要向前移一个元素。
    <2> 当正数第二个元素被确定的时候,冒泡排序完成。

    二、冒泡法应用于单向链表排序

    1、实例展示
    ① 初始链表

    在这里插入图片描述
    ② 第一轮排序
    在这里插入图片描述
    ③ 第二轮排序
    在这里插入图片描述
    ④ 第三轮排序
    在这里插入图片描述
    算法流程图
    在这里插入图片描述

    #include <stdio.h>
    #include <malloc.h>
    
    /* 排序状态取值表 */
    typedef enum
    {
        SORT_OK,    /* 排序成功标志 */
        SORT_ERR    /* 排序失败标志 */
    }SORTSTATE;        
    
    /* 接点结构体 */
    struct node{
        struct node * pnext;
        unsigned int value;
    };
    
    typedef struct node Node;
    
    SORTSTATE sort(Node * * chainhead);
    
    /** @函数功能:测试单向链表排序功能
      * @输入参数:无
      * @输出参数:无用
      */
    int main(void)
    {
        Node * head,* p;
        SORTSTATE status;
    
        /* 构建单向链表 */
        p = (Node *)malloc(sizeof(Node));
        head = p;                                    /* 保存链表头部 */
        p->value = 5;
        p->pnext = (Node *)malloc(sizeof(Node));
    
        p = p->pnext;
        p->value = 97;
        p->pnext = (Node *)malloc(sizeof(Node));
    
        p = p->pnext;
        p->value = 7;
        p->pnext = (Node *)malloc(sizeof(Node));
    
        p = p->pnext;
        p->value = 65;
        p->pnext = (Node *)malloc(sizeof(Node));
    
        p = p->pnext;
        p->value = 12;
        p->pnext = (Node *)malloc(sizeof(Node)); 
    
        p = p->pnext;
        p->value = 1;
        p->pnext = NULL;                            /* 链尾初始化为空 */
    
        /* 打印链表的内容 */
        p = head;
        while(p != NULL){
            printf("%4d",p->value);
            p = p->pnext;
        }
        printf("\n");
    
        /* 链表排序 */
        status = sort(&head);
        if(status == SORT_ERR){
            printf("Chain is wrong!\n");
        }
        
        /* 打印链表的内容 */
        p = head;
        while(p != NULL){
            printf("%4d",p->value);
            p = p->pnext;
        }
        printf("\n");
    
        return 0;
    }
    
    
    /** @函数功能:单向链表排序
      * @输入参数:指向链表头部的指针
      *        注意:指向指针的指针可以修改指针的指向
      * @输出参数:SORTSTATE 排序成功与否状态
      */
    SORTSTATE sort(Node * * chainhead)
    {
        Node * head,                                    /* 当前比较接点的上一个接点 */
             * first,                                    /* 当前比较接点 */
             * second,                                    /* 当前参与比较的另一个接点 */
             * end;                                        /* 当前比较接点的终点
                                                         * 终点意味着从终点开始往后的
                                                         * 链表排序已经确定,只需要将
                                                         * 终点前的所有接点按照冒泡法
                                                         * 排序,排序就将完成。
                                                         */
    
        if(*chainhead == NULL)                            /* 链表是否为空 */
            return SORT_ERR;
        if((*chainhead)->pnext == NULL)                    /* 链表是否就只有一个接点 */
            return SORT_OK;
    
        end = NULL;                                        /* 第一轮冒泡排序的终点接点值为NULL */
    
        /* 冒泡法排序,可能有很多轮次 */
        while(end != (*chainhead)->pnext){                /* 如果排序的终点等于接点的第二个地址,
                                                         * 也就是说从第二个接点开始所有的接点
                                                         * 都已经按照从小到大的顺序确定了位置。
                                                         * 显然,剩下的唯一一个“第一接点”位置
                                                         * 也就确定了。所有排序全部完成。
                                                         */
    
            /* 首先比较位于头部的两个接点,由于位于头部,
             * 与其他接点不一样,需要放在循环外边,单独处理。
             */
            first =   *chainhead;                        /* 第一个比较接点是链表头部指向的接点 */
            second = first->pnext;                        /* 第二个比较接点是紧邻的第二个接点 */
            
            /* 是否需要更改链表的连接顺序 */
            if(first->value > second->value){            
                *chainhead = second;                    /* 更改链表头部的指向 */    
                /* 重新连接链表,就相当于对链表排序 */
                first->pnext = second->pnext;            
                second->pnext = first;            
            }
    
            /* 移动比较接点到下两个接点 */
            head = *chainhead;                            /* 当前比较接点的上一个接点则是头部接点 */
            first = head->pnext;                        /* 当前比较接点 */
            second = first->pnext;                        /* 当前参与比较的另一个接点 */
            
            while(second != end)                        /* 此轮的比较是否结束 */
            {
                /* 是否需要更改链表的连接顺序 */
                if(first->value > second->value){    
                    /* 重新连接链表,就相当于对链表排序 */
                    head->pnext = second;    
                    first->pnext = second->pnext;
                    second->pnext = first;
                    
                }
                /* 移动比较接点到下两个接点 */
                head = head->pnext;
                first = head->pnext;
                second = first->pnext;
            }
    
            end = first;                                /* 一轮排序完成,结束接点位置上移一个 */
        }
    
        return SORT_OK;                                    /* 排序成功 */
    

    来源:https://www.cnblogs.com/amanlikethis/articles/3783670.html?tdsourcetag=s_pcqq_aiomsg

    展开全文
  • C/C++ 编写函数,通过输入单向链表的头指针,对链表的value进行排序,返回排序单向链表的头指针
  • 单向链表排序-归并排序

    千次阅读 2013-04-21 23:31:05
    链表排序中使用归并排序:归并排序不仅保持了它的 O( nlog(n) ) 的时间复杂度,而且它在数组排序中广受诟病的空间复杂度,在链表排序中从 O(n) 降低到 O( log(n) )。  对于单向链表的二路归并排序,首先是要找到...

    链表排序中使用归并排序:归并排序不仅保持了它的 O( nlog(n) ) 的时间复杂度,而且它在数组排序中广受诟病的空间复杂度,在链表排序中从 O(n) 降低到 O( log(n) )。

       对于单向链表的二路归并排序,首先是要找到链表的中间节点,将链表等分。我们可以使用快慢指针的方式找到链表的中间节点,即一个指针以一个步长移动,另一个指针使用两个步长移动,当快指针到结尾位置时,慢指针正好在中间位置。接下来是对两个链表进行归并排序。


    源程序:

    //filename : linklist.h
    
    #ifndef __LINKLIST_H_H_
    #define __LINKLIST_H_H_
    
    struct LinkList{
    	struct LinkList *next;
    	int value;
    };
    
    extern struct LinkList *createLinkList(int num);
    
    extern void printLinkList (struct LinkList *list);
    
    extern struct LinkList *merge(struct LinkList *first, struct LinkList *second);
    
    extern struct LinkList *mergeSort(struct LinkList *head);
    
    
    #endif

    源程序:

    //filename: linklist.cpp
    
    #include "linklist.h"
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>
    
    /**
     *创建一个带头结点的单向链表
     *@parm[in]: num 链表节点个数
     *@return : 链表头结点 
    */
    struct LinkList *createLinkList(int num)
    {
    	if (num <= 0) {
    		printf("could not create LinkList, the input number %d should biger than 0\n");
    		return NULL;
    	}
    	struct LinkList *head = (struct LinkList *)malloc(sizeof(struct LinkList));
    	if (NULL == head) {
    		printf("Could not malloc enough space\n");
    		exit(1);
    	}
    	struct LinkList *current = head;
    
    	srand( (int)time(0) );
    	for (int i = 0; i < num; ++i) {
    		struct LinkList *temp = (struct LinkList *)malloc(sizeof(struct LinkList));
    		temp->value = rand()%100;
    		current->next = temp;
    		current = current->next;
    	}
    	current->next = NULL;
    	return head;
    }
    
    /**
     *打印输出链表
     *@para[in]: list 有序链表首地址指针 
    **/
    void printLinkList (struct LinkList *list)
    {
    	while (list != NULL) {
    		printf("%6d  ", list->value);
    		list = list->next;
    	}
    }
    
    /**
     * 按递增顺序,将两个有序单向链表,归并成一个有序单向链表
     * @para[in]: first  有序单向链表首地址指针
     * @para[in]: second 有序单向链表首地址指针
     * @return:   返回排好序后的链表首地址指针
    */
    struct LinkList *merge(struct LinkList *first, struct LinkList *second)
    {
    	struct LinkList *tempsort = (struct LinkList *)malloc(sizeof(struct LinkList));
    	if (!tempsort) {
    		printf("Could not malloc enough space\n");
    		exit(1);
    	}
    	struct LinkList *curr = tempsort;
    
    	while (first != NULL && second != NULL) {
    		if (first->value <= second->value) {
    			curr->next = first;
    			first = first->next;
    
    		} else {
    			curr->next = second;
    			second = second->next;
    		}
    		curr = curr->next;
    	}
    	if ( NULL != first) {
    		curr->next = first;
    	}
    	if (NULL != second) {
    		curr->next = second;
    	}
    	curr = tempsort->next;
    	free(tempsort);
    	return curr;
    }
    
    /**
     *使用快慢指针,等分单向链表,并调用merge函数对链表排序
     *@para[in/out]: head有序单向链表首地址指针
     *@return: 返回排好序的单链表首地址地址
    **/
    struct LinkList *mergeSort(struct LinkList *head)
    {
    	struct LinkList *first = head;
    	struct LinkList *second = head;
    
    	if (NULL == first|| NULL == second) {
    		return first;
    	}
    	
    	//使用快慢指针将链表等分为两个链表
    	while (second->next != NULL && second->next->next != NULL) {
    		first = first->next;
    		second = second->next->next;
    	}
    	if (first->next != NULL) {
    		second = first->next;
    		first->next = NULL;
    		first = head;
    	}
    
    	//只剩一个节点时,返回
    	if (first == second) {
    		return first;
    	}
    
    	return merge(mergeSort(first), mergeSort(second));
    }

    源程序:

    //filename: main.cpp
    
    #include <stdio.h>
    #include <stdlib.h>
    
    #include "linklist.h"
    
    
    int main()
    {
    	int num = 20;
    	struct LinkList *head = NULL;
    
    	head = createLinkList(num);
    	printf("Before sort: \n");
    	printLinkList(head->next);
    	struct LinkList * headnext = mergeSort(head->next);
    	head->next = headnext;
    	printf("After sort\n");
    	printLinkList(head->next);
    	return 0;
    }



    展开全文
  • 归并排序改变链接 ...对单向链表排序有2种形式,只改变节点的值 和 只改变链接// 节点 struct ListNode { int val; ListNode* next; ListNode(int v, ListNode* n = NULL) { val = v; next = n;

    对单向链表的排序有2种形式,只改变节点的值只改变链接

    // 节点
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int v, ListNode* n = NULL) {
            val = v;
            next = n;
        }
    };

    本文链接:单向链表排序:快速排序和归并排序

    参考资料链接:
    链表排序(冒泡、选择、插入、快排、归并、希尔、堆排序)

    1. 归并排序(改变链接)

    归并排序是最适合单链表排序的算法,因为两个链表的归并比较简单,和数组的归并过程思路相同。
    需要注意的是:如何找到链表的中点?
    通过2个快慢指针,快指针每一步走2个节点,慢指针每一步走1个节点,当快指针到达链表尾部时,慢指针到达链表的中间节点。

    class MergeSort {
    public:
        static ListNode* ListMergeSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return pHead;
            ListNode* pFast = pHead;
            ListNode* pSlow = pHead;
            // 找到位于中间的节点,快慢指针,快的到结尾,慢的到中点
            while (pFast != NULL && pFast->next == NULL) {
                pFast = pFast->next->next;
                pSlow = pSlow->next;
            }
            pFast = pSlow;
            pSlow = pSlow->next; // 分割成2段
            pFast->next = NULL;
            pHead = ListMergeSort(pHead);
            pSlow = ListMergeSort(pSlow);
            pHead = merge(pHead, pSlow);
            return pHead;
        };
    private:
        static ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
            if (pHead1 == NULL || pHead2 == NULL) {
                return pHead1 == NULL ? pHead2 : pHead1;
            }
            // 找出合并后的链表头
            ListNode* pHead = NULL;
            if (pHead1->val > pHead2->val) {
                pHead = pHead2;
                pHead2 = pHead2->next;
            } else {
                pHead = pHead1;
                pHead1 = pHead1->next;
            }
            // 将2个链表中值较小的节点依次链接到结果链表中
            ListNode* pHead_orgin = pHead;
            while (pHead1 != NULL && pHead2 != NULL) {
                if (pHead1->val > pHead2->val) {
                    pHead->next = pHead2;
                    pHead2 = pHead2->next;
                } else {
                    pHead->next = pHead1;
                    pHead1 = pHead1->next;
                }
                pHead = pHead->next;
            }
            if (pHead1 == NULL)
                pHead->next = pHead2;
            else
                pHead->next = pHead1;
            return pHead_orgin;
        };
    };

    2. 快速排序(改变链接)

    只改变链接的指向。
    将比基元(第一个节点)小的值,链接到一个左链表中;比基元大的值,链接到一个右链表中;
    将左链表,基元,右链表链接起来。

    对一段链表执行划分过程时,头节点可能发生改变以及终止节点可能是非空的,因此对一段链表的划分过程需要给出
    前驱节点(指向头节点)和终止节点(标志结束)
    故对传入划分函数的一次链表划分处理不包括第一个节点和最后一个节点的。(双开区间)

    class QuickSort {
    public:
        static ListNode* ListQuickSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return pHead;
            ListNode headPrev(0, pHead); // pHead 的前驱节点
            ListQuickSort(&headPrev, pHead, NULL);
            return headPrev.next;
        }
    private:
        static void ListQuickSort(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
            // 处理过程不涉及 pHeadPrev 和 pTail
            if (pHead == pTail || pHead->next == pTail)
                return;
            ListNode* pMid = Partation(pHeadPrev, pHead, pTail);
            ListQuickSort(pHeadPrev, pHeadPrev->next, pMid);
            ListQuickSort(pMid, pMid->next, pTail);
        };
    
        static ListNode* Partation(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
            int key = pHead->val; // 选第一个节点为基元
            ListNode nodeL(0), nodeR(0);
            ListNode* pLeftPrev = &nodeL; // 小于基元的链表
            ListNode* pRightPrev = &nodeR; // 大于等于基元的链表
            for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
                if (pNode->val < key) {
                    pLeftPrev->next = pNode;
                    pLeftPrev = pNode;
                } else {
                    pRightPrev->next = pNode;
                    pRightPrev = pNode;
                }
            }
            pRightPrev->next = pTail; // 保证子链表继续和后面的相连
            pLeftPrev->next = pHead; // 基元节点链接
            pHead->next = nodeR.next;
            pHeadPrev->next = nodeL.next; // 链表头节点
            return pHead;
        };
    };

    3. 快速排序(改变节点值)

    由于链表只能顺序索引,故不能使用数组划分的方法。
    将比基元小的节点的值,依次和基元后的节点的值交换。
    如 5->3->6->4->7->2
    5 为基元
    3 < 5: swap(3, 3) ,(起始交换位置为基元的下一个节点,即第2个节点)
    6 > 5: continue;
    4 < 5: swap(6, 4) (交换位置后移,交换4和第3个节点的值)
    7 > 5: continue
    2 < 5: swap(4, 2) (交换位置后移,交换2和第4个节点的值)

    循环结束 swap(5, 2) (交换基元值和第4个节点的值)

    最后得到:2->3->4->5->6->7

    class QuickSortValue {
    public:
        static void QuickSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return;
            QuickSort(pHead, NULL);
        }
    private:
        static void QuickSort(ListNode* pHead, ListNode* pTail) {
            if (pHead == pTail || pHead->next == pTail)
                return;
            ListNode* pMid = Partation(pHead, pTail);
            QuickSort(pHead, pMid);
            QuickSort(pMid->next, pTail);
        }
        static ListNode* Partation(ListNode* pHead, ListNode* pTail) {
            if (pHead == pTail || pHead->next == pTail)
                return pHead;
            ListNode* pPivot = pHead; // 基元
            int key = pHead->val;
            for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
                if (pNode->val < key) {
                    pPivot = pPivot->next; // 将比基元小的值,依次交换到前面
                    swap(pNode, pPivot);
                }
            }
            swap(pHead, pPivot);
            return pPivot;
        }
        static void swap(ListNode* pA, ListNode* pB) {
            int temp = pA->val; pA->val = pB->val; pB->val = temp;
        }
    };

    4. 所有源码和测试函数

    #include <iostream>
    #include <stdlib.h>
    #include <time.h>
    using namespace std;
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int v, ListNode* n = NULL) {
            val = v;
            next = n;
        }
    };
    void PrintList(ListNode* pHead) {
        while (pHead != NULL) {
            cout << pHead->val << " ";
            pHead = pHead->next;
        }
        cout << endl;
        return;
    }
    class MergeSort {
    public:
        static ListNode* ListMergeSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return pHead;
            ListNode* pFast = pHead;
            ListNode* pSlow = pHead;
            // 找到位于中间的节点,快慢指针,快的到结尾,慢的到中点
            while (pFast != NULL && pFast->next == NULL) {
                pFast = pFast->next->next;
                pSlow = pSlow->next;
            }
            pFast = pSlow;
            pSlow = pSlow->next; // 分割成2段
            pFast->next = NULL;
            pHead = ListMergeSort(pHead);
            pSlow = ListMergeSort(pSlow);
            pHead = merge(pHead, pSlow);
            return pHead;
        };
    private:
        static ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
            if (pHead1 == NULL || pHead2 == NULL) {
                return pHead1 == NULL ? pHead2 : pHead1;
            }
            // 找出合并后的链表头
            ListNode* pHead = NULL;
            if (pHead1->val > pHead2->val) {
                pHead = pHead2;
                pHead2 = pHead2->next;
            } else {
                pHead = pHead1;
                pHead1 = pHead1->next;
            }
            ListNode* pHead_orgin = pHead;
            while (pHead1 != NULL && pHead2 != NULL) {
                if (pHead1->val > pHead2->val) {
                    pHead->next = pHead2;
                    pHead2 = pHead2->next;
                } else {
                    pHead->next = pHead1;
                    pHead1 = pHead1->next;
                }
                pHead = pHead->next;
            }
            if (pHead1 == NULL)
                pHead->next = pHead2;
            else
                pHead->next = pHead1;
            return pHead_orgin;
        };
    };
    
    class QuickSort {
    public:
        static ListNode* ListQuickSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return pHead;
            ListNode headPrev(0, pHead); // pHead 的前驱节点
            ListQuickSort(&headPrev, pHead, NULL);
            return headPrev.next;
        }
    private:
        static void ListQuickSort(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
            if (pHead == pTail || pHead->next == pTail)
                return;
            ListNode* pMid = Partation(pHeadPrev, pHead, pTail);
            ListQuickSort(pHeadPrev, pHeadPrev->next, pMid);
            ListQuickSort(pMid, pMid->next, pTail);
        };
    
        static ListNode* Partation(ListNode* pHeadPrev, ListNode* pHead, ListNode* pTail) {
            int key = pHead->val; // 选第一个节点为基元
            ListNode nodeL(0), nodeR(0);
            ListNode* pLeftPrev = &nodeL;
            ListNode* pRightPrev = &nodeR;
            for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
                if (pNode->val < key) {
                    pLeftPrev->next = pNode;
                    pLeftPrev = pNode;
                } else {
                    pRightPrev->next = pNode;
                    pRightPrev = pNode;
                }
            }
            pRightPrev->next = pTail; // 保证子链表继续和后面的相连
            pLeftPrev->next = pHead; // 基元节点链接
            pHead->next = nodeR.next;
            pHeadPrev->next = nodeL.next;
            return pHead;
        };
    };
    
    class QuickSortValue {
    public:
        static void QuickSort(ListNode* pHead) {
            if (pHead == NULL || pHead->next == NULL)
                return;
            QuickSort(pHead, NULL);
        }
    private:
        static void QuickSort(ListNode* pHead, ListNode* pTail) {
            if (pHead == pTail || pHead->next == pTail)
                return;
            ListNode* pMid = Partation(pHead, pTail);
            QuickSort(pHead, pMid);
            QuickSort(pMid->next, pTail);
        }
        static ListNode* Partation(ListNode* pHead, ListNode* pTail) {
            if (pHead == pTail || pHead->next == pTail)
                return pHead;
            ListNode* pPivot = pHead; // 基元
            int key = pHead->val;
            for (ListNode* pNode = pHead->next; pNode != pTail; pNode = pNode->next) {
                if (pNode->val < key) {
                    pPivot = pPivot->next; // 将比基元小的值,依次交换到前面
                    swap(pNode, pPivot);
                }
            }
            swap(pHead, pPivot);
            return pPivot;
        }
        static void swap(ListNode* pA, ListNode* pB) {
            int temp = pA->val; pA->val = pB->val; pB->val = temp;
        }
    };
    
    int main() 
    {
        srand(time(0));
        const int N = 30;
        ListNode* pHead = NULL;
        for (int i = 0; i < N; i++) {
            if (pHead == NULL) {
                pHead = new ListNode(rand() % 100 + 1, NULL);
            }
            else {
                ListNode* tempNode = new ListNode(rand() % 100 + 1, pHead);
                pHead = tempNode;
            }
        }
        PrintList(pHead);
        pHead = MergeSort::ListMergeSort(pHead); // merge-sort
       // pHead = QuickSort::ListQuickSort(pHead); // quick-sort-swap-node
       //QuickSortValue::QuickSort(pHead); // quick-sort-swap-value
        PrintList(pHead);
    }
    展开全文
  • 单向链表排序(link-sort.cpp) 题目描述 输入N个不下降的整数,有一个整数X,把X插入到N个数中,使N+1个数仍然是不下降序列。 输入 第1行:整数N 第2行:N个空格分开的整数,以不降序排列。 第3行:整数X 输出 第1...

    一、题目描述

    单向链表排序(link-sort.cpp)
    题目描述
    输入N个不下降的整数,有一个整数X,把X插入到N个数中,使N+1个数仍然是不下降序列。

    输入
    第1行:整数N
    第2行:N个空格分开的整数,以不降序排列。
    第3行:整数X

    输出
    第1行:N+1个空格分开的整数,以不降序排列。

    样例输入
    5
    0 2 4 6 8
    3


    样例输出
    0 2 3 4 6 8

    二、分析

    这一道题完全可以用数组来做,而且用数组来做的话,难度会大幅度地降低,但是为了达到训练的目的,我们还是
    自觉一点,用链表来做............
    我们先建立一个结构体,
    <span style="font-size:18px;">struct node{
    	int x;
    	node *next;
    };
    </span>

    node *next是定义的一个结构体指针,然后定义node *head,*t,*now,再进行输入
    <span style="font-size:18px;">        int n,m,i;
    	node *head,*now,*t;
    	scanf("%d",&n);
    	head=new node;
    	scanf("%d",&head->x);
    	head->next=NULL;
    	now=head;
    	for(i=2;i<=n;i++)
    	{
    		t=new node;
    		scanf("%d",&t->x);
    		t->next=NULL;
    		now->next=t;
    		now=t;
    	}
    	scanf("%d",&m);</span>

    用链表存数据比较复杂,需要一步一步来,每一步都要理解透彻。
    如果我们再分析一下题目的话,就可以发现,在输出的时候进行比较就可以了,就不需要对数据进行排序。
    <span style="font-size:18px;">for(now=head;now!=NULL;now=now->next){
    		printf("%d ",now->x);
    		if(now->x<=m&&now->next->x>=m)
    			printf("%d ",m);
    	}</span>

    但是这种写法的代码几乎没有分,因为当数据是:
    5
    1 2 2 2 4
    2
    以上程序输出的结果为:1 2 2 2 2 2 2 2 4 ,就会有重复的情况。
    于是,我们加了一个int f=0来进行判重,输出的时候加一个判断语句就可以了。
    <span style="font-size:18px;">for(now=head;now!=NULL;now=now->next){
    		printf("%d ",now->x);
    		if(now->x<=m&&now->next->x>=m&&f==0){
    			printf("%d ",m);
    			f=1;
    		}
    }</span>
    然而,程序还是错了,而且还有运行错误,因为当数据是:
    2            2
    1 2  或   1 2
    0       3
    程序的判断就会有越界的情况,产生运行错误。
    AC代码:
    <span style="font-size:18px;">for(i=1,now=head;now!=NULL;now=now->next,i++){
    		if(i==1&&now->x>=m&&f==0){
    			printf("%d ",m);
    			f=1;
    		}
    		printf("%d ",now->x);
    		if((now->next==NULL&&now->x<=m&&f==0)||(now->x<=m&&now->next->x>=m&&f==0)){
    			printf("%d ",m);
    			f=1;
    		}
    }</span>


    展开全文
  • 利用快排对单向链表排序

    千次阅读 2018-08-02 17:08:08
    利用快排对单向链表进行排序,左右指针法和挖坑法都是不能使用的,因为这两种方法都要从最后往前进行查找,但是链表是双向的,往前面走是不可能的,所以只能采用前后指针法。 struct ListNode { int _val; ...
  • alg : 单向链表排序 on drv

    千次阅读 2013-06-05 14:15:50
    单向链表排序迁移到驱动层, 验证通过(组合: (升序/降序) *(链表回环/非回环)) 如果算法实现需要确认, 还是在应用层先验证完, 再迁入驱动层好些. 能节省大量时间. 迁移(应用层 => 驱动层)过程中的修改点: ...
  • alg : 单向链表排序

    千次阅读 2013-05-31 00:37:34
    采用的是冒泡排序 + ...支持单向链表回环, 非回环. 支持单向链表升序,降序排列. 排序函数: BOOL ListSort(PNODE * ppNodeHead, BOOL bSortBySmallToBig) { BOOL bListIsLoop = FALSE; ///链表是否回环 BOOL
  • 单向链表排序问题

    2016-04-04 22:42:00
    1 typedef struct node 2 { 3 int data; 4 struct node* next; 5 }Node; ...链表排序:基本思想是选择排序 转载于:https://www.cnblogs.com/chuanyang/p/5353217.html
  • 使用单向链表对字符串进行排序,并以从小到大的顺序显示出来。
  • #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;time.h&gt; struct node { int num; struct node * next; }; typedef struct node Node;...void creat_l...
  • [Asm] 纯文本查看 复制代码#include#include//为动态分配提供函数库typedef struct node {int num;//数据域struct node *next;...//排序void print();//输出node *head = NULL;//初始化链表头指针int main(vo...
  • LinkList* LinkListBubbleSort(LinkList* pHead) { LinkList* pCurr = (LinkList *)NULL; LinkList* pPost = (LinkList *)NULL; LinkList* pFirst = (LinkList *)NULL; LinkList* pPrev = (LinkList
  • 归并排序: 来自网上一篇博文,先贴上链接,后期将会上传个人见解: http://blog.sina.com.cn/s/blog_78a4bd490101fow8.html 转载于:https://www.cnblogs.com/Frank-C/p/4813670.html...
  • 最近在完成一个学生管理系统的程序,用的是链表,还差排序这一块就完成了,想用的是冒泡排序,但在交换节点时遇到了困难,难以实现,所以在这里求助,谢谢,希望能得到一个代码的示范
  • LinkList* LinkListInsertSort(LinkList* pHead) { LinkList *pFirst = ... /* 原链表剩下未排序节点的头指针 */ LinkList *pCurrInsert = (LinkList *)NULL; /* 无序链表中当前待插入节点 */ LinkList *pPrev
  • 网上看到一段链表排序代码,看的很迷糊,有没有大侠配上注释来给菜鸟详细说明一下啊,跪谢~~ ///////////排序,指针做行参 link *Sort1(link *head) { link *h, *p, *q, *r, *s; h=p=(link *)malloc(sizeof...
  • 单向链表排序(冒泡)

    千次阅读 2006-02-24 16:30:00
    =head->next->next) /* p2作为尾指针控制p1循环,采用下沉法排序,从head->next开始排序*/   {  while(p1->next!=p2)   {  if (p1->count<p1->next->count)  { p3->next=p1->next;  p1->next=p1->...
  • C#单向链表排序

    2019-10-06 18:43:37
    C#的单向链表排序一、创建无序单向链表二、排序方法(按节点的值从小到大排序)1、暴力排序2、插入排序 一、创建无序单向链表 首先,要创建一些无序的单向链表用于测试。 public class ListNode { public int val...
  • 排序单向链表

    2018-12-12 17:55:06
    使用快速排序算法,对单向链表排序 题目: 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。 示例 1: 输入: 4-&gt;2-&gt;1-&gt;3 输出: 1-&gt;2-&gt;3-&gt;4 ...
  • 单向链表的插入排序

    2019-05-27 20:49:02
    题目:使用插入排序给单向链表排序。 题目来源:LeetCode--147. Insertion Sort List 原题目:Sort a linked list using insertion sort. A graphical example of insertion sort. The partial sorted list ...
  • c++单向链表排序 河北联合大学 2011-2012 第 2 学期 软 件 设 计 基 础 - C + + 课程设计报告 设计名称 设计一个处理单向链表的程序链表的排 序 姓 名 王 学 增 学 号 201005100206 专业班级 土木工程 1 班 学 院 ...

空空如也

空空如也

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

单向链表排序