备战2019---《数据结构与算法》复习详解---参考哈工大精品教程

第一章 绪论

本章的学习目的主要是对数据结构基础的一些概念解释，包括：

基本定义，研究对象，抽象数据型，算法，算法求解。

1.1. 数据结构起源

数据结构的创始人---Donald. Knuth

补充： 属于面向对象的编程有：C++,java , python ，三个基本特征是继承，封装，多态

（封装可以隐藏实现细节，使得代码模块化；继承可以扩展已存在的代码模块（类，多态使得同一操作面向不同对象产生不同结果）

1.2 研究对象与基本概念

注意： 这个概念经常考到，我们举例说明，比如说有一个学籍管理的表结构

数据元素—每一行记录，数据项—每个段，如学号，姓名，数据对象----每一列的信息，类似于数组。/单独的一张表就称为数据对象？？

学籍管理----一一对应表，人机---一对多-树，计划---图

补充：顺序存储： 存储单元的连续性反映元素的顺序逻辑关系

链接存储：选择任意存储单元指针表示元素的逻辑关系

1.3 抽象数据模型---ADT

数据类型：是一个值的集合和定义在这个值集合的一组操作的总称。类似int，float，bool等等这些数据类，数据类型分为两大类：原子类型（不能再分，例如int，float）和结构类型（可再分，例如：数组，线性表，树等）

抽象数据类型： 是数据模型和定义在上面的操作集合。数据结构可以用二元组来表示（D,S）（D是数据元素有限集，S是D上的关系有限集），而抽象数据类型可以用三元组进行表示（D,S,P）（P是基本操作集）。简单来概括一下，抽象数据类型==数据结构+操作。

1.4 算法及算法分析

辗转相除法是求两个自然数的最大公约数的一种方法（参考百度百科）

python算法实现：

def  gongyueshu(m,n):    r=m % n    while(r!=0):        m=n        n=r        r=m % n        #print("r是最大公约数",n)    if r==0:        print("n是最大公约数",n)if __name__=='__main__':    gongyueshu(319,377)

![()

重要！！！！！

pyth

1.5 逐步求精的程序设计方法

python代码实现：

在这里插入代码片

作业：

求程序（python版本和C语言版本---作业已写c语言版本）：设字符集为字母和数字的集合，字符的顺序为A，B，C，…，Z，0，l，2，…，9，请将下列字符串按字典顺序排列存储。PXC, 4A5C, ABC, XYC, SRSI,94,D99,H8, B9，并分析可以采取的存储方案。

答-------本题中，可采取的是链表的数据结构，通过比较字符串之间的顺序，进行插入，相比采用数组存取，更容易进行插入删除，数组不容易进行插入和删除。