代码汇总【数据结构与算法】【精致版】
学习
第一章 引言
第二章 线性表
顺序表
1-顺序表.h
1-顺序表的测试.c
//1.顺序表的初始化 //【算法2-1】 顺序表的初始化 //创建顺序表函数 初始化前n个数据 //2.顺序表的插入 //【算法2-2】顺序表的插入 //3.顺序表的删除 //【算法2-3】 顺序表的删除 //4.顺序表中的按值查找 //【算法2-4】顺序表中的按值查找 //5.另外 //按序号查询 ,结果返回由x实现
[例 2-1] 两个顺序表合并
2-5顺序表的合并.c
// [例 2-1] 两个顺序表合并 //【算法2-5】两个顺序表的合并
单链表
2-单链表.h
2-单链表的测试.c
//1.建立单链表 //【算法2-6】头插法建立单链表 //【算法2-7】尾插法建立单链表 //2.求表长 //【算法2-8】 求单链表的表长 //3.查找操作 //(1) 按序号查找 Get(H,k) //【算法2-9】单链中按序号查找 //(2) 按值x查找 //【算法2-10】单链中按值查找 //4.插入操作 //【算法2-11】单链表的插入 //在单链表H的第i个位置上插入值为x的元素 //5.删除操作 //【算法2-12】 单链表的删除
[例2-2]单链表的逆置
2-13单链表的逆置.c
// [例2-2]单链表的逆置 //【算法2-13】 单链表的逆置
[例2-3]单链表中删除重复结点
2-14单链表中删除重复结点.c
// [例2-3]单链表中删除重复结点 //【算法2-14】单链表中删除重复结点
[例2-4]两个集合的差集
2-15两个集合的差集.c
// [例2-4]两个集合的差集 // 【算法2-15】两个集合的差集
[例] 两个单链表的合并
两个单链表的合并.c
循环链表
3-循环链表.c
双向链表
4-双向链表.c
静态链表
5-静态链表.c
第三章 栈和队列
顺序栈
1-顺序栈.h
1-顺序栈测试.c
共享栈
2-共享栈.c
链栈
3-链栈.h
3-链栈.c
多个链栈
4-多个链栈.c
5-括号匹配.c
循环队列
6-循环队列.c
链队列
7-链队列.c
第四章 串
定长顺序串
1-定长顺序串.c
//(1)串插入函数 //【算法4-2】串插入函数 //(2)串删除函数 //【算法4-3】 串删除函数 //(3)串连接函数 //【算法4-4】 串连接函数 //(4)求子串函数 //【算法4-5】 求子串函数
堆串
2-堆串.c
//(1)串初始化函数 //【算法4-6】串初始化函数 //(2)串赋值函数 //【算法4-7】串赋值函数 //(3)串插入函数 //【算法4-8】 串插入函数 //(4)串删除函数 //【算法4-9】 串删除函数 //(5)串连接函数 //【算法4-10】 串连接函数 //(6)求子串函数 //【算法4-11】求子串函数
4-12BF模式匹配算法.c
//【算法4-12】BF模式匹配算法
4-13KMP模式匹配算法
//【算法4-13】KMP模式匹配算法 //【算法4-14】next算法 //【算法4-15】 nextval算法
块链串
3-块链串.c
第五章 多维数组和广义表
第六章 树
二叉树
1-二叉树的递归实现.c
//【算法6-1】递归 先序 //【算法6-2】递归 中序 //【算法6-3】递归 后序
2-二叉树的非递归实现.c
//【算法6-4】非递归 先序 //【算法6-5】非递归 中序-1 //【算法6-6】非递归 中序-2 //【算法6-7】非递归 后序 //【算法6-8】二叉树的层次遍历
3-二叉树的遍历算法应用.c
// 【算法6-9】先序遍历统计二叉树的结点数 // 【算法6-10】中序遍历输出二叉树的叶子结点 // 【算法6-11】后序遍历输出二叉树的叶子结点数目 //【算法6-12】全局变量法求二叉树的高度 //【算法6-13】求二叉树的高度 //【算法6-14】求二叉树中某一结点的双亲 //【算法6-15】二叉树相似性判定 //【算法6-16】按树状打印二叉树
第七章 图
1-邻接矩阵.c
//【算法7.1】用邻接矩阵创建无向网
2-邻接矩阵plus.c
3-邻接表.c
4-邻接表plus.c
5-DFSAdjMatrix.c
6-DFSAdjList.c
//【算法 7-2】递归深度优先搜索遍历连通子图 //【算法 7-3】深度优先遍历图g //【算法 7-4】非递归深度优先搜索遍历连通子图
7-BFSAdjMatrix.c
8-BFSAdjList.c
//【算法7-5】广度优先搜索遍历连通子图 //【算法7-6】广度优先遍历图g
9-Prim.c
//【算法7-7】Prim算法求得最小生成树
10-拓扑排序.c
//【算法7-8】获取图中每个顶点入度值 //【算法7-9】 拓扑排序
11-单源最短路径.c
//【算法7-11】采用Dijkstra算法求得从源点到其余各顶点的最短路径
12-多源最短路径.c
//【算法7-12】Floyd算法求得任意两顶点之间的最短路径
第八章 查找
1-顺序查找.c
//【算法8-1】顺序查找 //【算法8-2】加“监视哨”的顺序查找
2-折半查找.c
//【算法 8-3】折半查找的非递归实现
3-二叉排序树.c
//【算法8-4】基于二叉排序树查找的非递归实现 //【算法8-5】 基于二叉排序树查找的递归实现 //【算法8-6】二叉排序树的插入 //【算法8-7】 二叉排序树的建立 //【算法8-8】 二叉排序树的删除
4-哈希表查找.c
// 【算法8-10】采用除留余数法构造哈希函数 //【算法8-11】采用线性探测再散列处理冲突 //【算法8-12】哈希表的查找 //【算法8-13】 哈希表的插入 //【算法8-14】哈希表的创建 //【算法8-15】 哈希表的删除
第九章 排序
插入类排序
1-直接插入排序.c
// 【算法9-1】直接插入排序 // 【算法9-2】改进的直接插入排序
2-折半插入排序.c
//【算法9-3】折半插入排序
3-希尔排序.c
//【算法9-4】希尔排序
交换类排序
4-冒泡排序.c
//【算法9-5】冒泡排序 //【算法9-6】改进冒泡排序
5-快速排序.c
//【算法9-7】一趟快速排序 //【算法9-8】快速排序
选择类排序
6-简单选择排序.c
//【算法9-9】简单选择排序
7-堆排序.c
//【算法9-10】堆的筛选 //【算法9-11】建立初始堆 //【算法9-12】堆排序
归并类排序
8- 二路归并排序.c
//【算法9-13】二路归并排序 //【算法9-14】二路归并排序
9-自然归并排序.c
//【算法9-15】自然归并排序
分配类排序
10-多关键字排序.c
11-链式基数排序.c
//【算法9-16】基于链队列的基数排序 //【算法9-17】提取关键字中第m位的数字值
习题
第一章 习题
9.1 在数组A[1…n]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志
9.2 找出数组A[1…n]中元素的最大值和次最大值
第二章 习题
(1) 设有一线性表e=(e1,e2,…,e[n-1],en,其逆线性表定义为e’=(en,e[n-1],…,e2,e1)。请设计一个算法,将线性逆置,要求逆线性表仍占用原线性表的空间,并且用顺序表和单链表两种方法来表示,写出不同的处理函数。
(3) 已知线性表A的长度为n,并且采用顺序存储结构。请编写算法，删除线性表中所有值为x的元素。
(5) 假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某结点的指针，试编写算法,在链表中删除指针s所指结点的前驱结点。
(8)设指针la和lb分别指向两个无头结点单链表中的首元结点,试设计算法,从表la中删除自第i个元素起共len个元素,并将它们插入表lb的第j个元素之后。
(9)设带头结点的线性单链表A=(a1,a2,…,am),B=(b1,b2,…bn)。试编写算法按下列规则合并A、B为线性单链表C,使得
C=(a1,b1,…,am,bm,b_(m+1),…,bn),m<=n
或者
C=(b1,a1,…,bn,an,a_(n+1),…,am),m>n
第三章 习题
(2) 回文是指正读反读均相同的字符序列,如“abba”和“abdba"均是回文,但“good"不是回文。试写一个算法判定给定的字符串是否为回文。
(6) 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的置空队、判队空、入队和出队算法。
(8) 在循环队列中,可以设置一个标志域tag,以区分当尾指针和头指针相等时,队列状态是“空”还是“满”（tag的值为0表示“空”,tag的值为1表示“满”),编写此结构相应的队列初始化、入队、出队算法。
第六章 习题
（1）编写算法,在以二叉链表存储的二叉树中,求度为2的结点的个数。
（2）编写算法,在以二叉链表存储的二叉树中,交换二叉树各结点的左右子树。
实验
二
约瑟夫环
约瑟夫环.c
//【算法2-16】约瑟夫环
一元多项式运算器
多项式.c
//【算法2-17】建立多项式 //【算法2-18】输出多项式 //【算法2-19】两个多项式相加 //【算法2-20】两个多项式相减
