查找、排序综合实验(2)

《 数据结构 》实验报告 - 5 -

j=i-1;

while(l->r[0].keyr[j].key) {

l->r[j+1].key =l->r[j].key ; j=j-1; }

l->r[j+1].key=l->r[0].key; }

for(int m=1;m<=l->length;m++) cout<r[m].key<<\cout<

//冒泡排序

void bubblesort(recordlist * l) {

int i,j,x;

int change=TRUE;

for(i=1;i<=l->length && change;++i) {

change=FALSE;

for(j=1;j<=l->length-i;++j)

if(l->r[j].key>l->r[j+1].key) {

x=l->r[j].key;

l->r[j].key=l->r[j+1].key ; l->r[j+1].key=x; change=TRUE; } }

for(int m=1;m<=l->length;m++) cout<r[m].key<<\\cout<

//快速排序

int qkpass(recordlist * l,int left,int right) {

int x=l->r[left].key; int low=left; int high=right; while(low

while(lowr[high].key >=x) high--; if(low

l->r[low].key =l->r[high].key ;

《 数据结构 》实验报告 - 6 -

low++; }

while(lowr[high].key

l->r[high].key=l->r[low].key; high--; } }

l->r[low].key=x; return low; }

void qksort(recordlist *l,int low,int high) {

int pos;

if(low<=high) {

pos=qkpass(l,low,high); qksort(l,low,pos-1); qksort(l,pos+1,high); } }

//折半查找

int binsrch(recordlist * l,int k) {

int low=1,high=l->length,mid; while(low<=high) {

mid=(low+high)/2; if(k==l->r[mid].key) {

cout<<\存在该元素：\ cout<<\该元素所在位置：\ return(1); }

else if(kr[mid].key) high=mid-1; else

low=mid+1; }

cout<<\查找失败!\return(0); }

//建立平衡二叉排序树

《 数据结构 》实验报告 - 7 -

void insertbst(bstree *bst,int k) {

bstree s;

if(*bst==NULL) {

s=(bstnode*)malloc(sizeof(bstnode)); s->key=k;

s->lchild=NULL; s->rchild=NULL; *bst=s; }

else if(k<(*bst)->key)

insertbst(&((*bst)->lchild),k); else if(k>(*bst)->key)

insertbst(&((*bst)->rchild),k); }

void creatbstree(bstree *bst) {

int k; *bst=NULL;

cout<<\输入元素:\cin>>k; while(k!=0) {

insertbst(bst,k);

cout<<\输入元素:\ cin>>k; } }

//二叉树查找

int searchbst(bstree bst,int k) {

if(!bst)return NULL; else if(bst->key==k) {

cout<<\输出特定元素：\ return 1; } else

if(kkey)

searchbst(bst->lchild,k); else

searchbst(bst->rchild,k); return 0; }

《 数据结构 》实验报告 - 8 -

//简单排序

void selectsort(recordlist * l) {

int i,j,k,x;

for(i=1;i<=l->length;++i) {

k=i;

for(j=1;j<=l->length;++j) {

if(l->r[j].keyr[k].key) k=j; if(k!=i) {

x=l->r[i].key;

l->r[i].key=l->r[k].key; l->r[k].key=x; } } } }

void main() {

int f=1,e,k,r,q; char s;

recordlist * L; slinklist * L1; HashTable* h;

h=(HashTable*)malloc(sizeof(HashTable)); bstree * B;

L1=(slinklist *)malloc(sizeof(slinklist)); L=(recordlist*)malloc(sizeof(recordlist)); B=(bstree *)malloc(sizeof(bstree) ); cout<<\输入所创顺序表的长度：\cin>>r;

L->length=r;

cout<<\输入表的元素：\for(int i=1;i<=L->length;i++) cin>>L->r[i].key; while(f) {

cout<

cout<<\请输入序号:-----------------\ cout<<\顺序查找请输入:A \ cout<<\直接插入排序请输入:B\

cout<<\冒泡排序请输入:C\

《 数据结构 》实验报告 - 9 -

cout<<\快速排序请输入:D\

cout<<\折半查找请输入:E\ cout<<\建立二叉排序树请输入:F\

cout<<\查找二叉树特定关键字请输入:G\ cout<<\建立哈希表请输入:H\

cout<<\哈希表上查找请输入:I\ cout<<\简单排序请输入:J\ cout<<\退出请输入:K\ cout<<\输入操作序号：\ cin>>s; switch(s) {

case 'A':

cout<<\进行顺序查找：\ cout<<\输入要查找的元素：\ cin>>k;

seqsearch(L,k); break; case 'B':

cout<<\进行直接插入排序：\ inssort(L); break; case 'C':

cout<<\进行还原：\ initrecord(L);

for( e=1;e<=L->length;e++) cout<r[e].key<<\ cout<

cout<<\进行冒泡排序：\ bubblesort(L); break; case 'D':

cout<<\进行还原：\ initrecord(L);

for( e=1;e<=L->length;e++) cout<r[e].key<<\ cout<

cout<<\快速排序:\ qksort(L,1,9);

for( q=1;q<=L->length;q++) cout<r[q].key<<\ cout<

cout<<\进行折半查找:\

cout<<\输入要查找的元素：\