C/C++与数据结构

什么是程序？算法 数据结构=程序。

数据结构是程序设计的核心,C 语言实现了常用数据结构的标准化,C语言是C 语言的直接先导。在提倡全民编程的时代,把它们融汇贯通,面向所有程序设计爱好者,是本书的主旨。

本书共26章。

第1～9章是C语言部分。从对象和运算符概念开始,通过程序比较序列,不断扩展到函数、指针和数组、顺序表、字符串、文件、链表、二维数组和指针等。它们的关系如下。

(1) 对象和运算符是计算机组织结构中存储单元和运算器在高级语言层面的映射。对象的大小、存储格式和基本操作由类型决定。编程是基于类型的设计,对象和运算符构成的表达式是程序的基本语句。

(2) 函数名是运算符的扩展,函数表达式是基本表达式的扩展。

(3) 指针和数组是对象名称和对象的扩展。指针是对象名称的扩展,它表示对象的地址。数组是对象的扩展,它是由一组对象构成的*简单的容器。指针和数组都是复合类型,即依赖其他类型而存在的类型。指针和数组互相依赖。

(4) 顺序表是带有基本操作函数的数组。

(5) 字符串既是特殊的数组,也是特殊的顺序表。

(6) 文件是特殊的顺序表。

(7) 链表是拓扑意义上的顺序表。

(8) 二维数组是特殊的数组。

第10～17章是C 语言部分。通过对称变换,实现了顺序表、字符串、链表和文件从初级到高级再到标准化的发展,包括顺序表类、String类、Date类和面向对象设计、向量类模板、链表类模板、C 流与文件等。具体关系如下。

(1) 顺序表类是从顺序表变换而来的,开始于指针到引用的变换。引用是隐藏的指针。

(2) String类是从字符串变换而来的。因为字符串是特殊的顺序表,所以这种变换可以与顺序表到顺序表类的变换类比。

(3) Data类从结构Data变换而来。面向对象设计是结构类型的扩展。

(4) 向量类模板是带有迭代器的顺序表类。迭代器是封装的、个性化的指针。

(5) 链表类模板是带有迭代器的链表。

(6) C 流与文件是从C文件变换而来的,文件读写函数由文件指针传递变为对象调用。

第18～26章是数据结构非线性部分,包括二叉树、堆、二叉搜索树、平衡二叉搜索树、树、图、B树、散列、性能分析和排序。具体关系如下。

(1) 二叉树是非线性结构和算法的基础。二叉树的垂直输出和链式存储结构的创建以二叉树的层次遍历为模型,快速排序以二叉树的前序遍历为模型,汉诺塔问题以二叉树的中序遍历为模型,二叉树深度计算、复制和删除以二叉树的后序遍历为模型。

(2) 堆是以线性连续方式存储的完全二叉树。

(3) 二叉搜索树是折半查找的扩展。

(4) 平衡二叉搜索树的删除和插入是关键操作,它们以二叉树的后序遍历迭代算法为模型。

(5) 树和图的底层结构是向量类模板和链表类模板。

(6) B树是平衡二叉搜索树的扩展。

至今,本书共改版4次,相应的改革先后在天津师范大学、北京联合大学商务学院、对外经济贸易大学和湖北工业大学实验推广,得到很多专业人士和朋友的支持和鼓励,借此机会表示衷心感谢。我们所取得的成果还存在一些需要改进的地方,现把它提供给大家,希望得到更多具有建设性的意见。

编者2020年3月

本教材共16章，从C到C 。由程序转换序列贯串，每一个程序都是在前一个程序的基础上扩展或转换而来，解决前一个程序的问题，概念逐步总结生成，变抽象为具体。实现了线性常用数据结构从低级到高级再到标准化的转换，解决了程序语言和数据结构脱节，从C语言到C 语言过渡难的问题。有多媒体教学软件与教材配套。