简介殷人昆《数据结构习题解析——面向对象方法和C语言描述》配套习题解答PDF面向需要课后巩固、复习备考或深入理解C数据结构的计算机专业学生。资料共1个PDF文件大小约313KB整体小巧便于阅读内容以问答形式梳理教材绪论部分的重要题目覆盖数据与信息的关系、数据结构三要素、逻辑结构与存储结构、线性/非线性结构特点以及抽象数据类型等核心概念。其中线性结构强调每个数据成员最多一个直接前驱和直接后继非线性结构如树和图则可有多个前驱后继相关解释便于夯实概念。尤其在面向对象部分给出了C复数类complex的完整类声明、构造函数、四则运算重载和友元输出实现复数类通过私有成员封装实部虚部对外提供公有接口展示了抽象数据类型的封装与信息隐藏。全文按题号逐问解答适合快速查找答案、理清思路并自查基础概念掌握情况。目前已有546人学习对系统巩固数据结构基础、准备考试或复习C面向对象实现的读者有参考价值。1. 数据结构习题解析-面向对象方法和C语言描述为什么该按“设计题”而不是“填空题”来做“数据结构习题解析-面向对象方法和C语言描述”这本配套册子放在不同人手里用法完全不同。只想要期末答案的人会去翻“代码片段”但真正把它读完的人会发现标题里的“面向对象方法”不是风格声明而是解题前提每一道线性表、树、图题目都应该被拆成“谁是数据、谁拥有数据、谁通过接口访问数据”这三个问题。用 C 语言描述不意味着写出能编译的代码就算完成还要求你说明清楚类层次、成员可见性、析构和拷贝语义。本文按同一套思路展开先讲明数据结构题目里 ADT 与面向对象的关系再给出可复现的类设计、接口拆分和边界测试步骤最后补一个可用于考前自检的验证技巧。适合配合 C 语言学习数据结构、正在准备考研或面向对象软件工程师面试的读者。2. 面向对象方法落在何处把数据结构题重写成“接口 私有表示”的类设计2.1 为什么这类习题偏爱“抽象数据类型”这个切入点传统的数据结构教材从存储结构讲起先教数组、再教链表、然后是树和图。殷人昆这套教材的路线不同它把“抽象数据类型”作为第一层抽象存储结构只是第二层选择。配套习题解析里凡是出现“设计一个XX类”“实现一个ADT”字样的题目其实都在考同一件事能不能把逻辑行为与物理存储分开。这种拆法背后是面向对象方法的基本功。拿线性表举例逻辑上它只需要支持插入、删除、按位置取值、求长度至于内部是用连续数组还是用散列结点的链表是表示层的事。如果代码里到处直接访问p-lchild、p-rchild那么用树还是用二叉树就只是指针操作问题类设计的价值完全体现不出来。我把做这类题时的判断标准列成一张表方便对照设计位置面向过程的习惯面向对象方法下的做法数据表示全局数组或裸指针随处传入私有成员变量外部只能通过方法拿到拷贝或引用操作入口提供Insert(p, i, e)这类散装函数对象自带Insert(pos, item)由类维护不变量结构细节调用方需要知道结点类型结点类型藏在类内部甚至在.cpp里异常与错误返回错误码靠调用方自觉检查统一约定返回值与抛异常边界这也就是为什么同一个“设计顺序表类”的题放在面向过程风格里只是几行数组操作放在面向对象风格里却必须回答“构造函数里怎么初始化”“拷贝发生时怎么办”“析构时谁负责释放”。2.2 用 C 语言描述一个最小栈接口先抽象、后实现“面向对象方法”的第一步是定义接口第二步才是选择存储结构。下面这个例子刻意把接口和实现分成两层栈的逻辑操作Push、Pop、IsEmpty全部写在抽象基类里长度上限和数组空间则留在具体类中// stack_intf.h #ifndef DS_STACK_INTF_H_ #define DS_STACK_INTF_H_ #include stdexcept #include cstddef // 逻辑层只描述行为不描述存储方式 template typename T class StackIntf { public: virtual ~StackIntf() default; // 基类析构函数必须为 virtual virtual bool IsEmpty() const 0; virtual bool IsFull() const 0; virtual void Push(const T item) 0; // 满栈时抛异常或返回状态 virtual T Pop() 0; // 空栈时抛异常或返回状态 protected: std::size_t count_ 0; // 子类共享的元素计数 }; // 表示层数组实现只通过继承关系与逻辑层相连 template typename T, std::size_t N class FixedArrayStack : public StackIntfT { public: bool IsEmpty() const override { return count_ 0; } bool IsFull() const override { return count_ N; } void Push(const T item) override { if (IsFull()) { throw std::overflow_error(stack overflow); } data_[count_] item; } T Pop() override { if (IsEmpty()) { throw std::underflow_error(stack underflow); } return data_[--count_]; } private: T data_[N]{}; // 数组仍属于表示层外界不可见 }; #endif // DS_STACK_INTF_H_这个代码片段对应数据结构习题里最常见的一类“用数组实现栈”或“用链表实现栈”的变体。关键是先把析构函数声明为virtual否则后续会增加抛出 type-erased 的风险——实际是要靠基类指针删除子类对象。IsFull用 N而不是 N是防御式写法如果某次调用前计数被误改到N1仍能阻止越界写入。Pop的返回方式在纯 C 风格的题解里往往写成“输出参数e”面向对象方法下两种都可以但返回值更接近客户端直觉也更容易直接放进assert表达式。2.3 容易被忽略的拷贝控制才是面向对象习题的隐藏考点数组栈是简单类但很多同学实现完Push/Pop就以为题目完成了忽略了 C 的三五法则。当一个类持有原始指针时编译器自动生成的拷贝构造函数是浅拷贝两个栈对象会指向同一块内存析构时二次释放直接造成未定义行为。习题解析里不少错误案例都死在这里。处理办法有两种。第一种是禁用拷贝像顺序表、链表这类本就不该被大体积复制的结构用 delete把拷贝构造和赋值运算符禁掉干净利落第二种是深拷贝或者切换到std::vector这类自带值语义的容器。真正要把面向对象方法答完整应该在代码注释里写明这个类到底是“资源所有者”还是“纯逻辑对象”资源所有者必须有拷贝、赋值、析构的明确策略。提示凡是类里有new、malloc、文件句柄这类资源题目答案至少要说明被禁用还是被深拷贝。只写一句“用了智能指针”并不能让评分者信服写清智能指针所有权转移给谁才见功夫。3. 顺序表与单链表的标准解法先列 ADT 操作表再让 C 类按不变量落地3.1 读题第一步把自然语言翻译成操作签名拿到“实现一个带头结点的单链表支持在第 i 个位置插入元素、删除第 i 个位置元素并把值带回、求表长、清空”这类题不要立刻写while循环。先列操作表把每个操作的输入、输出、修改对象写清楚操作名输入输出是否修改对象状态Insert位置pos、元素值valuebool表示插入是否成功是Remove位置pos、输出参数old_valuebool表示删除是否成功是Size无元素个数否Clear无空表是这张表的作用是提前框定错误处理。比如“在第 i 个位置插入”的 i 是否允许等于表长允许那是尾部插入是否允许大于表长大多数题解里应返回false。删除时pos越界是静默失败还是抛异常习题原则上是“返回 false”因为这类题目很少要求引入异常机制。把这些问题在写代码前定了后面就不必在实现里临时改签名。3.2 用私有内部类隐藏结点保持面向对象封装单链表的结点类型通常只服务于链表本身不应暴露给调用方。做法是让Node成为类内部的私有嵌套结构// slist.h #include cstddef template typename T class SinglyLinkedList { private: struct Node { // 结点类型私有调用方无需关心 T data; Node* next; explicit Node(const T value) : data(value), next(nullptr) {} }; Node* head_; // 不带头结点则用头指针 std::size_t size_; public: explicit SinglyLinkedList() : head_(nullptr), size_(0) {} ~SinglyLinkedList() { Clear(); } // 防止浅拷贝导致二次释放 SinglyLinkedList(const SinglyLinkedList) delete; SinglyLinkedList operator(const SinglyLinkedList) delete; bool Insert(std::size_t pos, const T value) { if (pos size_) return false; // 允许尾插禁止跳空 if (pos 0) { Node* n new Node(value); n-next head_; head_ n; } else { Node* cur head_; for (std::size_t i 0; i pos - 1; i) { cur cur-next; } Node* n new Node(value); n-next cur-next; cur-next n; } size_; return true; } bool Remove(std::size_t pos, T old_value) { if (pos size_) return false; // 空表与越界一并拦截 Node* target; if (pos 0) { target head_; head_ head_-next; } else { Node* cur head_; for (std::size_t i 0; i pos - 1; i) { cur cur-next; } target cur-next; cur-next target-next; } old_value target-data; delete target; // 结点生命周期必须收敛在链表类内部 --size_; return true; } std::size_t Size() const { return size_; } void Clear(); };关于表头有人习惯额外加一个“带头结点”的head真正的数据从head-next开始好处是插入和删除首位时不需要单独分支不带头结点的写法则代码更少但每个操作都要考虑空表。习题解析里的答案以带头结点居多因为很多题目直接要求“带头结点”但两种实现都必须注意删除最后一个结点后head_的更新上面的if (pos 0)分支已经把这种情况处理了。Insert里for循环的条件i pos - 1来源于要找到第pos个结点的前驱。如果是带头结点循环可以从头部哨兵开始初始指针不同“前驱”的定义也不同。建议在两个版本之间各写一遍插入删除这对理解指针链断裂真正有价值。3.3 立刻套上最小测试用例而不是等写完所有功能再调试做题最忌讳“全部写完再运行”。学生时代最省时间的方案是先把类骨架写出来马上补一个只跑边界条件的小main// test_slist.cpp #include cstdio #include slist.h int main() { SinglyLinkedListint list; int old_value 0; // 空表删除必须失败 if (list.Remove(0, old_value)) { std::printf(fail: remove from empty list\n); return 1; } // 连续插入并检查每次返回值 for (int i 0; i 3; i) { if (!list.Insert(static_caststd::size_t(i), i)) { return 2; } } // 中间删除old_value 必须是被删除的值 if (!list.Remove(1, old_value) || old_value ! 1) { return 3; } // 反复删除首结点直到清空 while (list.Remove(0, old_value)) { // 循环体内不必做事Return 值已保证没越界 } if (list.Size() ! 0) return 4; return 0; }这份用例的作用是把“边界”直接暴露出来空删除、首位删除、中间删除、连续删除到空表。前两个用例一跑通头指针的更新逻辑基本就没问题了。这里bool返回值本质上就是普通错误码而面向对象 C 风格的进一步做法是保持接口不变内部改用std::optionalT表达删除结果两种都合理只要在接口处说明错误语义即可。4. 树和图的递归实现如何在 C 中转为“对象协作”的迭代版本4.1 递归解法的正确不代表你已经理解数据结构二叉树的中序、前序、后序遍历从函数角度很容易写成递归三行。但面向对象的 C 语言描述要求更进一步谁创建Node谁释放Node递归访问时每次函数调用其实是一个独立执行栈这本身就是一种“调用对象协作”。许多同学在习题册上看到“用递归和非递归两种方式实现中序遍历”会背一个用std::stack的模板却解释不清楚为什么递归在深层树时会栈溢出。这里先列一张对比表把递归与显式栈各自的花费看清楚遍历实现时间开销额外空间适用场景递归中序O(n)O(h)h 为树高函数调用栈树高小代码可读性优先显式栈中序O(n)O(h)堆上栈结构树高可能很大担心调用栈溢出层序队列O(n)O(w)w 为层最大结点数需要逐层访问、广度优先策略题目要求“不用递归”时最稳妥的做法不是硬改递归函数而是用std::stack来保存被中断的状态。这在 C 里非常自然算法书里讲的“工作栈”本来就对应类里的一个成员或局部对象。4.2 层序遍历的标准队列实现与参数约束队列实现二叉树层序遍历几乎是网上流传最广的代码体但很多角落存在两个细节要问明白一是空树的入队检查二是结点出队后的左右子树判空。一个可以直接跑在已有二叉树类上的实现如下// level_order.h #include queue #include cstdio // 假设二叉树结点由 BinaryTreeNode 模板提供 // T GetData() const // BinaryTreeNodeT* GetLeft() const // BinaryTreeNodeT* GetRight() const template typename T void LevelOrder(BinaryTreeNodeT* root) { if (!root) return; std::queueBinaryTreeNodeT* work; work.push(root); while (!work.empty()) { BinaryTreeNodeT* current work.front(); work.pop(); // 访问当下结点输出操作集中在这里 std::printf(%d\n, current-GetData()); // 左子树先入队保证同层从左到右输出 if (current-GetLeft()) work.push(current-GetLeft()); if (current-GetRight()) work.push(current-GetRight()); } }队列在循环中的含义是“已经发现、尚未访问”的结点集合。每访问一个结点就把它的孩子送入队尾因此同一层的结点会连续出队下一层结点则在上层全部出队后依序登场。由面向对象的视角看queue就是本次遍历的工作对象而二叉树自身不感知“是否被遍历过”。如果题目改为按层输出并嵌套表示下属层级需要同时记录当前层剩余结点数与下一层计数。这两种做法在习题解析中经常成对出现考点在于队内边界如果只用一个普通计数器控制循环for (int i 0; i q.size(); i)q.size()会随入队而变大从而在同层混入下一层结点结果是全部节点顺序出队而非分层输出。4.3 递归转迭代的通用套路掌握后图遍历也只是同一思想换容器图的深度优先搜索用栈或递归广度优先搜索用队列本质与树遍历没有任何模式差异差别仅在于“visited”数组需要独立维护。在 C 的实现里比较合适的做法是把 visited 状态封装成std::vectorbool并作为出入参传入而不是放在全局变量里#include vector #include queue // graph 用邻接表 vectorvectorsize_t 表示 void BFS(const std::vectorstd::vectorstd::size_t graph, std::size_t start, std::vectorbool* visited) { if (!visited || start graph.size()) return; std::queuestd::size_t work; work.push(start); (*visited)[start] true; while (!work.empty()) { std::size_t v work.front(); work.pop(); // 访问 v记账、打印或加入结果集 for (std::size_t next : graph[v]) { if (!(*visited)[next]) { (*visited)[next] true; // 入队时标记避免重复入队 work.push(next); } } } }这里(*visited)[next] true放在入队前是 BFS 的经典防重入手段如果只在出队时标记同一结点可能被多个邻居重复推进队列。这类细节在数据结构习题中属于必考的小陷阱。时间复杂度方面邻接表下的 BFS 与 DFS 都是 O(V E)邻接矩阵下则是 O(V²)。如果题目明确“图用邻接表存储”复杂度解释里写 O(VE) 即可若没有给存储结构则应当补一句“选用邻接表维护边总代价与边数成正比”。提示写非递归的树遍历时先用小规模随机树验证顺序是否正确再单独拉一条“极端链状树”验证深度较大时是否栈溢出。链状树的高度等于结点数可以轻易暴露递归实现的天花板。5. 破坏性用例优先设计用三段式自检把代码和题解需求同时验干净最后说一个多数人写题时来不及用的方法其实它比多刷十道题更值钱在动手写实现之前就把破坏性用例列出来然后让代码逐个通过。破坏性用例不是常规测试而是专门戳“结点悬空、指针失效、大小不一致”等让代码崩掉的情况。做题和平时写业务代码都是同理。一套可以直接套用的自检模板可以照这样组织// exercise_checker.h —— 对“插入/删除”类习题的最小自检器模板 #include cstdio // 1. 前置校验对象初值必须为空 // 2. 操作序列先删除空表 - 反复插入 - 反复删除 // 3. 后置校验对象重新为空且没有崩溃 template typename ListType bool RunDestructiveChecks(ListType* storage, int value) { std::size_t start_size storage-Size(); // 第一次破坏空容器删除 if (storage-Remove(0, value)) return false; // 第二次破坏首尾交替插入 for (int i 0; i 100; i) { if (!storage-Insert(0, static_castint(i))) return false; if (!storage-Insert(storage-Size(), static_castint(i))) return false; } // 第三次破坏交替删除首尾直到空 while (storage-Size() 0) { if (!storage-Remove(0, value)) return false; } // 校验不变量来回折腾后必须回到初始大小 return storage-Size() start_size; }这三段分别对应三种典型事故空表删除访问nullptr、首尾插入没有正确修改head_、连续删除后size_与真实结点数不一致。加入题解代码后只需要在main里构造对象并调用这个模板就能把八成指针问题暴露出来。如果题目更偏算法而非容器还可以把同样的思路变成“大样例抽样核对”对排序题目生成完全逆序、完全有序、全部相同、极大极小混杂四组数据对二叉树题目构造只有左子树的“退化树”验证递归深度对哈希表题目构造大量冲突键验证扩容行为。这个习惯的价值在于你把“题解对不对”的模糊问题转变成“输入-操作-不变量”的精确断言答案有错时定位就快得多。最后一条实用建议给每一个类单独建一个小清单文件里面只留三类断言——构造后为空、反复破坏后恢复、删除越界返回失败。把这套清单绑定到提交前必跑的脚本里比事后对照题解找差异可靠。本文还有配套的精品资源点击获取