数据结构与算法 数据结构与算法主要记录了简单数据结构与算法。
摘要: 在一个由n个元素组成的集合中，第i个顺序统计量是该集合中第i小的元素。一个中位数是它所属集合的“中点元素”。当n为奇数时，中位数是唯一的，位于i=(n+1)/2处；当n为偶数时，存在两个中位数，分别位于i=n/2和i=n/2+1处。如果不考虑n的奇偶性，中位数总是出现在i=⌊(n+1)/2⌋处（下中...阅读全文
摘要: 动态规划通常用于解决最优化问题，在这类问题中，通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原问题形式相同的子问题。当多于一个选择子集都生成相同的子问题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。钢条切割问题Serli...阅读全文
摘要: 堆排序的时间复杂度是，具有空间原址性，即任何时候都只需要常数个额外的元素空间存储临时数据。一、堆二叉堆是一个数组，可看成一个近似的完全二叉树，树上的每个结点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左到右填充。二叉堆可以分为两种形式：最大堆和最小堆。在最大堆中除根节点外所有结点i...阅读全文
摘要: 动态规划（dynamic programming）是通过组合子问题的解而解决整个问题的。分治算法是指将问题划分为一些独立的子问题，递归地求解各子问题，然后合并子问题的解而得到原问题的解。动态规划适用于子问题不是独立的情况，也就是各子问题包含公共的子子问题。在这种情况下，若用分治法则会做许多不必要...阅读全文
摘要: 一、快速排序的描述快速排序是基于分治策略的。对一个子数组A[p…r]快速排序的分治过程的三个步骤为：1、分解数组A[p…r]被划分成两个（可能空）子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每个元素都小于等于A[q]，且小于等于A[q+1…r]中的元素。下标q也在这个划分过程中...阅读全文
摘要: 一、哈弗曼树的基本概念。哈夫曼树，又称最优树，是一类带权路径长度最短的树。下面有几个概念：（1）路径。树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。（2）路径长度。路径上的分枝数目。（3）树的路径长度。从树根到每一个结点的路径长度之和。（4）结点的带权路径长度。从该结点到树根之间的路径...阅读全文
摘要: C语言非递归实现二叉树的先序、中序、后序、层序遍历代码如下： 1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 7 //*****二叉树的二叉链表存储表示*****// ...阅读全文
摘要: 思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。说明：（1）子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止。由于这个原因...阅读全文
摘要: 寻找数组A的和最大的非空连续子数组。例如：int A[] = {1, -2, 3, 10, -4, 7, 2, -5}的最大子数组为3, 10, -4, 7, 2，其最大和为18。方法1：枚举所有子数组并求出他们的和。长度为n的数组有O(n2)个子数组（即：n + n-1 + ... + 1=n(n...阅读全文
摘要: 1 #include 2 #include 3 //*****二叉树的二叉链表存储表示*****// 4 typedef struct BiNode 5 { 6 char data; 7 struct BiNode *lchild...阅读全文