排序与查找(综合实验报告)

PAGE本科学生实验报告实验课程名称数据结构（C语言版）实验名称排序与查找开课学期2009至＿2010学年＿第二学期云南师范大学旅游与地理科学学院编印一、实验准备实验名称：排序与查找实验时间：2010年6月21日实验类型：综合实验1、实验目的和要求：实验目的(1)掌握查找的不同方法，并能用c语言实现查找算法。(2)掌握常用的排序方法，并掌握用c语言实现排序算法的方法。(3)熟练掌握顺序表的选择排序、冒泡排序、直接插入排序等算法的实现；(4)了解各种方法的排序过程及其时间复杂度的分析方法。实验要求(1)完整理解有关排序和查找的相关算法和基本思想以及种种算法使用的数据存储结构；(2)根据要实现的结果选择合适的查找算法和排序算法；(3)编写完整程序并上机调试运行；(4)认真整理并上交实验报告。2、实验材料及相关设备：计算机一台（装有turboc2软件）、《数据结构（C语言版）》（清华大学出版社）一本3、实验理论依据或知识背景：（1）查找有静态查找和动态查找。①静态查找表：仅作查询和检索操作的查找表。其定义为：ADTStaticSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：Create(&ST,n);操作结果：构造一个含n个数据元素的静态查找表ST。Destroy(&ST)；初始条件：静态查找表ST存在。操作结果：销毁表ST。Search(ST,key);初始条件：静态查找表ST存在，key为和查找表中元素的关键字类型相同的给定值。操作结果：若ST中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit是对元素操作的应用函数。操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次一旦Visit()失败，则操作失败。}ADTStaticSearchTable②动态查找表：有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。其定义为：ADTDynamicSearchTable{数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：InitDSTable(&DT)；操作结果：构造一个空的动态查找表DT。DestroyDSTable(&DT)；初始条件：动态查找表DT存在。操作结果：销毁动态查找表DT。SearchDSTable(DT,key);初始条件：动态查找表DT存在，key和关键字类型相同的给定值。操作结果：若DT中存在其关键字等于key数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。InsertDSTable(&DT,e);初始条件：态查找表DT存在，e为待插入的数据元素。操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到DT。DeleteDSTable(&T,key);初始条件：动态查找表DT存在，key为和关键字类型相同的给定值；操作结果：若DT中存在其关键字等于key的数据元素，则删除之。TraverseDSTable(DT,Visit());初始条件：动态查找表DT存在，Visit是对结点操作的应用函数；操作结果：按某种次序对DT的每个结点调用函数Visit()一次且至多一次。一旦Visit()失败，则操作失败。}ADTDynamicSearchTable二、实验内容、步骤和结果一：实验内容：（1）通过线性表对一组数据中的某个数据进行查找；（2）对该组数据进行从小到大的顺序进行排序；二：实验步骤：（1）新建一个txt的文本文档；（2）在文本文档中输入所需程序；（3）调试并运行；（4）任意输入不同的10个数，最后一个数为-1，回车；（5）得到所需结果并截图。输入的程序如下：#include<stdlib.h>#include"stdio.h"typedefstructnode{intdata;structnode*next;}LNode;LNode*create(){intx,n=0;LNode*h,*p,*q;h=(LNode*)malloc(sizeof(LNode));q=h;scanf("%d",&x);while(x!=-1) { p=(LNode*)malloc(sizeof(LNode)); p->data=x; q->next=p; q=p; n++; scanf("%d",&x); } q->next='\0'; h->data=n;returnh;}/*建立线性表并在里面输入元素并计数*/voidout(LNode*h){LNode*p;p=h;printf("\n");while(p!='\0'){printf("%6d",p->data);p=p->next;}}/*如果存在则输出*/LNode*search(LNode*h,inti){LNode*p;intj=1;p=h->next;while((p!='\0')&&(j<i)){p=p->next;j++;}if((p=='\0')||j>i)return(NULL);returnp;}/*查找已存在元素*/sort(LNode*h){intx;LNode*p,*q,*min;p=h->next;while(p){min=p;q=p->next;while(q){if(q->data<min->data)min=q;q=q->next;}if(min!=p){x=p->data;p->data=min->data;min->data=x;}p=p->next;}}/*排序*/main(){LNode*h,*p;h=create();out(h);p=search(h,5);if(p!=NULL)printf("\n%d",p->data);elseprintf("\ndontfind!");sort(h);out(h);}/*运用上述函数输出*/三：实验截图：运行程序，输入10个数：7,12,16,28,32,50,68,82,98，-1。得到的结果截图如下。三、实验小结1、实验中出现过的问题（或错误）、原因分析（1）写程序时常常不知道下一步该写什么，原因是对课本的基本知识的不熟悉和对程序内容的模糊；（2）写好程序后运行，发现了很多错误，有少了分号、忘记定义等，原因是编程时不够认真，粗心大意；（3）调试好程序成功运行，发现程序不够完善美观，原因是对这方面的知识了解的还是太少。2、保证实验成功的关键问题（1）