数据结构期末算法复习：树、查找、排序

一、树

1.二叉链-定义

typedef struct BiTNode{
ElemType data;//数据域
struct BiTNode *lchild ,*rchild;//左、右孩子指针
}BiTNode , *BiTree ;

2.查找值为x的结点

BTNode   FindNode(BTNode   b，ElemType x) 
{  BTNode *p;
   if (b==NULL) return NULL;
   else if (b->data==x) return b;
   else
   {   p=FindNode(b->lchild，x);
       if (p!=NULL) return p;
       else return FindNode(b->rchild，x);
   }
}

3.求高度

int BTHeight(BiTree root) 
{  int m，n;
   if (root==NULL) return 0; 	//空树的高度为0
   else  
   {  m=BTHeight(root->lchild);	//求左子树的高度为lchilddep
      n=BTHeight(root->rchild);	//求右子树的高度为rchilddep
      return(m>n)? (m+1):(n+1));}
}

4.统计二叉树的结点

void PreOrder(BiTree root)
{  int count=0;
   if(root)
{  count++;
   PreOrder(root->LChild);
   PreOrder(root->RChild);}
}

5.输出叶子结点

void inOrder(BiTree root)
{if(root)
{     inOrder(root->LChild);
      if(root->LChild==NULL&& root->RChild==NULL)
            printf(root->data);
      inOrder(root->RChild);}
}

6.统计叶子结点个数

int leaf(BiTree root)
{int nl,nr;
if(root==NULL)   return 0; 
   if(root->LChild==NULL&& root->RChild==NULL)
             return 1;
   nl=leaf(root->RChild);
   nr=leaf(root->LChild);
    return(nl+nr);
}

二、查找

1.定义

typedef struct{//查找表的数据结构（顺序表)
ElemType *elem;//动态数组基址
int TableLen;//表的长度
}SSTable;

2.顺序查找

int Search_Seq( SSTable ST,ElemType key){
	int i; ST.elem[0] =key; //哨兵	
	for( i=ST.TableLen ;ST.elem[i] !=key; --i) ;//从后往前找	
	return  i;//查找成功，则返回元素下标;查找失败，则返回0
}

3.折半查找

int Binary_Search( SSTable L,ElemType key){
	int low=1, high=L.TableLen,mid;
	while( low<=high){
		mid=( low+high)/2;//取中间位置
		if(L.elem[mid]==key)
			return mid;/查找成功则返回所在位置
		else if(L.elem [mid]>key)
	high=mid-1;//从前半部分继续查找
else
	low=mid+1;//从后半部分继续查找
}
return -1;  //查找失败，返回-1
}

4.二叉排序树

typedef struct BSTNode{
    int key;//数据域
    struct BSTNode*lchild ,*rchild;//左、右孩子指针
}BSTNode,*BSTree;

5.查找

BSTNode *BST_Search(BSTree T,int key){
while(T!=NULL&&key!=T->key){
       //若树空或等于根结点值，则结束循环
	if(key<T->key)T=T->lchild; //小于，则在左子树上查找
	else T=T->rchild;//大于，则在右子树上查找
}
	return T;
}

6.二叉排序树插入

int BST_Insert(BSTree &T, int k){
if(T==NULL){//原树为空，新插入的结点为根结点
	T=(BSTree )malloc(sizeof(BSTNode) ) ;
	T->key=k;
	T->lchild=T->rchild=NULL;
	return 1;//返回1，插入成功  }
else if(k==T->key)//树中存在相同关键字的结点，插入失败
	return 0;
else if( k<T->key)//插入到T的左子树
	return BST_Insert(T->lchild,k);
        else //插入到T的右子树
	return BST_Insert(T->rchild,k);}

三、排序

1.待排序的数据类型定义

#define MAXSIZE  1000    //待排序的记录数目
typedef  int  KeyType;       //关键字类型
typedef  struct 
{
    KeyType   key;                 //关键字项    
    OtherType  other_data;  //其他数据项
} RecordType;                            //纪录类型
typedef  struct 
{
 RecordType    r[MAXSIZE+1];   
      int               length;            //序列长度
} RecordList;                         //记录序列类型（顺序表类型）

2.直接插入排序

void InsertionSort ( SqList &L ) 
{
      for ( i=2; i<=L.length; ++i ) 
        if (L.r[i].key < L.r[i-1].key) 
        {
          L.r[0] = L.r[i];            
         for ( j=i-1; L.r[0].key < L.r[j].key;  -- j )
                  L.r[j+1] = L.r[j];        
         L.r[j+1] = L.r[0];               
        }
}

3.折半插入排序

void BiInsertionSort ( SqList &L ) 
{
  int i,j,low,high,mid;
for ( i=2; i<=L.length; ++i ) 
{
L.r[0] = L.r[i];      
low = 1;   high = i-1;
while (low<=high) 
{ m= (low+high)/2;           
   if (L.r[0].key < L.r[m].key)
        high = m-1;   
    else  low = m+1; }
for ( j=i-1;  j>=low;  --j )
    L.r[j+1] = L.r[j];      
}
L.r[low] = L.r[0];  
}

4.冒泡法排序

void BubbleSort(RecordList L)
{ int i,j;
  RecordType x;
  int  flag=1;
    for(i=1; i<=L.length-1&&flag; i++)
    {	flag=0;
	for(j=1;j<= L.length-1; j++)
	{  if(L.r[j].key>L.r[j+1].key)
	     {	x=L.r[j];L.r[j]=r[j+1];L.r[j+1]=x; 
                   flag=1;}
                }
      }
} 

5.快速排序

int QKpass (RecordType r[ ], int low, int high) 
{
r[0] = r[low];  
while (low<high) 
{
     while(low<high&& r[high].key>= r[0].key)
        -- high;      
       r[low] = r[high];
while (low<high && r[low].key<= r[0].key) 
        ++ low;      
r[high] = r[low];
}
r[low] = r[0];     return low;
}
void QKSort(RecordType r[ ],int low,int high)
{   
     r[0]=r[low];
     if(low<high)
     {
           pos=QKpass(r,low,high);
	 QKSort(r,low,pos-1);
     	 QkSort(r,pos+1,high);	
}

6.简单选择排序

void SelectSort(RecordList L)
{  int i,j;
    RecordType t;
     for(i=1;i<= L.length -1;i++)
     {	k=i;		  
	    for(j=i+1;j<= L.length -1; j++)	  
	         if(L.r[j].key<L.r[k].key)  
               k=j;      
	    if(k!=i)	       
	   {  t=L.r[i]; L.r[i]=L.r[k]; L.r[k]=t;}
          }
}