目录
逻辑结构
存储结构
算法有以下五个特性
算法+数据结构 = 程序
时间复杂度
空间复杂度
数据元素是数据的基本单位
数据项是数据的最小单位
数据结构是带有结构的各数据元素的集合
时间复杂度例题
线性表
关于带头节点的单链表及不带头节点的单链表
栈和队列
栈和队列的定义和特点
栈
队列
二叉树:先序,中序,后序
哈夫曼树
构造
编程
普里姆算法
归并排序
直插排序
逻辑结构
集合结构,线性结构,树形结构,图形结构
存储结构
顺序结构(地址连续)
链式结构(任意存储单元)(可连续,可不连续)
算法有以下五个特性
-
有穷性
-
确定性
-
可行性
-
输入
-
输出
算法+数据结构 = 程序
时间复杂度
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 + " "); } } }