C/C++:编写程序建立一个单向链表。链表结点中的数据为从键盘输入的一个字符串,但要求将该串字符按由小到大的顺序组织在链表中。
时间: 2024-02-19 21:58:25 浏览: 86
c语言实现链表的基本操作,链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
以下是我用 C++ 编写的程序,可以实现你的要求:
```cpp
#include <iostream>
#include <string>
using namespace std;
// 定义链表结点
struct ListNode {
string val;
ListNode* next;
ListNode(string x) : val(x), next(nullptr) {}
};
// 插入一个结点
void insert(ListNode* head, string val) {
ListNode* node = new ListNode(val);
ListNode* prev = head;
while (prev->next != nullptr && prev->next->val < val) {
prev = prev->next;
}
node->next = prev->next;
prev->next = node;
}
int main() {
// 创建头结点
ListNode* head = new ListNode("");
cout << "请输入字符串(以空格分隔):" << endl;
string s;
while (cin >> s) {
// 按顺序插入结点
insert(head, s);
}
// 遍历链表并输出结果
ListNode* p = head->next;
while (p != nullptr) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
// 释放内存
p = head;
while (p != nullptr) {
ListNode* q = p->next;
delete p;
p = q;
}
return 0;
}
```
程序思路如下:
1. 定义链表结点 `ListNode`,其中 `val` 存储字符串,`next` 指向下一个结点。
2. 创建头结点 `head`。
3. 从键盘输入一串字符串,每次调用 `insert` 函数将其插入链表中。
4. `insert` 函数中,从头结点开始遍历链表,找到插入位置并插入结点。
5. 遍历链表并输出结果。
6. 释放内存,从头结点开始遍历链表并依次删除每个结点。
其中比较关键的是 `insert` 函数的实现,它保证了链表中的字符串按从小到大的顺序排列。
阅读全文