华农数据结构部分答案

8576 顺序线性表的基本操作
#include
#include
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct
{
int *elem;
int length;
int listsize;
}SqList;

int InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem)
{
return ERROR;
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}

int Load_Sq(SqList &L)
{
int i;
if (L.length==0)
{
printf("The List is empty!");
}
else
{
printf("The List is: ");
for (i = 0; i < L.length; i++)
{
printf("%d ",L.elem[i]);
}
}
printf("\n");
return OK;
}

int ListInsert_Sq(SqList &L, int i, ElemType e)
{
int *newbase,*p,*q;
if ((i < 1) || (i > L.length + 1))
{
return ERROR;
}
if (L.length >= L.listsize)
{
newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
{
return ERROR;
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i-1]);
for (p = &(L.elem[L.length-1]); p >= q; --p)
{
*(p+1) = *p;
}
*q = e;
L.length++;
return OK;
}

int ListDelete_Sq(SqList &L,int i, ElemType &e)
{
int *p,*q;
if((i < 1) || (i > L.length))
{
return ERROR;
}
p = &(L.elem[i-1]);
e = *p;
q = L.elem + L.length - 1;
for(++p; p <= q; ++p)
{
*(p-1) = *p;
}
--L.length;
return OK;
}

int main()
{
SqList T;
int a, i;
ElemType e,x;
if (InitList_Sq(T))
{
printf("A Sequence List Has Created.\n");
}
while(1)
{
printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
scanf("%d",&a);
switch(a)
{
case 1:scanf("%d%d",&i,&x);
if(!ListInsert_Sq(T,i,x))
{
printf("Insert Error!\n");
}
else
{
printf("The Element %d is Successfully Inserted!\n",x);
}
break;
case 2:scanf("%d",&i);
if(!ListDelete_Sq(T,i,e))
{
printf("Delete Error!\n");
}
else
{
printf("The Element %d is Successfully Deleted!\n",e);
}
break;
case 3:Load_Sq(T);
break;
case 0:return 1;
}
}
}
8577 合并顺序表
#include
#include
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct
{
int *elem;
int length;
int listsize;
}SqList;

int InitList_Sq(SqList &L)
{
L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) return ERROR;
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}

void Load_Sq(SqList &L,char name)
{
int i;
if(L.length==0) printf("The List is empty!");
else
{
printf("List %c:",name);
for(i=0;i}
printf("\n");
}

int ListInsert_Sq(SqList &L,int e)
{
ElemType *newbase,*p;
if(L.length>=L.listsize){
newbase=(ElemType *)realloc(L

.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if(!newbase) return ERROR;
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
p=&(L.elem[L.length]);
*p=e;
++L.length;
return OK;
}

int MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
int *pa,*pb,*pc,*pa_last,*pb_last;
pa=La.elem;pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType *)malloc(Lc.listsize*sizeof(ElemType));
if(!Lc.elem) return ERROR;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while(pa<=pa_last&&pb<=pb_last){
if(*pa<=*pb) *pc++=*pa++;
else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;
return OK;
}

int main()
{
SqList A,B,C;
int n,i;
ElemType x;
InitList_Sq(A);
InitList_Sq(B);
InitList_Sq(C);
char name[]={'A','B','C'};
scanf("%d",&n);
for(i=0;iscanf("%d",&x);
ListInsert_Sq(A,x);
}
scanf("%d",&n);
for(i=0;iscanf("%d",&x);
ListInsert_Sq(B,x);
}
MergeList_Sq(A,B,C);
Load_Sq(A,name[0]);
Load_Sq(B,name[1]);
Load_Sq(C,name[2]);
}
8578 顺序表逆置
#include
#include
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L, int n)
{
LinkList p, q;
int i;
ElemType e;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
q = L;
for (i = 0; i < n; i++)
{
scanf("%d",&e);
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = NULL;
q->next = p;
q = p;
}
return OK;
}

int LoadLink_L(LinkList &L, char name[])
{
LinkList p = L->next;
if (!p)
{
printf("The List is empty!");
}
else
{
printf("The%sList is:",name);
while (p)
{
printf("%d ",p->data);
p = p->next;
}
}
printf("\n");
return OK;
}

int LinkInsert_L(LinkList &L, int i, ElemType e)
{
LinkList s, p = L;
int j = 0;
while(p && j < i - 1)
{
p = p->next;
j++;
}
if(!p || j > i - 1)
{

return ERROR;
}
s =(LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p ->next;
p->next = s;
return OK;
}

int ListDelete_L(LinkList &L, int i, ElemType &e)
{
LinkList q, p = L;
int j = 0;
while(p && j < i - 1)
{
p = p->next;
j++;
}
if(!p || j > i - 1)
{

return ERROR;
}
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}

void ListTurn_L(LinkList &L)
{
LinkList p_current, p_last, p;
p = p_current = L;
p_last = L->next;
if (p_last->next == NULL)
{
return;
}
while ((p_current->next)->next !=NULL)
{
while(p_last->next != NULL)
{
p_last = p_last->next;
p = p->next;
}
p->next = NULL;
p_last->next = p_current->next;
p_current->next = p_last;
p_current = p_last;
p_last = p_last->next;
p = p_current;
}
}

int main()
{
LinkList T;
int num;
scanf("%d",&num);
CreateLink_L(T,num);
LoadLink_L(T," ");

ListTurn_L(T);
LoadLink_L(T," turned ");
return OK;
}
8579 链式线性表的基本操作
#include
#include
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L, int n)
{
LinkList p, q;
int i;
ElemType e;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
q = L;
for (i = 0; i < n; i++)
{
scanf("%d",&e);
p = (LinkList)malloc(sizeof(LNode));
p->data = e;
p->next = NULL;
q->next = p;
q = p;
}
return OK;
}

int LoadLink_L(LinkList &L)
{
LinkList p = L->next;
if (!p)
{
printf("The List is empty!");
}
else
{
printf("The LinkList is:");
while (p)
{
printf("%d ",p->data);
p = p->next;
}
}
printf("\n");
return OK;
}

int LinkInsert_L(LinkList &L, int i, ElemType e)
{
LinkList s, p = L;
int j = 0;
while(p && j < i - 1)
{
p = p->next;
j++;
}
if(!p || j > i - 1)
{

return ERROR;
}
s =(LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p ->next;
p->next = s;
return OK;
}

int ListDelete_L(LinkList &L, int i, ElemType &e)
{
LinkList q, p = L;
int j = 0;
while(p->next && j < i - 1)
{
p = p->next;
++j;
}
if(!(p->next) || j > i - 1)
{

return ERROR;
}
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}

int main()
{
LinkList T;
int a, n, i;
ElemType x, e;
printf("Please input the init size of the linklist:\n");
scanf("%d",&n);
printf("Please input the %d element of the linklist:\n",n);
if (CreateLink_L(T,n))
{
printf("A Link List Has Created.\n");
LoadLink_L(T);
}
while(1)
{
printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");
scanf("%d",&a);
switch(a)
{
case 1:scanf("%d%d",&i,&x);
if(!LinkInsert_L(T, i, x))
{
printf("Insert Error!\n");
}
else
{
printf("The Element %d is Successfully Inserted!\n",x);
}
break;
case 2:scanf("%d",&i);
if(!ListDelete_L(T, i, e))
{
printf("Delete Error!\n");
}
else
{
printf("The Element %d is Successfully Deleted!\n",e);
}
break;
case 3:LoadLink_L(T);
break;
case 0:return 1;
}
}
}
8580 合并链表
#include
#include
#define ERROR 0
#define OK 1
#define ElemType int

typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;

int CreateLink_L(LinkList &L,int n)
{
LinkList p,q;
int i;
ElemType e;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
q=L;
for(i=0;iscanf("%d",&e);
p=(LinkList)malloc(sizeof(LNode));
p->data=e;
p->next=q->next;
q->next=p;
q=p;
}
return OK;
}

int LoadLink_L(LinkList &L)
{
LinkList p=L->next;
if(!p) printf("The List is empty!");
else
{
while(p)
{
printf("%d ",p->data);
p=p->next;
}
}

printf("\n");
return OK;
}

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
LinkList pa,pb,pc;
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
else{pc->next=pb;pc=pb;pb=pb->next;
}
}
pc->next=pa?pa:pb;
free(Lb);
}

int main()
{
LinkList A,B,C;
int n;
scanf("%d",&n);
CreateLink_L(A,n);
scanf("%d",&n);
CreateLink_L(B,n);
printf("List A:");
LoadLink_L(A);
printf("List B:");
LoadLink_L(B);
MergeList_L(A,B,C);
printf("List C:");
LoadLink_L(C);
}
8581 线性链表逆置
#include
#include
#define OK 1
#define ERROR 0
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define ElemType int

typedef struct
{
int *elem;
int length;
int listsize;
}SqList;

int InitList_Sq(SqList &L)
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if (!L.elem)
{
return ERROR;
}
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}

int Load_Sq(SqList &L, char name[])
{
int i;
if (L.length==0)
{
printf("The List is empty!");
}
else
{
printf("The%sList is:", name);
for (i = 0; i < L.length; i++)
{
printf("%d ",L.elem[i]);
}
}
printf("\n");
return OK;
}

int ListInsert_Sq(SqList &L, int i, ElemType e)
{
int *newbase,*p,*q;
if ((i < 1) || (i > L.length + 1))
{
return ERROR;
}
if (L.length >= L.listsize)
{
newbase = (ElemType *)realloc(L.elem,(L.listsize + LISTINCREMENT)*sizeof(ElemType));
if(!newbase)
{
return ERROR;
}
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i-1]);
for (p = &(L.elem[L.length-1]); p >= q; --p)
{
*(p+1) = *p;
}
*q = e;
L.length++;
return OK;
}

int ListDelete_Sq(SqList &L,int i, ElemType &e)
{
int *p,*q;
if((i < 1) || (i > L.length))
{
return ERROR;
}
p = &(L.elem[i-1]);
e = *p;
q = L.elem + L.length - 1;
for(++p; p <= q; ++p)
{
*(p-1) = *p;
}
--L.length;
return OK;
}

void ListTurn(SqList &L)
{
int i;
ElemType temp;
for(i = L.length - 1; i > L.length - i - 1; i--)
{
temp = L.elem[i];
L.elem[i] = L.elem[L.length - i - 1];
L.elem[L.length - i - 1] = temp;
}
}
int main()
{
SqList T;
int num, i;
ElemType e;
InitList_Sq(T);
scanf("%d",&num);
for (i = 1; i <= num; i++)
{
scanf("%d",&e);
ListInsert_Sq(T, i, e);
}
Load_Sq(T," ");
ListTurn(T);
Load_Sq(T," turned ");
return OK;
}
8583 顺序栈的基本操作
#include
#include
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int SElemType;
typedef int Status;
struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
};

Status InitStack(SqStack &S)
{
S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)return ERROR;
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Stat

us Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base = (SElemType *)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));
if(!S.base)return ERROR;
S.top = S.base +S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{
if(S.top == S.base)return ERROR;
e=*--S.top;
return OK;
}
Status GetTop(SqStack S,SElemType &e)
{
if(S.top == S.base)return ERROR;
e=*(S.top-1);
return OK;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
Status StackTraverse(SqStack S)
{
SElemType *p;
p=S.top;
if(S.top == S.base)printf("The Stack is Empty!");
else
{
printf("The Stack is:");
p--;
while(p>=S.base)
{
printf(" %d",*p);
p--;
}
}
printf("\n");
return OK;
}
int main()
{
int a ;
SqStack S;
SElemType x,e;
if(InitStack(S))
{
printf("A Stack Has Created.\n");
}
while(1)
{
printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack \n5:Load the Stack \n0:Exit\nPlease choose:\n");
scanf("%d",&a);
switch(a)
{
case 1:scanf("%d",&x);
if(!Push(S,x))printf("Push Error!\n");
else printf("The Element %d is Successfully Pushed!\n",x);
break;
case 2:if(!Pop(S,e))printf("Pop Error!\n");
else printf("The Element %d is Successfully Poped!\n",e);
break;
case 3:if(!GetTop(S,e))printf("Get Top Error!\n");
else printf("The Top Element is %d!\n",e);
break;
case 4:printf("The Length of the Stack is %d!\n",StackLength(S));
break;
case 5:StackTraverse(S);
break;
case 0:return 1;
}
}
}
8585 栈的应用——进制转换
#include
#include
#define OK 1
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int SElemType;
typedef int Status;

struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
};

Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status Pop(SqStack &S,SElemType &e)
{
if(S.top ==S.base ) return ERROR;
e=*--S.top ;
return OK;
}

Status Push(SqStack &S,SElemType e)
{
if(S.top -S.base >=S.stacksize ){
S.base =(SElemType *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top =S.base +S.stacksize ;
S.stacksize +=STACKINCREMENT;
}
*S.top ++=e;
return OK;
}

Status StackEmpty(SqStack &S){
if(S.base==S.top) return 1;
else return ERROR;
}

void conversion(){
SqStack S;
int n;
SElemType e;
InitStack(S);
scanf("%d",&n);
while(n){
Push(S,n%8);
n=n/8;
}
while(!StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
}


int main()
{
conversion();
}

8591 计算next值
#include
#include
#define MAXSTRLEN 255 // 用

户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; // 0号单元存放串的长度

void get_next(SString T,int next[]){
// 求模式串T的next函数值并存入数组next
int i,j;
i=1;j=0;
next[1]=0;
while(i{
if(j==0||T[i]==T[j]){
++i;++j;next[i]=j;
}
else j=next[j];
}
}//get_next


void main(){
int next[MAXSTRLEN];
SString S;
int n,i,j;
char ch;
scanf("%d",&n); // 指定要验证NEXT值的字符串个数
ch=getchar();
for(i=1;i<=n;i++)
{
ch=getchar();
for(j=1;j<=MAXSTRLEN&&(ch!='\n');j++) // 录入字符串
{
S[j]=ch;
ch=getchar();
}
S[0]=j-1; // S[0]用于存储字符串中字符个数
get_next(S,next);
printf("NEXT J is:");
for(j=1;j<=S[0];j++)
printf("%d",next[j]);
printf("\n");
}
}
8592 KMP算法
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASLBLE -1
#define OVERFLOW -2
#define MAXSTRLEN 255 //用户可在255以内定义最大串长
typedef unsigned char SString[MAXSTRLEN+1]; //0号单元存放串的长度

void get_next(SString T,int next[]){
// 算法4.7
// 求模式串T的next函数值并存入数组next
int i,j;
i=1;j=0;
next[1]=0;
while(i{
if(j==0||T[i]==T[j]){
++i;++j;next[i]=j;
}
else j=next[j];
}
}

int Index_KMP(SString S,SString T,int pos){
// 算法4.6
// 利用模式串T的next函数求T在主串S中第pos个字符之后的位置
int i,j,next[MAXSTRLEN];
i=pos;j=1;
get_next(T,next);
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index_KMP


void main()
{
SString T,S;
int i,j,n;
char ch;
int pos;
scanf("%d",&n); // 指定n对需进行模式匹配的字符串
ch=getchar();
for(j=1;j<=n;j++)
{
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入主串
{
S[i]=ch;
ch=getchar();
}

S[0]=i-1; // S[0]用于存储主串中字符个数
ch=getchar();
for( i=1;i<=MAXSTRLEN&&(ch!='\n');i++) // 录入模式串
{
T[i]=ch;
ch=getchar();
}
T[0]=i-1; // T[0]用于存储模式串中字符个数
pos= Index_KMP(S,T,1); // 请填空
printf("%d\n",pos);
}

}
8606 二叉树的构建及遍历操作
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef char ElemType;

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

BiTree CreateBiTree(BiTree &T){
char ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return T;
}

Status PrintElement(ElemType e){
printf("%c",e);
return OK;
}

Status PreOrderTraverse(BiTree T

,Status(*Visit)(ElemType)){
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->lchild,Visit))
if(PreOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else return OK;
}

Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)){
if(T){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit))
return OK;
return ERROR;
}
else return OK;
}

Status PostOrderTraverse(BiTree T,Status(*Visit)(ElemType)){
if(T){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data))
return OK;
return ERROR;
}
else return OK;
}

int main()
{
BiTree T;
CreateBiTree(T);
PreOrderTraverse(T,PrintElement);
printf("\n");
InOrderTraverse(T,PrintElement);
printf("\n");
PostOrderTraverse(T,PrintElement);
printf("\n");

}
8607 实现二叉排序树的各种算法(1)
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;
typedef int ElemType;

typedef struct BiTNode{
ElemType key;
struct BiTNode *left,*right;//左右孩子指针
}BiTNode,*BiTree;


BiTree InsertBiT(BiTree T,ElemType key)
{
BiTree f,p=T;
while(p)
{
if(p->key==key) return NULL;
f=p;
p=(keykey)?p->left:p->right;
}
p=(BiTree)malloc(sizeof(BiTNode));
p->key=key;
p->left=p->right=NULL;
if(T==NULL)
T=p;
else
if(keykey)
f->left=p;
else
f->right=p;
return T;
}

BiTree CreateBiT()
{
BiTree T=NULL;
ElemType key;
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&key);
T=InsertBiT(T,key);
}
return T;
}

void preorder_btree(BiTree root)
{
BiTree p=root;
if(p!=NULL)
{
printf("%d ",p->key);
preorder_btree(p->left);
preorder_btree(p->right);
}
}


void inorder_btree(BiTree root)
{
BiTree p=root;
if(p!=NULL){
inorder_btree(p->left );
printf("%d ",p->key );
inorder_btree(p->right );
}
}


void postorder_btree(BiTree root)
{
BiTree p=root;
if(p!=NULL)
{
postorder_btree(p->left );
postorder_btree(p->right );
printf("%d ",p->key );
}
}

Status visit(BiTree p)
{
printf("%d ",p->key);
return OK;
}

//栈

typedef BiTree SElemType;

struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
};

Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status Push(SqStack &S,SElemType e)
{
if(S.top -S.base >=S.stacksize ){
S.base =(SElemType *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top =S.base +S.stacksize ;
S.stacksize +=STACKINCREMENT;
}
*S.top ++=e;
return OK;
}

Status Pop(SqStack

&S,SElemType &e)
{
if(S.top ==S.base ) return ERROR;
e=*--S.top ;
return OK;
}


Status StackEmpty(SqStack &S){
if(S.base==S.top) return TRUE;
else return FALSE;
}

Status InOrderTraverse(BiTree T)
{//非递归中序
SqStack S;
InitStack(S);
BiTree p=T;
while(p||!StackEmpty(S)){
if(p)
{
Push(S,p);
p=p->left;
}
else
{
Pop(S,p);
if(!visit(p)) return ERROR;
p=p->right;
}
}
return OK;
}


int treedepth(BiTree bt)
{
int hl,hr,max;
if(bt!=NULL)
{
hl=treedepth(bt->left);
hr=treedepth(bt->right);
max=(hl>hr)?hl:hr;
return (max+1);
}
else
return 0;
}

int count=0;

int leafcount(BiTree bt)
{
if(bt!=NULL)
{
leafcount(bt->left);
leafcount(bt->right);
if(bt->left==NULL&&bt->right==NULL)
count++;
}
return count;
}

void paintleaf(BiTree bt)
{
if(bt!=NULL)
{
if(bt->left==NULL&&bt->right==NULL)
printf("%d ",bt->key);
paintleaf(bt->left);
paintleaf(bt->right);
}
}

BiTNode *searchBiT(BiTree t,ElemType key)
{
if(t==NULL||key==t->key)
return t;
if(keykey)
return searchBiT(t->left,key);
else
return searchBiT(t->right,key);
}



typedef BiTree QElemType ;


typedef struct QueueNode
{
QElemType data;
struct QueueNode *next;
} QueueNode;


typedef struct linkQueue
{
QueueNode * front;
QueueNode * rear;
}linkQueue;


void initQueue(linkQueue * q)
{
q->front=q->rear =NULL; //----无头结点
}


int QueueEmpty(linkQueue * Q)
{
return (Q->front==NULL)&&(Q->rear==NULL);

}


void EnQueue(linkQueue *Q,QElemType x)
{

QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));
p->data=x; p->next=NULL;
if(QueueEmpty(Q)) //----无头结点
Q->front=Q->rear=p;
else
{
Q->rear->next=p;
Q->rear=p;
}
}


QElemType DeQueue (linkQueue *Q)
{
QElemType x;
QueueNode *p;
if(QueueEmpty(Q))
{
printf("Queue underflow");
return ERROR;
}
p=Q->front;
x=p->data;
Q->front=p->next;
if(Q->rear==p)
Q->rear=NULL;
free(p);
return x;
}


void breadthFirst2(BiTree root)
{
BiTree p,tmp;
linkQueue * q;
tmp=(BiTNode *)malloc(sizeof(BiTNode));
q=(linkQueue *)malloc(sizeof(linkQueue));
tmp->key=-1;
initQueue(q);
p=root;
if(p!=NULL)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->key!=-1)
{
if(p->left!=NULL)
EnQueue(q,p->left);
else
EnQueue(q,tmp);
if(p->right!=NULL)
EnQueue(q,p->right);
else
EnQueue(q,tmp);
}
}
}
}

void breadthFirst(BiTree root)
{
BiTree p;
linkQueue * q;
q=(linkQueue *)malloc(sizeof(linkQueue));
initQueue(q);
p=root;
if(p!=NULL)
{
EnQueue(q,p);
while(!QueueEmpty(q))
{
p=DeQueue(q);
visit(p);
if(p->left!=NULL)
EnQueue(q,p->left);
if(p->right!=NULL)
EnQueue(q,p->right);
}
}
}


int main

()
{
BiTree T;
ElemType search1,search2,insert;
T=CreateBiT();
scanf("%d %d %d",&search1,&search2,&insert);
preorder_btree(T);
printf("\n");
inorder_btree(T);
printf("\n");
postorder_btree(T);
printf("\n");
if(searchBiT(T,search1)==NULL)
printf("0\n");
else printf("1\n");
if(searchBiT(T,search2)==NULL)
printf("0\n");
else printf("1\n");
T=InsertBiT(T,insert);
preorder_btree(T);
printf("\n");
inorder_btree(T);
printf("\n");
postorder_btree(T);
printf("\n");
InOrderTraverse(T);
printf("\n");
breadthFirst(T);

}




8587行编辑程序
typedef char SElemType;
#include"malloc.h"
#include"stdio.h"
#include"math.h"
//#include"process.h" //exit()
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2

struct SqStack
{
SElemType *base;
SElemType *top;
int stacksize;
};

FILE *fp;

Status InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}

Status StackEmpty(SqStack &S){
if(S.base==S.top) return TRUE;
else return FALSE;
}

Status ClearStack(SqStack &S){
S.top =S.base ;
return OK;
}

Status DestroyStack(SqStack &S)
{
free(S.base );
S.base =NULL;
S.top =NULL;
S.stacksize=0;
return OK;
}

Status Push(SqStack &S,SElemType e)
{
if(S.top -S.base >=S.stacksize ){
S.base =(SElemType *)realloc(S.base ,(S.stacksize +STACKINCREMENT)*sizeof(SElemType));
if(!S.base) return ERROR;
S.top =S.base +S.stacksize ;
S.stacksize +=STACKINCREMENT;
}
*S.top ++=e;
return OK;
}

Status Pop(SqStack &S,SElemType &e)
{
if(S.top ==S.base ) return ERROR;
e=*--S.top ;
return OK;
}

Status StackTraverse(SqStack S,Status(*visit)(SElemType))
{
while (S.top >S.base )
visit(*S.base ++);
printf("\n");
return OK;
}

Status visit(SElemType c)
{
printf("%c",c);
return OK;
}

void LineEdit()
{
SqStack s;
char ch,c;
int n,i;
InitStack(s);
scanf("%d",&n);
ch=getchar();
for(i=1;i<=n;i++)
{
ch=getchar();
while(ch!='\n')
{
switch(ch)
{
case '#':Pop(s,c);
break;
case '@':ClearStack(s);
break;
default:Push(s,ch);
}
ch=getchar();
}
StackTraverse(s,visit);
ClearStack(s);
DestroyStack(s);
}

}

int main()
{
LineEdit();
return 1;
}