数据结构实验指导书(2016)(10)

if(!l)printf(\没有创建ST!\\n\

l->length=0;l->sum=3;

l->elem=(student*)malloc(3*sizeof(student)); if(!l->elem)printf(\没有创建elem!\\n\return(l); }

int place(ST *l,int c,int num) {int low,high,mid,j=-1,i; low=0;high=l->length-1; while(low<=high) {mid=(low+high)/2;

if(l->elem[mid].num>num)high=mid-1; else {j=mid;low=mid+1;}} i=j;

for(j=mid;j>=i;j--)

{if(j==-1||num>l->elem[j].num)break;

else if(num==l->elem[j].num&&c>l->elem[j].cla)break;} return(++j);}

void move(ST *l,int j) {int i;

for(i=l->length-1;i>=j;i--)

{l->elem[i+1].cla=l->elem[i].cla;

strcpy(l->elem[i+1].name,l->elem[i].name); l->elem[i+1].num=l->elem[i].num; l->elem[i+1].sex=l->elem[i].sex;

l->elem[i+1].phonenum=l->elem[i].phonenum;}}

void createlist(ST *l) {int i,j,c,num;

char nam[20],s;long p;

printf(\输入学生信息(class name num sex phonenum):\\n\for(i=0;isum;i++) {flushall();

scanf(\j=!(l->length)?0:place(l,c,num); move(l,j);

l->elem[j].cla=c;

strcpy(l->elem[j].name,nam); l->elem[j].num=num; l->elem[j].sex=s;

l->elem[j].phonenum=p;

第43页 /共58页

l->length++;}}

void searchshun(ST *l) {int num,c,i;

printf(\输入查找人的学号和班级号:\scanf(\for(i=0;i<=l->length;i++)

if(l->elem[i].num==num)break; if(i!=l->length)

printf(\em[i].num,l->elem[i].sex,l->elem[i].phonenum); else

printf(\无此人！\ }

void printlist(ST *l) {int i,j=0;

printf(\当前表中信息如下:class/name/num/sex/phonenum\\n\for(i=0;isum;i++)

{printf(\elem[i].num,l->elem[i].sex,l->elem[i].phonenum); if(++j==3){j=0;printf(\printf(\

void main() {

ST *l2; l2=initlist(); createlist(l2); printlist(l2);

printf(\用顺序查询实现class2\\n\searchshun(l2); }

实验十三二叉排序树的查找算法实现

实验预备知识：

1．理解哈希函数和哈希表。

2．掌握各种哈希函数和冲突解决办法。

第44页 /共58页

一、实验目的

1．理解动态查找表的动态生成过程； 2．掌握二叉排序树的建立和查找；

二、实验环境

⒈ 硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉ 软件：DOS或Windows操作系统+Turbo C；

三、实验要求

1．定义二叉排序树的数据结构；

2．实现二叉排序树的插入算法与查找算法，并建立二叉排序树； 3．进行数据查找和建树过程的比较。

四、实验内容

1．在自己的U盘的“姓名+学号”文件夹中创建“实验12”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。

2．已知一个个数为12的数据元素序列为{Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May, July,Jan,Mar},要求：

（1）按各数据元素的顺序（字母大小顺序）构造一棵二叉排序数，并中序打印排序结果。

（2）查找数据\是否存在。

3．已知一棵二叉排序树，其根结点的地址为 root。请编写一个程序，构造出一棵具有相同结点的满二叉树，且它同样是二叉排序树。提示：可利用中序遍历，分别找出各个结点序列的中点元素，然后重新构造一棵二叉排序树。 #include #include #include struct month { char y[5]; }y[12];

typedef struct Lnode//二叉排序树的创建，采用二叉链表 {

struct Lnode *lchild,*rchild; char data[5]; }node;

int BSTsearch(node *h, char c[5]) {

if (h==NULL) {

第45页 /共58页

return 0;

}//查找失败，返回0 else {

if(strcmp(c,h->data)==0) {

c=h->data; return 1; }

else if(strcmp(c , h->data)<0) {

return BSTsearch(h->lchild,c); } else {

return BSTsearch(h->rchild,c); } } }

void Insert(node *&h,char c[5]) {

if(h==NULL) {

node *s=(node *)malloc(sizeof(node));

strcpy(s->data,c);

s->lchild=s->rchild=NULL; h=s;

}

else if(strcmp(c,h->data)<0)

{

Insert(h->lchild,c); }

else

第46页 /共58页

{

Insert(h->rchild,c); } }

void create(node *&h) {

int n;

printf(\输入关键字个数：\\n\ scanf(\ for(int i=0;i

{

printf(\输入节点的值：\\n\ scanf(\ Insert(h,y[i].y); } }

void Print(node *h) {

int k=0;

if(h!=NULL)

{

Print(h->lchild); printf(\ Print(h->rchild); } }

void main() {

node *h=NULL; struct month m; create(h);

printf(\输入查找的元素：\\n\ scanf(\

第47页 /共58页