数据结构查找实验报告
【篇一：数据结构查找算法实验报告】
数据结构实验报告 实验第四章：
实验: 简单查找算法
一．需求和规格说明：
查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。由于自己能力有限，本想实现其他算法，但没有实现。其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。 二．设计思想：
开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。 三．设计表示： 四．实现注释：
其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。在查找到数据的时候要想办法输出查找过程的相关信息，并统计。这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。 在
查找后对查找数据进行了统计。二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。建立了二叉树后，遍历和查找就很简单了。而哈希表，应该说自我感觉掌握的很不好，程序主要借鉴了书上和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(\\n\\n);
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;i9;i++) a[i]=0; for(i=0;in;i++) { c=arr[i]%7; printf(以下为哈希表输出\\n); int a[10]; int b,i,j,c;
if(a[c]==0)a[c]=arr[i]; else {c=(c+1)%7;j++;a[c]++;goto a;}
printf(\\n%d在哈希表的第%d位,第%d次放入哈希表\\n,arr[i],c,j); j=1;}
【篇二：数据结构(c语言版) 实验报告】
数据结构(c语言版) 实验报告
专业：计算机科学与技术 学号:_______________________ 班级:_______________________ 姓名:_______________________ 指导教师:___________________ 青岛大学信息工程学院 2014年10月 实验1
实验题目：顺序存储结构线性表的插入和删除