一、树
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; //空树的高度为0else { m=BTHeight(root->lchild); //求左子树的高度为lchilddepn=BTHeight(root->rchild); //求右子树的高度为rchilddepreturn(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;//从前半部分继续查找
elselow=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;}}
}