2014下《数据结构》复习提纲
第1章绪论
有关术语；算法、算法复杂度的分析和计算方法
例题：
1．下面算法的时间复杂度为O( n )。
int f( unsigned int n ){
if ( n = = 0 || n = = 1 ) return 1;
else returen n *f ( n – 1 ); }
2．for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}时间复杂度为O(n2)
第2-3章线性表，栈和队列
线性表的概念、存储结构、插入与删除操作；栈和队列的概念，理解栈顶指针、队首、队尾指针的意义和作用，特别是循环队列的头、尾指针的设置。为什么要这样设置。它们基本操作的实现。判空和判满？了解有关应用。
例题：
1．在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p 之间插入一个s所指的结点,则执行的语句？（答：q->next=s; s->next=p）；注意在某个已知结点前插需要执行的语句？
2．注意循环（链）队列的判空和判满的条件？（看书理解！）
3．对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为 O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n)。
4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 (rear+l)％n= = front。
执行出队操作后其头指针front如何
5. 线性表采用链式存储时，结点的存储地址连续与否均可;
6. 链式栈删除栈顶元素的操作序列为top=top->next.
7.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是p->next=p->next->next.
8.判定“带头结点的链队列为空”的条件是Q.front==Q.rear.
9. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。则队满的条件表达式为quelen == m；队空的条件表达式quelen == 0；队头元素位置的表达式( rear - quelen + m ) % m
第6章树和二叉树
树和二叉树的定义、完全二叉树及其性质、存储表示及遍历算法（递归和非递归）、哈夫曼树的概念。
例题：
1．在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加1 ）;对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着。
2. n 个权构成一棵Huffman树，其节点总数为2n-1.
3. 设用权6，10，13，14，20，37构造Huffman树，则该Huffman树的根结点的权值为100. （仔细验算构造Huffman树）
4. 一棵深度为k的满二叉树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1，最大值为2k-1。
5. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树.
6.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDECF ，中序遍历序列为DBEAFC ，后序遍历序列为DEBFCA.
7. 一棵完全二叉树中共有768结点，则该树中共有384个叶子结点。
8. 深度为k的完全二叉树中最少有2k-1个结点。
9. 二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是任一结点无右孩子
第7章图
图的存储及遍历算法，图的有关概念，最短路径,（最小）生成树例题：
1．由一个具有n个顶点的连通图生成的最小生成树中，具有n-1条边。2．有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入度。
3. 若要把n个顶点连接为一个连通图，则至少需要n-1 条边。
4.连通图G中有n个顶点e条边，则对应的最小生成树上有n-1条边5．在一个图中，所有顶点的度数之和等于所有边数的 2 倍。
6.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。
7.无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为O(n2); 用邻接表作为图的存储上述复杂度O(n+e).
8.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为n2－2e.
9.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为d=e.
10. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=d/2
11.掌握最小生成树算法.例如使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，画出各步的结果。
12.已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其他顶点的最短距
1. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为4。
2. 有序表中进行二分查找，则比较一次查找成功的结点数有1个，比较两次查找成功有结点数有2个,比较三次……
3．理解并掌握二叉排序树的概念，会构造二叉排序树及查找、插入和删除操作。
4.中序遍历二叉排序树可以得到一个从小到大的有序序列。
5. 设哈希表HT表长m为13，哈希函数为H(k)=k MOD m，给定的关键值序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。
(1)表形态：
(2)平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.6
6.设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是19/
7.
第10章内部排序
掌握基本排序方法的实现思想。
例题：
1. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为3。
2．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是42，40，55，60，80，85
考试题型：
一.单项选择题（15×2分=30分）
二.填空题（10×2分=20分）
1.实现数据x进栈程序填空；
2. 二叉树中各类结点个数及关系；
3. 关于无向图的度；
4. 无向图邻接矩阵中找邻接点；
5.二叉树遍历;
6.顺序循环队列元素个数;
7. 二叉排序树平均查找长度;
8. 哈夫曼树构造和哈夫曼树的高度;
9.最小生成树构造及其上权值之和; 10. 二叉排序树中插入一个新结点算法填空。
三.解答题（5×6分=30分）
1．循环队列在特定设置下判满判空,计算元素位置；2. 给出邻接矩阵,画出该图,画出深度优先生成树；3. 填写出散列表和平均查找长度; 4. 求某顶点到其余各顶点的最短路径; 5.构造一棵二叉排序树, 画出删去结点之后的二叉排序树.
四.算法阅读题（2×6分=12分）
1.在带头结点的单链表中，删除数据元素的算法;
2.中序遍历二叉树过程中实现对一些节点的其他操作.
五、算法设计题（8分）
1. 将一个简单的递归程序改写成非递归,实现相同功能.
以上各例题中的答案并不保证完全正确，希望自己亲自验证。找到并对照书本上的相应内容仔细阅读3遍以上。切实理解和掌握每个知识点的实质，决不可以似是而非，侥幸过关。
祝同学们考出好成绩！
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 ．实验目的 （1 ）掌握使用Visual C++ 6.0 上机调试程序的基本方法； （2 ）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 ．实验要求 （1 ）认真阅读和掌握和本实验相关的教材内容。 （2 ）认真阅读和掌握本章相关内容的程序。 （3 ）上机运行程序。 （4 ）保存和打印出程序的运行结果，并结合程序进行分析。 （5 ）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表，由用户输入各结点data 域之值， // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 山东建筑大学测绘地理信息学院 实验报告 （2016—2017学年第一学期） 课程：计算机图形学 专业：地理信息科学 班级：地信141 学生姓名：王俊凝 学号：20140113010 指 实验一直线生成算法设计 一、实验目的 掌握基本图形元素直线的生成算法，利用编程语言C分别实现直线和圆的绘制算法。 二、实验任务 在TurboC环境下开发出绘制直线和圆的程序。 三、实验仪器设备 计算机。 四、实验方法与步骤 1 运行TurboC编程环境。 2 编写Bresenham直线绘制算法的函数并进行测试。 3 编写中点圆绘制算法的函数并进行测试。 4 增加函数参数，实现直线颜色的设置。 提示： 1. 编程时可分别针对直线和圆的绘制算法，设计相应的函数，例如void drawline(…)和void drawcircle(…)，直线的两个端点可作为drawline的参数，圆的圆心和半径可作为drawcircle的参数。 2. 使用C语言编写一个结构体类型用来表示一个点，结构体由两个成员构成，x和y。这样，在向函数传入参数时，可使用两个点类型来传参。定义方法为： typedef struct{ int x; int y; }pt2; 此处，pt2就是定义的一个新的结构体数据类型，之后就可用pt2来定义其他变量，具体用法见程序模板。 3. 在main函数中，分别调用以上函数，并传入不同的参数，实现对直线的绘制。 4. 线的颜色也可作为参数传入，参数可采用TurboC语言中的预设颜色值，具体参见TurboC图形函数。 五、注意事项 1 代码要求正确运行，直线和圆的位置应当为参数，实现可配置。 2 程序提交.c源文件，函数前和关键代码中增加注释。 程序模板 #include 数据结构应用设计设计报告题目名称：___基于哈夫曼编码的文件压缩器_ 设计环境：____ __ＶＣ6.0 ____________ 指导教师：_____ _蔡茂蓉______________ 专业班级：______软件工程0601班__ ___ 姓名：__ _ __杨文辉_____________ 学号：___ ____ _____ 联系电话：_ _ 电子邮件： 设计日期：年月日至年月日 设计报告日期：年月日 1 ．题目................................................................................................... 错误!未定义书签。 2 ．需求分析........................................................................................... 错误!未定义书签。 2.1文件压缩过程：......................................................................... 错误!未定义书签。 2.2文件解压过程：......................................................................... 错误!未定义书签。 2.3压缩文件的存储结构设计图：................................................. 错误!未定义书签。 2.4ＨＡＦ文件示例：...................................................................... 错误!未定义书签。 3 ．详细设计........................................................................................... 错误!未定义书签。 3.1压缩流程图：............................................................................. 错误!未定义书签。 3.2解压流程图：............................................................................. 错误!未定义书签。 3.3节点类设计：............................................................................. 错误!未定义书签。 3.4编码和译码时的控制结构的实现............................................. 错误!未定义书签。 ４．调试分析........................................................................................... 错误!未定义书签。 6 ．测试结果........................................................................................... 错误!未定义书签。 6.1文件压缩..................................................................................... 错误!未定义书签。 6.2文件解压..................................................................................... 错误!未定义书签。 ７．实验总结........................................................................................... 错误!未定义书签。 8 ．参考文献........................................................................................... 错误!未定义书签。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 《建筑结构试验》实验报告 班级： 学号： 姓名： 南昌航空大学土木工程试验中心 二○一○年四月 目录 试验一电阻应变片的粘贴及防潮技术试验二静态电阻应变仪的使用及接桥试验三电阻应变片灵敏系数的测定 试验四简支钢筋混凝土梁的破坏试验 试验一电阻应变片的粘贴及防潮技术 姓名：学号：星期第讲第组 实验日期：年月日同组者： 一、实验目的： 1.掌握电阻应变片的选用原则和方法； 2.学习常温用电阻应变片的粘贴方法及过程； 3.学会防潮层的制作； 4.认识并理解粘贴过程中涉及到的各种技术及要求对应变测试工作的影响。 二、实验仪表和器材： 1.模拟试件（小钢板）； 2.常温用电阻应变片； 3.数字万用表； 4.兆欧表； 5.粘合剂：T-1型502胶，CH31双管胶（环氧树脂）或硅橡胶； 6.丙酮浸泡的棉球； 7.镊子、划针、砂纸、锉刀、刮刀、塑料薄膜、胶带纸、电烙铁、焊锡、焊锡膏等小工具； 8.接线柱、短引线 三、简述整个操作过程及注意事项： 1.分选应变片。在应变片灵敏数K相同的一批应变片中，剔除电阻丝栅有形状缺陷，片内有气泡、霉斑、锈点等缺陷的应变片，将电阻值在120±2Ω范围内的应变片选出待用。 2.试件表面处理。去除贴片位置的油污、漆层、锈迹、电镀层，用丙酮棉球将贴片处擦洗干净，至棉球洁白为止，以保证应变片能够牢固的粘贴在试件表面。 3.测点定位。应变片必须准确地粘贴在结构或试件的应变测点上，而且粘贴方向必须是要测量的应变方向。 4.应变片粘贴。注意分清应变片的正、反面，保证电阻栅的中心与十字交叉点对准。应变片贴好后，先检查有无气泡、翘曲、脱胶等现象，再用数字万用表的电阻档检查应变片有无短路、断路和阻值发生突变(因应变片粘贴不平整导致)的现象。 5.导线固定。接线柱粘帖不要离应变片太远，接线柱挂锡不可太多，导线挂锡一端的裸露线芯不能过长，以31mm为宜。引出线不要拉得太紧，以免试件受到拉力作用后，接线柱与应变片之间距离增加，使引出线先被拉断，造成断路；也不能过松，以避免两引出线互碰 数据结构课程设计图的应用个人报告 1979:Red and Black 第一、题目理解 有一个长方形的房间，覆盖平方米瓷砖。每一层的颜色或是红色或黑色。一名男子正站在一个黑色的瓷砖。从瓷砖，他可以转移到四个相邻瓷砖。但是他不能进入红色瓷砖，他只能移动黑砖。写程序的数量黑色瓦片，他可以达到通过重复上述动作。 题目要求只能走黑格子而不能走红格子，从其中一块黑格子开始求出可以到达的黑格子数。 第二、算法思想 用图的深度优先遍历可以解决问题，从开始的位置探索四个方向的格子，用递归直到走完所有黑格子。 建图结构，图的每一个顶点表示瓦片，如果两个相邻顶点都表示黑瓦，则在两个顶点间连线，表示可以从一片黑瓦移到另一片上；对建好的图从给定的起始点开始调用深度优先遍历算法，能访问几个顶点表示重复移动能达到的黑瓦的数目. 第三、如何实现 用一个二维数组来表示房间格子的分布。用变量count来记录可行黑格子的个数。用深度优先遍历算法来遍历整个二维数组。 search(int k,int t){ // Search函数,递归调用. if(k>=0 && k 1915: Knight Moves 第一、题目理解 题目要求要计算国际象棋中骑士从一个指定位置到目的位置的最少步数。因为每一次都有八种走法，要把可行的走法记录下来，直到走到终点为止。输出最少的步数。 第二、算法思想 此问题可利用广度优先遍历算法，用一个数组来记录可行的走法，然后再用另一个数组来记录数组中的每一种情况的可行走法，重复以上步骤，当终点出现在第n数组中则结束。数组的数量n就是最小的步数。 第三、如何实现 数据结构： typedef struct { //定义顶点的结构 int x, y; int direction; }VRType; typedef struct { int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int length; }MGraph; typedef VRType QElemType; //队列定义 #define MAXQSIZE 1000 typedef struct { QElemType *base; int front; int rear; }SqQueue; 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 算法与数据结构课程设计 报告 系（院）：计算机科学学院 专业班级：计科11005 姓名：张林峰 学号： 201003784 指导教师：詹泽梅 设计时间：2012.6.11 - 2012.6.18 设计地点：12教机房 目录 一、课程设计目的 (2) 二、设计任务及要求 (2) 三、需求分析 (2) 四、总体设计 .............. 错误！未定义书签。 五、详细设计与实现[含代码和实现界面].. 8 六、课程设计小结 (15) 一．设计目的 1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力。二．设计任务及要求 根据《算法与数据结构》课程的结构体系，设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。比如，主界面是大项，主要是学过的各章的名字诸如线性表、栈与队列、串与数组及广义表等，子菜单这些章中的节或者子节。要求所有子菜单退出到他的父菜单。编程实现时，要用到C++的面向对象的功能。 三．需求分析 菜单运用极其广泛，应用于各行各业。菜单运用起来极其方便。随着社会的发展，社会的行业出现多样化，也就需要各式 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 《数据结构》实验报告 实验序号：4 实验项目名称：栈的操作 附源程序清单： 1. #include { return false; } else { st->top++; //移动栈顶位置 st->data[st->top]=x; //元素进栈 } return true; } bool Pop(SqStack *st,ElemType &e) //出栈 { if(st->top==-1) { return false; } else { e=st->data[st->top]; //元素出栈 st->top--; //移动栈顶位置} return true; } //函数名：Pushs //功能：数组入栈 //参数：st栈名,a->数组名，i->数组个数 bool Pushs(SqStack *st,ElemType *a,int i) { int n=0; for(;n 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 课程实验报告课程名称：数据结构 专业班级：信安1302 学号： 姓名： 指导教师： 报告日期：2015. 5. 12 计算机科学与技术学院 目录 1 课程实验概述............ 错误!未定义书签。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 ...................................................... 错误!未定义书签。 2.2 系统设计 ...................................................... 错误!未定义书签。 2.3 系统实现 ...................................................... 错误!未定义书签。 2.4 效率分析 ...................................................... 错误!未定义书签。 3 实验二基于链式结构的线性表实现 3.1 问题描述 ...................................................... 错误!未定义书签。 3.2 系统设计 ...................................................... 错误!未定义书签。 3.3 系统实现 ...................................................... 错误!未定义书签。 3.4 效率分析 ...................................................... 错误!未定义书签。 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 ...................................................... 错误!未定义书签。 4.2 系统设计 ...................................................... 错误!未定义书签。 4.3 系统实现 ...................................................... 错误!未定义书签。 4.4 效率分析 ...................................................... 错误!未定义书签。 5 实验总结与评价 ........... 错误!未定义书签。 1 课程实验概述 这门课是为了让学生了解和熟练应用C语言进行编程和对数据结构进一步深入了解的延续。 实验一静态应变测量原理 在电阻应测量中，如在电桥中仅接入一个电阻应变片，则实际测量值中含有由于温度变化时构件产生的应变，这是实验中所不希望的，通过适当的接线方式，可消除温度的影响，在课本中有许多不同的接线方式，主要分为两大类，一是设置专门温度补偿片，这种方式又可分为公共补偿与单片补偿两种，二是通过工作片间互相补偿，称为互相补偿或自补偿，接线要有一定的技巧。掌握电阻应变测量中的温度补偿方式及不同接线方式的测量结果的区别是很重要的。 一、实验目的 1、熟悉电阻应变仪的操作规程； 2、掌握电阻应变仪测量的基本原理； 3、学会用电阻应变片作半桥测量的方法； 4、掌握温度补偿的基本原理。 二、实验设备及仪表 1、DH3819型静态电阻应变仪； 2、等强度梁； 3、电阻应变片，导线。 三、实验内容 进行两种电阻应变测量接线方法的实验，掌握电阻应变测量的不同接线基本原理，以及消除温度影响的方法，根据实验结果分析两种接线不同测量数值理论依据。 四、试验方法 1、1/4桥接线+公共补偿： 单片补偿接线方法：将应变片R1接于应变仪1组，Eg、接线柱，温度补偿片R2接于、0接线柱，则构成外半桥，另内半桥由应变仪内部两个标准电阻构成。输入应变片灵敏度系数，导线电阻，应变片电阻。 公共补偿接线方法：断开补偿组的连线，将公共补偿接线连接于该组，将等强度梁的上侧应变片R1接于1组的Eg、接线柱，将等强度梁下侧应变片R3接、0接线柱。 2、半桥接线 按应变仪的设计原理更换公共补偿端的接线方式，然后在每个测量桥路中接入两个电阻应变片。本试验中，在一个测量桥路中按半桥方式接入等强度梁的上下测应变片。 五、实验步骤 1、接上述接桥方法分别接通桥路； 2、将电阻应变仪调平衡； 3、作预加载1公斤，检查仪表和装置； 4、正式试验，每级加载1公斤，加三级，记取读数，重复三次。 六、试验报告 1、实验方案； 2、实验过程； 3、整理出实验数据，试验数据填入应变记录表。（表格见下表） 4、比较两种接线方法，分析原因，给出结论。 5、写出试验操作方法和体会。 6、回答后面的思考题。 编号：XH03JW024-05/0 实训（验）报告 班级：姓名：座号：指导教师：成绩： 课程名称：算法与数据结构实训（验）：实验六图的应用2011年12月9 日 一、实验目的： 1、掌握图的两种存储结构； 2、掌握图深度优先遍历的基本思想； 3、掌握图广度优先遍历的基本思想。 二、实训（验）内容、记录和结果（含数据、图表、计算、结果分析等） 1、程序源代码： // (以下为邻接表的队操作) void init1(linkqueue *q) { q->front=q->rear=(queue)malloc(sizeof(node)); q->front->next=NULL; } void ENQUEUE1(linkqueue *q, int v) { queue P; P=(queue)malloc(sizeof(node)); P->data=ga[v].vertex; P->next=NULL; q->rear->next=P; q->rear=P; } int DEQUEUE(linkqueue *q) { int k=0,u; queue P; P=q->front->next; while(ga[k].vertex!=P->data) k++; u=k; q->front->next=P->next; if(q->rear==P) q->rear=q->front; return u; } int isempty1(linkqueue *q) { if(q->front==q->rear) return 1; else return 0; } void CREATADJLIST(VerNode ga[]) /*建立无向图的邻接表*/ { int i,j,k; EdgeNode *s; getchar(); for(i=0;i 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template { int i, j, k; vertexNum = n, arcNum = e; for(i = 0; i < vertexNum; i++) vertex[i] = a[i]; for(i = 0;i < vertexNum; i++) for(j = 0; j < vertexNum; j++) arc[i][j] = 0; for(k = 0; k < arcNum; k++) { cout << "Please enter two vertexs number of edge: "; cin >> i >> j; arc[i][j] = 1; arc[j][i] = 1; } } template(完整版)数据结构实验报告全集
图形学实验报告
数据结构应用设计设计报告
数据结构实验十一：图实验
《建筑结构试验》实验报告
数据结构图的应用报告
数据结构实验---图的储存与遍历
数据结构课程设计报告,含菜单
数据结构实验报告图实验
《数据结构》实验报告
数据结构线性表的应用实验报告
数据结构实验
数据结构课程实验报告(15)
工程结构试验与检测实验报告
算法与数据结构图的应用实验报告
数据结构实验报告--图实验
相关主题
文本预览