数据结构 读书笔记

《数据结构与算法（c++版）》（清华大学出版社）

第一章

对于非数值计算问题，主要采用数据结构义.数据结构的研究范畴主要是非数值计算问题的操作对象及它们之间的关系，以及在计算机中的表示和实现。如果有足够的存储空间存储一组操作对象，总可以查找指定的操作一对象，显示不同的操作对象，或者将这些操作对象排序成任何期望的顺序，或者修改任何特定的操作对象。数据结构有集合结构、线性结构、树状结构、图状结构四种基本结构。算法是解决特定问题求解步骤的描述，在计算机中为指令的有限序列，并且每条指令表示为一个或多个操作。对于一个算法的评价，首先应考虑算法的正确性，其次是运算量（即运行效率的高低），还要考虑算法所占的存储空间的大小，重点考虑时间复杂度。算法中基本操作执行次数通常为问题规模n的某个函数f（n），则算法时间度量T（n）=O（f（n）），为时间复杂度。

第二章

线性表是由数据类型相同的数据元素组成的有限序列，不同线性表的数据元素类型不同，可以是最简单的数值和字符，也可以是比较复杂的信息。在顺序实现中，数据存储在一个长度为maxSize，数据类型为ElemType的数组中，并用count存储在数组中的长线性表的实际元素个数。线性表的顺序存储结构有如下特点

（1）线性表的顺序存储结构用一组地址连续的存储单元依次存储线性表的元素。（2）线性表的顺序存储结构用元素在存储器中的“物理位置相邻”表示线性表中数据元素之间的逻辑关系。（3）线性表的顺序存储结构可直接存取任一个数据元素，所以线性表的顺序存储结构是一种随机存取的存储结构。（4）在进行插入或删除操作时需移动大量的数据元素。单链表是一种最简单的线性表的链式存储结构，单链表也称为线性链表，用它来存储线性表时，每个数据元素用一个结点（node）来存储，一个结点由两个成分域组成，一个是存放数据元素的data，称为数据域，另一个是存储指向此链表下一个结点的指针next，称为指针域。线性表的链式存储结构有如下特点：

（1）数据元素之间的逻辑关系由结点中的指针域表示；（2）每个元素的存储位置由其直接前驱的指针域所指示；（3）线性表的链式存储结构是非随机存取的存储结构：（4）线性表的链式存储结构中的尾结点的直接后继为空（指针域为空）。