WHCSRL 技术网

3.数据结构C语言-循环单链表_static

3.1主要涉及循环单链表的初始化、尾插建表和合并带头指针的循环单链表/*合并带尾指针的循环单链表*/操作,代码实现如下:

  1. /*头文件、循环单链表存储结构的描述和各种操作函数的声明*/
  2. #include <stdio.h>
  3. typedef char ElemType;
  4. typedef struct CirculLinkList {
  5. ElemType data;
  6. struct CirculLinkList* next;
  7. }Node, * CLinkList;
  8. void InitList(CLinkList* CL); /*初始化循环单链表*/
  9. void PrintList(CLinkList CL); /*打印循环单链表*/
  10. void CreateCLinkList(CLinkList CL); /*尾插法创建带头指针的循环单链表*/
  11. CLinkList Merge_1(CLinkList CL1, CLinkList CL2); /*合并两个带头指针的循环单链表算法*/
  12. //CLinkList Merge_2(CLinkList CL1, CLinkList CL2); /*合并两个带尾指针的循环单链表算法*/
  13. /*各种操作函数的定义实现*/
  14. void InitList(CLinkList* CL) /*初始化循环单链表*/
  15. {
  16. *CL = (CLinkList)malloc(sizeof(Node));
  17. (*CL)->next = *CL; /*初始化头结点的next指针指向自己*/
  18. }
  19. void PrintList(CLinkList CL) /*打印循环单链表*/
  20. {
  21. Node* cur = CL->next;
  22. while (cur != CL)
  23. {
  24. printf("%%c ", cur->data);
  25. cur = cur->next;
  26. }
  27. printf(" ");
  28. }
  29. void CreateCLinkList(CLinkList CL) /*尾插法创建带头指针的循环单链表*/
  30. {
  31. Node* rear = CL; /*用于尾插法建表时指向链表的最后一个结点*/
  32. Node* s; /*用于创建新结点*/
  33. char c;
  34. int flag = 1;
  35. while (flag)
  36. {
  37. c = getchar();
  38. if (c != '$')
  39. {
  40. s = (Node*)malloc(sizeof(Node)); /*开辟新结点*/
  41. s->data = c; /*给新结点的数据域赋值*/
  42. rear->next = s; /*将原循环链表中指向头结点的结点的next指针指向新建结点*/
  43. s->next = CL; /*将新结点的next指针指向头结点*/
  44. rear = rear->next; /*尾指针顺移一位*/
  45. }
  46. else
  47. {
  48. flag = 0;
  49. }
  50. }
  51. rewind(stdin); /*清空输入缓冲区*/
  52. }
  53. CLinkList Merge_1(CLinkList CL1, CLinkList CL2) /*合并两个带头指针的循环单链表算法*/
  54. {
  55. Node* rear1 = CL1->next;
  56. Node* rear2 = CL2->next;
  57. while (rear1->next != CL1) /*使rear1指针指向CL1链表的表尾*/
  58. {
  59. rear1 = rear1->next;
  60. }
  61. while (rear2->next != CL2) /*使rear2指针指向CL2链表的表尾*/
  62. {
  63. rear2 = rear2->next;
  64. }
  65. rear1->next = CL2->next; /*使CL1链表表尾指向CL2链表的第一个结点*/
  66. rear2->next = CL1; /*使CL2链表表尾指向CL1链表的头结点*/
  67. free(CL2); /*释放掉CL2链表的头结点*/
  68. return CL1; /*返回合成后的链表的头指针*/
  69. }
  70. //CLinkList Merge_2(CLinkList CL1, CLinkList CL2) /*合并两个带尾指针的循环单链表算法*/
  71. //{
  72. // Node* h;
  73. // h = CL1->next; /*在CL1尾结点的next指针指向CL2的第一个节点之前,保存CL1链表的表头位置*/
  74. // CL1->next = CL2->next->next; /*将CL1尾结点的next指针指向CL2链表的第一个节点*/
  75. // free(CL2->next); /*在CL2尾结点的next指针指向CL1表头之前释放掉它原来所指的CL2表头空间*/
  76. // CL2->next = h; /*将CL2尾结点的next指针指向CL1表头*/
  77. // /*free(CL2);*/
  78. // return CL2; /*返回合成后的链表的尾指针*/
  79. //} /*带尾指针的循环单链表好处是在合并时时间复杂度为O(1)*/
  80. /*测试函数和主函数*/
  81. void TestCLinkList()
  82. {
  83. /*CLinkList CL;
  84. InitList(&CL);
  85. CreateCLinkList(CL);
  86. PrintList(CL);*/
  87. CLinkList CL1;
  88. CLinkList CL2;
  89. InitList(&CL1);
  90. InitList(&CL2);
  91. CreateCLinkList(CL1);
  92. CreateCLinkList(CL2);
  93. PrintList(Merge_1(CL1, CL2));
  94. }
  95. int main()
  96. {
  97. TestCLinkList();
  98. return 0;
  99. }

推荐阅读