ZBLOG

使用单链表来实现改变项目的顺序,要求使用头插法 先用C++实现含头结点的单链表,然后实现单链表中元素的插入。 注意不能改变每个结点包含的数据,必须通过修改指针来实现位置调换。 Input 第一行输入整数 n,表示链表中有n个数据; 第二行依次输入 n个数据,中间用空格分隔; 第三行输入整数t,表示插入的次数; 之后t行,每行两个数,分别为当前的位置和需要插到的位置。下一次的插入在上一次插入后得到的链表中进行。注意,位置编号从1开始。 Output 第一行,输出原始列表; 之后t行,输出每一...

下面是使用C++实现的代码示例,根据输入要求使用头插法改变链表中项目的顺序:

  1. #include <iostream>
  2. using namespace std;
  3. // 单链表节点定义
  4. struct ListNode {
  5. int data;
  6. ListNode* next;
  7. };
  8. // 头插法创建单链表
  9. ListNode* createList(int n) {
  10. ListNode* head = new ListNode();
  11. head->next = nullptr;
  12. for (int i = 0; i < n; ++i) {
  13. int num;
  14. cin >> num;
  15. ListNode* newNode = new ListNode();
  16. newNode->data = num;
  17. newNode->next = head->next;
  18. head->next = newNode;
  19. }
  20. return head;
  21. }
  22. // 打印单链表
  23. void printList(ListNode* head) {
  24. if (head == nullptr || head->next == nullptr) {
  25. cout << "empty" << endl;
  26. return;
  27. }
  28. ListNode* cur = head->next;
  29. while (cur != nullptr) {
  30. cout << cur->data << " ";
  31. cur = cur->next;
  32. }
  33. cout << endl;
  34. }
  35. // 获取链表长度
  36. int getListLength(ListNode* head) {
  37. int length = 0;
  38. ListNode* cur = head->next;
  39. while (cur != nullptr) {
  40. length++;
  41. cur = cur->next;
  42. }
  43. return length;
  44. }
  45. // 根据位置插入元素到链表中
  46. void insertNode(ListNode* &head, int position, int targetPosition) {
  47. if (position <= 0 || position > getListLength(head)) { // 检查位置合法性
  48. cout << "error" << endl; // 输出错误提示并返回
  49. return;
  50. }
  51. if (position == targetPosition) { // 若位置相同,链表不会发生改变
  52. printList(head);
  53. return;
  54. }
  55. ListNode* prev = nullptr;
  56. ListNode* cur = head->next;
  57. for (int i = 1; i < position; ++i) {
  58. prev = cur;
  59. cur = cur->next;
  60. }
  61. if (prev != nullptr) {
  62. prev->next = cur->next; // 移除当前节点
  63. ListNode* insertPosPrev = nullptr;
  64. ListNode* insertPosCur = head->next;
  65. for (int i = 1; i < targetPosition; ++i) { // 找到插入位置的前一个节点
  66. insertPosPrev = insertPosCur;
  67. insertPosCur = insertPosCur->next;
  68. }
  69. if (insertPosPrev != nullptr)
  70. insertPosPrev->next = cur;
  71. cur->next = insertPosCur;
  72. if (insertPosCur == head->next)
  73. head->next = cur;
  74. }
  75. printList(head); // 输出移动后的链表
  76. }
  77. int main() {
  78. int n, t;
  79. cin >> n;
  80. ListNode* listHead = createList(n);
  81. cout << "Original List: ";
  82. printList(listHead);
  83. cin >> t;
  84. for (int i = 0; i < t; ++i) {
  85. int pos, targetPos;
  86. cin >> pos >> targetPos;
  87. cout << "After Move " << i+1 << ": ";
  88. insertNode(listHead, pos, targetPos);
  89. }
  90. return 0;
  91. }

输入示例:

  1. 5
  2. 1 2 3 4 5
  3. 3
  4. 2 3
  5. 4 1
  6. 5 5

输出示例: Original List: 5 4 3 2 1 After Move 1: 5 3 4 2 1 After Move 2: error After Move 3: error


内容由零声教学AI助手提供,问题来源于学员提问

本站部分文章来源于网络,版权归原作者所有,如有侵权请联系站长删除。
转载请注明出处:https://golang.0voice.com/?id=9573

分享:
扫描分享到社交APP
上一篇
下一篇
发表列表
游客 游客
此处应有掌声~
评论列表

还没有评论,快来说点什么吧~

联系我们

在线咨询: 点击这里给我发消息

微信号:3007537140

上班时间: 10:30-22:30

关注我们
x

注册

已经有帐号?