在C++中,我們可以通過多種方式展示數據結構與算法的結合。以下是一個簡單的例子,使用鏈表(一種常見的數據結構)和排序算法(如冒泡排序)來展示它們是如何協同工作的。
首先,我們定義一個鏈表節點結構體和一個簡單的鏈表類:
#include <iostream>
using namespace std;
// 鏈表節點結構體
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 鏈表類
class LinkedList {
public:
LinkedList() : head(NULL) {}
// 在鏈表末尾添加一個新節點
void append(int val) {
if (!head) {
head = new ListNode(val);
return;
}
ListNode* current = head;
while (current->next) {
current = current->next;
}
current->next = new ListNode(val);
}
// 打印鏈表
void print() {
ListNode* current = head;
while (current) {
cout << current->val << " ";
current = current->next;
}
cout << endl;
}
private:
ListNode* head;
};
接下來,我們實現一個簡單的冒泡排序算法,并將其應用于鏈表:
// 冒泡排序算法
void bubbleSort(LinkedList& list) {
if (!list.head || !list.head->next) {
return;
}
bool swapped;
ListNode* current = list.head;
ListNode* next;
do {
swapped = false;
current = list.head;
while (current->next) {
if (current->val > current->next->val) {
// 交換兩個節點的值
int temp = current->val;
current->val = current->next->val;
current->next->val = temp;
swapped = true;
}
current = current->next;
}
} while (swapped);
}
最后,我們創建一個鏈表實例,向其中添加一些元素,并使用冒泡排序對其進行排序:
int main() {
LinkedList list;
list.append(5);
list.append(3);
list.append(8);
list.append(1);
list.append(4);
cout << "原始鏈表: ";
list.print();
bubbleSort(list);
cout << "排序后的鏈表: ";
list.print();
return 0;
}
這個例子展示了如何使用鏈表作為數據結構,以及如何使用冒泡排序算法對其進行排序。當然,這只是一個簡單的示例,實際應用中可能會涉及更復雜的數據結構和算法。