例1学生信息检索系统 当我们需要查找某个学生的有关情况 的时候:或者想查询某个专业或年级的学 记录号学号姓名性别专业 年级 980001吴承志男计算机科学与技术98级 生的有关情况的时候,只要我们建立了相 298000李淑芳女信息与计算科学98级 39901刘丽女数学与应用数学99级 关的数据结构,按照某种算法编写了相关 49902张会友男信息与计算科学99级 程序,就可以实现计算机自动检索。由此 5990303石宝国男计算机科学与技术99级 6000801何文颖女计算机科学与技术200级 可以在学生信息检索系统中建立一张按学 7000802赵胜利男数学与应用数学2000级 号顺序排列的学生信息表和分别按姓名、 800803崔文靖男信息与计算科学200级 9010601刘丽女计算机科学与技术2001级 专业、年级顺序排列的索引表,由这四张 10010602魏永鸣男数学与应用数学2001级 (a)学生信息表 表构成的文件便是学生信息检索的数学模 型,计算机的主要操作便是按照某个特定 崔文靖8 计算机科学与技术1,5,6,9 信息与计算科学2,4,8 要求(如给定姓名)对学生信息文件进行 李淑芳 2 数学与应用数学 3,7,10 查询 刘 (c)专业索引表 石宝国 魏永鸣 6,7,8 10 赵胜利 1,2,3 张会有 99级 4,5 (b)姓名索引表 (d)年级索引表 图1.1学生信息查询系统中的数据结构 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 6 例1 学生信息检索系统 当我们需要查找某个学生的有关情况 的时候；或者想查询某个专业或年级的学 生的有关情况的时候，只要我们建立了相 关的数据结构，按照某种算法编写了相关 程序，就可以实现计算机自动检索。由此， 可以在学生信息检索系统中建立一张按学 号顺序排列的学生信息表和分别按姓名、 专业、年级顺序排列的索引表，由这四张 表构成的文件便是学生信息检索的数学模 型，计算机的主要操作便是按照某个特定 要求（如给定姓名）对学生信息文件进行 查询。 （b）姓名索引表 崔文靖 8 何文颖 6 李淑芳 2 刘 丽 3，9 石宝国 5 魏永鸣 10 吴承志 1 赵胜利 7 张会有 4 2000级 6，7，8 2001级 9，10 98级 1，2，3 99级 4，5 计算机科学与技术 1，5，6，9 信息与计算科学 2，4，8 数学与应用数学 3，7，10 记录号 学号 姓名 性别 专 业 年 级 1 980001 吴承志 男 计算机科学与技术 98级 2 980002 李淑芳 女 信息与计算科学 98级 3 990301 刘 丽 女 数学与应用数学 99级 4 990302 张会友 男 信息与计算科学 99级 5 990303 石宝国 男 计算机科学与技术 99级 6 000801 何文颖 女 计算机科学与技术 2000级 7 000802 赵胜利 男 数学与应用数学 2000级 8 000803 崔文靖 男 信息与计算科学 2000级 9 010601 刘 丽 女 计算机科学与技术 2001级 10 010602 魏永鸣 男 数学与应用数学 2001级 （a）学生信息表 （c）专业索引表 （d）年级索引表 图 1.1 学生信息查询系统中的数据结构
例2八皇后问题 ◆在八皇后问题中,处理过程不是根 据某种确定的计算法则,而是利用试 探和回溯的探索技术求解。为了求得 合理布局,在计算机中要存储布局的 当前状态。从最初的布局状态开始, 步步地进行试探,每试探一步形成 个新的状态,整个试探过程形成了 棵隐含的状态树。如图1.2所示(为 了描述方便,将八皇后问题简化为四 皇后问题) 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构,它可以应 用在许多非数值计算的问题中。 图1.2四皇后问题中隐含的状态树 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 7 在八皇后问题中，处理过程不是根 据某种确定的计算法则，而是利用试 探和回溯的探索技术求解。为了求得 合理布局，在计算机中要存储布局的 当前状态。从最初的布局状态开始， 一步步地进行试探，每试探一步形成 一个新的状态，整个试探过程形成了 一棵隐含的状态树。如图1.2所示（为 了描述方便，将八皇后问题简化为四 皇后问题）。 回溯法求解过程实质上就是一个遍 历状态树的过程。在这个问题中所出 现的树也是一种数据结构，它可以应 用在许多非数值计算的问题中。 例2 八皇后问题