工作报告之数据结构查找实验报告

数据结构查找实验报告

【篇一：数据结构查找算法实验报告】

数据结构实验报告 实验第四章：

实验: 简单查找算法

一．需求和规格说明：

查找算法这里主要使用了顺序查找，折半查找，二叉排序树查找和哈希表查找四种方法。由于自己能力有限，本想实现其他算法，但没有实现。其中顺序查找相对比较简单，折半查找参考了书上的算法，二叉排序树查找由于有之前做二叉树的经验，因此实现的较为顺利，哈希表感觉做的并不成功，感觉还是应该可以进一步完善，应该说还有很大的改进余地。 二．设计思想：

开始的时候提示输入一组数据。并存入一维数组中，接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序，然后利用三个标志，分别指向最大，中间和最小数据，接下来根据待查找数据和中间数据的比较不断移动标志，直至找到。二叉排序树则是先构造，构造部分花费最多的精力，比根节点数据大的结点放入根节点的右子树，比根节点数据小的放入根节点的左子树，其实完全可以利用递归实现，这里使用的循环来实现的，感觉这里可以尝试用递归。当二叉树建好后，中序遍历序列即为由小到大的有序序列，查找次数不会超过二叉树的深度。这里还使用了广义表输出二叉树，以使得更直观。哈希表则是利用给定的函数式建立索引，方便查找。 三．设计表示： 四．实现注释：

其实查找排序这部分和前面的一些知识联系的比较紧密，例如顺序表的建立和实现，顺序表节点的排序，二叉树的生成和遍历，这里主要是中序遍历。应该说有些知识点较为熟悉，但在实现的时候并不是那么顺利。在查找到数据的时候要想办法输出查找过程的相关信息，并统计。这里顺序查找和折半查找均使用了数组存储的顺序表，而二叉树则是采用了链表存储的树形结构。为了直观起见，在用户输入了数据后，分别输出已经生成的数组和树。折半查找由于只能查找有序表，因此在查找前先调用函数对数据进行了排序。 在

查找后对查找数据进行了统计。二叉排序树应该说由于有了之前二叉树的基础，并没有费太大力气，主要是在构造二叉树的时候，要对新加入的节点数据和跟数据进行比较，如果比根节点数据大则放在右子树里，如果比根节点数据小则放入左子树。建立了二叉树后，遍历和查找就很简单了。而哈希表，应该说自我感觉掌握的很不好，程序主要借鉴了书上和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

实验题目：顺序存储结构线性表的插入和删除

实验目的：

了解和掌握线性表的逻辑结构和顺序存储结构，掌握线性表的基本算法及相关的时间性能分析。 实验要求：

建立一个数据域定义为整数类型的线性表，在表中允许有重复的数据；根据输入的数据，先找到相应的存储单元，后删除之。 实验主要步骤：

1、分析、理解给出的示例程序。

2、调试程序，并设计输入一组数据（3，-5，6，8，2，-5，4，7，-9），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。 程序代码:

#includestdio.h #includemalloc.h #includestdlib.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 init\\n);

scanf(%d,d); printf(please input the number you want to init\\n); while(1) {scanf(%d,e);l.elem[i]=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 delete\\n);

scanf(%d,e); for(i=0;il.length;i++) {if(l.elem[i]==e){ p=l.elem[i]; q=l.elem+l.length-1;for(++p;p=q;++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(il.length) {printf(M,l.elem[i]); } }

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： );

操作结果：构造一个空的动态查找表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和宏定义: #includestdio.h #includestdlib.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;

本文来源：https://www.bwwdw.com/article/58la.html