数据结构查找实验报告.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( \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;i i++) a[i]=0; for(i=0;i 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），测试程序的如下功能：根据输入的数据，找到相应的存储单元并删除，显示表中所有的数据。
程序代码:
#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 init\n scanf( %d , printf( please input the number you want to init\n while(1) {scanf( %d , 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 , for(i=0;i L.length;i++) {if(L.elem[i]==e){ p= L.elem[i]; 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.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：
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;