WHCSRL 技术网

CG.单链表节点的删除与排序

问题描述】输入一组整数,以单链表的形式存储,删掉里面存放偶数的节点,并按照从小到大的顺序排序,并输出
【输入形式】整数序列,以空格为间隔,最多十个整数
【输出形式】整数序列,以空格为间隔
【样例输入】3 5 8 9 1 2 4
【样例输出】1 3 5 9
【样例说明】
【评分标准】

思路:节点的排序与冒泡排序基本相同,可以采用交换data值而不改变节点值

           删除时可以不使用函数,在录入节点时就将其pass掉,符合条件的才能作为data录入

  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<string>
  4. using namespace std;
  5. typedef struct node
  6. {
  7. int data;
  8. struct node *next;
  9. }node;
  10. node *Creatlist()
  11. {
  12. char ch = 0; //停止变量需要初始化
  13. int n;
  14. node *head = new node;
  15. head->next = NULL;
  16. node *pre = head;
  17. while(ch!=' ') //输入回车后 停止输入
  18. {
  19. cin >> n;
  20. ch = getchar();
  21. if (n%% 2 != 0) { //只有奇数才纳入节点,不用单独设置删除函数
  22. node* p = new node; //变量节点
  23. p->data = n;
  24. p->next = NULL;
  25. pre->next = p;
  26. pre = p;
  27. }
  28. }
  29. pre->next = NULL;
  30. return head;
  31. }
  32. void sort(node *head)
  33. {
  34. int temp;
  35. for (node *pre = head->next; pre ; pre = pre->next) //循环对比指针需放在1位置
  36. {
  37. for (node *p = pre->next; p ; p = p->next)
  38. {
  39. if (pre->data > p->data)
  40. {
  41. temp = pre->data;
  42. pre->data = p->data;
  43. p->data = temp;
  44. }
  45. }
  46. }
  47. }
  48. void show(node *head)
  49. {
  50. node *pre = head->next;
  51. while (pre)
  52. {
  53. cout << pre->data << " ";
  54. pre = pre->next;
  55. }
  56. }
  57. int main()
  58. {
  59. node *head = Creatlist(); //函数与变量都是 node*同类型
  60. sort(head); //排序和输出不需要返回值
  61. show(head);
  62. return 0;
  63. }

tips:输入完毕后 回车结束的设置

  1. int ch=0;
  2. while(ch!=' ')
  3. {
  4. cin>>data;
  5. ch=getchar();
  6. ....
  7. }

推荐阅读