{ change=false;
for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; j
{ a[j] ←→a[j+1] ; change=TURE ; } }
– 最好情况：0次
– 最坏情况：1+2+3+?+n-1=n(n-1)/2
– 平均时间复杂度为： O(n2)
---------------------------------------------------------------------------------
算法说明 ：算法中pa ，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。
LNode *Merge_LinkList(LNode *La， LNode *Lb)
/* 合并以La, Lb为头结点的两个有序单链表 */ { LNode *Lc, *pa , *pb , *pc, *ptr ;
Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ; while (pa!=NULL && pb!=NULL) { if (pa->data
{ pc->next=pa ; pc=pa ; pa=pa->next ; } /* 将pa所指的结点合并，pa指向下一个结点 */ if (pa->data>pb->data)
{ pc->next=pb ; pc=pb ; pb=pb->next ; }
/* 将pa所指的结点合并，pa指向下一个结点 */
if (pa->data==pb->data)
{ pc->next=pa ; pc=pa ; pa=pa->next ; ptr=pb ; pb=pb->next ; free(ptr) ; }
/* 将pa所指的结点合并，pb所指结点删除 */
}
if (pa!=NULL) pc->next=pa ;
else pc->next=pb ; /*将剩余的结点链上*/ free(Lb) ; return(Lc) ; }
采用静态顺序栈方式实现 void conversion(int n , int d)
/*将十进制整数N转换为d(2或8)进制数*/ { SqStack S ; int k, *e ; S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈 */
while (S.top!=0) /* 栈不空时出栈，输出 */ { pop(S, e) ;
printf(“ ” , *e) ;
} }
求转置矩阵的算法如下：
void TransMatrix(TMatrix a , TMatrix b) { int p , q , col ;
b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* 置三元组表b.data的行、列数和非0元素个数 */ if (b.tn==0) printf(“ The Matrix A=0\\n” ); else
{ q=0;
for (col=1; col<=a.cn ; col++) /* 每循环一次找到转置后的一个三元组 */
for (p=0 ;p
{ b.data[q].row=a.data[p].col ; b.data[q].col=a.data[p].row ; b.data[q].value=a.data[p].value; q++ ; }
} }
先序遍历的递归算法
void PreorderTraverse(BTNode *T) { if (T!=NULL)
{ visit(T->data) ; /* 访问根结点 */ PreorderTraverse(T->Lchild) ;
PreorderTraverse(T->Rchild) ; } }
非递归算法
设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 访问p所指向的结点；
⑵ q=p->Rchild ，若q不为空，则q进栈；
⑶ p=p->Lchild ，若p不为空，转(1)，否则转(4)； ⑷ 退栈到p ，转(1)，直到栈空为止。
算法实现：
#define MAX_NODE 50
void PreorderTraverse( BTNode *T)
{ BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ;
if (T==NULL) printf(“ Binary Tree is Empty!\\n”) ; else { do
{ visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ;
if (p==NULL) { p=stack[top] ; top-- ; } }
while (p!=NULL) ;
} }
==============================================================================中序遍历的递归算法
void InorderTraverse(BTNode *T) { if (T!=NULL)
{ InorderTraverse(T->Lchild) ;
visit(T->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } }
非递归算法
设T是指向二叉树根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T ⑴ 若p不为空，p进栈， p=p->Lchild ；
⑵ 否则(即p为空)，退栈到p，访问p所指向的结点； ⑶ p=p->Rchild ，转(1)； 直到栈空为止。
算法实现：
#define MAX_NODE 50
void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ;
if (T==NULL) printf(“ Binary Tree is Empty!\\n”) ; else { do
{ while (p!=NULL)
{ stack[++top]=p ; p=p->Lchild ; } if (top==0) bool=0 ;
else { p=stack[top] ; top-- ;
visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } }
===============================================================================
后序遍历的递归算法
void PostorderTraverse(BTNode *T) { if (T!=NULL)
{ PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ;
visit(T->data) ; /* 访问根结点 */ } }
非递归算法
在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。
因此，设立一个状态标志变量tag ： 0 ： 结点暂不能访问
1 ： 结点可以被访问
其次，设两个堆栈S1、S2 ，S1保存结点，S2保存结点的状态标志变量tag 。S1和S2共用一个栈顶指针。
设T是指向根结点的指针变量，非递归算法是： 若二叉树为空，则返回；否则，令p=T； ⑴ 第一次经过根结点p，不访问：
p进栈S1 ， tag 赋值0，进栈S2，p=p->Lchild 。 ⑵ 若p不为空，转(1)，否则，取状态标志值tag ：
⑶ 若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1) ，取S1栈顶元素的右子树，即p=S1[top]->Rchild ，转(1)； ⑷ 若tag=1：S1退栈，访问该结点； 直到栈空为止。 算法实现：
#define MAX_NODE 50
void PostorderTraverse( BTNode *T) { BTNode *S1[MAX_NODE] ,*p=T ; int S2[MAX_NODE] , top=0 , bool=1 ;
if (T==NULL) printf(“Binary Tree is Empty!\\n”) ; else { do
{while (p!=NULL)
{ S1[++top]=p ; S2[top]=0 ; p=p->Lchild ; }
if (top==0) bool=0 ; else if (S2[top]==0)
{ p=S1[top]->Rchild ; S2[top]=1 ; } else
{ p=S1[top] ; top-- ;
visit( p->data ) ; p=NULL ;
/* 使循环继续进行而不至于死循环 */
}
} while (bool!=0) ; } }
===============================================================================
设T是指向根结点的指针变量，层次遍历非递归算法是： 若二叉树为空，则返回；否则，令p=T，p入队； ⑴ 队首元素出队到p； ⑵访问p所指向的结点；
⑶将p所指向的结点的左、右子结点依次入队。直到队空为止。
#define MAX_NODE 50
void LevelorderTraverse( BTNode *T) { BTNode *Queue[MAX_NODE] ,*p=T ; int front=0 , rear=0 ; if (p!=NULL)
{ Queue[++rear]=p; /* 根结点入队 */ while (front { p=Queue[++front]; visit( p->data ); if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ } } } ===============================================================================利用层次遍历算法可以直接求得二叉树的深度。 算法实现： #define MAX_NODE 50 int search_depth( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int front=0 , rear=0, depth=0, level ; /* level总是指向访问层的最后一个结点在队列的位置 */ if (T!=NULL) { Queue[++rear]=p; /* 根结点入队 */ level=rear ; /* 根是第1层的最后一个节点 */ while (front { p=Queue[++front]; if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ if (front==level) /* 正访问的是当前层的最后一个结点 */ { depth++ ; level=rear ; }