头歌 数据结构 实验七——数据查找与排序

前言：

这次一下更新两个实验，都是很简单的东西，就一些简单的排序和查找，也就不解释啦。

查找

第1关：查找特定的数据元素-顺序查找

#include <stdio.h>

int find_pos(int data[] ,int n, int key)
{//在数组data中查找给定数据key,n表示数组中数据元素的个数
 /*------------begin-----------------*/
  for(int i=0;i<n;i++){
    if(data[i]==key){
      return i;
    }
  }
  return -1;
 /*------------end-----------------*/
}

int main(void)
{
int a[]={99,23,5,189,-1,66};
int x;
scanf("%d",&x);
//此处填写代码，调用find_pos，在a数组中查找给定数据x的位置，并输出函数返回的数据元素的位置
  /*------------begin-----------------*/
  int p=find_pos(a,6,x);
  printf("%d",p);
 /*------------end-----------------*/   
    
return 1;
}

第2关：查找-进阶(二分查找）

#include <stdio.h>

int find_pos(int data[] ,int n, int key)
{//在数组data中查找给定数据key，n是数组中数据元素的个数，返回值是数据元素比较的次数.
    
 /*------------begin-----------------*/
  int low=0,high=n-1,count=0;
  if(key<data[0]||key>data[n-1]){
    return count;
  }
  while(low<=high){
    int mid=(low+high)/2;
    if(key==data[mid]){
      count++;
      return count;
    }
    if(key<data[mid]){
      high=mid-1;
      count++;
    }else if(key>data[mid]){
      low=mid+1;
      count++;
    }
  }
  return count;
 /*------------end-----------------*/
}

int main(void)
{
int a[]={-1,15,66,99,122,189};
int x;
scanf("%d",&x);
//此处填写代码，调用find_pos，在a数组中查找给定数据x的位置，并输出函数返回值
  /*------------begin-----------------*/
  int p=find_pos(a,6,x);
  printf("%d",p);
 /*------------end-----------------*/   
    
return 1;
}

第3关：查找进阶

#include <stdio.h>
void compute(int data[],int n, int target)
{//在此处填写代码，在data数组中查找是否存在两个元素之和为target，并按要求输出
  /*-----------begin---------------*/ 
  int a=-1,b=-1;
  for(int i=0;i<n-1;i++){
    for(int j=i+1;j<n;j++){
      if(data[i]+data[j]==target){
        a=i;b=j;
      }
    }
  }
  printf("%d,%d",a,b);
 /*-----------end---------------*/ 

}

int main(void)
{
    int a[]={-3,2,5,9,15,32};
    int x ;
    scanf("%d",&x);
    compute(a,6,x);
}

排序

第1关：冒泡排序

#include <stdio.h>
void print(int a[] ,int n)
{//输出数组元素，数字之间以一个空格为界，输出结束后换一行
  for(int i=0;i<n;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}

void bubbleSort(int a[] ,int n) //对数组a中的n个元素进行排序，调用print函数输出每趟排序后的结果
{
  int m=n,flag=1,t=0;
  while(flag==1&&m>1){
    flag=0;
    t++;
    for(int i=0;i<m-1;i++){
      if(a[i]>a[i+1]){
        flag=1;
        int tmp=a[i];
        a[i]=a[i+1];
        a[i+1]=tmp;
      }
    }
    if(flag==1||t==1){
      print(a,n);
    }
    m--;
  }



}


int main(void)
{
  int num ;
  scanf("%d",&num);
  int data[num];
  for(int i=0;i<num;i++)
    scanf("%d",&data[i]);

  bubbleSort(data ,num);
}

第2关：快速排序

#include <stdio.h>
void print(int a[] ,int n)
{//输出数组元素，数字之间以一个空格为界，输出结束后换一行
  for(int i=0;i<n;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}
void qSort(int a[] ,int left, int right) //
{
  int flag=0,tleft=left,tright=right;
  if(tleft<tright){
    int tmp=a[tleft];
    while(tleft<tright){
      while(tleft<tright&&a[tright]>=tmp){
        tright--;
      }
      a[tleft]=a[tright];
      while(tleft<tright&&a[tleft]<=tmp){
        tleft++;
      }
      a[tright]=a[tleft];
    }
    a[tleft]=tmp;
    flag=tleft;
    print(a,right+1);
    qSort(a,left,flag-1);
    qSort(a,flag+1,right);
  }
}
int main(void)
{
  int num ;
  scanf("%d",&num);
  int data[num];
  for(int i=0;i<num;i++)
    scanf("%d",&data[i]);

  qSort(data ,0,num-1);
  print(data,num);
}