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

1、中国矿业大学计算机学院实验报告课程名称：数据结构实验名称：搜索班级：姓名：实验报告要求：一、实验目的1熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法适合在何种 存储结构下实现2熟练掌握二叉排序树的特性、建立方法以及动态搜索算法3熟练掌握散列表的特点及构造方法二、实验内容与代码基本题1、实现基于有序顺序表的折半搜索。程序代码：#include stdafx.h#include #define MaxSize 100using namespacestd;/排序连续顺序文件的折半查找方法int Bin_Search(int key口,int n,int k)int iLow = 1

2、,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 iNuml = 0,iNum;cout 请输入你想查找的数组的长度： iNuml;cout 请输入一组数字，按照从小到大的顺序排列： endl;for (int i = 0; i i

3、Arri;cout 请输入你想搜索的整数的值？ iNum;cout 该整数的位置为: Bin_Search(iArr,iNum1,iNum) + 1 endl; return 0;程序运行的结果：iSi C ：WlMDOWSvsystei-n32cimci. exe翳森疆藤疆麋翟数组采倜诙请输入一组数字，按照从小到大的顺序排列:1234片输入你想搜索的整数的值？震整数的位置为二3请按任意键雅坡 . 2、设单链表的结点是按关键字的值从小到大排列的，试写生对此表的搜索程序并调试。程序代码：/ 2、设单链表的结点是按关键字的值从小到大排列的,/*试写出对此表的搜索程序并调试。*/ database.

4、cpp :定义控制台应用程序的入口点。/#include stdafx.h#include using namespacestd;typedef struct Node Node* 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

5、 (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

6、= (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;/删除线性链表中数据域值为i

7、tem的所有链接点；/删除的位置不同处理的结果不相同。如果处理的位置在第一个位置，则需要和在第二个 位置之后的区分；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

8、 = 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;国 C： WINDOV/S1 systenfi32cmd.exe请输入你旭建立线性表的长度:靖输入一个你想查找的数字:33B5B20福按任意键继续.-加强题1、若输入12000个不同的整数，其值介于0和19999之间，用散列法将这些数进行存储，散列函数为H(n户n/2 ,请设计实现程序并调试。程序代码

9、：#include stdafX.h#include using namespace std;/散列表查找算法的实现#define SUCCESS 1#define UNSUCCESS 0#define HASHSIZE 12/定义散列表长为数组的长度#define NULLKEY -32768typedef structint* elem;int count;HashTable;/数组元素存储基址，动态分配数组/当前元素个数；int iLenHashTable;/散列表表长，全局变量；/对初始化散列表int InitiHashTable(HashTable* Head) iLenHashTa

10、ble = 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 = (i

11、Addr + 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 UN