• 数据结构之单向链表


    单向链表中的每个结点都有一个数据域、一个指针域。

    数据域用来存储结点的数据,指针域用来存储下一个结点所在的内存空间地址。

    这里完成了单向链表的五个基本功能,初始化、头插法、尾插法、删除结点、遍历链表。

    一、代码结构

    1.1单向链表的数据结构

    1. typedef struct node
    2. {
    3. int data;//数据域
    4. struct node * next;//指针域
    5. }Node;

    结点结构体中,数据域用整型变量data存储数据,指针域用指针变量next存储后继结点所在的内存空间地址。

    1.2操作单向链表的五个方法

    1.2.1 Node * initialize()

    初始化单向链表,返回头结点指针

    1.2.2 void headInsert(Node * head,int data)

    头插法,每次插入的新结点都会出现在首结点(第一个结点)的位置,也就是头结点的后面

    1.2.3 void tailInsert(Node * head,int data)

    尾插法,每次插入的新结点都会成为末结点的后继结点,变成新的末结点

    1.2.4 int delete(Node * head,int data)

    删除结点,根据指定的数据,删除对应的结点,删除成功返回1,删除失败返回0

    1.2.5 void reveal(Node * head)

    遍历单向链表

    二、主要代码

    1. /*
    2. 单向链表
    3. 初始化
    4. 头插法
    5. 尾插法
    6. 删除元素
    7. 遍历链表
    8. */
    9. #include
    10. #include
    11. //定义单向链表的数据结构
    12. typedef struct node
    13. {
    14. int data;//数据域
    15. struct node * next;//指针域
    16. }Node;
    17. //初始化链表
    18. Node * initialize()
    19. {
    20. Node * head=(Node*)(malloc(sizeof(Node)));//头结点(我更愿意称它为源结点)
    21. head->data=0;//头结点的数据域用来存储单链表中结点的个数
    22. head->next=NULL;//头结点指针域中当前为空,无指向
    23. return head;
    24. }
    25. //头插法
    26. void headInsert(Node * head,int data)
    27. {
    28. Node * newborn=(Node*)(malloc(sizeof(Node)));//创建新结点
    29. newborn->data=data;//给新结点的数据域赋值
    30. newborn->next=head->next;//给新结点的指针域赋值,值为头结点指针域的值
    31. head->next=newborn;//将头结点指针域指向新结点
    32. head->data++;//头结点的数据域自增,即单链表的结点个数增加
    33. }
    34. //尾插法
    35. void tailInsert(Node * head,int data)
    36. {
    37. Node * newborn=(Node*)(malloc(sizeof(Node)));//创建新结点
    38. newborn->data=data;//给新结点的数据域赋值
    39. newborn->next=NULL;//新结点的指针域值为空
    40. Node * start=head->next;//指针变量start通过头结点的指针域指向单链表中第一个结点
    41. while(start->next)//指针变量start的指针域若为NULL,则当前结点为末结点,循环终止
    42. {
    43. start=start->next;//结点向后遍历
    44. }
    45. start->next=newborn;//末结点指针域指向新结点
    46. head->data++;//头结点数据域自增
    47. }
    48. //删除元素
    49. int delete(Node * head,int data)
    50. {
    51. Node * start=head->next;//指针变量start通过头结点的指针域指向第一个结点
    52. Node * previousNode=head;//指针变量previousNode用来存储当前结点的前驱结点,
    53. while(start)//若指针变量start为NULL时,则说明没有找到指定数据,循环结束
    54. {
    55. if(start->data==data)//找到指定数据
    56. {
    57. previousNode->next=start->next;//当前结点的前驱结点指针域指向当前结点的后继结点
    58. free(start);//释放当前结点
    59. head->data--;//头结点的数据域自减,即链表中的结点数减少一个
    60. return 1;
    61. }
    62. previousNode=start;//previousNode存储当前结点,在下一轮循环中,将变为当前结点的前驱结点
    63. start=start->next;//start从当前结点向后遍历
    64. }
    65. return 0;
    66. }
    67. //遍历链表
    68. void reveal(Node * head)
    69. {
    70. printf("[");
    71. Node * start=head->next;
    72. for(;;start=start->next)
    73. {
    74. if(start->next!=NULL)//如果没有到达最后一个结点
    75. {
    76. printf("%d,",start->data);
    77. }else//否则,到达最后一个结点
    78. {
    79. printf("%d",start->data);
    80. break;
    81. }
    82. }
    83. printf("]\n");
    84. }
    85. int main(int argc,char * argv[])
    86. {
    87. Node * head=initialize();
    88. printf("head=\t%p\n",head);
    89. puts("-------------头插法-------------");
    90. //头插法
    91. headInsert(head,1);
    92. headInsert(head,2);
    93. headInsert(head,3);
    94. reveal(head);
    95. printf("length:%d\n\n",head->data);
    96. puts("-------------尾插法-------------");
    97. //尾插法
    98. tailInsert(head,4);
    99. tailInsert(head,5);
    100. tailInsert(head,6);
    101. reveal(head);
    102. printf("length:%d\n\n",head->data);
    103. puts("-------------删除结点-------------");
    104. puts("现有结点");
    105. reveal(head);
    106. puts("删除数据为3的结点");
    107. printf("%s\n",delete(head,3)==1?"删除成功":"删除失败");
    108. reveal(head);
    109. printf("length:%d\n\n",head->data);
    110. puts("删除数据为6的结点");
    111. printf("%s\n",delete(head,6)==1?"删除成功":"删除失败");
    112. reveal(head);
    113. printf("length:%d\n\n",head->data);
    114. puts("删除数据为1314的结点");//单链表中无此结点
    115. printf("%s\n",delete(head,1314)==1?"删除成功":"删除失败");
    116. reveal(head);
    117. printf("length:%d\n\n",head->data);
    118. }

    三、运行展示

     四、感受

            认真学习、研究数据结构,你会发现数据结构挺有意思的。

  • 相关阅读:
    Java skill - 动态指定feign的访问地址
    学会Linux,看完这篇就行了!
    c语言系统编程十四:Linux进程间的同步与互斥
    参与开源之夏 x OpenTiny 跨端跨框架 UI 组件库贡献,可以赢取奖金🏆!这份《OpenTiny 开源贡献指南》请收好🎁!
    STM32 通过USB接口读写挂载的SD卡(支持fatfs文件系统)
    pytorch_lightning模型训练加速技巧与涨点技巧
    亿级流量高并发下如何进行估算和调优
    (二十二)devops持续集成开发——jenkins服务代理Agent搭建
    Oracle——数据操纵DML(一)
    Spring - FactoryBean扩展接口
  • 原文地址:https://blog.csdn.net/yjhqukq/article/details/127568308