实验五-查找算法应用

实验报告

学院（系）名称：计算机与通信工程学院

姓名 班级 * * 2015级*班 课程名称 实验时间 考核标准 成绩栏 实验过程 25分 程序运行 20分 □功能完善, □功能不全 □有小错 □无法运行 学号 实验项目 **** **** 专业 计算机科学与技术 实验五： 查找算法应用 课程代码 实验地点 特色 功能 5分 考勤违纪情况 5分 数据结构与算法 年 月 日第节 回答问题 15分 ○正确 ○基本正确 ○有提示 ○无法回答 实验报告 30分 ○完整 ○较完整 ○一般 ○内容极少 ○无报告 0661013 7-*** 成绩 其它批改意见: 考核内容 评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。 ○有 ○无 ○有 ○无 教师签字： ,. 一、实验目的 实验目的：理解二叉排序树、AVL 树的查找、插入、删除、建立算法的思想及程序实现；掌握散列 存储结构的思想，能选择合适散列函数，实现不同冲突处理方法的散列表的查找、建立。能运用所 学查找结构与算法等解决实际问题。 二、实验题目与要求 1.折半查找算法 1）问题描述：从键盘读入一串整数和一个待查关键字，查找在该整数串中是否有这个待查关键 字。如果有，输出它在整数串中的位置；如果没有，输出-1 2）实验要求： ①利用折半查找算法查找 ②用递归和非递归两种方式实现折半查找算法 3) 实现提示： ①递归实现参考书上折半查找算法的实现 ②非递归算法利用栈实现 2.构造二叉排序树，并进行中序遍历（实验类型：综合型） 1）问题描述：从键盘读入一串整数构造一棵二叉排序树，并对得到的二叉排序树进行中序遍历， 得到有序序列。 2）实验要求：该二叉排序树以二叉链表存储 3）实现提示：二叉排序树的构成，可从空的二叉树开始，每输入一个结点数据，就建立一个新 结点插入到当前已生成的二叉排序树中，所以它的主要操作是二叉排序树插入运算。在二叉排序树 中插入新结点，只要保证插入后仍符合二叉排序树的定义即可。 3．哈希表查找 1）问题描述：针对某个集体的“人名”构造哈希表，解决按“人名”进行查找的索引结构。 2）实验要求：要求表的平均查找长度不超过 R（R 可以从键盘输入确定），完成相应的建表和 查表程序。 4. 拼写检查 ,. 1）问题描述：现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词， 有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词 A 与单词 B 相 似的情况有三种： ① 删除单词 A 的一个字母后得到单词 B； ② 用任意一个字母替换单词 A 的一个字母后得到单词 B； ③ 在单词 A 的任意位置增加一个字母后得到单词 B。 2）实验要求：发现词典中与给定单词相同或相似的单词。 实验过程与实验结果 应包括如下主要内容： ➢ 数据结构定义 ➢ 数表的查找方法通常适用于动态集合。动态集合的特点是集合结构本身在查找过程中动态生成，即对于给定值k，若集合中存在关键字等于k的记录，则查找成功，否则插入关键字为k的新记录。 ➢ 二叉排序树，又叫二叉查找树或二叉搜索树。它或者是一棵空树，或者是一棵具有如下特征的非空二叉树： ➢ 1）若它的左子树非空，则左子树上所有节点的关键字均小于根节点的关键字。 ➢ 2）若它的右子树非空，则右子树上所有节点的关键字均大于根节点的关键字。 ➢ 3）左、右子树也分别是二叉排序树。 ➢ 平衡二叉树的定义是：若一棵二叉排序树中每个节点的左、右子树的高度之差的绝对值不超过1，则称这样的二叉排序树为平衡二叉树。 ➢ 算法设计思路简介 ➢ 1、 ➢ 数据有序，用折半查找法，通过即可快速找到关键字。 ➢ 2、 ➢ 二叉树表实际上就是个二叉树，就像建立一个普通的二叉树一样建立树，只是在插入节点的时候要和当前节点的值比较，若当前节点为空则插入当前节点；否则，若小于当前值则插入左子树大于当前节点就插入右子树。对建立好的树进行中序遍历即可得到有序序列。 ➢ 3、 ➢ 人的姓一般有很大可能性相同，但是人名的第二个字一般是不同的，既然人名示例是拼音形式姑且认为第二个字母即为第二个字。将其ASCLL码模49作为哈希函数，将各人名分类存,. 在不同的链表中，提高查询效率。 ➢ 算法描述：可以用自然语言、伪代码或流程图等方式 4、 以单词中字母的数目为标准将单词分类，若字母数想等或相差一则进行细致的比较（下面有详细描述），否则根本不相似。 1、 mid = (low+high)/2 low = 1,high = n 输入a[i],key i = 1,2,3,…,n 开始 ,. = mid = key? ≠ 是 k < a[mid]? 否 是 low <= high? 否 输出-1 return -1 return mid high = mid-1 low = mid+1 输出mid ,. 2、 (1)创建普通二叉树节点。 (2)输入要插入的值k。 结束 (3)将k插入二叉树节点中，若当前节点为空则申请节点空间并将k存入当前节点的data域中，令其左右子树均为空;若当前节点不为空且k小于当前节点的data值，则将k存入当前节点的左子树中去，若当前节点不为空且k大于当前节点的data值，则将k存入当前节点的右子树中去。 (4)中序遍历此二叉树。 3、 ➢ (1)录入人名。 ➢ (2)以人名的第二个字母的ASCLL码模49（所用数组空间为50），得到的数作为下标，将此人名存入相应的邻接表中。 ➢ (3)输入待查人名。 ➢ (4)以人名的第二个字母的ASCLL码模49得到的数字为下标找到相应的链表，若链表为空则表明待查人名不在名单中，输出0；若不为空，则与链表中的每一个名字做比较，入股在下标对应的整个链表中都找不到此名字则说明待查人名不在名单中，输出0，否则表明待查人名在名单中，输出1。 4、 (1)输入单词列表并存入字典中。 (2)输入待查单词。 (3)将待查单词和字典中的每个单词做比较。 ,. (3)计算字典中单词列表中每个单词的长度和待查单词的长度。分三种情况： 若字典中单词的长度等于待查单词的长度，将字典中单词的每个字母和待查单词的每个字母做比较，若相同的字母数和单词长度相同则说明两单词完全相同，若或比人名长度少一则说明两单词只有一个字母不同属于替换一个字母就相同的情况。两种情况均打印1. 若字典中的单词长度等于待查单词长度减一，将字典中单词的每个字母和待查单词的每个字母作比较，若相同字母数为字典中单词的长度，则说明待查单词与字典中的单词相似，只是多了一个字母，打印1. 若字典中单词长度等于待查单词长度加一，将字典中的每个字母和待查单词的每个字母作比较，若相同字母数为字典中单词长度减一，则说明待查单词与字典中的单词相似，只是少了一个字母，打印1. 其余情况均不相似，打印0. ➢ 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ➢ 1、 ➢ ➢ ➢ 2、 ➢ ,. ➢ ➢ 3、 ➢ ➢ 4、 ➢ ➢ 算法时间复杂度分析 ➢ 1、 ➢ O(log2n). ➢ 2、 ➢ 最差情况（单枝树）O(n) ➢ 一般情况O(log2n) ,. ➢ 3、 ➢ O(1) ➢ 4、 ➢ O(mn) ➢ m:字典中的单词数 ➢ n:待查单词数 四、收获与体会 之前只知道查找这回事，以为以现在计算机的性能查找已经变得很方便了。跟戴老师学习了查找之后才发现大数据的可怕，无论多少条记录我们都希望在几秒内完成。那么在短时间内计算机性能无法大幅度提高的前提下就要考虑查找的算法了(其实就算计算机性能再好，优化算法也能提高查找效率)。 顺序查找肯定是不学都会，折半查找之前也听说过，如何让查找表变得有序也是让人头疼的事。就说这个散列查找，竟然能达到O(1)阶的查找效率，真让人感叹人类的智慧了。 做完了图那章的实验，感觉这次实验简单多了。数据结构真的是越来越有趣了，慢慢感受到了编程的魅力。 五、源代码清单 1、 #include using namespace std; int binarysearch(int array[],int Key,int N) { int low = 1; int high = N; int mid; while(low <= high) ,. } { } return -1; mid = (low+high)/2; //cout << \"mid:\" << mid << endl; if(array[mid] == Key) return mid; else if(Key < array[mid]) high = mid-1; else low = mid+1; int main() { } int a[20] = {0}; int n,key,result; cin >> n; cin >> key; for(int i = 1;i <=n;i++) cin >> a[i]; result = binarysearch(a,key,n); cout << result; return 0; 2、 #include ,. using namespace std; int count = 0; int N = 0; typedef struct BitNode { int data; struct BitNode *lchild,*rchild; }BitNode,*BitTree; void insert(BitTree &T,int k) { } void InOrder(BitNode *T) { if(T == NULL) return; InOrder(T->lchild); if(T == NULL) { } else if(k < T->data) insert(T->lchild,k); else if(k > T->data) insert(T->rchild,k); else if(k == T->data) insert(T->lchild,k); T = (BitNode*)malloc(sizeof(BitNode)); T->data = k; T->lchild = T->rchild = NULL; ,. } cout << T->data; count++; //cout << \"N = \" << N << endl; //cout << \"count = \" << count << endl; if(count < N) cout << \" \"; InOrder(T->rchild); int main() { BitNode *root; root = NULL; int a[20] = {0}; for(int j = 0;j < 20;j++) { } int i = 0; cin >> a[j]; N++; if(a[j] == -1) { } N--; break; ,. } while(a[i] != -1) { } //cout << \"haha\" << endl; InOrder(root); count = 0; N = 0; return 0; insert(root,a[i]); i++; 3、 #include #include using namespace std; typedef struct Hash { char data[50]; struct Hash *next; }Hash; typedef struct { int data; struct Hash *next; ,. }FirstHash[30]; int main() { int n,q; int counts; cin >> n; cin >> q; char name[50][50]; char checkname[50][50]; FirstHash *h; h = (FirstHash*)malloc(sizeof(FirstHash[50])); for(int i = 0;i < 50;i++) { } for(int i = 0;i < n;i++) { cin >> name[i]; //cout << \"name[i][1] = \" << name[i][1] << endl; counts = (int)name[i][1] % 49; //cout << \"counts = \" << counts << endl; Hash *hash = (Hash*)malloc(sizeof(Hash)); h[i]->data = i; h[i]->next = NULL; ,. } strcpy(hash->data,name[i]); //cout << \"hash->data:\" << hash->data << endl; hash->next = h[counts]->next; h[counts]->next = hash; //以°?上¦?程¨¬序¨°没?问¨º题¬a for(int i = 0;i < q;i++) { } for(int i = 0;i < q;i++) { counts = (int)checkname[i][1] % 49; if(h[counts]->next == NULL) else { Hash *temp = h[counts]->next; while(temp!= NULL && strcmp(temp->data,checkname[i]) != 0) { } if(temp == NULL) cout << 0 << endl; temp = temp->next; cout << 0 << endl; cin >>checkname[i]; ,. } } } else cout << 1 << endl; return 0; 4、 #include using namespace std; char Dic[50][50]; char Check[50][50]; int getLength(char array[])//得到单词的长度 { } int research(char array1[],char array2[])//字典,待查词汇 ，字典中的某个单词与某个待查单词是否相似 { int count1 = 0; int i = 0; while(array[i] != '\\0') { } return i; i++; ,. int count2 = 0; int simble = 0; count1 = getLength(array1); count2 = getLength(array2); // cout << \"count1 = \" << count1 << endl; // cout << \"count2 = \" << count2 << endl; if(count1 == count2)//单词长度相等，替换任一字母 { } else if(count1 == count2-1)//比字典长度长1 { simble = 0; simble = 0; int i = 0; while(i < count1) { } if(simble >= count1-1) return 1; else return 0; if(array1[i] == array2[i]) simble++; i++; ,. } int i = 0,j = 0; while(j < count2 && i < count1) { } if(simble >= count1) return 1; else return 0; if(array1[i] == array2[j]) { } j++; simble++; i++; else if(count1 == count2+1)//比字典长度短1 { int i = 0,j = 0; simble = 0; while(i < count1 && j < count2) { if(array1[i] == array2[j]) { j++; ,. } } } } simble++; i++; if(simble >= count1-1) return 1; else return 0; else { } return 0; int main() { int n = 0;//字典中的单词数量 int q = 0;//待查单词数量 int count = 0;//字典中的单词与某个待查单词相似的数目 cin >> n; cin >> q; for(int i = 0;i < n;i++)//输入字典单词 { cin >> Dic[i]; ,. } } for(int j = 0;j < q;j++)//输入待查单词 { } for(int i = 0;i < q;i++)//将i号待查单词与字典中的每一个单词进行比较 { } return 0; count = 0; for(int j = 0;j < n;j++) { } if(count == 0) cout << 0 << endl; count += research(Dic[j],Check[i]); cin >> Check[j]; else cout << 1 << endl;

,.