队列的链式存储
定义：
typedef struct node
{elemtype data;
struct node *next;}  queueqtr;
typedef struct
{queueptr *front,*rear;} linkedquetp;

初始化算法：
void inilinkedque(linkedquetp *s)
{s->front=(queueptr *)malloc(sizeof(queueptr));
s->rear=s->front;
s->front->next=Null';
}
入队列算法：
void enlinkedque(linkedquetp *s,elemtype x)
{queueptr *p;
p=(queueptr *)malloc(sizeof(queueptr));
p->data=x;
p->next=Null;
s->rear->next=p;
s->rear=p;
}
出队列算法：
elemtype dllinkedque(linkedquetp *s)
{queueptr *p;
if(s->front==s->rear)
   return(Null);
else
   {p=s->front;
    s->front=s->front->next;
    free(p);
    return(s->front->data);}
}

[color=#DC143C]栈和队列

[color="ffffff"]串 基本运算： StrAssign(&t,chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串t。 StrCopy(&t,s) 初始条件：串s存在。 操作结果：由串s复制得串t。 StrEpty(s) 初始条件：串s存在。 操作结果：若s为空串，则返回TRUE，否则返回FALSE。 StrCompare(s,t) 初始条件：串s和串t存在。 操作结果：若s>t，则返回值>0；若s=t，则返回值=0；若s

[color="FFFFFF"]串的实现 定义： #define STRINGMAX 81 struct string {int len; static char ch[STRINGMAX];}; typedef struct string STRING; 初始化： void ClearString(s) STRING *s; {int i; for(i=0;i='; ';; (*s).len=0; } 从文本文件f上读入一串字符到串变量s中： #include "stdio.h" void readstring(s,f) STRING *s; char f[]; {FILE *fp; int i=1; ClearString(s); if((fp=fopen(f,"r"))=Null) {printf("不能打开此文件\n"); exit(0); } while(((*s).ch=fgetc(fp)!=eof)&&(i<(STRINGMAX-1))) {(*s).len++; i++; } (*s).ch=';\0';; close(fp); } 求串长： int StrLength(s) STRING *s; {return((*s).len);} 串的联接： Status concat(&t,s1,s2) STRING *t,*s1,*s2; {int j,k; if((*s1).len+(*s2).len>=(STRINGMAX-1)) printf("t串超长\n") else {将s1前s1.len个转移到t； 将s2前s2.len个转移到t中的s1后； (*t).len=(*s1).len+(*s2).len; } } 求子串： void substring(&t,s,pos,len) STRING *t,*s; int pos,len; {int i; if((pos<1)||(pos)>(*s).len)||(len<0)||(len>(*s).len-pos+1) printf("pos或len超界\n"); else {(*t).ch[1..len]=(*s).ch[pos..pos+len-1]; (*t).len=len; } } 子串的插入： void StrInsert(s,pos,t) STRING *s,*t; int pos; {if((*t).len>0) if((pos>0)&&(pos<=(*s).len+1)) if((*s).len+(*t).len<(STRINGMAX-1)) {(*s).ch[pos+(*t).len..(*s).len+(*t).len]=(*s).ch[pos..(*s).len]; (*s).ch[pos..pos+(*t).len-1]=(*t).ch[1..(*t).len]; (*s).len=(*s).len+(*t).len; } else printf("t串超长\n"); else printf("pos位置不合适\n"); else printf("t串是空串\n"); } 字串的删除： 略 串的置换： void replace(s,t,v) STRING *s,*t,*v; {int index1,p,m,n,p; n=(*s).len; m=(*t).len; q=(*v).len; p=1; do {index1=index(s,t,p); if(index1!=0) { StrDelete(s,index1,m); StrInsert(s,index1,v); p=index1+q; (*s).len=(*s).len+q-m; n=(*s).len; } } while((p<=n-m+1)&&(index1!=0)); } 求子串位置： int Index(s,t,pos) STRING *s,*t; int pos; {int i,j; if((pos<1)||(pos+(*t).len>(*s).len+1)||((*t).len==0)) return(0); else {i=pos;j=1; while((i<=(*s).len)&&(j<=(*t).len)) {if ((*s).ch==(*t).ch[j]) {i++;j++;} else {i=i-j+2;j=1;} } if(j>(*t).len) return i-(*t).len; else return(0); } } 更好的匹配算法，求子串位置： int index_kmp(s,t,pos) STRING *s,*t; int pos; {if((pos<1)||(pos+(*t).len>(*s).len+1)||((*t).len==0)) return(0); else {i=pos;j=1; while((i<=(*s).len)&&(j<=(*t).len)) {if((j==0)||(s==t[j]) {++i;++j;} else j=next[j]; } if(j>(*t).len) return(i-(*t).len) else return(0); } } next函数： void get_next(t,int &next[]) STRING *t; {i=1;next[1]=0;j=0; while(i<(*t).len) {if((j=0)||((*t).ch==(*t).ch[j])) {++i;++j;next=j;} else j=next[j]; } } 更好的next函数： void get_nextval(t,int &next[]) STRING *t; {i=1;nextval[1]=0;j=0; while(i<(*t).len) {if((j=0)||((*t).ch==(*t).ch[j])) {++i;++j;nextval=j; if((*t).ch!=(*t).ch[j]) nextval=j; else nextval=nextval[j]; } else j=nextval[j]; } }

串：

[color=#DC143C]数组和广义表 三元组顺序表： 定义： #define maxsize 1000 typedef struct {int i,j; datatype v; } node; typedef strcut {int mu,nu,tu; node data[maxsize]; } matrix; 求a的转置矩阵： matrix transmatrix(a) matrix *a; {int am,bn,col; matrix *b; b=(matrix)malloc(sizeof(matrix)); b.mu=a.nu; b.nu=a.mu; a.tu=b.tu; bn=0; for(col=0;col

十字链表 定义： typedef struct node {int i,j; struct node *down,*right; union {struct node *next; datatype v;} val; } linklist; 建表： linklist *creatcrosslink() {linklist *p,*q,*h,*cp[smax]; int i,j,m,n,t,s; datatype v; sacnf("%d%d%d",&m,&n,&t); if(m>n) s=m; else s=n; h=malloc(sizeof(linklist)); h->i=m;h->j=m; cp[0]=h; for(i=1;i<=s;i++) {p=malloc(sizeof(linklist)); p->i=0;p->j=0; p->right=p; p->down=p; cp=p; cp[i-1]->val.next=p; } cp->val.next=h; for(i=1;i<=t;i++) {scanf("%d%d%d",&i,&j,&v) p=malloc(sizeof(linklist)); p->i=i;p->j=j;p->val.v=v; q=cp; while((q->right!=cp)&&(q->right->jright; p->right=q->right; q->right=p; q=cp[j]; while((q->down!=cp[j])&&(q->down->idown; p->down=q->down; q->down=p; } return h; } 一个插入函数： insert(crow,ccol,cval,cp) int crow,ccol,cval; linklist *cp[smax]; {linklist *s,*last; s=malloc(sizeof(linklist)); s->i=crow;s->j=ccol;s->v=cval; last->right=s;last=s; cp[ccol]->next->down=s; cp[ccol]->next=s; } 加法运算： linklist *matrixadd(a,b,c,cp) linklist *a,*b,*c,*cp[smax]; {int n,i,arow,brow; linklist *last,*arow,*brow,*s,*pa,*pb; c=malloc(sizeof(linklist)); c->i=a->i;c->j=a->j; if(a->i>a->j) n=a->i; else n=a->j; cp[0]=c; for(i=1;i<=n;i++) {s=malloc(sizeof(linklist)); s->i=0;s->j=0; s->right=s;s->down=s; sp=s; } arow=a->next;brow=b->next; last=cp[0]; i=0; while((arow!=a)&&(brow!=b)) {pa=arow->right;pb=brow->right; while((pa!=arow)&&(pb!=brow)) { if(pa->j==pb->j) {if(pa->v+pb->v!=0) insert(pa->i,pa->j,pa->v+pb->v); pa=pa->right;pb=pb->right; } else if(pa->j>pb->j) {insert(pb->i,pb->j,pb->v); pb=pb->right; } else {insert(pa->i,pa->j,pa->v); pa=pa->right; } } while(pa!=arow) {insert(pa->i,pa->j,pa->v); pa=pa->right;} while(pb!=arow) {insert(pb->i,pb->j,pb->v); pb=pb->right; } last->right=cp; i++; last=cp; arow=arow->next;brow=brow->next; } for(i=1;i<=c->j;i++) cp->next->down=cp; for(i=1;i<=n-1;i++) cp->next=cp[i+1]; if(n==0) c->next=c; else {cp[n]->next=c; c->next=cp[1]; } }

广义表
定义：
typedef struct bnode
{int atom;
struct bnode *next;
union
  {struct bnode *snext;
   datatype data;} elemtype;
} slists;
或：
typedef struct dbnode
{datatype data;
struct dbnode *next1,*next2;
} dblists;
求深度：
depth(ls)
slists *ls;
{int max,dep;
max=0;
while(ls!=Null)
  {if(ls->atom==1)
     {dep=depth(ls->snext);
        if(dep>max)  max=dep;
      }
   ls=ls->next;
  }
return max+1;
}

[color=&#35;DC143C]数组和广义表

[color=&#35;DC143C]树
树的基本运算：
(1)SETNULL(T)
置T为空表。
(2)ROOT(T)或ROOT(x)
找根函数。求树T的根或求结点x所在的树的根结点。若T是空树或x不在任何一棵树上，则函数值为“空”。
(3)PARENT(T,x)
找双亲函数。求树T结点为x的双亲结点。若结点x是树T的根结点，或者结点x不在树T上，则函数值为“空”。
(4)CHILD(T,x,i)
找孩子结点函数。求树T中结点为x的第i个孩子结点。若结点x无第i个孩子，则函数值为“空”。
(5)CREATE(x,F)
建树函数。生成一棵以x为结点为根、以森林F为子树森林的树。
(6)ADDCHILD(y,i,x)
添加子树操作。把结点x为根的树置为结点y的第i棵子树。若原树中无结点y或结点y个子树个数小于i-1，则为空操作。
(7)DELCHILD(x,i)
删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数小于i，则为空操作。
(8)TRAVERSE(T)
遍历操作。按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。

二叉树的基本操作：
(1)SETNULL(BT)
置BT为空表。
(2)ROOT(BT)或ROOT(x)
找根函数。求树BT的根或求结点x所在的树的根结点。若BT是空树或x不在任何一棵树上，则函数值为“空”。
(3)PARENT(BT,x)
找双亲函数。求树BT结点为x的双亲结点。若结点x是树BT的根结点，或者结点x不在树BT上，则函数值为“空”。
(4)LCHILD(BT,x)和RCHILD(BT,x)
找孩子结点函数。求树BT中结点x的左孩子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。
(5)CREATE(x,LBT,RBT)
建树函数。生成一棵以x结点为根、LBT和RBT分别为左子树和右子树的二叉树。
(6)ADDLCHILD(BT,y,x)和ADDLCHILD(BT,y,x)
添加子树操作。把结点x为根的树置为结点y的左边或右边。
(7)DELLCHILD(BT,x)和DELRCHILD(BT,x)
删除子树操作。分别删除二叉树BT中以结点x为根的左子树或右子树。若无左子树或右子树，则为空操作。
(8)TRAVERSE(BT)
遍历操作。按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。

二叉树的存储
顺序存储结构：
利用满二叉树编号，将二叉树的结点按对应的编号存储在数组中。
二叉链表法：
typedef struct btnode
{telemtype data;
struct btnode *lchild,*rchild;
} bitnode,*bitree;
三叉链表法：
typedef struct btnode
{telemtype data;
struct btnode *lchild,*rchild，*parent;
} bitnode,*bitree;

生成二叉排序树的算法 生成二叉排序树的递归算法： bitree creat_ordbt() {bitree t,s; telemtree x; t=Null; scanf(&x); while(x!=0) {s=(bitree)malloc(sizeof(binode)); s->data=x;s->lchild->Null;s->right=Null; t=ins_node(s,t);/* 插入结点函数 */ scanf(&x); } return t; } bitree ins_node(bitree s,bitree t) {if(t==Null) t=s; else if(s->datadata) t->lchild=ins_node(s,t-lchild); else t->rchild=ins_node(s,t->rchild); return t; } 生成二叉排序树的非递归算法： bitree creat_ordbt_2() {bitree t,s,p,q; telemtree x; t=Null; scanf(&x); while(x!=0) {s=(bitree)malloc(sizeof(binode)); s->data=x;s->lchild->Null;s->right=Null; if(!t) t=s; else {p=t; while(p) {q=p; if(s->datadata) p=p->lchild; else p=p->rchild; } if(s->datadata) q->lchild=s; else q->rchild=s; } } return t; }

二叉树的遍历
前序遍历：先访问根结点，再按前序遍历左子树，最后按前序遍历右子树。
中序遍历：先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。
后序遍历：先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。

遍历的递归算法
前序遍历：
void preorder(bitree root)
{if(root!=Null)
   {printf("%d\t",root-data);
    preorder(root->lchild);
    preorder(root->rchild);
   }
}
中序遍历：
void inorder(bitree root)
{if(root!=Null)
   {inorder(root->lchild);
    printf("%d\t",root-data);
    inorder(root->rchild);
   }
}
后序遍历：
void postorder(bitree root)
{if(root!=Null)
   {postorder(root->lchild);
    postorder(root->rchild);
    printf("%d\t",root-data);
   }
}

按前序序列建二叉树的算法：
bitree createbitree()
{bitree t;char ch;
scanf("%c",&ch);
if(ch==" ") t=Null;
else
    {t=(bitree)malloc(sizeof(bitnode));
     t->data=ch;
     t->lchild=creatbitree();
     t->rchild=creatbitree();
    }
return t;
}
遍历的非递归算法
&#35;define M 100
前序遍历：
void preorder(bitree t)
{int top=0;
bitree p,s[M];
p=t;
do
   {while(p!=Null)
         {printf("%d\t",p->data);
          if(p->rchild!=null)
          s[top++]=p->rchild;
          p=p->lchild;
         }
    if(top>=0) p=s[--top];
   }
while(top>=0);   
}
中序遍历：
void inorder(bitree t)
{int top=0;
bitree p,s[M];
p=t;
do
   {while(p!=Null)
         {s[top++]=p;
          p=p->lchild;
         }
    if(top>=0)
         {p=s[--top];
          printf("%d\t",p->data);
          p=p->rchild;
         }
   }
while(top>=0);
}
后序遍历：
void postorder(bitree t)
{int s2[M],top=0,b;
bitree p,s1[M];
p=t;
do
    {while(p!=Null)
        {s1[top]=p;
         s2[top++]=0;
         p=p->lchild;
        }
     if(top>0)
        {b=s2[--top];
         p=s1[top];
         if(b==0)
            {s1[top]=p;s2[top++]=1;
             p=p->rchild;
            }
         else
            {printf("%d\t",p->data);
             p=Null;
            }
        }
    }
while(top>0);
}

二叉树算法举例
求二叉树的叶子树：
int countleaf(bitree t,int num)
{if(t!=Null)
      {if((t->lchild==Null)&&(t->rchild==Null)) num++;
       num=countleaf(t->lchild,num);
       num=countleaf(t->rchild,num);
      }
return num;
}
求二叉树的树高：
int treedepth(bitree t)
{int h,lh,rh;
if(t==Null) h=0;
else
    {lh=treedepth(p->lchild);
     rh=treedepth(p->rchild);
     if(lh>=rh) h=lh+1;
     else h=rh+1;
    }
return h;
}