行业知识
C语言 数据结构与算法
2026-11-13 09:20:09
来源：互联网转载
文章目录
- 排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 快速排序
- 查找算法
- 顺序查找
- 二分查找
- 顺序表
- 数组
- 链表
- 链表的初始化（只生成头结点）
- 栈（stack）
- 队列
- 栈的应用
- 串
- 串的基本操作
- 矩阵
- 树
- 二叉树链式存储
- 二叉排序树
- 哈夫曼树（最小权值树）
- 邻接矩阵
- 邻接表
- 带权图
- 深度优先遍历 DFS
- 广度优先遍历算法
- 最小生成树
- 普利姆算法（Prim）
- 克鲁斯卡尔算法（Kruskal）
- 最短路径
- 迪杰斯特拉（Dijkstra）
- 弗洛伊德（Floyd）
- 拓扑排序
- AOV网
排序算法
冒泡排序
-
冒泡排序
（）思想：两数比较 将最大 或 最小 的元素，放到最后。
int i, j, temp;// 定义 外层循环变量 i，// i 外层循环变量，j 内层循环变量 ，temp 临时变量for( i=0 ; i// 外层 控制 元素 比较多少躺 for( j=0 ; j//内层 控制 元素 比较次数 if( arr[j] arr[j+1] ){//从小到大 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } KeyType key;}RecType;//单个节点 的 数据类型typedef struct{ Rectype r[10000]; int len;//顺序表长度}Sqlist;//顺序表 的 数据类型int i, j, temp;Sqlist *q;for(i=0 ; ilen-i-1 ;j++){ if( q->r[j].key >q->r[j+1].key ){ temp = q->r[j].key; q->r[j].key = q->r[j+1].key; q->r[j+1].key = temp; } }}注意：冒泡排序 稳定，最多执行 n(n-1)/2 次。
（）选择排序
-
简单选择排序
思想：找 最大 或 最小 的元素，往前放，分成 "已排序" 和 "待排序" 序列。
void selectSort(int arr[], int len){ int i, j ,temp, min; for(i=0 ; i选择排序 不稳定，平均比较次数 n(n-1)/2 次。
插入排序
-
直接插入排序
思想：由后向前 查找 确定的位置，并插入元素。
void insertSort(int arr, int len){ int i, j, temp; for( i=1; i =0 && arr[j]>temp ;j--){ arr[j+1] = arr[j];// 元素后移，为 待插入元素 腾空位置 arr[j+1] = temp;// 插入 比较的后一位 } }直接插入排序，是在有序基础上，速度最快且最稳定的排序方法，最多执行 n(n-1)/2 次。
希尔排序
-
希尔排序
希尔排序：又称为 "缩小增量排序"。思想：按照 步长 进行分组，然后每一组的 第 几个 元素 进行排序。增量 及 步长。
// dk 是 增量步长void shellInsert(int arr[], int len, int dk){ int i, j, temp;// i 循环变量，j 前面组的位置，temp 临时变量 for( i=dk; i //判断每组的 第几个元素大小 if( arr[i] temp ; j-=dk ){ //前面的值 给到 后面 arr[j+dk] = arr[j]; } arr[j+dk] = tmep; } } }希尔排序 是 不稳定的。
快速排序
-
快速排序
基准值，i 从前向后找，比基准值大的元素，j 从后向前找，找比基准值小的元素。最后 结束的条件是 i = j ，此时 将 基准值 放到这个位置。
int getPivot(int arr[], int low, int high){ int pivot = arr[low]; while( low = pivot ){ high--; } // 找到了 比基准值小的元素，将 元素 给到 i 位置 arr[low] = arr[high]; // i 从前向后找，找比 基准值 大 的元素 while( low next;//指针后移 } //返回链表长度 return count; } -
链表的遍历（数据域）
void foreach(LinkList head){ if(!head){ return; } LinkList p = head->next; while(p){ printf("%d ",p->data); p = p->next; } } -
链表的清空
void clear(LinkList head){ if(!head){ return; } Node *p = head->next; while(p){ // q 存放的是，p 下一个结点的地址 LinkList q = p->next; // 释放 p free(p); p = q; } head->next = NULL; } -
链表的销毁
void destory(LinkList head){ if(!head){ return; } clear(head); free(head);// 释放头结点 head = NULL;// 指针变量 设置为 空 } -
链表的插入（尾插法）
void insert(LinkList head){ if(!head){ return; } int num; printf("请输入要插入的结点数量："); scanf("%d",&num); Node *q = head; for(int i=0; i LinkList p = (Node *)malloc(sizeof(Node)); printf("请输入数据域的值："); scanf("%d",&p-data); q->next = p; q = q->next; } q->next = NULL; }尾插法 生成 链表。
-
链表的插入（头插法）
void insert(LinkList head){ if(!head){ return; } int num; printf("请输入要插入的结点数量："); scanf("%d",&num); for(int i=0; i Node *p = (Node *)malloc(sizeof(Node)); printf("请输入数据域的值："); scanf("%d",&p-data); p->next = NULL; // 头插法 p->next = head->next; head->next = p; } }头插法，经常用 头指针 及逆行元素的插入。
-
链表的删除
// 根据 元素值 去删除 这个结点void delete(LinkList head, int value){ if(!head){ return; } Node *p = head;// p 指针 指向 头结点的下一个 Node *q; while( p->next ){ if( p->next->data == value ){// 若满足条件，则 p 就是待删除元素结点的直接前驱 q = p->next;// 令 q 指向 待删除结点 p->next = q->next;// 直接前驱结点 指向 待删除结点的 后一位结点 free(q);// 此时 释放结点 } else{ p = p->next; } } }删除一个结点，必须知道这个结点的 直接前驱。
栈（stack）
-
栈的特点：先进后出 / 后进先出
1、栈 分成了 "栈顶" 与 "栈底" （在栈顶进行元素的插入和删除）2、入栈(push)出栈(pop)
-
栈的顺序存储（使用 数组）
数组的首地址 做 "栈顶" 还是 "栈底" 比较好？ 答：做 "栈底" 比较好。
因为 栈顶 要进行元素的插入和删除操作，所以数组尾部更适合比较频繁的插入和删除。
-
栈 的 结构体
typedef struct Stack{ int data[MXA];//数据域 (MAX 为 宏定义值) int size;//栈的大小 (指 栈中的元素个数) }Stack, * SeqStack; -
栈 的 初始化
SeqStack create(){ //创建栈，相当于 动态开辟一个数组出来 SeqStack p = (Stack *)malloc(sizeof(Stack)); if(!p){ printf("空间开辟失败！"); return; } //初始化 栈 的大小 p->size = 0; //初始化 栈中的元素 for(int i=0; i p-data[i] = 0; } return p; } -
入栈
void push(SeqStack stack, int data){ if(!stack){ return; } //入栈 需要判断 栈是否已满 if( stack->size == MAX ){ printf("栈已满！\n"); return; } // stack->size 栈的大小 就是 待插入元素 的下一个位置 stack->data[stack->size] = data; //改变栈的大小 stack->size++; }入栈 需要注意 栈是否 不存在 and 已满。
-
出栈
void pop(SeqStack stack){ if(!stack) return; if(stack->size == 0){ printf("栈已空\n"); return; } //删除一个元素 stack->data[stack->size -1] = 0; //改变栈的大小 stack->size --; }出栈 需要注意 栈是否 不存在 and 已空。
-
遍历 栈中元素
void forerachStack(SeqStack stack){ if(!stack) return; for(int i=0;isize; i++) printf("%d ",stack->data[i]); }-
栈 的 链式存储（链表）
链表的头结点端 做 “栈顶” 还是 “栈底” 比较好？
答：做 “栈顶” 比较好。
因为 链表的头结点端 可以更方便的进行元素的 插入(头插法) and 删除(头结点做直接前驱)。
-
栈链式存储 结构体
//结点结构体trpedef struct Node{ int data; struct Node *next;}Node;//栈的结构体trpedef struct Stack{ struct Node header;//头结点 int size;//栈的大小 即元素个数 }Stack, *LinkStack; -
初始化栈
LinkStack inir_LinkStack(){ // myStack 是指针，指向所申请的空间 LinkStack myStack = (Stack *)malloc(sizeof(Stack)); if(!Stack) return NULL; //初始化 长度为0 myStack->size = 0; //相当于 初始化 链表的头结点 指针域 myStack->header.next = NULL; }什么时候使用 " -> " ,什么时候使用 " . " ？
-> 在指针的时候
. 在变量名的时候
-
注意事项
struct Node *list;list->next list->nextstruct Node a;a.data a.next
-
入栈
void push(LinkStack stack, int data){ if(!stack) return; //创建一个结点 Node *p = (Node *)malloc(sizeof(Node)); //给 结点数据域 赋值 p->data = data; //头插法 先连后面 p->next= stack->header.next; stack->header.next = p; //改变 栈中元素 的个数 stack->size ++; } -
出栈
void pop(LinkStack stack){ //判断栈是否存在 if(!stack) return; //判断栈空 if(stack->size ==0){ printf("栈中无元素！\n"); return; } //定义一个节点类型的指针，用作删除结点 Node *p = stack->header.next; //头结点 连接到 删除结点 的后边 stack->header.next = p->next; //释放结点 free(p); //更新 栈的大小 stack->size --; }队列
-
队列：先进先出 后进后出
1、只允许 从一端 添加元素，从 另一端 删除元素2、队头 出元素，队尾 进元素3、push 入队pop 出队
-
队列的顺序存储
数组的首地址做 “队头” 好，还是 “队尾” 比较好？
答：都一样。
做 队头 和 队尾 差别不大，因为都需要移动大量元素。
-
队列的结构体
typedef struct Queue{ int data[MAX];//顺序存储 数组模拟的队列 int size;//队列的大小(队列中元素的个数)}Queue, *SeqQueue; -
队列的初始化（数组头做队头，数组尾做队尾）
SeqQueue init(){ //申请队列空间，即数组空间 SeqQueue p = (Queue *)malloc(sizeof(Queue)); if(!p){ return NULL; } //初始化队列大小 p->size = 0; for(int i=0; i p-data[i] = 0; } reutrn p; } -
入队
void push(SeqQueue p, int value){ if(!p){//队列不存在 return; } if(p->size == MAX){ printf("队列元素已满！\n"); return; } //插入元素(进队) p->data[p->size] = value; //改变队列元素个数 p->size ++; } -
出队
void push(SeqQueue p){ if(!p){//队列不存在 return; } if(p->size == 0){ printf("队列元素已空！\n"); return; } //出队 删除数组首元素 for(int i=0; isize -1 ;i++){ p->data[i] = p->data[i+1]; } //改变队列元素个数 p->size --; }要记得，看到循环里边有 i+1 的时候，要改变 最终值。
-
队列的链式存储
链表的 头结点端 做 “队头” 还是 “队尾” 比较好？
答：做 “队头” 好。
因为 头结点端 进行删除方便，尾端 插入元素方便（尾插法）。
-
队列的结构体
//队列的结构体typedef struct LQueue{struct Node header; //头结点int size; //队列大小struct Node* pTail; //尾结点指针}LQueue, *LinkQueue; -
循环队列
//队满front = (rear + 1)%n;// front 头，rear 尾//队空front = rear;// 头指针 指向 尾指针时，队为空
栈的应用
- 前 中 后 缀表达式 如何计算？
首先运算优先级最高的，然后 将 运算符放两个整体之前 就是 前缀，放两个整体之后，就是 后缀。
串
-
零个 或者多个任意字符组成的 有限序列 是我们的字符串。
-
串 是 内容受限的线性表。
-
子串：一个串中 任意个连续字符组成的子序列（含空串）。
"*jkj12k0"//它的子串有哪些？ // 单字符6// 双字符7// 三字符6// 四字符5// 五字符4// 六字符3// 七字符2// 八字符1//空串1分别是： // *// *j// *jk// *jkj// *jkj1// *jkj12// *jkj12k// *jkj12k0// j// jk// jkj// jkj1// jkj12// jkj12k// jkj12k0// k// kj// kj1// kj12// kj12k// kj12k0// j1// j12// j12k// j12k0// 1// 12// 12k// 12k0// 2// 2k// 2k0// k0// 0// 空串
-
真子串（不包含自身的子串）。
-
主串：包含子串的串，称之为 主串。
-
字符位置：字符在数组中的位置。
-
子串位置：子串第一个字符串 在 主串中的位置。
-
空格串：一个空格或者多个空格组成的串，称之为空格串。
-
空串：零个没有任意字符的串，称之为空串。
" "// 空格串""// 空串
-
串相等：当两个串长度相等，并且每个位置对应字符完全一样的时候，两个串才相等。
串的基本操作
1. 赋值StrAssign(s,t) 将串t的值赋值给串s2. 求串长 StrLength(s) 返回字符串s的长度3. 串比较 StrCompare(s,t) 比较两个串，返回-1、0和1，分别代表st4. 连接 Concat(s,t) 将串t连接在串s的尾部，形成新的字符串5. 求子串 SubString(s,start,len) 返回串s从start开始、长度为len的字符序列6. 串拷贝 StrCopy(t,s) 将串s拷贝到串t上7. 串判空 StrEmpty(s) 判断串s是否为空串8. 清空串ClearString(s) 清空字符串s9. 子串位置 Index(S,T,pos) 字符串S中返回T所出现的位置10. 串替换 Replace(S,T) 串S替换为T
-
串的顺序存储
-
结构体
typedef struct SString{ char ch[MAX +1];// 字符数组空间，MAX 为宏定义值 int length;// 串的长度}; -
BF算法
// str 是主串subStr 是模式匹配串int BF(char str[], char subStr[]){ int i=0,j=0;//定义 i 主串下表，j 模式串下标 while( i //如果对应位置相等，则下标后移，比较下一位元素 if(str[i] == subStr[j]){ i++; j++; } else{ i = i-j+1;//主串下标进行回溯 j = 0;//子串下标回溯 } } if( j == strlen(subStr) ){//子串下标 与 子串长度相等 //返回子串位置 return i - strlen(subStr) + 1; } return -1;//未找到子串下标 }hr / h3矩阵/h3 ulli p把矩阵当作 二维数组，只不过下标都是从 1 开始。/p /lili p二维数组 以行为主序存储，二维数组 以列为主序存储。/p pre 以行存储，先去计算前 (i-1)行有多少元素以列存储，先去计算前 (j-1)列有多少元素/pre blockquote p前提：数组下标从一开始。/p /blockquote /lili p对称矩阵：以主对角线为对称轴，个元素对应相等的矩阵。/p /lili p对角矩阵：除主对角线意外，全是 0 的矩阵。/p /lili p稀疏矩阵：非零元素个数，远远少于 零元素个数，且零元素分布无规律。/p /lili p三元组 (行,列,值) ：/p pre (4,5,8)//第四行，第五列，值为8(前提：行列下标都从1开始)(4,5,8)//第三行，第四行，值为8(前提：行列下标都从0开始)/pre hr / h3树/h3 ulli树 是 非线性结构 。/lili根节点：没有 父节点 的节点 。/lili叶子节点：没有 子节点 的节点 。/lili节点的层次：树一共有几层，节点的层次就是几 。/lili节点的祖先：从 根节点 到 该节点 的 所有节点 。/lili节点的度：该节点 有几个 直接后继，就是几度。/lili树的度：树中，最大的 节点度 就称之为 树的度。/lili树的深度/高度：从 根节点 开始，长度最长的一条路径 有几个节点，深度就是几。hr / ulli p树的性质/p pre 1、树中的节点数 等于 所有节点的度数加1。2、度为 M 的树中，第i层上至多有 M的(i-1) 次方个节点(i=1)。3、高度为 H 的 M 叉树中，之多有 (M的H次方)/(M-1) 个节点。// 二叉树 需要 再减去1：(M的H次方)/(M-1)-1/pre /lili p二叉树：有0个 到 2个节点的树，称为 二叉树。/p /lili p二叉树的性质/p ulli性质一：在二叉树中，在第 i 层上最多有 font color="red"2supi-1/sup /font 个节点 (i>0)。 - 性质二：深度为 k 的二叉树，最多有 2k-1 个节点 (k>0)。
- 性质三：树上的节点数为 n ，则边数一定为 n-1 。
- 性质四：任意一棵二叉树中，度为 0 的节点个数 = 度为 2 的节点个数 + 1。
- 性质五：具有 n 个节点的 完全二叉树 的深度为 ⌊ log 2 n ⌋ + 1 (向下取整)。
-
大顶堆，小顶堆
// 大顶堆 每个根节点(所有的根节点) 都大于 它的子结点ki >= k2ik2 >= k2i +1// 小顶堆 每个根节点(所有的根节点) 都小于 它的子结点ki char ch;// 数据域 struct TreeNode *lchild;//左孩子 指针 struct TreeNode *rchild;//右孩子 指针 }TreeNode; //递归结束条件，也就是说当一个节点 某个指针域为 NULL if(!root){ return; } printf("%c ",root-ch); //递归调用左子树 preOrder(root-lchild); //递归调用右子树 preOrder(root->rchild); } -
中序遍历
void inOrder(Node *root){ //递归结束条件，也就是说当一个节点 某个指针域为 NULL if(!root){ return; } //递归调用左子树 preOrder(root->lchild); printf("%c ",root->ch); //递归调用右子树 preOrder(root->rchild); } -
后序遍历
void lastOrder(Node *root){ //递归结束条件，也就是说当一个节点 某个指针域为 NULL if(!root){ return; } //递归调用左子树 preOrder(root->lchild); //递归调用右子树 preOrder(root->rchild); printf("%c ",root->ch); }-
根据遍历的序列 确定 二叉树 的形状
// 1、先序 和 中序 可以确定一棵二叉树答：根据先序 确定 根节点的位置，然后去 中序 找到该节点，该节点左边元素都是左子树，右边元素都是右子树；依次重复上述过程，即可根据序列确定 二叉树形状。(从前找根节点)// 2、后序 和 中序 可以确定一棵二叉树 答：根据先序确定 根节点的位置，然很去中序中找到该节点左边元素都是左子树，右边元素都是右子树，一次重复上述过程，即可根据序列确定 二叉树形状。(从后找根节点)// 3、先序 和 后序 不可以确定一棵二叉树
-
非递归中序遍历
void inOrder(Node * root){ //指针p 指向 根节点，并按照某种顺序游走于每一个结点 Node *p = root; //建立栈，用来实现 递归 LinkStack s = init_LinkStack(); //初始化栈，初始化一个头结点出来 //p 不指向 NULL 并且 栈不空的时候 while(p || ! isEmpty_LinkStack(s)){ //根节点不空，进栈,让其指向左子树 if(p){ push_LinkStack(s , p); p = p->lchild; //指向左子树 }else{ //定义一个指针 指向 栈顶元素 （就是 子树的根节点） Node *top = top_LinkStack(s); //元素出栈 pop_LinkStack(s); printf("%c ",top->data); p = top->rchild; } } //销毁栈 destory_LinkStack(s);} -
如果有 n 个节点，则有 n+1 个空指针域。
-
线索：指向其 前驱 和 后继 的指针。
-
孩子兄弟表示法：左边指针是孩子，右边指针是兄弟。
二叉排序树
- 概念：是一颗空树，或者是满足以下性质的二叉树
- 左子树非空，左边节点 小于 根节点。
- 右子树非空，右边节点 大于 根节点。
- 中序遍历，可以实现二叉排序树 从小到大排序。
// 定义节点 结构体typedef struct TreeNode{ int data;//数据域 struct TreeNode *lchild;//左指针(指向左孩子) struct TreeNode *rchild;//右指针(指向右孩子) }TreeNode;TreeNode* searchTreeNode( TreeNode *root, int key ){ //递归结束条件， root 为 NULL 相当于 没有找到节点 if( (!root) || (key == root->data) ){ return root; } else if( key data )// 递归左子树查找 { retuen searchTreeNode(root->lchild, key); } else//递归右子树查找 { retuen searchTreeNode(root->rchile, key); } }哈夫曼树（最小权值树）
-
路径：两个节点之间的 线 就是 路径。
-
节点的路径：从 根节点 到 该节点，有几根线，路径长度就是几。
-
树的路径长度：所有结点的路径长度之和，称之为树的路径长度。
-
权值：给这个节点 赋一个数值，这个数值就是 权值。
-
节点的带权路径长度：路径长度 * 该节点的权值。
-
树的带权路径长度（WPL）：所有 叶子节点 的带权路径长度 之和。
-
重点：哈夫曼树构造
//哈夫曼二叉树构造1、每次从 序列中找出 权值最小的两个节点（一般：从左至右，从小到大）2、生成一个新的节点，将这个节点放入 序列中，删除刚才的两个最小权值节点，再重复此过程。
邻接矩阵
- 无向图 对应的临界矩阵 是 对称矩阵。
- 矩阵的大小 只与 顶点个数有关，是一个 N*N阶矩阵。
- 顶点的度：
- 入度：邻接矩阵 对应于 列上值的总和。
- 出度：邻接矩阵 对应于 行上值的总和。
邻接表
-
防止浪费空间（稀疏矩阵），但是效率 相对于 邻接矩阵 较低。
-
邻接表：顶点用 一维数组存储，后面跟着 单链表 存储邻接点。
-
邻接表 中 邻接点的个数 和 图中这个顶点 的出度有关。
带权图
- 边 给一个值，称之为 边权，对应图 称之为 带权图，也称之为 网。
深度优先遍历 DFS
- 不撞南墙不回头（遍历不唯一）。
广度优先遍历算法
- 相当于我们的二叉树层次遍历（用到队列，先进先出）。
- 记得保持顺序。
G = (V,E) ：G指的图 V指的顶点 E指的边。
- 强连通图：任意顶点都能到达其他顶点，称之为：强连通图。
最小生成树
-
生成树：顶点由边连接在一起，不存回路的图。
-
生成树顶点个数 和 图顶点个数相同。
-
生成树（极小连通图） 去掉一条边，则变成非连通图。
-
连通图有 n 个顶点，则其 生成树 有 n-1条边。
-
生成树 再加一条边，必然形成回路。
含有 n 个顶点 n-1 条边的图，不一定是 生成树。
-
无向图的生成树
- 深度优先生成树
- 广度优先生成树
-
最小生成树：边权值之和最小的树。
普利姆算法（Prim）
- 普利姆算法 和 点 有关。
- 每次去找和点连接的最小权值的边（包括之前的点）。
克鲁斯卡尔算法（Kruskal）
-
克鲁斯卡尔 和 边 有关。
-
每次去找 边权值 最小的边，两个顶相连，依次构成最小生成树。
最短路径
迪杰斯特拉（Dijkstra）
- 两点间最短路径。
弗洛伊德（Floyd）
- 所有顶点间的最短路径。
- 两个矩阵，一个存储 权值，一个存储 路径。
- 把所有的顶点依次加入矩阵中，找最小权值路径。
拓扑排序
AOV网
- 顶点 表示 活动。
- 弧 表示活动之间的有限制约关系。
- 拓扑排序：前提 有向无环图。
- 拓扑排序：找 入度为0(无前驱) 的结点 删除，循环上述过程即可。
- 逆拓扑排序：找 出度为0(无后继) 的结点 删除，循环上述过程即可。
- 判断 AOV网 中是否有环。
- 两点间最短路径。
-
-
-
- 强连通图：任意顶点都能到达其他顶点，称之为：强连通图。
- 不撞南墙不回头（遍历不唯一）。
- 边 给一个值，称之为 边权，对应图 称之为 带权图，也称之为 网。
-
-
- 概念：是一颗空树，或者是满足以下性质的二叉树
-
-
-
-
- 前 中 后 缀表达式 如何计算？
-
-
-
-
-
-
-
-
-
-
-
-
- AOV网
上一篇：dell服务器盖怎么拆?
下一篇：怎么打开小米的云服务器?
