课程设计静态查找的实现操作

1、届课程设计课程设计论文学生姓名 学 号 所属学院 信息工程学院专 业 计算机科学与技术 班 级 计算机15-2班 指导教师 教师职称 讲师塔里木大学教务处制目录前言1设计背景和意义1数据结构简介1选择算法的原因1设计的原理和内容1正文12.1 设计的目的和意义12.2 目标和总体方案22.3 设计方法和内容22.3.1 设计流程图2设计内容32.4 程序的设计思想和内容4程序设计的初始运行环境4静态查找中的顺序查找4静态查找表的折半查找5静态查找表的销毁6静态查找表的退出操作62.5 设计创新与关键技术6存在的问题7解决方案7参考文献7附录7前言数据结构简介数据结构是计算机程序设计的重要理论设

2、计基础，它不仅是计算机学科的核心课程，而且成为其他理工专业的热门选修课。数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率的算法。比如在计算机中央处理器中，CPU接到一个中断请求便会停下当前正在执行的指令去处理这个中断请求完成中断操作，首先要做的就是保护现场。保护现场需要将下一条指令的地址指针和当前指令返回地址等重要的数据进行存储。在众多的数据结构中，这些重要的数据被存储到栈这个数据结构中。选择算法的原因在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是

3、否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。本次程序设计采用C语作为描述和实现算法的程序语言，主要的设计思路就是完成对静态查找的操作，如表中元素的查找、元素对应表中的位置等等，这些操作都是通过C语言程序来实现的。最后的结果就是运行程序时能够完成对以上设计的操作。正文静态查找表是查找表的一种，它也就具备了查找表的特点，是有同一类型的数据元素构成的集合，由于“集合”中的元素之间存在着完全松散的关系，因此是一种非常灵便的数据结构方法。其主要操作查询某个特定的元素是

4、否在表中，检索某个特定的元素的各种属性。2.1 设计的目的和意义我们是计算机科学与技术专业的本科生，数据结构是我们重要的必修课程。当代社会学要大学培养出理论扎实，动手实践能力强的大学生。所以，本次课程设计的目的就在于通过一次实践性的活动加深对这门课程的理解，使我们在感性的认识上进一步升华为理性的认识。为后继课程的学习打下坚实的基础。马克思主义唯物辩证法认为，实践是连接客观实在和人主观意识的通道和桥梁。物质对意识的作用以及意识对物质的反作用都蕴含在实践活动当中。也就是，实践是检验真理的唯一标准。对这门课的学习状况的好坏，用一次课程设计便可以检验出来。而这，就是本次我们进行设计的意义之所在。2.2

5、 目标和总体方案静态查找表是根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素，若表中存在这样的一个记录或数据则便查找成功，此时查找的结果为给出的记录信息或者是指出该记录在查找表中的位置，表中若不存在关键字与给定值的记录则查找失败。本次设计的目标在于将静态查找中的操作用程序语言形象地再现和描述出来。于是特制订了一个总体的方案。由于时间只有十天，故做了如下的计划安排，将这项工程分为两大部分：程序的设计和程序的调试。首先在程序的设计部分由分为几个步骤：第一步：查阅有关数据结构静态查找操作的资料，用半天的时间。第二步：设计这个项目的整体架构和算法。用一到两天的时间。第三步：选择一

6、门程序设计语言进行算法的描述。两天的时间。其次，进行程序的调试。用一天。2.3 设计方法和内容“工欲善其事，必先利其器”。有了总体方案后必须用一个事半功倍的设计方法来提高程序设计的效率。在这个项目的设计上，选择了语言作为算法的描述语言，因为语言具有丰富的表达能力以及代码的高效性，并且有着良好的移植性和灵活性。采用“自顶向下，个个击破”的程序设计思路和思想，充分运用语言强大的功能。 设计流程图开始输出元素及其在表中的位置结束查找某个元素输出表中元素创建一个顺序表SWICH语句创建菜单进行选择图3-1 程序流程图设计内容一、程序设计的基本算法介绍1、静态查找表是一种只能在叫做查找表的一段进行查询操

7、作灵便的数据结构。静态查找表的主要特点是数据元素在顺序表中可以任意排列的，表中数据元素之间仅存在着“同属一个集合”的松散关系无逻辑关系。2、静态查找表的基本操作: (1)创建一个顺序表。 (2)输出表中所有元素 (3)输入一个关键字 (4) 比较关键字与表中元素的记录相等则返回它不等则在表中不存在 (5) 判断表若表为空，返回1，否则返回03、通常静态查找表用顺序表存储，与线性表的顺序存储类似，静态查找表中的数据元素存放在上述数组的第1到第n个单元，第n+1到最后一个单元为备用区。不同的是，这里多说明了一个单元即第0个单元，该单元被用于设置岗哨以便简化查找运算的实现。二、程序中涉及的基本算法

8、静态查找表是只能进行记录或元素在表中的查找看其是否在表中或者是检索某个记录或元素的各种属性，不能进行插入和删除等操作是一种查找表是同一类型数据元素集合数据之间存在着完全松散的关系，无逻辑上的关系。1、静态查找表的定义及基本操作 StaticSearchTableCreate(&ST,n); /构造含有n个元素的静态查找表STDestroy(&ST); /销毁表Search(ST,key); /查找关键字为key的数据元素Traverse(ST,visit(); /遍历查找表StaticSearchTable(1) 若选择顺序查找则其算法为： Search_Seq(SSTable ST, Key

9、Type key)/顺序查找的算法，0号元素为监视哨int i；ST.elem0.key=key;for (i=ST.length; !EQ(ST.elemi.key,key);-i);return i;(2) 若选择折半查找其算法为：int Search_Bin(SSTable ST,KeyType key) int low,high,mid; low = 1; high=ST.length; while (low high) mid = (low+high)/2; if (EQ(key,ST.elemmid.key) return mid;else if (LT(key,ST.elemmi

10、d.key) high=mid-1; /继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0; /顺序表中不存在待查元素2.4 程序的设计思想和内容程序设计的初始运行环境这个项目是由主函数模块和功能函数模块组成的。其中主函数模块是项目的控制部分，很重要的一个作用就是对整个程序的初始化功能。在设计初始运行环境时，为了每一次栈操作后都可以进行对程序的初始化，采用了dowhile循环语句构成一个无限循环，使得每一次静态查找操作之后都可以将程序初始化重新选择对静态查找的另一个操作，例如：选择3，将顺序表销毁，程序便又回到了初始的菜单界面，我们可以选择1进行静

11、态查找中的顺序查找。静态查找中的顺序查找其具体算法如下：void Search_Item(sqlist A)int i,n,k,temp=0,j;printf(请你创建一个顺序表);printf(请你输入元素的个数：);scanf(%d,&n);for(i=1;in+1;i+)printf(输入第%d个元素的值:,i);scanf(%d,&Ai);printf(n);for(i=1;in+1;i+)printf(%d,Ai);printf(n);printf(请你输入要查找的元素:);scanf(%d,&k);for(i=1;in+1;i+)if(Ai=k) j=i;temp=1;if(tem

12、p)printf(你所查找的元素在表中第%d个元素,j);elseprintf(你所查找的元素不在表中);静态查找表的折半查找折半查找的过程事先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或是找不到该记录为止在处于区间中间的位置记录的关键字和给定值比较，若想等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或是查找区间的大小小于零时（表明查找不成功）为止。具体程序算法及运行后的界面如下：int m, l=1, h=n;/置区间初值 while (l k) /继续在前半区间进行查找h = m - 1; if(Am k) /继续在后半区间进行查找l = m

13、+ 1;静态查找表的销毁当需要重新建立顺序表或建立新的时候为了减少内部空间的浪费需要对原来建有的顺序表进行销毁其具体操作算法如下：int Destory(sqlist A); if(1) printf(销毁顺序表);静态查找表的退出操作其退出静态查找的算法如下：exit(0)；2.5 设计创新与关键技术这个课程设计是一个简单的设计，如果说有“设计创新与关键技术”的话，只能勉强说有设计创新，至于关键技术应该谈不上。谈到设计创新，只能说在设计思路、设计方法和设计内容上有别人没有的东西。而所用的技术倒是没有多少。主要是运用了C语言丰富的表达能力，将静态查找表中的顺序查找和折半查找等操作形象的反应出来

14、。本次设计进展顺利，如期完成，并且达到了预先的设计要求，完全贯彻和执行了设计的总体方案。对于静态查找表的基本操作的描述和实现比较成功。然而，限于时间和水平，这个设计还有很多的不足之处。存在的问题一、所做界面不够美观。缺少一定的人性化因素二、所有的对静态查找表的的操作只能当表建立后方可进行。当进行顺序查找时，如果表长太长平均查找长度太大浪费时间。 解决方案一、针对其界面问题，可以到互联网上求助高手或自己到图书馆查阅相关的书籍。二、当对大型数据或是记录的文件进行查找时，这时候使用折半查找的查找方法会节约大量的时间提高了效率。参考文献12345杨路明C语言程序设计上机指导与习题选解. 北京邮电大学出

15、版附录#include stdio.h#includestdlib.h#define Maxlen 20typedef int elemtype ;typedef elemtype sqlistMaxlen;typedef int keytype ;void Search_Item(sqlist A);void Search_Middle(sqlist A);void main ()int cord;sqlist A;doprintf(nn);printf(n*主菜单*n);printf(n*1请你创建一个顺序表，进行顺序查找*n);printf(n*2请你创建一个有序表，进行折半查找*n);

16、printf(n*3销毁顺序表*n);printf(n*4退出*n);printf(n请输入你的选择：);scanf(%d,&cord);switch(cord)case 1:Search_Item(A);break;case 2:Search_Middle(A);break;case 3:int Destory(sqlist A);if(1)printf(销毁顺序表);break;case 4:exit(0);break;while (cord=4);int Destory(sqlist A) free(A);A=NULL;return 1;void Search_Item(sqlist A

17、)int i,n,k,temp=0,j;printf(请你创建一个顺序表);printf(请你输入元素的个数：);scanf(%d,&n);for(i=1;in+1;i+)printf(输入第%d个元素的值:,i);scanf(%d,&Ai);printf(n);for(i=1;in+1;i+)printf(%d,Ai);printf(n);printf(请你输入要查找的元素:);scanf(%d,&k);for(i=1;in+1;i+)if(Ai=k) j=i;temp=1;if(temp)printf(你所查找的元素在表中第%d个元素,j);elseprintf(你所查找的元素不在表中);void Search_Middle(sqlist A)int i,n,k,temp=0;printf(请你创建一个顺序表);printf(请你输入元素的