您的位置:新葡亰496net > 奥门新萄京娱乐场 > 新葡亰496net:排序算法,Python实现链表

新葡亰496net:排序算法,Python实现链表

发布时间:2019-11-09 07:53编辑:奥门新萄京娱乐场浏览(167)

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    链表是编程中的一种常用数据结构,具有很强的灵活性。由于python中不存在有指针,这里将使用python中的引用来实现链表。

    [LeedCode OJ]#21 Merge Two Sorted Lists

     

     

    题意:

    给定两个已经排好序的链表,现在要求把这两个链表归并成一个新的有序链表

     

    思路:

    由于两个链表都是有序的,所以我们只需要两个链表都从头结点开始,比较其结点中值的大小,每次选值较小的结点加入目标链表中。

     

     

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution
    {
     public:
      ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
      {
       ListNode *l3 = new ListNode(0);
       ListNode *newlist = l3;
       while(l1&&l2)
       {
        if(l1->val<=l2->val)
        {
         l3->next = l1;
         l1 = l1->next;
        }
        else
        {
         l3->next = l2;
         l2 = l2->next;
        }
        l3 = l3->next;
       }
       l3->next = l1?l1:l2;
       return newlist->next;
      }
    };
    

     

     

    OJ]#21 Merge Two Sorted Lists 题意: 给定两个已经排好序的链表,现在要求把这两个链表归并成一个新的有序链表 思路: 由于两个链表都...

    1. /* //对于很小的数源,插入排序比快速排序好,此时,插入排序速度快也稳定。
    2. //插入排序只用在小的或是非常接近排好序的输入数据上。

    3. ==========================

    4. 功能:直接插入排序
    5. 返回:指向链表表头的指针
    6. ==========================
    7. */
    8. /*
    9. 直接插入排序的基本思想就是假设链表的前面n-1个节点是已经按键值
    10. (就是用它排序的字段,我们取学号num为键值)排好序的,对于节点n在
    11. 这个序列中找插入位置,使得n插入后新序列仍然有序。按照这种思想,依次
    12. 对链表从头到尾执行一遍,就可以使无序链表变为有序链表。
    13. 单向链表的直接插入排序图示:
    14. ---->[1]---->[3]---->[2]...---->[n]---->[NULL]
    15. head1->next3->next2->nextn->next
    16. ---->[1]---->[NULL](从原链表中取第1个节点作为只有一个节点的有序链表)
    17. head
    18. 图11
    19. ---->[3]---->[新葡亰496net:排序算法,Python实现链表。2]...---->[n]---->[NULL](原链表剩下用于直接插入排序的节点)
    20. first3->next2->nextn->next
    21. 图12
    22. ---->[1]---->[2]---->[3]...---->[n]---->[NULL]
    23. head1->next2->next3->nextn->next
    24. 图13:有N个节点的链表直接插入排序
    25. 1、先在原链表中以第一个节点为一个有序链表,其余节点为待定节点。
    26. 2、从图12链表中取节点,到图11链表中定位插入。
    27. 3、上面图示虽说画了两条链表,其实只有一条链表。在排序中,实质只增加了一个用于指向剩下需要排序节点的头指针first罢了。
    28. 这一点请读者务必搞清楚,要不然就可能认为它和上面的选择排序法一样了。
    29. */
    30. structstudent*InsertSort(structstudent*head)
    31. {
    32. structstudent*first;/*为原链表剩下用于直接插入排序的节点头指针*/
    33. structstudent*t;/*临时指针变量:插入节点*/
    34. structstudent*p;/*临时指针变量*/
    35. structstudent*q;/*临时指针变量*/
      1. first=head->next;/*原链表剩下用于直接插入排序的节点链表:可根据图12来理解。*/
    36. head->next=NULL;/*只含有一个节点的链表的有序链表:可根据图11来理解。*/
      1. while(first!=NULL)/*遍历剩下无序的链表*/
    37. {
    38. /*注意:这里for语句就是体现直接插入排序思想的地方*/
    39. for(t=first,q=head;&&(q->num<t->num));p=q,q=q->next);/*无序节点在有序链表中找插入的位置*/
      1. /*退出for循环,就是找到了插入的位置*/
    40. /*注意:按道理来说,这句话可以放到下面注释了的那个位置也应该对的,但是就是不能。原因:你若理解了上面的第3条,就知道了。*/
    41. first=first->next;/*无序链表中的节点离开,以便它插入到有序链表中。*/
      1. if/*插在第一个节点之前*/
    42. {
    43. head=t;
    44. }
    45. else/*p是q的前驱*/
    46. {
    47. p->next=t;
    48. }
    49. t->next=q;/*完成插入动作*/
    50. /*first=first->next;*/
    51. }
    52. returnhead;
    53. }

    示例:

    实现节点类

    节点类最基本的功能包括:更新数据,查询数据,更新后继节点和查询后继节点。

    #节点类class Node: #初始化,需要传入节点的数据 def __init__(self, data): self.data = data self.next = None #返回节点的数据 def get_data: return self.data #更新节点的数据 def set_data(self, new_data): self.data = new_data #返回后继节点 def get_next: return self.next #变更后继节点 def set_next(self, new_next): self.next = new_next
    
    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4
    
    
    class ListNode:
        def __init__(self, x):
            self.val = x
            self.next = None
    
        def __repr__(self):# 显示方式
            return "{}->{}".format(self.val,self.next)
    
    
    class Solution:
        def mergeTwoLists(self, l1, l2):
            """
            :type l1: ListNode
            :type l2: ListNode
            :rtype: ListNode
            """
            if not l1:return l2
            if not l2:return l1
            current =tmp= ListNode(0) #current 和 tmp 指向同一个头结点
            while l1 and l2:
                if l1.val < l2.val:
                    current.next = l1
                    l1=l1.next
                else:
                    current.next = l2
                    l2=l2.next
    
                current = current.next #单向链表,指向最后一个结点"指针"
    
            current.next = l1 or l2 #current链表最后一个结点的"指针"指向l1或者l2的头结点
            return tmp.next  #current的指针指向了l1或者l2的头结点,返回tmp完整链表
    

    实现链表

    链表的主要功能包括:节点的增加、删除和查询,返回链表的长度,返回链表是否为空等。

    #链表类class Linked_list: #初始化,头结点为空 def __init__: self.head = None #添加节点,添加的新节点作为新的头结点 def add(self, data): new_node = Node new_node.set_next() = self.head self.head = new_node #包含查询,传入值,返回该值在链表中是否存在 def search(self, data): checking = self.head #从头结点开始查询 while checking != None : if checking.get_data() == data: #查找到,返回True return True checking = checking.get_next() #查询下一个节点 return False #遍历到最后也未能找到,返回False #删除节点,将第一个具有传入值的节点从链表中删除 def remove(self, data): checking = self.head #从头结点开始查询 previous = None #记录前一个节点,头结点的前一个节点为None while checking != None : if checking.get_data() == data: #查找到,跳出查找循环 break previous = checking # 更新前一个节点 checking = checking.get_next() #查询下一个节点 if previous == None:#如果头结点便是查找的节点 self.head = checking.get_next() else: # 查找的节点不在头结点,即,存在前驱节点 previous.set_next(checking.get_next #判断链表是否为空 def isEmpty: return self.head == None #返回链表长度 def size: count = 0 counting = self.head #从头结点开始计数 while counting != None : count  = 1 counting = counting.get_next() return count
    

     

    实现有序链表

    有序链表是非常常用的链表。有序链表在实现中与普通链表的差别体现在插入节点和查询节点的操作上。下面是一个头结点小,尾节点大的有序链表:

    #有序链表类class Ordered_linked_list: #初始化,头结点为空 def __init__: self.head = None #添加节点 def add(self, data): checking = self.head #从头结点开始查询 previous = None #记录前一个节点,头结点的前一个节点为None while checking != None : if checking.get_data() > data: #查找到可以插入的位置,跳出循环 break previous = checking # 更新前一个节点 checking = checking.get_next() #查询下一个节点 new_node = Node #创建新节点 if previous == None: #插入在头结点位置 new_node.set_next() = self.head self.head = new_node else : #插入在中间或者尾部 previous.set_next new_node.set_next #包含查询,传入值,返回该值在链表中是否存在 def search(self, data): checking = self.head #从头结点开始查询 while checking != None : if checking.get_data() == data: #查找到,返回True return True elif checking.get_data() > data: #过了需要查询的值 return False checking = checking.get_next() #查询下一个节点 return False #遍历到最后也未能找到,返回False #删除节点,将第一个具有传入值的节点从链表中删除 def remove(self, data): checking = self.head #从头结点开始查询 previous = None #记录前一个节点,头结点的前一个节点为None while checking != None : if checking.get_data() == data: #查找到,跳出查找循环 break previous = checking # 更新前一个节点 checking = checking.get_next() #查询下一个节点 if previous == None:#如果头结点便是查找的节点 self.head = checking.get_next() else: # 查找的节点不在头结点,即,存在前驱节点 previous.set_next(checking.get_next #判断链表是否为空 def isEmpty: return self.head == None #返回链表长度 def size: count = 0 counting = self.head #从头结点开始计数 while counting != None : count  = 1 counting = counting.get_next() return count
    

    本文由新葡亰496net发布于奥门新萄京娱乐场,转载请注明出处:新葡亰496net:排序算法,Python实现链表

    关键词: