数据结构与算法实验指导书 PDF下载

编辑推荐

本书是数据结构课程的辅助教材，采用C和C 两种语言来描述数据结构，让学生在实验与习题中体会与掌握数据结构，同时培养编程能力和分析能力。主要内容包括实验与习题两大部分，用于巩固数据结构的理论知识，提高实践应用能力。；；本书内容立足于高校教学的要求，适用于本科院校的课程和学生群体，可作为数据结构与算法课程的辅助教材，也可作为初学数据结构读者的自学读物。

；

内容简介

本书是数据结构课程的辅助教材，采用C和C 两种语言来描述数据结构，让学生在实验与习题中体会与掌握数据结构，同时培养编程能力和分析能力。主要内容包括实验与习题两大部分，用于巩固数据结构的理论知识，提高实践应用能力。本书内容立足于高校教学的要求，适用于本科院校的课程和学生群体，可作为数据结构与算法课程的辅助教材，也可作为初学数据结构读者的自学读物。

作者简介

暂无

数据结构与算法实验指导书 PDF下载

 ；
目录
第1部分实验要求及规范1第2部分面向过程语言实现数据结构3
实验0复数ADT及其实现3
实验1线性表(顺序表)4
实验2线性表(链表)7
实验3栈12
实验4队列15
实验5串与数组20
实验6树与二叉树24
实验7图27
实验8查找31
实验9排序35第3部分面向对象语言实现数据结构40
实验0复数ADT——C 实现45
实验1线性表(顺序表)——C 实现46
实验2线性表(链表)——C 实现50
实验3栈——C 实现52
实验4队列——C 实现57
实验5串与数组——C 实现62
实验6二叉树的遍历——C 实现68
实验7图——C 实现71
实验8查找——C 实现73
实验9内部排序——C 实现76第4部分习题与部分参考答案79
习题1绪论79
习题2线性表81
习题3栈和队列85
习题4串88
习题5数组和广义表89
习题6树和二叉树91
习题7图99
习题8查找106
习题9排序109参考文献113

前沿

前言；；数据结构是计算机专业的核心课程,它从长期的程序设计实践中提炼而成,运用于程序设计；更是操作系统、编译原理等计算机核心课程的基础,在计算机专业课程中起着承上启下的作用。；；数据结构与算法的原理比较抽象,概念性强,难度大,不易掌握,但同时也具有较强的可应用性和实践性。实验是一个重要的教学环节,通过实现原理与算法,并将实验结果反馈到原理与算法中去,有助于理解。；；各种数据结构以及相应算法的描述总是要选用一种语言工具。本书兼顾面向对象及面向过程两种编程思想,采用了C语言和C 两种语言来实现数据结构以及相应算法。；；本书分为四个部分: 第一部分绪论,要求学习者养成良好的实验习惯；第二部分和第三部分分别采用C语言和C 语言来描述线性结构、栈、队列、串与数组、树与二叉树、图、查找和排序等数据结构及算法；第四部分为数据结构每章的习题练习。；；本书中所有算法的实现均通过实验验证可行。希望读者通过本书的学习,能更加深入地理解和掌握数据结构的相关知识。；；由于编者水平有限,书中难免存在差错,敬请广大读者批评指正。作者的电子邮箱地址: qinwang@126.com。

；作者2018年3月

免费在线读

第3部分面向对象语言实现数据结构本部分实验指导是为已经学习过C 语言的学生而编写。编写实验指导的目的是为了配合理论教学。程序要求在Visual C 或者C Builder开发环境之下调试运行,采用面向对象方法进行设计。典型的数据结构被设计成为类(class),典型算法设计成为类的函数成员,然后在主函数中声明创建类对象,根据实际需要调用重要的算法。由于C 的使用具有一定的难度,为了更好地学习数据结构自身的知识内容,克服描述工具所带来的困难,这里针对数据结构上机实验所必需的C 基本知识(结构体、类等等)做补充介绍。1. 源程序组成；这部分内容参见本指导书的程序实例。2. 结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类”。在C 语言中,结构体和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式: struct 结构体类型名；{类型名1 变量名1；//数据子域类型名2 变量名2；类型名n 变量名n；}其中,struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个具体的结构体类型的变量,声明创建一个结构体变量的方法是: 结构体类型名结构体变量名；一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型(int char 等),也可以是已经定义的另一结构体名。数据子域变量名可以是简单变量,也可以是数组。它们也可以称为结构体的数据成员,其访问控制具有“公有”属性。(1) 通过“结构体变量名.数据子域” 可以访问数据子域。// 设计Student结构体,在主程序中运用。#include

#include

#include

struct Student//定义结构体Student{longnum； //学号int x；//成绩charname[10]； //姓名}int main( ) ；；{ Student s1；//声明创建一个结构体变量s1//为s1的数据子域提供数据s1.num=1001 ；s1. x=83；strcpy( s1.name, " 李明")；//输出结构体变量s1 的内容cout<；<； "姓名: "<；<； s1.name <；

<；<； "学号:="" "<；<；="" s1.num<；

<；<；="" "成绩:"<；<；="" s1.x="" <；

>；a[i].num；//输入数组元素a[i]的学号域cout<；<；"姓名:"； cin>；>； a[i].name；//输入数组元素a[i]的姓名域cout<；<；"成绩:"； cin>；>；a[i].x；//输入数组元素a[i]的成绩域}以上是关于结构体的基本概念和简单运用。数组a有5个数组元素,每个数组元素都是Student结构体类型。数组a的存储结构如下: ；3. 类的基本概念及运用类是面向对象程序的基本单位。类由数据成员和相关的函数成员组成。从面向对象的角度考虑“学生”这个类,它不仅包括“学生”的一般属性(学号、姓名、成绩等),还应包括对于这些属性的操作(输入输出、听课、实验等)。；类定义的一般格式: class类名{若干数据成员；若干函数成员；}；类的数据成员和函数成员均存在访问控制权限问题。访问控制分为3种: 公有(public)、私有(private)和受保护(protected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是,它们必须明确访问控制。而公有数据成员,可以认为与结构体的数据域的访问权限相同。成员函数的定义与一般函数的定义基本相同。不同的是,类中成员函数也必须明确访问控制权限。如果在类之中定义成员函数带函数体,并没有什么特殊之处。如果在类之中仅有成员函数的原型声明,那么当在类定义之外定义函数体时,需要加上类限定标识“类名: : ”。下面是“学生”类的定义: class Students//定义类结构体Students ；{private: //私有数据成员longnum；//学号int x； //成绩charname[10]；//姓名public: //公有成员函数；Students( )；；Students ( long n, int x0, char na0 ) ；；{ num=n；x=x0；strcpy( name,na0)；} ；~Students( ) { }；；void SetDat( long n, int x0, char na0 ) ；；{ num=n；x=x0；strcpy( name,na0)；；} ；void PrintOut( )；//输出函数的原型声明；//其他函数…;};voidStudents::PrintOut( )//输出函数前加Students:: {cout<< " 姓名: "<< name <

<< "学号:="" "<<="" num<

<<="" "成绩:"<<="" x="" <

>m>>y>>xname;s. SetDat( m, y, xname ) ;//修改对象s的数据 s. PrintOut( );//输出改变后s的内容Studentsw(1002, 85, "LiHua") s; //声明创建一个类对象w,调用有参构造函数w. PrintOut( ); //输出对象w的内容_getch( ); return 0;}运行结果: 姓名:O学号:0成绩:0输入学号,成绩,姓名: 1001 90 WangMing姓名:WangMing学号:1001成绩:90姓名:LiHua学号:1002成绩:85通过上面两个类对象的图示,可以了解它们的内部数据情况。对象s的数据是通过键盘输入,再经由s. SetDat( m, y, xname ) 这个公有函数的运行,提供给对象s的私有数据成员。而对象w的数据是通过Studentsw(1002, 85, "LiHua") s;声明创建对象w时自动调用构造(有形参的)函数,将实参数据提供给对象w的私有数据成员。这个例题中的数据成员全部定义为私有(private),以便保证数据安全性。而函数成员全部定义为公有(public)成员函数,可以作为类对外部的接口。通过s. SetDat( m, y, xname ) 直接访问公有函数成员SetDat( ), 将实参(主函数的局部变量m、y、xname)的数据赋值给类的私有数据成员num、x、name。通过 s.PrintOut( )直接访问公有函数成员PrintOut( ),由它间接访问和输出私有数据成员num、x、name。在面向对象的程序设计中,正确理解构造函数的作用是非常重要的。在主函数中,语句“Students s;”的作用是自动调用无参构造函数,声明创建一个类对象s。主函数中倒数第3行语句“Students w (1002, 85, "LiHua")s;”的作用是自动调用带有形参的构造函数,声明创建一个类对象w。而语句“w. PrintOut();”的作用是输出对象w的数据内容。4. 结构体在类中的使用1) 结构体数组做类的数据成员const int MAXSIZE=100; //数组的容量structElemType //数据元素的类型{int numb; char name[20]; long tel;};class Sqlist { private:ElemTypeelem[MAXSIZE];//结构体类型的数组elem[ ]做数据成员int length;public:Sqlist( void);~Sqlist( ){ };//其他函数};在上面这个类Sqlist之中,数组的每个元素elem［i］都不是简单的数据类型,而是结构体ElemType的类型。那么在输入输出时不能直接写: cin>> elem［i］或cout<< elem［i］,而需要写成: cin>>elem[i].numb; cin>>lelm[i].name;cin>>elem[I].tel;cout<< elem[i].numb;cout<

next=Head; //头结点Head 形成空环};~ Link ( ){ };voidcreat( );voidouts( );};在上面这个类Link之中,数据成员仅是一个指针,当为它申请和分配到一个结点的存储空间之后,简单的情况如上图所示。在一般情况下可以构成连接多个数据结点的链表。实验0复数ADT——C 实现〖*2〗1. 实验目的(1) 本实验是预备性实验,可以机动掌握。(2) 了解抽象数据类型(ADT)的基本概念及描述方法。(3) 通过对复数抽象数据类型ADT的实现,熟悉C/C 语法及程序设计。为以后章节的学习打下基础。2. 实例复数的抽象数据类型ADT面向对象程序设计的实现。［复数ADT的描述］ADT complex{ 数据对象:D={ c1,c2 c1,c2∈FloatSet }数据关系:R={

c1为实部,c2为虚部的实系数 }基本操作:创建一个复数creat(a);输出一个复数outputc(a);求两个复数相加之和add(a,b);求两个复数相减之差sub(a,b);求两个复数相乘之积chengji(a,b);等等;} ADT complex; ［复数ADT实现的面向对象源程序］#include

#include

class Complex//定义结构体复数类型Complex { private:floatx; //实部floaty;//虚部public:Complex( ){}Complex(float x0,float y0){ x=x0; y=y0; }~Complex( ){}void outputc( ){ cout<< "复数: "<

<<" i"="" <

<

>k;//接收用户的选择//根据k值,转向对应的case 分支程序段执行switch(k){ case 1:{as.SetData( ); as.PrintOut( ); }break;case 2:{ cout<<"\n 插入的位置,数据 i,e=?"; cin>>i>>e; as.Insert(i,e);as.PrintOut( );}break;case 3:{cout<<"\n 删除第几个元素i=?";cin>>i;x=as.Delet(i); cout<<"\n元素数值= "<

=1&&k<4);cout<<"\n再见!";cout<<"\n 按任意键,返回。";_getch( ); return 0;}//-----------------------------------------------(1) 线性表顺序存储结构的本质是: 在逻辑上相邻的两个数据元素ai-1和ai,在存储地址中也是相邻的,即地址连续。顺序存储结构也称“向量(vector)”。在下列类设计中,采用静态一维数组elem［］表示向量,同时用length表示线性表长度。ElemTypeelem[MAXSIZE];int length;有时可以采用动态一维数组来表示向量。ElemTypeelem;int length;int MAXSIZE这就要求在类的构造函数中为其elem动态分配存储空间,而在析构函数中释放内存空间。在上机实验时,需要将数据结构的类定义(包括成员函数的定义)的程序代码,写入源程序。同时用户必须自己编写一段主函数main( ),在主函数中创建声明类的具体对象,通过这些对象调用类的公有函数,以便将一个典型数据结构类运用到实际问题中去。(2) 下面是一个完整的源程序,目的是提供一个示范,供参考。［使用线性表实现一个通讯录］本程序的特点是: 数据元素的类型不再是简单类型(int、char、float),而是更加接近实用的比较复杂的结构体类型。在数据元素输入输出时,情况复杂一些。#include

#include

#include

#include

//------------------------------------------------------------struct ElemType//数据元素的类型 { int numb; char name[20]; long tel; };const int MAXSIZE=100; //数组的容量class Sqlist{ private:ElemTypeelem[MAXSIZE];int length;public:Sqlist( void);~Sqlist( ){ };voidSetData( );voidInsert( int i, ElemType e);ElemType Delet(int i);void PrintOut( );

};//------------------------------------------------------------Sqlist::Sqlist( ) { length=0;}voidSqlist::SetData( ) //初步建立一个通讯录 { cout<<\n 输入人数length="; cin>>length;for(int i=0;i

>elem[i].numb;cout<<"\n 输入姓名:";cin>> elem[i].name;cout<<"\n 输入电话号码:="; cin>>elem[i].tel;}}voidSqlist::Insert( int i, ElemType e){ int j; i--; if(i<0||i>length)cout<< " i Error!"<

i; j--) elem[j]=elem[j-1];elem[i]=e; length ; }}ElemType Sqlist::Delet(int i) {ElemType x; int j; i--;if(i<0||i>length-1){ cout<< " i Error!"<

>k;switch(k) { case 1:{as.SetData( ); as.PrintOut( );}break;case 2:{ cout<<"\n 插入的位置, i=?"; cin>>i; cout<<"\n 插入的数据编号=?"; cin>>e.numb; cout<<"\n 插入的数据姓名=?"; cin>>e.name; cout<<"\n 插入的数据电话号码=?"; cin>>e.tel; as.Insert(i,e);as.PrintOut( ); }break;case 3:{ cout<<"\n 删除第几个元素i=?";cin>>i;x=as.Delet(i);cout<<"\n被删除的元素数值= "<

<

<

<

<

<

=1&&k<4); cout<<"\n再见!";cout<<"\n 按任意键,返回。"; _getch( ); return 0;}//-----------------------------------------------实验2线性表(链表)——C 实现〖*2〗1. 实验目的(1) 了解线性表的逻辑结构特性,以及这种特性在计算机内的链表存储结构。(2) 重点是线性表的基本操作在链表结构上的实现,其中以链表的操作为侧重点,并进一步学习结构化的程序设计方法。(3) 掌握使用 C 面向对象的程序设计技术,设计数据结构源程序的方法。2. 实例(1) 线性表的链表存储表示(结构)及实现。阅读下列程序请注意几个问题。一个链表由一个头结点和若干个数据结点组成。① 每个结点的结构定义如下: struct NodeType//结点的结构定义{intnum;//编号子域char name[20]; //姓名子域NodeType next;//指针域};② 链表类的定义。在链表类之中,仅列出该链表的表头指针作为类的数据成员。例如,Head是指向上面已经定义过的结点类型NodeType的指针。具体如下: class linkList//类声明{ private: NodeType Head;};(2) 约瑟夫问题的一种描述: 编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数。方法1,报数为m的人出列(将其删除),从他在顺时针方向上的下一个人开始重新从1报数……如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程,按照出列的顺序打印出各人的编号和此人密码。方法2,报m的人出列(将其删除),将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数……如此下去,直到所有人全部出列为止。试设计一个程序求出出列顺序。要求利用单向循环链表存储结构模拟此过程,按照出列的顺序打印出各人的编号。［方法1的程序清单］#include

#include

struct NodeType//结点的结构定义 {intnum;//编号子域char name[20]; //姓名子域NodeType next;//指针域 };class Jose//类声明{ private: NodeType Head; public: Jose( ){ Head=new NodeType; //为头结点申请空间Head->next=Head;//头结点Head 形成空环};~Jose( ){ };voidcreat( );voidouts( );};void Jose::creat( ){inti=0, n; NodeTypenewp, pre, h; pre= Head; cout<<"\n 输入总人数 n=";cin>>n; for(i=0;i

num=i 1;//结点送值(号码)cout<<"\n 姓名=";cin>>newp->name;//读入姓名newp->next=Head;pre->next=newp;pre=newp;//形成循环链表} pre->next= Head->next; delete Head;//删除附加头结点Head Head=pre->next;//头指针指向第一个数据元素结点 }//建成约瑟夫环void Jose::outs( )//约瑟夫问题的方法1{int m,i; NodeType q=Head, p; cout<<"\n输入m值(m>=2)";cin>>m; cout<<"\n根据m值,开始报数输出:"<

next!=q) { for(i=1;i

next;}//报数到第m个人 cout<

num<<""<

name<

next=q->next; delete q;//第m个人出列 q=p->next; }cout<

num<<""<

name<

#include

#include

//------------------------栈的顺序存储结构------------------------typedef intElemType; //数据元素的类型const int MAXSIZE=100; //数组的容量class SqStack{ private:ElemTypeelem[MAXSIZE];int top;public:SqStack( void);~SqStack( ){};intSqStack::SetEmpty( );voidSqStack::push(ElemType e);ElemType SqStack::pop( );void SqStack::PrintOut( ); int SqStack::IsEmpty(void)const ;};//------------------------------------------------------------SqStack::SqStack( void):top(0){ }intSqStack::SetEmpty( ) { return top==0; }

voidSqStack::push(ElemType e){ if(top==MAXSIZE-1) {cout<<"栈满溢出"<

=1;k--) cout<

<

<

>k;switch(k){ case 1:{cout<<"\n 入栈,数据 e=?"; cin>>e; as.push(e); as.PrintOut( );}break; case 2:{cout<<"\n 出栈"; x=as.pop( ); cout<<"\n出栈元素数值= "<

=1&&k<4);cout<<"\n再见!";cout<<"\n 按任意键,返回。";_getch( ); return 0;}2) 栈的链式存储结构及实现（C 语言源程序）//------------------------------------------------------------

#include

#include

typedef int ElemType;struct Lsnode{ ElemType data; Lsnode next;};class LsStack{private:Lsnode top;public:LsStack( );void Display( );void Push(ElemType x);ElemType Pop( );};LsStack::LsStack( ){ LsStack p; top=NULL;}void LsStack::Display( ){Lsnode p;p=top;while(p!=NULL){cout< data;p=p->next;}cout<<"结束!outend";}void LsStack::Push(ElemTypex){Lsnode p;p=new Lsnode;p->data=x;p->next=top;top=p;}ElemType LsStack::Pop( ){Lsnode p;ElemType x;if(top!=NULL){p=top;top=top->next;x=p->data;delete p;; return x; }else{cout<<"Stack null!\n";exit(1);}}int main(){ElemType e;int j;LsStack h;int k;cout<<"\n栈的链式存储结构演示";do{cout<<"\n\n";cout<<"\n\n1.初步建立一个空栈";cout<<"\n\n2.输出整个链表栈";cout<<"\n\n3.入栈:插入数据元素e";cout<<"\n\n4.出栈:删除数据元素";cout<<"\n\n5.结束程序";cout<<"\n\";cout<<"\n请输入你的选择(1,2,3,4,5,6)";cin>>k;switch(k){case 1:{LsStack::LsStack( );}break;case 2:{h.Display( );}break;case 3:{cout<<"进栈data=??";cin>>e;h.Push(e);h.Display( );}break;case 4:{e=h.Pop( );cout<<"出栈的结点值是:"<

<

=1&&k<6);cout<<"\n再见";cout<<"\n按任意键,返回。";_getch( );return 0; }实验4队列——C 实现〖*2〗1. 实验目的(1) 掌握队列这种数据结构的逻辑特性及其主要存储结构。(2) 在简单情况下会使用顺序结构的队列,熟练掌握循环队列的使用。 (3) 在复杂情况下会使用链表结构的队列,并能在现实生活中灵活运用。2. 实例在各种教科书中关于队列的叙述十分清晰。但是,关于它们在计算机内的实现介绍不够详细。为了降低学生上机实验的难度,在此给出几个例题供参考。本实验给出了队列的顺序存储结构及实现(C 语言源程序)和队列的链式存储结构及实现(C 语言源程序）。1) 队列的顺序存储结构及实现（C 语言源程序）//------------------------------------------------------------#include

#include

#define MAXSIZE 20typedef int ElemType; class SeQueue//循环队列类{private: ElemType elem[MAXSIZE];int front,rear; public:SeQueue( );~SeQueue( );void Display( );void AddQ(ElemType x);ElemType DelQ( );};SeQueue::SeQueue( ){front=0; rear=0; cout<<"init!"<

>k;switch(k){ case 1:{SeQueue::SeQueue( );}break; case 2:{h.Display( );}break; case 3:{cout<< "进队data=?";cin>>e;h.AddQ(e);h.Display( ); }break; case 4:{ e=h.DelQ( ); if(e!=-1) cout<< "出队的结点值是:"<

<

=1&&k<5);cout<<"\n再见!";cout<<"\n 按任意键,返回。"; _getch( ); return 0;}2) 队列的链式存储结构及实现（C 语言源程序）//------------------------------------------------------------#include

#include

typedef int ElemType;struct quenode{ ElemType data; quenode next;};

<

<

<

<

<

<

<

<

<

<<">

<<>
<<>