用C语言实现查找算法.doc

《用C语言实现查找算法.doc》由会员分享，可在线阅读，更多相关《用C语言实现查找算法.doc（30页珍藏版）》请在三一文库上搜索。

1、用C语言实现查找算法学生姓名：* 指导老师：*摘 要 查找同人们每天的生活和工作息息相关，例如从电话号码本中查找某个电话号码，从成绩表中查找某个同学的成绩，从图书目录中查找某本书，从工资表中查找工资，从铁路时刻表中查找铁路时刻等。对于小规模的查找可以使用人力，对于大规模的查找活动使用计算机会更快、更准确【1】。因此，理解并会应用各种查找算法非常重要，本程序融合顺序查找，二分查找，二叉排序树，哈希算法等多种查找方法，我们可以从中比较并依据不同数据的特点使用不同的查找方法，具有较高的实用价值。C语言是一种结构化语言。它层次清晰，便于按模块化方式组织程序，易于调试和维护。C语言的表现能力和处理能力极

2、强。既可用于系统软件的开发，也适合于应用软件的开发。此外，C语言还具有效率高，可移植性强等特点。因此，用C语言实现查找算法具有很高的实用性。本程序主要包括四大块包括：（1）顺序查找；（2）二分查找；（3）二叉排序树；（4）哈希查找。本程序根据实际生活的需要，满足各方的要求，因此，运用空间还可进一步提高。在课程设计中，程序的开发平台是Windows XP，程序设计语言采用C语言，程序应用平台为Windows 2000/XP。采用自定义函数、数组和结构体来解决管理系统中的各种问题。程序经过调试和修改，基本实现了设计目标。关键词 程序设计；自定义函数；数组；结构体；查找算法1 引 言11课题背景 在

3、现代计算机应用中，程序设计占据重要地位，如学生成绩管理、万年历、网上问卷调查等等。用C语言实现查找算法要求实现顺序查找、二分查找、二叉排序树、哈希查找等多种查找方法。如何解决这些问题成为我研究的课题之一。作为一名学计算机的学生，光有理论知识是远远不够的，更重要的是我们的实际动手能力。学习计算机，理论能够指导我们的实践，能让我们在实践的应用过程中得心应手；反过来说，实践也能使我们对理论知识有更深刻的理解和体会，会促使我们更好的发现问题和解决问题，同时也使我在专业知识上的视野得到了很好的扩展。因此，综上所述，学计算机，最好的方法就是需要理论结合实际。而我们最缺乏的就是实践，因此，本次的课程设计给我

4、们提供了一个很好的实践的机会。程序设计实践课程设计是非常重要的综合性实践教学环节。通过该课程设计，进一步熟悉了软件开发的基本理论知识，了解了软件设计的一般步骤，掌握了软件开发的常用技巧，并且学会了更多的解决软件开发过程常见问题的方法。运用所学的数据结构的基本原理、基本知识和基本技巧，解决某一具体的实际问题，培养我们综合分析和解决问题的能力，为今后分析、设计、开发和调试程序打下坚实的基础【3】。1.2程序设计目的1、巩固面数据结构的基本理论知识2、进一步熟悉Visual C+6.0的编程环境，掌握相关控件的使用方法3、更深层次的理解自定义函数、数组和各种查找算法4、增强实践操作能力1.3程序设计

5、内容用C语言实现各种查找算法的想法来源于生活和工作中的需要。如今，随着社会的飞速发展，信息时代改变着人们的各种生活方式。人们的联系信息、联系方式变得复杂而多样化，人们的日常生活中也要求各类查找，由于传统的查找不方便、功能单一等缺陷已经无法胜任它的“时代使命”，因而，用计算机编程来实现各种查找方法已成为时代的迫切需要。此程序只是一个初步构想，可以将其应用到人们日常生活中的各种查找，很有现实意义。用C语言实现各类查找，它的内容对于电子产品来说是至关重要的，它能够为电子产品的使用者提供充足的信息和快捷的查询手段。用Visual C+6.0构建的各种查找方法，包括顺序查找、二分查找、二叉排序树、哈希查

6、找等。本程序设计合理、操作方便、运行稳定、功能完备，具有较高的实用价值。2 设计思路与方案2.1查找算法整体结构系统需要实现顺序查找、二分查找、二叉排序树、哈希查找四个模块，其中这四个模块又由其子程序实现，如图2.1所示：用C语言实现查找算法二分查找法哈希查找法顺序查找法二叉排序树图2.1 功能模块图2.2 设计方案编写一个程序，模拟查找算法管理系统。该系统主要有以下几个功能：（1）顺序查找子模块的实现： 顺序查找包括建立顺序表、输入表中数据、打印查找表、用哨兵查找法查找等几个内容，通过自定义函数，最终实现顺序查找的目的。（2）二分查找法的实现： 二分查找法又叫折半查找法，它需要把无序表变为有

7、序表（用Sort(SSTable *table )函数实现）之后再进行查找，设定3个变量low、mid和high，以实现二分查找法的功能。折半查找过程是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记录的关键字等于给定值或者查找区间的大小小于零时为止【2】。（3）二叉排序树的实现： 从主菜单进入二叉排序树功能，用户可根据提示输入相应信息，包括二叉排序树的建立、输出、插入、删除、查找等，可以充分利用二叉排序树的特点，实现查找的功能，可以提高查找效率。 （4）哈希查找的实现：从主菜单进入哈希查找功能，根据除留余数法构建哈希表，用二次探测法解

8、决冲，用SearHash(HashTable H,int key,int *p)函数进行查找。3 详细设计3.1 主菜单模块 通过四个自定义函数printSeq()、printBin()、printTree()、printHash()简化了主菜单，使其更加简洁明了，同时采用模块化的结果，是程序更加清晰，增强了它的易读性。3.2 顺序查找子模块 首先输入元素个数，然后输入这几个元素的值，用户再输入需要查询的数字即可得出查找结果，如果查找成功则显示出关键字所在的位置，否则显示“查找失败，表中无此数据”，如图3.2所示：输入1进入顺序查找功能输入元素个数判断是否在表中输出“查找失败，表中无此数据”输

9、出此元素在表中的位置输入各个元素的值输入要查找的关键字的值NY图3.23.3 二分查找子模块的实现：通过主菜单按键选择2进入二分查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，系统排序后会显示该关键字在顺序表中的位置，否则显示“查找失败，表中无此数据”，如图3.3所示：输入2进入二分查找功能输入元素个数输入元素个数按从小到大的顺序排序输入要查找的关键字的值输入各个元素的值输入要查找的关键字的值输出“查找失败，表中无此数据”N判断是否在表中Y输出在顺序表中的位置图3.33.4 二叉排序树子模块的实现：通过主菜单按键选择3进入二叉排序树功能，根据提示建立二叉排序树，然后进入

10、二叉排序树的菜单，通过数字选择想要实现的功能中序输出、插入一个节点、删除一个结点、查找一个结点等。3.5 哈希查找子模块的实现：通过主菜单按键选择3进入哈希查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，如果查找成功则显示存在此元素，否则显示“不存在此元素！”，如图3.5所示：输入4进入顺序查找功能输入元素个数判断是否在表中输出“不存在此元素！”输出“查找成功！”输入各个元素的值输入要查找的关键字的值NY图3.54 运行环境与结果4.1 运行环境在本课程设计中，系统开发平台为WindowsXP,程序设计语言为Visual C+6.0，程序的运行环境为Visual C+

11、6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的

12、首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Microsoft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。V

13、isual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。4. 2 运行结果（1）首主菜单：首先出现主菜单，通过选择相应数字进行相应功能的实现，如图所示：图4.2.1 主

14、菜单（2）通过主菜单按键选择1进入顺序查找功能，输入元素个数，然后输入这几个元素的值，用户再输入需要查询的数字即可得出查找结果，如果查找成功则显示出关键字所在的位置，否则显示“查找失败，表中无此数据”，图4.2.2示：图4.2.2 顺序查找（3）通过主菜单按键选择2进入二分查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，系统排序后会显示该关键字在顺序表中的位置，否则显示“查找失败，表中无此数据”，如图4.2.3所示：图4.2.3 查询功能（4）a通过主菜单按键选择3进入二叉排序树功能，首先输入结点个数及结点的值建立二叉排序树，然后便进入一个菜单提示选择二叉排序树的某个功

15、能如图4.2.4a所示：图4.2.4a 二叉排序树功能菜单b.中序遍历二叉排序树，如图4.2.4b所示：图4.2.4b 中序遍历二叉排序树c.插入一个结点，如图4.2.4c所示：图4.2.4c二叉排序树插入一个结点d删除一个结点，如图4.2.4d所示：图4.2.4d 二叉排序树删除一个结点e查找一个结点，如图4.2.4e所示：图4.2.4e 二叉排序树查找一个结点（5）通过主菜单按键选择4进入哈希查找功能，根据提示输入元素个数，再输入这几个值，然后输入要查找的关键字，找到则显示“查找成功！”，否则显示“不存在此元素”，如图4.2.5所示：图4.2.5 哈希查找法5 结束语这是一个简单的通过c语

16、言实现各种查找算法的系统，该系统实用性强可以根据我们的需要实现它的更多功能，具有很大的优越性。然而，这个程序还有一定的瑕疵，不同的查找算法的平均时间复杂度不同，他们的准确程度也不同，还有待进一步的提高。由于水平有限，有一些算法的实现不够简洁，不能达到理想水平。同时通过本次课程设计，我有很多感悟，主要几点如下：（1）通过本次对C语言的深入学习，让我对C语言有了更多的了解并学习到更多的知识，成功地运用各类函数、循环变量、结构化的程序设计，及结构体、数组、链表的使用加深了对查找算法的理解；（2）但在学习中发现，编程确实不是很好做的，并非是你想要就能完成的，它需要的是认真、仔细地对待每一个程序块；（3

17、）要多多动手，只看不动手永远不能达到自己想要的要求，并且容易出错，对能力提高不大；（4）今后要多多编程，增强对语言的熟悉程度，对自己严格要求，提高自己的综合水平；（6）总而言之，课程设计的过程就是一个汲取知识的过程，从中获益匪浅，通过这次课程设计使我们懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，参 考 文 献1 刘怀亮编著.数据结构（C程序）.北京：冶金工业出版社，20042 严蔚敏，吴伟民编著.数据结构：C语言版.北京：清华大学出版社，19973 杨路明等编著.C语言程序设计教程.北京：北京邮电大学出版社，2005附录：

18、程序相关源代码/ 程序名称：Search.cpp/ 程序功能：采用结构化方法设计程序，实现多种查找算法。/ 程序作者：*/ 最后修改日期：2011-3-3#includeiostream#includestdlib.h#includestdio.h#include malloc.h#define MAX 11 using namespace std;typedef int ElemType ;/顺序存储结构typedef struct ElemType *elem; /数据元素存储空间基址，建表时按实际长度分配，号单元留空 int length; /表的长度 SSTable; void Cre

19、ate(SSTable *table, int length);void Destroy(SSTable *table);int Search_Seq(SSTable *table, ElemType key);void Traverse(SSTable *table, void (*visit)(ElemType elem);/ 构建顺序表void Create(SSTable *table, int length) SSTable *t = (SSTable*) malloc(sizeof(SSTable);/分配空间t-elem=(ElemType*)malloc(sizeof(Elem

20、Type)*(length+1);t-length=length;*table=t;/ 无序表的输入void FillTable(SSTable *table)ElemType *t=table-elem;/for循环，输入各个元素for(int i=0; ilength; i+)t+;scanf(%d, t);/输入元素getchar();/ 销毁表void Destroy(SSTable *table)free(table-elem);/释放元素空间free(table);/释放表的空间/ 打印查找表void PrintTable(SSTable *table) int i;/定义变量El

21、emType *t=table-elem;for(i=0; ilength; i+)/进入循环，依次打印表中元素 t+;printf(%d , *t);/打印输出printf(n);/哨兵查找算法int Search_Seq(SSTable *table, ElemType key)table-elem0=key;/设置哨兵int result=0; / 找不到时，返回int i;for (i=table-length; i=1;i-) if (table-elemi=key) result=i;break;return result;/返回结果void printSeq()/先设置几个变量S

22、STable *table;int r;intn;ElemType key;printf(请输入元素个数:); scanf(%d,&n);/输入元素个数Create(&table, n);/建立表printf(请输入);cout0)printf( 关键字%d 在表中的位置是：%dn,key, r);/打印关键字在表中的位置printf(n);else /查找失败printf (查找失败，表中无此数据。nn);/ 排序算法 void Sort(SSTable *table )int i, j;ElemType temp; for (i=table-length; i=1 ;i-) / 从前往后找

23、 for (j=1; jelemjtable-elemj+1)temp=table-elemj;table-elemj=table-elemj+1;table-elemj+1=temp; / 二分法查找（非递归）int Search_Bin(SSTable *table, ElemType key) int low=1; int high=table-length; int result=0; / 找不到时，返回 while(low elemmid=key)/如果找到result=mid;break;else if(keyelemmid)/如果关键字小于mid对应的值high=mid-1;el

24、se /否则的话low=mid+1; return result;/返回结果void printBin()/声明变量SSTable *table;int r;intn;ElemType key;printf(请输入元素个数:);scanf(%d,&n);Create(&table, n);/建立表printf(请输入);cout0)printf(关键字%d 在表中的位置是：%dn,key, r);else printf (查找失败，表中无此数据。nn);/二叉排序树typedef struct BiTnode /定义二叉树节点int data; /节点的值struct BiTnode *lch

25、ild,*rchild;/节点的左孩子，节点的右孩子BiTnode,*BiTree;/查找（根据节点的值查找）返回节点指针BiTree search_tree(BiTree T,int keyword,BiTree *father)BiTree p;/ 临时指针变量*father = NULL;/先设其父亲节点指向空p = T;/p赋值为根节点（从根节点开始查找）while (p & p-data!=keyword)/如果不是p不指向空且未找到相同值的节点*father = p;/先将父亲指向自己（注意：这里传过来的father是二级指针）if (keyword data)/如果要找的值小于自

26、己的值p = p-lchild;/ 就向自己的左孩子开始找elsep = p-rchild;/否则向自己的右孩子开始查找return p;/如果找到了则返回节点指针BiTree creat_tree(int count)BiTree T,p;/设置两个临时变量T,pint i = 1;while (i data);/输入p指向节点的值p-lchild = p-rchild = NULL;/p的左孩子和右孩子都指向空i+;elseint temp;/ 如果不是空树scanf(%d,&temp);/输入节点的值search_tree(T,temp,&p);/查找节点要插入的位置。（T是根节点，插入

27、的节点的值，父亲节点的地址）if (temp data)/如果插入的值小于父亲节点的值p-lchild = (BiTnode *)malloc(sizeof(BiTnode);/那么就为父亲节点的左孩子分配一个节点空间，并指向这个空间if (!p-lchild)return NULL;p = p-lchild;/分配成功，p指向自己的左孩子else/ 如果插入的值大于父亲节点的值p-rchild = (BiTnode *)malloc(sizeof(BiTnode);if (!p-rchild)return NULL;/分配不成功，退出p = p-rchild;/p指向自己的右孩子p - da

28、ta = temp;/新分配的节点的值赋值为插入的值p - lchild = p-rchild = NULL;/使其左右节点均为NULLi+;return T;/返回根节点void InOrder(BiTree T)if(T)InOrder(T-lchild);printf(%d ,T-data);InOrder(T-rchild);int insert_tree(BiTree *T,int elem)/插入（根节点，插入的值）返回-1和,-1代表插入失败，代表成功BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode);/s指向新开辟一个

29、节点if (!s)/为开辟成功return -1;/ 返回值-1s-data = elem;/新节点的值赋值为插入的值s-lchild = s-rchild = NULL;/其左右孩子为空p = search_tree(*T,elem,&father);/p赋值为要插入的节点if (!p)return -1;/未开辟成功，返回-1if (father = NULL)/如果父亲节点指向空，说明是空树*T = s;/让根节点指向selse if (elem data)/否则如果插入的值小于父亲的值father-lchild = s;/父亲的左孩子赋值为selsefather-rchild = s;

30、/否则父亲的右孩子赋值为sreturn 0;/返回/删除树结点的操作int delete_tree(BiTree *T,int elem)BiTree s,p,q,father;/声明变量p = search_tree(*T,elem,&father);/查找if(!p)return -1;if(!p-lchild)/如果p的左孩子为空if (father = NULL)*T = p-rchild;/T指向左孩子free(p);/释放preturn 0;if (p = father-lchild)/如果p和father的左孩子相等father-lchild = p-rchild; /将p的左孩

31、子的值赋给father的左孩子elsefather-rchild = p-rchild;/将p的左孩子的值赋给father的右孩子free(p);/释放preturn 0;elseif(!p-rchild)if (father = NULL)/如果father为空*T = p-lchild;/将p的左孩子赋给Tfree(p);/释放preturn 0;if (p = father-lchild)/如果p等于father的左孩子的值father-lchild = p-lchild; /将p的左孩子的值赋给father的左孩子elsefather-rchild = p-lchild; /将p的左孩

32、子的值赋给father的右孩子free(p);return 0;elseq = p;s = p-lchild;/将p的左孩子赋给swhile (s-rchild)q = s;s = s-rchild;p-data = s-data;/将s的值赋给pif (q != p)/如果q不等于pq-rchild = s-lchild; /将s的左孩子值赋给p的右孩子elseq-lchild = s-lchild; /将s的左孩子值赋给p的右孩子free(s);/释放sreturn 0;/定义print1（）以便调用void print1()printf(t*n);printf(t1,输出中序遍历n);p

33、rintf(t2,插入一个结点n);printf(t3,删除一个结点n);printf(t4,查找一个结点n);printf(t5,返回主菜单n);printf(t*n);void printTree()/声明变量BiTree T,p;T=NULL;inti,n;ElemType key;printf(请输入结点个数：n);scanf(%d,&n);/输入值printf(请输入);coutn;printf(个值：);T=creat_tree(n);/建立树print1();scanf(%d,&i);/输入各个值while(i!=5)/i不等于5时switch(i)case 1:printf(中

34、序遍历二叉树结果如下：n);InOrder(T);/中序遍历break;case 2:printf(请输入要插入的结点值：);scanf(%d,&key);/输入要查找的关键字if(insert_tree(&T,key)/如果插入成功printf(插入成功！);elseprintf(已存在此元素！);break;case 3:printf(请输入要删除的结点值：);scanf(%d,&key); /输入要删除的关键字if(!(delete_tree(&T,key)/如果删除成功printf(删除成功！);elseprintf(不存在此元素！);break;case 4:printf(请输入要查

35、找的结点值：);scanf(%d,&key); /输入要查找的关键字if(search_tree(T,key,&p)/如果查找成功printf(查找成功！);elseprintf(不存在此元素！);break;default:printf(按键错误！);printf(n);print1();scanf(%d,&i);/哈希表typedef struct int num; Elemtype;/定义查找的结点元素typedef struct Elemtype *elem; /数据元素存储基址int count; /数据元素个数int sizeindex; HashTable;/定义哈希表int H

36、ash(int num) int p; p=num%11; return p; /定义哈希函数/冲突处理函数，采用二次探测再散列法解决冲突int collision(int p,int &c) int i,q; i=c/2+1; while(i=0) return q; else i=c/2+1; else q=(p-i*i)%MAX; c+; if(q=0) return q; else i=c/2+1; return 0;void InitHash(HashTable *H)/创建哈希表 int i; H-elem=(Elemtype *)malloc(MAX*sizeof(Elemtyp

37、e); H-count=0; H-sizeindex=MAX; for(i=0;ielemi.num=0;/初始化，使SearHash函数能判断到底有没有元素在里面 int SearHash(HashTable H,int key,int *p)/查找函数 *p=Hash(key); while(H.elem*p.num!=key&H.elem*p.num!=0) *p=*p+1; if(H.elem*p.num=key) return 1; else return 0; void InsertHash(HashTable *H,Elemtype e) /如果查找不到就插入元素int p; SearHash(*H,e.num,&p); /查找H-elemp=e; +H-count; void printHash()/调用哈希表 HashTable H; int p,key,i,n; Elemtype e; InitHash(&H);printf