数据结构实验指导书(计算机软件方向使用)

1、数据结构-C+实现实验指导书专 业： 计算机 编 者：黄建灯、赵莹莹日 期： 2009、5 单 位： 信科院信息工程系数据结构实验指导书第1部分 C+基本知识各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学发展过程中，早期数据结构教材大都采用PASCAL语言为描述工具，后来出现了采用C语言为描述工具的教材版本、至今又出现了采用C+语言为描述工具的多种教材版本。本教实验指导书是为已经学习过C+语言的学生而编写。编写实验指导书目的为了配合理论教学。程序要求在C+ Builder开发环境之下调试运行，采用面向对象方法进行设计。典型的数据结构被设计成为类（class），典型算法设计成

2、为类的函数成员，然后在主函数中声明创建类对象，根据实际需要调用重要的算法。由于C+的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的C+基本知识（结构体、类等等）做补充介绍。#include . /编译预处理class A .;/ 类成员函数定义；.int main().编译预处理等类的相关程序编码主函数程序代码一、 源程序组成 这部分内容详细参见本指导书的第3部分的程序实例。二、结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类”。在C+语言中结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式：s

3、truct 结构体类型名 类型名1 变量名1； /数据子域类型名2 变量名2；类型名n 变量名n；其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量，声明创建一个结构体变量的方法是： 结构体类型名 结构体变量名；一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型（int char 等），也可是已经定义的另一结构体名。数据子域变量名可以是简单变量，也可以是数组。它们也可以称为结构体的数据成员，它们的访问控制具有公有属性。1. 通过“结构体变量名.数据子域” 可以访问数据子域。 / 设计Student结构体，在主程序中运用。#incl

4、ude #include #include struct Student /定义结构体Student long num; / 学号 int x; / 成绩 char name10; / 姓名int main( ) Student s1; /声明创建一个结构体变量s1或者使用键盘输入 cin s1.num;cin s1.x;cin ;/为s1的数据子域提供数据s1.num=1001 ; s1. x=83; strcpy( , “ 李 明”)； /输出结构体变量s1 的内容cout “ 姓名： ” endl;cout “ 学号： ” s1.numendl

5、:cout “ 成绩：” s1.x ednl; _getch(); return 0; 2. 设计一维数组，每个数组元素是Student结构体类型，通过以下语句段可以说明结构体数组的一般用法：通过“结构体数组名下标.数据子域”访问数据域。 Student a5; /声明创建一个结构体数组a for(int i=0, i5, i+) coutai.num; /输出数组元素ai的学号域cout ； /输出数组元素ai的姓名域coutai.x; /输出数组元素ai的成绩域 以上是关于结构体的基本概念和简单运用。三、 类的基本概念及运用类的是面向对象程序的基本单位。类是由数据成员和相关的

6、函数成员组成。从面向对象的角度考虑“学生”这个类，它不仅包括“学生”的一般属性：学号、姓名、成绩等等，还应包括对于这些属性的操作：输入/输出、听课、实验、等等。 类定义的一般格式：class 类名 若干数据成员； 若干函数成员； ；类的数据成员和函数成员均存在访问控制权限问题。访问控制分为三种：公有（public）、私有(private)和受护(protected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是它们必须明确访问控制。而公有数据成员，可以认为与结构体的数据域的访问权限相同。成员函数的定义又和一般函数的定义基本相同。不同的是类中成员函数也必须明确访问控制权限。如果在类之中

7、定义成员函数带函数体，并未有什么特殊之处。如果在类之中仅有成员函数的原型声明，当在类定义之外定义函数体时，需要加上类限定标识“类名：”。下面是“学生”类的定义：class Students /定义类结构体Students private: /私有成员long num; / 学号 int x; / 成绩 char name10; / 姓名public: /公有成员 Students(); Students() ; void SetDat( long n, int x0, char *na0 ) num=n; x=x0; strcpy( name,na0); void PrintOut( ); /

8、输出函数的原型声明 .;void Students:PrintOut( ) / 输出函数前加Students: cout “ 姓名： ” name endl;cout “ 学号： ” numendl:cout “ 成绩：” x ednl; 在主程序中运用类 S main( ) Students s; /声明创建一个类对象s，调用构造函数s.PrintOut( ); /输出s的内容long m; int y; char xname10; coutmyxname;s. SetDat( m, y, xname ) ; /修改对象s数据 s. PrintOut(); /输出改变后

9、s的内容_getch(); return 0;运行结果： 姓名：O学号：0成绩：0 输入学号，成绩，姓名：1001 90 WangMing姓名：WangMing学号：1001成绩：90这个例题中数据成员全部定义为私有（private），以便保证数据安全性。而函数成员全部定义为公有（public）成员函数，可以作为类对外部的的接口。 通过s. SetDat( m, y, xname ) ; 直接访公有函数成员SetDat( )， 将实参（主函数的局部变量m, y, xname） 的数据赋给私有数据成员 num，x，name。 通过 s.PrintOut( );直接访公有函数成员PrintOut(

10、 )，间接访问输出私有成员num，x，name。四、 结构体在类中的使用 1结构体数组做类的数据成员const int MAXSIZE=100; / 数组的容量struct ElemType / 数据元素的类型 int numb; char name20; long tel; ;class Sqlist private: ElemType elemMAXSIZE; /结构体ElemType类型的数组elem 做数据成员 int length; public: Sqlist( void); Sqlist() ;/其他函数;2.结构体指针变量做类的数据成员struct NodeType / 结点的

11、结构定义 int data; / 数据域 NodeType *next; / 指针域 ;class Link /类声明 private: NodeType *Head; /指向结构构体NodeType的指针变量Head做数据成员 public: Link ( ) Head=new NodeType; / 为头结点申请空间 Head-next=Head; / 头结点Head 形成空环 ;Head Link () ; void creat(); void outs();第2部分 上机实验上机实验要求及规范一、实验目的、要求和任务数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。上机

12、实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性。但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程。按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），正确的方法是：首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体实习步骤如下：1.问题分析与系统结构设计上机实验是针对一个具体的实际问题，进行程序设计以便解决问题。首先需要充分地分析和理解问题

13、本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照面向对象技术的原则，考虑所需设计的类是什么？在主函数中如何使用类对象，如何实现问题的解决。具体来讲，搞清实际问题的若干数据元素的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），设计哪些有关操作的函数。将数据存储结构和算法对应的函数封装成为一个类，一些重要的典型的算法往往以类的成员函数形式出现。要求绘制简明扼要的系统结构图，主要描述主函数系统结构。对于复杂重要的算法，也要绘制该函数的流程图。2.详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言或自然语言写出算法框架，这时不必确定很多结构和变

14、量。编码，即程序设计。就是对详细设计结果的进一步求精，即用某种高级语言（如C+语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。3.上机准备熟悉高级语言用法，如C+语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。4.上机调试程序上机调试程序应该分步骤分层次进行。程序由简到繁、规模由小到大、数据量由少到多，逐步完成。比如，针对一个类

15、它可能有许多函数，建议首先仅仅调试类的构造函数和输入/出函数，这一步比较简单容易。即使如此，实验数据的规模也从少量几个开始（1-3个），程序调通之后，再用大量数据（十个到几十个或者更多）实验。此时，还可以排除一些错误。通过这一阶段，可以排除数据结构设计、构造函数和输入/输出函数设计的错误。然后，再把体现重要算法的函数加入到源程序之中，这包括：类代码中的函数原型声明、函数实现的程序代码以及对它的调用语句等等。此时，实验数据规模也从少量几个开始，以便检查算法设计的正确性，程序基本调通之后，再用大量数据进行实验。本阶段还可进一步排除一些错误。但是，出现错误的范围往往集在新加入的代码段之中。5.整理实

16、习报告 在上机实开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析。写出实验报告,实验报告的书写格式。二、实验基本内容及学时分配为了达到实验目的，本课程安排了五个实验单元，训练的重点在于基本的数据结构，而不是强调面面俱到。各实验单元与教科书的各章只具有粗略的对应关系，一个实验题常常涉及到几部分教学内容。总学时：12学时。1、线性表（2学时）（1） 熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现；（2） 以线性表的各种操作（建立、插入、删除等）的实现为重点；（3） 通过本次实验帮助学生提高C语言的编程能力（特别是函数参数、指针类型

17、、链表的使用）。 2、栈和队列及其应用（2学时）（1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2） 训练的要求是掌握“栈”的基本特点及其典型用法；问题求解的状态表示及其递归算法；由递归程序到非递归程序的转化方法。3、串及其应用（2学时）（1） 熟悉串类型的实现方法和文本模式；（2） 串的模式匹配算法；（3） 熟悉一般文字处理软件的设计方法，较为复杂问题的分解、求精方法。4、树、图及其应用（4学时）（1） 树和图是两种非线性数据结构，广义表的实质是树结构，而稀疏矩阵的十字链表存储结构也是图的一种存储结构，故本单元是本课的实习重点；（2） 要求学生熟悉各种

18、存储结构的特性，以及如何应用树和图结构求解具体问题；（3） 训练的要点是：递归算法的设计方法；表达式的求值技术；哈夫曼方法及其编译码技术；完整的应用系统的用户界面设计和操作定义方法；矩阵乘法的特殊操作顺序；路径遍历（树、图的遍历）技术。5、查找和排序（2学时） 本次实验旨在集中对几个专门的问题做较为深入的探讨和理解。 散列技术与实际问题关系密切，哈希函数的选择和冲突解决方法的选用都带有较强的技巧性和经验性；学生在实习中体会这一有效技术在查找和内部排序实习中，理解开发高效率算法的可能性和寻找、构造高效算法的方法。三、说明1、 该课程采用理论与实践相结合的教学方法，集知识性与趣味性于一体，达到良好

19、的教学效果。2、 硬件要求：在多媒体教室讲解及演示。为保证教学顺利进行，要求实验室提供PII及以上的微机。3、 学生每次上机实验都必须遵守实验室的有关规定。四、实验报告规范(详见附录1)五、如何提高上机效率为了提高上机的效率，真正达到实验目的，要求同学做好实验前的准备工作，写好实验预习报告，即实验报告规范中的1）、2）、3）、4）部分，编写好程序，并用一组测试数据手工执行程序静态检查程序是否有错，通过阅读、执行程序或给别人讲解自己的程序而深入全面地理解程序逻辑，提高程序的正确性。对C,C+语言程序不熟悉的同学，上机时最好带上C,C+语言程序设计的教材，以备查询。调试中遇到问题，应认真分析，确定

20、可疑点，设置调试断点或输出断点处变量的值，以便发现问题，迅速排除问题，加快调试速度。实验一 线性表一、实验目的1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。3. 掌握使用 C+面向对象的程序设计技术，设计数据结构源程序的方法。二、实验内容 1. 线性表的顺序存储表示（结构）及实现。阅读下列程序请注意几个问题。（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。顺序存储结构也称“向量（vecto

21、r）”。在下列类设计中，采用静态一维数组elem表示向量,同时用length表示线性表长度。ElemType elemMAXSIZE; int length;(2)在上机实验时，需要将数据结构的类定义（包括成员函数的定义）的程序代码，写入源程序。同时用户必须自己编写一段主函数main()，在主函数中创建声明类的具体对象，通过这些对象调用类的公有函数。以便将一个典型数据结构类运用到实际问题中去。l 源称序结构：见本资料的第1页。l 数据结构类定义（包括成员函数的定义）的程序代码对于小型程序，这部分代码可以直接放入源称序之中，如上图所示。对于复杂较大的程序，这部分代码可以生成一个头文件（例如Sql

22、istc.h）与源程序文件存储在同一个文件夹中。再在源程序之中写入一个语句，如下：#include “Sqlistc.h”;l 主函数在学生没有学习可视化图形界面之前，建议在主函数中简单设计一个“菜单”(do-while循环内嵌套一个 switch结构)。随着学习的深入，应该学会熟练使用“菜单”技术，这样会明显提高编程和运行效率。一个主函数一般样式如下：int main( ) /声明程序所需要的一般变量int i,k; ElemType e,x; /声明和创建类对象，这个类往往是典型数据结构类 Sqlist as; coutn 线性表顺序存储结构演示; do /显示菜单内容 coutnn; c

23、outnn 1. 初步建立一个线性表 ; coutnn 2. 插入一个数据元素 ; coutnn 3. 删除一个元素，返回其值; coutnn 4. 结束程序; coutn* ; coutk; /接收用户的选择/根据k值，转向对应的case 分支程序段执行switch(k) case 1: as.SetData(); as.PrintOut(); break;case 2: coutie; as.Insert(i,e); as.PrintOut(); break; case 3: couti; x=as.Delet(i); coutn 元素数值= =1&k4); / coutn 再见!; co

24、utn 按任意键，返回。; _getch(); return 0;/-要求：使用线性表实现一个通讯录，通讯录内容包含学号、姓名、电话三项数据。完成通讯录数据的建立，纪录插入和删除功能。参考程序：#include #include #include #include /-struct ElemType / 数据元素的类型 int numb; char name20; int tel; ;const int MAXSIZE=100; / 数组的容量class Sqlist private: ElemType elemMAXSIZE; int length; public: Sqlist( void

25、); Sqlist() ; void SetData(); void Insert( int i, ElemType e); ElemType Delet(int i); void PrintOut(); ;/-Sqlist:Sqlist( ) length=0；void Sqlist:SetData( ) /初步建立一个通讯录 coutlength;for(int i=0;ilength;i+) coutelemi.numb;cout ;coutelemi.tel; void Sqlist:Insert( int i, ElemType e) /请完成此函数 ElemTy

26、pe Sqlist:Delet(int i) ElemType x; int j; i-; if(ilength-1) cout i Error!endl; x.numb=-1; else return x;void Sqlist:PrintOut() /输出 coutn 通讯录总人数：length; coutn PrintOut Data:n;coutsetw(16)”学号” setw(20)”姓名”setw(20)”电话号”endl; ; for(int k=0; klength;k+) coutsetw(16)elemk.numb setw(20)setw(20)el

27、emk.telcoutendl; /-int main( ) int i,k; ElemType e,x; Sqlist as; coutn 通讯录演示; do coutnn; coutnn 1. 初步建立一个通讯录（线性表） ; coutnn 2. 插入一个数据元素 ; coutnn 3. 删除一个元素，返回其值; coutnn 4. 结束程序; coutn* ; coutk;switch(k) case 1: as.SetData(); as.PrintOut(); break; case 2: couti; coute.numb; ; coute.tel; as.In

28、sert(i,e); as.PrintOut(); break; case 3: couti; x=as.Delet(i); coutn 被删除的元素数值= setw(10)x.numb setw(10)setw(10)=1&k4); coutn 再见!; coutn 按任意键，返回。; _getch(); return 0;/- 三、实习题用链表建立通讯录。通讯录内容有：姓名、通讯地址、电话号码。 要求：（1）通讯录是按姓名项的字母顺序排列的； （2）能查找通讯录中某人的信息； 提示 可用链表来存放这个通讯录，一个人的信息作为一个结点。成链的过程可以这样考虑：先把头结点后面的第一

29、个数据元素结点作为链中的首结点，也是末结点。从第二个数据开始逐一作为工作结点，需从链表的首结点开始比较，如果工作结点的数据元素的姓名字符串比链中的当前结点的数据元素的姓名字符串小，就插在其前面。否则，再看后面是否还有结点，若没有结点了就插在其后面成为末结点；若后面还有结点，再与后面的结点逐一比较处理。 实验二 栈和队列一、实验目的1. 掌握栈这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。2. 掌握队列这种数据结构特性及其主要存储结构，并能在现实生活中灵活运用。 3. 了解和掌握递归程序设计的基本原理和方法。二、实例在教材中,我们给出了栈的链表存储结构及实现C+语言源程序和队列的链

30、表存储结构及实现C+语言源程序的实现,下面给出的是栈的顺序存储结构及实现C+语言源程序和队列的顺序存储结构及实现C+语言源程序。1栈的顺序存储结构及实现C+语言源程序。/-/栈的顺序存储结构，顺序表类/测试环境为Borland C+ Builder 5#include#include#include /-栈的顺序存储结构-typedef int ElemType; / 数据元素的类型const int MAXSIZE=100; / 数组的容量class SqStack private: ElemType elemMAXSIZE; int top; public: SqStack( void);

31、 SqStack(); int SqStack:SetEmpty(); void SqStack:push( ElemType e); ElemType SqStack:pop(); void SqStack:PrintOut(); int SqStack:IsEmpty(void)const ;/-SqStack:SqStack( void):top(0) int SqStack:SetEmpty() return top=0; void SqStack:push( ElemType e) ElemType SqStack:pop() void SqStack:PrintOut() int

32、k; cout=1;k-) coutsetw(6)elemk; coutendl; int SqStack:IsEmpty(void)const if(top=0) return 1; else return 0; /-int main(int argc, char* argv) int i,k; ElemType e,x; SqStack as; coutn 顺序表存储结构演示; do coutnn; coutnn 1.插入一个数据元素e（入栈）; coutnn 2.删除一个元素，返回其值（出栈）; coutnn 3.结束程序; coutn* ; coutk; switch(k) case

33、1:coute; as.push(e); as.PrintOut(); break; case 2: coutn 出栈; x=as.pop(); coutn 出栈元素数值= x; as.PrintOut(); break; default:break; /switch cout=1&k3); coutn 再见!; coutn 按任意键，返回。; _getch(); return 0;/-2队列的顺序存储结构及实现C+语言源程序。/-#include #include #define MAXSIZE 20typedef int ElemType; class SeQueue private: E

34、lemType elemMAXSIZE; int front,rear; public: SeQueue(); SeQueue(); void Display(); void AddQ(ElemType x); ElemType DelQ();SeQueue:SeQueue() front=0; rear=0; coutinit!endl; SeQueue:SeQueue();/ delete MAXSIZEQ.elem;void SeQueue:Display() ElemType x; int j=0; if(rear=front) coutQUEUE IS FULL!; elsej=fr

35、ont+1;while(j!=rear+1) x=elemj;coutx ;j=(j+1)%MAXSIZE; coutendl; void SeQueue:AddQ(ElemType x) ElemType SeQueue:DelQ() int main( ) ElemType e; int j; SeQueue h; int k; coutn 队列存储结构演示; do coutnn; coutnn 1.初步建立一个队列; coutnn 2.输出整个队列; coutnn 3.入队; coutnn 4.出队; coutnn 5.结束程序; coutn* ; coutk; switch(k) ca

36、se 1:SeQueue:SeQueue(); break; case 2:h.Display(); break; case 3: coute; h.AddQ(e); h.Display(); break; case 4: e=h.DelQ(); if(e!=-1) cout 出队的结点值是：eendl; h.Display(); break; default:break; cout=1&k5); coutn 再见!; cout0,n=0 时akm(m-1,akm(m,n-1) 当 m0,n0 时akm(m,n)= 2. 斐波那锲级数的实现： （1）设计运用递归算法的源程序，上机运行。 （2）写一个非递归算法的源程序，上机运行。并进行比较。实验三 串一、实验目的通过训练，加深理解并把握串的基本运算的特点。二、实验内容【问题描述】本题目中的串编辑要求对串实现以下两种功能：插入：把一个字符串插入到给定串的指定位置；删除：将串中某指定位置开始的若干字符从串中删除；【实现提示】 数据结构 结点结构：一个结点由DATA和LINK两个字段组成，如下所示： DATALINK在DATA字段中存放一个字符 字符串结构：用一个单循环链表表示一个字符串，如，T=ABCD