线性表

线性表的顺序存储（顺序表）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. const int MAXSIZE = 50;
  6. typedef struct SequenceList
  7. {
  8.     int* data;
  9.     int length;
  10. }SqList;
  12. void Initialize(SqList*, int);    //初始化顺序表
  13. bool AppendElem(SqList*, int);    //添加元素
  14. bool InsertElem(SqList*, int, int);    //插入元素
  15. bool DeleteElem(SqList*, int, int*); //删除元素
  16. void Destroy(SqList*);    //销毁顺序表
  18. bool IsEmpty(SqList*);    //是否为空
  19. bool IsFull(SqList*);    //是否已满
  20. int GetLength(SqList*);    //获取长度
  21. int GetElem(SqList*, int);    //按位查找
  22. int LocateElem(SqList*, int);    //按值查找
  23. void Traverse(SqList*);    //遍历顺序表
  25. int main(void)
  26. {
  27.     SqList L;
  28.     return 0;
  29. }
  31. void Initialize(SqList* L)
  32. {
  33.     L->data = (int*)malloc(sizeof(int) * MAXSIZE);
  34.     L->length = 0;
  35. }
  36. bool AppendElem(SqList* L, int val)
  37. {
  38.     if (IsFull(L))
  39.     {
  40.         return false;
  41.     }
  42.     else
  43.     {
  44.         L->data[L->length] = val;
  45.         L->length++;
  46.         return true;
  47.     }
  48. }
  49. bool InsertElem(SqList* L, int pos, int val)
  50. {
  51.     if (IsFull(L))
  52.     {
  53.         return false;
  54.     }
  55.     else
  56.     {
  57.         for (int i = L->length; i >= pos; i--)
  58.         {
  59.             L->data[i] = L->data[i - 1];
  60.         }
  61.         L->data[pos - 1] = val;
  62.         L->length++;
  63.         return true;
  64.     }
  65. }
  66. bool DeleteElem(SqList* L, int pos, int* backVal)
  67. {
  68.     if (IsEmpty(L))
  69.     {
  70.         return false;
  71.     }
  72.     else
  73.     {
  74.         *backVal = L->data[pos - 1];
  75.         for (int i = pos; i < L->length; i++)
  76.         {
  77.             L->data[i - 1] = L->data[i];
  78.         }
  79.         L->length--;
  80.         return true;
  81.     }
  82. }
  83. void Destroy(SqList* L)
  84. {
  85.     free(L->data);
  86.     L->data = NULL;
  87. }
  89. bool IsEmpty(SqList* L)
  90. {
  91.     if (L->length <= 0)
  92.     {
  93.         return true;
  94.     }
  95.     else
  96.     {
  97.         return false;
  98.     }
  99. }
  100. bool IsFull(SqList* L)
  101. {
  102.     if (L->length >= MAXSIZE)
  103.     {
  104.         return true;
  105.     }
  106.     else
  107.     {
  108.         return false;
  109.     }
  110. }
  111. int GetLength(SqList* L)
  112. {
  113.     return L->length;
  114. }
  115. int GetElem(SqList* L, int pos)
  116. {
  117.     return L->data[pos - 1];
  118. }
  119. int LocateElem(SqList* L, int val)
  120. {
  121.     for (int i = 0; i < L->length; i++)
  122.     {
  123.         if (L->data[i] == val)
  124.         {
  125.             return i + 1;
  126.         }
  127.     }
  128.     return -1;
  129. }
  130. void Traverse(SqList* L)
  131. {
  132.     for (int i = 0; i < L->length; i++)
  133.     {
  134.         printf("%d ", L->data[i]);
  135.     }
  136.     printf("\n");
  137. }

线性表的链式存储（单链表）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef struct ElemType
  5. {
  6.     char name[8];
  7.     int score;
  8. }ElemType;
  10. typedef struct LinkNode
  11. {
  12.     ElemType data;
  13.     struct LinkNode* pNext;
  14. }LinkNode, * LinkList;
  16. void HeadInitialize(LinkList*); //采用头插法初始化单链表
  17. void TailInitialize(LinkList*); //采用尾插法初始化单链表
  18. void AppendElem(LinkList, ElemType); //添加结点
  19. bool Insert(LinkList, int, ElemType); //插入新结点
  20. bool Delete(LinkList, int, ElemType*); //删除结点
  21. void Destroy(LinkList); //销毁链表
  23. bool IsEmpty(LinkList); //是否为空
  24. int GetLength(LinkList); //计算表长
  25. LinkNode* GetElem(LinkList, int); //按位查找结点
  26. LinkNode* LocateElem(LinkList, ElemType); //按值查找结点
  27. void Traverse(LinkList); //遍历单链表
  29. int main(void)
  30. {
  31.     LinkList L;
  33.     TailInitialize(&L);
  34.     Traverse(L);
  36.     AppendElem(L, { "sprout",100 });
  37.     Traverse(L);
  39.     Insert(L, 2, { "Insert",100 });
  40.     printf("在第2个结点处插入一个新节点\n");
  41.     Traverse(L);
  43.     ElemType e;
  44.     Delete(L, 4, &e);
  45.     printf("删除第4个结点，结点的名字是：%s，结点的成绩是：%d\n", e.name, e.score);
  46.     Traverse(L);
  48.     Destroy(L);
  49.     printf("销毁链表");
  51.     return 0;
  52. }
  54. void HeadInitialize(LinkList* pL)
  55. {
  56.     int length;
  58.     *pL = (LinkNode*)malloc(sizeof(LinkNode));
  59.     (*pL)->pNext = NULL;
  61.     printf("请输入你想要创建的结点个数：");
  62.     scanf("%d", &length);
  64.     for (int i = 0; i < length; i++)
  65.     {
  66.         LinkNode* pNew = (LinkNode*)malloc(sizeof(LinkNode));
  67.         printf("请输入第%d个结点的姓名：", i + 1);
  68.         scanf("%s", &pNew->data.name);
  69.         printf("请输入第%d个结点的成绩：", i + 1);
  70.         scanf("%d", &pNew->data.score);
  72.         pNew->pNext = (*pL)->pNext;
  73.         (*pL)->pNext = pNew;
  74.     }
  75.     printf("\n");
  76. }
  77. void TailInitialize(LinkList* pL)
  78. {
  79.     int length; //存储链表结点个数
  81.     *pL = (LinkNode*)malloc(sizeof(LinkNode));
  82.     LinkNode* pTail = *pL;
  83.     pTail->pNext = NULL;
  85.     printf("请输入您要创建的链表节点个数：");
  86.     scanf("%d", &length);
  88.     for (int i = 0; i < length; i++)
  89.     {
  90.         LinkNode* pNew = (LinkNode*)malloc(sizeof(LinkNode));
  91.         printf("请输入第%d个结点的姓名：", i + 1);
  92.         scanf("%s", &pNew->data.name);
  93.         printf("请输入第%d个结点的成绩：", i + 1);
  94.         scanf("%d", &pNew->data.score);
  96.         pNew->pNext = NULL;
  97.         pTail->pNext = pNew;
  98.         pTail = pNew;
  99.     }
  100.     printf("\n");
  101. }
  102. void AppendElem(LinkList L, ElemType e)
  103. {
  104.     LinkNode* p = L;
  105.     while (p->pNext != NULL)
  106.     {
  107.         p = p->pNext;
  108.     }
  109.     int length = GetLength(L);
  110.     printf("在链表的第%d个位置新添一个结点\n", length + 1);
  111.     LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));
  112.     q->data = e;
  113.     q->pNext = NULL;
  114.     p->pNext = q;
  115. }
  116. bool Insert(LinkList L, int pos, ElemType e)
  117. {
  118.     LinkNode* p = GetElem(L, pos - 1);
  119.     LinkNode* q = (LinkNode*)malloc(sizeof(LinkNode));
  120.     q->data = e;
  121.     q->pNext = p->pNext;
  122.     p->pNext = q;
  123.     return true;
  124. }
  125. bool Delete(LinkList L, int pos, ElemType* backElem)
  126. {
  127.     if (IsEmpty(L))
  128.     {
  129.         return false;
  130.     }
  131.     LinkNode* p = GetElem(L, pos - 1);
  132.     LinkNode* q = p->pNext;
  133.     *backElem = q->data;
  134.     p->pNext = p->pNext->pNext;
  135.     free(q);
  136.     q = NULL;
  137.     return true;
  138. }
  139. void Destroy(LinkList L)
  140. {
  141.     LinkNode* p = L;
  142.     while (L != NULL)
  143.     {
  144.         L = L->pNext;
  145.         free(p);
  146.         p = L;
  147.     }
  148. }
  150. bool IsEmpty(LinkList L)
  151. {
  152.     if (L->pNext == NULL)
  153.     {
  154.         return true;
  155.     }
  156.     return false;
  157. }
  158. int GetLength(LinkList L)
  159. {
  160.     if (IsEmpty(L))
  161.     {
  162.         return 0;
  163.     }
  164.     int i = 1;
  165.     LinkNode* p = L->pNext;
  166.     while (p->pNext != NULL)
  167.     {
  168.         p = p->pNext;
  169.         i++;
  170.     }
  171.     return i;
  172. }
  173. LinkNode* GetElem(LinkList L, int pos)
  174. {
  175.     if (pos < 1)
  176.     {
  177.         return NULL;
  178.     }
  179.     if (pos == 0)
  180.     {
  181.         return L;
  182.     }
  184.     int i = 1;
  185.     LinkNode* p = L->pNext;
  186.     while (i < pos && p != NULL)
  187.     {
  188.         p = p->pNext;
  189.         i++;
  190.     }
  191.     return p;
  192. }
  193. LinkNode* LocateElem(LinkList L, ElemType e)
  194. {
  195.     for (LinkNode* p = L->pNext; p != NULL; p = p->pNext)
  196.     {
  197.         if (p->data.name == e.name && p->data.score == e.score)
  198.         {
  199.             return p;
  200.         }
  201.     }
  202.     return NULL;
  203. }
  204. void Traverse(LinkList L)
  205. {
  206.     int i = 1;
  207.     for (LinkNode* p = L->pNext; p != NULL; p = p->pNext)
  208.     {
  209.         printf("链表第%d个结点的名字是：%s，成绩是：%d\n", i, p->data.name, p->data.score);
  210.         i++;
  211.     }
  212. }

栈

栈的顺序存储（顺序栈）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. const int MaxSize = 50;
  6. typedef struct SequenceStack
  7. {
  8.     int* data;
  9.     int top;
  10. }SqStack;
  12. void Initialize(SqStack*);
  13. bool Push(SqStack*, int);
  14. bool Pop(SqStack*, int*);
  15. void Destroy(SqStack*);
  17. bool IsEmpty(SqStack*);
  18. bool IsFull(SqStack*);
  19. int GetTop(SqStack*);
  21. int main(void)
  22. {
  23.     SqStack s;
  24.     return 0;
  25. }
  27. void Initialize(SqStack* pS)
  28. {
  29.     pS->data = (int*)malloc(sizeof(int) * MaxSize);
  30.     pS->top = 0;
  31. }
  32. bool Push(SqStack* pS, int val)
  33. {
  34.     if (pS->top == MaxSize)
  35.     {
  36.         return false;
  37.     }
  38.     else
  39.     {
  40.         pS->data[pS->top] = val;
  41.         pS->top++;
  42.         return true;
  43.     }
  44. }
  45. bool Pop(SqStack* pS, int* backVal)
  46. {
  47.     if (pS->top == 0)
  48.     {
  49.         return false;
  50.     }
  51.     else
  52.     {
  53.         pS->top--;
  54.         *backVal = pS->data[pS->top];
  55.         return true;
  56.     }
  57. }
  58. void Destroy(SqStack* pS)
  59. {
  60.     free(pS->data);
  61.     pS->top = 0;
  62. }
  64. bool IsEmpty(SqStack* pS)
  65. {
  66.     if (pS->top == 0)
  67.     {
  68.         return true;
  69.     }
  70.     return false;
  71. }
  72. bool IsFull(SqStack* pS)
  73. {
  74.     if (pS->top == MaxSize)
  75.     {
  76.         return true;
  77.     }
  78.     return false;
  79. }
  80. int GetTop(SqStack* pS)
  81. {
  82.     return pS->data[pS->top - 1];
  83. }

栈的链式存储（链栈）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef struct LinkNode
  5. {
  6.     int data;
  7.     struct LinkNode* next;
  8. }LNode;
  10. typedef struct LinkStack
  11. {
  12.     LNode* top;
  13.     LNode* bottom;
  14. }LStack;
  16. void Initialize(LStack*);
  17. void Push(LStack*, int);
  18. bool Pop(LStack*, int*);
  19. void Destroy(LStack*);
  21. bool IsEmpty(LStack*);
  22. int GetTop(LStack* pS);
  24. int main(void)
  25. {
  26.     LStack s;
  27.     return 0;
  28. }
  30. void Initialize(LStack* pS)
  31. {
  32.     pS->top = (LNode*)malloc(sizeof(LNode));
  33.     pS->bottom = pS->top;
  34.     pS->top->next = NULL;
  35. }
  36. void Push(LStack* pS, int val)
  37. {
  38.     LNode* pNew = (LNode*)malloc(sizeof(LNode));
  39.     pNew->data = val;
  40.     pNew->next = pS->top;
  41.     pS->top = pNew;
  42. }
  43. bool Pop(LStack* pS, int* backVal)
  44. {
  45.     if (pS->top == pS->bottom)
  46.     {
  47.         return false;
  48.     }
  49.     LNode* p = pS->top->next;
  50.     *backVal = pS->top->data;
  51.     free(pS->top);
  52.     pS->top = p;
  53.     return true;
  54. }
  55. void Destroy(LStack* pS)
  56. {
  57.     LNode* p = pS->top->next;
  58.     while (pS->top != pS->bottom)
  59.     {
  60.         free(pS->top);
  61.         pS->top = p;
  62.         p = p->next;
  63.     }
  64. }
  66. bool IsEmpty(LStack* pS)
  67. {
  68.     if (pS->top == pS->bottom)
  69.     {
  70.         return true;
  71.     }
  72.     return false;
  73. }
  74. int GetTop(LStack* pS)
  75. {
  76.     return pS->top->data;
  77. }

队列

队列的顺序存储（顺序队）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. const int MaxSize = 50;
  6. typedef struct SequenceQueue
  7. {
  8.     int* data;
  9.     int front;
  10.     int rear;
  11. }SqQueue;
  13. void Initialize(SqQueue*);
  14. bool EnQueue(SqQueue*, int);
  15. bool DeQueue(SqQueue*, int*);
  17. bool IsEmpty(SqQueue*);
  18. bool IsFull(SqQueue*);
  19. int GetFront(SqQueue*);
  21. int main(void)
  22. {
  23.     SqQueue q;
  24.     return 0;
  25. }
  27. void Initialize(SqQueue* pQ)
  28. {
  29.     pQ->data = (int*)malloc(sizeof(int) * MaxSize);
  30.     pQ->front = pQ->rear = 0;
  31. }
  32. bool EnQueue(SqQueue* pQ, int val)
  33. {
  34.     if ((pQ->rear + 1) % MaxSize == pQ->front)    //rear的下一个位置是front，说明队列已满
  35.     {
  36.         return false;
  37.     }
  38.     else
  39.     {
  40.         pQ->data[pQ->rear] = val;
  41.         pQ->rear = (pQ->rear + 1) % MaxSize;
  42.         return true;
  43.     }
  44. }
  45. bool DeQueue(SqQueue* pQ, int* backVal)
  46. {
  47.     if (pQ->rear == pQ->front)    //rear和front的位置重合，说明队列为空
  48.     {
  49.         return false;
  50.     }
  51.     else
  52.     {
  53.         *backVal = pQ->data[pQ->front];
  54.         pQ->front = (pQ->front + 1) % MaxSize;
  55.         return true;
  56.     }
  57. }
  59. bool IsEmpty(SqQueue* pQ)
  60. {
  61.     if (pQ->rear == pQ->front)
  62.     {
  63.         return true;
  64.     }
  65.     return false;
  66. }
  67. bool IsFull(SqQueue* pQ)
  68. {
  69.     if ((pQ->rear + 1) % MaxSize == pQ->front)
  70.     {
  71.         return true;
  72.     }
  73.     return false;
  74. }
  75. int GetFront(SqQueue* pQ)
  76. {
  77.     return pQ->data[pQ->front];
  78. }

队列的链式存储（链队）

  1. #include <stdio.h>
  2. #include <malloc.h>
  4. typedef struct LinkNode
  5. {
  6.     int data;
  7.     struct LinkNode* next;
  8. }LNode;
  10. typedef struct LinkQueue
  11. {
  12.     LNode* front;
  13.     LNode* rear;
  14. }LQueue;
  16. void Initialize(LQueue*);
  17. void EnQueue(LQueue*, int);
  18. bool DeQueue(LQueue*, int*);
  20. int main(void)
  21. {
  22.     LQueue q;
  23.     return 0;
  24. }
  26. void Initialize(LQueue* pQ)
  27. {
  28.     pQ->rear = (LNode*)malloc(sizeof(LNode));
  29.     pQ->front = pQ->rear;
  30.     pQ->front->next = NULL;
  31. }
  32. void EnQueue(LQueue* pQ, int val)
  33. {
  34.     LNode* pNew = (LNode*)malloc(sizeof(LNode));
  35.     pNew->data = val;
  36.     pNew->next = NULL;
  37.     pQ->rear->next = pNew;
  38.     pQ->rear = pNew;
  39. }
  40. bool DeQueue(LQueue* pQ, int* backVal)
  41. {
  42.     if (pQ->rear == pQ->front)
  43.     {
  44.         return false;
  45.     }
  46.     else
  47.     {
  48.         *backVal = pQ->front->next->data;
  49.         LNode* p = pQ->front->next;
  50.         pQ->front->next = p->next;
  51.         if (p == pQ->rear)    //如果队列中此时只有一个结点
  52.         {
  53.             pQ->rear = pQ->front;
  54.         }
  55.         free(p);
  56.         p = NULL;
  57.         return true;
  58.     }
  59. }