数据结构与算法分析——C语言描述 第三章的单链表

2022-09-07 15:09:02

数据结构与算法分析——C语言描述 第三章的单链表

很基础的东西。走一遍流程。有人说学编程最简单最笨的方法就是把书上的代码敲一遍。这个我是头文件是照抄的。.c源文件自己实现。

list.h

  1. typedef int ElementType;
  2. #ifndef _List_H
  3. #define _List_H
  4. struct Node;
  5. typedef struct Node *PtrToNode;
  6. typedef PtrToNode List;
  7. typedef PtrToNode Position;
  8. List CreatList();
  9. List MakeEmpty(List L);
  10. int IsEmpty(List L);
  11. int IsLast(Position P, List L);
  12. Position Find(ElementType X, List L);
  13. void Delete(ElementType X, List L);
  14. Position FindPrevious(ElementType X, List L);
  15. void Insert(ElementType X, Position P);
  16. void DeleteList(List L);
  17. Position Header(List L);
  18. Position First(List L);
  19. Position Advance(Position P);
  20. ElementType Retrieve(Position P);
  21. #endif

list.c

  1. #include"list.h"
  2. #include<stdlib.h>
  3. #include"fatal.h"
  4. struct  Node
  5. {
  6. ElementType Element;
  7. Position Next;
  8. };
  9. List CreatList() {
  10. List l = malloc(sizeof(struct Node));
  11. if (l == NULL)
  12. Error("out of memory");
  13. l->Next = NULL;
  14. return l;
  15. }
  16. List MakeEmpty(List L) {
  17. if (L != NULL)
  18. DeleteList(L);
  19. L = malloc(sizeof(struct Node));
  20. if (L == NULL)
  21. FatalError("Out of memory");
  22. L->Next = NULL;
  23. return L;
  24. }
  25. int IsEmpty(List L) {
  26. return L->Next == NULL;
  27. }
  28. int IsLast(Position P, List L) {
  29. return P->Next == NULL;
  30. }
  31. Position Find(ElementType X, List L) {
  32. Position P;
  33. P = L->Next;
  34. while (P != NULL&&P->Element != X)
  35. {
  36. P = P->Next;
  37. }
  38. return P;
  39. }
  40. void Delete(ElementType X, List L) {
  41. Position P;
  42. P = FindPrevious(X, L);
  43. if (!IsLast(P, L)) {
  44. Position TmpCell = P->Next;
  45. P->Next = TmpCell->Next;
  46. free(TmpCell);
  47. }
  48. }
  49. Position FindPrevious(ElementType X, List L) {
  50. Position P;
  51. P = L;
  52. while (P->Next != NULL&&P->Next->Element != X)
  53. P = P->Next;
  54. return P;
  55. }
  56. void Insert(ElementType X, Position P) {
  57. Position tmpCell;
  58. tmpCell = malloc(sizeof(struct Node));
  59. if (tmpCell == NULL)
  60. FatalError("Out of space!!");
  61. tmpCell->Element = X;
  62. tmpCell->Next = P->Next;
  63. P->Next = tmpCell;
  64. }
  65. void DeleteList(List L) {
  66. Position p;
  67. p = L->Next;
  68. L->Next = NULL;
  69. while (p != NULL){
  70. Position tmp;
  71. tmp = p->Next;
  72. free(p);
  73. p = tmp;
  74. }
  75. }
  76. Position Header(List L) {
  77. return L;
  78. }
  79. Position First(List L) {
  80. return L->Next;
  81. }
  82. Position Advance(Position P) {
  83. return P->Next;
  84. }
  85. ElementType Retrieve(Position P) {
  86. return P->Element;
  87. }

fatal.h

    1. #include<stdio.h>
    2. #include<stdlib.h>
    3. #define Error(Str) FatalError(Str)
    4. #define FatalError(Str) fprintf(stderr,"%s\n",Str),exit(1)
上一篇：java用正则方法验证文件名是否合法


下一篇：SQL Server 2008 R2没有卸载干净