算法与数据结构实验册(2)

数据结构与算法实习_实验指导书数据结构与算法课程实习实验指导书目录实验一顺序表的基本操作 (2)实验二链表的基本操作 (3)实验三二叉树的基本操作 (4)实验四综合应用 (5)附录A 实验报告示例 (9)附录B实验报告封面、评语得分表 (12)实验一顺序表的基本操作【实验目的】1、掌握顺序存储的概念，学会对顺序表的基本操作。

2、加深对顺序存储数据结构的理解，逐步培养解决实际问题的能力。

【实验性质】设计型实验【实验内容】1、实现顺序表显示；2、实现顺序表插入；3、实现顺序表查找（显示比较次数）；4、实现顺序表删除（显示移动次数）；5、实现顺序表排序（分别实现简单选择、快速，显示比较次数、移动次数）；6、实现顺序表的折半查找（显示比较次数）；7、编程实现一个顺序表的就地逆置，即利用原表的存储空间将顺序表逆置；8顺序表有序插入（显示比较次数、移动次数），屏幕提示后，从键盘输入一个元素值，在经过排序的线性表中插入这个元素；屏幕显示比较次数和移动次数，应有溢出判断和报告；9、要求以较高的效率实现删除顺序表中元素值在x到y（x和y自定）之间的所有元素;10、编程实现将两个非递减的顺序表进行合并，要求同样的数据元素只出现一次；*11、编程实现顺序表的shell排序（步长为5, 3，1）；*12、编程实现堆排序算法；*13、利用三元组顺序表存储矩阵，实现矩阵的转置（请独立写程序实现）。

【实验环境】VC++ 6.0【实验要求】将如上文件保存在命名为学号+姓名”勺文件夹中并上传到指定的服务器。

实验二链表的基本操作【实验目的】1、掌握链表的概念，学会对链表进行操作。

2、加深对链式存储结构的理解，逐步培养解决实际问题的编程能力。

【实验性质】设计型实验【实验内容】1、实现单链表的创建；2、实现单链表的显示；3、实现单链表的查找（显示比较次数）；4、实现单链表的插入；5、实现单链表的删除（显示比较次数）；6、对已创建的链表（数据不限）进行直接插入排序；7、将链接存储线性表逆置，即最后一个结点变成第1个结点，原来倒数第2个结点变成第2个结点，如此等等；8、生成有序的两个单链表A和B （链表的数据和个数自定），其首结点指针分别为a 和b,要求将两个单链表合并为一个有序的单链表C,其首结点指针为c,并且合并后的单链表的数据不重复；9、将一个首结点指针为a的单链表A分解成两个单链表A和B，其首结点指针分别为a和b，使得链表A中含有原链表A中序号为奇数的元素，而链表B中含有原链表A中序号为偶数的元素，且保持原来的相对顺序；10、请编程实现链栈的基本操作函数，并通过调用这些基本函数，实现十进制和八进制转换的功能。

算法与数据结构实验报告实验二实验名称：线性表实现集合运算姓名：卢丽娟学号：211006289专业：软件工程班级：二班指导教师：陈亦萍日期: 2012年3月24日一、实验目的本实验是要实现线性表的集合运算，通过该实验更深刻地理解线性结构的特点，学会并掌握线性表的顺序或链式表示和实现。

二、实验内容与实验步骤采用线性表表示集合，用线性表实现集合以及基本操作，实现两个集合的并、交、差运算。

用到的各种函数如下程序步骤所示。

步骤：1. 链表销毁void DestoryList_L(list& L){ list p=L->next,s;while(p){ s=p; p=p->next;free(s);}L->next=NULL;}2. 链表初始化void InitList(list &L){ L=NULL;}3. 往链表L中插入元素e，并按升序排列，如果L中已有元素e，则不插入ListInsert_L(list &L, char e){ list p=L->next,t,s; t = L;while(p!=NULL &&p->data<= e){ if(p->data==e) return OK;t=p; p=p->next;}s =(list)malloc(sizeof(LNode));s->data=e;s->next=p;t->next=s;return OK;}4. 创建链表,按字符串输入元素void CreateList_L(list &L, int n){ L =(list)malloc(sizeof(LNode));L->next=NULL;int i=0;for(i=n;i>0;i--){ char e; scanf("%c",&e);ListInsert_L(L,e);}getchar();}5.定义输入函数，分配存储空间void inputdata(list head)//定义输入函数{ list p;char tmp;scanf("%c",&tmp);while(tmp!='\n'){ p=(list)malloc(sizeof(struct LNode));//分配存储空间p->data=tmp;p->next=head->next;head->next=p;scanf("%c",&tmp); }}6.定义输出函数，初始化，并判断其是否为空void outputdata(list head)//定义输出集合函数{ list p;p=head->next;//初始化，p指向第一个结点while(p!=NULL)//判断是否为空{ printf("%c",p->data);p=p->next;} printf("\n");//输出集合函数}7.定义集合的并集函数，其中函数的数据元素均已按值非递减排列void MergeList(list head1,list head2,list head3)//定义集合的并集函数{//已知p1、p2中的数据元素按值非递减排列。

数据结构与算法的实验报告数据结构与算法第二次实验报告电子105班赵萌2010021526实验二：栈和队列的定义及基本操作一、实验目的：. 熟练掌握栈和队列的特点. 掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用. 掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作. 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力二、实验内容:定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素;实现十进制数与八进制数的转换;定义链式队列，完成队列的基本操作：入队和出队;1．问题描述：（1）利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：. 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底;. 完成一个元素的入栈操作，修改栈顶指针;. 完成一个元素的出栈操作，修改栈顶指针;. 读取栈顶指针所指向的元素的值;. 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d 取余法。

例如：（1348）10=（2504）8N N div 8 N mod 81348 168 4168 21 021 2 52 0 2从中我们可以看出，最先产生的余数4 是转换结果的最低位，这正好符合栈的特性即后进先出的特性。

所以可以用顺序栈来模拟这个过程。

以此来实现十进制数与八进制数的转换; . 编写主程序，实现对各不同的算法调用。

（2）利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作：. 初始化一个空队列，形成一个带表头结点的空队;. 完成一个元素的入队操作，修改队尾指针;. 完成一个元素的出队操作，修改队头指针;. 修改主程序，实现对各不同的算法调用。

其他算法的描述省略，参见实现要求说明。

2．实现要求：对顺序栈的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。

《算法与数据结构》实验报告学院专业姓名学号每个实验报告的程序名为班级号_学号_姓名_题号.c++(多文件压缩为rar)实验1：ADT List（线性表）（3学时）[问题描述]线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算或并运算。

[实验目的]（1）掌握线性表的两种存储结构，即顺序表和链表。

（2）掌握在顺序表和单链表上基本操作的实现。

（3）在掌握顺序表和单链表的基本操作上进行综合题的实现。

[实验内容及要求]（1）集合的元素限定为十进制数。

（2）任意输入两个集合的元素。

（3）显示两个集合的内容及其运算结果。

[测试数据]（1）set1={3, 5, 8, 11}，set2={2, 6, 8, 9, 11, 15, 20}set1∪set2＝？set1∩set2＝？（2）set1={9, 3, 14, 6}，set2={1, 30, 3, 7, 14, 25, 6, 3, 19, 9}set1∪set2＝？set1∩set2＝？[思考]（1）算法的复杂度是多少？（2）线性表可以用顺序表或单链表实现，你采用的是哪一种？为什么？（3）若把实验要求（2）更改为两个集合内的元素是递增的，请你提出一种时间复杂度更少的算法，并说明时间复杂度是多少？《算法与数据结构》实验报告学院专业姓名学号每个实验报告的程序名为班级号_学号_姓名_题号.c++(多文件压缩为rar)实验2：串的基本操作的实现（3学时）[问题描述]串是数据类型为字符的特殊的线性表，在串的基本操作中，通常以“串的整体”作为操作对象。

所以串的基本操作和线性表有很大差别。

本实验是实现串的一些基本操作。

[实验目的]（1）熟悉串的基本操作的含义。

（2）掌握串的数组存储以及在其上实现串操作的基本方法。

（3）掌握重载操作的设计和实现方法。

[实验内容及要求]（1）不允许使用C++语言本身提供的串函数。

（2）利用数组存储实现串的基本操作：即赋值、求长度、连接、求子串、子串定位、替换、退出等操作。

《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：06111001学号：**********姓名：宝竞宇一、实验目的掌握栈的建立，输入，删除，出栈等基本操作。

应用栈解决实际问题。

二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。

要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。

例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计1、概要设计抽象数据类型定义：两个栈结构，分别用来储存数据和计算符号宏定义：函数“成功”，“失败的返回值”在主程序程序中先依次输入各表达式，存入相应各栈，然后，调用“判断函数”来判断计算符的优先次序，然后再利用计算函数来计算，表达式值。

其中还有，取栈顶元素函数，存入栈函数。

2、详细设计数据类型实现：struct t{ char dat[200];int top;}prt;入栈函数：存入数组，栈顶指针上移void pushd(long int a){ prd.dat[prd.top++]=a;}出栈：取出对应值，栈顶指针下移long int popd( ){ return prd.dat[--prd.top];}比较优先级：建立数组，比较返回大于小于号。

计算函数：以字符型输入，运算符号，用switch来分支计算判断，返回计算数值long int operation ( long int x, long int y, char a){ s witch(a){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y )return x/y;else{ printf("Divide 0.\n");return 0;}case '%': return (long int) fmod(x,y);case '^': if (y>=0 ) return (long int) pow(x,y);else return (0);default: printf("Error No. 3\n");return 0;}}主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。

福建农林大学实验报告系（教研室）：计算机专业：年级：实验课程：姓名：学号：实验室号：_ 计算机号：实验时间：指导教师签字：成绩：实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。

（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）Turbo C 3.0四、算法描述及实验步骤1、算法描述1.构造哈夫曼树的函数，定义哈夫曼树的存储结构，用于存放结果。

2.定义最大权值，根据权重建立哈夫曼树，实现哈夫曼编码。

3.定义打印链表和释放链表的函数。

4.最后在主函数里面调用这些函数，输出哈夫曼编码。

2、算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3、代码(注释)#include <stdio.h>#define maxbit 10 /*定义哈夫曼编码的最大长度*/#define maxvalue 10000 /*定义最大权值*/#define maxleaf 30 /*定义哈夫曼树中最多叶子节点个数*/#define maxnode maxleaf*2-1 /*定义哈夫曼树最多结点数*/typedef struct { /*哈夫曼编码信息的结构*/int bit[maxbit];int start;}Hcodetype;typedef struct { /*定义哈夫曼树结点的结构*/int weight; int parent; int lchild; int rchild;}Hnodetype;void huffmantree(Hnodetype huffnode[maxnode],int n) /*构造哈夫曼树的函数*/{int i,j,m1,m2,x1,x2;for(i=0;i<2*n-1;i++) /*存放哈夫曼树结点的数组huffnode[]初始化*/{huffnode[i].weight=0; huffnode[i].parent=-1; huffnode[i].lchild=-1; huffnode[i].rchild=-1;} for(i=0;i<n;i++) /*输入入N个叶子节点的权值*/{printf("请输入第%d个哈夫曼树的元数的权值：\n",i+1);scanf("%d",&huffnode[i].weight);}for(i=0;i<n-1;i++) /*开始循环构造哈夫曼树*/{m1=m2=maxvalue;x1=x2=0;for(j=0;j<n+i;j++){if(huffnode[j].weight<m1&&huffnode[j].parent==-1){m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;}else if(huffnode[j].weight<m2&&huffnode[j].parent==-1){m2=huffnode[j].weight;x2=j;}}huffnode[x1].parent=n+i; huffnode[x2].parent=n+i;huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;huffnode[n+i].lchild=x1; huffnode[n+i].rchild=x2;}}void main(){Hnodetype huffnode[maxnode];Hcodetype huffcode[maxleaf],cd;int i,j,c,p,n;printf("请输入哈夫曼树元数的个数n：\n");scanf("%d",&n); /*输入叶子节点个数*/huffmantree(huffnode,n); /*建立哈夫曼树*/for(i=0;i<n;i++) /*该循环求每个叶子节点对应字符的哈夫曼编码*/{cd.start=n-1;c=i;p=huffnode[c].parent;while(p!=-1){if(huffnode[p].lchild==c) cd.bit[cd.start]=0;else cd.bit[cd.start]=1;cd.start--;c=p; p=huffnode[c].parent;}for(j=cd.start+1;j<n;j++) /*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/huffcode[i].bit[j]=cd.bit[j]; huffcode[i].start=cd.start;}for(i=0;i<n;i++) /*输出每个叶子节点的哈夫曼编码*/{printf("第%d个哈夫曼树的元数编码为:",i+1);for(j=huffcode[i].start+1;j<n;j++)printf("%d",huffcode[i].bit[j]); printf("\n");}}五、调试过程语句“start=n-1”并未表明，应改为“cd.start=n-1”六、实验结果测试数据（1）：4个哈夫曼树的元数的权值分别为：1，2，3，4实验结果（1）：4个哈夫曼树的元数编码分别为：110，111，10，0实验截图（1）：测试数据（2）：6个哈夫曼树的元数的权值分别为：1，2，3，4，5，6实验结果（2）：6个哈夫曼树的元数编码分别为：1110，1111，110，00，01，10实验截图（2）：七、总结通过这次实验我更好地掌握了哈夫曼树，并对哈夫曼树有了深一步的了解，掌握树的有关操作算法并且熟悉树的基本存储方式，学会利用树求解实际问题。

算法与数据结构实验报告算法与数据结构实验报告1.引言该实验报告旨在介绍算法与数据结构实验的设计、实施和结果分析。

本章节将概述实验的背景和目的。

2.实验设计2.1 实验背景在本节中，我们将介绍该实验的背景和应用领域，以便读者能够更好地理解实验的重要性。

2.2 实验目的在本节中，我们将详细介绍该实验的目的和预期的成果，以便读者明确实验的研究问题和目标。

3.算法与数据结构概述3.1 算法定义在本节中，我们将简要介绍算法的概念，并讨论其在实验中的应用。

3.2 数据结构定义本节将简要介绍数据结构的概念，并说明其在算法中的作用。

4.算法实现4.1 实验环境和工具本节将介绍实验所使用的环境和工具，包括编程语言、开发平台和相关库。

4.2 算法逻辑设计在本节中，我们将详细描述所选算法的逻辑设计，包括输入、处理和输出过程。

4.3 数据结构设计本节将详细介绍所选算法中使用的数据结构设计，包括数组、链表、栈等。

4.4 算法实现步骤在本节中，我们将逐步介绍算法的实现步骤，包括代码编写和算法调试。

5.实验结果与分析5.1 实验数据收集在本节中，我们将详细介绍实验数据的收集以及所采用的评估指标。

5.2 实验结果展示本节将展示实验结果的统计数据、图表和其他可视化形式，以便读者更好地理解实验结果。

5.3 结果分析在本节中，我们将对实验结果进行分析，讨论其优势、局限性以及可能的改进方向。

6.总结与展望6.1 实验总结本节将对整个实验过程进行总结，并概括实验的主要发现和成果。

6.2 实验展望在本节中，我们将探讨实验结果的未来发展方向，并提出后续研究的建议和展望。

附件：1.数据集：包含实验中使用的原始数据集2.源代码：包含实验所编写的算法代码和实现注释：1.算法：指计算机科学中用来解决问题的可执行指令序列。

2.数据结构：指组织和存储数据的方式，以便能够高效地访问和处理。

数据结构实验报告实验名称：实验2——栈和队列1 实验目的通过选择下面五个题目之一进行实现，掌握如下内容：进一步掌握指针、模板类、异常处理的使用掌握栈的操作的实现方法掌握队列的操作的实现方法学习使用栈解决实际问题的能力学习使用队列解决实际问题的能力2 实验内容利用栈结构实现八皇后问题。

八皇后问题19世纪著名的数学家高斯于1850年提出的。

他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列、同一斜线上。

请设计算法打印所有可能的摆放方法。

提示：1、可以使用递归或非递归两种方法实现2、实现一个关键算法：判断任意两个皇后是否在同一行、同一列和同一斜线上2. 程序分析主程序：#include<iostream>using namespace std;const int StackSize=8; //皇后的个数int num=0;template <class T>class SeqStack //定义顺序栈模板类{public:SeqStack(){top=-1;} //构造函数，初始化空栈void Push(T x); //入栈操作void Pop();//出栈操作void PlaceQueen(int row); //放置皇后bool Judgement();//判断是否符合条件void Print();//输出符合条件的皇后排列bool Empty(){if(top==-1) return true;else return false;}; //判断栈是否为空private:T data[StackSize]; //定义数组int top; //栈顶指针};template <class T>void SeqStack<T>::Push(T x) //入栈操作{if(top>=StackSize-1) throw"上溢";top++;//栈顶指针上移data[top]=x;}template <class T>void SeqStack<T>::Pop()//出栈操作{if(Empty()) throw"下溢";top--;//栈顶指针下移}template <class T>bool SeqStack<T>::Judgement()//判断该位置是否合适{for(int i=0;i<top;i++)if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))//判断是否满足任意两个皇后不在同列同一斜线return false;return true;}template <class T>void SeqStack<T>::PlaceQueen(int row) //放置皇后{for (int i=0;i<StackSize;i++){Push(i); //入栈if (Judgement())//判断位置是否合适{if (row<StackSize-1)PlaceQueen(row+1); //如果合适满足条件则放置一个皇后,递归调用else{num++;//不满足条件则到下一行Print();//输出符合条件的皇后}}Pop();//出栈}}template <class T>void SeqStack<T>::Print()//输出皇后函数{cout<<"NO."<<num<<":"<<endl; for(int i=0;i<StackSize;i++){for(int j=0;j<data[i];j++){cout<<"□";}cout<<"■";for(int j=StackSize-1;j>data[i];j--){cout<<"□";}cout<<endl;}cout<<endl;}void main(){SeqStack<int> Queen;Queen.PlaceQueen(0);cout<<"总共有"<<num<<"种摆放方法。

《算法与数据结构》吴景岚王润鸿编撰闽江学院计算机实验教学中心印制目录前言 (1)实验一顺序表基本操作的实现 (2)实验二链表基本操作的实现 (4)实验三串基本操作的实现 (7)实验四二叉树基本操作的实现 (9)实验五图基本操作的实现 (12)前言《数据结构》是计算机科学与技术、软件工程等专业的专业基础必修课，主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法进行分析和评价。

本课程的学习应使学生深刻地理解数据结构的逻辑结构和物理结构的基本概念及有关算法，培养学生基本的、良好的程序设计技能以及针对具体问题，选择适当的数据结构，设计出有效算法的能力。

《数据结构》是一门理论和实践相结合的课程，它在整个计算机专业教学体系中处于举足轻重的地位，是计算机科学的算法理论基础和软件设计的技术基础，其上机实验的目的主要是编程实现数据结构各章的主要算法，训练学生实际动手进行程序设计和程序调试的能力，加深对数据结构相关概念和算法的理解。

实验一顺序表基本操作的实现专业：计算机科学系嵌入式应用班级： 2班学号： 3141101212 姓名：粟代琼实验地点：工A207 实验时间： 2015 10 15 指导教师：陈雄峰【实验课程名称】算法与数据结构【实验项目名称】顺序表基本操作的实现一、实验目的1掌握线性表顺序存储基本操作；2学会设计实验数据验证程序。

二、实验仪器及环境计算机，window xp操作系统，VC++6.0三、实验内容及步骤线性表顺序存储基本操作存储结构定义：#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量typedef struct{ElemType *elem; //存储空间基址int length；//当前长度int listsize; //当前分配的存储容量（以sizeof(ElemType)为单位）}SqList；实现的基本操作：InitList( &L )操作结果：构造一个空的线性表 L 。

《算法与数据结构》 实 验 指 导 手 册授课教师： 吴国仕教授实验指导教师： 李 晶教学对象： 二年级本科生开课时间： 秋季学期北京邮电大学软件学院2011年8月《算法与数据结构》实验指导手册（2011年8月）一． 实验一1、实验名称及学时数线性表2学时2、实验目的本次实验的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。

同时，通过本次实验帮助学生复习高级语言的使用方法。

3、实验内容必做内容1）城市链表[问题描述]将若干城市的信息，存入一个带头结点的单链表。

结点中的城市信息包括：城市名，城市的位置坐标。

要求能够利用城市名和位置坐标进行有关查找、插入、删除、更新等操作。

[基本要求]（1）创建城市链表；（2）给定一个城市名，返回其位置坐标；（3）给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。

（4）在已有的城市链表中插入一个新的城市；（5）更新城市信息；（6）删除某个城市信息。

[测试数据]由学生依据软件工程的测试技术自己确定。

注意测试边界数据。

2）约瑟夫环[问题描述]约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。

报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。

试设计一个程序求出出列顺序。

[基本要求]利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

[测试数据]m的初值为20；密码：3，1，7，2，6，8，4（正确的结果应为6，1，4，7，2，3，5）。

[实现提示]程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。

设n≤30。

选做内容1）向上述程序中添加在顺序结构上实现的部分。