查找与排序算法的设计和实现（实现插入、选择等各种排序算法）

本文主要是介绍查找与排序算法的设计和实现（实现插入、选择等各种排序算法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

主要运用：

1．在顺序表上进行顺序查找及在有序顺序表上进行二分查找的算法。

2．二叉排序树的定义和有关操作，理解对二叉排序树进行操作的递归算法；

3．各种排序算法思想、时间和空间复杂度分析，能根据实际需要选择合适的排序方法。

实现功能：

1、实现顺序表的顺序查找和二分查找或建立一个二叉排序树并进行查找操作。

2、实现插入、选择等各种排序算

主要代码：

#include <iostream>
#include <malloc.h>
using namespace std;
typedef int KeyType;
typedef char ElemType;
typedef struct bstnode
{
    KeyType key;
    ElemType data;
    struct bstnode *lchild,*rchild;
}BSTNode;



BSTNode *BSTSearch(BSTNode *bt,KeyType k)
{
	BSTNode *p=bt;
while(p!=NULL)
{
	if(p->key==k)
	return p;
	else if(k<=p->key)
		p=p->lchild;
	else p=p->rchild;
}
return NULL;
}


int BSTInsert(BSTNode *&bt,KeyType k)
{
    BSTNode *f,*p=bt;
    while(p!=NULL)
    {
        if(p->key==k)
            return 0;
         f=p;
         if(k<p->key)
            p=p->lchild;
         else
            p=p->rchild;
    }
    p=(BSTNode *)malloc(sizeof(BSTNode));
    p->key=k;
    p->lchild=p->rchild=NULL;
    if(bt==NULL)
        bt=p;
    else if(k<f->key)
        f->lchild=p;
    else
        f->rchild=p;
        return 1;
}

void CreateBST(BSTNode *&bt,KeyType a[],int n)
{
    bt=NULL;
    int i=0;
    while(i<n)
    {
        BSTInsert(bt,a[i]);
        i++;
    }
}



void DestroyBST(BSTNode *&bt)
{
    if(bt!=NULL)
    {
        DestroyBST(bt->lchild);
        DestroyBST(bt->rchild);
        free(bt);
    }
}



void DispBST(BSTNode *bt)
{
    if(bt!=NULL)
    {
        printf("%d",bt->key);
        if(bt->lchild!=NULL||bt->rchild!=NULL)
        {
            printf("(");
            DispBST(bt->lchild);
            if(bt->rchild!=NULL)
                printf(".");
            DispBST(bt->rchild);
            printf(")");
        }
    }
}

int BSTDelete(BSTNode *&bt,KeyType k)
{
    BSTNode *p=bt,*f,*q,*ql,*fl;
    f=NULL;
    if(bt==NULL) return 0;
    while(p!=NULL)
    {
        if(p->key==k)
            break;
        f=p;
        if(k<p->key)
            p=p->lchild;
        else
            p=p->rchild;

    }
    if(p==NULL) return 0;
    else if(p->lchild==NULL)
    {
        if(f==NULL)
            bt=p->rchild;
        else if(f->rchild==p)
            f->lchild=p->rchild;
        else if(f->rchild==p)
            f->rchild=p->rchild;
        free(p);
    }
    else if(p->rchild==NULL)
    {
        if(f==NULL)
            bt=p->lchild;
        if(f->lchild==p)
            f->lchild=p->lchild;
        else if(f->rchild==p)
            f->rchild=p->lchild;
        free(p);

    }
    else
    {
        q=p->lchild;
        if(q->rchild==NULL)
        {
            p->key=q->key;
            p->data=q->data;
            p->lchild=q->lchild;
            free(q);
        }
        else
        {
            fl=q;ql=fl->rchild;
            while(ql->rchild!=NULL)
            {
                fl=ql;
                ql=ql->rchild;

            }
            p->key=ql->key;
            p->data=ql->data;
            fl->rchild=ql->lchild;
            free(ql);
        }
    }
    return 1;
}





int  main()
{
	KeyType a[]={25,18,46,2,53,39,32,4,74,67,60,11},k=25;
	int n=12;
	BSTNode * bt;
	CreateBST(bt,a,n);
	printf("BST:");DispBST(bt);printf("\n");
	printf("删除关键字%d\n",k);
	if (BSTDelete(bt,k))
	{
		printf("BST:");
		DispBST(bt);printf("\n");
	}
	else printf("未找到关键字为%d的结点\n",k);
		printf("插入关键字%d\n",k);
	if (BSTDelete(bt,k))
	{
		printf("BST:");
		DispBST(bt);printf("\n");
	}
	else printf("存在重复的关键字%d\n",k);
	DestroyBST(bt);
}

实现界面： 

这篇关于查找与排序算法的设计和实现（实现插入、选择等各种排序算法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！