Java双向链表通讯录与24点求解器实战

Java双向链表通讯录与24点求解器实战

发布时间：2026/9/26 1:11:34
Java双向链表通讯录与24点求解器实战 简介本资源是面向高校计算机专业本科生的数据结构课程设计实践项目聚焦Java语言实现与核心数据结构应用通过手机通讯录模拟和24点扑克牌游戏两大典型场景系统训练链表、哈希表、递归、回溯、排序等关键知识点的工程化落地能力。压缩包共73个文件含53张界面与流程图PNG用于功能演示与设计说明、5个核心Java源码文件含通讯录增删查改及24点DFS求解逻辑、5个编译后class文件、8个XML配置与IDE配置文件以及HTML项目说明文档整体体积仅431KB轻量易部署。已有648人学习下载资源结构清晰src目录下分version_1/2/3多版迭代代码配合详尽截图与模块化注释便于理解设计演进过程、调试关键算法如24点全排列四则组合回溯及掌握生产级通讯录系统的数据组织方式。1. 两个经典数据结构实战用 Java 实现通讯录增删查改 24 点扑克牌穷举求解不是玩具代码是能跑通、能调试、能交作业的完整课程设计包你手头那份《数据结构》教材里链表、栈、队列、二叉树讲得再透不亲手把“手机通讯录”塞进链表、不把“24点”拆成后缀表达式栈运算就永远卡在“看懂了但写不出”的玄学阶段。这个课程设计包不是 Demo它包含两个独立可运行的 Java 工程一个是基于双向链表实现的模拟手机通讯录支持按姓名/号码模糊搜索、按拼音排序、批量导入导出 TXT另一个是用回溯栈哈希去重实现的 24 点游戏求解器输入四张牌输出所有合法算式组合含括号优先级处理。所有代码无第三方依赖JDK 8 直接javac java运行每个模块都带单元测试断言比如通讯录插入 5 条后 size() 524 点对 [3,3,8,8] 输出 2 个唯一解配套 PDF 文档含 UML 类图、核心算法流程图、时间复杂度分析通讯录搜索 O(n)24 点穷举 O(1) 因为固定 4 张牌但实际剪枝后约 7680 种排列组合。适合计算机/软件工程专业本科生做课程设计、实验报告或期末复习抓手——它不教你“什么是链表”它逼你写出“链表怎么让通讯录支持快速删除中间联系人”。2. 手机通讯录系统双向链表 拼音排序 文件持久化从零构建可交互的 CLI 应用2.1 为什么选双向链表而不是 ArrayList三个硬性约束倒逼结构选型通讯录最频繁的操作是按姓名插入新联系人需保持有序、删除任意位置联系人、按拼音首字母跳转浏览。ArrayList 插入/删除中间元素要移动大量数据O(n) 时间不可接受HashMap 虽快但无法维持顺序且不支持“下一个联系人”这种遍历语义。双向链表完美匹配插入时通过findInsertPosition()定位插入点prev.next newNode; newNode.prev prev; newNode.next next; next.prev newNode四步完成 O(1) 链接删除时直接prev.next next; next.prev prev;断开连接无需移动其他节点遍历时current current.next或current current.prev支持双向滚动适配手机键盘“上/下键”逻辑。提示本设计中ContactNode类同时持有nameString、phoneString、pinyinFirstchar预计算存入字段避免每次搜索都调用PinyinUtil.toPinyin()这是性能关键点。2.2 核心类 ContactList 的完整实现与关键方法解析public class ContactList { private ContactNode head; // 哨兵头节点head.next 为第一个真实联系人 private ContactNode tail; // 哨兵尾节点tail.prev 为最后一个真实联系人 private int size; public ContactList() { this.head new ContactNode(null, null); // 哨兵节点不存数据 this.tail new ContactNode(null, null); this.head.next this.tail; this.tail.prev this.head; this.size 0; } // 按姓名插入保持升序使用拼音首字母比较 public void insert(Contact contact) { ContactNode newNode new ContactNode(contact); ContactNode prev findInsertPosition(newNode); // 返回应插入位置的前驱节点 ContactNode next prev.next; // 四步链接 prev.next newNode; newNode.prev prev; newNode.next next; next.prev newNode; size; } private ContactNode findInsertPosition(ContactNode newNode) { ContactNode current head.next; while (current ! tail compareByPinyin(current.contact.getName(), newNode.contact.getName()) 0) { current current.next; } return current.prev; // 返回插入点前驱 } private int compareByPinyin(String a, String b) { char aFirst getFirstPinyinChar(a); char bFirst getFirstPinyinChar(b); if (aFirst ! bFirst) return Character.compare(aFirst, bFirst); return a.compareTo(b); // 首字母相同时按完整姓名字典序 } private char getFirstPinyinChar(String name) { // 使用 pinyin4j 库已打包进 lib/此处简化为调用工具类 return PinyinUtil.getFirstChar(name); } }参数说明与逻辑要点head和tail是哨兵节点sentinel node极大简化边界判断无需判空、无需特殊处理头尾插入findInsertPosition()返回的是前驱节点而非插入位置本身这是双向链表插入的标准写法避免current.prev为空指针compareByPinyin()先比拼音首字母相同再比全名确保“张三”和“张四”不会因首字母相同而乱序size字段手动维护避免遍历计数O(1) 获取长度。2.3 文件导入导出TXT 格式规范与异常安全写法通讯录必须落盘否则重启就丢数据。本设计采用纯文本格式每行一条联系人字段用|分隔张三|13800138000|2023-05-01 李四|13900139000|2023-06-15导入时严格校验手机号格式11位数字导出时自动补全缺失字段如无生日则填null// 导入方法带异常捕获与部分失败容忍 public void importFromTxt(String filename) throws IOException { try (BufferedReader reader new BufferedReader(new FileReader(filename))) { String line; int successCount 0; while ((line reader.readLine()) ! null) { line line.trim(); if (line.isEmpty()) continue; try { String[] parts line.split(\\|, -1); // -1 保留末尾空字段 if (parts.length 2) throw new IllegalArgumentException(字段数不足); String name parts[0].trim(); String phone parts[1].trim(); if (!phone.matches(\\d{11})) { throw new IllegalArgumentException(手机号格式错误: phone); } String birthday parts.length 2 ? parts[2].trim() : null; insert(new Contact(name, phone, birthday)); successCount; } catch (IllegalArgumentException e) { System.err.println(跳过非法行 line : e.getMessage()); continue; // 单行失败不影响整体 } } System.out.println(成功导入 successCount 条联系人); } } // 导出方法使用 try-with-resources 保证流关闭 public void exportToTxt(String filename) throws IOException { try (PrintWriter writer new PrintWriter(new FileWriter(filename))) { ContactNode current head.next; while (current ! tail) { Contact c current.contact; writer.printf(%s|%s|%s%n, c.getName(), c.getPhone(), c.getBirthday() null ? null : c.getBirthday()); current current.next; } } }关键细节split(\\|, -1)中-1参数确保a||c解析为[a, , c]而非[a, c]避免生日字段丢失导入时continue跳过单行错误而非throw终止整个导入符合真实场景容错需求printf使用%n而非\n适配不同操作系统换行符。2.4 通讯录搜索与排序模糊匹配与拼音索引的协同优化搜索支持两种模式精确匹配searchByName(张三)→ 返回所有姓名完全等于“张三”的节点模糊匹配searchByKeyword(zhang)→ 将关键词转拼音后在所有联系人的pinyinFull字段中contains()。为加速模糊搜索预计算每个联系人的完整拼音如“张三丰”→zhangsanfeng并存入Contact对象public ListContact searchByKeyword(String keyword) { if (keyword null || keyword.trim().isEmpty()) return new ArrayList(); String pinyinKey PinyinUtil.toPinyin(keyword.trim()); // zhang → zhang ListContact results new ArrayList(); ContactNode current head.next; while (current ! tail) { String fullPinyin current.contact.getPinyinFull(); // 预计算字段 if (fullPinyin ! null fullPinyin.contains(pinyinKey)) { results.add(current.contact); } current current.next; } return results; }性能权衡说明预计算pinyinFull占用额外内存但避免每次搜索都调用耗时的toPinyin()contains()是线性扫描O(n)但对于通讯录通常 1000 条足够快若数据量大可构建HashMapCharacter, ListContactNode做首字母索引本设计未采用以保持简洁。2.5 避坑双向链表操作中五个血泪教训现象 → 原因 → 解决插入后遍历时出现重复节点或跳过节点→ 原因插入时只链接了prev.next newNode和newNode.next next但忘了newNode.prev prev和next.prev newNode导致反向指针断裂。→ 解决严格按四步法操作用assert newNode.prev ! null newNode.next ! null在 debug 模式下校验。删除联系人后size不变或变为负数→ 原因删除方法中size--写在if (current ! tail)判断之外当链表为空时current tail仍执行size--。→ 解决size--必须放在成功删除节点后的if块内且删除前校验current ! tail。导入 TXT 时中文乱码显示为 ????→ 原因FileReader默认使用平台编码Windows 是 GBK而文件是 UTF-8 编码。→ 解决改用new InputStreamReader(new FileInputStream(filename), UTF-8)显式指定编码。模糊搜索 li 匹配不到 李四但 li si 可以→ 原因PinyinUtil.toPinyin(李四)返回lǐsì带声调而toPinyin(li)返回li无声调contains()失败。→ 解决统一使用PinyinUtil.toPinyinWithoutTone(name)方法移除声调符号。导出 TXT 后用 Excel 打开显示所有内容在一列→ 原因Excel 默认用逗号分隔 CSV而本设计用|分隔需手动选择分隔符。→ 解决在导出方法末尾添加注释// 提示用户用 Excel 打开时选择「分隔符号」→「其它」→ 输入 |或改用标准 CSV 格式但会增加引号转义逻辑。3. 24 点扑克牌游戏回溯生成所有排列 栈计算后缀表达式 哈希去重覆盖全部 7680 种可能3.1 为什么不用暴力枚举四则运算符数学本质决定必须用后缀表达式给定四张牌[a,b,c,d]目标是找到形如((a op1 b) op2 c) op3 d或(a op1 (b op2 (c op3 d)))等所有加括号方式。如果硬写 5 种括号模板会遗漏(a op1 b) op2 (c op3 d)这种情况且代码爆炸。正确解法是步骤一生成 4 个数字的全排列4! 24 种步骤二对每种排列枚举 3 个运算符的组合4^3 64 种 - * /步骤三对每种数字排列运算符组合生成所有合法的后缀表达式结构共 5 种对应 5 种二叉树形状步骤四用栈计算每个后缀表达式结果 ≈ 24.0浮点误差 1e-6即为解。提示本设计中PostfixEvaluator类用StackDouble计算遇到数字push遇到运算符pop两个数apop(), bpop()注意顺序b op a结果push。除法时检查a ! 0避免 NaN。3.2 五种后缀表达式模板的穷举与生成逻辑四张数字必须用完且每个运算符连接两个操作数。合法后缀表达式长度恒为 74 数 3 符且任意前缀中数字个数 运算符个数。满足此条件的模式只有 5 种由 Catalan 数 C₃ 5 决定模板编号后缀序列N数字O运算符对应括号形式1N N O N O N O((a op b) op c) op d2N N O N N O O(a op b) op (c op d)3N N N O O N O(a op (b op c)) op d4N N N O N O Oa op ((b op c) op d)5N N N N O O Oa op (b op (c op d))生成代码如下generatePostfixes方法private static final int[][] TEMPLATES { {0,0,1,0,1,0,1}, // 模板1: N N O N O N O {0,0,1,0,0,1,1}, // 模板2: N N O N N O O {0,0,0,1,1,0,1}, // 模板3: N N N O O N O {0,0,0,1,0,1,1}, // 模板4: N N N O N O O {0,0,0,0,1,1,1} // 模板5: N N N N O O O }; public ListString generatePostfixes(int[] nums, char[] ops) { ListString results new ArrayList(); for (int[] template : TEMPLATES) { StackInteger numStack new Stack(); // 存储当前可用数字索引 StackCharacter opStack new Stack(); // 存储当前可用运算符索引 for (int i 0; i nums.length; i) numStack.push(i); for (int i 0; i ops.length; i) opStack.push(i); StringBuilder postfix new StringBuilder(); boolean valid true; for (int t : template) { if (t 0) { // 需要数字 if (numStack.isEmpty()) { valid false; break; } int numIdx numStack.pop(); postfix.append(nums[numIdx]).append( ); } else { // 需要运算符 if (opStack.isEmpty()) { valid false; break; } int opIdx opStack.pop(); postfix.append(ops[opIdx]).append( ); } } if (valid !postfix.toString().trim().isEmpty()) { results.add(postfix.toString().trim()); } } return results; }关键说明TEMPLATES是硬编码的 5 种模式每个int[]中0表示放数字1表示放运算符numStack和opStack确保每个数字/运算符只用一次避免重复使用valid标志防止模板长度不匹配如模板要求 4 个数字但numStack已空。3.3 后缀表达式计算栈运算与除零保护的工业级写法public static double evaluate(String postfix) throws ArithmeticException { String[] tokens postfix.split(\\s); StackDouble stack new Stack(); for (String token : tokens) { if (token.isEmpty()) continue; if (isOperator(token)) { if (stack.size() 2) throw new ArithmeticException(表达式格式错误: 运算符缺少操作数); double a stack.pop(); // 第二个弹出的是右操作数 double b stack.pop(); // 第一个弹出的是左操作数 double result applyOp(b, a, token.charAt(0)); // 注意顺序b op a if (Double.isInfinite(result) || Double.isNaN(result)) { throw new ArithmeticException(计算溢出或非法操作); } stack.push(result); } else { try { stack.push(Double.parseDouble(token)); } catch (NumberFormatException e) { throw new ArithmeticException(非法数字: token); } } } if (stack.size() ! 1) { throw new ArithmeticException(表达式格式错误: 操作数与运算符数量不匹配); } return stack.pop(); } private static double applyOp(double a, double b, char op) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (Math.abs(b) 1e-9) throw new ArithmeticException(除零错误); return a / b; default: throw new IllegalArgumentException(未知运算符: op); } }参数与异常设计applyOp(a, b, op)中a是左操作数b是右操作数a / b符合直觉6/32Math.abs(b) 1e-9判断除零比b 0更鲁棒浮点精度所有异常都继承ArithmeticException便于上层统一捕获。3.4 解的去重与标准化哈希归一化消除等价表达式[3,3,8,8]有解8/(3-8/3)24但8 ÷ (3 - 8 ÷ 3)、8 / (3 - 8 / 3)、(8)/((3)-(8)/(3))本质相同。本设计用抽象语法树AST哈希去重将后缀表达式转为二叉树叶子为数字内部节点为运算符对树做中序遍历但数字统一替换为N运算符保留得到规范字符串如N/(N-N/N)用HashSetString存储规范字符串重复则跳过。private String normalizeToAST(String postfix) { String[] tokens postfix.split(\\s); StackNode stack new Stack(); for (String token : tokens) { if (isOperator(token)) { Node right stack.pop(); Node left stack.pop(); stack.push(new Node(token.charAt(0), left, right)); } else { stack.push(new Node(N, null, null)); // 数字统一为 N } } return inorderTraversal(stack.pop()); } private String inorderTraversal(Node node) { if (node null) return ; if (node.left null node.right null) return String.valueOf(node.val); return ( inorderTraversal(node.left) node.val inorderTraversal(node.right) ); }效果验证输入[1,2,3,4]输出 2 种唯一解123*4和(123)*4而非 10 种括号变体。3.5 避坑24 点求解中六个典型翻车点现象 → 原因 → 解决[1,1,1,1]返回无解但实际有11114≠ 24→ 原因代码中Math.abs(result - 24.0) 1e-6判断正确但evaluate()抛出ArithmeticException时未被catch导致该分支直接跳过。→ 解决try-catch包裹evaluate()调用捕获异常后continue而非让异常终止整个回溯。[4,4,4,4]输出444416等错误结果→ 原因applyOp()中减法写成a - b但后缀表达式要求b - a因为pop()顺序是右→左4 4 -应得0但算成4-40正确4 4 4 - -却错。→ 解决严格按b op a计算b是先弹出的左操作数a是后弹出的右操作数已在evaluate()中修正。程序运行 10 秒无输出→ 原因未对除法做提前剪枝[1,1,1,1]中1/1/1/1计算无问题但[1,2,3,4]中1/2/3/4产生极小浮点数后续乘法仍需计算。→ 解决在applyOp()中若op /且Math.abs(b) 1e-3直接return Double.MAX_VALUE并标记无效避免后续计算。[3,3,8,8]输出两个解但实际数学等价→ 原因AST 归一化未处理交换律ab和ba生成不同字符串。→ 解决对加法/乘法节点强制左子树 ≤ 右子树按字符串比较再生成中序遍历。输入0开头的牌如[0,1,2,3]报 NumberFormatException→ 原因Integer.parseInt(01)抛异常但扑克牌允许0代表 10。→ 解决输入预处理将0替换为10或parseDouble()允许前导零。多线程调用solve()时结果错乱→ 原因static字段如results列表被共享。→ 解决solve()方法内声明局部ListString不使用静态变量所有状态封装在实例中。4. 课程设计交付物详解源码结构、编译运行指南与实验报告写作锚点4.1 项目目录结构与各模块职责JDK 8 兼容phonebook-24game/ ├── src/ │ ├── contact/ # 通讯录核心模块 │ │ ├── Contact.java # 联系人实体含拼音预计算 │ │ ├── ContactNode.java # 链表节点 │ │ └── ContactList.java # 双向链表实现增删查改/文件IO │ ├── game/ # 24点游戏模块 │ │ ├── GameSolver.java # 主求解器回溯模板生成 │ │ ├── PostfixEvaluator.java # 后缀表达式计算器 │ │ └── ASTNormalizer.java # 解的标准化与去重 │ ├── util/ # 工具类 │ │ ├── PinyinUtil.java # 拼音转换pinyin4j 封装 │ │ └── InputParser.java # 命令行输入解析 │ └── Main.java # CLI 入口菜单驱动 ├── lib/ │ └── pinyin4j-2.5.1.jar # 拼音库已编译进 jar ├── data/ │ ├── contacts.txt # 示例通讯录数据 │ └── test-cards.txt # 24点测试用例每行 4 个数字 ├── docs/ │ ├── design.pdf # UML 类图 算法流程图 复杂度分析 │ └── report-template.docx # 实验报告框架含评分点提示 └── build.sh # 一键编译脚本javac -d bin src/**/*.java关键路径说明src/contact/下所有类构成完整通讯录ContactList是主干PinyinUtil依赖lib/pinyin4jsrc/game/中GameSolver.solve(int[])是唯一对外接口返回ListString格式化解data/目录存放测试数据避免硬编码方便教师替换考题docs/design.pdf是教师批改重点明确标注了“链表插入时间复杂度 O(1)”、“24点穷举空间复杂度 O(1)”等得分点。4.2 三步编译运行从源码到可执行 JAR无 IDE 依赖步骤 1编译所有 Java 文件# Linux/macOS javac -cp lib/pinyin4j-2.5.1.jar -d bin src/**/*.java # WindowsPowerShell javac -cp lib\pinyin4j-2.5.1.jar -d bin src\**\*.java注意-cp指定依赖路径-d bin输出到bin/目录src/**/*.java递归编译所有源文件。步骤 2打包可执行 JAR# 创建 MANIFEST.MF指定 Main-Class echo Main-Class: Main MANIFEST.MF echo Class-Path: lib/pinyin4j-2.5.1.jar MANIFEST.MF # 打包包含 classpath jar cfm phonebook-24game.jar MANIFEST.MF -C bin .步骤 3运行与测试# 直接运行自动加载 lib/ java -jar phonebook-24game.jar # 或指定 classpath 运行兼容旧版 JVM java -cp phonebook-24game.jar:lib/pinyin4j-2.5.1.jar Main # 测试 24 点命令行参数 java -cp phonebook-24game.jar:lib/pinyin4j-2.5.1.jar Main 3 3 8 8 # 输出8/(3-8/3)24验证要点运行java -jar时若报NoClassDefFoundError: net/sf/pinyin4j/PinyinHelper说明MANIFEST.MF中Class-Path路径错误应为lib/pinyin4j-2.5.1.jarJAR 内路径非绝对路径build.sh脚本已预置上述命令直接chmod x build.sh ./build.sh即可。4.3 实验报告写作指南紧扣数据结构课程核心得分点教师最关注的不是功能是否实现而是是否体现数据结构知识应用。报告中必须包含以下锚点报告章节必写内容直接抄分值权重需求分析“通讯录需支持动态增删故选用双向链表而非数组24点需穷举所有括号组合故选用后缀表达式栈规避递归深度问题”15%数据结构设计“ContactList 类中 head/tail 哨兵节点减少 4 处边界判断GameSolver 中用 Stack 计算后缀时间复杂度 O(1)固定 7 个 token”25%算法复杂度“通讯录插入平均 O(n/2)删除 O(1)24点求解总时间 O(24×64×5×7)O(53760)常数级可接受”20%测试用例“提供 contacts.txt含 10 条含中文姓名数据和 test-cards.txt含 [1,2,3,4], [3,3,8,8] 等 5 组 24 点用例”20%总结反思“双向链表的 prev/next 指针易出错通过单元测试 assert sizeexpected 验证24点中除法精度问题通过 Math.abs(diff)1e-6 解决”20%提示docs/report-template.docx已预留这些标题只需填充具体描述避免空泛“收获很大”。4.4 单元测试用例JUnit 4 验证核心逻辑附可运行代码每个模块配Test*.java例如ContactListTest.javaimport org.junit.Test; import static org.junit.Assert.*; public class ContactListTest { Test public void testInsertAndSize() { ContactList list new ContactList(); list.insert(new Contact(张三, 13800138000)); list.insert(new Contact(李四, 13900139000)); assertEquals(2, list.getSize()); // getSize() 返回 size 字段 } Test public void testSearchByName() { ContactList list new ContactList(); list.insert(new Contact(张三, 13800138000)); list.insert(new Contact(张四, 13800138001)); assertEquals(1, list.searchByName(张三).size()); assertEquals(2, list.searchByName(张).size()); // 模糊匹配 } Test public void test24PointSolve() { GameSolver solver new GameSolver(); ListString solutions solver.solve(new int[]{3,3,8,8}); assertTrue(solutions.stream().anyMatch(s - s.contains(8/(3-8/3)))); assertEquals(1, solutions.size()); // 去重后唯一解 } }运行方式javac -cp bin:lib/junit-4.13.2.jar:lib/hamcrest-core-1.3.jar test/**/*.java java -cp bin:lib/junit-4.13.2.jar:lib/hamcrest-core-1.3.jar org.junit.runner.JUnitCore contact.ContactListTest测试设计原则每个Test方法只验证一个行为失败时精准定位assertEquals(expected, actual)优于assertTrue(actual expected)失败时输出差异24点测试用[3,3,8,8]而非[1,1,1,1]因前者有解后者无解覆盖正反例。4.5 避坑课程设计交付时五个致命细节现象 → 原因 → 解决提交 ZIP 包里缺lib/目录教师运行报ClassNotFoundException→ 原因学生只传src/认为“代码就是一切”。→ 解决ZIP 必须包含src/,lib/,data/,docs/全目录build.sh脚本也一并打包。design.pdf中类图用 Visio 画教师电脑打不开→ 原因未导出为 PDF或用 Word 直接截图。→ 解决用 draw.io在线免费画图导出为 PDF或用 PlantUML 生成startuml ... enduml。实验报告写“用了 ArrayList”但代码实际用双向链表→ 原因复制粘本文还有配套的精品资源点击获取