2专业基础实验1指导书1(实验一)

1、For pers onal use only in study and research; not for commercial use专业基础实验1指导书软件 101、102第1部分上机实验上机实验要求及规范一、实验目的、要求和任务数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机实验是一个重要的教学环节。学生应该重视实验环节，对于编写程序上机练习具有一定的积极性。更应该重视 实验的总结、实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向

2、对象的训练将在其它后继课程中进 行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向 下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：1问题分析与系统结构设计上机实验是针对一个具体的实际问题，进行程序设计以便解决问题。首先需要充分地分析和理解问题本身，弄清要求 做什么（而不是怎么做）， 限制条件是什么。按照面向对象技 术的原则，考虑所需设计的 类是什么？在主函数中如何使用类对象，如何实现问题的解决。 具体来讲，搞清实际问题的若干数据元素的逻辑结构（是线性表还是树、图？），确定数据 的存储结构（是顺序结构还是链表结构？），设计哪些有关操作的函数。将数

3、据存储结构和算法对应的函数封装成为一个类，一些重要的典型的算法往往以类的成员函数形式出现。要求绘制简明扼要的系统结构图，主要描述主函数系统结构。对于复杂重要的算法， 也要绘制该函数的流程图。充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。2. 详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言或自然语言写出算法框架，这 时不必确定很多结构和变量。编码，即程序设计。就是对详细设计结果的进一步求精，即用某种高级语言（如C+H语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加 一些输出语句，便于差错矫正，在程序

4、成功后再删去它们。3. 上机准备熟悉高级语言用法，如 C+语言。熟悉机器（即操作系统），基本的常用命令。静态检 查主要有两条路径， 一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或 给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。 如果程序中逻辑概念清楚，后者将比前者有效。4. 上机调试程序上机调试程序应该分步骤分层次进行。程序由简到繁、规模由小到大、数据量由少到多， 逐步完成。比如，针对一个类它可能有许多函数，建议首先仅仅调试类的构造函数和输入/出函数，这一步比较简单容易。即使如此，实验数据的规模也从少量几个开始（1-3个），程序调通之后，再用大

5、量数据（十个到几十个或者更多）实验。此时，还可以排除一些错误。通过这 一阶段，可以排除数据结构设计、构造函数和输入/输出函数设计的错误。然后，再把体现重要算法的函数加入到源程序之中，这包括：类代码中的函数原型声明、函数实现的程序代码以及对它的调用语句等等。此时，实验数据规模也从少量几个开始，以便检查算法设计的正确性，程序基本调通之后，再用大量数据进行实验。本阶段还可进一步 排除一些错误。但是，出现错误的范围往往集在新加入的代码段之中。5. 测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、 敏感性，测试方案包括模块测试和模块集成测试。6. 整理实习报告在上机实开始之前要充分准备实验数

6、据，在上机实践过程中要及时记录实验数据，在 上机实践完成之后必须及时总结分析。写出实验报告，实验报告的书写格式。实验报告书写：（1 ）实验目的及要求按任务书给出实验目的及要求，实验目的要深刻体会。（2 ）实验内容按任务书给出的实验内容抄写（3 ）解决问题的思路1）对实验问题的描述：2）算法的数据结构；3）算法基本操作的说明及分析（可能需要流程图）（4）工作表清单给出算法描述的程序代码（加附页）（5）总结1） 给出测试数据及实验结果分析与评价；2）实验方法的拓展；3）算法的时间复杂度为；4）实验心得体会附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行

7、输出， 当然还可以含有其它测试数据和运行输出（有时需要多组数据）。二、如何提高上机效率为了提高上机的效率， 真正达到实验目的， 要求同学做好实验前的准备工作，写好实验预习报告，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对c,c+语言程序不熟悉的同学，上机时最好带上c,c+语言程序设计的教材，以备查询。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。第2部分C+基本知识各种数据结构以及相应算法的描述总是要选用一种语言工具。在计

8、算机科学发展过程中，早期数据结构教材大都采用PASCALS言为描述工具，后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C+语言为描述工具的多种教材版本。本实验指导书是为已经学习过C+语言的学生而编写。程序要求在Devc+开发环境之下调试运行，采用面向对 象方法进行设计。 典型的数据结构被设计成为类（class），典型算法设计成为类的函数成员，然后在主函数中声明创建类对象，根据实际需要调用重要的算法。由于C+的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的C+基本知识（结构体、类等等）做补充介绍。#in elu

9、de编译预处理编译预处理等类的相关程序编码主函数程序代码一、源程序组成class A；/类成员函数定义;int mai n()这部分内容详细参见本指导书的第3部分的程序实例。二、结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类” 。在C+语言中结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式：struct 结构体类型名类型名1变量名1;数据子域类型名2变量名2;类型名n变量名n;其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是：int结构体类型名结构体变量名；一个结构体中可以包含多个数据

10、子域。数据子域的类型名一般指基本数据类型（char等),也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数 组。它们也可以称为结构体的数据成员，它们的访问控制具有公有属性。i. 通过“结构体变量名.数据子域”可以访问数据子域。/设计Student结构体，在主程序中运用。#in elude#in elude#in elude/定义结构体Stude nt longnum;/学号intx;/成绩charn amei0;/姓名int main() Stude ntsi;/为si的数据子域提供数据struct Stude nt声明创建一个结构体变量si或者使用键盘输入si. num=

11、1001 ;si. x=83;cin si. num; cin si. x;strcpy( si. name.李明”);cin si. name;/输出结构体变量si的内容cout “ 姓名:” endl;cout“学号:” si.numendl:cout“成绩:” si.x ednl;_getch(); return 0;2.设计一维数组，每个数组元素是Stude nt结构体类型，通过以下语句段可以说明结构 体数组的一般用法：通过“ 结构体数组名下标.数据子域”访问数据域。Stude nt a5;声明创建一个结构体数组afor(i nti=0, i5, i+) coutai.

12、num;/输出数组元素 ai的学号域cout ；/输出数组元素 ai的姓名域coutai.x;/输出数组元素ai的成绩域以上是关于结构体的基本概念和简单运用。三、类的基本概念及运用类的是面向对象程序的基本单位。类是由数据成员和相关的函数成员组成。从面向对象的角度考虑“学生”这个类，它不仅包括“学生”的一般属性：学号、姓名、成绩等等，还应包括对于这些属性的操作：输入/输出、听课、实验、等等。类定义的一般格式:class 类名若干数据成员; 若干函数成员;；类的数据成员和函数成员均存在访问控制权限问题。访问控制分为三种：公有(public )、私有(private)和受护(prot

13、ected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是它们必须明确访问控制。而公有数据成员，可以认为与结构体的数据域的访问权限相同。成员函数的定义又和一般函数的定义基本相同。不同的是类中成员函数也必须明确访问控制权限。如果在类之中定义成员函数带函数体，并未有什么特殊之处。如果在类之中仅有成员函数的原型声明，当在类定义之外定义函数体时，需要加上类限定标识“类名：”。下面是“学生”类的定义：class Stude nts private:long num;int x;char n ame10; public:Stude nts();Stude nts() ;/定义类结构体Stude

14、nts私有成员/学号/ 成绩/姓名/公有成员void SetDat( long n, i nt xO, char *naO ) num=n; x=x0; strcpy( n ame ,n a0);void Prin tOut();输出函数的原型声明;void Stude nts:Pri ntOut()输出函数前加 Stude nts: cout “ 姓名： ” iame endl;cout “学号： ” numendl:cout “成绩：” ednl;在主程序中运用类Stude main()/声明创建一个类对象s,调用构造函数输出s的内容Stude ntss;s.Prin tO

15、ut();long m; int y; char xn ame10;cout yx name;s. SetDat( m, y, xname );修改对象 s 数据s. PrintOut();输出改变后s的内容运行结果:_getch(); return 0;姓名：o学号：0成绩：0输入学号，成绩，姓名：1001 90 Wan gMi ng姓名：Wan gMi ng学号：1001成绩：90这个例题中数据成员全部定义为私有(private),以便保证数据安全性。而函数成员全部定义为公有(public )成员函数，可以作为类对外部的的接口。通过s. SetDat( m, y, xname );直接访公

16、有函数成员SetDat()，将实参(主函数的局部变量 m, y,xn ame)的数据赋给私有数据成员num, x, name。通过s.PrintOut();直接访公有函数成员PrintOut()，间接访问输出私有成员num，x，name。四、结构体在类中的使用1结构体数组做类的数据成员con st i nt MAXSIZE=100;/ 数组的容量struct ElemType/数据元素的类型 int nu mb;char n ame20;long tel;class Sqlist private:ElemType elemMAXSIZE;/结构体ElemType类型的数组 elem做数据成员i

17、nt len gth;public:Sqlist( void);Sqlist() ;/其他函数;2. 结构体指针变量做类的数据成员struct NodeType int data;/结点的结构定义/数据域NodeType *n ext;/指针域；class Link/类声明 private:NodeType *Head;指向结构构体NodeType的指针变量Head做数据成员public:Li nk ( )Head=new NodeType;Head-n ext=Head; Lin k () ;void creat();/为头结点申请空间/头结点Head形成空环Headvoid outs();

18、实验一：关于抽象数据类型ADT勺实验一、实验目的及要求1熟悉C+环境(DEVC+)，理解抽象数据类型 ADT的基本概念;2. 学会运用C设计实现复数的ADT、集合的ADT ；3. 练习运算符重载的使用。二、实验内容01. 定义复数的数据结构，在复数加法的基础上增加减法、乘法、除法操作。2. 定义集合的数据结构，实现集合的并、交、差运算基本操作。要求：演示程序有很好的界面及交互性。如：实验1的参考界面：卜-二欢迎使用真薮电算岳建花貫数的输入2”复数C2的输入包-复薮的输由4-c-cl*c25 . c =c 1 c2 c =ci*c27 . c =clZc28 -退出 输入直已Tii.中的日示dJ

19、tju丄玄-4 输入:LF= 2R+hl中的豆币= ? 输入丄312-41k；S+7i 输入：4*?+3i三、实验准备 1.计算机设备;2.程序调试环境的准备，如 Devc+环境;3实验内容的算法分析与代码设计与分析准备 四、实验背景知识1数据结构的相关知识(1) .数据结构数据结构指的是有某种关系(某一种关系)的数据元素的集合。包括以下三个方面的内容: 数据的逻辑结构一一数据元素之间的逻辑关系(D，S)。数据的存储结构一一数据元素及其关系在计算机存储器内的表示。运算（操作特征）一一对数据进行操作的特点和规范。（P）（2）.数据的逻辑结构数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关

20、，是独立于计算机的。有四大类：集合、线性结构、树型结构、图型结构。线性结构的逻辑特征是：若结构是非空集，则符合以下四个特征：有且仅有一个表头结点；有且仅有一个表尾结点；除了表头结点，其余结点均有且仅有一个直接前驱；除了表尾结点，其余结点均有且仅有一个直接后继。（3）.数据的存储结构数据的存储结构是逻辑结构用计算机语言的实现，即建立计算机的机内表示，在存储空间中建立各结点之间的关联来表示数据元素之间的逻辑关系。数据的存储结构主要有顺序存储结构和链式存储结构两大类。顺序存储结构中的元素都依次存储在一个连续的区域中，元素的物理地址就体现了元素的逻辑关系。链式存储结构中的结点不仅包含一个数据元素，还包

21、含一个指针，指向该元素逻辑上的直接后继结点。（4）.数据结构的运算1）创建运算（create）：创建一个数据结构；2）清除运算（clear）:删除数据结构中的全部元素；3）插入运算（insert）:在数据结构的指定位置上插入一个新元素；4）删除运算（remove）:将数据结构中的某个元素删除；5）搜索运算（search）:在数据结构中搜索满足一定条件的元素；6）更新运算（replace）:修改数据结构中某个元素的值；7）访问运算（retrieve）:访问数据结构中某个元素；8）遍历运算（traverse）:按照某种次序，系统地访问数据结构的各元素，使得每个元素 恰好被访问一次。（5）.数据结构

22、的规范和实现数据结构的规范（ADT ）：是指它的逻辑结构和运算的规范；数据结构的实现：是指它的存储表示和运算的实现。2复数复数的代数形式：形如 a + bi （a, b R）的数叫复数，实数 a、b分别叫做实部和虚部。 试设计一个复数类，该类有实部和虚部两个成员数据，成员数据采用私有访问权限，同时该类有两个共有成员函数。设z仁a+bi,z2=c+di是任意两个复数，复数的四则运算规定为：z1+z2 =（ a+ c） + （ b + d） i,z1-z2=（ a c） + （ b d） i,z1*z2 =（ ac bd） + （ bc+ ad） i,2 2 2 2z1/z2= （ac+bd） /

23、 （c +d ） + （bc ad） / （c +d ） i.3. 集合是一些可确定的可相互区别的事物（同种类型的数据元素）汇集在一起所组成的整体。集合的元素具有以下三个性质：（1）确定性.元素与集合的关系是属于或不属于，二者必居其一.(2) 互异性集合中元素彼此不同，没有重复的元素。(3) 无序性集合中的元素与排列顺序无关。并、交、差是集合常用的运算。五、设计与实现1 复数的有关操作(1)复数的ADTADT complex数据对象：D= e1,e2 | e1,e2 RealSet 数据关系：R1 = | el是复数的实数部分,e2是复数的虚数部分运算：Ini tComplex (v1, v2

24、 )操作结果：构造一复数，其实部和虚部分别被赋以参数v1和v2的值。DestroyComplex()操作结果：复数被销毁。GetReal(&realPart )初始条件：复数已存在。操作结果：用realPart返回复数的实部值。Getlmag(&lmagPart )初始条件：复数已存在。操作结果：用ImagPart返回复数的虚部值。Add(z1,z2)初始条件：z1, z2是复数。操作结果：返回两个复数z1、z2的和值。 ADT Complex(2)复数类模板的定义 (XXXX.h，女口 complex.h)template class Complexprivate:T real,imag;p

25、ublic:Complex();Complex(T r,T i);T Getreal()c on st;T Getimag()c on st;Complex Add(Complex &c);/其他运算Complex operator+(Complex &c);/其他运算重载void Output(ostrea m& out); void In put(istrea m& in);；(3 )复数类模板中成员函数的实现(complex.cpp)(4 )主程序模块定义在没有学习可视化图形界面之前，建议在主函数中简单设计一个菜单”(do-while循环内嵌套一个switch结构)。随着学习的深入，应该

26、学会熟练使用菜单”技术，这样会明显提高编程和运行效率。一个主函数一般样式如下：(参考代码) do显示菜单内容cout=欢迎使用复数运算系统 =n;cout1.复数C1的输入 2. 复数C2的输入n; cout3.复数的输出4.c=c1+c2n;cout5.c=c1-c26.c=c1*c2n;cout7.c=c1/c28.退出 n;cout=n;cout c1; break;case 2:c inc2; break;case 3:coutc1c2; break;case 4:c3=c1+c2; break;case 5:c3=c1-c2; break;case 6:c3=c1*c2;break;case 7:c3=c1/c2;break;case 8:retur n; break;while(1)主程序结构(实现见文件：complexmain.cpp):菜单显示；选择操作；(5)测试数据及测试结果(只列举了加法运算)1) 0,;0;应输出o2) 3.1,0;4.22,8.9;应输出 7.32+8.9 i3) -1.33,2.34;0.1,-6.5;应输出-1.23 4.16 i4) 0,9.7;-2.1,-9.7;应输出-2.15) 7.7,-8;-7.7,0;应输出-8i2 集合的有关操作(1)集合的ADTADT set/完成此部分内容 ADT