验证性实验
scanf("%d",&key);
while(key != -1)
{
insertbstree(&t,key);
scanf("%d",&key);
}
return t;
}
void inorder(bstree t)
{
if (t)
{
ห้องสมุดไป่ตู้inorder(t->lchild);
printf("%d ",t->key);
typedef int KeyType;
typedef struct {
KeyType *elem; //零号单元留空
int length; //表长度
}SSTable;
int Search_Seq(SSTable ST, KeyType key){
int i;
ST.elem[0] = key; //“哨兵”
实验名称:
实验类型:验证性实验
班级:20112111
学号:2011211102
姓名:车红岫
实验日期:2013.6
1.问题描述
以下四个验证性实验都做。
(1)顺序查找验证
(2)折半查找验证
(3)二叉排序树的建立
(4)哈希表的建立
2.数据结构设计
(1)顺序查找验证
typedef struct {
KeyType *elem; //零号单元留空
(2)输入n
(3)输出结果
(4)哈希表的建立
(1)运行程序,显示菜单
(2)输入n
(3)输出结果
6.实验收获及思考
建立哈希表时没有考虑冲突处理问题,做程序时要谨慎小心。
附录:源代码
(1)顺序查找验证
#include <stdio.h>
#include <stdlib.h>
#define MAX_LENGTH 100
printf("\n哈希表如下:\n");
VistHashList(l);
return 0;
}
void InitHashList(HashArray&l, int input[], int account) //建立哈希表
{ int i = 0, j = 0, pos = 0;
ListLink q, p;
q = new Lnode; //申请结点
q->data = input[i];
q->next = NULL;
if(l.HArrary[pos].firstnode == NULL)//判断当前地址表头是否还没有元素连入
l.HArrary[pos].firstnode = q;
else
{ p = l.HArrary[pos].firstnode;
system("pause");
}
(3)二叉排序树的建立
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node
{
datatype key;
struct node *lchild,*rchild;
}bsnode;
typedef structLnode
{
int data;
structLnode *next;
}Lnode, *ListLink; //建立链表结点
typedef struct
{
intpos;
ListLinkfirstnode; //建立数组结点
}HashBox;
typedef struct
{
HashBoxHArrary[INIT_MAXSIZE]; //建立哈希数组(哈希表的地址表头)
typedef bsnode *bstree;
void insertbstree(bstree *t,datatype x)
{
bstree f,p;
p = *t;
while(p)
{
f = p;
if(x < p->key)
p = p ->lchild;
else
p = p ->rchild;
}
p =(bstree)malloc(sizeof(bsnode));
typedef structLnode
{
int data;
structLnode *next;
}Lnode, *ListLink; //建立链表结点
typedef struct
{
intpos;
ListLinkfirstnode; //建立数组结点
}HashBox;
typedef struct
{
HashBoxHArrary[INIT_MAXSIZE]; //建立哈希数组(哈希表的地址表头)
}HashArray;
3.算法设计
4.界面设计
(1)顺序查找验证
(2)折半查找验证
(3)二叉排序树的建立
(4)哈希表的建立
5. 运行、测试
(一)顺序查找验证
(1)运行程序,显示菜单
(2)输入n
(3)输出结果
(2)折半查找验证
(1)运行程序,显示菜单
(2)输入n
(3)输出结果
(3)二叉排序树的建立
(1)运行程序,显示菜单
horder(t->rchild);
printf("%d ",t->key);
}
}
int main()
{
bstree t = NULL,p;
printf("请输入一个-1为结束标记的结点序列:\n");
p = creatbstree(t);
printf("中序遍历:");
inorder(p);
printf("\n");
while (p->next != NULL)
{ p = p->next; //找到链表表尾
}
p->next = q; //将要插入的结点接入表尾
}
}
}
void VistHashList(HashArray&l) //输出哈希表
{ ListLink p;
int i;
for (i = 0; i < INIT_MAXSIZE; i++)
#define ERROR 0
void main()
{
int score[100];
int length;
int key;
printf("输入数据个数:\n");
scanf("%d",&length);
for(int i=1;i<=length;i++)
{ printf("输入第%d个元素",i);
scanf("%d",&score[i]);
}
printf("\n输入要查找的关键字\n");
scanf("%d",&key);
int low,high,mid;
low=1;
high=length;
while(low<=high)
{
mid=(low+high)/2;
if(score[mid]==key) //找到待查元素
printf("\n输入要查找的数据\n");
scanf("%d", &key);
i = Search_Seq(T,key);
printf("位置是 %d\n",i);
system("pause");
}
(2)折半查找验证
#include<stdio.h>
#include<stdlib.h>
#define OK 1
char ch = 'A';
for (i = 0; i < INIT_MAXSIZE; i++) //初始化哈希表头
{ l.HArrary[i].pos = ch++;
l.HArrary[i].firstnode = NULL;
}
for (i = 0; i < account; i++)
{ pos = input[i] % INIT_MAXSIZE; //计算元素地址
HashArray l;
printf("请输入要插入哈希表元素的个数:");
scanf("%d", &account);
printf("请输入要插入哈希表的元素:");
for (i = 0; i < account; i++)
{ scanf("%d", &input[i]);
}
InitHashList(l, input, account);
inorder(t->rchild);
}
}
void qorder(bstree t)
{ if(t)
{
printf("%d ",t->key);
qorder(t->lchild);
qorder(t->rchild);
}
}
void horder(bstree t)