折半查找和快速排序

数据结构

实验项目 名称 实验 目的及要求

折半查找和快速排序查找 目的：是同学们理解并掌握折半查找和快速排序查找法 要求：根据所学的内容进行实验

实验 内容

折半查找和快速排序查找

1、

折半查找

#include<stdio.h> #include<malloc.h>实验步骤

typedef int KeyType; typedef struct{ KeyType key; }ElemType; typedef struct{ ElemType *elem; int length; }SSTable; int Search_Sq(SSTable ST,KeyType key){ ST.elem[0].key=key; for(int i=ST.length;ST.elem[i].key!=key;--i); return i; }

数据结构

int BinSearch(SSTable ST,KeyType key){ int low,high,mid; low=1; high=ST.length; while(low<=high){ mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].key>key) high=mid-1; else low=mid+1; } return 0; } void main(){ KeyType a[]={0,13,24,35,32,65,19,7,74,20,38}; SSTable T; T.elem=(ElemType *)malloc(11*sizeof(ElemType)); T.le ngth=10; for(int i=1;i<=10;i++) T.elem[i].key=a[i]; printf("要找的元素的位置为%d\n",Search_Sq(T,35));

数据结构

SSTable S; S.elem=(ElemType *)malloc(11*sizeof(ElemType)); S.length=10; KeyType b[]={0,2,4,6,8,10,12,14,16,18,20}; for(int k=1;k<=10;k++) S.elem[k].key=b[k]; printf("要进行折半查找的元素的位置为%d\n",BinSearch(S,10)); } 2、 #include<stdio.h> int a[]={11,54,7,62,85,1,39,78,9,5,21,13,98,18,80,16}; int Partition(int i, int j) { int low = a[i]; while (i < j) { while ((i < j) && (a[j] > low)) { j--; } a[i] = a[j]; while ((i < j) && (a[i] < low))

数据结构

{ i++; } a[j] = a[i]; } a[i] = low; return i; } void QuickSort( int left, int right) { if (left < right) { int pivotpos = Partition(left, right); QuickSort( left, pivotpos-1); QuickSort( pivotpos+1, right); } } int main() { printf("排序前： "); for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++) {

数据结构

printf("%d ", a[i]); } printf("\n"); QuickSort( 0, sizeof(a)/sizeof(a[0])-1); printf("排序后: "); for(i = 0; i < sizeof(a)/sizeof(a[0]); i++) { printf("%d ",a[i]); } printf("\n"); return 0; }

实验环境

Microsoft Visual C++

实验结果与 分析

1、 做到的是查找要找的数的位 置，分别使用了顺序查找和折半查找的方法。

2、

在

不理解的情况下，与同学交流，在网上查找资料，虽然懂的不是很多，但也 学到了些。

数据结构

注：可根据实际情况加页