双向链表上的归并排序

2024年8月28日 | 阅读 18 分钟

归并排序是一种递归方法，它反复将列表分成两半。如果列表为空或只包含一个项（基本情况），则该列表按定义已排序。如果列表包含多个项，我们将其分成两半，并对两部分递归地执行归并排序。在两半排序后，将执行称为归并的基本过程。归并是将两个较小的已排序列表集成到一个已排序的新列表中。如果列表的长度小于或等于一，则该列表已经排序，不需要进一步处理。但是，如果长度大于一，则使用 Python 切片方法提取左半部分和右半部分。值得注意的是，列表可能甚至没有很多条目。这无关紧要，因为长度只会相差一。以下步骤概念性地展示了归并排序的工作原理：

将未排序的列表分成 n 个子列表，每个子列表包含一个条目（包含一个元素的列表被认为是已排序的）。
重复合并子列表以创建新的已排序子列表，直到只剩下一个子列表。这里将显示已排序的列表。

自上而下的实现

自上而下的归并排序技术采用索引递归地将列表（在本例中称为运行）拆分为子列表，直到子列表大小为 1，然后将这些子列表合并以生成已排序的列表。通过在每个递归级别旋转合并方向，可以避免复制回步骤（除了初始的一次性复制，也可以避免）。

考虑一个两元素数组以更好地理解这一点。组件在合并到 A[] 之前被传输到 B[]。如果有四个元素，来自 A[] 的单元素运行在递归级别的底部合并到 B[]，而两元素运行在下一个更高递归级别合并到 A[]。随着每个递归级别，模式持续存在。

自然归并排序

自然归并排序类似于自下而上的归并排序，因为它利用输入中任何自然出现的运行（已排序序列）。列表（或等效地，磁带或文件）是用于**单调**和**位元**（交替上升/下降）运行的有用数据结构（用作 FIFO 队列或 LIFO 堆栈）。自下而上的归并排序的起点是每个运行的长度为一个项目。

由于存在长的自然运行，自然归并排序在许多实际情况下被用作 Timsort 的基本组件。实际上，随机输入数据将包含许多偶然排序的短运行。因为需要合并的运行更少，所以在大多数情况下，自然归并排序可能不需要那么多遍。在最佳情况下，输入已经排序（即，它是一个单一的运行）。因此，自然归并排序只需要遍历数据一次。

优化归并排序

由于现代计算机采用多个内存层次结构，引用局部性在程序优化中至关重要。已经开发了归并排序算法的缓存感知变体，其操作经过精心设计，以最大程度地减少机器内存缓存中页面的进出。例如，分块归并排序算法在子数组大小达到 S 时停止拆分子数组。S 是适合 CPU 缓存的数据项数量。为了避免内存交换，每个子数组都使用插入排序等就地排序算法进行排序，然后以传统的递归方式完成常规归并排序。

现在让我们编写一些代码，借助归并排序算法对双向链表数据结构执行排序操作。

Java 代码

首先，让我们编写 Java 代码以对双向链表数据结构执行归并排序。

// Java program to implement merge sort in a singly linked list 

import java.util.Scanner;  
// Linked List Class 
class LinkedList { 
  
    static Node head;  // head of the list 
  
    /* Node Class */
    static class Node { 
  
        int data; 
        Node next, prev; 
  
        // Constructor to create a new node 
        Node(int d) { 
            data = d; 
            next = prev = null; 
        } 
    } 
  
    void print(Node node) { 
        Node temp = node; 
        System.out.println("Forward Traversal using next pointer"); 
        while (node != null) { 
            System.out.print(node.data + " "); 
            temp = node; 
            node = node.next; 
        } 
        System.out.println("Backward Traversal using prev pointer"); 
        while (temp != null) { 
            System.out.print(temp.data + " "); 
            temp = temp.prev; 
        } 
    } 
  
    // Split a doubly linked list (DLL) into 2 DLLs of 
    // half sizes 
    Node split(Node head) { 
        Node fast = head, slow = head; 
        while (fast.next != null && fast.next.next != null) { 
            fast = fast.next.next; 
            slow = slow.next; 
        } 
        Node temp = slow.next; 
        slow.next = null; 
        return temp; 
    } 
  
    Node mergeSort(Node node) { 
        if (node == null || node.next == null) { 
            return node; 
        } 
        Node second = split(node); 
  
        // Recur for left and right halves 
        node = mergeSort(node); 
        second = mergeSort(second); 
  
        // Merge the two sorted halves 
        return merge(node, second); 
    } 
  
    // Function to merge two linked lists 
    Node merge(Node first, Node second) { 
        // If first linked list is empty 
        if (first == null) { 
            return second; 
        } 
  
        // If second linked list is empty 
        if (second == null) { 
            return first; 
        } 
  
        // Pick the smaller value 
        if (first.data < second.data) { 
            first.next = merge(first.next, second); 
            first.next.prev = first; 
            first.prev = null; 
            return first; 
        } else { 
            second.next = merge(first, second.next); 
            second.next.prev = second; 
            second.prev = null; 
            return second; 
        } 
    }
    /* Function to insert a node at the beginning of the Doubly Linked List */
    void push(int new_Data) 
    { 
        Node new_Node = new Node(new_Data);     /* allocate node */
          
        // if head is null, head = new_Node 
        if(head==null){ 
            head = new_Node; 
            return; 
        } 
          
        /* link the old list off the new node */
        new_Node.next = head; 
          
        /* change prev of head node to new node */
        head.prev = new_Node; 
          
        /* since we are adding at the begining, prev is always NULL */
        new_Node.prev = null; 
          
        /* move the head to point to the new node */
        head = new_Node; 
    }  
  
    // Driver program to test above functions 
    public static void main(String[] args) { 
  
        LinkedList list = new LinkedList();  
        Scanner scan = new Scanner(System.in);
        char ch;
        /**  Perform tree operations  **/
        do    
        {
            System.out.println("\nSelect one of the operations::\n");
            System.out.println("1. To insert a new node in the Doubly Linked List.");
            System.out.println("2. To display the nodes of the Doubly Linked List.");
            System.out.println("3. To perform Merge sort on the Doubly Linked List.");
 
            int choice = scan.nextInt();            
            switch (choice)
            {
            case 1 : 
                System.out.println("Enter integer element to insert");
                list.push(scan.nextInt());                     
                break;                          
            case 2 : 
                System.out.println("Doubly Linked List::");
                list.print(head);
                break;                                          
            case 3 : 
                System.out.println("Quicksort done.");
                head = list.mergeSort(head);
                break;     
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');
    } 
} 

输出

上述代码给出以下输出。

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
23

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
76

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
55

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
20
Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
89

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
78  1
Enter integer element to insert
78

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
32 1  1
Enter integer element to insert
31

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter integer element to insert
68

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2
Doubly Linked List::
Forward Traversal using next pointer
68 31 78 89 20 55 76 23 Backward Traversal using prev pointer
23 76 55 20 89 78 31 68 
Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
3
Quicksort done.

Do you want to continue (Type y or n) 

y

Select one of the operations::

1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2
Doubly Linked List::
Forward Traversal using next pointer
20 23 31 55 68 76 78 89 Backward Traversal using prev pointer
89 78 76 68 55 31 23 20 
Do you want to continue (Type y or n) 

n

C++ 代码

现在，让我们编写 C++ 代码以对双向链表数据结构执行归并排序。

// C++ program for merge sort on doubly linked list  

#include <bits/stdc++.h> 
using namespace std; 
class Node  
{  
    public: 
    int data;  
    Node *next, *prev;  
};  
  
Node *split(Node *head);  
  
// Function to merge two linked lists  
Node *merge(Node *first, Node *second)  
{  
    // If first linked list is empty  
    if (!first)  
        return second;  
  
    // If second linked list is empty  
    if (!second)  
        return first;  
  
    // Pick the smaller value  
    if (first->data < second->data)  
    {  
        first->next = merge(first->next,second);  
        first->next->prev = first;  
        first->prev = NULL;  
        return first;  
    }  
    else
    {  
        second->next = merge(first,second->next);  
        second->next->prev = second;  
        second->prev = NULL;  
        return second;  
    }  
}  
  
// Function to do merge sort  
Node *mergeSort(Node *head)  
{  
    if (!head || !head->next)  
        return head;  
    Node *second = split(head);  
  
    // Recur for left and right halves  
    head = mergeSort(head);  
    second = mergeSort(second);  
  
    // Merge the two sorted halves  
    return merge(head,second);  
}  
  
// A utility function to insert a new node at the  
// beginning of the doubly linked list  
void insert(Node **head, int data)  
{  
    Node *temp = new Node(); 
    temp->data = data;  
    temp->next = temp->prev = NULL;  
    if (!(*head))  
        (*head) = temp;  
    else
    {  
        temp->next = *head;  
        (*head)->prev = temp;  
        (*head) = temp;  
    }  
}  
  
// A utility function to print a doubly linked list in  
// both forward and backward directions  
void print(Node *head)  
{  
    Node *temp = head;  
    cout<<"Forward Traversal using next poitner";  
    while (head)  
    {  
        cout << head->data << " ";  
        temp = head;  
        head = head->next;  
    }  
    cout  << "Backward Traversal using prev pointer";  
    while (temp)  
    {  
        cout << temp->data << " ";  
        temp = temp->prev;  
    }  
}  
  
// Utility function to swap two integers  
void swap(int *A, int *B)  
{  
    int temp = *A;  
    *A = *B;  
    *B = temp;  
}  
  
// Split a doubly linked list (DLL) into 2 DLLs of  
// half sizes  
Node *split(Node *head)  
{  
    Node *fast = head,*slow = head;  
    while (fast->next && fast->next->next)  
    {  
        fast = fast->next->next;  
        slow = slow->next;  
    }  
    Node *temp = slow->next;  
    slow->next = NULL;  
    return temp;  
}  
  
// Driver program  
int main(void)  
{  
    Node *head = NULL;  
    int data;
    char ch;
        /*  Perform tree operations  */
        do    
        {
            cout<<"\nSelect one of the operations::"<<endl;
            cout<<"1. To insert a new node in the Doubly Linked List."<<endl;
            cout<<"2. To display the nodes of the Doubly Linked List."<<endl;
            cout<<"3. To perform Merge sort on the Doubly Linked List."<<endl;
             
            int choice;
            cin>>choice;            
            switch (choice)
            {
            case 1 : 
                cout<<"Enter the value of the node to be inserted"<<endl;
                cin>>data;
                insert(&head,data);                     
                break;                          
            case 2 : 
                cout<<"Contents of the Doubly Linked List are::"<<endl;
                print(head);
                break; 
            case 3 : 
                cout<<"Merge sort applied successfully on the Doubly Linked List."<<endl;
                head=mergeSort(head);
                break;
            default : 
                cout<<"Wrong Entry \n ";
                break;   
            }
 
            cout<<"\nDo you want to continue (Type y or n) \n";
            cin>>ch;                        
        } while (ch == 'Y'|| ch == 'y'); 
    return 0;  
} 

输出

上面的 C++ 代码给出以下输出。

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
12

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
78

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
45

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
33

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
92

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
45

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1
Enter the value of the node to be inserted
65

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2
Contents of the Doubly Linked List are::
Forward Traversal using next pointer
65 45 92 33 45 78 12 
Backward Traversal using prev pointer
12 78 45 33 92 45 65 
Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
3
Merge sort applied successfully on the Doubly Linked List.

Do you want to continue (Type y or n) 
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2
Contents of the Doubly Linked List are::
Forward Traversal using next pointer
12 33 45 45 65 78 92 
Backward Traversal using prev pointer
92 78 65 45 45 33 12 
Do you want to continue (Type y or n) 
n

C 代码

现在，让我们编写 C 代码以对双向链表数据结构执行归并排序。

// C program for merge sort on doubly linked list 
#include<stdio.h> 
#include<stdlib.h> 
struct Node 
{ 
    int data; 
    struct Node *next, *prev; 
}; 
  
struct Node *split(struct Node *head); 
  
// Function to merge two linked lists 
struct Node *merge(struct Node *first, struct Node *second) 
{ 
    // If first linked list is empty 
    if (!first) 
        return second; 
  
    // If second linked list is empty 
    if (!second) 
        return first; 
  
    // Pick the smaller value 
    if (first->data < second->data) 
    { 
        first->next = merge(first->next,second); 
        first->next->prev = first; 
        first->prev = NULL; 
        return first; 
    } 
    else
    { 
        second->next = merge(first,second->next); 
        second->next->prev = second; 
        second->prev = NULL; 
        return second; 
    } 
} 
  
// Function to do merge sort 
struct Node *mergeSort(struct Node *head) 
{ 
    if (!head || !head->next) 
        return head; 
    struct Node *second = split(head); 
  
    // Recur for left and right halves 
    head = mergeSort(head); 
    second = mergeSort(second); 
  
    // Merge the two sorted halves 
    return merge(head,second); 
} 
  
// A utility function to insert a new node at the 
// beginning of the doubly linked list 
void insert(struct Node **head, int data) 
{ 
    struct Node *temp = 
        (struct Node *)malloc(sizeof(struct Node)); 
    temp->data = data; 
    temp->next = temp->prev = NULL; 
    if (!(*head)) 
        (*head) = temp; 
    else
    { 
        temp->next = *head; 
        (*head)->prev = temp; 
        (*head) = temp; 
    } 
} 
  
// A utility function to print a doubly linked list in 
// both forward and backward directions 
void print(struct Node *head) 
{ 
    struct Node *temp = head; 
    printf("\nForward Traversal using next poitner\n"); 
    while (head) 
    { 
        printf("%d ",head->data); 
        temp = head; 
        head = head->next; 
    } 
    printf("\nBackward Traversal using prev pointer\n"); 
    while (temp) 
    { 
        printf("%d ", temp->data); 
        temp = temp->prev; 
    } 
} 
  
// Utility function to swap two integers 
void swap(int *A, int *B) 
{ 
    int temp = *A; 
    *A = *B; 
    *B = temp; 
} 
  
// Split a doubly linked list (DLL) into 2 DLLs of 
// half sizes 
struct Node *split(struct Node *head) 
{ 
    struct Node *fast = head,*slow = head; 
    while (fast->next && fast->next->next) 
    { 
        fast = fast->next->next; 
        slow = slow->next; 
    } 
    struct Node *temp = slow->next; 
    slow->next = NULL; 
    return temp; 
} 
  
// Driver program 
int main(void) 
{ 
    struct Node *head = NULL; 
    int data;
    char ch;
        /*  Perform tree operations  */
        do    
        {
            printf("\nSelect one of the operations::");
            printf("\n1. To insert a new node in the Doubly Linked List.");
            printf("\n2. To display the nodes of the Doubly Linked List.");
            printf("\n3. To perform Merge sort on the Doubly Linked List.\n");

            int choice;
            scanf("%d",&choice);            
            switch (choice)
            {
            case 1 : 
                printf("\nEnter the value of the node to be inserted\n");
                scanf("%d",&data);
                insert(&head,data);                     
                break;                          
            case 2 : 
                printf("\nContents of the Doubly Linked List are::\n");
                print(head);
                break; 
            case 3 : 
                printf("\nMerge sort applied successfully on the Doubly Linked List.\n");
                head = mergeSort(head);
                break;
            default : 
                printf("Wrong Entry\n");
                break;   
            }

            printf("\nDo you want to continue (Type y or n)\n");
            scanf(" %c",&ch);                        
        } while (ch == 'Y'|| ch == 'y'); 
    return 0; 
}

输出

上面的 C 代码给出以下输出。

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
22

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
89

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
54

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
32

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
81

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
47

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
8 3

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
1

Enter the value of the node to be inserted
97

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2

Contents of the Doubly Linked List are::

Forward Traversal using next pointer
97 3 47 81 32 54 89 22 
Backward Traversal using prev pointer
22 89 54 32 81 47 3 97 
Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
3

Merge sort applied successfully on the Doubly Linked List.

Do you want to continue (Type y or n)
y

Select one of the operations::
1. To insert a new node in the Doubly Linked List.
2. To display the nodes of the Doubly Linked List.
3. To perform Merge sort on the Doubly Linked List.
2
Contents of the Doubly Linked List are::

Forward Traversal using next pointer
3 22 32 47 54 81 89 97 
Backward Traversal using prev pointer
97 89 81 54 47 32 22 3 
Do you want to continue (Type y or n)
n

通过这种方式，我们编写了 Java、C++ 和 C 代码来对双向链表数据结构执行归并排序操作。为双向链表数据结构编写了三个函数，一个是向双向链表添加新节点，第二个是显示双向链表的所有节点并显示与这些节点关联的值，第三个也是最后一个函数是执行归并排序操作在双向链表数据结构上。

用户首先在双向链表数据结构中添加足够数量的节点。成功添加节点后，通过从每次操作后显示的菜单中选择第三个选项，在双向链表数据结构上执行归并排序操作，该选项将调用代码中编写的 **mergesort()** 函数，并将双向链表的根节点作为参数传递。

成功完成归并排序操作后，用户可以通过选择用户的第二个选项来显示双向链表中节点的值，从而确认快速排序操作的结果。所有操作完成后，用户可以通过输入“n”或“N”字符退出代码。

下一主题使用递归对栈进行排序

双向链表上的归并排序

自上而下的实现

自然归并排序

优化归并排序

Java 代码

C++ 代码

C 代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

双向链表上的归并排序

自上而下的实现

自然归并排序

优化归并排序

Java 代码

C++ 代码

C 代码

相关帖子

对近乎排序、k 排序或几乎排序的数组进行排序

N 元树的序列化和反序列化

查找二叉树中两个节点的直接父节点

完美二叉树

将所有零移到数组末尾

DS 中的队列操作

第 N 个偶数斐波那契序列

从给定的排序字典中查找优先级字符

栈指针

树的左视图

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器