数据结构笔记：串
串的抽象数据类型
1234567891011121314151617181920212223ADT 串（string）DataOperation StrAssign(T, *chars): 生成一个其值等于字符串常量chars的串T StrCopy(T, S): 串S存在，由串S复制得串T ClearString(S): 串S存在，将串清空 StringEmpty(S): 若串S为空，返回true，否则返回false StrLength(S): 返回串S的元素个数，即串的长度 StrCompare(S, T): 若S>T，返回值>0，若S=T，返回0，若S<T，返回值<0 Concat(T, S1, S2): 用T返回由S1和S2联接而成的新串 SubString(Sub, S, pos, len): 串S存在，1≤pos≤StrLength(S)， 且0≤len≤StrLength(S)-pos+1，用sub ...
数据结构笔记：队列
队列的抽象数据类型
123456789101112ADT 队列（queue）DataOperation InitQueue(*Q): 初始化操作，建立一个空队列Q DestroyQueue(*Q): 若队列Q存在，则销毁它 ClearQueue(*Q): 将队列Q清空 QueueEmpty(Q): 若队列Q为空，返回true，否则返回false GetHead(Q, *e): 若队列Q存在且非空，用e返回队列Q的队头元素 EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素 DeQueue(*Q, *e): 删除队列Q中队头元素，并用e返回其值 QueueLength(Q): 返回队列Q的元素个数endADT
循环队列
循环队列的结构
1234561 typedef int QElemType; // QElemType类型根据实际情况而定，这里假设为int2 typedef struct {3 QElemType data[MAXSIZE];4 int front; // ...
数据结构笔记：栈
栈的抽象数据类型
123456789101112ADT 栈（stack）Dataoperation InitStack(*S): 初始化操作，建立一个空栈S DestroyStack(*S): 若栈存在，则销毁它 ClearStack(*S): 将栈清空 StackEmpty(S): 若栈为空，返回true，否则返回false GetTop(S, *e): 若栈存在且非空，用e返回S的栈顶元素 Push(*S, e): 若栈S存在，插入新元素e到栈S中并成为栈顶元素 Pop(*S, e): 删除栈S中栈顶元素，并用e返回其值 StackLength(S): 返回栈S的元素个数endADT
栈的顺序存储结构
栈的结构
123451 typedef int SElemType; // SElemType类型根据实际情况而定，这里假设为int2 typedef struct {3 SElemType data[MAXSIZE];4 int top; // 用于栈顶指针5 } SqStack;
进栈 ...
数据结构笔记：线性表(顺序存储结构&链式存储结构）（待填坑
线性表的抽象数据类型
123456789101112ADT 线性表(List)DataOperation InitList(*L); 初始化操作，建立一个空的线性表L ListEmpty(L); 若线性表为空，返回true，否则返回false ClearList(*L); 将线性表清空 GetElem(L, i, *e) 将线性表L中的第i个位置元素值返回给e LocateElem(L, e); 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败 ListInsert(*L, i, e); 在线性表L中的第i个位置插入新元素e ListDelete(*L, i, *e); 删除线性表L中第i个位置元素，并用e返回其值 ListLength(L); 返回线性表L的元素个数endADT
线性表的顺序存储结构
将所有的在线性表Lb中但不在La中的数据元素插入到La中
1234567891011 1 void unionL(SqList *La, SqList Lb) { 2 ...
贪心算法例题
硬币问题
1234567891011121314151617 1 // 硬币的面值 2 const int V[6] = {1, 5, 10, 50, 100, 500}; 3 4 // 输入 5 int C[6]; // C[0] = C_1, C[1] = C_5, ... 6 int A; 7 8 void solve() { 9 int ans = 0;10 for (int i = 5; i >= 0; i--) {11 int t = min(A / V[i], C[i]); //使用硬币i的枚数12 A -= t * V[i];13 ans += t;14 }15 16 printf("%d\n", ans);17 }
区间问题
12345678910111213141516171819202122232425262728 1 const int MAX_N = 100000; 2 3 // 输 ...
DFS和BFS的实例
深度优先搜索的两个实例：
部分和问题
1234567891011121314151617181920212223 1 // 输入 2 int a[MAX_N]; 3 int n, k; 4 5 // 已经从前i项得到了和sum，然后对于i项之后的进行分支 6 bool dfs(int i, int sum) { 7 // 如果前n项都计算过了，则返回sum是否与k相等 8 if (i == n) return sum == k; 9 10 // 不加上a[i]的情况11 if (dfs(i + 1, sum)) return true;12 13 // 加上a[i]的情况14 if (dfs(i + 1, sum + a[i])) return true;15 16 // 无论是否加上a[i]都不能凑成k就返回false17 return false;18 }19 20 void solve() {21 if (dfs(0, 0)) printf("Yes\n" ...
完全二叉树之堆
堆排序和快速排序一样，时间复杂度为Ο(N㏒N)。以升序排序为例，可以先建立最小堆，然后每次删除顶部元素并将顶部元素输出或者放入一个新的数组中，直到堆空为止。最终输出的或者存放在新数组中的数就已经是排序好的了。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 1 //第一种方法 2 #include <stdio.h> 3 4 int h[101]; //用来存放堆的数组 5 int n; //用来存储堆中元素的个数，也就是堆的大小 6 7 //交换函数，用来交换堆中的两个元素的值 8 void swap(int x, int y) { 9 int t;10 t = h[x];11 h[x] = h[y];12 h[y] = t;13 }14 15 //向下调整16 void sif ...
分别用DFS和BFS实现图的遍历
DFS模板：
1234567891011 1 void dfs(int step) { 2 if (...) //判断边界,到达边界则返回 3 return; 4 for (循环所有方向) { 5 if (...) { //可能需要判断条件 6 book[...] = 1; //标记 7 dfs(step+1); 8 book[...] = 0; //取消标记 9 }10 }11 }
用DPS遍历图。我们用一个二维数组e来储存图。
我们用上面二维数组中的(i, j)储存的数字来表示顶点i到顶点j是否有边——1表示有边，∞表示没有边，0表示自己到自己（即i等于j）。
12345678910111213141516171819202122232425262728293031323334353637383940414243 1 //图的遍历 - 深度优先 2 #include <s ...
栈
直接看实例吧，用栈判断回文
1234567891011121314151617181920212223242526272829303132333435363738 1 #include <stdio.h> 2 #include <string.h> 3 int main() { 4 char a[101], s[101]; 5 int i, len, mid, next, top; 6 7 gets(a); //读入一行字符串 8 len = strlen(a); //求字符串的长度 9 printf("%d\n", len);10 mid = len/2-1; //求字符串的中点11 printf("%d\n", mid);12 13 top = 0; //栈的初始化14 //将mid前的字符依次入栈15 for (i = 0; i <= mid; i++)16 s[++top] = a[i];17 18 ...
链表
2021-07-14 09:54:08
来填坑了。 链表是如何实现的呢？如下。
12345678910111213141516171819202122232425262728293031323334353637 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 //创建一个结构体用来表示链表的结点类型 5 struct node { 6 int data; 7 struct node *next; 8 }; 9 10 int main() {11 struct node *head, *p, *q, *t;12 int n, a;13 scanf("%d", &n);14 head = NULL; //头指针初始为空15 for (int i = 1; i <= n; i++) { //循环读入n个数16 scanf("%d", &a);17 ...