数据结构：查找实验(共9页)

1、精选优质文档-倾情为你奉上数据结构实验报告课程 数据结构实验 实验名称 查找 系 别 计算机学院 专业班级 组别_一. 实验目的：1. 掌握顺序查找，二分查找的算法2. 能运用线性表的查找方法解决实际问题二. 实验内容（）实验题目一：写给出一个无序表A中采用顺序查找算法查找值为x的元素的算法1.要点分析：顺序查找首先从表的先端开始，依次与给定值x进行比较，直达找到与其相等的元素值，返回该元素值的下标，查找成功。否则给出查找失败信息。2.程序源代码：#include<stdio.h>#define N 10int search(int A,int x,int n)int i=0; w

2、hile(i<n&&Ai!=x) /找遍且找到i+;if(i>=n)return -1;elsereturn i;void main() int aN=2,38,42,44,25,12,3,1,23,89,d,i,k;printf("A数组下标:n");for(i=0;i<N;i+)printf("%d ",i);printf("n");printf("A数组值:n");for(i=0;i<N;i+)printf("%d ",ai);printf(&quo

3、t;n输入要查找的值：");scanf("%d",&d);k=search(a,d,N);if(k>=0)printf("a%d=%dn",k,d);else printf("%d未找到n",d);3.实验结果（2） 实验题目二：编写一个算法，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。1 要点分析：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查

4、找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。2 程序源代码：#include <stdio.h> #include <string.h>#define maxnum 100int input(int *); /输入数据int search(int *,int,int); /查找插入位置void plug(int *,int,int); /插入数据void main()int datamaxnum,m;int insert=1;m=input(data);printf("请输入要插入

5、的数据: n"); /输入插入的数据scanf("%d",data); /输入插入的数据存放在data数组0号位置insert=search(data,1,m); /找到数据要插入的位置plug(data,insert,m); /运用递归的方法插入数据printf("最后结果: n");for(insert=1;insert<=m+1;insert+)printf("%d ",*(data+insert);getchar();int input(int * data)int i,m;printf("请输入该有

6、序表的长度: n");scanf("%d",&m);printf("请按大小顺序输入%d个数据 n",m);for(i=1;i<=m;i+)scanf("%d",data+i);return m;int search(int *data,int low,int high)int mid;if(low>high) /没有找到插入位置return low;elsemid=(low+high)/2;if(*(data+mid)= *data)return mid;else if(*(data+mid)<*

7、data)low=mid+1;else if(*(data+mid)>*data)high=mid-1;search(data,low,high);void plug(int *data,int insert,int m) /移动并插入数据int i;for(i=m;i>=insert;i-)*(data+i+1)=*(data+i);*(data+insert)=*data;3.实验结果（三）实验题目：设计一个算法，读入一串整数，构造其对应的二叉排序树1.要点分析二叉排序树的递归式定义。二叉排序树又称二叉查找树，它可以是一棵空树，若非空时具有下述性质： 1、若根结点的左子树非空，

8、则左子树上所有结点的关键字值均小于等于根结点的关键字值。 2、若根结点的右子树非空，则右子树上所有结点的关键字值均大于等于根结点的关键字值。 3、根结点的左、右子树也分别为二叉排序树。二叉排序树建立说明：当需要插入一个节点到二叉排序树时，需要先找到它的父节点。其实 它就是用插入的节点不断的和每一个节点比较（第一次当然是和根节点比较啦），如果小于等于则进入左边子树，再与左边子树的根节点比较，直到找到它要放的位置，否则进入右子树，进行上述操作2.源程序代码#include<stdio.h>#include<malloc.h>typedef struct node /二叉排序

9、树的结点类型int key;struct node *lchild,*rchild;BSTNode;typedef BSTNode *BSTree;void insertBST(BSTree *prt,int key) BSTNode *f,*p=*prt;while(p) / 判断数据插入的位置if(p->key=key) / 树中已有此节点无需插入 return;f=p;p=(key<(p->key)?p->lchild:p->rchild; p=(BSTNode *)malloc(sizeof(BSTNode); /建立新的结点p->key=key;p

10、->lchild=p->rchild=NULL;if(*prt=NULL) *prt=p;else if(key<f->key)f->lchild=p;elsef->rchild=p;BSTree createBST(void) BSTree T=NULL;int key;printf("请输入根节点n"); /先建立一个根节点scanf("%d",&key);while(key)insertBST(&T,key);printf("请输入一个数据 以0结束：");scanf("%d",&key); return T;void inorder(BSTree T) /中序遍历if(T)inorder(T->lchild);printf("%3d ",T->key);inorder(T->rchild);void main()BSTree T;T=createBST();printf("中序遍历结果：n")