資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究C++中連結串列的交替排序
連結串列是一種線性資料結構，它儲存元素，並存儲指向下一個資料節點的指標。
在這個連結串列排序問題中，交替排序是指以這樣一種方式排序：第一個節點包含最小值資料，第二個節點包含最大值資料，第三個節點包含次最小值資料，以此類推。這種交替最大值和最小值的模式是在連結串列的交替排序中建立的。
讓我們舉個例子來更好地理解這個問題：
Input : 3 > 4 > 21 >67 > 1 > 8. Output : 1 > 67 > 3 > 21 > 4 > 8. Explanation : Sort order of elements is 1 , 3 , 4 ,8 ,21 ,67. For required output we need to take one value from the beginning and one from end and it outputs the result.
現在，我們知道了這個問題。我們將嘗試找到這個問題的解決方案。所以，既然我們需要交替最小值和最大值，我們就應該相應地對連結串列進行排序。為此，可以使用任何連結串列排序方法。然後，我們將從開頭取一個值，從結尾取一個值。最好使用兩個不同的列表來避免重疊。我們將反轉後兩個一半，然後以交替的順序將它們合併回來。由於我們必須使用合併排序技術的一些部分，因此對於排序，合併排序也相當有效。
演算法
Step 1 : Sort the linked list using merge sort technique. Step 2 : Create two linked list of half the length of the original linked list. Now, place one half in first half linked list and other half in second half linked list. Step 3 : reverse the second linked list and store in new linked list (required for reversal ). Step 4 : Create the result linked list using the first and reverse linked list. Using the elements of both list in alternate order.
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
Node* getNode(int data){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) ;
Node* SortedMerge(Node* a, Node* b) ;
void MergeSort(Node** headRef) ;
void alternateMerge(Node* head1, Node* head2) ;
Node* altSortLinkedList(Node* head) ;
void printList(Node* head) ;
static void reverse(Node** head_ref){
Node* prev = NULL;
Node* current = *head_ref;
Node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
int main(){
Node* head = getNode(3);
head->next = getNode(4);
head->next->next = getNode(21);
head->next->next->next = getNode(67);
head->next->next->next->next = getNode(1);
head->next->next->next->next->next = getNode(8);
cout << "Initial list: ";
printList(head);
head = altSortLinkedList(head);
cout << "\nSorted list: ";
printList(head);
return 0;
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef){
Node* fast;
Node* slow;
if (source == NULL || source->next == NULL) {
*frontRef = source;
*backRef = NULL;
}
else {
slow = source;
fast = source->next;
while (fast != NULL) {
fast = fast->next;
if (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
}
*frontRef = source;
*backRef = slow->next;
slow->next = NULL;
}
}
Node* SortedMerge(Node* a, Node* b){
Node* result = NULL;
if (a == NULL)
return b;
else if (b == NULL)
return a;
if (a->data <= b->data) {
result = a;
result->next = SortedMerge(a->next, b);
} else {
result = b;
result->next = SortedMerge(a, b->next);
}
return result;
}
void MergeSort(Node** headRef){
Node* head = *headRef;
Node *a, *b;
if ((head == NULL) || (head->next == NULL))
return;
FrontBackSplit(head, &a, &b);
MergeSort(&a);
MergeSort(&b);
*headRef = SortedMerge(a, b);
}
void alternateMerge(Node* head1, Node* head2){
Node *p, *q;
while (head1 != NULL && head2 != NULL) {
p = head1->next;
head1->next = head2;
head1 = p;
q = head2->next;
head2->next = head1;
head2 = q;
}
}
Node* altSortLinkedList(Node* head){
MergeSort(&head);
Node *front, *back;
FrontBackSplit(head, &front, &back);
reverse(&back);
alternateMerge(front, back);
return front;
}
void printList(Node* head){
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}輸出
Initial list: 3 4 21 67 1 8 Sorted list: 1 67 3 21 4 8
更新於：2019年10月16日
206 次瀏覽
廣告