数据结构实验报告
1．实验要求
（1）实验目的
通过选择下面5个题目之一进行实现，掌握如下内容：
掌握图基本操作的实现方法
了解最小生成树的思想和相关概念
了解最短路径的思想和相关概念
学习使用图解决实际问题的能力
(2)实验内容
根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。图的基本功能：
1、图的建立
2、图的销毁
3、深度优先遍历图
4、广度优先遍历图
5、使用普里姆算法生成最小生成树
6、使用克鲁斯卡尔算法生成最小生成树
7、求指定顶点到其他各顶点的最短路径
8、其他：比如连通性判断等自定义操作
编写测试main()函数测试图的正确性
2. 程序分析
存储结构
图：
(1)带权值的无向图
V0
9 6
V1 2 V2
(2)带权值的有向图
6
3 9 4
V1 2 V2关键算法分析
（1）深度优先遍历
int visited[MAXSIZE]={false};
template
void MGraph
{
c out< v isited[v]=true; f or(int j=0;j if(arc[v][j]==1&&!visited[j]) DFS(j); } 时间复杂度：O(n2) （2）广度优先遍历 int queue[MAXSIZE]; i nt f=0,r=0; c out< q ueue[++r]=v; w hile(f!=r) { v=queue[++f]; for(int j=0;j { if(arc[v][j]==1&&!visit[j]) { cout< queue[++r]=j; } 时间复杂度：O（n2） （3）普利姆算法 int adjvex[MAXSIZE]; int lowcost[MAXSIZE]; int MAX=10000; template int mininum(MGraph { i nt min=MAX; i nt k=0; f or(int i=0;i<;i++) { if(a[i]!=0&&a[i] E[k].endV=j; E[k].weight=[i][j]; k++; } for(i=0;i<;i++) { for(j=i+1;j<;j++) if(E[i].weight>E[j].weight) { VEdge t=E[i]; E[i]=E[j]; E[j]=t; } } } const int MAX_VERTEXT=20; template void MGraph { i nt vset[MAX_VERTEXT]; f or(int i=0;i int sn1=vset[m]; 程序运行结果 （1）流程图： 初始化带权值的无向图 深度优先遍历，广度优先遍历 用普利姆算法求最小生成树 用克鲁斯卡尔算法求最小生成树 初始化带权值的有向图 用Floyd算法求任意两点间最短路径，并判断连通性 删除图 （2）本程序所用的图 带权值的无向图 V0 9 6 V1 2 V2 带权值的有向图 V0 6 3 9 4 V1 2 V2 （3）程序结果 4. 总结 （1）遇到的问题：私有数据访问权的问题，在编程时应该注意 （2）心得体会：通过这次实验，我掌握了图基本操作的实现方法，了解最小生成树的思想和相关概念，了解最短路径的思想和相关概念等等。 （3）改进： 可以适当对某些步骤进行合并或省略，使程序更加简洁。 源代码： #include using namespace std; const int MAXSIZE=20; const int MAX_EDGE=20; const int MAX_VALUE=1000; struct VEdge{ i nt fromV;romV=i; E[k].endV=j; E[k].weight=[i][j]; k++; } for(i=0;i<;i++) { for(j=i+1;j<;j++) if(E[i].weight>E[j].weight) { VEdge t=E[i]; E[i]=E[j]; E[j]=t; } } } const int MAX_VERTEXT=20; template void MGraph { i nt vset[MAX_VERTEXT]; f or(int i=0;i int sn1=vset[m];//m所属的集合 int sn2=vset[n];//n所属的集合 if(sn1!=sn2) { cout<<'V'< k++; for(int i=0;i { if(vset[i]==sn2)//集合编号为sn2的全部改为sn1 vset[i]=sn1; } } j++; } } //求最短路径 //连通性判断 int dist[MAXSIZE][MAXSIZE]; int path[MAXSIZE][MAXSIZE]; template void Floyd(MGraph { f or(int i=0;i<;i++) //寻找最短路径 for(int j=0;j<;j++) { dist[i][j]=[i][j]; if(dist[i][j]!=MAX_VALUE) path[i][j]=i; else path[i][j]=-1; } for(int k=0;k<;k++) for(int i=0;i<;i++) for(int j=0;j<;j++) if(dist[i][k]+dist[k][j] { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } cout<<"任意两点间的最短路径(以矩阵表示）："< int l=1; for(int i=0;i<;i++) for(int j=0;j<;j++) { cout< l++; if(l> {cout< } } void main() { i nt v,e; c out<<"请输入顶点数(<21)和边数(<21)："; cin>>v>>e; if(v>20||v<0||e<0||e>20) cout<<"输入错误！"< c har ch[20]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r' ,'s','t'}; M Graph cout<<"请输入深度优先遍历的起始顶点下标："; int s; cin>>s; c out<<"深度优先遍历:"< (s); c out< c out<<"请输入广度优先遍历的起始顶点下标："; i nt k; c in>>k; c out<<"广度优先遍历："< (k); c out< c out<<"普利姆算法求最小生成树："< c out<<"克鲁斯卡尔算法求最小生成树："< G enSortEdge(A,EdgeList); (EdgeList,v,e); //初始化带权值的有向图 cout<<"构造带权值的有向图，请输入弧数："; i nt h; c in>>h; M Graph F loyd(B); } 数据结构实验报告 欧阳光明（2021.03.07） 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期： 2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统 计，统计每个字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编 码，并将每个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并 将编码后的字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符 串进行译码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析， 讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchildparent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 《数据结构与算法设计》 实验报告 ——实验四 学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固线性表的相关操作； 2. 熟悉VC 环境，加强编程、调试的练习； 3. 用C 语言实现线性表的抽象数据类型，实现线性表构造、插入、取数据等基本操作； 4. 理论知识与实际问题相结合，利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序， 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序，调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块，排序模块与显示输出模块。 本科实验报告 实验名称：实验三使用8251A的串行接口应用实验 课程名称：计算机原理与应用实验实验时间： 任课教师：实验地点： 实验教师： 实验类型：□原理验证■综合设计□自主创新 学生姓名： 学号/班级：组号：学院：同组搭档：专业：成绩： 1. 实验目的 1) 掌握串行通信原理及半双工和全双工的编程方法； 2) 掌握用8251A接口芯片实现微机间的同步和异步通信； 3) 掌握8251A芯片与微机的接口技术和编程方法。 2. 实验原理和内容 8251A是一种可编程的同步/异步串行通信接口芯片，具有独立的接收器和发送器，能实现单工、半双工、双工通信。 1) 8251A内部结构 8251A通过引脚D0~D7和系统数据总线直接接口，用于和CPU传递命令、数据、状态信息。读写控制逻辑用来接收CPU的控制信号、控制数据传送方向。CPU对8251A的读写操作控制表如表3-4所示。 表3-4 CPU对8251A的读写操作控制表 2) 8251A的方式控制字和命令控制字 方式控制字确定8251A的通信方式（同步/异步）、校验方式（奇校/偶校/不校）、字符长度及波特率等，格式如图3-10所示。 命令控制字使8251A处于规定的状态以准备收发数据，格式如图3-11所示。 方式控制字和命令控制字无独立的端口地址，8251A 根据写入的次序来区分。 CPU对8251A初始化时先写方式控制字，后写命令控制字。 3) 状态寄存器 8251状态寄存器用于寄存8251A的状态信息，供CPU查询，定义如图3-12所示。TXRDY位：当数据缓冲器空时置位，而TXRDY引脚只有当条件( 数据缓冲器空?/CTS?TXE)成立时才置位。 溢出错误：CPU没读走前一个字符，下一个字符又接收到，称为溢出错误。 北理工《数据结构与算法》在线作业 试卷总分：100 测试时间：-- 试卷得分：99.5 一、单选题（共40 道试题，共99.5 分。）得分：99.5 1. 下列说法正确的是() A. 堆栈是在两端操作、先进后出的线性表 B. 堆栈是在一端操作、先进后出的线性表 C. 队列是在一端操作、先进先出的线性表 D. 队列是在两端操作、后进先出的线性表 正确答案：B 满分：2.5 分得分：2.5 2. 判定一个队列Q(最多元素为m0)为满队列的条件是() A. rear-front= = m0 B. rear-front-1= =m0 C. front= =rear D. front= =rear+1 正确答案：D 满分：2.5 分得分：2.5 3. 评价排序算法好坏的标准主要是()。 A. 执行时间 B. 辅助空间 C. 算法本身的复杂度 D. 执行时间和所需的辅助空间 正确答案：D 满分：2.5 分得分：2.5 4. 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为()。 A. 3700 B. 4376 C. 3900 D. 4620 正确答案：D 满分：2.5 分得分：2.5 5. 根据二叉树的定义可知二叉树共有()种不同的形态。 A. 4 B. 5 C. 6 D. 7 正确答案：B 满分：2.5 分得分：2.5 6. 以下排序方法中，稳定的排序方法是()。 A. 直接插入排序和希尔排序 B. 直接插入排序和冒泡排序 C. 希尔排序和快速排序 D. 冒泡排序和快速排序 正确答案：B 满分：2.5 分得分：2.5 7. 下述几种排序方法中，平均查找长度最小的是()。 A. 插入排序 B. 选择排序 C. 快速排序 实验1 控制系统的模型建立 一、实验目的 1. 掌握利用MATLAB 建立控制系统模型的方法。 2. 掌握系统的各种模型表述及相互之间的转换关系。 3. 学习和掌握系统模型连接的等效变换。 二、实验原理 1. 系统模型的 MATLAB描述 系统的模型描述了系统的输入、输出变量以及内部各变量之间的关系，表征一个系统的模型有很多种，如微分方程、传递函数模型、状态空间模型等。这里主要介绍系统传递函数（TF）模型、零极点增益（ZPK）模型和状态空间（SS）模型的MATLAB 描述方法。 1）传递函数（TF）模型 传递函数是描述线性定常系统输入-输出关系的一种最常用的数学模型，其表达式一般为 在MATLAB 中，直接使用分子分母多项式的行向量表示系统，即 num = [bm, bm-1, … b1, b] den = [an, an-1, … a1, a0] 调用tf 函数可以建立传递函数TF 对象模型，调用格式如下： Gtf = tf(num,den) Tfdata 函数可以从TF 对象模型中提取分子分母多项式，调用格式如下： [num,den] = tfdata(Gtf) 返回cell 类型的分子分母多项式系数 [num,den] = tfdata(Gtf,'v') 返回向量形式的分子分母多项式系数 2）零极点增益（ZPK）模型 传递函数因式分解后可以写成 式中，z1,z2…zm称为传递函数的零点，p1,p2…pn?称为传递函的极点，k 为传递系数（系统增益）。 在MATLAB 中，直接用[z,p,k]矢量组表示系统，其中z，p，k 分别表示系统的零极点及其增益，即： z=[ z1,z2…zm]; p=[p1,p2…pn]; k=[k]; 调用zpk 函数可以创建ZPK 对象模型，调用格式如下： G= zpk(z,p,k) 同样，MATLAB 提供了zpkdata 命令用来提取系统的零极点及其增益，调用格式如下：[z,p,k] = zpkdata(Gzpk) 返回cell 类型的零极点及增益 [z,p,k] = zpkdata (Gzpk,’v’) 返回向量形式的零极点及增益 函数pzmap 可用于求取系统的零极点或绘制系统得零极点图，调用格式如下：pzmap(G) 在复平面内绘出系统模型的零极点图。 [p,z] = pzmap(G) 返回的系统零极点，不作图。 3）状态空间（SS）模型 由状态变量描述的系统模型称为状态空间模型，由状态方程和输出方程组成： 其中：x 为n 维状态向量；u 为r 维输入向量； y 为m 维输出向量； A 为n×n 方阵，称为系统矩阵； B 为n×r 矩阵，称为输入矩阵或控制矩阵；C 为m×n 矩阵，称为输出矩阵； D为m×r 矩阵，称为直接传输矩阵。 在MATLAB 中，直接用矩阵组[A,B,C,D]表示系统，调用ss 函数可以创建ZPK 对象模型，调用格式如下： Gss = ss(A,B,C,D) 同样，MATLAB 提供了ssdata 命令用来提取系统的A、B、C、D 矩阵，调用格式如下：[A,B,C,D] = ssdata (Gss) 。它返回系统模型的A、B、C、D 矩阵。 4）三种模型之间的转换 上述三种模型之间可以互相转换，MATLAB 实现方法如下 TF 模型→ZPK 模型：zpk(SYS)或tf2zp(num,den) TF 模型→SS 模型：ss(SYS)或tf2ss(num,den) ZPK 模型→TF 模型：tf(SYS)或zp2tf(z,p,k) ZPK 模型→SS 模型：ss(SYS)或zp2ss(z,p,k) SS 模型→TF 模型：tf(SYS)或ss2tf(A,B,C,D) 数据结构实验报告 实验名称：实验3——哈夫曼编码 学生姓名： 班级： 班内序号： 学号： 日期：2013年11月24日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 2. 程序分析 2.1存储结构： struct HNode { char c;//存字符内容 int weight; int lchild, rchild, parent; }; struct HCode { char data; char code[100]; }; //字符及其编码结构 class Huffman { private: HNode* huffTree; //Huffman树 HCode* HCodeTable; //Huffman编码表 public: Huffman(void); void CreateHTree(int a[], int n); //创建huffman树 void CreateCodeTable(char b[], int n); //创建编码表 void Encode(char *s, string *d); //编码 void Decode(char *s, char *d); //解码 void differ(char *,int n); char str2[100];//数组中不同的字符组成的串 int dif;//str2[]的大小 ~Huffman(void); }; 结点结构为如下所示： 三叉树的节点结构： struct HNode//哈夫曼树结点的结构体 { int weight;//结点权值 int parent;//双亲指针 int lchild;//左孩子指针 int rchild;//右孩子指针 char data;//字符 }; 示意图为： int weight int parent int lchild int rchild Char c 编码表节点结构： 北理工《实用数据结构与算法》在线作业 一、单选题： 1.（单选题）当两个元素比较出现反序时就相互交换位置的排序方法称为()。 (满分 A归并排序 B选择排序 C交换排序 D插入排序 正确:C 2.（单选题）设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为() (满分 Afront=front+1 Bfront=(front+1)%m Crear=(rear+1)%m Dfront=(front+1)%(m+1) 正确:D 3.（单选题）快速排序方法在()情况下最不利于发挥其长处。 (满分 A被排序的数据量太大 B被排序数据中含有多个相同值 C被排序数据已基本有序 D被排序数据数目为奇数 正确:C 4.（单选题）具有65个结点的完全二叉树其深度为（根的层次号为1）()。 (满分 A8 B7 C6 D5 正确: 5.（单选题）稀疏矩阵一般的压缩存储方法有两种，即()。 (满分 A二维数组和三维数组 B三元组表和散列表 C三元组表和十字链表 D散列表和十字链表 正确: 6.（单选题）从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为()排序法。 (满分:) A插入 B选择 C交换 D二路归并 正确: 7.（单选题）下列排序方法中效率最高的排序方法是()。 (满分:) A起泡排序 B堆排序 C快速排序 D直接插入排序 正确: 8.（单选题）栈与一般的线性表的区别在于()。 (满分:) A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同 MATLAB在自动控制理论中应用 实验报告 姓名： 班级： 学号： 一、实验目的 实验一 1. 掌握利用MATLAB建立控制系统模型的方法。 2. 掌握系统的各种模型表述及相互之间的转换关系。 3. 学习和掌握系统模型连接的等效变化。 实验二 1.学习和掌握利用MATLAB进行系统时域响应求解和仿真的方法。 2.考察二阶系统的时间响应，研究二阶系统参数对系统暂态特性的影响。 实验三 1.学习和掌握利用MATLAB绘制根轨迹图的方法 2.学习和掌握利用系统根轨迹图分析系统的性能。 实验四 1.学习和掌握利用MATLAB绘制系统Nyquist图和Bode图的方法。 2.学习和掌握利用系统的频率特性分析系统的性能。 一、实验原理 1)传递函数模型（TF） gtf=tf(num,den) 2)零极点增益模型（ZPK） Gzpk=zpk(z,p,k) 3)状态空间模型（SS） Gss=ss(a,b,c,d) 4)三种模型之间的转换 TF→ZPK: z pk(sys) TF→SS: ss(sys) ZPK→TF: t f(sys) ZPK→SS: s s(sys) SS→TF: tf(sys) SS→ZPK: z pk(sys) 5)绘制系统零极点图 Pzmap(gzpk); Grid on; 6)系统模型的串联 G(s)=G1(s)*G2(s) 7)系统模型的并联 G(s)=G1(s)+G2(s) 8)系统模型的反馈连接 T=feedback(G,H) T=feedback(G,H,sign) 9)绘制阶跃响应 step(sys) step(sys,T) 10)线性时不变系统仿真工具 ltiview 11)绘制系统根轨迹图 rlocus(sys) rlocus(sys,k) [r,k]=rlocus(sys) 12)计算鼠标选择点处根轨迹增益值和闭环极点值 [k,poles]=rlocfind(sys) 13)在连续系统根轨迹或零极点图上绘制出栅格线 sgrid(‘new’) sgrid(z,Wn) 14)绘制系统的Nyquist图 nyquist(SYS) nyquist(sys,w) 15)绘制系统的Bode图 bode(sys) bode(sys,w) 16)从频率响应数据中计算幅度裕度，相位裕度及对应角频率 margin(sys) [mag,phase]=bode(sys,w) 二、实验结果 东南大学能源与环境学院 实验报告 课程名称：自动控制基础 实验名称：闭环电压控制系统研究 院（系）：能源与环境学院专业：热能与动力工程 姓名：周兴学号：03011127 实验室：418 实验组别：XX 同组人员：张亚丽实验时间：2013年10月30 日评定成绩：审阅教师： 目录 一．实验目的 (3) 二．实验设备 (3) 三．实验原理 (3) 四．实验线路图 (4) 五．实验步骤 (4) 六．报告要求 (5) 七．实验结果与分析 (5) 八．思考与回答 (11) 九．实验总结 (17) 一．实验目的 （1）通过实例展示，认识自动控制系统的组成、功能及自动控制原理课程所要解决的问题； （2）学会正确实现闭环负反馈； （3）通过开、闭环实验数据说明闭环控制效果。 二．实验设备 1. THBDC-1型控制理论·计算机控制技术实验平台； 2. PC机一台(含上位机软件)、数据采集卡、37针通信线1根、16芯数据排线、采接卡接口线。 三．实验原理 （1）利用各种实际物理装置（如电子装置、机械装置、化工装置等）数学上的“相似性”，将各种实际物理装置经过简化、并抽象成数学形式。我们在设计控制系统时，不必研究每一种实际装置，而用几种“等价”的数学形式来表达、研究和设计。又由于人本身的自然属性，人对纯数学而言，不能直接感受它的自然物理属性，这给我们分析和设计带来了困难。所以，我们又用替代、模拟、仿真的形式把纯数学形式再变成“模拟实物”来研究。这样，就可以“秀才不出门，遍知天下事”。实际上，在后面的课程里，不同专业的学生将面对不同的实际物理装置，而“模拟实物”的实验方式可以举一反三，我们就是用下列“模拟实物”——电路，也有实际物理装置——电机，替代各种实际物理装置。 （2）自动控制的根本是闭环，尽管有的系统不能直接感受到它的闭环形式，如步进电机控制，专家系统等，从大局看，还是闭环。闭环控制可以带来想象不到的好处，两个演示实例说明这一点。本实验就是用开环和闭环在负载扰动下的实验数据，说明闭环控制效果。自动控制系统性能的优劣，其原因之一就是取决调节器的结构和算法的设计（本课程主要用串联校正、极点配置），本实验为了简洁，采用单闭环、比例算法K。通过实验证明：不同的统K，对系性能产生不同的影响。说明正确设计调节器算法的重要性。 （3）为了使实验有代表性，本实验采用三阶（高阶）系统。这样，当调节器K值过大时，控制系统会产生典型的现象——振荡。本实验可以认为是真实 数据结构实验报告实验名称：实验四排序（题目1） 姓名： 班级： 班内序号： 学号： 1．实验要求 实验目的：学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。实验内容：使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换 计为3次移动）。 3、对2的结果进行分析，验证上述各种算法的时间复杂度。 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 2.2 关键算法分析 2.2.1 插入排序 插入排序的基本方法是寻找一个指定元素在待排序元素中的位置，然后插入。一趟直接插入排序的C++描述过程如下： ①将待插入纪录赋值给哨兵r[0]：r[0]=r[i]; ②从后向前进行顺序查找：for(j=i-1;r[0] {r[j+1]=r[j];move++; comp++;} //循环中移动计数器++ comp++; //比较计数器++ r[j+1]=r[0];move++; //移动计数器++ } comp++; //比较计数器++ } cout<<"本次直接插入排序数据长度为："< 数据结构实验报告 实验名称：实验四——链表的排序 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 [内容要求] 使用链表实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、冒泡排序 3、快速排序 4、简单选择排序 5、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试线性表的正确性 代码要求 1、必须要有异常处理，比如删除空链表时需要抛出异常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出 2. 程序分析 2.1 存储结构 [内容要求] 存储结构：双链表 2.2 关键算法分析 [内容要求] 定义类： template 数据结构实验四 1.实验要求 置换-选择排序的实现 【问题描述】 对文件中的记录的关键字采用外部排序的置换-选择算法实现。 【实验要求】 设计置换-选择排序的模拟程序。 （1）记录存储在文件中。 （2）采用多路归并算法实现。 （3）采用置换-选择算法实现。 2实验描述 外部排序过程中，为了减少外存读写次数需要减小归并趟数（外部排序的过程中用到归并），外部排序1（其中k为归并路数，n为归并段的个数）。增加k和减小n都可以达到减小归并趟数的目的。置换-选择排序就是一种减小n的、在外部排序中创建初始归并段时用到的算法。它可以让初始归并段的长度增减，从而减小初始归并段的段数（因为总的记录数是一定的）。 置换-选择排序是在树形选择排序的基础上得来的，它的特点是：在整个排序（得到初始归并段）的过程中，选择最小（或最大）关键值和输入、输出交叉或并行进行。它的主要思路是：用败者树从已经传递到内存中的记录中找到关键值最小（或最大）的记录，然后将此记录写入外存，再将外存中一个没有排序过的记录传递到内存（因为之前那个记录写入外存后已经给它空出内存），然后再用败者树的一次调整过程找到最小关键值记录（这个调整过程中需要注意：比已经写入本初始归并段的记录关键值小的记录不能参见筛选，它要等到本初始段结束，下一个初始段中才可以进行筛选），再将此最小关键值记录调出，再调入新的记录.......依此进行指导所有记录已经排序过。内存中的记录就是所用败者树的叶子节点。开发环境：VC6.0。 3.置换-选择排序的实现 //A是从外存读入n个元素后所存放的数组 template 北理工微机实验四 实验4 A/D和D/A转换 一、实验目的 1．了解A/D转换的基本原理，掌握ADC0809芯片的使用方法。 2．了解D/A转换的基本原理，掌握DAC0832芯片的使用方法。 3．了解直流电机控制的基本方法。 二、实验内容与步骤 （一）A/D转换部分 1. 接线：CS /0809 接 Y3 /IO地址 IN0 /0809 接0~5V /直流信号 EOC 接总线的IRQ 2. 实验电路原理图如图1.通过实验台左下角电位器RW1输出0 ~ 5V 直流电压送入 ADC0809通道0（IN0），利用 debug 的输出命令启动A/D 转换器，输入命令读取转换结果，验证输入电压与转换后数字的关系。 启动IN0开始转换：OUT 298H 读取转换结果：IN 298H 图1 模数转换电路 3. 用万用表测量 CLOCK、ADD-C、ADD-B、ADD-A 在实验系统上如何联系的？ 4. 编程按中断方式采集IN0输入的电压，在屏幕上显示出转换后的数据（用16进制数）。 5. 考虑如果采用IN7输入的电压，启动开始转换和读取转换结果的地址应该是多少？ 6. 按查询方式采集IN0输入的电压，软硬件如何实现？ ● 编程提示 1. ADC0809的IN0口地址为298H. 2. IN0 单极性输入电压与转换后的数字的关系为： 其中，为输入电压，为参考电压，这里的参考电压为+5V电源。 3. 一次A/D 转换的程序可以为： MOV DX , port OUT DX , AL ;延时 IN AL , DX （二）D/A转换部分 1. 接线：CS /0832 接Y2 /IO 地址 用万用表测量WR2和XFER在实验系统上如何联系的？ 2. 实验电路原理如图2所示： 图2 DAC0832电路原理图 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验三树 ----- 哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1. 实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init):能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：禾U用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print):以直观的方式打印赫夫曼树(选作) 6计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符 一律不用编码。 2. 程序分析 2.1存储结构 Huffman 树给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径 长度最小的二叉树称为Huffman 树，也叫做最优二叉树 哈夫虽树示意图 root 孩子双亲表示法 _____________________ JL________________ weight Ichild rchild pare nt 数据结构实验报告 实验名称：实验三树——哈夫曼编/解码器 学生姓名： 班级： 班内序号： 学号： 日期：2014年12月11日 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个 字符的频度，并建立赫夫曼树 2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每 个字符的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的 字符串输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译 码，并输出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼 编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 Huffman树 给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，其中带权路径长度最小的二叉树称为Huffman树，也叫做最优二叉树。 weight lchild rchild parent 2-1-1-1 5-1-1-1 6-1-1-1 7-1-1-1 9-1-1-1 weight lchild rchild parent 2-1-15 5-1-15 6-1-16 7-1-16 9-1-17 7017 《数据结构与算法统计》 实验报告 ——实验四 学院： 班级： 学号： 姓名： 一、实验目的 1、熟悉VC 环境，学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试，加强对线性表的理解和运用的能力。 3、锻炼动手编程，独立思考的能力。 二、实验内容 从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。 (1)抽象数据类型： ADT SqList{ 数据对象：D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： InPut(SqList &L) 操作结果：构造一个线性表L 。 OutPut(SqList L) 初始条件：线性表L 已存在。 操作结果：按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件：线性表L 已存在。 操作结果：对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表，调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。 ⑶模块调用关系 数据结构实验报告 1．实验要求 (1)实验目的 通过选择下面两个题目之一，学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。 (2)实验内容 使用简单数组实现下面各种排序算法，并进行比较。 排序算法： 1、插入排序 2、希尔排序 3、冒泡排序 4、快速排序 5、简单选择排序 6、堆排序（选作） 7、归并排序（选作） 8、基数排序（选作） 9、其他 要求： 1、测试数据分成三类：正序、逆序、随机数据 2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其 中关键字交换计为3次移动）。 3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒 （选作） 4、对2和3的结果进行分析，验证上述各种算法的时间复杂度 编写测试main()函数测试排序算法的正确性。 2. 程序分析 2.1 存储结构 顺序表: 示意图： 2.2 关键算法分析 （1）测试数据的产生：正序、逆序、随机数据 用两个数组实现乱序、顺序以及逆序数据的排序。 基本思想为：随机序列产生一个指定长度的乱序序列，然后通过memcpy()函数拷贝到第 二个数组里，第二个数组作为乱序序列的保存数组，每次对第一个数组进行排序，之后拷贝第二个数组中的乱序序列到第一个数组，实现各次乱序排列。只要算法正确（第一步可以检验），之后顺序排列只需反复对第一个数组进行操作即可，再后用第二个数组保存逆序数组，然后同样在每次排序之后复制第二数组存储的乱序序列到第一组，对第一组反复排序即可。 <1> pRandom1=new long int[Max+1];pRandom2=new long int[Max+1]; <2> srand((unsigned)time(NULL)); for(int i = 1; i <= Max;i++ ) pRandom2[i]=rand(); <3> memcpy(obj.pRandom1,obj.pRandom2,(Max+1)*sizeof(long int)); （2）排序算法： <1>插入排序：依次将待排序的序列中的每一个记录插入到先前排序好的序列中，直到全部记录排序完毕。 /1/int j=0; /2/ for(int i =2; i <= Max;i++) parray[0]=parray[i];comparetimes[0]++; /4/parray[j+1]=parray[0];movetimes[0]+=2; 示意图： r1,r2,r3,…,ri-1,ri,ri+1,…,rn 有序区待插入无序区 <2>希尔排序：先将整个序列分割成若干个子列，分别在各个子列中运用直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序。 int Sort::ShellSort(long int parray[]) {int j=0; for(int d=Max/2;d>=1;d/=2) {for(int i=d+1;i<=Max;i++) { parray[0]=parray[i]; comparetimes[1]++; for(j=i-d;j>0 && parray[0] 第四次实验 第一部分线性控制系 统的频域分析 一．实验目的： 一、实验目的 1) 了解线性系统频率特性的基本概念。 2) 了解和掌握对数幅频曲线和相频曲线（伯德图）的构造及绘制方法。 3) 了解和掌握利用频率法建模的方法、步骤和基本原理。 4) 掌握二阶开环系统的对数幅频特性L(ω)和相频特性φ(ω)，实频特性Re(ω)和虚频特性Im(ω)的计算方法。 5) 了解和掌握欠阻尼Ⅰ型二阶闭环系统中的自然频率Wn、阻尼比ζ对谐振频率Wr和谐振峰值L(Wr)的影响，及Wr和L(Wr)的计算方法。 6) 了解阻尼比ζ对开环参数幅值穿越频率Wc和相位裕度γ的影响及幅值穿越频率Wc和相位裕度γ的计算方法。 7) 了解和掌握Ⅰ型二阶闭环系统对数幅频曲线和相频曲线和幅相曲线的构造方法。 二、实验原理 对于稳定的线性系统，当输入为正弦信号时，其输出也是一个正弦信号，频率和输出信号的频率相同，但幅值和相角发生了变化。其幅值和相角只与系统参数及输入正弦函数的频率有关，即每改变一次角频率，都将得到一个幅值比和相位差，这两个值分别属于频率特性中的幅频特性和相频特性曲线上的两个点。不断改变角频率，所测得的一组值构成了频率特性。对一般系统，输入为 x(t)=Xsin(wt+) t->∞时：输出为 y(t)=Ysin(wt+) 幅值比为A=，记A(w)幅频特性，相角差为φ= ?，φ(w)为相频特性。 频域分析法是应用频率特性研究线性系统的一种经典方法。它以控制系统的频率特性作为数学模型，以伯德图或其他图表作为分析工具，来研究和分析控制系统的动态。 三．实验内容及步骤 二阶闭环系统的频率特性测试电路如图 （1）按模拟电路连接电路 （2）描绘系统的闭环对数幅频、相频 特性曲线。 用MATLAB画出该二阶闭环系统的伯德图进行对比。 程序如下： num=25; den=[0.1,1,25]; sys=tf(num,den); margin(sys) [gm,pm,wcg,wcp]=margin(sys ) 所得的结果如图所示：北邮信通院数据结构实验报告三哈夫曼编码器之欧阳光明创编
北京理工大学《数据结构与算法设计》实验报告实验四
北理工微机原理实验三 使用8251A的串行接口应用实验
北理工《数据结构与算法》在线作业_2
北京理工大学自动控制实验报告模板
北邮数据结构实验3哈夫曼编码
北理工《实用数据结构与算法》在线作业
北理工_自动控制理论matlab实验
自控实验三
北邮数据结构第四次实验题目一排序
北邮数据结构实验四-链表排序
数据结构实验四
北理工微机实验四
北邮信通院数据结构实验报告三哈夫曼编码器
北邮信通院数据结构实验报告三哈夫曼编码器
北京理工大学数据结构实验报告4
北邮数据结构实验 第三次实验 排序
北京理工大学自动控制理论实验报告4
相关主题
文本预览