逆序(算法时间复杂度为O(n))

柔情只为你懂 2022-10-22 11:59 197阅读 0赞

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. struct Node
  4. {
  5. int data;
  6. struct Node* next;
  7. };
  8. short list_Length;//全局变量list_Length记录当前表长
  9. struct Node* head;//全局指针head, 负责指向当前链表的头结点
  10. struct Node* rear;//全局指针rear, 负责指向当前表尾结点: 如果表为空, 那么rear指向头结点
  11. void Create_LinkList()//创建链表, 即初始化头结点
  12. {
  13. head=(struct Node*)malloc(sizeof(struct Node));
  14. if(head!=NULL)//结点申请成功
  15. {
  16. head->data=0;//头结点的数据域置零
  17. rear=head;//表尾指针暂时指向头结点
  18. head->next=NULL;
  19. list_Length=0;
  20. }
  21. else//结点申请失败
  22. {
  23. printf("头结点申请失败!\n");
  24. }
  25. return ;
  26. }
  27. void Node_Insert(int c)//插入新结点到链表中
  28. {
  29. struct Node* p;
  30. p=(struct Node*)malloc(sizeof(struct Node));//申请新的Node结点
  31. if(p!=NULL)//结点申请成功
  32. {
  33. p->data=c;//新结点的数据由函数外传入
  34. p->next=NULL;
  35. rear->next=p;//插入结点前的表尾结点的next指针指向当前结点
  36. rear=p;//表尾指针指向当前新申请结点
  37. list_Length++;//表长+1
  38. }
  39. else
  40. {
  41. printf("结点申请失败!\n");
  42. return ;
  43. }
  44. }
  45. void f2()//f()函数的改进
  46. {
  47. //第一步, 把数据导入数组中
  48. int T[list_Length];
  49. struct Node* p=head->next;
  50. int i=0;
  51. while(p!=NULL)
  52. {
  53. T[i]=p->data;
  54. p=p->next;
  55. i++;
  56. }
  57. //第二步, 逆序输出数组中的数据
  58. i=list_Length-1;
  59. while(i>=0)
  60. {
  61. if(i!=0)//当前输出元素不是输出序列的最后一个
  62. printf("%d ", T[i]);
  63. else//当前输出元素是输出序列的最后一个
  64. printf("%d\n", T[i]);
  65. i--;
  66. }
  67. return ;
  68. }//时间复杂度降为O(n)
  69. int main()
  70. {
  71. int c;
  72. Create_LinkList();//创建头结点
  73. while(1)
  74. {
  75. scanf("%d", &c);
  76. Node_Insert(c);
  77. if(getchar()=='\n')
  78. {
  79. break;
  80. }
  81. }
  82. f2();
  83. return 0;
  84. }

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA0ODQ2Mw_size_16_color_FFFFFF_t_70 1

发表评论

表情:
评论列表 (有 0 条评论,197人围观)

还没有评论,来说两句吧...

相关阅读

    相关 算法时间复杂

    在 [算法基础][Link 1] 中,我们简单介绍了什么是算法、对算法的要求,以及说了评断算法效率的两大类方法。今天我们将重点介绍衡量算法效率的一个概念——时间复杂度。 --

    相关 算法时间复杂

    算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,比如排序就有前面的十大经典排序和几种奇葩排序,虽

    相关 算法 - 时间复杂

    注:本文仅为笔记 [原文][Link 1] [极客时间 - 数据结构与算法之美 - 03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?][- _ - 03

    相关 算法时间复杂

    时间复杂度就是通常我们简称的复杂度,O(f(n))表示。 常见的算法时间复杂度由小到大依次为: Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n\2)<