. . .. . .
算法设计与分析
实验指导书
东北大学软件学院
2012年
.. .专业. .
目录
算法设计与分析 (1)
实验指导书 (1)
前言 (3)
实验要求 (4)
实验1 分治法的应用（2学时） (5)
1.实验目的 (5)
2.实验类型 (5)
3.预习要求 (5)
4.实验基本要求 (5)
5.实验基本步骤 (7)
实验2动态规划（2学时） (9)
1.实验目的 (9)
2.实验类型 (9)
3.预习要求 (9)
4.实验基本要求 (9)
5.实验基本步骤 (10)
实验3 回溯法（4学时） (12)
1.实验目的 (12)
2.实验类型 (12)
3.预习要求 (12)
4.实验基本要求 (12)
5.实验基本步骤 (13)
前言
《算法设计与分析》是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习，使学生理解和掌握计算机算法的通用设计方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定基础。
要求掌握算法复杂度分析、分治法、动态规划法、贪心法、回溯法、分支限界法等算法的设计方法及其分析方法。能将这些方法灵活的应用到相应的问题中，并且能够用C++实现所涉及的算法，并尽量做到低复杂度，高效率。
通过本课程的实验，使学生加深对课程容的理解，培养学生严密的思维能力，运用所学知识结合具体问题设计适用的算法的能力；培养学生良好的设计风格，激励学生创造新算法和改进旧算法的愿望和热情。希望同学们能够充分利用实验条件，认真完成实验，从实验中得到应有的锻炼和培养。
希望同学们在使用本实验指导书及进行实验的过程中，能够帮助我们不断地发现问题，并提出建议，使《算法设计与分析》课程成为对大家有益的课程。
实验要求
《算法设计与分析》课程实验的目的是为了使学生在课堂学习的同时，通过一系列的实验，使学生加深理解和更好地掌握《算法设计与分析》课程教学大纲要求的容。
在《算法设计与分析》的课程实验过程中，要求学生做到：
（1）仔细观察调试程序过程中出现的各种问题，记录主要问题，做出必要说明和分析。
（2）认真书写实验报告。实验报告模板见附录1。
（3）遵守机房纪律，服从辅导教师指挥，爱护实验设备。
（4）实验课程不迟到。如有事不能出席，所缺实验一般不补。
（5）本实验采用的开发环境为Microsoft Visual C++ 6.0，同学在做实验之前要求熟悉该软件的使用方法。
（6）实验成绩主要从以下几方面考核：实验过程态度，实验结果及报告书写。
实验1 分治法的应用（2学时）
1.实验目的
（1）理解分治法的思想。
（2）掌握用分治法解决问题
2.实验类型
设计型
3.预习要求
熟悉Visual C++ 6.0上机编程调试的基本方法。掌握教材上分治法的思想，掌握各种排序方法及二分搜索的思想。
4.实验基本要求
（1）仔细阅读备选实验的题目，选择一个（可选多个）作为此次实验题目，设计的程序要满足正确性，代码中有关键的注释，书写格式清晰，简洁易懂，效率较高，利用C＋＋的模板，设计的程序通用性好，适合各种合理输入，并能对不合理输入做出正确的提示。
（2）可供选择的题目有以下3个：
中位数问题
★问题描述
设X[ 0 : n - 1]和Y[ 0 : n– 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。
★编程任务
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。
★数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。
★结果输出
程序运行结束时，将计算出的中位数输出到文件output.txt中。
输入文件示例输出文件示例
input.txt output.txt
14
3
5 15 18
3 1
4 21
★实现提示
比较两个序列的中位数大小，如果两个数相等，则该数为整个2n个数据的中位数，否则通过比较，分别减少两个序列的查找围，确定查找的起止位置，继续查找。
（ii）Gray码问题
★问题描述
Gray码是一个长度为2n的序列。序列中无相同的元素，每个元素都是长度为n位的串，相邻元素恰好只有一位不同。用分治策略设计一个算法对任意的n构造相应的Gray码。
★编程任务
利用分治策略试设计一个算法对任意的n构造相应的Gray码。
★数据输入
由文件input.txt提供输入数据n。
★结果输出
程序运行结束时，将得到的所有编码输出到文件output.txt中。
输入文件示例输出文件示例
input.txt output.txt
3 000
100
101
010
011
111
101
001
★实现提示
把原问题分解为两个子问题，分别对两个子问题的每个数组后一位加0和1。
（iii）归并排序
★问题描述
目前的网上拍卖系统会显示很多待拍卖的物品，通常这些系统具有按照某个关键字对打出的广告进行排序列出的功能，并且能够按照用户输入的某个关键字进行过虑，找到某些特定的物品。★编程任务
定义一个Advertisement类，该类中至少包含该物品的数量，名称，联系人，最好有开拍时间及关闭时间，根据用户输入的关键字比如名称，mail，时间等，利用非递归的归并排序对所有的广告进行排序，并列出所有排好序的广告。
★数据输入
由文件input.txt提供输入的所有广告信息。程序中由用户输入要排序的关键字。
★结果输出
程序运行结束时，排好序的广告输出到文件output.txt中，并为每个广告添加序号。
输入文件示例输出文件示例
input.txt output.txt
Coat(物品名称) 1
3（数量）
amail.
Skirt
5
bmail.
Cap
7
cmail.
Bag
12
amail.
Title（用户输入按照title排序）
Bag
12
amail.
2
Cap
7
cmail.
3
Coat(物品名称) 3（数量）amail.
4
Skirt
5
bmail.
（3）按照指定的格式书写实验报告，实验报告清晰，但不赘述，字体最大为四号。在实验结束一周上交实验报告。
5.实验基本步骤
（1）选定实验题目，仔细阅读实验要求，设计好输入输出，按照分治法的思想构思算法，选取合适的存储结构实现应用的操作。
（2）设计的结果应在Visual C++ 实验环境下实现并进行调试。
（3）实验要有详细的测试记录，包括各种可能的测试数据。
实验报告
课程名称：算法设计与分析班级：软件1304实验成绩：
实验名称：分治策略学号：20134726 批阅教师签字：
实验编号：实验一：航实验日期：2016年1月 1 日
指导教师：莉组号：实验时间：时分－时分
一、实验目的
理解分治法的思想。
掌握用分治法解决问题
二、实验容
中位数问题
★问题描述
设X[ 0 : n - 1]和Y[ 0 : n– 1 ]为两个数组，每个数组中含有n个已排好序的数。找出X和Y的2n个数的中位数。
★编程任务
利用分治策略试设计一个O (log n)时间的算法求出这2n个数的中位数。
★数据输入
由文件input.txt提供输入数据。文件的第1行中有1个正整数n（n<=200），表示每个数组有n个数。接下来的两行分别是X，Y数组的元素。
三、实验环境
WINDOWS7家庭版
DEVC++
四、问题分析
（1）分析要解决的问题，给出你的思路，可以借助图表等辅助表达。
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和
y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索围,然后再分别取两个子
数列的中位数再比较,再减少搜索围,继续下去直到找到最后结果
（2）分析利用你的想法解决该问题可能会有怎样的时空复杂度。
O（n）
（3）其它（你认为需要在此说明的）
五、问题解决
（1）根据对问题的分析，写出解决办法。
设两个长度为n的数列分别为x[ 0 : n -1]和y[ 0 : n -1],分别找出这两个数列的中位数x[i]和
y[ j ],二者进行比较,根据比较结果可以在每个数列中减少一半的搜索围,然后再分别取两个子
数列的中位数再比较,再减少搜索围,继续下去直到找到最后结果
（2）描述你在进行实现时，主要的函数或操作部的主要算法；分析这个算法的时、空复杂度，并
C语言程序设计实验报告 实验一：链表的基本操作一·实验目的 1.掌握链表的建立方法 2.掌握链表中节点的查找与删除 3.掌握输出链表节点的方法 4.掌握链表节点排序的一种方法 5.掌握C语言创建菜单的方法 6.掌握结构化程序设计的方法 二·实验环境 1.硬件环境：当前所有电脑硬件环境均支持 2.软件环境：Visual C++6.0 三.函数功能 1. CreateList // 声明创建链表函数 2.TraverseList // 声明遍历链表函数 3. InsertList // 声明链表插入函数 4.DeleteTheList // 声明删除整个链表函数 5. FindList // 声明链表查询函数 四．程序流程图 五．程序代码 #include
r=head;//r指向头结点 printf("输入数字:\n"); for(i=n;i>0;i--)//for 循环用于生成第一个节点并读入数据{ scanf("%d",&x); p=(node *)malloc(sizeof(node)); p->data=x;//读入第一个节点的数据 r->next=p;//把第一个节点连在头结点的后面 r=p;//循环以便于生成第二个节点 } r->next=0;//生成链表后的断开符 return head;//返回头指针 } void output (linklist head)//输出链表 { linklist p; p=head->next; do { printf("%3d",p->data); p=p->next; } while(p); printf("\n") } Status insert ( linklist &l,int i, Elemtype e)//插入操作 { int j=0; linklist p=l,s; while(j
《数据结构》实验报告 1、实验名称:设计循环单链表 2、实验日期: 2013-3-26 3、基本要求： 1）循环单链表的操作，包括初始化、求数据元素个数、插入、删除、取数据元素； 2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。 4、测试数据： 依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出数据元素。 5、算法思想或算法步骤: 主函数主要是在带头结点的循环单链表中删除第i个结点，其主要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。 6、模块划分： 1）头文件LinList.h。头文件LinList.h中包括：结点结构体定义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作； 2）实现文件dlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。
7、数据结构： 链表中的结点的结构体定义如下： typedef struct Node { DataType data; struct Node *next; }SLNode; 8、源程序： 源程序存放在两个文件中，即头文件LinList.h和实现文件dlb.cpp。//头文件LinList.h typedef struct Node { DataType data; struct Node *next; }SLNode; void ListInitiate(SLNode **head) //初始化 { *head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; }
矿压测试技术实验指导书 学号： 班级： 姓名： 安徽理工大学 能源与安全学院采矿工程实验室
实验一常用矿山压力仪器原理及使用方法 第一部分观测岩层移动的部分仪器 ☆深基点钻孔多点位移计 一、结构简介 深基点钻孔多点位移计是监测巷道在掘进和受采动影响的整个服务期间，围岩内部变形随时间变化情况的一种仪器。 深基点钻孔多点位移包括孔内固定装置、孔中连接钢丝绳、孔口测读装置组成。每套位移计内有5~6个测点。其结构及其安装如图1所示。 二、安装方法 1.在巷道两帮及顶板各钻出φ32的钻孔。 2.将带有连接钢丝绳的孔内固定装置，由远及近分别用安装圆管将其推至所要求的深度。(每个钻孔布置5~6个测点，分别为；6m、5m、4m、3m、2m、lm或12m、10m、8m、6m、4m、2m)。 3.将孔口测读装置，用水泥药圈或木条固定在孔口。 4。拉紧每个测点的钢丝绳，将孔口测读装置上的测尺推至l00mm左右的位置后，由螺丝将钢丝绳与测尺固定在一起。 三、测试方法 安装后先读出每个测点的初读数，以后每次读得的数值与初读数之差，即为测点的位移值。当读数将到零刻度时，松开螺丝，使测尺再回到l00mm左右的位置，重新读出初读数。 ☆顶板离层指示仪 一、结构简介： 顶板离层指示仪是监测顶板锚杆范围内及锚固范围外离层值大小的一种监测仪器，在顶板钻孔中布置两个测点，一个在围岩深部稳定处，一个在锚杆端部围岩中。离层值就是围岩中两测点之间以及锚杆端部围岩与巷道顶板表面间的相对位移值。顶板离层指示仪由孔内固定装置、测量钢丝绳及孔口显示装置组成如图1所示。
二、安装方法： 1.在巷道顶板钻出φ32的钻孔，孔深由要求而定。 2.将带有长钢丝绳的孔内固定装置用安装杆推到所要求的位置；抽出安装杆后再将带有短钢丝绳的孔内固定装置推到所要求的位置。 3.将孔口显示装置用木条固定在孔口(在显示装置与钻孔间要留有钢丝绳运动的间隙)。 4.将钢丝绳拉紧后，用螺丝将其分别与孔口显示装置中的圆管相连接，且使其显示读数超过零刻度线。 三、测读方法： 孔口测读装置上所显示的颜色，反映出顶板离层的范围及所处状态，显示数值表示顶板的离层量。☆DY—82型顶板动态仪 一、用途 DY-82型顶板动态仪是一种机械式高灵敏位移计。用于监测顶底板移近量、移近速度，进行采场“初次来压”和“周期来压”的预报，探测超前支撑压力高 峰位置，监测顶板活动及其它相对位移的测量。 二、技术特征 (1)灵敏度(mm) 0.01 (2)精度(％) 粗读±1,微读±2.5 (3)量程(mm) 0～200 (4)使用高度(mm) 1000～3000 三、原理、结构 其结构和安装见图。仪器的核心部件是齿条6、指针8 以及与指针相连的齿轮、微读数刻线盘9、齿条下端带有读 数横刻线的游标和粗读数刻度管11。 当动态仪安装在顶底板之间时，依靠压力弹簧7产生的 弹力而站立。安好后记下读数(初读数)并由手表读出时间。 粗读数由游标10的横刻线在刻度管11上的位置读出，每小 格2毫米，每大格(标有“1”、“22'’等)为10毫米，微读数 由指针8在刻线盘9的位置读出，每小格为0.01毫米(共200 小格，对应2毫米)。粗读数加微读数即为此时刻的读数。当 顶底板移近时，通过压杆3压缩压力弹簧7，推动齿条6下 移，带动齿轮，齿轮带动指针8顺时针方向旋转，顶底板每 移近0.01毫米，指针转过1小格；同时齿条下端游标随齿条 下移，读数增大。后次读数减去前次读数，即为这段时间内的顶底板移近量。除以经过的时间，即得
计算机与信息技术学院综合性、设计性实验报告 一、实验目的 (1)熟悉顺序表的创建、取值、查找、插入、删除等算法，模块化程序设计方法。 二、实验仪器或设备 (1)硬件设备：CPU为Pentium 4 以上的计算机，内存2G以上 (2)配置软件：Microsoft Windows 7 与VC++6.0 三、总体设计(设计原理、设计方案及流程等) 设计原理： 单链表属于线性表，线性表的存储结构的特点是：用一组任意存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。因此，对于某个元素来说，不仅需要存储其本身的信息，还需要存储一个指示其直接后继的信息。 设计方案： 采用模块化设计的方法，设计各个程序段，最终通过主函数实现各个程序段的功能。设计时，需要考虑用户输入非法数值，所以要在程序中写入说可以处理非法数值的代码。 设计流程： 1. 引入所需的头文件； 2. 定义状态值； 3. 写入顺序表的各种操作的代码； 写入主函数，分别调用各个函数。在调用函数时，采用if结构进行判断输 入值是否非法，从而执行相应的程序 四、实验步骤(包括主要步骤、代码分析等) #include
实验三分治算法（2） 一、实验目的与要求 1、熟悉合并排序算法（掌握分治算法） 二、实验题 1、问题陈述: 对所给元素存储于数组中和存储于链表中两中情况，写出自然合并排序算法. 2、解题思路: 将待排序元素分成大小大相同的两个集合,分别对两个集合进行排序,最终将排好序的子集合合并成为所要求的排好序的集合.自然排序是通过一次扫描待排元素中自然排好序的子数组,再进行子数组的合并排序. 三、实验步骤 程序代码: #include
int target[N],head[N],tail[N]; int i=0,n,m; for(; i
土木工程学院 《混凝土结构设计基本原理》实验指导书 及实验报告 适用专业：土木工程周淼 编 班级：：学 号： 理工大学 2018 年9 月
实验一钢筋混凝土梁受弯性能试验 一、实验目的 1.了解适筋梁的受力过程和破坏特征； 2.验证钢筋混凝土受弯构件正截面强度理论和计算公式； 3.掌握钢筋混凝土受弯构件的实验方法及荷载、应变、挠度、裂缝宽度等数据的测试技术 和有关仪器的使用方法； 4.培养学生对钢筋混凝土基本构件的初步实验分析能力。 二、基本原理当梁中纵向受力钢筋的配筋率适中时，梁正截面受弯破坏过程表现为典型的三个阶段：第一阶段——弹性阶段（I阶段）：当荷载较小时，混凝土梁如同两种弹性材料组成的组合梁，梁截面的应力呈线性分布，卸载后几乎无残余变形。当梁受拉区混凝土的最大拉应力达到混凝土的抗拉强度，且最大的混凝土拉应变超过混凝土的极限受拉应变时，在纯弯段某一薄弱截面出现首条垂直裂缝。梁开裂标志着第一阶段的结束。此时，梁纯弯段截面承担的弯矩M cr称为开裂弯矩。第二阶段——带裂缝工作阶段（II阶段）：梁开裂后，裂缝处混凝土退出工作，钢筋应力急增，且通过粘结力向未开裂的混凝土传递拉应力，使得梁中继续出现拉裂缝。压区混凝土中压应力也由线性分布转化为非线性分布。当受拉钢筋屈服时标志着第二阶段的结束。此时梁纯弯段截面承担的弯矩M y称为屈服弯矩。第三阶段——破坏阶段（III阶段）：钢筋屈服后，在很小的荷载增量下，梁会产生很大的变形。裂缝的高度和宽度进一步发展，中和轴不断上移，压区混凝土应力分布曲线渐趋丰满。当受压区混凝土的最大压应变达到混凝土的极限压应变时，压区混凝土压碎，梁正截面受弯破坏。此时，梁承担的弯矩M u 称为极限弯矩。适筋梁的破坏始于纵筋屈服，终于混凝土压碎。整个过程要经历相当大的变形，破坏前有明显的预兆。这种破坏称为适筋破坏，属于延性破坏。 三、试验装置
. 实验一、单链表的插入和删除 一、目的 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 二、要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 三、程序源代码 #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表
ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存 //==========主函数============== void main() { char ch[10],num[10]; LinkList head; head=CreatListR1(); //用尾插入法建立单链表，返回头指针printlist(head); //遍历链表输出其值 printf(" Delete node (y/n):");//输入“y”或“n”去选择是否删除结点scanf("%s",num); if(strcmp(num,"y")==0 || strcmp(num,"Y")==0){ printf("Please input Delete_data:"); scanf("%s",ch); //输入要删除的字符串 DeleteList(head,ch); printlist(head); } DeleteAll(head); //删除所有结点，释放内存 } //==========用尾插入法建立带头结点的单链表
土工实验指导书及实验报告编写毕守一 安徽水利水电职业技术学院 二OO九年五月
目录 实验一试样制备 实验二含水率试验 实验三密度试验 实验四液限和塑限试验 实验五颗粒分析试验 实验六固结试验 实验七直接剪切试验 实验八击实试验 土工试验复习题
实验一试样制备 一、概述 试样的制备是获得正确的试验成果的前提，为保证试验成果的可靠性以及试验数据的可比性，应具备一个统一的试样制备方法和程序。 试样的制备可分为原状土的试样制备和扰动土的试样制备。对于原状土的试样制备主要包括土样的开启、描述、切取等程序；而扰动土的制备程序则主要包括风干、碾散、过筛、分样和贮存等预备程序以及击实等制备程序，这些程序步骤的正确与否，都会直接影响到试验成果的可靠性，因此，试样的制备是土工试验工作的首要质量要素。 二、仪器设备 试样制备所需的主要仪器设备，包括： （1）孔径0.5mm、2mm和5mm的细筛； （2）孔径0.075mm的洗筛； （3）称量10kg、最小分度值5g的台秤； （4）称量5000g、最小分度值1g和称量200g、最小分度值0.01g的天平；
（5）不锈钢环刀（内径61.8mm、高20mm；内径79.8mm、高20mm或内径61.8mm、高40mm）； （6）击样器：包括活塞、导筒和环刀； （7）其他：切土刀、钢丝锯、碎土工具、烘箱、保湿器、喷水设备、凡士林等。 三、试样制备 （一）原状土试样的制备步骤 1、将土样筒按标明的上下方向放置，剥去蜡封和胶带，开启土样筒取土样。 2、检查土样结构，若土样已扰动，则不应作为制备力学性质试验的试样。 3、根据试验要求确定环刀尺寸，并在环刀内壁涂一薄层凡士林，然后刃口向下放在土样上，将环刀垂直下压，同时用切土刀沿环刀外侧切削土样，边压边削直至土样高出环刀，制样时不得扰动土样。 4、采用钢丝锯或切土刀平整环刀两端土样，然后擦净环刀外壁，称环刀和土的总质量。 5、切削试样时，应对土样的层次、气味、颜色、夹杂物、裂缝和均匀性进行描述。 6、从切削的余土中取代表性试样，供测定含水率以及颗粒分析、界限含水率等试验之用。
本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生：俞梦真 指导教师：郝晓丽 2018年05月04 日
实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011
010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计：
链表实验报告
————————————————————————————————作者: ————————————————————————————————日期：
《数据结构》实验报告二 系别:嵌入式系统工程系班级:嵌入式1１0０3班 学号:１1160400３１4姓名：孙立阔 日期：2012年４月９日指导教师:申华 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求: 1.从键盘输入1０个字符，产生不带表头的单链表，并输入结点值。 2.从键盘输入1个字符,在单链表中查找该结点的位置。若找到,则显示“找到了”；否则, 则显示“找不到”。 3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插 入在对应位置上，输出单链表所有结点值,观察输出结果。 4.从键盘输入１个整数,表示欲删除结点的位置，输出单链表所有结点值,观察输出结果。 5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结 点值,观察输出结果。 6.删除其中所有数据值为偶数的结点，输出单链表所有结点值,观察输出结果。 7.（★)将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素, 而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表Ａ和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述: (包括程序的结构,数据结构，输入/输出设计,符号名说明等） 创建一个空的单链表，实现对单链表的查找，插入,删除的功能。 三、源程序及注释： #dｅfiｎｅOK 1 #defｉne EＲＲOR 0 #ｄefiｎe INFEASIBLE －1 #defｉne OVEＲFＬOW －2 #deｆine TRUE 1
北京邮电大学世纪学院 实验、实习、课程设计报告撰写格式与要求 （试行） 一、实验报告格式要求 1、有实验教学手册，按手册要求填写，若无则采用统一实验报告封面。 2、报告一律用钢笔书写或打印，打印要求用A4纸；页边距要求如下：页边距上下各为2.5厘米，左右边距各为2.5厘米；行间距取固定值（设置值为20磅）；字符间距为默认值（缩放100%，间距：标准）。 3、统一采用国家标准所规定的单位与符号，要求文字书写工整，不得潦草；作图规范，不得随手勾画。 4、实验报告中的实验原始记录，须经实验指导教师签字或登记。 二、实习报告、课程设计报告格式要求 1、采用统一的封面。 2、根据教学大纲的要求手写或打印，手写一律用钢笔书写，统一采用国家标准所规定的单位与符号，要求文字书写工整，不得潦草；作图规范，不得随手勾画。打印要求用A4纸；页边距要求如下：页边距上下各为2.5厘米，左右边距各为2.5厘米；行间距取固定值（设置值为20磅）；字符间距为默认值（缩放100%，间距：标准）。 三、报告内容要求 1、实验报告内容包括：实验目的、实验原理、实验仪器设备、实验操作过程、原始数据、实验结果分析、实验心得等方面内容。 2、实习报告内容包括：实习题目、实习任务与要求、实习具体实施情况（附上图表、原始数据等）、实习个人总结等内容。 3、课程设计报告或说明书内容包括：课程设计任务与要求、总体方案、方案设计与分析、所需仪器设备与元器件、设计实现与调试、收获体会、参考资料等方面内容。 北京邮电大学世纪学院 教务处 2009-8
实验报告 课程名称计算机绘图（CAD） 实验项目AutoCAD二维绘图实验 专业班级 姓名学号 指导教师实验成绩 2016年11月日
数据结构 课程设计 设计题目：单链表 专业班级：11软会四班 指导教师：吉宝玉 日期：2012 目录 一、实验目的 (2) 1、 (2) 2、 (2) 二、实验内容 (3)
三、实验基本要求（软、硬件） (3) 四、算法设计思想 (3) 1、 (3) 2、 (3) 3、 (3) 4、 (3) 5、 (3) 6、 (3) 7、 (3) 8、 (3) 五、算法流程图 (4) 六、算法源代码 (4) 七、运行结果 (9) 1、 (9) 2、 (10) 3、 (11) 4、 (11) 5、 (11) 6、 (12) 7、 (12) 8、 (13) 9、 (13) 八、收获及体会 (14) 一、实验目的 1、理解并掌握单链表的结构特点和相关概念； 2、学会单链表的基本操作：建立、插入、删除、查找、 输入、撤销、逆置、求前驱和后继等并实现其算法。
二、实验内容 利用头插建立一个带头结点的单链表，并用算法实现该单链表的插入、删除查找、输出、求前驱和后继、再把此单链表逆置，然后在屏幕上显示每次操作的结果当所有操作完成后能撤销该单链表。 三、实验基本要求（软、硬件） 用VC++6.0软件平台，操作系统：Windows XP 硬件：内存要求：内存大小在256MB，其他配置一般就行。 四、算法设计思想 1、定义一个创建链表的函数，通过该函数可以创建一个链表，并为下面的函数应用做 好准备。 2、定义输出链表的算法，通过对第一步已经定义好的创建链表函数的调用，在这一步 通过调用输出链表的函数算法来实现对链表的输出操作。 3、定义一个遍历查找的算法，通过此算法可以查找到链表中的每一个节点是否存在。 4、定义查找链表的每一个前驱和后继，通过定义这个算法，可以很容易的实现对链表 的前驱和后继的查找工作。 5、定义插入节点的算法，通过定义这个算法，并结合这查找前驱和后继的算法便可以 在连链表的任意位置进行插入一个新节点。 6、定义删除节点的操作，这个算法用于对链表中某个多余节点的删除工作。 7、定义一个逆置单链表的操作，通过定义这个算法，可以逆置输出单链表。 8、定义一个撤销链表的算法，这个算法用于删除单链表中的所有节点，使链表为空。
算法递归典型例题 实验一：递归策略运用练习 三、实验项目 1．运用递归策略设计算法实现下述题目的求解过程。 题目列表如下： （1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。 （2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i 个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？ 源程序： （3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？ （4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？ （5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？ （6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少页？ （7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？ 四、实验过程 （一）题目一：…… 1.题目分析 由已知可得，运动会最后一天剩余的金牌数gold等于运动会举行的天数由此可倒推每一 天的金牌剩余数，且每天的金牌数应为6的倍数。 2.算法构造 设运动会举行了N天， If(i==N)Gold[i]=N; Else gold[i]=gold[i+1]*7/6+i;
实验报告 课程名称：数据结构 题目：链表实现多项式相加 班级： 学号： 姓名： 完成时间：2012年10月17日
1、实验目的和要求 1）掌握链表的运用方法； 2）学习链表的初始化并建立一个新的链表； 3）知道如何实现链表的插入结点与删除结点操作； 4）了解链表的基本操作并灵活运用 2、实验内容 1）建立两个链表存储一元多项式； 2）实现两个一元多项式的相加； 3）输出两个多项式相加后得到的一元多项式。 3、算法基本思想 数降序存入两个链表中，将大小较大的链表作为相加后的链表寄存处。定义两个临时链表节点指针p,q,分别指向两个链表头结点。然后将另一个链表中从头结点开始依次与第一个链表比较，如果其指数比第一个小，则p向后移动一个单位，如相等，则将两节点的系数相加作为第一个链表当前节点的系数，如果为0，则将此节点栓掉。若果较大，则在p前插入q,q向后移动一个，直到两个链表做完为止。 4、算法描述 用链表实现多项式相加的程序如下： #include
void add_node(struct node*h1,struct node*h2); void print_node(struct node*h); struct node*init_node() { struct node*h=(struct node*)malloc(sizeof(struct node)),*p,*q; int exp; float coef=1.0; h->next=NULL; printf("请依次输入多项式的系数和指数(如:\"2 3\"；输入\"0 0\"时结束):\n"); p=(struct node*)malloc(sizeof(struct node)); q=(struct node*)malloc(sizeof(struct node)); for(;fabs(coef-0.0)>1.0e-6;) { scanf("%f %d",&coef,&exp); if(fabs(coef-0.0)>1.0e-6) { q->next=p; p->coef=coef; p->exp=exp; p->next=NULL; add_node(h,q); } } free(p); free(q); return(h); } void add_node(struct node*h1,struct node*h2) { struct node*y1=h1,*y2=h2; struct node*p,*q; y1=y1->next; y2=y2->next; for(;y1||y2;) if(y1) { if(y2) { if(y1->exp
《流体力学》课程实验指导书袁守利编 汽车工程学院 2005年9月
前言 1.实验总体目标、任务与要求 1)学生在学习了《流体力学》基本理论的基础上，通过伯努利方程实验、动量方程实 验，实现对基本理论的验证。 2）通过实验，使学生对水柱（水银柱）、U型压差计、毕托管、孔板流量计、文丘里流量计等流体力学常用的测压、测流量装置的结构、原理和使用有基本认识。 2.适用专业 热能与动力工程 3.先修课程 《流体力学》相关章节。 4.实验项目与学时分配 5. 实验改革与特色 根据实验内容和现有实验条件，在实验过程中，采取学生自己动手和教师演示相结合的方法，力求达到较好的实验效果。
实验一伯努利方程实验 1．观察流体流经实验管段时的能量转化关系，了解特定截面上的总水头、测压管水头、压强水头、速度水头和位置水头间的关系，从而加深对伯努利方程的理解和认识。 2．掌握各种水头的测试方法和压强的测试方法。 3．掌握流量、流速的测量方法，了解毕托管测速的原理。 二、实验条件 伯努利方程实验仪 三、实验原理 1．实验装置： 图一伯努利方程实验台 1.水箱及潜水泵 2.上水管 3.电源 4.溢流管 5.整流栅 6.溢流板 7.定压水箱 8.实验 细管9. 实验粗管10.测压管11.调节阀12.接水箱13.量杯14回水管15.实验桌 2.工作原理 定压水箱7靠溢流来维持其恒定的水位，在水箱下部装接水平放置的实验细管8，水经实验细管以恒定流流出，并通过调节阀11调节其出水流量。通过布置在实验管四个截面上的四组测压孔及测压管，可以测量到相应截面上的各种水头的大小，从而可以分析管路中恒定流动的各种能量形式、大小及相互转化关系。各个测量截面上的一组测压管都相当于一组毕托管，所以也可以用来测管中某点的流速。 电测流量装置由回水箱、计量水箱和电测流量装置（由浮子、光栅计量尺和光电子
数据结构(C语言版) 实验报告
专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序 的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"stdio.h" #include"string.h" #include"stdlib.h" #include"ctype.h" typedef struct node //定义结点 { char data[10]; //结点的数据域为字符串 struct node *next; //结点的指针域 }ListNode; typedef ListNode * LinkList; // 自定义LinkList单链表类型 LinkList CreatListR1(); //函数，用尾插入法建立带头结点的单链表 LinkList CreatList(void); //函数，用头插入法建立带头结点的单链表 ListNode *LocateNode(); //函数，按值查找结点 void DeleteList(); //函数，删除指定值的结点 void printlist(); //函数，打印链表中的所有值 void DeleteAll(); //函数，删除所有结点，释放内存
算法设计与分析课程实验项目目录 学生：学号： *实验项目类型：演示性、验证性、综合性、设计性实验。 *此表由学生按顺序填写。
本科实验报告专用纸 课程名称算法设计与分析成绩评定 实验项目名称蛮力法指导教师 实验项目编号实验项目类型设计实验地点机房 学生学号 学院信息科学技术学院数学系信息与计算科学专业级 实验时间2012年3月1 日～6月30日温度24℃ 1.实验目的和要求： 熟悉蛮力法的设计思想。 2.实验原理和主要容： 实验原理：蛮力法常直接基于问题的描述和所涉及的概念解决问题。 实验容：以下题目任选其一 1).为蛮力字符串匹配写一段可视化程序。 2).写一个程序，实现凸包问题的蛮力算法。 3).最著名的算式谜题是由大名鼎鼎的英国谜人 H.E.Dudeney(1857-1930)给出的： S END +MORE MONEY . 这里有两个前提假设： 第一，字母和十进制数字之间一一对应，也就是每个字母只代表一个数字，而且不同的字母代表不同的数字；第二，数字0不出现在任何数的最左边。求解一个字母算术意味着找到每个字母代表的是哪个数字。请注意，解可能并不是唯一的，不同人的解可能并不相同。3.实验结果及分析： （将程序和实验结果粘贴，程序能够注释清楚更好。）
该算法程序代码如下： #include "stdafx.h" #include "time.h" int main(int argc, char* argv[]) { int x[100],y[100]; int a,b,c,i,j,k,l,m,n=0,p,t1[100],num; int xsat[100],ysat[100]; printf("请输入点的个数：\n"); scanf("%d",&num); getchar(); clock_t start,end; start=clock(); printf("请输入各点坐标:\n"); for(l=0;l CENTRAL SOUTH UNIVERSITY 题目利用Matlab模拟点电荷电场的分布姓名xxxx 学号xxxxxxxxxx 班级电气xxxx班 任课老师xxxx 实验日期2010-10 电磁场理论 实验一 ——利用Matlab 模拟点电荷电场的分布 一．实验目的： 1．熟悉单个点电荷及一对点电荷的电场分布情况； 2．学会使用Matlab 进行数值计算，并绘出相应的图形； 二．实验原理： 根据库伦定律：在真空中，两个静止点电荷之间的作用力与这两个电荷的电量乘积成正比，与它们之间距离的平方成反比，作用力的方向在两个电荷的连线上，两电荷同号为斥力，异号为吸力，它们之间的力F 满足： R R Q Q k F ? 212 = (式1) 由电场强度E 的定义可知： R R kQ E ? 2 = (式2) 对于点电荷，根据场论基础中的定义，有势场E 的势函数为 R kQ U = (式3) 而 U E -?= (式4) 在Matlab 中，由以上公式算出各点的电势U ，电场强度E 后，可以用Matlab 自带的库函数绘出相应电荷的电场分布情况。 三．实验内容： 1. 单个点电荷 点电荷的平面电力线和等势线 真空中点电荷的场强大小是E=kq /r^2 ,其中k 为静电力恒量, q 为电量, r 为点电荷到场点P(x,y)的距离。电场呈球对称分布, 取电量q> 0, 电力线是以电荷为起点的射线簇。以无穷远处为零势点, 点电荷的电势为U=kq /r,当U 取 常数时, 此式就是等势面方程.等势面是以电荷为中心以r 为半径的球面。 平面电力线的画法 在平面上, 电力线是等角分布的射线簇, 用MATLAB 画射线簇很简单。取射线的半径为( 都取国际制单位) r0=, 不同的角度用向量表示( 单位为弧度) th=linspace(0,2*pi,13)。射线簇的终点的直角坐标为: [x,y]=pol2cart(th,r0)。插入x 的起始坐标x=[x; *x].同样插入y 的起始坐标, y=[y; *y], x 和y 都是二维数组, 每一列是一条射线的起始和终止坐标。用二维画线命令plot(x,y)就画出所有电力线。 平面等势线的画法 在过电荷的截面上, 等势线就是以电荷为中心的圆簇, 用MATLAB 画等势 线更加简单。静电力常量为k=9e9, 电量可取为q=1e- 9; 最大的等势线的半径应该比射线的半径小一点 r0=。其电势为u0=k8q /r0。如果从外到里取7 条等势线, 最里面的等势线的电势是最外面的3 倍, 那么各条线的电势用向量表示为: u=linspace(1,3,7)*u0。从- r0 到r0 取偶数个点, 例如100 个点, 使最中心点的坐标绕过0, 各点的坐标可用向量表示: x=linspace(- r0,r0,100), 在直角坐标系中可形成网格坐标: [X,Y]=meshgrid(x)。各点到原点的距离为: r=sqrt(X.^2+Y.^2), 在乘方时, 乘方号前面要加点, 表示对变量中的元素进行乘方计算。各点的电势为U=k8q. /r, 在进行除法运算时, 除号前面也要加点, 同样表示对变量中的元素进行除法运算。用等高线命令即可画出等势线 contour(X,Y,U,u), 在画等势线后一般会把电力线擦除, 在画等势线之前插入如下命令hold on 就行了。平面电力线和等势线如图1, 其中插入了标题等等。越靠近点电荷的中心, 电势越高, 电场强度越大, 电力线和等势线也越密。电磁场实验指导书及实验报告
相关主题
文本预览