3.数据结构C语言-循环单链表_static
3.1主要涉及循环单链表的初始化、尾插建表和合并带头指针的循环单链表/*合并带尾指针的循环单链表*/操作,代码实现如下:
- /*头文件、循环单链表存储结构的描述和各种操作函数的声明*/
- #include <stdio.h>
-
- typedef char ElemType;
- typedef struct CirculLinkList {
- ElemType data;
- struct CirculLinkList* next;
- }Node, * CLinkList;
-
- void InitList(CLinkList* CL); /*初始化循环单链表*/
- void PrintList(CLinkList CL); /*打印循环单链表*/
- void CreateCLinkList(CLinkList CL); /*尾插法创建带头指针的循环单链表*/
- CLinkList Merge_1(CLinkList CL1, CLinkList CL2); /*合并两个带头指针的循环单链表算法*/
- //CLinkList Merge_2(CLinkList CL1, CLinkList CL2); /*合并两个带尾指针的循环单链表算法*/
-
- /*各种操作函数的定义实现*/
- void InitList(CLinkList* CL) /*初始化循环单链表*/
- {
- *CL = (CLinkList)malloc(sizeof(Node));
- (*CL)->next = *CL; /*初始化头结点的next指针指向自己*/
- }
-
- void PrintList(CLinkList CL) /*打印循环单链表*/
- {
- Node* cur = CL->next;
- while (cur != CL)
- {
- printf("%%c ", cur->data);
- cur = cur->next;
- }
- printf("
");
- }
-
- void CreateCLinkList(CLinkList CL) /*尾插法创建带头指针的循环单链表*/
- {
- Node* rear = CL; /*用于尾插法建表时指向链表的最后一个结点*/
- Node* s; /*用于创建新结点*/
- char c;
- int flag = 1;
- while (flag)
- {
- c = getchar();
- if (c != '$')
- {
- s = (Node*)malloc(sizeof(Node)); /*开辟新结点*/
- s->data = c; /*给新结点的数据域赋值*/
- rear->next = s; /*将原循环链表中指向头结点的结点的next指针指向新建结点*/
- s->next = CL; /*将新结点的next指针指向头结点*/
- rear = rear->next; /*尾指针顺移一位*/
- }
- else
- {
- flag = 0;
- }
- }
- rewind(stdin); /*清空输入缓冲区*/
- }
-
- CLinkList Merge_1(CLinkList CL1, CLinkList CL2) /*合并两个带头指针的循环单链表算法*/
- {
- Node* rear1 = CL1->next;
- Node* rear2 = CL2->next;
- while (rear1->next != CL1) /*使rear1指针指向CL1链表的表尾*/
- {
- rear1 = rear1->next;
- }
- while (rear2->next != CL2) /*使rear2指针指向CL2链表的表尾*/
- {
- rear2 = rear2->next;
- }
- rear1->next = CL2->next; /*使CL1链表表尾指向CL2链表的第一个结点*/
- rear2->next = CL1; /*使CL2链表表尾指向CL1链表的头结点*/
- free(CL2); /*释放掉CL2链表的头结点*/
- return CL1; /*返回合成后的链表的头指针*/
- }
-
- //CLinkList Merge_2(CLinkList CL1, CLinkList CL2) /*合并两个带尾指针的循环单链表算法*/
- //{
- // Node* h;
- // h = CL1->next; /*在CL1尾结点的next指针指向CL2的第一个节点之前,保存CL1链表的表头位置*/
- // CL1->next = CL2->next->next; /*将CL1尾结点的next指针指向CL2链表的第一个节点*/
- // free(CL2->next); /*在CL2尾结点的next指针指向CL1表头之前释放掉它原来所指的CL2表头空间*/
- // CL2->next = h; /*将CL2尾结点的next指针指向CL1表头*/
- // /*free(CL2);*/
- // return CL2; /*返回合成后的链表的尾指针*/
- //} /*带尾指针的循环单链表好处是在合并时时间复杂度为O(1)*/
-
- /*测试函数和主函数*/
- void TestCLinkList()
- {
- /*CLinkList CL;
- InitList(&CL);
- CreateCLinkList(CL);
- PrintList(CL);*/
- CLinkList CL1;
- CLinkList CL2;
- InitList(&CL1);
- InitList(&CL2);
- CreateCLinkList(CL1);
- CreateCLinkList(CL2);
- PrintList(Merge_1(CL1, CL2));
-
- }
- int main()
- {
- TestCLinkList();
- return 0;
- }
推荐阅读