用动态分区算法,并且不利用sort函数再次编写上述代码
时间: 2024-03-18 10:39:05 浏览: 25
好的,这是一个使用动态分区算法实现的C++程序:
```cpp
#include <iostream>
#include <cstring>
using namespace std;
struct SongNode {
char name[50];
SongNode *next;
};
int main()
{
const int MAX_SONG_NUM = 10;
SongNode *song_head = nullptr; // 存放歌名的链表头指针
SongNode *song_tail = nullptr; // 存放歌名的链表尾指针
char name[50];
// 输入10首歌名并存入链表中
cout << "Please enter 10 song names:" << endl;
for (int i = 0; i < MAX_SONG_NUM; i++) {
cin >> name;
SongNode *node = new SongNode;
strcpy(node->name, name);
node->next = nullptr;
if (song_head == nullptr) {
song_head = node;
song_tail = node;
} else {
song_tail->next = node;
song_tail = node;
}
}
// 使用冒泡排序算法对歌名进行排序
for (SongNode *i = song_head; i != nullptr; i = i->next) {
for (SongNode *j = i->next; j != nullptr; j = j->next) {
if (strcmp(i->name, j->name) > 0) {
char temp[50];
strcpy(temp, i->name);
strcpy(i->name, j->name);
strcpy(j->name, temp);
}
}
}
// 输出排序后的歌名
cout << "The sorted song names are:" << endl;
for (SongNode *i = song_head; i != nullptr; i = i->next) {
cout << i->name << endl;
}
// 释放链表节点的内存
while (song_head != nullptr) {
SongNode *node = song_head;
song_head = song_head->next;
delete node;
}
return 0;
}
```
这个程序使用了一个链表存放输入的歌名,然后使用冒泡排序算法对链表中的歌名进行排序。由于链表中的节点可以动态分配内存,所以这个程序没有使用固定大小的字符数组,而是使用了动态分区算法。最后,我们依次输出排序后的歌名,并释放链表节点的内存。