数据结构与算法

1.线性表

  1. // 线性表的顺序存储结构
  2. // 静态分配
  3. #include <stdio.h>
  5. /* 存储空间初始分配量 */
  6. #define MAXSIZE 10
  8. typedef struct {
  9.     int data[MAXSIZE];
  10.     int length;
  11. } SqList;
  13. // 初始化
  14. void InitList(SqList &L) {
  15.     for (int i=0; i<MAXSIZE; i++) {
  16.         L.data[i] = 0;
  17.     }
  18.     L.length = MAXSIZE;
  19. }
  21. // 插入元素
  22. bool ListInsert(SqList &L, int i, int e) {
  23.     if (i<1 || i>L.length+1)
  24.     {
  25.         return false;
  26.     }
  27.     if (L.length > MAXSIZE)
  28.     {
  29.         return false;
  30.     }
  31.     for (int j = L.length; j >= i; j--) {
  32.         L.data[j] = L.data[j-1]; // 将第i个元素及其以后的元素后移
  33.     }
  34.     L.data[i-1] = e;
  35.     L.length++;
  36.     return true;
  37. }
  39. // 删除元素
  40. bool ListDelete(SqList &L, int i, int &e) {
  41.     if (i<1 || i>L.length)
  42.     {
  43.         return false;
  44.     }
  45.     e = L.data[i-1];  // 被删除的元素赋值给e
  46.     for (int j = i; j <= L.length; j++)
  47.     {
  48.         L.data[j-1] = L.data[j];    // 将第i个位置以及以后前移
  49.     }
  50.     L.length++;
  51.     return true;
  52. }
  54. void printList(SqList &l) {
  55.     for (int i = 0; i < l.length; i++)
  56.     {
  57.         printf("list:%d,%d\n", i, l.data[i]);
  58.     }
  59.     printf("length=%d\n", l.length);
  60. }
  62. int main(int argc, char const *argv[]) {
  63.     SqList l;
  64.     InitList(l);
  65.     printList(l);
  66.     ListInsert(l, 1, 1);
  67.     printList(l);
  68.     ListInsert(l, 2, 2);
  69.     printList(l);
  70.     int e = -1;
  71.     if (ListDelete(l, 1, e)) {
  72.         printf("删除第1个元素成功，值为%d\n", e);
  73.         printList(l);
  74.     } else {
  75.         printf("删除失败\n");
  76.     }
  77.     return 0;
  78. }
  1. // 顺序表的动态分配
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. #define InitSize 10
  7. typedef struct {
  8.     int *data;      // 动态分配数组的指针
  9.     int MaxSize;    // 最大容量
  10.     int length;     // 当前长度
  11. } SqList;
  13. // 初始化
  14. void initList(SqList &l) {
  15.     // 用malloc申请连续内存，data表示首地址
  16.     l.data = (int *)malloc(InitSize*sizeof(int));
  17.     l.length = 0;
  18.     l.MaxSize = InitSize;
  19. }
  21. // 动态增加数组长度
  22. void increaseSize(SqList &l, int len) {
  23.     int *p = l.data;
  24.     l.data = (int *)malloc((l.MaxSize+len)*sizeof(int));
  25.     for (int i = 0; i < l.length; i++) {
  26.         l.data[i] = p[i];   // 将数据复制到新区域
  27.     }
  28.     l.MaxSize = l.MaxSize + len;
  29.     free(p);
  30. }
  32. int main(int argc, char const *argv[])
  33. {
  34.     SqList l;
  35.     initList(l);
  36.     increaseSize(l, 5);
  37.     return 0;
  38. }
  1. // 带头结点的单链表
  2. #include <stdlib.h>
  4. typedef int ElemType;
  5. typedef struct LNode
  6. {
  7.     ElemType data;
  8.     struct LNode *next;
  9. } LNode, *LinkList;
  11. // 初始化
  12. bool InitList(LinkList &l) {
  13.     l = (LNode *)malloc(sizeof(LNode));  // 分配一个头结点
  14.     if (l == NULL)
  15.     {
  16.         return false;
  17.     }
  18.     l->next = NULL;
  19.     return true;
  20. }
  22. bool isEmpty(LinkList &l) {
  23.     if (l->next == NULL)
  24.     {
  25.         return true;
  26.     }
  27.     return false;
  29. }
  1. // 双向链表
  2. #include <stdio.h>
  3. #include <stdlib.h>
  5. typedef int ElemType;
  7. typedef struct DNode {
  8.     ElemType data;
  9.     struct DNode *prior, *next;
  10. } DNode, *DLinkList;
  12. // 初始化
  13. bool InitDLinkList(DLinkList &l) {
  14.     l = (DNode *)malloc(sizeof(DNode)); // 分配头节点
  15.     if (l == NULL)
  16.     {
  17.         return false;
  18.     }
  19.     l->prior = NULL;
  20.     l->next = NULL;
  21.     return true;
  22. }
  24. // 在p节点后插入s节点
  25. bool InsertNextDNode(DNode *p, DNode *s) {
  26.     if (p == NULL || s == NULL)
  27.     {
  28.         return false;
  29.     }
  30.     s->next = p->next;  // 将p的后继节点设置为s的后继节点
  31.     if (p->next != NULL) // 如果p有后继节点
  32.     {
  33.         // 将p的后继节点的上一个设置为s
  34.         p->next->prior = s;
  35.     }
  36.     s->prior = p;
  37.     p->next = s;
  38. }
  40. // 删除p节点的后继节点
  41. bool DeleteNextDNode(DNode *p) {
  42.     if (p == NULL) {
  43.         return false;
  44.     }
  45.     DNode *q = p->next;
  46.     if (q == NULL)
  47.     {
  48.         return false;
  49.     }
  50.     p->next = q->next;
  51.     if (q->next != NULL)
  52.     {
  53.         q->next->prior = p;
  54.     }
  55.     free(q);
  56.     return true;
  57. }
  59. int main(int argc, char const *argv[])
  60. {
  61.     DLinkList l;
  62.     bool ret = InitDLinkList(l);
  63.     if (ret)
  64.     {
  65.         printf("初始化成功\n");
  66.     } else
  67.     {
  68.         printf("初始化失败\n");
  69.     }
  70.     return 0;
  71. }

2.栈

  1. // 栈(数组实现)
  2. #include <stdio.h>
  3. #define MaxSize 10
  5. typedef struct {
  6.     int data[MaxSize];
  7.     int top;
  8. } SqStack;
  10. // 初始化
  11. void InitStack(SqStack &s) {
  12.     s.top = -1;
  13. }
  15. bool IsEmpty(SqStack &s) {
  16.     if (s.top == -1)
  17.     {
  18.         return true;
  19.     }
  20.     return false;
  21. }
  23. // 入栈
  24. bool push(SqStack &s, int &x) {
  25.     // 栈已满
  26.     if (s.top == MaxSize - 1)
  27.     {
  28.         return false;
  29.     }
  30.     s.top++;
  31.     s.data[s.top] = x;
  32.     return true;
  33. }
  35. // 出栈
  36. bool pop(SqStack &s) {
  37.     if (s.top == -1)
  38.     {
  39.         return false;
  40.     }
  41.     int x = s.data[s.top];
  42.     printf("pop stack, value=%d\n", x);
  43.     s.top--;
  44.     return true;
  45. }
  47. int main(int argc, char const *argv[])
  48. {
  49.     SqStack stack;
  50.     InitStack(stack);
  51.     int x = 1;
  52.     push(stack, x);
  53.     pop(stack);
  54.     return 0;
  55. }
  1. /*
  2. * 检查括号是否成对出现，且没有交叉 
  3. */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  8. #define MaxSize 10
  10. // 定义栈
  11. typedef struct {
  12.     char data[MaxSize];
  13.     int top;
  14. } SqStack;
  16. // 初始化
  17. void initStack(SqStack &s) {
  18.     s.top = -1;
  19. }
  21. // 是否空
  22. bool isEmpty(SqStack &s) {
  23.     if (s.top == -1)
  24.     {
  25.         return true;
  26.     }
  27.     return false;
  28. }
  30. // 入栈
  31. bool push(SqStack &s, char x) {
  32.     if (s.top == MaxSize-1) {
  33.         return false;
  34.     }
  35.     s.top++;
  36.     s.data[s.top] = x;
  37.     return true;
  38. }
  40. // 出栈，用x返回
  41. bool pop(SqStack &s, char &x) {
  42.     if (s.top == -1)
  43.     {
  44.         return false;
  45.     }
  46.     x = s.data[s.top];
  47.     s.top--;
  48.     return true;
  49. }
  51. bool bracketCheck(char str[]) {
  52.     SqStack s;
  53.     initStack(s);
  54.     int length = strlen(str);
  55.     printf("str length is %d\n", length);
  56.     for (int i = 0; i < length; i++)
  57.     {
  58.         if (str[i] == '(' || str[i] == '[' || str[i] == '{') {
  59.             push(s, str[i]);  // 左括号则入栈
  60.         } else {
  61.             // 右括号检查，如果栈空，则失败
  62.             if (isEmpty(s))
  63.                 return false;
  64.             char topElem;
  65.             pop(s, topElem); // 栈顶元素出栈
  66.             if (str[i] == ')' && topElem != '(') {
  67.                 return false;
  68.             }
  69.             if (str[i] == ']' && topElem != '[') {
  70.                 return false;
  71.             }
  72.             if (str[i] == '}' && topElem != '{') {
  73.                 return false;
  74.             }
  75.         }
  76.     }
  77.     return isEmpty(s);
  78. }
  80. int main(int argc, char const *argv[])
  81. {
  82.     char ss[] = "([])[";
  83.     bool ret = bracketCheck(ss);
  84.     if (ret) {
  85.         printf("检查成功");
  86.     } else {
  87.         printf("检查失败");
  88.     }
  90.     return 0;
  91. }