《数据结构》课程实验指导

数据结构精品课程 实验指导 数据结构实验指导 数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结 构中要解决的问题更接近于实际。数据结构实验是对学生的一种全面的综合训练，与程序设计语言课 程中的实验不同，数据结构课程中的实验多属于创造性的活动，需要自己进行问题分析、结构设计、 算法编写、编码实现、上机调试及程序测试。因此，数据结构实验是一种自主性很强的学习过程。 1实验概述 1.1教学目的 数据结构课程是计算机和信息管理等相关专业一门非常重要的专业基础课，具有承上启下的地位 和作用。当我们用计算机解决实际问题时，要涉及到数据表示及数据处理，而数据表示及数据处理正 是数据结构课程的主要研究对象，通过这两方面内容学习，为后续课程，特别是软件方面的课程打下 了厚实的知识基础，同时也提供了必要的技能训练。数据结构课程不仅具有较强的理论性，同时也具 有较强的可应用性和实践性，要想学好这门课，仅通过课堂教学或课后自学获取理论知识是远远不够 的，还必须加强实践，亲自动手设计，并上机输入、编辑、调试、运行已有的各种典型算法和（或） 自己编写的算法，从成功和失败的经验中得到锻炼，才能够熟练掌握和运用理论知识解决软件开发中 遇到的实际问题，真正达到学以致用的目的。 上机实验是数据结构课程的一个重要教学环节，通过实践，使学生对常用数据结构的基本概念及 其不同实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体 会。本书安排8个综合实验：线性表、栈、队列、广义表、树和二叉树、图、查找、排序。其侧重点 在于基本的数据结构，而不强调面面俱到。 1.2实验步骤 拿到一个题目后，一般不要急于编程，而是首先要理解问题，明确给定的条件和要求解决的问题 然后按照自顶向下、逐步求精、分而治之的策略，逐一地解决子问题。具体步骤如下：

数据结构精品课程 实验指导 1 数据结构实验指导 数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结 构中要解决的问题更接近于实际。数据结构实验是对学生的一种全面的综合训练，与程序设计语言课 程中的实验不同，数据结构课程中的实验多属于创造性的活动，需要自己进行问题分析、结构设计、 算法编写、编码实现、上机调试及程序测试。因此，数据结构实验是一种自主性很强的学习过程。 1 实验概述 1.1 教学目的 数据结构课程是计算机和信息管理等相关专业一门非常重要的专业基础课，具有承上启下的地位 和作用。当我们用计算机解决实际问题时，要涉及到数据表示及数据处理，而数据表示及数据处理正 是数据结构课程的主要研究对象，通过这两方面内容学习，为后续课程，特别是软件方面的课程打下 了厚实的知识基础，同时也提供了必要的技能训练。数据结构课程不仅具有较强的理论性，同时也具 有较强的可应用性和实践性，要想学好这门课，仅通过课堂教学或课后自学获取理论知识是远远不够 的，还必须加强实践，亲自动手设计，并上机输入、编辑、调试、运行已有的各种典型算法和（或） 自己编写的算法，从成功和失败的经验中得到锻炼，才能够熟练掌握和运用理论知识解决软件开发中 遇到的实际问题，真正达到学以致用的目的。 上机实验是数据结构课程的一个重要教学环节，通过实践，使学生对常用数据结构的基本概念及 其不同实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体 会。本书安排 8 个综合实验：线性表、栈、队列、广义表、树和二叉树、图、查找、排序。其侧重点 在于基本的数据结构，而不强调面面俱到。 1.2 实验步骤 拿到一个题目后，一般不要急于编程，而是首先要理解问题，明确给定的条件和要求解决的问题， 然后按照自顶向下、逐步求精、分而治之的策略，逐一地解决子问题。具体步骤如下：

数据结构精品课程 实验指导 1.问题分析和任务定义 明确问题要求做什么，限制条件是什么。对问题的描述应避开算法和所涉及的数据类型，而应该 就要完成的任务做出明确的回答。比如输入输出数据的类型、值的范围以及输入的形式。这一步还应 该为调试程序准备好测试数据，包括合法的输入数据和非法的输入数据。 2。数据类型和系统设计 在设计这一步骤中分为概要设计和详细设计两步实现。 (1)概要设计。 对问题描述中涉及到的数据定义抽象数据类型，设计数据结构，设计算法的伪代码描述。在这个 过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单，抽象数据类型尽可能做到数据封 闭，基本操作的说明尽可能明确。不必过早地设计存储结构，不必过早地考虑语言实现细节，不必过 早地表述辅助数据结构和局部变量。 (2)详细设计。 设计具体的存储结构以及算法所需的辅助数据结构，算法在伪代码的基础上要考虑细节问题并用 类C描述：此外，还要设计一定的用户界面。详细设计的结果是对数据结构和基本操作的规格说明做 出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法 框架。 3.算法转化和编码实现 编码是对详细设计结果的进一步求精，即用某种高级语言（比如℃语言）表达出来。静态检查主 要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）：二是通过阅读或给别人讲解自 己的程序而深入全面地理解程序逻辑，在这个过程中尽量多加一些注释语句，使程序清晰易懂。也尽 量临时增加一些输出语句，便于程序调试，在程序调试成功后可以再别除这些注释。 4.上机测试和程序调试 掌握调试工具，设计测试数据，上机调试和测试程序。调试最好分模块进行，自底向上，即先调 试底层函数模块，必要时可以另写一个调用函数。表面上看起来，这样做似乎麻烦了一些，但实际上 却可以大大降低调试时所面临的复杂性，提高工作效率。调试正确后，认真整理源程序和注释，给出 带有完整注释且格式良好的源程序清单和结果

数据结构精品课程 实验指导 2 1. 问题分析和任务定义 明确问题要求做什么，限制条件是什么。对问题的描述应避开算法和所涉及的数据类型，而应该 就要完成的任务做出明确的回答。比如输入/输出数据的类型、值的范围以及输入的形式。这一步还应 该为调试程序准备好测试数据，包括合法的输入数据和非法的输入数据。 2. 数据类型和系统设计 在设计这一步骤中分为概要设计和详细设计两步实现。 （1）概要设计。 对问题描述中涉及到的数据定义抽象数据类型，设计数据结构，设计算法的伪代码描述。在这个 过程中，要综合考虑系统的功能，使得系统结构清晰、合理、简单，抽象数据类型尽可能做到数据封 闭，基本操作的说明尽可能明确。不必过早地设计存储结构，不必过早地考虑语言实现细节，不必过 早地表述辅助数据结构和局部变量。 （2）详细设计。 设计具体的存储结构以及算法所需的辅助数据结构，算法在伪代码的基础上要考虑细节问题并用 类C描述；此外，还要设计一定的用户界面。详细设计的结果是对数据结构和基本操作的规格说明做 出进一步的求精，写出数据存储结构的类型定义，按照算法书写规范用类C语言写出函数形式的算法 框架。 3. 算法转化和编码实现 编码是对详细设计结果的进一步求精，即用某种高级语言（比如C语言）表达出来。静态检查主 要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自 己的程序而深入全面地理解程序逻辑，在这个过程中尽量多加一些注释语句，使程序清晰易懂。也尽 量临时增加一些输出语句，便于程序调试，在程序调试成功后可以再删除这些注释。 4. 上机测试和程序调试 掌握调试工具，设计测试数据，上机调试和测试程序。调试最好分模块进行，自底向上，即先调 试底层函数模块，必要时可以另写一个调用函数。表面上看起来，这样做似乎麻烦了一些，但实际上 却可以大大降低调试时所面临的复杂性，提高工作效率。调试正确后，认真整理源程序和注释，给出 带有完整注释且格式良好的源程序清单和结果

数据结构精品课程 实验指导 5。实验总结和报告写 为了培养和训练学生分析综合能力及书面表达能力，为以后进一步撰写科学实验报告及科技论文 做好前期准备，应该重视总结和整理实验报告这一环节，否则等同于没有完成实验任务。这里最能体 现个人特色或创造性思维。上机实验之前要充分准备实验数据，上机实践过程中要及时记录实验数据 上机实践完成之后必须及时总结分析，写出实验报告。 课程实验报告的基本要求如下： (1)个人信息：班级、学号、姓名、日期 (2)实验题目：实验内容叙述 (3)数据类型：数据存储结构的类型定义 (4)算法描述：按照算法书写规范用类C代码写出函数形式的算法框架 (5)程序清单：带有必要的注释 (6)调试报告：测试数据及输出结果 1.3报告示例 班级*学号中**姓名*日期◆* 1,实验题目 逆序创建单链表。 2.数据类型 typedef struct LNode int data; struct LNode *next LNode,*LinkList; 3.算法描述 逆序创建单链表的伪代码算法描述如下所示： 3

数据结构精品课程 实验指导 3 5. 实验总结和报告撰写 为了培养和训练学生分析综合能力及书面表达能力，为以后进一步撰写科学实验报告及科技论文 做好前期准备，应该重视总结和整理实验报告这一环节，否则等同于没有完成实验任务。这里最能体 现个人特色或创造性思维。上机实验之前要充分准备实验数据，上机实践过程中要及时记录实验数据， 上机实践完成之后必须及时总结分析，写出实验报告。 课程实验报告的基本要求如下： （1）个人信息：班级、学号、姓名、日期 （2）实验题目：实验内容叙述 （3）数据类型：数据存储结构的类型定义 （4）算法描述：按照算法书写规范用类 C 代码写出函数形式的算法框架 （5）程序清单：带有必要的注释 （6）调试报告：测试数据及输出结果 1.3 报告示例 班级 ****** 学号 ****** 姓名 ****** 日期 ****** 1. 实验题目 逆序创建单链表。 2. 数据类型 typedef struct LNode { int data; struct LNode *next; } LNode,*LinkList; 3. 算法描述 逆序创建单链表的伪代码算法描述如下所示：

数据结构精品课程 实验指导 多 for(i=n;1>0;-i) 1.生成一个新结点 2。按照逆位序读入数据，并存入新结点的数据域： 3.将新结点作为第一个结点插入到单链表： 4。修改单链表头结点的指针域。 逆序创建单链表的类C算法描述如下所示： void CreateList_(LinkList sL,int n)( /按黑逆序输入个元素的值，从表尾到表头逆向建立单链表红 L=new LNode:L->next=NULL: /1建立一个空链表L for(i=n:i>0:-i》[ p=new LNode;cin>>p->datar 1生成新结点 p->next=L->next; //插入新结点到虹中作为第一个结点 L->next=p; /川缘改红头结点的指针城 )//creattist_ 4.程序清单 tinclude #include ciostream.h> #include typedef struct LNode int data; struct LNode *next }LNode,*LinkList void CreateList_L(LinkList 6L,int n)( //To Creatre a LinkList 1 with HeadNode int i: LNode *p:

数据结构精品课程 实验指导 4 逆序创建单链表的类C算法描述如下所示： void CreateList_L(LinkList &L,int n) { // 按照逆序输入n个元素的值，从表尾到表头逆向建立单链表L L=new LNode; L->next=NULL; // 建立一个空链表L for(i=n;i>0;-i) { p=new LNode; cin>>p->data; // 生成新结点 p->next=L->next; // 插入新结点到L中作为第一个结点 L->next=p; // 修改L头结点的指针域 } } // CreatList_L 4. 程序清单 #include #include #include typedef struct LNode { int data; struct LNode *next; } LNode,*LinkList; void CreateList_L(LinkList &L,int n) { // To Creatre a LinkList L with HeadNode int i; LNode *p; for(i=n;i>0;-i) 1. 生成一个新结点； 2. 按照逆位序读入数据，并存入新结点的数据域； 3. 将新结点作为第一个结点插入到单链表； 4. 修改单链表头结点的指针域

数据结构精品课程 实验指导 L-new LNode; L->pext-NULL; cout"0:-i)( p=(LinkList)malloc(sizeof(LNode)); cin>>p->data: p->next-L->next; L->next-p: if(n)cout"; cin>>InitINodeNum; CreateList L(L,InitLNodeNum); cout<<"OK.!"<<endl; getch(); /main() 5.调试报告 第一组测试数据： InitLNodeNum=0 第一组输出结果： A NULL LinkList have been created 第二组测试数据：

数据结构精品课程 实验指导 5 L=new LNode; L->next=NULL; cout"0;-i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; } if(n) cout "; cin>>InitLNodeNum; CreateList_L(L,InitLNodeNum); cout<<"OK.!"<<endl; getch(); } // main() 5. 调试报告 第一组测试数据： InitLNodeNum=0 第一组输出结果： A NULL LinkList have been created ! 第二组测试数据：

数据结构精品课程 实验指导 InitLNodeNum-5 Please input the data for LinkList Nodes: 第二组输出结果： Success to Create a LinkList 注意：测试程序应该包括运行的各种数据集合所有的输入输出情况。 2实验内容 2.1线性表综合实验（二选一） 实验1：约瑟夫环问题 。实验内容： 设有编号为1,2， ,n的风>0)个人围成一个图，每个人持有一个密码m,从第1个人 开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止 报数，报m的出圈，.，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计 算法求n个人出圈的次序。 。实验要求： 。建立模型，确定存储结构 ■对任意n个人，密码为m,实现约瑟夫环问题： 。出圈的顺序可以依次输出，也可以用一个数组存储。 实验2：一元多项式相加问题 。实验内容： 己知Axaar+a2r2+.+an”和Bxb+bx+b2r24.+bmx,并且在Ax)和Bx)中指数 相差很多，求A片Ax+Bx. 。实验要求： 。设计存储结构表示一元多项式 ■设计算法实现一元多项式相加 ■分析算法的时间复杂度和空间复杂度 2.2栈综合实验（二选一） 实验1：表达式求值问题 6

数据结构精品课程 实验指导 6 InitLNodeNum=5 Please input the data for LinkList Nodes: 第二组输出结果： Success to Create a LinkList ! 注意：测试程序应该包括运行的各种数据集合所有的输入输出情况。 2 实验内容 2.1 线性表综合实验（二选一） 实验 1：约瑟夫环问题 实验内容： 设有编号为 1，2，.，n 的 n(n>0)个人围成一个圈，每个人持有一个密码 m，从第 1 个人 开始报数，报到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到 m 时停止 报数，报 m 的出圈，.，如此下去，直到所有人全部出圈为止。当任意给定 n 和 m 后，设计 算法求 n 个人出圈的次序。 实验要求： „ 建立模型，确定存储结构 „ 对任意 n 个人，密码为 m，实现约瑟夫环问题； „ 出圈的顺序可以依次输出，也可以用一个数组存储。 实验 2：一元多项式相加问题 实验内容： 已知 A(x)=a0+a1x+a2x 2 +.+anx n 和 B(x)=b0+b1x+b2x 2 +.+bmx m ，并且在 A(x)和 B(x)中指数 相差很多，求 A(x)=A(x)+B(x)。 实验要求： „ 设计存储结构表示一元多项式 „ 设计算法实现一元多项式相加 „ 分析算法的时间复杂度和空间复杂度 2.2 栈综合实验（二选一） 实验 1：表达式求值问题

数据结构精品课程 实验指导 。实验内容 对一个合法的中缀表达式求值。假设表达式只包含+、·、×、÷四个双目运算符，且运算符 本身不具有二义性。 。实验要求： ■正确解释表达式 ■符合四则运算规则 ■输出最后的计算结果 实验2：迷宫问题 。实验内容： 迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入 口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口 处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图1所示为一个迷宫的示意 图，其中双边矩形表示迷宫，1代表有障碍，0代表无障碍。 。实验要求： ·设计数据结构存储迷宫 ■设计存储结构保存从入口到出口的通路 ·设计算法完成迷宫问题的求解 ■分析算法的时间复杂度 123456789 01111111111 入▣0,011011101111 21101011111 31010000011 41011101111 51100110001 61011001101出口6,8) 71111111111 图1迷宫示意图，其中1代表有障码，0代表无障碍 前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下 2.3队列综合实验（二选一） 实验1：双端队列问题 。实验内容：

数据结构精品课程 实验指导 7 实验内容： 对一个合法的中缀表达式求值。假设表达式只包含+、-、×、÷ 四个双目运算符，且运算符 本身不具有二义性。 实验要求： „ 正确解释表达式 „ 符合四则运算规则 „ 输出最后的计算结果 实验 2：迷宫问题 实验内容： 迷宫求解是实验心理学中的一个经典问题，心理学家把一只老鼠从一个无顶盖的大盒子的入 口处赶进迷宫，迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出口 处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。例如，图 1 所示为一个迷宫的示意 图，其中双边矩形表示迷宫，1 代表有障碍，0 代表无障碍。 实验要求： „ 设计数据结构存储迷宫 „ 设计存储结构保存从入口到出口的通路 „ 设计算法完成迷宫问题的求解 „ 分析算法的时间复杂度 2.3 队列综合实验（二选一） 实验 1：双端队列问题 实验内容： 图 1 迷宫示意图，其中 1 代表有障碍，0 代表无障碍 前进的方向有八个，分别是上、下、左、右、左上、左下、右上、右下

数据结构精品课程 实验指导 双端队列是插入和删除操作可以在两端进行的线性表，表的两端分别称作端点1和端点2。 设计双端队列的数据结构，实现入队、出队等基本操作。 。实验要求： ·设计存储结构存储双端队列 ■设计双端队列的插入和删除算法 ·分析算法的时间性能 实验2：火车车厢重排问题 ●实验内容： 一列货运列车共有m节车厢，每节车厢将停放在不同的车站。假定n个车站的编号分别为1~， 即货运列车按照第n站至第1站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢 编号应该与车站（目的地）的编号相同，使各车厢从前至后按编号1到的次序排列，这样，在 每个车站只需要卸掉最后一节车厢即可。所以，给定任意次序的车厢，必须重新排列它们。 。实验要求： ■设计存储结构存储货运列车车厢 ·设计火车车厢重排算法 ■分析算法的时间性能 2.4广义表综合实验（二选一） 实验1：魔方阵问题 。实验内容： 魔方阵，又叫幻方阵，在我国古代称为“纵横图”。它是在一个nxn的矩阵中填入1到n的 数字（为奇数），使得每一行、每一列、每条对角线的累加和都相等。例如图2就是一个3阶魔 方阵。 8i→5 →15 9→5 图23阶魔方阵示例 ●实验要求： ■设计数据结构 ■设计算法完成任意n阶魔方阵的填数 8

数据结构精品课程 实验指导 8 双端队列是插入和删除操作可以在两端进行的线性表，表的两端分别称作端点 1 和端点 2。 设计双端队列的数据结构，实现入队、出队等基本操作。 实验要求： „ 设计存储结构存储双端队列 „ 设计双端队列的插入和删除算法 „ 分析算法的时间性能 实验 2：火车车厢重排问题 实验内容： 一列货运列车共有 n 节车厢，每节车厢将停放在不同的车站。假定 n 个车站的编号分别为 1~n， 即货运列车按照第 n 站至第 1 站的次序经过这些车站。为了便于从列车上卸掉相应的车厢，车厢 编号应该与车站（目的地）的编号相同，使各车厢从前至后按编号 1 到 n 的次序排列，这样，在 每个车站只需要卸掉最后一节车厢即可。所以，给定任意次序的车厢，必须重新排列它们。 实验要求： „ 设计存储结构存储货运列车车厢 „ 设计火车车厢重排算法 „ 分析算法的时间性能 2.4 广义表综合实验（二选一） 实验 1：魔方阵问题 实验内容： 魔方阵，又叫幻方阵，在我国古代称为“纵横图”。它是在一个 n×n 的矩阵中填入 1 到 n 2的 数字（n 为奇数），使得每一行、每一列、每条对角线的累加和都相等。例如图 2 就是一个 3 阶魔 方阵。 图 2 3 阶魔方阵示例 实验要求： „ 设计数据结构 „ 设计算法完成任意 n 阶魔方阵的填数

数据结构精品课程 实验指导 ·分析算法的时间复杂度 实验2：抽签游戏问题 。实验内容： 抽签是我们日常生活中经常遇到的一件事，并且其形式有很多种。这里介绍一种抽签游戏，如图 3所示，最上面一排是游戏的参加者一称为抽签者，最下面一排是签号（奖品、公差等）。每个人依 次顺着竖线往下走，当碰到横线时，即转横向前进，碰到竖线再往下，以此类推，则游戏结束后，抽 签者会一一对应到最下面一排的签号。 Aa Ag 顺若路径走，最后对应到p2 暇设:是奖品（或公差），则A对 到P·A这个人即中签 po P1 图3抽签游戏示例 。实验要求： ■设计存储结构存储抽签者、签号、游戏用横线、竖线等 ■设计算法实现抽签 ■存储游戏的最终结果 2.5树和二叉树（二选一） 实验1：判断两棵二叉树是否相似问题 。实验内容： 设计算法判断给定的两棵二叉树是否相似。两棵二叉树当且仅当满足以下条件，称这两棵一 叉树是相似的 ()他们都为空或都只有一个根结点： (2)他们的左右子树也相似。 。实验要求： ■设计数据结构（建议采用二叉链表作存储结构） ■设计递归算法判断两棵二叉树是否相似 ■分析算法的时间复杂度 实验2：哈夫曼编码问题 ·实验内容：

数据结构精品课程 实验指导 9 „ 分析算法的时间复杂度 实验 2：抽签游戏问题 实验内容： 抽签是我们日常生活中经常遇到的一件事，并且其形式有很多种。这里介绍一种抽签游戏，如图 3 所示，最上面一排是游戏的参加者——称为抽签者，最下面一排是签号（奖品、公差等）。每个人依 次顺着竖线往下走，当碰到横线时，即转横向前进，碰到竖线再往下，以此类推，则游戏结束后，抽 签者会一一对应到最下面一排的签号。 图 3 抽签游戏示例 实验要求： „ 设计存储结构存储抽签者、签号、游戏用横线、竖线等 „ 设计算法实现抽签 „ 存储游戏的最终结果 2.5 树和二叉树（二选一） 实验 1：判断两棵二叉树是否相似问题 实验内容： 设计算法判断给定的两棵二叉树是否相似。两棵二叉树当且仅当满足以下条件，称这两棵二 叉树是相似的： (1) 他们都为空或都只有一个根结点； (2) 他们的左右子树也相似。 实验要求： „ 设计数据结构（建议采用二叉链表作存储结构） „ 设计递归算法判断两棵二叉树是否相似 „ 分析算法的时间复杂度 实验 2：哈夫曼编码问题 实验内容：

数据结构精品课程 实验指导 设某编码系统共有n个字符，使用频率分别为wl,w2,w,设计一个不等长的编码方案。 使得该编码系统的空间效率最好， 。实验要求： 设计数据结构 ■设计编码算法 ·分析算法的时间复杂度和空间复杂度 2.6图（二选-） 实验1：TSP问题 ●实验内容： 所谓TSP问题是指旅行家要旅行个城市，要求各个城市经历且仅经历一次，并要求所走的 路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题 。实验要求： ■上网查找TSP问题的应用实例 ■分析求TSP问题的全局最优解的时间复杂度 ■设计一个求近似解的算法 ■分析算法的时间复杂度 实验2：医院选址问题 。实验内容： n个村庄之间的交通图可以用有向网图来表示，图中边<vi,少上的权值表示从村庄i到村庄 j的道路长度。现在要从这个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄， 才能使所有的村庄离医院都比较近？ 。实验要求： 。建立模型，设计存储结构 ·设计算法完成问题求解 ■分析算法的时间复杂度和空间复杂度 2.7查找（二选一） 实验1：直方图问题 ●实验内容： 直方图是用来整理观测数据，分析其分布状态的统计方法，用于对总体的分布特征进行推断。 10

数据结构精品课程 实验指导 10 设某编码系统共有 n 个字符，使用频率分别为{w1, w2, ., wn}，设计一个不等长的编码方案， 使得该编码系统的空间效率最好。 实验要求： „ 设计数据结构 „ 设计编码算法 „ 分析算法的时间复杂度和空间复杂度 2.6 图（二选一） 实验 1：TSP 问题 实验内容： 所谓 TSP 问题是指旅行家要旅行 n 个城市，要求各个城市经历且仅经历一次，并要求所走的 路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人知的问题。 实验要求： „ 上网查找 TSP 问题的应用实例 „ 分析求 TSP 问题的全局最优解的时间复杂度 „ 设计一个求近似解的算法 „ 分析算法的时间复杂度 实验 2：医院选址问题 实验内容： n 个村庄之间的交通图可以用有向网图来表示，图中边上的权值表示从村庄 i 到村庄 j 的道路长度。现在要从这 n 个村庄中选择一个村庄新建一所医院，问这所医院应建在哪个村庄， 才能使所有的村庄离医院都比较近？ 实验要求： „ 建立模型，设计存储结构 „ 设计算法完成问题求解 „ 分析算法的时间复杂度和空间复杂度 2.7 查找（二选一） 实验 1：直方图问题 实验内容： 直方图是用来整理观测数据，分析其分布状态的统计方法，用于对总体的分布特征进行推断