数据结构实验报告-查找算法（共11篇）
1.数据结构实验报告-查找算法 篇一
实验题9.1 设计一个程序exp9-1.cpp，输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法找关键字5的过程。程序如下：
//文件名:exp9-1.cpp #include
KeyType key;
//KeyType为关键字的数据类型 //其他数据
//定义表中最多记录个数
InfoType data;
} NodeType;typedef NodeType SeqList[MAXL];
//顺序表类型
int SeqSearch(SeqList R,int n,KeyType k)//顺序查找算法
{
int i=0;
while(i { } printf(“%d ”,R[i].key);i++; //从表头往后找 if(i>=n)return-1; else } void main(){ SeqList R;{ } printf(“%d”,R[i].key);return i; } int n=10,i;KeyType k=5;int a[]={3,6,2,10,1,8,5,7,4,9};for(i=0;i //建立顺序表 printf(“关键字序列:”);for(i=0;i 截图如下： 实验题9.2 设计一个程序exp9-2.cpp，输出在顺序表{1，2，3，4，5，6，7，8，9，10}中采用折半查找法查找关键字9的过程。 程序如下： //文件名:exp9-2.cpp #include //定义表中最多记录个数 KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL]; //顺序表类型 int BinSearch(SeqList R,int n,KeyType k)//二分查找算法 { int low=0,high=n-1,mid,count=0;while(low<=high) { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d]R[%d]:%dn”,++count,low,high,mid,R[mid].key); if(R[mid].key==k) //查找成功返回 return mid; if(R[mid].key>k) //继续在R[low..mid-1]中查找 high=mid-1; else low=mid+1; //继续在R[mid+1..high]中查找 } return-1;} void main(){ SeqList R;KeyType k=9;int a[]={1,2,3,4,5,6,7,8,9,10},i,n=10;for(i=0;i //建立顺序表 R[i].key=a[i];printf(“关键字序列:”);for(i=0;i 比 较 元 素 中 } else printf(“元素%d的位置是%dn”,k,i);printf(“元素%d不在表中n”,k); 截图如下： 实验题9.3 设计一个程序exp9-3.cpp，输出在顺序表{8，14，6，9，10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87}中采用分块查找法查找（每块的块长为5，共5块）关键字46的过程。 程序如下： //文件名:exp9-3.cpp #include KeyType key; //KeyType为关键字的数据类型 //定义表中最多记录个数 //定义索引表的最大长度 InfoType data; //其他数据 } NodeType;typedef NodeType SeqList[MAXL];typedef struct { KeyType key;int link; //KeyType为关键字的类型 //指向分块的起始下标 //顺序表类型 } IdxType;typedef IdxType IDX[MAXI]; //索引表类型 int IdxSearch(IDX I,int m,SeqList R,int n,KeyType k)//分块查找算法 { int low=0,high=m-1,mid,i,count1=0,count2=0;int b=n/m; //b为每块的记录个数 printf(“二分查找n”);while(low<=high) //在索引表中进行二分查找,找到的位置存放在low中 { mid=(low+high)/2;printf(“ 第%d 次 比 较 :在[%d,%d] 中 比 较 元R[%d]:%dn”,count1+1,low,high,mid,R[mid].key); if(I[mid].key>=k) high=mid-1; else low=mid+1; count1++; //累计在索引表中的比较次数 } if(low //在索引表中查找成功后,再在线性表中进行顺序查找 { printf(“比较%d次,在第%d块中查找元素%dn”,count1,low,k); i=I[low].link; printf(“顺序查找:n ”); while(i<=I[low].link+b-1 && R[i].key!=k) { i++;count2++; printf(“%d ”,R[i].key);} //count2累计在顺序表对应块中的比较次数 printf(“n”); printf(“比较%d次,在顺序表中查找元素%dn”,count2,k); if(i<=I[low].link+b-1) return i; else return-1;} 素 } return-1;void main(){ } SeqList R;KeyType k=46;IDX I;int a[]={8,14,6,9,10,22,34,18,19,31,40,38,54,66,46,71,78,68,80,85,100,94,88,96,87},i;for(i=0;i<25;i++)R[i].key=a[i]; //建立顺序表 I[0].key=14;I[0].link=0;I[1].key=34;I[1].link=4;I[2].key=66;I[2].link=10;I[3].key=85;I[3].link=15;I[4].key=100;I[4].link=20;if((i=IdxSearch(I,5,R,25,k))!=-1)else printf(“元素%d不在表中n”,k);printf(“元素%d的位置是%dn”,k,i);printf(“n”); 截图如下： 【关键词】位置服务 查询隐私 k-匿名 网格和密度 最小匿名空间 【中图分类号】TP309 【文献标识码】A 【文章编号】2095-3089（2016）11-0249-01 Interval Cloak产生的大量的空间冗余现象是由于空间划分精度太粗和没有考虑用户分布情况，体现用户分布不均匀的状态就是密度的概念，而空间网格化是为了提高空间划分的精度。本节将在地理信息系统中应用比较成熟的网格技术，对空间进行网格划分，以网格为一个计算单元，再根据用户分布密度，在用户分布相对密度最大的范围内寻找合适的匿名集。 一、算法原理 在地理信息系统中，网格数据模型被用来分析空间特征，由于其数据结构简单，且成本低廉等优势，在地理空间分析中得到了广泛应用。网格数据模型中，空间被规则的划分为网格，每个网格的位置由网格的行列号来表示，网格的值表示这个位置上物体的类型或状态。本节提出的基于网格和密度的（GDB， Grid and Density？鄄Based）匿名空间查找算法基本思想是首先将整个空间映射为m×n网格，提高空间计算的精度，再利用空间用户分布相对密度公式，计算用户分布相对密度，在用户分布密度最大的范围内寻找满足匿名条件的匿名集，根据密度概念，容易得知，同一k匿名要求下，用户分布密度越大，匿名空间越小，正是利用这个原理，GDB在用户分布密度最大的范围内寻找满足匿名条件的最小匿名空间。 二、剥离冗余边缘 对于最小包含空间S2的空间冗余部分，本小节定义了用户分布相对密度公式，根据此公式，计算各网格用户分布相对密度，然后由远及近用户分布密度由小到大依次剥离其冗余边缘，为避免用户过于密集，匿名空间过小导致的位置隐私泄露，限定条件匿名空间的最小粒度为Smin。 根据用户分布相对密度矩阵，以用户u为中心，由远及近依次删除用户分布相对密度最小的行或列，直到剥离某条边缘后，得到的匿名空间不满足匿名条件。 三、敏感度约束 为了满足LBS（p， k）匿名条件，需在MASSA算法过程中加入p敏感约束，称为p-MASSA算法，针对一般LBS（p， k）匿名提出的算法称为p1-MASSA算法，针对增强的LBS（p， k）匿名提出的算法称为p2-MASSA算法。 与空间用户分布矩阵类似，对于用户提交的敏感查询和非敏感查询，分别用1和0来表示，构建匿名区域内用户查询敏感度矩阵，矩阵每个坐标的值表示对应网格内敏感查询的个数，为了简化计算，将匿名集中敏感查询所占比例不超过p的条件修改为匿名集中敏感查询个数不超过floor（k×p），仍以上面的例子为例，假设查询敏感度矩阵如矩阵Sid，若用户敏感度要求为0.3，即空间内敏感查询的个数不超过floor（4×0.3）=1，根据矩阵Sid可知阴影区域内敏感查询个数为1，满足匿名条件，则直接将该空间返回。 算法描述了基于增强的LBS（p， k）匿名空间查找算法。1行，Q集状态初始化，4～8行，在匿名度条件、匿名空间最小粒度条件满足的前提下，若敏感查询个数大于floor（k×p），则根据用户分布密度矩阵和敏感度矩阵依次删除用户分布密度最小，敏感度最大的网格内的查询，9～12行，若While循环退出时敏感查询个数不超过floor（k×p），则将此时Q内的所有查询标记flag修改为true，表示该集合内的查询满足敏感度条件，查询都能被处理，之后算法过程不需考虑查询敏感性，与MASSA算法过程相同，找到合适的匿名空间并将其返回，13～15行，否则，表示匿名失败，拒绝此次查询请求。 四、总结 本文分析了目前最典型的匿名空间查找算法在查找过程中产生的大量的空间冗余现象，提出了基于网格和密度的最小k匿名空间查找算法，首先将空间划分为m×n网格，其次，根据用户所处网格邻域空间内的用户数对空间进行迭代分割，找到最小包含空间，然后根据用户分布密度矩阵一次剥离用户分布密度最小的边，找到最小匿名空间。最后，在MASSA算法内加入了p敏感约束，并构建了查询敏感度矩阵，根据第3章提出的一般LBS（p， k）匿名模型和增强的LBS（p， k）匿名模型，分别提出了p1-MASSA算法和p2-MASSA算法，p1-MASSA算法最小以空间边缘为一个处理单位，p2-MASSA算法最小以一个网格为处理单位，先删除敏感度最大的网格，在敏感度要求较高的情况下，提高了匿名成功的可能性。 参考文献： [1]刘洋.位置服务：冬去春未来[J]. 环球财经， 2011， 12（7）： 99-101. [2]潘晓，肖珍，孟小峰.位置隐私研究综述[J]. 计算机科学与探索， 2007， 1（3）： 268-281. [3]魏琼，卢炎生.位置隐私保护技术研究进展[J]. 计算机科学， 2008， 35（9）： 21-25. 000648043 姚金宇 我是计算机系2006级本科生，在大二上学期选修了张铭老师的数据结构与算法实验班。数据结构与算法课是每一个计算机专业学生的必修课，从我目前所学习的后续课程，包括算法设计、编译技术等课程来看，这门课是其非常重要的基础课程之一。 我从初中就开始接触高中的信息学奥林匹克竞赛，对数据结构与算法方面的相关知识接触的比较早。张老师为了更有针对性地对具有不同基础的学生进行因材施教，开设了数据结构算法实验班，我很荣幸地被批准通过选修实验班的课。通过一个学期的学习，我加深了对数据结构与算法的相关知识的理解，并通过张老师细致地讲解，将自己过去从高中竞赛所学到的离散的、碎片式的知识点连贯地串了起来，形成了一套较为完整的知识体系。我想这对于我后续的学习和对更高层次数据结构与算法知识的探索，都是大有裨益的。 我认为，在这门课的学习过程中，张老师所引导我们掌握的不仅仅是知识点与问题的简单联系，而是进行拓展性地思考和探索。例如树的顺序存储，除了讲解各种带标记的存储方法以外，我们还讨论了这些存储方式中记录的信息是不是都是必须的、如何用最少的标记信息表示一棵树等问题。这就让我们对原本看似平凡的知识有更深刻的认识。另外，我们所完成的作业和练习也都不是简单的解题训练，很多问题都是带有可研究性与可扩展性的，甚至很多问题没有单一的结论，这就引导我们创造性地应用所学的知识去研究问题、解决问题。 张老师在实验班的课堂上不但注重基础知识的讲解，还会适当介绍一些较为高级的数据结构（例如伸展树、后缀树等），以及一些较新的算法研究成果。这些介绍不仅对于巩固基础数据结构有很强的促进作用，还让对我们往后更难的课程更有信心。事实上，我认为算法与数据结构在我们计算机专业课程的学习中是无处不在的，图论中的树、图模型，组合数学中模型的计数，编译技术中关于文法的分析、自动机模型，无一不包含数据结构与算法的理论。能够更快、更好地掌握后续这些课程的知识体系，于我在数据结构与算法课中所学是分不开的。我是北大ACM队员之一，并于今年代表北京大学参加了第32届ACM-ICPC国际大学生程序设计竞赛全球总决赛，获得了第13名。ACM-ICPC竞赛十分注重选手对于模型抽象的能力、对于数据结构与算法的理解以及编程能力。这门课程对我参加ACM竞赛无疑也是帮助甚大。它让我更系统、透彻地理解了数据结构与算法的相关知识，对于在赛场上的解题能力和解题速度都有很大的提高。总而言之，张老师的数据结构与算法这门课程作为我的必修课之一，对于我计算机专业的学习是帮助很大并且影响深远的。 北京大学计算机系2006级本科生 000648043 姚金宇 一、实验名称：银行家算法 二、实验目的：银行家算法是避免死锁的一种重要方法，通过编写一个简单的银行家算法程序，加深了解有关资源申请、避免死锁等概念，并体会和了解死锁和避免死锁的具体实施方法。 三、问题分析与设计： 1、算法思路：先对用户提出的请求进行合法性检查，即检查请求是否大于需要的，是否大于可利用的。若请求合法，则进行预分配，对分配后的状态调用安全性算法进行检查。若安全，则分配；若不安全，则拒绝申请，恢复到原来的状态，拒绝申请。 2、银行家算法步骤：（1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。 （3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： Available=Available-Request[i];Allocation=Allocation+Request;Need=Need-Request;(4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 3、安全性算法步骤： （1）设置两个向量 ①工作向量Work。它表示系统可提供进程继续运行所需要的各类资源数目，执行安全算法开始时，Work=Allocation;②布尔向量Finish。它表示系统是否有足够的资源分配给进程，使之运行完成，开始时先做Finish[i]=false，当有足够资源分配给进程时，令Finish[i]=true。 （2）从进程集合中找到一个能满足下述条件的进程： ①Finish[i]=false ②Need （3）当进程P获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work=Work+Allocation;Finish[i]=true;转向步骤（2）。 （4）如果所有进程的Finish[i]=true,则表示系统处于安全状态；否则，系统处于不安全状态。 4、流程图： 系统主要过程流程图 银行家算法流程图 安全性算法流程图 四、实验代码： //#define M 5 //#define N 3 #include void line()//美化程序，使程序运行时更加明朗美观 { printf(“-----------------n”);} void start()//表示银行家算法开始 { line();printf(“ 银行家算法开始n”);printf(“--死锁避免方法 line();} void end()//表示银行家算法结束 { line();printf(” 银行家算法结束，谢谢使用n“);line();} void input()//输入银行家算法起始各项数据 { for(n=0;n<5;n++) { printf(”请输入进程P%d的相关信息：n“,n); printf(”Max:“); for(m=0;m<1;m++) scanf(”%d“,&max[n][m]); printf(”Allocation:“); for(m=0;m<1;m++) scanf(”%d“,&allocation[n][m]); n”); } for(m=0;m<1;m++) need[n][m]=max[n][m]-allocation[n][m];printf(“请输入系统可利用资源数Available:”);for(m=0;m<1;m++) } void output()//输出系统现有资源情况 { line();printf(“资源情况 Max Allocation Need Availablen”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++){ printf(“P%d%3d%3d%3d”,n,max[n][0],allocation[n][0],need[n][0]); } line();} void change()//当Request[i,j]<=Available[j]时，系统把资源分配给进程P[i]，Available[j]和Need[i,j]发生改变 { for(m=0;m<1;m++){ if(n==0)else printf(“n”); printf(“%3d%3dn”,available[0]);scanf(“%d”,&available[m]); } } available[m]-=request[i][m];allocation[i][m]+=request[i][m];need[i][m]-=request[i][m];void outputsafe()//输出安全序列的资源分配表 { printf(“该安全序列的资源分配图如下：n”);line();printf(“资源情况 Work Need Allocation Work+Allocation Finishn”);printf(“进程 A A A A n”);line();for(n=0;n<5;n++) printf(“P%d%9d%3d%3d%5d%12sn”,safe[n],works[safe[n]][0],need[safe[n]][0],allocation[safe[n]][0],works[safe[n]][0]+allocation[safe[n]][0],finish[n]);line();} int check()//安全性算法 { printf(“开始执行安全性算法……n”);for(m=0;m<1;m++)//数组work和finish初始化 work[m]=available[m];for(n=0;n<5;n++){ } finish[n]=“false”;safe[n]=0;k=0;for(m=0;m<5;m++)for(n=0;n<5;n++) if(strcmp(finish[n],“false”)==0 && need[n][0]<=work[0])//查找可以分配资源但尚未分配到资源的进程 { safe[k]=n;//以数组safe[k]记下各个进程得到 分配的资源的顺序 works[safe[k]][0]=work[0]; 放出分配给它的资源 work[0]+=allocation[n][0];//进程执行后释 finish[n]=“ture”;//finish[n]变为1以示该进 程完成本次分 } k++;for(m=0;m<5;m++)//判断是否所有进程分配资源完成{ 0 素都为ture } else if(m==4)//此处m=4表示所有数组finish的所有元if(strcmp(finish[m],“false”)==0){ printf(“找不到安全序列，系统处于不安全状态。n”);return 0;//找不到安全序列，结束check函数，返回 { printf(“找到安全序列P%d->P%d->P%d->P%d->P%d，系统是安全的n”,safe[0],safe[1],safe[2],safe[3],safe[4]); } return 1;} void main()//主程序开始 { start();for(;j==0;)//确认输入数据的正确性，若输入错误，重新输入 { 入：“); } printf(”数据确认无误，算法继续。n“);if(check()==0)//若check函数返回值为0，表示输入的初始数据找不到安全序列，无法进行下一步，程序结束 { } for(;j==1;)//当有多个进程请求资源时，循环开始 { printf(”请输入请求资源的进程i(0、1、2、3、4)：“);//输入发出请求向量的进程及请求向量 end();exit(0);input();printf(”以下为进程资源情况，请确认其是否正确：n“);output();printf(”数据是否无误：n正确：输入1n错误：输入0n请输 } j=1; outputsafe();//输出安全序列的资源分配表 scanf(“%d”,&j); scanf(“%d”,&i);printf(“请输入进程P%d的请求向量Request%d：”,i,i);for(n=0;n<1;n++) scanf(“%d”,&request[i][n]); for(;request[i][0]>need[i][0];)//若请求向量大于需求资源，则认为是输入错误，要求重新输入 { printf(“数据输入有误，请重试！n请输入进程P%d的请求向量Request%d：”,i,i); 提供分配 n“,i); } if(request[i][0]<=available[0])//判断系统是否有足够资源 for(n=0;n<1;n++) scanf(”%d“,&request[i][n]);{ } else printf(”系统没有足够的资源，进程P%d需要等待。printf(“系统正在为进程P%d分配资源……n”,i);change();//分配资源 j=0;if(j==0)//j=0表示系统有足够资源分配的情况 { printf(“当前系统资源情况如下：n”);//输出分配资源后的系统资源分配情况 分配无效 output(); if(check()==0)//若找不到安全系列，则之前的资源 { printf(“本次资源分配作废，恢复原来的资源分配 状态。n”); 资源状态 输入：“); for(m=0;m<1;m++)//恢复分配资源前的系统 } } { } output();//输出系统资源状态 available[m]+=request[i][m];allocation[i][m]-=request[i][m];need[i][m]+=request[i][m];printf(”是否还有进程请求资源？n是：输入1n否：输入0n请 scanf(“%d”,&j);//若还有进程请求资源，j=1，之前的for循环条件满足 } end();} 五、程序执行结果： 六、实验总结 实验六 遗传算法实验II 一、实验目的： 熟悉和掌握遗传算法的原理、流程和编码策略，并利用遗传求解函数优化问题，理解求解TSP问题的流程并测试主要参数对结果的影响。 二、实验原理： 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。 遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。要求利用遗传算法求解TSP问题的最短路径。 三、实验内容： 1、参考实验系统给出的遗传算法核心代码，用遗传算法求解TSP的优化问题，分析遗传算法求解不同规模TSP问题的算法性能。 2、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 3、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 4、上交源代码。 四、实验报告要求： 1、画出遗传算法求解TSP问题的流程图。 2、分析遗传算法求解不同规模的TSP问题的算法性能。 规模越大，算法的性能越差，所用时间越长。 3、对于同一个TSP问题，分析种群规模、交叉概率和变异概率对算法结果的影响。 （1） 种群规模对算法结果的影响 x 0 1.1 3.5 4.5 y 1.1 5.1 4.5 实验次数：10 最大迭代步数:100 交叉概率：0.85 变异概率：0.15 种群规模 平均适应度值 最优路径 25.264 4-5-8-7-6-3-1-0-9-2 26.3428 2-9-1-0-3-6-7-5-8-4 25.1652 1-3-6-7-5-8-4-2-9-0 25.1652 0-1-3-6-7-5-8-4-2-9 25.1652 9-0-1-3-6-7-5-8-4-2 25.1652 1-0-9-2-4-8-5-7-6-3 150 25.1652 5-8-4-2-9-0-1-3-6-7 200 25.1652 1-3-6-7-5-8-4-2-9-0 250 25.1652 3-1-0-9-2-4-8-5-7-6 300 25.1652 5-8-4-2-9-0-1-3-6-7 如表所示，显然最短路径为25.1652m,最优路径为1-0-9-1-3-6-7-5-8-4-2或3-1-0-9-2-4-8-5-7-6，注意到这是一圈，顺时针或者逆时针都可以。当种群规模为10，20时，并没有找到最优解。因此并不是种群规模越小越好。 （2） 交叉概率对算法结果的影响 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 实验次数：15 种群规模：25 最大迭代步数:100 变异概率：0.15 实验结果： 交叉概率 最好适应度 最差适应度 平均适应度 最优解 0.001 28.0447 36.6567 32.6002 9-2-6-0-5-4-8-7-3-1 0.01 27.0935 34.9943 32.1495 7-8-3-1-9-2-6-0-5-4 0.1 28.0447 35.3033 31.9372 7-3-1-9-2-6-0-5-4-8 0.15 28.0447 34.1175 31.2183 0-5-4-8-7-3-1-9-2-6 0.2 28.7108 33.9512 30.9035 3-1-9-2-6-5-0-4-7-8 0.25 28.0447 35.1623 30.7456 1-3-7-8-4-5-0-6-2-9 0.3 27.0935 31.9941 29.9428 8-3-1-9-2-6-0-5-4-7 0.35 27.0935 32.8085 30.9945 9-1-3-8-7-4-5-0-6-2 0.4 27.0935 32.5313 30.1534 1-3-8-7-4-5-0-6-2-9 0.45 27.0935 33.2014 30.1757 8-3-1-9-2-6-0-5-4-7 0.5 28.0934 33.6307 30.9026 5-0-2-6-9-1-3-8-7-4 0.55 27.0935 33.5233 29.1304 1-9-2-6-0-5-4-7-8-3 0.6 27.0935 33.2512 30.7836 3-1-9-2-6-0-5-4-7-8 0.65 28.0447 33.7003 30.9371 5-4-8-7-3-1-9-2-6-0 0.7 27.0935 32.0927 29.9502 9-1-3-8-7-4-5-0-6-2 0.75 28.0447 32.4488 30.3699 0-5-4-8-7-3-1-9-2-6 0.8 27.0935 32.1551 29.9382 7-4-5-0-6-2-9-1-3-8 0.85 27.0935 34.5399 30.3594 5-0-6-2-9-1-3-8-7-4 0.9 27.0935 32.6273 30.69 6-0-5-4-7-8-3-1-9-2 0.95 27.0935 32.4672 29.919 6-2-9-1-3-8-7-4-5-0 （注:红色表示非最优解） 在该情况下，交叉概率过低将使搜索陷入迟钝状态，得不到最优解。 （3） 变异概率对算法结果的影响 x 1.1 3.5 3.5 4.5 y 1.1 5.1 8.5 实验次数：10 种群规模：25 最大迭代步数:100 交叉概率：0.85 实验结果： 变异概率 最好适应度 最差适应度 平均适应度 最优解 0.001 29.4717 34.732 32.4911 0-6-2-1-9-3-8-7-4-5 0.01 29.0446 34.6591 32.3714 8-4-5-0-2-6-9-1-3-7 0.1 28.0934 34.011 30.9417 5-0-2-6-9-1-3-8-7-4 0.15 27.0935 32.093 30.2568 6-0-5-4-7-8-3-1-9-2 0.2 27.0935 32.2349 30.3144 8-7-4-5-0-6-2-9-1-3 0.25 27.0935 32.718 30.1572 4-5-0-6-2-9-1-3-8-7 0.3 27.0935 32.4488 30.2854 0-5-4-7-8-3-1-9-2-6 0.35 27.0935 33.3167 30.7748 1-3-8-7-4-5-0-6-2-9 0.4 29.0446 34.3705 31.3041 2-0-5-4-8-7-3-1-9-6 0.45 27.0935 31.374 29.6816 2-6-0-5-4-7-8-3-1-9 0.5 27.0935 32.3752 30.2211 2-9-1-3-8-7-4-5-0-6 0.55 27.0935 33.3819 30.6623 1-3-8-7-4-5-0-6-2-9 0.6 28.0934 33.2512 30.36 1-3-8-7-4-5-0-2-6-9 0.65 27.0935 32.7491 30.0201 3-1-9-2-6-0-5-4-7-8 0.7 28.7108 32.4238 30.785 1-3-8-7-4-0-5-6-2-9 0.75 27.0935 31.8928 30.2451 1-9-2-6-0-5-4-7-8-3 0.8 28.0934 31.6135 30.3471 9-1-3-8-7-4-5-0-2-6 0.85 29.662 33.2392 31.1585 2-9-1-3-7-8-4-0-5-6 0.9 28.0447 32.0387 30.4152 0-5-4-8-7-3-1-9-2-6 0.95 28.0447 31.3036 30.0067 9-1-3-7-8-4-5-0-6-2 从该表可知，当变异概率过大或过低都将导致无法得到最优解。 4、增加1种变异策略和1种个体选择概率分配策略，比较求解同一TSP问题时不同变异策略及不同个体选择分配策略对算法结果的影响。 不同变异策略和不同个体选择分配策略几乎不影响算法运行的时间，但会影响适应度。 五、实验心得与体会 通过本实验，更加深入体会了参数设置对算法结果的影响。同一个算法，参数值不同，获得的结果可能会完全不同。 讨论了空间最近目标查找的基本算法和相关的空间索引机制,简单地比较了几种算法和索引机制的优缺点.详细地介绍了在Windows IIS和.Net下,建立多级空间格网索引,实现空间最近目标查找的实现方法. 作 者：田锋 蒋许锋 TIAN Feng JIANG Xu-feng 作者单位：田锋,TIAN Feng(宁夏基础地理信息中心,宁夏,银川,750021) 蒋许锋,JIANG Xu-feng(天津市测绘院,天津,300381) 一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验要求及内容 要求编写的程序所能实现的功能包括： 1、从键盘输入要排序的一组元素的总个数 2、从键盘依次输入要排序的元素值 3、对输入的元素进行快速排序 4、对输入的元素进行折半插入排序 三、实验代码及相关注释 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的结构体 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的结构体 int Partition(SqList &L, int low, int high) //1 寻找基准 { L.r[0]=L.r[low];//子表的第一个记录作基准对象 int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： 实验报告 学生姓名 课 程 电力系统分析的计算机算法 学 号 专 业 电气工程及其自动化 指导教师 邱晓燕 二Ο一四 年 六 月 二日 实验一 潮流计算 一、实验目的 1．了解并掌握电力系统计算机算法的相关原理。 2．了解和掌握PSD-BPA电力系统分析程序稳态分析方法（即潮流计算）。3．了解并掌握PSD-BPA电力系统分析程序单线图和地理接线图的使用。 二、实验背景 随着科学技术的飞速发展，电力系统也在不断地发展，电网通过互联变得越来越复杂，同时也使系统稳定问题越来越突出。无论是电力系统规划、设计还是运行，对其安全稳定进行分析都是极其重要的。 PSD-BPA软件包主要由潮流和暂稳程序构成，具有计算规模大、计算速度快、数值稳定性好、功能强等特点，已在我国电力系统规划、调度、生产运行及科研部门得到了广泛应用。 本实验课程基于PSD-BPA平台，结合《电力系统分析计算机算法》课程，旨在引导学生将理论知识和实际工程相结合，掌握电力系统稳态、暂态分析的原理、分析步骤以及结论分析。清晰认知电力系统分析的意义。 三、原理和说明 1.程序算法 PSD-BPA电力系统分析程序稳态分析主要是潮流计算，软件中潮流程序的计算方法有P_Q分解法，牛顿_拉夫逊法，改进的牛顿－拉夫逊算法。采用什么算法以及迭代的最大步数可以由用户指定。 注：采用P-Q分解法和牛顿－拉夫逊法相结合，以提高潮流计算的收敛性能，程序通常先采用P-Q分解法进行初始迭代，然后再转入牛顿－拉夫逊法求解潮流。 2.程序主要功能 可进行交流系统潮流计算，也可进行包括双端和多端直流系统的交直流混合潮流计算。除了潮流计算功能外，该软件还具有自动电压控制、联络线功率控制、系统事故分析（N-1开断模拟）、网络等值、灵敏度分析、节点P－V、Q－V和P－Q曲线、确定系统极限输送水平、负荷静特性模型、灵活多样的分析报告、详细的检错功能等功能。 3.输入、输出相关文件 *.dat 潮流计算数据文件 *.bse 潮流计算二进制结果文件（可用于潮流计算的输入或稳定计算）*.pfo 潮流计算结果文件 *.map 供单线图格式潮流图及地理接线图格式潮流图程序使用的二进制结果文件 *.pff，*.pfd 中间文件（正常计算结束后将自动删除。不正常时，将留在硬盘上，可随时删除） pwrflo.dis 储存一个潮流作业计算时屏幕显示的信息。pfcard.def 定义潮流程序卡片格式文件，用户可更改及调整该文件。该文件安装时放在与潮流程序相同的目录中。打开TextEdit应用程序时先读入该文件。4.程序常用控制语句 常用的控制语句主要包括： (1)指定潮流文件开始的一级控制语句“(POWERFLOW, CASEID=方式名, PROJECT=工程名)” (2)指定计算方法和最大迭代次数的控制语句“/SOL_ITER, DECOUPLED=PQ法次数, NEWTON=牛拉法次数”； (3)指定计算结果输出的控制语句“/P_OUTPUT_LIST, „”；(4)指定计算结果输出顺序的控制语句“/RPT_SORT= „”； (5)指定计算结果分析列表的控制语句“/P_ANALYSIS, LEVEL= ？”；(6)指定潮流结果二进制文件名的控制语句“/NEW_BASE, FILE = 文件名”； (7)指定潮流图和地理接线图使用的结果文件控制语句“/PF_MAP，FILE=文件名”； (8)指定网络数据的控制语句“/NETWORK_DATA”；(9)指定潮流数据文件结束的控制语句“(END)”； 5.计算结果介绍（PFO文件） 潮流计算结果文件内容主要分下述几个方面： 1）程序控制语句列表。 2）输入、输出文件及输出的内容列表。 3）错误信息。如为致命性错误，则中断计算。4）误差控制参数列表。5）迭代过程。6）计算结果输出： 详细计算结果列表：按节点、与该节点相联接支路顺序，并根据用户的要求（通过控制语句控制）可按照字母、分区或区域排序输出潮流计算结果。 分析报告列表：并根据用户的要求（通过控制语句控制），输出各种潮流分析报告。 7）错误信息统计。6.算例 IEEE 9节点例题： 图1 IEEE9节点系统接线图 节点参数、线路参数及变压器参数分别见表1～表3。 表1 IEEE 9节点算例节点参数 表2 IEEE 9节点算例线路参数 表3 IEEE 9节点算例变压器参数 注：表1-表3中功率基准值为100MVA；电阻、电感值为标幺值。对应于上述系统及数据的潮流计算数据（IEEE90.DAT）见例1。例1： (POWERFLOW,CASEID=IEEE9,PROJECT=IEEE_9BUS_TEST_SYSTEM)/SOL_ITER,DECOUPLED=2,NEWTON=15,OPITM=0./P_INPUT_LIST,ZONES=ALL /P_OUTPUT_LIST,ZONES=ALL /RPT_SORT=ZONE /NEW_BASE,FILE=IEEE90.BSE /PF_MAP,FILE = IEEE90.MAP /NETWORK_DATA BS GEN1 16.501 999.999.1.04 B GEN1 230.01 B STATIONA 230.01 125.50.0 0.B STATIONB 230.01 90.30.0 0.B STATIONC 230.01 100.35.0 0.000 B GEN2 230.01 BE GEN2 18.001 163.999 10 25 B GEN3 230.01 BE GEN3 13.801 85.999.1025 .L-----------------transmission lines----------------------------L GEN1 230.STATIONA230..0100.0850.0440 L GEN1 230.STATIONA230.2.0100.0850.0440 L GEN1230.STATIONB230..0170.0920.0395 L STATIONA230.GEN2230..0320.1610.0765 L STATIONB230.GEN3230..0390.1700.0895 L GEN2230.STATIONC230..0085.0720.03725 L STATIONC230.GEN3230..0119.1008.05225.T-----transformers--------- T GEN116.5 GEN1230..0576 16.5 230.T GEN218.0 GEN2230..0625 18.0 230.T GEN313.8 GEN3230..0586 13.8 230.(END) 四、实验过程及结果 （一）IEEE9节点算例： 1.系统接线图： 2.在BPA软件建立模型，并进行计算，结果如下： 1）系统数据 2）计算过程迭代信息及详细的输出列表： 小结 3.406 -60.2 0.000 28.2 0.000 0.0 3.406 -32.0 -------------- -------------- -------------- -------------- 总结 3.406 -60.2 0.000 28.2 0.000 0.0 3.406 -32.0 * 并联无功补偿数据列表 /----------电容器（Mvar）-----------/ /-----------电抗器（Mvar）-------------/ 区域/分区 最大容量 使用容量 备用 未安排容量 最大容量 使用容量 备用 未安排容量 01 73.4 73.4 0.0 0.0 0.0 0.0 0.0 0.0 ------- ------- ------- ------- ------- ------- ------- ------- 总结 73.4 73.4 0.0 0.0 0.0 0.0 0.0 0.0 TRANSMISSION LINES CONTAINING COMPENSATION OWN ZONE BUS1 BASE1 ZONE BUS2 BASE2 ID PERCENT CASE CONTAINS NO TRANSMISSION LINES WITH SERIES COMPENSATION * 节点相关数据列表 节点 电压 /--------发电--------/ /---负荷----/ /-----无功补偿-----/ 类型 拥有者 分区 电压/角度 kV MW MVAR 功率因数 MW MVAR 使用的存在的未安排 PU/度 发电机1 16.5 16.5 105.4 23.1 0.98 0.0 0.0 0.0 0.0 0.0 S 01 1.000/ 0.0 发电机2 18.0 18.0 180.0 40.6 0.98 17.0 8.0 0.0 0.0 0.0 E 01 1.000/ 5.4 发电机3 13.8 13.8 85.0 13.8 0.99 0.0 0.0 0.0 0.0 0.0 E 01 1.000/ 1.6 母线1 230.0 239.3 0.0 0.0 0.0 0.0 21.6 21.6 0.0 01 1.040/-3.5 母线2 230.0 238.3 0.0 0.0 35.0 10.0 0.0 0.0 0.0 01 1.036/-0.6 母线3 230.0 240.3 0.0 0.0 0.0 0.0 0.0 0.0 0.0 01 1.045/-1.3 母线A 230.0 232.6 0.0 0.0 125.0 70.0 20.5 20.5 0.0 01 1.011/-6.0 母线B 230.0 234.1 0.0 0.0 90.0 40.0 10.4 10.4 0.0 01 1.018/-5.7 母线C 230.0 235.6 0.0 0.0 100.0 55.0 21.0 21.0 0.0 01 1.024/-3.1 -------------- -------------------------------- 整个系统 370.4 77.6 367.0 183.0 73.4 73.4 0.0 电容器总和 73.4 73.4 0.0 电抗器总和 0.0 0.0 0.0 * 旋转备用数据列表 ------------有功功率----------- ------------------------无功功率----------------------- 区域/分区 最大值 实际出力 备用 最大值 最小值 已发无功 吸收无功 备用 (MW) (MW) (MW) (MVAR) (MVAR) (MVAR) (MVAR) (MVAR) 01 370.4 370.4 0.0 2997.0 0.0 77.6 0.0 2919.4 ------- ------- ------ ------- ------- ------- ------ ------- 总结 370.4 370.4 0.0 2997.0 0.0 77.6 0.0 2919.4 说明： 1.有功旋转备用不包含所有同步电动机的功率（如 抽水蓄能电机）。 有功出力为负值的发电机（包括电动机）作为负荷处理，不统计在内。 当最大出力值小于实际出力时，统计时最大出力值用实际出力值代替。 2.无功旋转备用不包含同步调相机的无功功率。 无功旋转备用只统计有功出力大于0并且基准电压小于30kV的发电机。 * 潮流计算迭代过程和平衡节点相关信息数据 计算结果收敛。牛顿-拉夫逊法迭代次数为 5次。 各区域平衡机出力数据列表 区域 平衡机 电压 额定有功 有功出力 无功出力 有功负荷 无功负荷 所属分区 SYSTEM 发电机1 16.5 1.000 0.00 105.41 23.11 0.00 0.00 01 * 没有遇到错误信息 23:03:48 3）单线图： （二）课本习题：E2-5 1.网络接线图： 2.程序： (POWERFLOW,CASEID=IEEE9,PROJECT=IEEE_9BUS_TEST_SYSTEM)/SOL_ITER,DECOUPLED=2,NEWTON=15,OPITM=0 /P_OUTPUT_LIST,ZONES=ALL /RPT_SORT=ZONE /NEW_BASE,FILE=IEEE90.BSE /PF_MAP,FILE = IEEE90.MAP /NETWORK_DATA.BUS-----------------节点数据-----BS 母线4 999 999 1.050 B 母线1 0.32 0.20 B 母线2 0.56 0.16 BE 母线3 0.5 999 1.10 .L-----------------支路数据-----L 母线1 母线2 0.11 0.40 0.015 L 母线2 母线4 0.08 0.40 0.014 L 母线4 母线1 0.12 0.51 0.019 .T--------------变压器数据，包括普通变压器、移相器、带调节的变压器等。 T 母线1 母线3 0.07 0.35 (END) 3.计算结果 4.系统单线图 五、总结及思考题 实验中遇到的问题及解决方法： 路径错误——————重设各个参数路径 卡片无法识别—————将参数规范化 本次实验使我初步掌握了PSD-BPA软件在电力系统潮流计算中的使用方法，收获良多，为今后的工作打下了基础。获益匪浅。 电力系统潮流计算是研究电力系统稳态运行情况的一种基本计算。它的任务是根据给定的运行条件和网路结构确定整个系统的运行状态，如各母线上的电压（幅值及相角）、网络中的功率分布以及功率损耗等。电力系统潮流计算的结果是电力系统稳定计算和故障分析的基础。 数据结构与算法课程设计 说明书 动态查找表 学 院： 海洋信息工程学院 专 业： 计算机科学与技术 学生姓名： 学 号： 指导教师： 2015年月 26 日 动态查找表 学生姓名：银杰 指导老师：王晓莹 摘 要 本课程设计说明书系统地阐述了我使用C语言在Code::Blocks软件编写的动态查找表程序的整个过程，编写的环境是win7 64位操作系统。根据题目要求，编写动态查找表使用二叉排序树，即二叉链表作为存储结构。该程序具有建立数据功能、具有数据查找功能、具有数据插入功能、具有数据删除功能等基本功能操作。 关键词：动态查找表，Code::Blocks软件，win7 64位操作系统，C# dynamic lookup table Author :yinjie Tutor :Wangxiaoying Abstract This course design specification system to explain the whole process of using C language in Code:: Blocks software written in the dynamic look-up table program, the preparation of the environment is win7 64 bit operating system.According to the topic request, the preparation of the dynamic look-up table using the two fork sort tree, that is, the two binary list as the storage structure.The program has the function of building data, data searching, data insertion, data deletion and so on.Key words:dynamic lookup table, Code::Blocks software,win7 64 bit operating system，C # 目 录 引言.........................................................................................................................................................................1 查找的基本概念.................................................................................................................................................1 小结.....................................................................................................................................................................1 题目.....................................................................................................................................................................1 第1章 程序的构图设计.....................................................................................................................................2 1.1动态查询表：...............................................................................................................................................2 1.2程序功能流程图：.......................................................................................................................................2(1)、主函数模块............................................................................................................................................2(2)、二叉排序树的生成................................................................................................................................3(3)、二叉排序树的查找模块........................................................................................................................4(4)、二叉排序树的插入模块........................................................................................................................4(5)、二叉排序树删除连接模块....................................................................................................................5(6)、二叉排序树的删除模块........................................................................................................................5(7)、二叉排序树的遍历模块........................................................................................................................6 第2章 详细设计的程序.....................................................................................................................................6 各函数模块.........................................................................................................................................................6(1)主函数模块................................................................................................................................................6(2)二叉排序树的生成模块............................................................................................................................8(3)二叉排序树的查找模块............................................................................................................................8(4)二叉排序树的插入模块............................................................................................................................9(5)多态查找表删除模块..............................................................................................................................10(6)二叉排序树的中序遍历模块..................................................................................................................12 第3章 程序测试和运行.....................................................................................................................................12 3.1 程序测试....................................................................................................................................................12 3.2 程序运行....................................................................................................................................................13 1、主界面 ...................................................................................................................................................13 2、建立二叉排序树模块界面.....................................................................................................................13 3、二叉排序树查找模块界面.....................................................................................................................14 4、二叉排序树插入模块界面.....................................................................................................................14 5、二叉排序树删除模块界面 ...................................................................................................................14 6、退出程序的界面.....................................................................................................................................14 总 结.....................................................................................................................................................................15 程序完成情况...................................................................................................................................................15 有待改进之处...................................................................................................................................................15 课程设计期间的收获.......................................................................................................................................15 附录源代码如下...................................................................................................................................................17 桂林电子科技大学课程设计说明书 引言 查找的基本概念 查找又称为检索，就是从一个数据元素集合中找出某个特定的数据元素。查找是数据处理中最为常用的一种操作，查找算法的优劣对整个软件系统的效率影响很大，尤其当所涉及的数据量较大时，更是如此。在一个数据集合中进行查找操作可选用的方法与该数据元素集合的存储结构有很大关系。 查找是根据某个给定的值，在数据元素构成的集合中确定是否在这样一个数据元素，它的关键字等于给定值的关键字。 要进行查找，必须明确要查找对象的特征，也就是要查找元素的关键值。如果在数据集合中能找到与给定值相等的关键字，则该关键字所属的数据元素就是所要查找的数据元素，此时称该查找成功；如果查遍了整个数据元素集合也未能找到与给定值相等的关键字，则称该查找失败。小结 当然对于这个说明书，我不可能做得至善至美，但是一些基本的格式内容还是符合要求的。首先，我对查找表进行一个简要的概述。然后，我就查找表进行了详细的分析，这是设计中很重要的一步。接下来，我把查找表中所有的设计简明清晰地展现出来，并把我在设计中遇到的问题和分析解决问题的办法做了分析。最后，在结论中，我对自己的课程设计做了总体的评价同时简述了我在这次课程设计中的收获和经验。 题目 选题十二：动态查找表 【问题描述】 利用二叉排序树完成动态查找表的建立、指定关键字的查找、插入与删除指定关键字结点。【任务要求】 算法输入：指定一组数据。 桂林电子科技大学课程设计说明书 算法输出：显示二叉排序树的中序遍历结果、查找成功与否的信息、插入和删除后的中序遍历结果(排序结果)。 算法要点：二叉排序树建立方法、动态查找方法,对树进行中序遍历。【测试数据】 自行设定，注意边界等特殊情况。 第1章 程序的构图设计 1.1动态查询表： 依照输入的一组数据{56,80,65,20}所得的二叉排序树如下（a）所示：当插入11的时候就如（b）所示。 562065801 156206580 （a） （b）1.2程序功能流程图： (1)、主函数模块 桂林电子科技大学课程设计说明书 开始打印输出动态表的6个功能选择栏do循环输入选择号hSwitch(h)执行对应函数模块程序退出结束 (2)、二叉排序树的生成 开始输入数据个数Xfor循环输入X个数据调用插入函数Insert二叉树建成结束 桂林电子科技大学课程设计说明书 (3)、二叉排序树的查找模块 开始二叉排序树是否为空否根结点关键字？key是大于递归返回在左子树查找递归返回等于小于在右子树查找查找失败查找成功结束 (4)、二叉排序树的插入模块 开始调用查询函数Search()是否查询成功否被插入结点*s为新的根结点是插入的节点根结点<被插结点*s为左孩子插入成功结束 >被插结点*s为右孩子 桂林电子科技大学课程设计说明书 (5)、二叉排序树删除连接模块 开始左右子树是否为空是While循环否向右走到尽头重接它的左右子树将被删结点的前驱s的内容直接替代该结点的内容被删除结点的左子树的右子树是否为空否重接*q的右子树是重接*q的左子树连接成功结束(6)、二叉排序树的删除模块 开始输入要删除的的数据是否存在关键字等于n的数据元素否调用删除的连接函数Delete()结束返回是找到关键字并删除 桂林电子科技大学课程设计说明书 (7)、二叉排序树的遍历模块 开始二叉树根是否为空否对左子树按中序遍历进行访问根结点对右子树按中序遍历进行遍历完成结束是递归调用 第2章 详细设计的程序 各函数模块 (1)主函数模块： 用主函数main()来实现。主要是通过设计一个do()函数并让主函数调用它来显示主菜单，让用户选择操作。在do()函数中，我应用了switch-case语句来进行选择，是个比较简单实现的模块。最后若选择“5”退出循环。否则继续循环。主要代码如下： int main(){ bitree T=NULL,p;ElemType e;int n;int h;char c; do{ printf(“********************************************************n”); 桂林电子科技大学课程设计说明书 printf(“* *n”); printf(“* 动态查找表 *n”); printf(“* 1.建立二叉排序树 *n”); printf(“* 2.二叉排序树查找元素 *n”); printf(“* 3.二叉排序树插入元素 *n”); printf(“* 4.二叉排序树删除元素 *n”); printf(“* 5.退出 *n”); printf(“* *n”); printf(“********************************************************n”); printf(“请输入你的选择: n”); scanf(“%d”,&h); switch(h) { case 1:Init(T);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”); break; case 2:printf(“请输入要查找的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“数据已经存在!n”); else { printf(“数据不存在!n”);} break; case 3:printf(“请输入要插入的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) printf(“已经存在!n”); else{Insert(T, e);printf(“成功插入!n”);printf(“中序遍历二叉排序树: ”);Zhongxu(T);printf(“n”);} break; case 4:printf(“请输入要删除的数据:n”);scanf(“%d”,&n);e.key=n; if(Search(T,e,NULL,p)) { Deletebit(T,n);printf(“已经成功删除!n”);printf(“中序遍历二叉排序 桂林电子科技大学课程设计说明书 树: ”);Zhongxu(T);printf(“n”);} else printf(“数据不存在!n”); break; case 5:printf(“退出！n”); break; default:printf(“选择错误，重新开始!n”); } } while(h!=5);}(2)二叉排序树的生成模块： 二叉排序树的生成，是从空的二叉排序树开始，每输入一个结点数据，就调用一次插入算法将它插到当前已经生成的二叉排序树中。主要代码如下： void Init(bitree &T)//构造一个动态查找表T { int x;int i;int n; ElemType e;printf(“请输入结点个数: ”);scanf(“%d”,&x); for(i=1;i<=x;i++) { printf(“第%d个结点数据值:”,i);scanf(“%d”,&n); e.key=n;Insert(T,e); } printf(“二叉排序树已经建立!n”);} (3)二叉排序树的查找模块： 二叉排序树的查找方法如下。当二叉排序树为空时，查找失败。 当二叉排序树根结点的关键字等于key时，查找成功。 桂林电子科技大学课程设计说明书 当二叉排序树根结点的关键字大于key时，从根结点的左子树中以同样方法进行查找。当二叉树根结点的关键字小于key时，从根结点的右子树以同样方法进行查找。显然，该过程是一个递归过程，下面给出这一算法的实现。 主要代码： bitree Search(bitree T,ElemType e,bitree f,bitree &p)//在二叉排序树中查找数据 { if(!T) { p=f; return NULL; }//查找不成功 else if(T->data.key==e.key) { p=T;return T; } //查找成功 else if(T->data.key>e.key) return Search(T->lchild,e,T,p); else return Search(T->rchild,e,T,p);}//在二叉排序树中查找数据(4)二叉排序树的插入模块： 若要将一个关键字值为key的结点t插到二叉排序树中，只需要使该结点插入后，二叉排序树中的元素依然按照原来的规律排列即可。二叉排序树的插入方法如下。 若二叉排序树是空树，则key称为二叉排序树的根。 若二叉排序树为非空，则将key与二叉排序树的根结点进行比较：如果key的值等于根结点的值，则停止插入；如果key的值小于根结点的值，则将key插到左子树；如果key的值大于根结点的值，则将key插到右子树中。主要代码如下： void Insert(bitree &T,ElemType e)//在二叉排序树中插入数据 桂林电子科技大学课程设计说明书 { bitree p,s; if(!Search(T,e,NULL,p))//查找不成功 { s=(bitree)malloc(sizeof(bitnode)); s->data=e;s->lchild=s->rchild=NULL; if(!p)T=s;//被插入结点*s为新的根结点 else if(e.key data.key) p->lchild=s;//被插结点*s为左孩子 else p->rchild=s;//被插结点*s为右孩子 } }(5)多态查找表删除模块： 从二叉排序树中删除一个结点，不能简单地把以该结点为根的子树都删除，只能删除掉该结点，并且还应该保证删除后所得到的二叉树依然满足二叉树的性质不变。也就是说，在二叉排序树中删除一个结点相当于删除有序序列中的一个结点。 假设要删除的结点为P，其双亲结点为F，同时假设结点P是结点F的左孩子（右孩子的情况类似）。删除操作首先要确定被删结点P是否在二叉排序树中。若不在，则不做任何操作；若在，分为以下三种情况讨论。若P为叶子结点，可直接将其删除。 若结点P只有左子树，或只有右子树，则可将P的左子树或右子树直接改为其双亲结点F的左子树或右子树。 若P既有左子树，又有右子树此时有两种处理方法。 方法1：首先找到结点P在中序序列中的直接前驱结点S，然后用结点P的左子树改为F的左子树，而将P的右子树改为S的右子树。 方法2：首先找到结点P在中序序列中的直接前驱结点s，然后用结点s的值替代结点p的值，再将结点s删除，原结点s的左子树改为s的双亲结点q的右子树。主要代码如下： 桂林电子科技大学课程设计说明书 void Delete(bitree &p)//从二叉排序树中删除结点p，并重接它的左或右子树 { bitree q,s; if(!p->rchild)//右子树空，只需重接它的左子树 { q=p;p=p->lchild;free(q);q=NULL; } else if(!p->lchild)//左子树空，只需重接它的右子树 { q=p;p=p->rchild;free(q);q=NULL; } else{//左右子树均不空 q=p;s=p->lchild; while(s->rchild)//向右走到尽头 { q=s;s=s->rchild; } p->data=s->data;//将被删结点的前驱s的内容直接替代该结点的内容 if(q!=p)//若被删除结点的左子树的右子树不为空 q->rchild=s->lchild;//重接*q的右子树 else q->lchild=s->lchild;//重接*q的左子树 free(s);s=NULL; } }//删除结点 void Deletebit(bitree &T,int n)//删除二叉排序树中的数据 { if(!T)return;//不存在关键字等于n的数据元素 桂林电子科技大学课程设计说明书 else{ if(T->data.key==n)return(Delete(T));//找到关键字等于n的数据元素并删除它 else if(T->data.key>n)Deletebit(T->lchild,n);//继续在左子树中删除 else Deletebit(T->rchild,n);//继续在右子树中删除 } } (6)二叉排序树的中序遍历模块： 中序遍历二叉树定义：若二叉树根为空，则返回；否则，中序遍历左子树；访问根结点；中序遍历右子树。主要代码如下： void Zhongxu(bitree T)//中序遍历 { if(T!=NULL) { Zhongxu(T->lchild); printf(“%d ”,T->data.key); Zhongxu(T->rchild); } } 第3章 程序测试和运行 3.1 程序测试 程序测试是程序质量保证的主要活动之一，在程序编写的过程中，在各个阶段都有可能存在错误和缺陷。通过测试是可以发现程序设计中存在的种种问题，并可以及时改正。避免在程序运行时才出现不必要的错误。测试是质量保证一个临界和决定惩罚，它提供对程序说明、设计和编码的最终评审。是发现程序缺陷和错误的有力手段。根据系统设计目标和功能，对系统进行测试。 桂林电子科技大学课程设计说明书 1、功能性 （1）程序实现的主要功能，包括查询，插入，删除等。 （2）题目要求的输入输出字段，以及题目要求的输入限制。 2、可靠性 程序正确实现了对动态查找表的查询、插入、删除等各种功能。 3、易用性 现有程序实现了如下易用性： （1）查询，插入，删除，操作相关提示信息的一致性，可理解性 （2）输入限制的正确性 （3）输入限制提示信息的正确性，可理解性，一致性 （4）界面排版简洁完整 3.2 程序运行 1、主界面 ： 2、建立二叉排序树模块界面 ： 桂林电子科技大学课程设计说明书 3、二叉排序树查找模块界面 ： 4、二叉排序树插入模块界面 ： 5、二叉排序树删除模块界面 ： 6、退出程序的界面 ： 桂林电子科技大学课程设计说明书 总 结 程序完成情况 在编写程序写课程设计的时间里，虽然历经重重困难和挫折，但是在我自己的努力和老师的帮助下终于完成了动态查找表的设计。尽管该程序在功能和性能上可能还有一些缺陷，但是我已经完成了课程设计的任务和目标，达到了题目基本要求，成功完成了算法与数据结构课程设计。有待改进之处 有待改进： 1、我在编写程序的时候，用的是C++格式去保存编译的，用了C语言来编写，但是有一些C++的形式，当我用C来新建保存的时候却出现问题。所以程序我是用C++来新建保存的。 2、流程图画的不是很规范表准，在一些逻辑表达上不够简洁清晰。课程设计期间的收获 在完成此次的课程设计的过程中，我跨越了传统方式下的教与学的体制束缚，桂林电子科技大学课程设计说明书 通过自己的思考和设计，培养了自学能力和动手能力。并且由原先的被动的接受知识转换为主动的寻求知识，这可以说是学习方法上的一个很大的突破。在以往的传统的学习模式下，我们可能会记住很多的书本知识，但是通过课程设计，我们学会了如何将学到的知识转化为自己的东西，学会了怎么更好的处理知识和实践相结合的问题。 通过这次课程设计，我认识到数据结构与算法是计算机科学的基础课程，是我们学习的核心课程。我对数据结构和算法又有了新的认识。数据结构的研究不仅涉及到计算机软件，而且和计算机硬件的研究也有着密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一个核心内容，是从事计算机科学研究及其应用的人必须掌握的重要内容。 这次的课程设计有效的培养了我们独立思考的能力，提高了我们的动手操作水平。在具体设计中，我们巩固了上学期所学的数据结构与算法的理论知识，进一步提高了自己的编程能力。这也是课程设计的目的所在。通过编程实践，不仅开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力，更充分锻炼了我们的编程能力。 在这次课程设计中我也知道了的编程能力不强，有很多程序与算法是借鉴别人的，我想只要我有自己写程序，并且结合他人的程序算法，把程序完成，那我还是学习到东西了的。 在课程设计中我体会到：一个好的程序应该是一个高内聚低耦合的程序。而要做出一个好的程序则应该通过对算法与其数据结构的时间复杂度和空间复杂度进行实现与改进。然而，实际上很难做到十全十美，原因是各要求有时相互制约，要节约算法的执行时间往往要以牺牲更多的存储空间为代价：而为了节省存储空间又可能要以更多的时间为代价。因此，只能根据具体情况有所侧重：如果程序的使用次数较少，则应该力求算法简单易懂；如果程序反复多次使用，则应该尽可能选用快速算法或者设置为内联函数；如果解决问题的数据量极大，但是机器的内存空间不是很充足，则在编写算法时应该考虑如何节省空间。 学习了《数据结构与算法》这门课，我们在编写程序时就应该注意到所编写程序的时间复杂度和空间复杂度，以及是否运用了良好的算法，而不是只是象以前编写程序时单纯使用C++的知识。我们要充分考虑程序的性能，从而编写出更好的程序。 桂林电子科技大学课程设计说明书 在设计报告的写作过程中我也学到了做任何事情都要有的心态，首先我明白了做学问要一丝不苟，对于出现的任何问题都不要轻视，要通过正确的途径去解决，在做事情的过程中要有耐心和毅力，不要一遇到困难就打退堂鼓，只要坚持下去就可以找到思路去解决问题的，在遇到问题时，有必要向老师和同学请教，合作沟通的意义是巨大的。 在这次课程设计中，我认识到了自己的不足之处同时我也收获了很多知识和经验，在今后的学习中，我一定勤于思考，并灵活运用所学知识，多进行编程实践。在总结反思和编程训练中，不断提升自己的编程能力。相信在我的努力下，我的程序设计水平一定会不断提高。 参考文献 [1]数据结构与算法/汪沁，奚李峰主编.-北京：清华大学出版社，2012.9（第8章 查找） [2]百度文库>专业资料>IT/计算机>计算机软件及应用>动态查找表实验报告 http://wenku.baidu.com/link?url=crizbdK6WO86YXeSJWwkHNdXpaxUDkRJnoShcVDJqBfGO03Cbk6LAdVwBYHxE82kYHkuIjC1HFCiOrSiEWJXOOspWGIo3PNSDjbeY1jHbJu 附录源代码如下： （六）实验名称：数据库及SQL语言 班级_______ 姓名__________ 学号______实验日期： 实验机时：3 学时实验成绩： ----------------- 一.实验目的： 1、学习数据库设计的一般过程及相关技术； 2、学习access数据库管理系统； 3、掌握数据库的输入、查询、更新操作。 二.实验内容： 1、需求陈述：某校图书馆要建立一个图书数据管理系统。该图书馆的图书（书名、分类号、作者、出版社）存放在不同的借阅室（室名），读者（姓名、系名、类别）在书架上找到所需图书后，可以到服务台办理借阅（借阅时间）。 设计要求： 分析需求，建立数据库的概念模型； 将概念模型转换为关系模型（注意：是否需要作规范化处理）； 写出创建基本表的SQL语句； 写出以下查询要求的SQL语句： （1）所有“高等数学习题集”书的信息； （2）读者“李林”借了什么书？ （3）“社会学原理”在哪个借阅室？ 2、在access数据库管理系统中建立所设计的关系表； 3、向各表中输入一组实验数据（元组）（注意：关系完整性）； 4、对数据库进行查询。 三.实验结果： 1、实体-关系图； 2、数据库表； 3、创建基本表的语句； 孙博 1104011045 11 计本3班 如何合理的组织数据、高效的处理数据是扩大计算机应用领域、提高软件效率的关键。而在软件开发过程中人们会要求软件工程师们使程序有更高的运行效率。因此要成为一名合格的软件编程员，必须具备数据结构领域和算法设计领域的专门知识。 本学期我们在李红老师的带领下学习了《数据结构结构与算法》一书。这本书安排十分合理，在第一章对全书进行导引和学习的基础知识、预备知识。在2—6章中使逻辑结构为“线性”的数据结构及其应用知识内容。在7、8章中使逻辑结构中的为“树形”的数据结构及应哟就能够只是内容。在第九章中使逻辑结构为“集合性”的数据元素在三列存储下的数据结构及其应用知识内容。在第十章使逻辑结构为“图形”的数据数据结构及其应用知识内容。下面将对各章的内容惊醒总结： 第一章：首先介绍了数据的相关知识，讲述了数据的概、构成等，数据的最小组成单位。然后讲述了数据类型与数据结构。 数据类型包括概念及定义，数据类型包括简单数据类型和复杂数据。简单数据类型有：整数，实属，字符，指针，枚举量等。而复杂数据类型包括：数组，结构图，共用体。 而数据结构主要使讨论元素之间的关系，数据结构包括三方面内容，及逻辑结构，存储结构以及一组运算集合。数据的逻辑结构有四种基本结构：集合性结构，线性结构，树形结构，图形结构。数据的存储结构是指数据严肃在存储器中的存储方式包括顺序存储，链表存储，索引存储，散列存储。 然后介绍以前学习的C语言（及本教材的使用的算法描述工具）知识锦兴路回顾包括指针、结构比阿亮、函数、递归、动态存储分配、文件操作等内容。 第二章：顺序表及其应用主要介绍的是线性逻辑结构的呼声几乎在顺序存储方法下的数据结构顺序标的概念、数据类型、数据结构、基本运算及相关应用问题。 应用一：查找—介绍了两种方法：简单顺序查找（从书序标的一端来时扫描，将待查找元素与数据节点中的个元素比较。若相等，则查找成功，否则失败）和二分查找（将表中间的记录的关键字与给定的值比较，若相等，则成功。否则，将顺序表风味左右两个字表，然后在子表中进一步查找。）应用二：排序问题—介绍了交换排序，选择排序，插入排序，归并排序。 1、插入排序 包括直接插入排序(将顺序表分为左右两个子表，左子表为有序表，右子表为无序表，将右子表中的元素插入左子表中)和希尔排序法（将整个待排序的元素序列分割成若干子序列，对每个子序列分别进行直接插入排序，当整个带排序元素序列“基本有序时”，在进行直接插入排序） 2、交换排序 a)冒泡排序：两辆比较待排序元素的关键字，发现相反时即进行交换，知道没有逆序的元素为止。b)快速排序算法：在待排序的元素中选定一个“中间数”，将其他数据元素与该数比较，将比其小的数据放道左子表中，比起大的放入右子表中。 3、选择排序 a)直接选择排序：将数据进行多谈排序，每趟选出其中的最大数或最小数放在最终位置上，每趟中已排好的数不再参加下一轮的排序。b)堆排序：输出堆顶元素将剩余元素按关键字大小重诚信排列成一个堆重复上述2个步骤 4、归并排序 将两个或两个以上的有序表合并成一个新的有序表。应用三：字符处理问题 介绍了串和顺序串的定义及相关概念，还有顺序串的基本算法。 第三章：介绍链表。链表中数据元素的存储不一定是连续的，还可以占用任意的、不连续的物理存储区域。与顺序表相比，链表的插入、删除不需要移动元素，给算法的效率带来较大的提高，且在存储空间上有动态申请的优点。这一章中介绍了链表的节点结构、静态与动态链表的概念、链表的基本运算（如求表长、插入、查找、删除等）、单链表的建立（头插法和尾插法）以及双向循环链表的定义、结构、功能和基本算法。弄清其个运算的算法思想及其时间复杂度和空间性能。最后介绍了链表之中存储结构在实际中的相关应用。 a)单循环链表是一种首尾相接的单链表，终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(n)，不用遍历整个链表。 b)双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior，形成两条不同方向的链。由头指针head惟一确定。双链表也可以头尾相构成双循环链表。双链表上的插入和删除时间复杂度均为O(1)。 顺序表和链表的比较 a）基本空间的考虑 存储密度是指节点数据本身所占的存储量除以结点构所占的存储总量所得的值。值越大存储空间利用率越高。 顺序表是静态分配的，存储密度为1,链表是动态分配的，存储密度小于1。b)顺序表适用于静态查找，要进行删除和插入操作时，需移动大量结点。链表适用于做动态的插入和删除。 第四章：堆栈是运算受限制的线性结构。其基本运算方法与顺序表和链表运算方法基本相同，不同的是堆栈须遵循“先进后出”的规则，对堆栈的操作只能在栈顶进行；堆栈在文字处理，匹配问题和算术表达式的求值问题方面的应用。 a)栈的基本运算有六种：构造空栈：InitStack，判栈空：StackEmpty，判栈满：StackFull，进栈：Push，退栈：Pop，取栈顶元素：StackTop b)在顺序栈中有“上溢”和“下溢”的现象。“上溢”是栈顶指针指出栈的外面是出错状态。“下溢”可以表示栈为空栈，因此用来作为控制转移的条件。 c)顺序栈中的基本操作有六种：构造空栈，判栈空，判栈满，进栈，退栈，取栈顶元素 d)链栈则没有上溢的限制，因此进栈不要判栈满。链栈不需要在头部附加头结点，只要有链表的头指针就可以了。e) 链栈中的基本操作有五种：构造空栈，判栈空，进栈，退栈，取栈顶元素 第五章：队列及其应用，我们知道队列是一种特殊的线性表，是一种具有线性逻辑结构的数据元素的集合。而队列的运算遵循“先进后出”的原则，因此，队列也是一个运算受限制的线性表。a)队列的基本运算有六种：置空队：InitQueue，判队空：QueueEmpty，判队满：QueueFull，入队：EnQueue，出队：DeQueue，取队头元素：QueueFront b)顺序队列的“假上溢”现象：由于头尾指针不断前移，超出向量空间。这时整个向量空间及队列是空的却产生了“上溢”现象。为了克服“假上溢”现象引入循环向量的概念，是把向量空间形成一个头尾相接的环形，这时队列称循环队列。c)判定循环队列是空还是满，方法有2种：一种是另设一个标志变量来判断;第二种是少用一个元素空间，入队时先测试(q->rear%m=q->front?)满：空。d)队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。 第六章：介绍了特殊矩阵和广义表的概念与应用。其中，特殊矩阵包括对称矩阵、三角矩阵、对角矩阵和稀疏矩阵，书中分别详细介绍了它们的存储结构。其中三元组和十字链表这两种结构尤为重要；对着两种结构的建立了应用要掌握。稀疏矩阵的应用包括转置和加法运算等。最后介绍了广义表的相关概念及存储结构，关于它的应用，课本中举了m元多项式的表示问题。 第七章：二叉树的知识是重点内容。在介绍有关概念时，提到了二叉树的性质以及两种特殊的二叉树：完全二叉树和满二叉树。接着介绍二叉树的顺序存储和链接存储以及生成算法。重点介绍二叉树的遍历算法（递归算法、先序、中序和后序遍历非递归算法）和线索二叉树。二叉树的应用：基本算法、哈夫曼树、二叉排序树和堆排序，其中关于二叉排序树和哈弗曼书的构建是重点。 a)两种特殊的二叉树：完全二叉树（非叶子节点均有两个孩子节点并且对于仍一层某一节点有孩子节点，该层所有节点均有孩子节点）和满二叉树（在完全二叉树上的基础上最下层从左到右删除若干个节点。） b)二叉树的5个重要性质 c)根据结点的次序不同可得三种遍历：先序遍历，中序遍历、后序遍历。 d)二叉树的应用：基本算法、哈弗曼树、二叉排序树和堆排序 第八章：介绍了树和森林。树与二叉树是不同的概念。教材介绍了树和森林的概念、遍历和存储结构，还有树、森林和二叉树的相互关系，树或森林怎样转化成二叉树，二叉树又如何转换为树和森林等算法。 第九章：散列结构是一种查找效率很高的一种数据结构。本章的主要知识点有：散列结构的概念及其存储结构、散列函数、两种冲突处理方法、线性探测散列和链地址散列的基本算法以及散列结构的查找性能分析。 第十章：介绍了图的概念及其应用，是本书的难点。图的存储结构的知识点有：邻接矩阵、邻接表、逆邻接表、十字链表和邻接多重表。图的遍历包括图的深度优先搜索遍历和广度优先搜索遍历。其余知识点有：有向图、连通图、生成树和森林、最短路径问题和有向无环图及其应用。有向无环图重点理解AOV网和拓扑排序及其算法。 心得体会以及建议：通过学习《数据结构与算法》我们可以设计出更好的算法，高效地组织数据。一个程序无论采用何种语言，其基本算法思想不会改变。“软件开发好比写作文，计算机语言提供了许多华丽的辞藻，而数据结构则考虑如何将这些辞藻组织成一篇优秀的文章来。”在学习这门课中，要熟悉对算法思想的一些描述手段，包括文字描述、图形描述和计算机语言描述等。因此，计算机语言基础是必须的，因为它提供了一种重要的算法思想描述手段——机器可识别的描述。 这门课结束之后，我总结了学习中遇到的一些问题，最为突出的，书本上的知识与老师的讲解都比较容易理解，但是当自己采用刚学的知识点编写程序时却感到十分棘手，有时表现在想不到适合题意的算法，有时表现在算法想出来后，只能将书本上原有的程序段誊写到自己的程序中再加以必要的连接以完成程序的编写。针对这一情况，我会严格要求自己，熟练掌握算法思想，尽量独立完成程序的编写与修改工作，只有这样，才能够提高运用知识，解决问题的能力。 教学的建议 1、建议在上课过程中加大随堂练习的分量，以便学生能当堂消化课堂上学习的知识，也便于及时了解学生对知识点的掌握情况，同时有助于学生保持良好的精神状态。 2、建议在课时允许的情况下，增加习题课的分量，通过课堂的习题讲解，加深对知识点的掌握，同时对各知识点的运用有一个更为直观和具体的认识。 【数据结构实验报告-查找算法】推荐阅读： 数据结构实验顺序表09-17 课设报告数据结构08-28 数据库实验5实验报告09-20 数据库实验报告实验四10-06 数据通信实验总结报告08-31 软件体系结构实验报告06-13 一种改进的广义概率数据关联跟踪算法06-10 数据库基础与应用实验报告06-20 数据结构课程标准10-062.数据结构实验报告-查找算法 篇二
3.数据结构与算法实验班学习体会 篇三
4.银行家算法实验报告 篇四
5.遗传算法求解TSP问题实验报告 篇五
6.数据结构实验报告-查找算法 篇六
7.数据结构实验报告 篇七
8.数据结构实验报告-查找算法 篇八
9.数据结构课程设计：动态查找表 篇九
10.数据结构实验报告-查找算法 篇十
11.数据结构实验报告-查找算法 篇十一