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

数据结构精品课程 实验指导 数据结构实验指导 数据结构是一门实践性很强的课程，只靠读书和做习题是不能提高实践能力的，尤其是在数据结 构中要解决的问题更接近于实际。数据结构实验是对学生的一种全面的综合训练，与程序设计语言课 程中的实验不同，数据结构课程中的实验多属于创造性的活动，需要自己进行问题分析、结构设计、 算法编写、编码实现、上机调试及程序测试。因此，数据结构实验是一种自主性很强的学习过程。 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 <atdlib.h> #include ciostream.h> #include <conio.h> 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 <stdlib.h> #include <iostream.h> #include <conio.h> 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<<"Please input the data for LinkList Nodes: ceg.d,67,3,-9,45,.,>"<<end1月 for(i-n:i>0:-i)( p=(LinkList)malloc(sizeof(LNode)); cin>>p->data: p->next-L->next; L->next-p: if(n)cout<<"Success to Create a LinkList !"<Kendl; else cout<"A NULL LinkList have been created !"<endl 1//CreateList() void main() Linktist i int InitLNodeNum; cout<<"CreateList_L.cpp"<<endl<<"-="<<endl; cout<cendl<<"please input the Init LinkNode Number:<eg.5>"; 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<<"Please input the data for LinkList Nodes: <eg.4,67,3,-9,45,.>"<<endl; for(i=n;i>0;-i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; } if(n) cout<<"Success to Create a LinkList !"<<endl; else cout<<"A NULL LinkList have been created !"<<endl; } // CreateList() void main() { LinkList L; int InitLNodeNum; cout<<"CreateList_L.cpp"<<endl<<"================"<<endl; cout<<endl<<"Please input the Init LinkNode Number: <eg. 5> "; cin>>InitLNodeNum; CreateList_L(L,InitLNodeNum); cout<<"OK.!"<<endl; getch(); } // main() 5. 调试报告 第一组测试数据： InitLNodeNum=0 第一组输出结果： A NULL LinkList have been created ! 第二组测试数据：