数据实验四程序代码 中国矿业大学.doc

中国矿业大学计算机学院实验报告课程名称 ：数据结构 实验名称 ：搜索班级 ： 姓名 ：实验报告要求：一、实验目的 1 熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种存储结构下实现2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法3 熟练掌握散列表的特点及构造方法二、实验内容与代码 基本题1、实现基于有序顺序表的折半搜索。程序代码：#include stdafx.h#include #define MaxSize 100using namespace std;/ 排序连续顺序文件的折半查找方法int Bin_Search(int key,int n,int k)int iLow = 1,iHigh = n,iMid = 0;while(iLow keyiMid)iLow = iMid + 1;/ 查找范围缩小到后半部分；elseiHigh = iMid - 1;/ 查找范围缩小到后半部分;return 0;int main(int argc,char* argv)cout 折半查找的实例，我们用整形数组来调试： endl;int iArrMaxSize = 0;int iNum1 = 0,iNum;cout 请输入你想查找的数组的长度： iNum1;cout 请输入一组数字，按照从小到大的顺序排列： endl;for (int i = 0;i iArri;cout 请输入你想搜索的整数的值？ iNum;cout 该整数的位置为: Bin_Search(iArr,iNum1,iNum) + 1 endl;return 0;程序运行的结果：2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜索程序并调试。程序代码：/ 2、设单链表的结点是按关键字的值从小到大排列的，/*试写出对此表的搜索程序并调试。*/ database.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include using namespace std;typedef struct NodeNode* next;int iData;LNode,*LinkList;/ 创建一个节点数为n的线性链表;LinkList Creat(int n)LinkList r, p = NULL;LinkList head = NULL;int num = 0;for (int i = 0;i num;p = (LinkList)malloc(sizeof(LNode);p-iData = num;p-next = NULL;if (head = NULL)head = p;elser-next = p;r = p;return head;/ 确定元素item在线性表中的位置;LinkList Locate(LinkList& list,int item)if (list != NULL)LinkList p = list;while(p!=NULL & p-iData != item)p = p-next;return p;/ 在线性非空链表的第一个位置插入一个链接点;void InsertHead(LinkList& list,int item)if (list != NULL)LinkList p = NULL;p = (LinkList)malloc(sizeof(LNode);p-iData = item;p-next = list;list = p;/ 在非空线性链表的末尾插入一个元素为item的链接点;void InsertTail(LinkList& list,int item)if (list != NULL)LinkList r,p = NULL;p = (LinkList)malloc(sizeof(LNode);p-iData = item;r = list;while(r != NULL)r = r-next;p-next = NULL;r-next = p;/ 删除线性链表中数据域值为item的所有链接点;/ 删除的位置不同处理的结果不相同。如果处理的位置在第一个位置，则需要和在第二个位置之后的区分;void DeleteItem(LinkList& list,int item)if (list != NULL)LinkList p,q = list;/ 从第二个链接点开始遍历，满足条件进行如下的操作;p = list-next;while(p != NULL)if (p-iData = item)q-next = p-next;free(p);p = q-next;elseq = p;p = p-next;/ 若第一个节点满足条件则进行如下的操作;if (list-iData = item)q = list;list = list-next;free(q);int main()cout 请输入你想建立线性表的长度： a;LinkList p = Creat(a);cout 请输入一个你想查找的数字： a;cout Locate(p,a) endl;return 0;程序运行结果：加强题 1、若输入 12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存储，散列函数为H(n)=n/2，请设计实现程序并调试。程序代码：#include stdafx.h#include using namespace std;/ 散列表查找算法的实现#define SUCCESS 1#define UNSUCCESS 0#define HASHSIZE 12 / 定义散列表长为数组的长度#define NULLKEY -32768typedef struct int* elem;/ 数组元素存储基址，动态分配数组;int count;/ 当前元素个数；HashTable;int iLenHashTable;/ 散列表表长，全局变量;/ 对初始化散列表int InitiHashTable(HashTable* Head)iLenHashTable = HASHSIZE;Head-count = iLenHashTable;Head-elem = (int*)malloc(iLenHashTable * sizeof(int);for (int i = 0;i elemi = NULLKEY;return 1;/ 定义散列函数；int Hash(int key)return key / 2;/ 折半法;/ 插入关键字进散列表;void InsertHash(HashTable* Head,int key)int iAddr = Hash(key);/ 求散列表的地址;while(Head-elemiAddr != NULLKEY)/ 如果不为空，则发生冲突;iAddr = (iAddr + 1) % iLenHashTable;/ 开放定址法的线性探测；Head-elemiAddr = key;/ 直到有空位后插入关键字;/ 散列表中查找关键字;int SearchHash(HashTable* Head,int key,int* addr)*addr = Hash(key);/ 求散列表的地址;while(Head-elem*addr != key)/ 如果不为空，则发生冲突;*addr = (*addr + 1) % iLenHashTable;if (Head-elem*addr = NULLKEY | *addr = Hash(key)return UNS