线性表

顺序存储

链式存储

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. typedef int ElemType;
  5. typedef int Position;
  7. typedef struct LNode {
  8.     ElemType data;
  9.     struct LNode* next;
  10. } LNode, * LinkList;
  12. void PrintList(LinkList L);
  13. LinkList CreatListHead(LinkList L);  // 头插法
  14. LinkList CreatListTail(LinkList L);  // 尾插法
  15. LinkList GetElem(LinkList L, Position i); // 按位置查找
  16. LinkList LocateElem(LinkList L, ElemType e);
  17. bool ListFrontInsert(LinkList L, Position i, ElemType e);
  18. bool ListDelete(LinkList L, Position i);
  21. int main()
  22. {
  23.     LinkList L = NULL;
  24.     L = CreatListTail(L);
  25.     PrintList(L);
  27.     //LNode* search;
  28.     //search = GetElem(L, 100);
  29.     //if (search != NULL)
  30.     //{
  31.     //    printf("按序号查找成功！\n");
  32.     //    printf("%d\n", search->data);
  33.     //}
  35.     //search = LocateElem(L, 88);
  36.     //if (search != NULL)
  37.     //{
  38.     //    printf("按值查找成功！\n");
  39.     //    printf("%d\n", search->data);
  40.     //}
  42.     ListDelete(L, 2);
  43.     PrintList(L);
  44.     return 0;
  45. }
  47. // ========================函数区=========================
  48. void PrintList(LinkList L)
  49. {    
  50.     L = L->next;  // 因为统一要求带头结点，所以此处可以放心大胆的使用L->next。
  52.     while (L)  
  53.     {
  54.         printf("%d ", L->data);
  55.         L = L->next;
  56.     }
  57.     printf("\n");
  58. }
  60. // 头插法
  61. LinkList CreatListHead(LinkList L)
  62. {
  64.     L = (LinkList)malloc(sizeof(LNode));  // 
  65.     L->next = NULL;  // 如果是空表，确保没有安全隐患
  67.     LNode* p;
  68.     ElemType input;
  69.     scanf("%d", &input);
  70.     while (input != 9999) {
  71.         p = (LNode*)malloc(sizeof(LNode));
  72.         p->data = input;
  73.         p->next = L->next;
  74.         L->next = p;
  75.         scanf("%d", &input);
  76.     }
  77.     return L;
  78. }
  80. // 尾插法
  81. LinkList CreatListTail(LinkList L)
  82. {
  83.     L = (LinkList)malloc(sizeof(LNode));
  84.     LinkList s, r = L; // r表示链表表尾结点
  85.     ElemType input;
  86.     scanf("%d", &input);
  87.     while (input!=9999)
  88.     {
  89.         s = (LinkList)malloc(sizeof(LNode));
  90.         s->data = input;
  91.         r->next = s;
  92.         r = s;
  93.         scanf("%d", &input);
  94.     }
  95.     r->next = NULL;  // 尾结点的next指针赋值为NULL
  96.     return L;
  97. }
  99. LinkList GetElem(LinkList L, Position i)
  100. {
  101.     if (i == 0)
  102.         return L;
  103.     else if (i < 1)
  104.         return NULL;
  106.     LinkList p = L->next;
  107.     int j = 1;
  108.     while (p && j < i)
  109.     {
  110.         p = p->next;
  111.         ++j;
  112.     }
  113.     return p;
  114. }
  116. LinkList LocateElem(LinkList L, ElemType e)
  117. {
  118.     LinkList p = L->next;
  119.     while (p && p->data != e)
  120.         p = p->next;
  121.     return p;
  122. }
  124. bool ListFrontInsert(LinkList L, Position i, ElemType e)
  125. {
  126.     LinkList p = GetElem(L, i - 1);  // 拿到第i-1个元素的指针
  127.     if (!p)
  128.         return false;
  130.     LinkList s = (LinkList)malloc(sizeof(LNode));
  131.     s->data = e;
  133.     s->next = p->next;
  134.     p->next = s;
  136.     return true;
  137. }
  139. bool ListDelete(LinkList L, Position i)
  140. {
  141.     LinkList p = GetElem(L, i - 1);
  143.     if (!p)
  144.         return false;
  146.     LinkList q = p->next;
  147.     p->next = q->next;
  148.     free(q);
  149.     q = NULL; // 为了避免野指针
  150.     return true;
  151. }

栈

顺序栈

  1. #include <stdio.h>
  3. #define MaxSize 50
  4. typedef int ElemType;
  5. typedef struct {
  6.     ElemType data[MaxSize];
  7.     int top;
  8. } SqStack;
  10. void InitStack(SqStack& S);
  11. bool IsEmpty(SqStack S);
  12. bool IsFull(SqStack S);
  13. bool Push(SqStack& S, ElemType x);
  14. bool Pop(SqStack& S, ElemType& x);
  15. bool GetTop(SqStack S, ElemType& x);
  18. int main()
  19. {
  20.     SqStack S;
  21.     bool flag;
  23.     InitStack(S);
  24.     flag = IsEmpty(S);
  25.     ElemType ele;
  26.     if (flag) {
  27.         printf("栈是空的.\n");
  28.     }
  29.     Push(S, 3);
  30.     Push(S, 4);
  31.     Push(S, 5);
  32.     flag = GetTop(S, ele);
  33.     if (flag)
  34.         printf("栈顶元素：%d\n", ele);
  36.     flag = Pop(S, ele);
  37.     if (flag)
  38.         printf("弹出元素：%d\n", ele);
  40.     return 0;
  41. }
  44. // =========================函数区=======================
  45. void InitStack(SqStack &S)
  46. {
  47.     S.top = -1;
  48. }
  50. bool IsEmpty(SqStack S)
  51. {
  52.     return -1 == S.top;
  53. }
  55. bool IsFull(SqStack S)
  56. {
  57.     return MaxSize - 1 == S.top;
  58. }
  60. bool Push(SqStack& S, ElemType x)
  61. {
  62.     if (IsFull(S))
  63.         return false;
  64.     else {
  65.         S.data[++S.top] = x;
  66.         return true;
  67.     }
  68. }
  70. bool Pop(SqStack& S, ElemType& x)
  71. {
  72.     if (IsEmpty(S))
  73.         return false;
  74.     else {
  75.         x = S.data[S.top--];
  76.         return true;
  77.     }
  78. }
  80. bool GetTop(SqStack S, ElemType& x)
  81. {
  82.     if (IsEmpty(S))
  83.         return false;
  84.     else {
  85.         x = S.data[S.top];
  86.         return true;
  87.     }
  88. }

链栈（不重要）

一句话：头部插入，头部删除。

  1. typedef struct LinkNode {
  2.     ElemType data;
  3.     struct LinkNode* next;
  4. }* LinkStack;

队列

顺序存储：循环队列

链式存储