当前位置：文档之家 › 数据结构C语言实现二分查找

数据结构C语言实现二分查找

  • 格式：doc
  • 大小：46.50 KB
  • 文档页数：7

实验课题：【用C描述课本的同学】有以下结构体构成的数组：struct StudentInfo{ char ID[10];char * name;float score;}StuInfo[12]={{"0800301105", "JACK", 95},{"0800201505", "LUN", 85},{"0400820115", "MARY", 75.5},{"0400850122", "KATE", 78.9},{"0500201011", "LILI", 88},{"0800401105", "JACK", 96},{"0600830105", "JAN", 98.4},{"0952520012", "SAM", 75},{"9721000045", "OSCAR", 64},{"0700301105", "JACK", 97},{"0458003312", "ZOE", 68.9},{"0400830211", "BOBI", 87.6}};对数组StuInfo按照学号（ID）递增排序，然后用二分查找的方法进行学号查找，若找到则输出该学生的全部信息，若找不到相应记录也给出提示；接下来，对该数组按照学分绩（score）递减排序后，使用二分查找法以学分绩作关键字进行查找。

用C++版教科书的同学：对MyBirds分别以name和ID为关键字排序，然后进行二分查找。

实验程序1：#include<stdio.h>#include<string.h>#include<malloc.h>#define cutoff (3)struct StudentInf0{ char ID[11];char * name;float score;}StuInfo[12]={{"0800301105", "JACK", 95},{"0800201505", "LUN", 85},{"0400820115", "MARY", 75.5},{"0400850122", "KATE", 78.9},{"0500201011", "LILI", 88},{"0800401105", "JACK", 96},{"0600830105", "JAN", 98.4},{"0952520012", "SAM", 75},{"9721000045", "OSCAR", 64},{"0700301105", "JACK", 97},{"0458003312", "ZOE", 68.9},{"0400830211", "BOBI", 87.6}};void dizenginsertionsort(struct StudentInf0 *m,int n){ int j,p;struct StudentInf0 tmp;for(p=1;p<n;p++){ tmp=StuInfo[p];for(j=p;j>0&&strcmp((m+j-1)->ID,tmp.ID)>0;j--)StuInfo[j]=StuInfo[j-1];StuInfo[j]=tmp;}}void dijianinsertionsort(struct StudentInf0 *m,int n){ int j,p;struct StudentInf0 tmp;for(p=1;p<n;p++){ tmp=StuInfo[p];for(j=p;j>0&&(m+j-1)->score<tmp.score;j--)StuInfo[j]=StuInfo[j-1];StuInfo[j]=tmp;}}int search(char s[],struct StudentInf0 *m){ int center,left=0,right=11;center=(left+right)/2;while(strcmp(s,(m+center)->ID)){if(left==center){ if(!strcmp(s,(m+right)->ID)){ center=right;break;}else { center=-1;printf("不存在此学号");break;}}if(strcmp(s,(m+center)->ID)>0)left=center;elseright=center;center=(left+right)/2;}return center+1;}int xuefensearch(float a,struct StudentInf0 *m){ int center,left=0,right=11;center=(left+right)/2;while(a!=(m+center)->score){if(left==center){ if(a==(m+right)->score){ center=right;break;}else { center=-1;printf("不存在此学分绩");break;}}if(a>(m+center)->score)right=center;elseleft=center;center=(left+right)/2;}return center+1;}main(){ float a;int center,l=0;char c[100];dizenginsertionsort(StuInfo,12);printf("ID升序排列所得结果:\n");while(l<12){ printf("%s %7s %3.1f",StuInfo[l].ID,StuInfo[l].name,StuInfo[l].score);printf("\n");l++;}printf("请输入需要查找的学号ID:");gets(c);center=search(c,StuInfo);if(center){ printf("存在此学号");printf("该学生的全部信息是:%s %7s %3.1f\n",StuInfo[center-1].ID,StuInfo[center-1].name,StuInfo[center-1].score);}dijianinsertionsort(StuInfo,12);printf("学分绩降序排列所得结果:\n");l=0;while(l<12){ printf("%s %7s %3.1f",StuInfo[l].ID,StuInfo[l].name,StuInfo[l].score);printf("\n");l++;}printf("请输入需要查找的学分绩:");scanf("%f",&a);center=xuefensearch(a,StuInfo);if(center){ printf("存在此学分绩");printf("该学生的全部信息是:%s %7s %3.1f",StuInfo[center-1].ID,StuInfo[center-1].name,StuInfo[center-1].score);}}实验程序2：#include<stdio.h>#include<string.h>#include<malloc.h>typedef struct StudentInfo ElementType;struct StudentInfo{ char ID[11];char * name;double score;}StuInfo[12]={{"0800301105", "JACK", 95},{"0800201505", "LUN", 85},{"0400820115", "MARY", 75.5},{"0400850122", "KATE", 78.9},{"0500201011", "LILI", 88},{"0800401105", "JACK", 96},{"0600830105", "JAN", 98.4},{"0952520012", "SAM", 75},{"9721000045", "OSCAR", 64},{"0700301105", "JACK", 97},{"0458003312", "ZOE", 68.9},{"0400830211", "BOBI", 87.6}};void InsertionSort(ElementType A[],int N){int p,j;ElementType Tmp;for(p=1;p<N;p++){Tmp=A[p];for(j=p;j>0&&strcmp(A[j-1].ID,Tmp.ID)>0;j--)A[j]=A[j-1];A[j]=Tmp;}}void BubbleSort(ElementType B[],int m) {ElementType tmp;int i,k;for(i=0;i<m;i++)for(k=0;k<m-i;k++)if(B[k].score<B[k+1].score){tmp=B[k];B[k]=B[k+1];B[k+1]=tmp;}}int Binsch(ElementType C[],int low,int high,char t[]){if(low<high){int mid=(low+high)/2;if(strcmp(t,C[mid].ID)==0) return mid;else if(strcmp(t,C[mid].ID)<0) return Binsch(C,low,mid-1,t);else return Binsch(C,mid+1,high,t);}else return -1;}int chazhao(ElementType D[],int low,int high,double h){if(low<high){int mid=(low+high)/2;if(h==D[mid].score) return mid;else if(h>D[mid].score) return chazhao(D,low,mid-1,h);else return chazhao(D,mid+1,high,h);}else return -1;}void print(){int q;printf(" 学号ID 姓名分数\n"); for(q=0;q<12;q++){printf("%-15s",StuInfo[q].ID);printf("%-10s",StuInfo[q].name);printf("%-15f",StuInfo[q].score);printf("\n");}}void main(){char array[11];int y,r;double x;printf("请输入学生的学号、姓名、分数：\n"); print();printf("\n");printf("按学号排序后的顺序：\n"); InsertionSort(StuInfo,12);print();printf("\n");printf("请输入要查找的学号：");scanf("%s",array);y=Binsch(StuInfo,0,11,array);if(y!=-1){printf("%s ",StuInfo[y].ID);printf("%s ",StuInfo[y].name);printf("%f ",StuInfo[y].score);}else printf("查找失败！");printf("\n");printf("按学分绩排序后的顺序：\n"); BubbleSort(StuInfo,12);print();printf("\n");printf("请输入要查找的学分绩：");scanf("%f",&x);r=chazhao(StuInfo,0,11,x);if(r!=-1){printf("%s ",StuInfo[r].ID);printf("%s ",StuInfo[r].name);printf("%f ",StuInfo[r].score); }else printf("查找失败！");}。

合集下载

二分查找算法（C#实现）

二分查找算法（C#实现）

⼆分查找算法（C#实现）
想了解这个算法是因为在最近⾯试的时候看到了⼆分查找算法的时候懵⽐了,所以回来就要恶补⼀下 那么什么是⼆分查找算法呢.
看名称就知道它是⼀半⼀半的找的,有点类似快速排序算法
举个例⼦就是:有⼀个数组int[] array=new int[]{1,3,4,5,6,7};我们要找6这个数
第⼀次:中间数是4 6⽐4⼤,所以下⼀次需要找4右边的数
第⼆次:中间数是6 刚好
我们来看⼀下C#的实现
public static int fen(int[] array,int low,int high,int key)
{
int middle = (low + high) / 2;
if (low>high)
{
return1;
}
else
{
if (array[middle]==key)
{
return middle;
}
else if (array[middle] > key)
{
return fen(array, low, middle - 1, key);
}
else
{
return fen(array, middle+1, high, key);
}
}
}
static void Main(string[] args)
{
int[] array = new int[] {1,2,3,4,5,6,7,8,9,10 };
var t=fen(array, 0, array.Length - 1, 9);
Console.WriteLine(t);
Console.Read();
}。

反序数组二分法查找元素c语言

反序数组二分法查找元素c语言

反序数组二分法查找元素c语言如果你要在一个已经按照递增顺序排列的反序数组中使用二分法查找元素，你需要在二分查找的基础上进行一些修改。

以下是一个使用C 语言实现的例子，演示了如何在反序数组中进行二分查找：```c#include <stdio.h>int binarySearchInReverse(int arr[], int low, int high, int target) {while (low <= high) {int mid = low + (high - low) / 2;if (arr[mid] == target) {return mid; // 元素找到，返回索引}// 判断在哪一侧递增if (arr[mid] < arr[low]) {// 右侧递增if (target > arr[mid] && target <= arr[high]) {low = mid + 1; // 在右侧继续查找} else {high = mid - 1; // 在左侧继续查找}} else {// 左侧递增if (target >= arr[low] && target < arr[mid]) {high = mid - 1; // 在左侧继续查找} else {low = mid + 1; // 在右侧继续查找}}}return -1; // 元素未找到}int main() {int arr[] = {6, 5, 4, 3, 2, 1}; // 反序数组int n = sizeof(arr) / sizeof(arr[0]);int target = 3;int result = binarySearchInReverse(arr, 0, n - 1, target);if (result != -1) {printf("Element found at index %d\n", result);} else {printf("Element not found in the array\n");}return 0;}```这个例子中的`binarySearchInReverse` 函数对标准的二分查找进行了修改，以适应反序数组。

c语言折半查找法代码

c语言折半查找法代码

c语言折半查找法代码折半查找法，也称二分查找法，是一种高效的查找算法。

它的基本思想是将有序数组分成两部分，通过比较中间元素和目标元素的大小关系，来确定目标元素在哪一部分中，然后再在该部分中继续进行查找，直到找到目标元素或者确定目标元素不存在为止。

下面是C语言实现折半查找法的代码：```#include <stdio.h>int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}int main() {int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};int n = sizeof(arr) / sizeof(arr[0]);int target = 7;int index = binarySearch(arr, 0, n - 1, target);if (index == -1) {printf("目标元素不存在\n");} else {printf("目标元素在数组中的下标为：%d\n", index);}return 0;}```在上面的代码中，binarySearch函数接收四个参数：数组arr、左边界left、右边界right和目标元素target。

它通过while循环不断缩小查找范围，直到找到目标元素或者确定目标元素不存在为止。

其中，mid表示当前查找范围的中间位置，通过比较arr[mid]和target的大小关系来确定目标元素在哪一部分中。

利用C语言编写二分查找程序

利用C语言编写二分查找程序

}
sprintf(num,"%d",y);
settextstyle(0,0,4);
drawmat(cha64K, 64,180, 10,GREEN);
drawmat(zhao64K,64,270, 10, GREEN);/*设置字符串FIND的X、Y坐标*/
outtextxy(370,30,num);
1
二分查找法，它是一种效率较高的查找方法，它充分利用了元素间的次序关系，它的基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如果x<a[n/2]，则我们只要在数组a的左半部继续搜索x。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。
{
Clr(300);
Clr(80); /*这里的三个Clr是为了把屏幕上的箭头和文字删了*/
Clr(230);
drawmat(cha64K, 64,180, 10, YELLOW);
drawmat(zhao64K, 64,270, 10, YELLOW);
settextstyle(0,0,4);
outtextxy(370,30,str1);
2.5
在指定位置显示一字符串
2.6
冒泡排序，是指计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。