数据结构查找实验报告.doc

精品学习资料范文数据结构查找实验报告 篇一：数据结构查找算法实验报告 数据结构实验报告 实验第四章： 实验: 简单查找算法 一需求和规格说明： 查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。由于自己能力有限，本想实现其他算法，但没有实现。其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。 二设计思想： 开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。 三设计表示： 四实现注释： 其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。在查找到数据的时候要想办法输出查找过程的相关信息，并统计。这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。 在查找后对查找数据进行了统计。二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。建立了二叉树后，遍历和查找就很简单了。而哈希表，应该说自我感觉掌握的很不好，程序主要借鉴了书上和ppt上的代码，但感觉输出还是有问题，接下来应该进一步学习哈希表的相关知识。 其实原本还设计了其他几个查找和排序算法，但做到哈希表就感觉很困难了，因此没有继续往下做，而且程序还非常简陋，二叉树和哈希表的统计部分也比较薄弱，这也是接下来我要改进的地方。 具体代码见源代码部分。 5.详细设计表示： 6.用户手册： 程序运行后，用户首先要输入数据的个数。接下来输入一组数据并根据提示进行顺序查找，二分查找，二叉排序树查找和哈希表查找等操作，由于操作直接简单这里不再详述。 7.调试报告： 应该说在调试这个程序的过程中自己发现了很多不足，这次实验让我学到了不少东西，但应该说这个程序可实现的功能还是偏少，不太实用，接下来有待改进。 8.源代码清单和结果： #include stdio.h #define LENGTH 100 #include stdlib.h #include time.h #define INFMT %d #define OUTFMT %d /* #define NULL 0L */ #define BOOL int #define TRUE 1 #define FALSE 0 #define LEN 10000 typedef int ElemType; typedef struct BSTNode ElemType data; struct BSTNode *lchild, *rchild; BSTNode, *BSTree; typedef BSTree BiTree; /* 插入新节点 */ void Insert(BSTree *tree, ElemType item) BSTree node = (BSTree)malloc(sizeof(BSTNode); node- data = item; node- lchild = node- rchild = NULL; if (!*tree) *tree = node; else BSTree cursor = *tree; while (1) if (item cursor- data) if (NULL = cursor- lchild) cursor- lchild = node; break; cursor = cursor- lchild; else if (NULL = cursor- rchild) cursor- rchild = node; break; cursor = cursor- rchild; return; /* 查找指定值 */ BSTree Search(BSTree tree, ElemType item) BSTree cursor = tree; while (cursor) if(!T) printf( 空 return; / 打印根节点 printf( %d ,T- data); if(T- lchild |T- rchild) putchar( ( showbitree(T- lchild); / 递归显示左子树 putchar( , showbitree(T- rchild); / 递归显示右子树 putchar( ) void showbitree(BiTree T) / 递归显示二叉树的广义表形式 if (item = cursor- data) return cursor; else if ( item cursor- data) cursor = cursor- lchild; else cursor = cursor- rchild; return NULL; /* 中缀遍历 */ void Inorder(BSTree tree) BSTree cursor = tree; if (cursor) Inorder(cursor- lchild); printf(OUTFMT, cursor- data);Inorder(cursor- rchild); /* 回收资源 */ void Cleanup(BSTree tree) BSTree cursor = tree, temp = NULL; if (cursor) Cleanup(cursor- lchild); Cleanup(cursor- rchild); free(cursor); void searchtree(BSTree root) char choice; printf( 中序遍历的结果为:n Inorder(root); printf( nn ElemType item; BSTree ret; /* 二叉排序树的查找测试 */ do printf( n请输入查找数据： scanf( %d , item); getchar(); printf( Searching.n ret = Search(root, item); if (NULL = ret) printf( 查找失败！ else printf( 查找成功！ printf( n继续测试按y，退出按其它键。n choice = getchar(); while (choice= y |choice= Y Cleanup(root); searchhash(int *arr,int n) A: void SequenceSearch(int *fp,int Length); void Search(int *fp,int length);j=1; for(i=0;i i+) ai=0; for(i=0;i i+) c=arri%7; printf( 以下为哈希表输出n int a10; int b,i,j,c; if(ac=0)ac=arri; else c=(c+1)%7;j+;ac+;goto A; printf( n%d在哈希表的第%d位,第%d次放入哈希表n ,arri,c,j); j=1; 篇二：数据结构(C语言版) 实验报告 数据结构(C语言版) 实验报告 专业：计算机科学与技术 学号:_ 班级:_ 姓名:_ 指导教师:_ 青岛大学信息工程学院 2014年10月 实验1 实验题目：顺序存储结构线性表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。 程序代码: #include stdio.h #include malloc.h #include stdlib.h #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 typedef int status; typedef int ElemType; typedef struct ElemType *elem; int length; int listsize; sqlist; status initlist_sq(sqlist L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; /initList.sq status getelem_sq(sqlist L) int i=0,e,d; printf( please input how many number you want to initn scanf( %d , printf( please input the number you want to initn while(1) scanf( %d , L.elemi=e;L.length+;i+;if(i =d)break; return OK; status listdelet_sq(sqlist L) int i=0,e; int *p; int *q; printf( please input the number you want to deleten scanf( %d , for(i=0;i L.length;i+) if(L.elemi=e) p= L.elemi; q=L.elem+L.length-1;for(+p;p +p) *(p-1)=*p;-L.length;break; return OK; main() int i=0; sqlist L; initlist_sq(L); getelem_sq(L); listdelet_sq(L); while(i L.length) printf( %4d ,L.elemi); i+; 实验结果： 心得体会： 经过这次了解和掌握了线性表的逻辑结构和顺序存储结构，明白了线性表的基本算法。 实验2 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符类型的单链表，在链表中不允许有重复的字符；根据输入的字符，先找到相应的结点，后删除之。 实验主要步骤： 3、分析、理解给出的示例程序。 4、调试程序，并设计输入数据（如：A，C，E，F，H，J，Q，M），测试程序的如下功能：不允许重复字符的插入；根据输入的字符，找到相应的结点并删除。 5、修改程序： （1） 增加插入结点的功能。 （2） 建立链表的方法有“前插”、“后插”法。 程序代码: 实验结果： 心得体会： 篇三：数据结构实验报告动态查找表 数据结构实验报告 题目：动态查找表 学 院计算机学院 专 业计算机科学与技术 年级班别2010级计科4 班 学 号 3110006015 学生姓名 张法光 指导教师 张巍 成 绩 _ 2012年6月 1.题目 动态查找表的设计与实现 实现下列操作:构造空表、销毁表、查找关键字的元素、插入新元素、删除指定关键字的元素、遍历表中所有元素. 抽象数据类型定义： ADT DynamicSearchTable 数据对象 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( DT,key); 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 TraverseDSTable(DT,visit(); 初始条件：动态查找表DT存在，visit是对结点操作的应用函数。 操作结果：按某种次序对DT的每个结点调用函数visit()一次且至多一次，一旦visit() 失败，则操作失败。 ADT DynamicSearchTable 2. 存储结构定义： 公用头文件DS0.h和宏定义: #include stdio.h #include stdlib.h #define TRUE 1 /* TRUE函数值为1*/ #define FALSE 0 #define N 10 /* 数据元素个数 */ typedef int Status; /* Status为函数类型*/ typedef int KeyType; /* 关键字域为整型 */ #define EQ(a,b) (a)=(b) /*定义等于*/ #define LT(a,b) (a) (b) /*定义小于*/ 二叉排序树存储结构： 二叉排序树的类型BiTree定义如下： typedef int KeyType; /* 关键字域为整型 */ typedef struct KeyType key; int others; ElemType; /* 数据元素类型 */ typedef ElemType TElemType; typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指针 */ BiTNode,*BiTree; 3. 算法设计 /* 操作结果: 构造一个空的动态查找表DT */ Status InitDSTable(BiTree *DT) *DT=NULL; return TRUE; /* 初始条件: 动态查找表DT存在。操作结果: 销毁动态查找表DT */ void DestroyDSTable(BiTree *DT) if(*DT) if(*DT)- lchild) DestroyDSTable( (*DT)- lchild); /* 销毁左孩子子树 */ if(*DT)- rchild) DestroyDSTable( (*DT)- rchild); /* 销毁右孩子子树 */ free(*DT); *DT=NULL; /* 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素， */* 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。*/ BiTree SearchBST(BiTree T,KeyType key) if(!T)|EQ(key,T- data.key) return T; /* 查找结束 */ else if LT(key,T- data.key) /* 在左子树中继续查找 */ return SearchBST(T- lchild,key); else return SearchBST(T- rchild,key); /* 在右子树中继续查找 */ /* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 */* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 */* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */ void SearchBST1(BiTree *T,KeyType key,BiTree f,BiTree *p,Status *flag) if(!*T) /* 查找不成功 */ *p=f; *flag=FALSE; else if EQ(key,(*T)- data.key) /* 查找成功 */ *p=*T; *flag=TRUE; else if LT(key,(*T)- data.key) SearchBST1( (*T)- lchild,key,*T,p,flag); /* 递归调用-继续在左子树查找 */ else SearchBST1( (*T)- rchild,key,*T,p,flag); /* 递归调用-继续在右子树查找 */ /* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */ /* 否则返回FALSE。*/ Status InsertBST(BiTree *T, ElemType e) BiTree p,s; Status flag; SearchBST1(T,e.key,NULL, p, flag); if(!flag) /* 查找不成功 */ s=(BiTree)malloc(sizeof(BiTNode); s- data=e; s- lchild=s- rchild=NULL; if(!p) *T=s; /* 被插结点*s为新的根结点 */ else if LT(e.key,p- data.key) p- lchild=s; /* 被插结点*s为左孩子 */ else p- rchild=s; /* 被插结点*s为右孩子 */ return TRUE; else return FALSE; /* 树中已有关键字相同的结点，无需插入 */ /* 从二叉排序树中删除结点p，并重接它的左或右子树。*/ void Delete(BiTree *p) BiTree q,s; if(!(*p)- rchild) /* 右子树空则只需重接它的左子树 */ q=*p; *p=(*p)- lchild; free(q); else if(!(*p)- lchild) /* 只需重接它的右子树 */ q=*p; *p=(*p)- rchild; free(q); else /* 左右子树均不空 */ q=*p; s=(*p)- lchild; while(s- rchild) /* 转左*/ q=s; s=s- rchild;