期末复习——数据结构部分

悠悠 2022-06-02 02:25 197阅读 0赞

一、顺序查找  
从表中的第一个（或最后一个记录）开始，逐个进行记录的关键字和给定值比较，若某个记录字与给定值相等则查找成功，找到所查找的记录。如果直到最后一个记录（或第一个记录），都没有找到给定值与记录字相等，则表中没有所查找的记录，查找不成功。

/*顺序查找，a为数组，n为要查找的0数组的长度，key为关键字*/
    int SXSearch(int *a,int n,int key) 
    {
        int i;
        for(i=1;i<=n;i++)
        {
            if(a[i]==key)
                return i;
         } 
         return 0;
    }
    
    /*哨兵顺序查找*/
    int SXSearch(int *a,int n,int key)
    {
        int i;
        a[0]=key;
        i=n;
        while(a[i]!=key)
        {
            i--;
        }
        return i;
    }

二、折半查找  
折半查找又称二分查找，前提是线性表中的记录必须是关键有序（通常从小到大有序），线性表必须采用线性存储。在有序表中，取中间记录作为比较对象，若给定值与中间记录相等，则查找成功，若给定值小于中间记录，则在中间记录的左半区域查找，若给定值大于中间记录，则在中间记录的右半区域查找。

/*折半查找*/
    int ZhebanSearch(int *a,int n,int key)
    {
        int mid,high,low;
        low=1;
        high=n;
        while(low<high)
        {
            mid=(low+high)/2;
            if(a[mid]<key)
                low=mid+1;
            else if(a[mid]>key)
                high=mid-1;
            else
                mid;
         } 
         return 0;
     }

三、二叉排序树  
二叉排序树，又称二叉查找树，它要么是一棵空树，要么具有以下性质的二叉树：（1）若它的左子树不空，则左子树上所有的结点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有的值均大于它的根节点的值；（3）它的左子树和右子树也分别为二叉排序树。

/*二叉树的二叉链表结构定义*/
    typedef struct BiTNode
    {
        int data;
        struct BiTNode *lchild,*rchild;
    
    }BiTNode,*BiTree;
    
    /*二叉树的查找*/
    Status SearchBST(BiTree T,int key,BiTree f,BiTree *p)
    {
        if(!T)
        {
            *p=f;
            return FALSE;
        } 
        else if(key==T->data)
        {
            *p=T;
            return TRUE;    
        }   
        else if(key<T->data)
            return SearchBST(T->lchild,key,T,p);
        else if(key>T->data)
            return SearchBST(T->rchild,key,T,p)     
    }

/*二叉树的插入*/
    /*当二叉树中不存在等于key的数据元素时*/
    /*插入key返回TRUE否则返回FALSE*/ 
    Status InsertBST(BiTree *T,int key) 
    {
        BiTree s,p;
        if(!SearchBST(*T,key,NULL,&p))  /*如果查找不成功*/
        {
            s=(BiTree)malloc(sizeof(BiTNode));
            s->data=key;
            s->lchild=s->rchild=NULL;
            if(!p)
                *T=s;   /*插入s为新的根结点*/
            else if( key < p->data )
                p->lchild=s;   /*插入s为左孩子*/
            else 
                p->rchild=s;   /*插入s为右孩子*/
            return TRUE; 
         } 
         else
            return FALSE;     /*数中已有关键字相同的结点，不再插入*/
     }

/*若二叉排序树T中存在关键字等于key的元素时，删除该结点元素，并返回TRUE，否则返回FALSE*/
    Status DeleteBST(BiTree *T,int key)
    {
        if(!T)
            return FALSE;
    
        else
        {
            if(key==(*T)->data)
                return Delete(T);
            else if(key<(*)->data)
                return DeleteBST(&(*T)->lchild,key);
            else
                return DeleteBST(&(*T)->rchild,key);
         } 
     }

/*从二叉树中删除结点p并重接它的左右子树*/
    Status Delete(BiTree *p)
    {
        BiTree q,s;
        if((*p)->rchild==NULL)    /*如果右子树空*/
        {
            q=*p;
            *p=(*p)->lchild;
            free(q);
        } 
        else if((*p)->lchild==NULL)
        {
            q=*p;
            *p=(*p)->rchild;
            free(q);    
        }
        else   /*如果左右子树都不存在*/
        {
            q=*p; 
            s=(*p)->lchild
            while(s->rchild)  /*转左，然后向右到尽头（找到代删结点的前驱）*/
            {
                q=s;
                s=s->rchild;    
            }
            (*p)->data=s->data;  /*s指向被删除结点的直接前驱*/
            if(q!=*p)
                q->rchild=s->lchild;
            else
                q->lchild=s->lchild;
            free(q); 
        }
        return TRUE;
    }

四、平衡二叉树  
平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。它要么是一棵空树，要么它的左子树和右子树的深度之差的绝对值不超过1。我们将左子树深度减去右子树深度的值称为平衡因子BF，那么平衡二叉树上所有的结点的平衡因子只可能是-1，0，1。只要二叉树上有一个平衡因子的绝对值大于1，则该二叉树就不是平衡的。

/*二叉树的二叉链表结点结构定义*/
    typedef struct BiTNode 
    {
        int data;
        int bf;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    /*对以p为根的二叉排序树做右旋处理*/
    void RXBiT(BiTree *p)
    {
        BiTree L;
        L=(*p)->lchild;
        (*p)->lchild=L->rchild;
        L->rchild=*p;
        *p=L;   
    } 
    
    /*对以p为根的二叉排序树做左旋处理*/
    void LXBiT(BiTree *p)
    {
        BiTree R;
        R=(*p)->rchild;
        (*p)->rchild=R->lchild;
        R->lchild=*p;
        *p=R;       
    }

五、冒泡排序

#define MAXSIZE 10
    typedef struct
    {
        int r[MAXSIZE+1];  /*用于存储排序数组，r[0]用作哨兵或临时变量*/
        int length;     /*用于记录顺序表的长度*/ 
    }SqList;
    
    /*交换L中数组r的下标为i和j的值*/
    void swap(SqList *L,int i,int j)
    {
        int temp=L->r[i];
        L->r[i]=L->r[j];
        L->r[j]=temp;   
    } 
    
    /*对顺序表L作交换排序*/
    void Maopao(SqList *L) 
    {
        int i,j;
        for(i=1;i<L->length;i++)
        {
            for(j=i+1;j<=L->length;j++)
            {
                if(L->r[i]>L->r[j])
                {
                    swap(L,i,j);   /*交换L->r[i]与L->r[j]的值*/
                }
            }
        }
    }

/*对顺序表L作冒泡排序*/
    void Maopao(SqList *L)
    {
        int i,j;
        Status flag=TRUE;     /*flag用来做标记*/ 
        for(i=1;i<L->length&&flag;i++)   /*若flag为true则退出循环*/
        {
            flag=FALSE;    /*初始为false*/
            for(j=L->length;j>=1;j--)
            {
                if(L->r[j]>L->r[j+1])
                {
                    swap(L,j,j+1);
                    flag=TRUE;
                }
             } 
        }   
    }

六、直接插入排序  
将一个记录直接插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表。

void InsertSort(SqList *L)
    {
        int i,j;
        for(i=2;i<=L->length;i++)
        {
            if(L->r[i]<L->r[i-1])
            {
                L->r[0]=L->r[i];     /*设置哨兵*/
                for(j=i-1; L->r[j] > L->r[0];j--)
                    L->r[j+1]=L->r[j];
                L->r[j+1]=L->r[0];
            }
        }
    }

七、希尔排序

void XESort(SqList *L)
    {
        int i,j;
        int increment=L->length;
        do
        {
            increment=increment/3+1;
            for(i=increment+1;i<=L->length;i++)
            {
                if(L->r[i]<L->r[i-increment])
                {
                    L->r[0]=L->r[i];
                    for(j=i-increment:j>0&& L->r[0] < L->r[j];j=j-increment)
                        L->r[j+increment]=L->r[0];
                }
            }
        }
        while(increment>1);
    }

八、堆排序  
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

/*对顺序表进行堆排序*/
    void HeadSort(SqList *L) 
    {
        int i;
        for(i=L->length/2;i>0;i--)    /*构建大顶堆*/
        {
            HeapAdjust(L,i,L->length);
        }
        for(i=L->length;i>1;i--)
        {
            swap(L,1,i);     /*将堆顶记录和当前未经排序子序列的最后一个记录交换*/
            HeadAdjust(L,1,i-1); 
        }
    }

void HeadAdjust(SqList *L,int s,int m)
    {
        int temp,j;
        temp=L->r[s];
        for(j=2*s;j<=m;j*=2)
        {
            if(j<m&&L->r[j]<L->r[j+1])
                ++j;
            if(temp>=L->r[j])
                break;
            L->r[s]=L->r[j];
            s=j;
        }
        L->r[s]=temp;
    }

九、快速排序

int FastSort(SqList *L,int low,int high)
    {
        int key;
        key=L->r[low];
        while(low<high)
        {
            while( low<high && L->r[high]>=key )
                high--;
            swap(L,low,high);
            while(low<high && L->r[low]<=key)
                low++;
            swap(L,low,high);
        }
        return low;
    }

/*快速排序优化算法*/
    void FastSort(SqList *L,int low,int high)
    {
        int key;
        key=L->r[low];
        L->r[0]=key;
        while(low<high)
        {
            while(low<high&&L->r[high]>=key)
                high--;
            L->r[low]=L->r[hingh];
            while(low<high&&L->r[low]<=key)
                low++;
            L->r[high]=L->r[low];
        }   
        L->r[low]=L->r[0];
        return low;
    }