目录
逻辑结构
存储结构
算法有以下五个特性
算法+数据结构 = 程序
时间复杂度
空间复杂度
数据元素是数据的基本单位
数据项是数据的最小单位
数据结构是带有结构的各数据元素的集合
时间复杂度例题
线性表
关于带头节点的单链表及不带头节点的单链表
栈和队列
栈和队列的定义和特点
栈
队列
二叉树：先序，中序，后序
哈夫曼树
构造
编程
普里姆算法
归并排序
直插排序
逻辑结构
集合结构，线性结构，树形结构，图形结构
存储结构
顺序结构（地址连续）
链式结构（任意存储单元）（可连续，可不连续）
算法有以下五个特性
-
有穷性
-
确定性
-
可行性
-
输入
-
输出
算法+数据结构 = 程序
时间复杂度
x++
时间复杂度：O(1)
for(i=1;i<=n;i++){
x++;
}
时间复杂度：O(n)
for(i=1;i<=n;i++){
for(j=1;j<=n;i++){
x++;
}
}
时间复杂度：O(n^2)
空间复杂度
int i = 1;
int j = 2;
++i;
j++;
int m = i+j
空间复杂度：O(1)
int m[] = new int[n];
for(i=1;i<=n;i++){
j=i;
j+1;
}
空间复杂度O(n)
数据元素是数据的基本单位
数据项是数据的最小单位
数据结构是带有结构的各数据元素的集合
时间复杂度例题
i < 1;
whiel(i<=n){
i = i * 3;
}
时间复杂度O(log3n)
解释：设i = i * 3 执行了x次，则 3^x = n;故x=log3n
x = 0
for(i=1;i<n;i++){
for(j=1;j<=n-1;j++){
x++
}
}
时间复杂度O(n^2)
x = n;
y = 0;
while(x >= (y+1)*(y+1)){
y++;
}
时间复杂度O(更号n)
线性表
关于带头节点的单链表及不带头节点的单链表
-
首元结点： 是指链表中存储第一个数据元素的结点。
-
头结点： 是在首元素结点之间附设的一个结点，其指针指向首元结点。
-
头指针： 是指链表中第一个结点的指针。若链表没有头节点，则头节点指针为线性表的头结点；若链表不设头节点，则头指针所指的结点为该线性表的首元结点。
栈和队列
栈和队列的定义和特点
栈
-
栈：受约束的线性表，只允许栈顶元素入栈和出栈
-
对栈来说，表尾端称为栈顶，表头端称为栈底，不含元素的空表称为空栈
-
先进后出，后进先出
队列
-
队列：收约束的线性表，只允许在队尾插入，在队头删除
-
先进先出，后进后出
二叉树：先序，中序，后序
先序：根，左，右
中序：左，根，右
后序：左，右，根
哈夫曼树
哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。它常用于数据压缩，通过构建一个树形结构来表示一系列元素的频率，频繁出现的元素用较短的编码表示，不频繁出现的元素用较长的编码表示。下面是哈夫曼树的构造过程以及一个简单的编程实现思路。
构造
-
统计每个字符的频率：首先，统计需要编码的所有字符出现的次数。
-
创建节点集合：为每个字符创建一个叶子节点，节点的权值为该字符的频率。
-
构建哈夫曼树：
-
将所有叶子节点加入一个最小堆（优先队列），按照节点的权值进行排序。
-
取出权值最小的两个节点。
-
创建一个新的内部节点，其权值为这两个节点权值之和，新节点的左右子节点分别是这两个权值最小的节点。
-
将新节点加入到最小堆中。
-
重复上述过程，直到堆中只剩下一个节点，这个节点就是哈夫曼树的根节点。
-
编程
import java.util.*;
class HuffmanNode implements Comparable<HuffmanNode> {
int frequency; // 频率
char data;
HuffmanNode left, right;
HuffmanNode(int freq, char data) {
this.frequency = freq;
this.data = data;
left = right = null;
}
// 重写compareTo方法，用于优先队列的排序
public int compareTo(HuffmanNode node) {
return this.frequency - node.frequency;
}
}
public class HuffmanCoding {
// 构建哈夫曼树
static HuffmanNode buildHuffmanTree(Map<Character, Integer> freqMap) {
PriorityQueue<HuffmanNode> pq = new PriorityQueue<>();
// 将每个字符及其频率添加到优先队列中
for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {
pq.add(new HuffmanNode(entry.getValue(), entry.getKey()));
}
// 合并节点直到只剩下一个节点（即哈夫曼树的根）
while (pq.size() != 1) {
HuffmanNode left = pq.poll();
HuffmanNode right = pq.poll();
HuffmanNode newNode = new HuffmanNode(left.frequency + right.frequency, '\0');
newNode.left = left;
newNode.right = right;
pq.add(newNode);
}
return pq.peek(); // 返回哈夫曼树的根节点
}
// 生成哈夫曼编码（这里简化处理，未实现编码的具体生成逻辑）
static void printCodes(HuffmanNode root, String str) {
if (root == null)
return;
// 如果是叶子节点，则输出字符和编码
if (root.data != '\0') {
System.out.println(root.data + ": " + str);
return;
}
// 非叶节点，递归生成左子树和右子树的编码
printCodes(root.left, str + "0");
printCodes(root.right, str + "1");
}
public static void main(String[] args) {
Map<Character, Integer> freq = new HashMap<>();
freq.put('A', 5);
freq.put('B', 9);
freq.put('C', 12);
freq.put('D', 13);
freq.put('E', 16);
freq.put('F', 45);
HuffmanNode root = buildHuffmanTree(freq);
System.out.println("哈夫曼编码：");
printCodes(root, "");
}
}
普里姆算法
普里姆算法是一种用于寻找加权图的最小生成树的算法。下面是一个使用Java实现的普里姆算法的例子。在这个例子中，我们假设图是以邻接矩阵的形式存储的，其中INF表示两个顶点之间没有边。
import java.util.Arrays;
public class PrimAlgorithm {
final int V = 5; // 图的顶点数
final int INF = Integer.MAX_VALUE; // 代表无穷大
// 用来存储图的邻接矩阵
int[][] graph = new int[][]{
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};
// 用于选择顶点的数组，如果selected[i]为true，则顶点i已包含在最小生成树中
boolean[] selected = new boolean[V];
// 用于存储最小生成树的边的权重
int[] edgeWeight = new int[V];
// 用于存储最小生成树中各顶点的父顶点
int[] parent = new int[V];
// 普里姆算法的主要实现
void prim() {
Arrays.fill(edgeWeight, INF);
Arrays.fill(parent, -1);
edgeWeight[0] = 0;
parent[0] = -1; // 第一个顶点是没有父顶点的
for (int i = 0; i < V; i++) {
int u = minVertex();
selected[u] = true;
for (int v = 0; v < V; v++) {
if (!selected[v] && graph[u][v] != 0 && graph[u][v] < edgeWeight[v]) {
parent[v] = u;
edgeWeight[v] = graph[u][v];
}
}
}
}
// 找出未被选中的顶点中edgeWeight值最小的顶点
int minVertex() {
int min = INF;
int minIndex = -1;
for (int v = 0; v < V; v++) {
if (!selected[v] && edgeWeight[v] <= min) {
min = edgeWeight[v];
minIndex = v;
}
}
return minIndex;
}
// 打印最小生成树的边和权重
void printMST() {
System.out.println("边 \t 权重");
for (int i = 1; i < V; i++) {
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
}
public static void main(String[] args) {
PrimAlgorithm prim = new PrimAlgorithm();
prim.prim();
prim.printMST();
}
}
在这个程序中，prim()方法执行普里姆算法，找出图的最小生成树；minVertex()方法找到当前尚未包含在最小生成树中，且具有最小权重的顶点；printMST()方法用于打印最小生成树的边和对应的权重。
归并排序
public class SimpleMergeSort {
public static void mergeSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
mergeSort(array, 0, array.length - 1);
}
private static void mergeSort(int[] array, int start, int end) {
if (start < end) {
int mid = start + (end - start) / 2;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
}
private static void merge(int[] array, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int left = start, right = mid + 1, index = 0;
while (left <= mid && right <= end) {
if (array[left] <= array[right]) {
temp[index++] = array[left++];
} else {
temp[index++] = array[right++];
}
}
while (left <= mid) {
temp[index++] = array[left++];
}
while (right <= end) {
temp[index++] = array[right++];
}
for (int i = 0; i < temp.length; i++) {
array[start + i] = temp[i];
}
}
public static void main(String[] args) {
int[] testArray = {9, 5, 1, 4, 3};
mergeSort(testArray);
for (int i : testArray) {
System.out.print(i + " ");
}
}
}
直插排序
在这个实现中，insertionSort方法遍历数组中的每一个元素（从第二个元素开始，因为单个元素默认是有序的）。对于每一个元素，它会与前面已经排序好的部分进行比较，找到适当的位置并将其插入。这样逐步构建整个有序数组。
main方法提供了一个测试数组，并调用insertionSort方法对其进行排序，最后打印排序后的数组，以验证排序算法的正确性。
public class InsertionSort {
public static void insertionSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
for (int i = 1; i < array.length; i++) {
int current = array[i];
int j = i - 1;
while (j >= 0 && array[j] > current) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = current;
}
}
public static void main(String[] args) {
int[] testArray = {9, 5, 1, 4, 3};
insertionSort(testArray);
for (int value : testArray) {
System.out.print(value + " ");
}
}
}
