1、桂林电子科技大学信息科技学院数据结构实验指导书数据结构 -C+ 实现实验指导书第1部分C+基本知识各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学发展过程中，早期数据结构教材大都采用 PASCALS言为描述工具，后来出现了采用 C语言为描述工具的教材版本、至今又出现了采用 C+语言为描述工具的多种教材版本。本教实验指导书是为已经学习过 C+语言的学生而编写。编写实验指导书目的为了配合理论教学。程序要求在 C+ Builder开发环境之下调试运行，采用面向对象方法进行设计。典型的数据结构被设计 成为类（class），典型算法设计成为类的函数成员，然后在主函数中声明创建类对象，根
2、据 实际需要调用重要的算法。由于C+的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的 C+基本知识（结构体、类等等）做补充介绍。一、 源程序组成#in elude 编译预处理class A ;/类成员函数定义；int mai n() Jr编译预处理等类的相关程序编码主函数程序代码这部分内容详细参见本指导书的第 3部分的程序实例。二、结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类” 。在C+语言中结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式：struct 结构体类型名类型名1变量名1; /
3、数据子域类型名2变量名2;类型名n变量名n;其中struct是保留字。结构体类型名由用户自己命名。 在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是：结构体类型名 结构体变量名；int一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型(char等)，也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数 组。它们也可以称为结构体的数据成员，它们的访问控制具有公有属性。#in clude #i nclude! #i nclude! structStude nt/定义结构体longnum;/学号intx;/成绩charn ame10;/姓
4、名/设计Student结构体，在主程序中运用。Stude nt1.通过“结构体变量名.数据子域”可以访问数据子域。int main()_getch(); return 0;2.设计一维数组，每个数组元素是 Stude nt结构体类型，通过以下语句段可以说明结构体数组的一般用法：通过“ 结构体数组名下标.数据子域”访问数据域。Stude nt a5;声明创建一个结构体数组 a以上是关于结构体的基本概念和简单运用。类的基本概念及运用类的是面向对象程序的基本单位。 类是由数据成员和相关的函数成员组成。 从面向对象 的角度考虑“学生”这个类，它不仅包括“学生”的一般属性：学号、姓名、成绩等等，还应包括
5、对于这些属性的操作：输入 /输出、听课、实验、等等。类定义的一般格式：class 类名 若干数据成员； 若干函数成员；类的数据成员和函数成员均存在访问控制权限问题。 访问控制分为三种：公有(public )、私有(private)和受护(protected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是它们必须明确访问控制。 而公有数据成员，可以认为与结构体的数据域的访问权限相同。成员函数的定义又和一般函数的定义基本相同。 不同的是类中成员函数也必须明确访问 控制权限。如果在类之中定义成员函数带函数体， 并未有什么特殊之处。 如果在类之中仅有成员函数的原型声明，当在类定义之外定义函数
6、体时，需要加上类限定标识“类名： ：”。下void SetDat( long n, int x0, char *na0 ) num=n; x=x0; strcpy( name,na0);void PrintOut( ); /输出函数的原型声明;void Students:PrintOut( ) / 输出函数前加 Students: cout “ 姓名： ”name endl;cout “学号： ” numendl:cout 成绩：” ednl;int main( ) Students s; s.PrintOut( );在主程序中运用类 Students。/声明创建一个类对象 s,调用构造函数输
7、出s的内容long m; int y; char xname10;coutmyxname;s. SetDat( m, y, xname ) ; /修改对象 s 数据s. PrintOut(); /输出改变后 s 的内容_getch(); return 0;运行结果：姓名： O学号： 0成绩： 0 输入学号，成绩，姓名： 1001 90 WangMing姓名： WangMing学号： 1001成绩： 90 这个例题中数据成员全部定义为私有( private )，以便保证数据安全性。 而函数成员全部定义为公有( public )成员函数，可以作为类对外部的的接口。 通过 s. SetDat( m,
8、 y, xname ) ; 直接访公有函数成员 SetDat( )， 将实参(主函数的局部变量 m, y, xname) 的数据赋给私有数据成员 num，x，name。 通过 s.PrintOut( ); 直接访公有函数成员 PrintOut( ) ，间接访问输出私有成员 num，x， name。四、 结构体在类中的使用1 结构体数组做类的数据成员const int MAXSIZE=100; / 数组的容量 struct ElemType / 数据元素的类型 int numb;char name20;long tel;class Sqlist private:ElemType elemMAXS
9、IZE; / 结构体 ElemType 类型的数组 elem 做数据成员int length;public:Sqlist( void);Sqlist() ;/其他函数;2.结构体指针变量做类的数据成员struct NodeType / 结点的结构定义public:Li nk ( ) Head=new NodeType;Head-n ext=Head; Lin k () ;void creat();Headvoid outs();第 2 部分 上机实验上机实验要求及规范一、实验目的、要求和任务数据结构课程具有比较强的理论性， 同时也具有较强的可应用性和实践性。 上机实验是 一个重要的教学环节。
10、一般情况下学生能够重视实验环节， 对于编写程序上机练习具有一定 的积极性。 但是容易忽略实验的总结， 忽略实验报告的撰写。 对于一名大学生必须严格训练 分析总结能力、 书面表达能力。 需要逐步培养书写科学实验报告以及科技论文的能力。 拿到 一个题目， 一般不要急于编程。 按照面向过程的程序设计思路 （关于面向对象的训练将在其 它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题， 然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：1.问题分析与系统结构设计上机实验是针对一个具体的实际问题， 进行程序设计以便解决问题。 首先需要充分地分 析
11、和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照面向对象技 术的原则，考虑所需设计的类是什么？在主函数中如何使用类对象，如何实现问题的解决。 具体来讲，搞清实际问题的若干数据元素的逻辑结构（是线性表还是树、图？），确定数据 的存储结构（是顺序结构还是链表结构？），设计哪些有关操作的函数。将数据存储结构和 算法对应的函数封装成为一个类， 一些重要的典型的算法往往以类的成员函数形式出现。 要 求绘制简明扼要的系统结构图， 主要描述主函数系统结构。 对于复杂重要的算法， 也要绘制 该函数的流程图。2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言或自然语言写出
12、算法框架，这 时不必确定很多结构和变量。编码，即程序设计。就是对详细设计结果的进一步求精，即用 某种高级语言（如 C+语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加 一些输出语句，便于差错矫正，在程序成功后再删去它们。3.上机准备熟悉高级语言用法，如 C+语言。熟悉机器（即操作系统），基本的常用命令。静态检 查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或 给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。 如果程序中逻辑概念清楚，后者将比前者有效。4.上机调试程序 上机调试程序应该分步骤分层次进行。 程序由简到繁、
13、规模由小到大、 数据量由少到多， 逐步完成。比如， 针对一个类它可能有许多函数， 建议首先仅仅调试类的构造函数和输入 / 出函数， 这一步比较简单容易。即使如此，实验数据的规模也从少量几个开始（ 1-3 个），程序调通之后，再用大量数据（十个到几十个或者更多）实验。此时，还可以排除一些错误。通过这一阶段，可以排除数据结构设计、构造函数和输入 / 输出函数设计的错误。 然后，再把体现重要算法的函数加入到源程序之中， 这包括： 类代码中的函数原型声明、 函数实现的程序代码以及对它的调用语句等等。 此时， 实验数据规模也从少量几个开始， 以便检查算法设计的正确性， 程序基本调通之后， 再用大量数据进
14、行实验。 本阶段还可进一步 排除一些错误。但是，出现错误的范围往往集在新加入的代码段之中。5.整理实习报告在上机实开始之前要充分准备实验数据， 在上机实践过程中要及时记录实验数据， 在上 机实践完成之后必须及时总结分析。写出实验报告 , 实验报告的书写格式。二、实验基本内容及学时分配为了达到实验目的， 本课程安排了五个实验单元， 训练的重点在于基本的数据结构， 而 不是强调面面俱到。 各实验单元与教科书的各章只具有粗略的对应关系， 一个实验题常常涉 及到几部分教学内容。总学时： 12 学时。1、线性表（ 2 学时）（ 1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（
15、2） 以线性表的各种操作（建立、插入、删除等）的实现为重点；（3） 通过本次实验帮助学生提高 C 语言的编程能力 （特别是函数参数、 指针类型、 链表的使用） 。2、栈和队列及其应用（ 4 学时）（ 1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵 活运用它们；（ 2） 训练的要求是掌握“栈”的基本特点及其典型用法；问题求解的状态表示及 其递归算法；由递归程序到非递归程序的转化方法。3、串及其应用（ 2 学时）（ 1） 熟悉串类型的实现方法和文本模式；（ 2） 串的模式匹配算法；（ 3） 熟悉一般文字处理软件的设计方法，较为复杂问题的分解、求精方法。4、树、图及其应用（
16、 4 学时）（ 1） 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字 链表存储结构也是图的一种存储结构，故本单元是本课的实习重点；（ 2） 要求学生熟悉各种存储结构的特性， 以及如何应用树和图结构求解具体问题； （ 3） 训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其 编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的 特殊操作顺序；路径遍历（树、图的遍历）技术。5、查找和排序（ 4 学时） 本次实验旨在集中对几个专门的问题做较为深入的探讨和理解。 散列技术与实际问题关系密切， 哈希函数的选择和冲突解决方法的选用都带有较强 的技巧性和经验
17、性； 学生在实习中体会这一有效技术在查找和内部排序实习中， 理解开发高效率算法的可能性和寻找、构造高效算法的方法。三、说明1、 该课程采用理论与实践相结合的教学方法， 集知识性与趣味性于一体， 达到良好的教学效果。2、 硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供 PII及以上的微机。3、 学生每次上机实验都必须遵守实验室的有关规定。四、实验报告规范 （详见附录 1）五、如何提高上机效率为了提高上机的效率， 真正达到实验目的， 要求同学做好实验前的准备工作， 写好实验 预习报告，即实验报告规范中的 1）、 2）、3）、 4）部分，编写好程序，并用一组测试数据手 工执行程
18、序静态检查程序是否有错， 通过阅读、 执行程序或给别人讲解自己的程序而深入全 面地理解程序逻辑， 提高程序的正确性。 对 C,C+ 语言程序不熟悉的同学， 上机时最好带上c,c+语言程序设计的教材，以备查询。调试中遇到问题，应认真分析，确定可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。实验一 线性表一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点； 并进一步学习结构化的程序设计方法。3.掌握使用 C+ 面向对象的程序设计技术，设计数据结构源程序的方
19、法。二、实验内容1. 线性表的顺序存储表示（结构）及实现。 阅读下列程序请注意几个问题。（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素 an , ai,在存储地址中也是相邻的 , 既地址连续。顺序存储结构也称“向量（ vector ）”。在下列类设计 中，采用静态一维数组 elem 表示向量 , 同时用 length 表示线性表长度。ElemType elemMAXSIZE;int length;（2） 在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写 入源程序。同时用户必须自己编写一段主函数 main（） ，在主函数中创建声明类的具体对象， 通过这
20、些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。源称序结构：见本资料的第 1 页。 数据结构类定义（包括成员函数的定义）的程序代码 对于小型程序，这部分代码可以直接放入源称序之中，如上图所示。 对于复杂较大的程序，这部分代码可以生成一个头文件（例如 Sqlistc.h ）与源程序文件存储在同一个文件夹中。再在源程序之中写入一个语句，如下：#include “Sqlistc.h ”;主函数在学生没有学习可视化图形界面之前， 建议在主函数中简单设计一个 “菜单” （do-while 循环内嵌套一个 switch 结构 ） 。随着学习的深入，应该学会熟练使用“菜单”技术，这样 会
21、明显提高编程和运行效率。一个主函数一般样式如下： int main（ ） / 声明程序所需要的一般变量int i,k; ElemType e,x;/ 声明和创建类对象，这个类往往是典型数据结构类Sqlist as;coutn 线性表顺序存储结构演示 ;do /显示菜单内容coutnn;coutnn 1. 初步建立一个线性表 ;coutnn 2.coutnn 3.coutnn 4.插入一个数据元素 ; 删除一个元素，返回其值 结束程序 ;* H / 根据 k 值，转向对应的 case 分支程序段执行switch(k) case 1: as.SetData(); as.PrintOut(); br
22、eak;case 2: coutie;as.Insert(i,e); as.PrintOut();break;case 3: couti; x=as.Delet(i); coutn 元素数值 = =1&k4); /coutn 再见 !; coutn 按任意键，返回。 ;_getch(); return 0;/ 要求：使用线性表实现一个通讯录，通讯录内容包含学号、姓名、电话三项数据。完成通 讯录数据的建立，记录插入和删除功能。参考程序：#include #include #include #include / struct ElemType / 数据元素的类型int numb;char name
23、20;int tel;const int MAXSIZE=100; / 数组的容量class Sqlistprivate:ElemType elemMAXSIZE;int length;public:Sqlist( void);Sqlist() ;void SetData();void Insert( int i, ElemType e);int Delet(int i, ElemType &e);void PrintOut();/ Sqlist:Sqlist( ) length=0;void Sqlist:SetData( ) / 初步建立一个通讯录coutn 输入人数 length=len
24、gth;for(int i=0;ilength;i+)coutelemi.numb;cout elemi.name; coutelemi.tel; void Sqlist:Insert( int i, ElemType e) / 请完成此函数 / 程序填空 1int Sqlist:Delet(int i, ElemType &e)/ 删除成功返回 1，否则返回 0/ 程序填空 2return 1; void Sqlist:PrintOut() / 输出coutn 通讯录总人数： length;coutn PrintOut Data:n;coutsetw(16) 学号 setw(20) 姓名 s
25、etw(20) 电话号 endl; for(int k=0; klength;k+)coutsetw(16)elemk.numbsetw(20)elemk.namesetw(20)elemk.tel endl;/ int main( )通讯录演示 ;初步建立一个通讯录（线性表） 插入一个数据元素 ; 删除一个元素，返回其值 ; int i,k,x; ElemType e,w; Sqlist as;coutndocoutnn;coutnn 1.coutnn 2.coutnn 3.coutnn 4. 结束程序 coutn* H coutk;switch(k)case 2: coutn couti;
26、插入的数据 编号 =?; cine.numb;case 1: as.SetData(); as.PrintOut(); break;coutncoute.name; 插入的数据 电话号 =?; cine.tel;as.Insert(i,e); as.PrintOut();break;case 3: coutnx=as.Delet(i,w);if(x=1) couti;被删除的元素数值 = setw（10）w.numbsetw(10)w.namesetw(10)=1&k4); coutn _getch(); return 0;/ 再见 !; coutn按任意键，返回。三、实习题用链表建立通讯录。
27、通讯录内容有：姓名、通讯地址、电话号码。要求：（1）通讯录是按姓名项的字母顺序排列的；（ 2）能查找通讯录中某人的信息；提示 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这 样考虑： 先把头结点后面的第一个数据元素结点作为链中的首结点， 也是末结点。 从第二个 数据开始逐一作为工作结点 ，需从链表的首结点开始比较，如果工作结点的数据元 素的姓名字符串比链中的当前结点的数据元素的姓名字符串小，就插在其前面。否则， 再看后面是否还有结点， 若没有结点了就插在其后面成为末结点； 若后面还有结点， 再与后 面的结点逐一比较处理。实验二 栈和队列一、实验目的1.掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。2. 掌握队列这种数据结构特性及其主要存储结构，3.4.并能在现实生活中灵活运用。5.了解和掌握递归程序设计的基本原理和方法。二、实例在教材中 ,我们给出了栈的链表存储结构及实现 C+ 语言源程序和队列的链表存储结构及实现C+语言源程序的实现，下面给出的是栈的顺序存储结构及实现 C+语言源程序和队列的顺序存储结构及实现 C+语言源程序。1栈的顺序存储结构及实现 C+ 语言源程序。/ /栈
