《实验3 循环链表的操作》由会员分享，可在线阅读，更多相关《实验3 循环链表的操作（5页珍藏版）》请在金锄头文库上搜索。
1、试验三循环链表的操作一试验目的通过本试验中循环链表的使用，进一步娴熟把握链表的操作方式二 试验内容（1） 建立一个单循环链表。（2） 实现单循环链表的逆置。三 试验要求（1） 依据试验内容编写程序，上机调试并获得运行结果（2） 撰写试验报告四 关键操作思路与算法（1） 建立循环链表首先要用 s 来表示需要建立的每个节点，用r 来保存上一个 s 节点，然后在下一次进展循环时，让 s = r-next，如此循环往复，一个用尾插法建立的单链表就形成了，然后在最终的时候进展一次推断看 L 链表的尾节点是否为头 L，假设不成立，那么让尾节点指向头。算法如下:1. /建立带头结点的循环单链表2. Link
2、edList* CreateListH() 3. 4. LinkedList *L = NULL;5. LinkedList *s, *r = NULL;6. char ch;7. ch = getchar();8. while(ch != ”$”)9.10. s = (LinkedList* )malloc(sizeof(LinkedList);11. s-data = ch;12.if(L = NULL)/!两个等号13. L = s;14. else15. r-next = s;16. r = s;17. ch = getchar();18.19. if(r != L)20. r-nex
3、t = L;21. return L;22. （2） 循环链表倒置首先要把头结点用 cur 保存下来，然后把头结点的下一个节点用 pre 保存，然后每次让 pre 指向 cur，然后循环，每次执行单步倒置之后，让 pre 和 cur 分别指向它们的下一个，当 pre 走到 head 时，让 pre-next 指向 cur，这样就完成了整个循环链表的倒置，然后返回 cur 即原链表的尾节点，即新链表的头结点算法如下:1. /链表倒置2. LinkedList* ReList(LinkedList *head) 3. 4. LinkedList *cur,*pre,*temp;5. cur=hea
4、d;6. pre=head-next;7. while(pre != head)8.9. temp=pre-next;10. pre-next=cur;11. cur=pre;12. pre=temp;13.14. pre-next = cur;15. return cur;16. 五源代码23. #include24. #include25. #include26. #include27. #include28. #define TRUE 129. #define FALSE 030. #define OK 131. #define ERROR -1 32.33. typedef char
5、datatype;34. /定义节点35. typedef struct node36. 37. datatype data;38. struct node *next;39. LinkedList;40. /置空表41. void InitLList(LinkedList* L)42. 43.L-next = NULL;44. 45. /建立带头结点的循环单链表46. LinkedList* CreateListH()47. 48. LinkedList *L = NULL;49. LinkedList *s, *r = NULL;50. char ch;51. ch = getchar()
6、;52. while(ch != ”$”)53.54. s = (LinkedList* )malloc(sizeof(LinkedList);55. s-data = ch;56.if(L = NULL)/!两个等号57. L = s;58. else59. r-next = s;60. r = s;61. ch = getchar();62.63. if(r != L)64. r-next = L;65. return L;66. 67. /输出带头节点的循环单链表68. void PrintList(LinkedList *L)69. 70. LinkedList *p;71. int
7、i = 0;72. p = L;73. while(i data);76. p = p-next;77.i+;78.79.printf(“n“);80.81.82./链表倒置83.LinkedList* ReList(LinkedList *head)84.85.LinkedList *cur,*pre,*temp;86.cur=head;87.pre=head-next;88.while(pre != head)89.90.temp=pre-next;91.pre-next=cur;92.cur=pre;93.pre=temp;94.95.pre-next = cur;96.return c
8、ur;97.98./主函数99.int main()100.101.LinkedList *a;102.printf(“请输入表输入$代表输入完毕:“);103.a= CreateListH();104.printf(“挨次输出n“);105.PrintList(a);106./倒置之后的结果107.printf(“倒序输出n“);108.a = ReList(a);109.PrintList(a);110.return 0;111.六代码测试图七.试验总结:本节试验，我学到了循环线表和链表的倒置，循环链表它是在单链表根底上让尾节点指向链表头结点，这样就形成了一个循环链表，倒置链表算法就是设立两个节点，一个指向第一个节点 cur，一个指向下一个节点 pre，并让 pre 的 next 指向 cur，然后每次让两个节点往后移直到完成整个链表的倒置
