数据结构查找实验

数据结构实验报告

课程 数据结构实验 实验名称查找

系 别 计算机学院专业班级组别_____________

一.实验目的：

1. 掌握顺序查找，二分查找的算法 2. 能运用线性表的查找方法解决实际问题

二.实验内容

（－）实验题目一：写给出一个无序表A中采用顺序查找算法查找值为x的元素的算法 1.要点分析：

顺序查找首先从表的先端开始，依次与给定值x进行比较，直达找到与其相等的元素值，返回该元素值的下标，查找成功。否则给出查找失败信息。

2.程序源代码： #include #define N 10

int search(int A[],int x,int n) {

int i=0;

while(i

void main() {

int a[N]={2,38,42,44,25,12,3,1,23,89},d,i,k;

i++;

if(i>=n)

return -1;

else

return i;

printf(\数组下标:\\n\for(i=0;i

printf(\

printf(\

printf(\数组值:\\n\for(i=0;i

printf(\

printf(\输入要查找的值：\

scanf(\

k=search(a,d,N); if(k>=0)

printf(\

else

printf(\未找到\\n\}

3.实验结果

（二）实验题目二：编写一个算法，利用二分查找算法在一个有序表中插入一个元素x，并保持表的有序性。 1．要点分析：

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

2．程序源代码： #include #include #define maxnum 100

int input(int *); //输入数据 int search(int *,int,int); //查找插入位置 void plug(int *,int,int); //插入数据 void main() {

int data[maxnum],m;

}

int insert=1; m=input(data);

printf(\请输入要插入的数据: \\n\输入插入的数据

scanf(\输入插入的数据存放在data数组0号位置 insert=search(data,1,m); //找到数据要插入的位置 plug(data,insert,m); //运用递归的方法插入数据 printf(\最后结果: \\n\

for(insert=1;insert<=m+1;insert++)

printf(\

getchar();

int input(int * data) { }

int search(int *data,int low,int high) {

int mid;

if(low>high) //没有找到插入位置

return low; int i,m;

printf(\请输入该有序表的长度: \\n\scanf(\

printf(\请按大小顺序输入%d个数据 \\n\for(i=1;i<=m;i++)

scanf(\

return m;

else {

mid=(low+high)/2;

if(*(data+mid)== *data)

return mid;

else if(*(data+mid)<*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.实验结果

移动并插入数据