线索二叉树
定义：
typedef enum{0,1} ptrtag;
typedef struct bithrnode
{telemtype data;
struct bithrnode *lchild,*rchild;
ptrtag ltag,rtag;
} bithrnode,*bithrtree;
构造中序线索二叉树：
bithrtree crt_inordthrd(t,pre)
bithrtree thrt,pre;
{thrt=(bithrtree)malloc(sizeof(bithrnode));
thrt->ltag=0;thrt->rtag=1;
thrt->rchild=thrt;
if(t==null) thrt->lchild=thrt;
else
   {thrt->lchild=t;pre=thrt;
    inthrd(t);
    pre->rchild=thrt;pre->rtag=1;
    thrt->rchild=pre;
   }
return thrt;
}
void inthrd(bithrtree p)
{if(p!=Null)
   {inthrd(p->lchild);
    if(p->lchild==Null)
       {p->ltag=1;p->lchild=pre;}
    if(p->rchild==Null)
       {pre->rtag=1;pre->rchild=p;}
    pre=p;
   }
inthrd(p->rchild);
}
遍历线索二叉树：
void inordtraverse_thr(bithrtree t)
{bithrtree p;
p=t->lchild;
while(p!=t)
    {while(p->ltag==0) p=p->lchild;
     printf("%..",p->data);
     while((p->rtag==1)&&(p->rchild!=t))
         {p=p->rchild;
          printf("%..",p->data);}
     p=p->rchild;
    }
}

树的存储结构
#define mtsize 100
双亲表示法：
typedef struct ptnode
{telemtype data;
int parent;
} ptnode;
typedef struct
{ptnode tree[mtsize];
int n;
} ptree;
孩子表示法：
typedef struct ctnode
{int child;
struct ctnode *next;
} *childptr;
typedef struct
{telemtype data;
childptr firstchild
} ctbox;
typedef struct
{ctbox tree[mtsize];
int n,r;
} ctree;
孩子兄弟表示法：
typedef struct csnode
{elemtype data;
struct csnode *firstchild,*nextsibling;
} csnode,*cstree;

哈夫曼树： 定义： typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; }htnode,*huffmantree; typedef char *huffmancode 求哈夫曼树： huffmantree crt_huffmantree(int *w,int n) {huffmantree ht; m=2*n-1; ht=(huffmantree)malloc((m+1)*sizeof(htnode)); for(p=ht,i=1;i<=n;i++,p++,w++) *p={*w,0,0,0}; for(;i<=m;i++,p++) *p={0,0,0,0}; for(i=n+1;i<=m;i++) {select(ht,i-1,s1,s2); ht[s1].parent=i;ht[s2].parent=i; ht.lchild=s1;ht.rchild=s2; ht.weight=ht[s1].weight+ht[s2].weight; } return ht; } 从叶子到根逆向求每个字符的哈夫曼编码： huffmancode get_huffmancode(huffmantree ht,int n) {hc=(huffmancode)malloc((n+1)*sizeof(char)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]="\0"; for(i=1;i<=n;i++) {start=n-1; for(c=i,f=ht.parent;f!=c;f=ht[f].parent) if(ht[f].lchild==c) cd[--start]="0"; else cd[--start]="1"; hc=(char*)malloc((n-start)*sizeof(char)); strcpy(hc,&cd[start]); } free(cd); return hc; }

[color=#DC143C]图 图的存储结构 接矩阵表示法： #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 int adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {vertextype vex[MAX_VERTEX_NUM]; adjmatrix arcs; int vexnum,arcnum; } mgraph; 邻接矩阵表示法建立无向网： void creatmg(mgraph g) {int i,j,k,v1,v2,w; scanf(&g.vexnum,&g.arcnum); for(i=0;i"); for(i=0;i[j]=INFINITY; for(k=0;k[j]=g.arcs[j]=w; } } 邻接表表示法： 结点： #define M 60 typedef struct node {int vex; struct node *link; } JD; 表头结点： typedef struct tnode {int data; struct node *link; } TD; 邻接表表示法建立无向网： void creatljb(TD ad[],int n) {JD *p; int i,j,k; for(k=1;k<=n;k++) ad[k].link=Null; scanf("%d,%d",&i,&j); while((i>0)&&(j>0)) {p=(JD)malloc(sizeof(JD)); p->vex=j;p->link=ad.link; ad.link=p; p=(JD*)malloc(sizeof(JD)); p->vex=i;p->link=ad[j].link; ad[j].link=p; scanf("%d,%d",&i,&j); } } 邻接多重表表示法： 表示边的结点： typedef struct arcnode {int mark,ivex,jvex; struct arcnode *ilink,*jlink; } JD; 表示顶点的结点： typedef struct vexnode {int data; struct arcnode *firstarc; } DD;

图的遍历 深度优先搜索遍历 从顶点v按深度优先： void dfs(TD g[],int v,int c[]) {JD *p;int i; c[v]=1;printf("%d\n",v); for(p=g[v].link;p!=Null;p=p->link) {i=p->vex; if(c==0) dfs(g,i,c); } } 对整个图遍历的算法： void blt(TD g[];int n) {int v; int c[M]; for(v=1;v<=n;v++) c[v]=0; for(v=1;v<=n;v++) if(c[v]==0) dfs(g,v,c); } 广度优先搜索遍历 从顶点v按广度优先： void bfs(TD g[],int v,int c[]) {int q[M],r=0,f=0; JD *p; c[v]=1;printf("%d\n",v); q[0]=v; while(f<=r) {v=q[f++]; p=g[v].link; while(p!=Null) {v=p->vex; if(c[v]==0) {c[v]=1; printf("%d\n",v); q[++r]=v; } p=p->link; } } }

最小生成树 普里姆算法： #define M 30 #define MAX 99 void prim(mgragh g,int k,int n) {int i,j,min,p; struct {int adjvex; int lowcost; } closedge[M]; for(i=1;i.adjvex=k; closedge.lowcost=g.arcs[k]; } closedge[k].lowcost=0; for(i=1;i

最短路径： 求从一个顶点到其它各顶点的最短路径： (迪杰斯特拉算法) #define MAX 32767 void dijkstra(int ad[][M],int k,int pre[],int dist[],int n) {int i,j,p,min; k=k-1; for(i=0;i=ad[k]; if(dist=k+1; else pre=0; } pre[k]=0;dist[k]=0; ad[k][k]=1; for(j=0;j<(n-1);j++) {min=MAX; p=-1; for(i=0;i==0&&dist;} if(p==-1) break; else {ad[p][p]=1; for(i=0;i==0&&(min+ad[p])) {dist=min+ad[p]; pre=p+1; } } } } 求每一对顶点之间的最短路径： (弗洛伊德算法) void floyd(int ad[][M],int p[][M],int n) {int i,j,k; for(i=0;i[j]=0; else if(ad[j][j]=i+1; else p[j]=0 } for(k=0;k[k]+ad[k][j][j]) {ad[j]=ad[k]+ad[k][j]; p[j]=p[k][j]; } }

拓扑排序 用邻接表存储结构实现拓扑排序： typedef struct node {int vex; struct node *link; } JD; typedef struct tnode {int in; struct node *link; } TD; void topsort(TD g[],int n) {int top,m,k,j; JD *p; top=0;m=0; for(j=1;j<=n;j++) if(g[j].in==0) {g[j].in=top;top=j;}/*入度为0的顶点进栈*/ while(top>0) {j=top;top=g[top].in; printf("%d\n",j); m++; p=g[j].link; while(p!=Null) {k=p->vex; g[k].in--; if(g[k].in==0) {g[k].in=top; top=k; } p=p->link; } } printf("m=%d\n",m); if(m

[color=#DC143C]检索 线性表的检索 顺序检索： typedef struct {keytype key; elemtype other; } sqlist; sqlist R[n+1] int seqsrch(R,k) sqlist R[]; keytype k; {int i; R[0].key=k; i=n; while(R.key!=k) i--; if(i==0) return(False); else return i; } 折半检索： int binsrch(R,k) keytype k; {int low,high,mid; low=0; high=n-1; while(low<=high) {mid=(low+high)/2; if(k==R[mid].key) return mid; else if(k; int Blocksrch(R,ID,m,k); sqlist R[]; indexlist ID[]; keytype k; int m; {int i,j; i=0; while((i<=m-1)&&(k>ID.key)) i++; if(i>m-1) return(False); else {j=R.stadr; while((j.stadr+ID.len)&&(k!=R[j].key)) j++; if(j==ID.stadr+ID.len) return(False); else return j; } }

树表的检索 二叉排序树： typedef struct node {keytype key; elemtype other; strcut node *lchild,*rchild; } bilist; bilist *bstsrch(t,k) bilist *t; keytype k; {if((t==Null)||(t->key==k)) return(t); else if(t->keyright,k)); else return(bstsrch(t->left,k)); } 插入一个新的叶子结点到二叉排序树： bilist *insert(t,s) bilist *t,*s; {bilist *p,*q; if(t==Null) return s; p=t; while(p!=Null) {q=p; if(s->key==p->key) return t; else {if(s-key>p->key) p=p->right; else p=p->left; } } if(s->key>q->key) q->right=s; else q->left=s; return t; } 利用插入算法构造一棵具有n个结点的二叉排序树： bilist *bstcreat() {bilist *t,*s; keytype k; int i,n; elemtype data; t=Null; scanf("%d",&n); for(i=1;i<=n;i++) {scanf("%d",&key); s=malloc(sizeof(bilist)); s->lchild=Null; s->rchild=Null; s->key=key; s->other=data; t=insert(t,s); } } 三叉表示法： typedef struct node {keytype key; elemtype other; strcut node *left,*right,*parent; } bstsrchtree; 在一个排序二叉树删除一个关键值为k的结点： bstsrchtree *delete(k,t) keytype k; bstsrchtree t; {bstsrchtree *p,*q,*r; p=t; while((p!=Null)&&(k!=p->key)) if(kkey) p=p->left; else p=p->right; if(p==Null) break; if((p->left==Null)||(p->right==Null)) q=p; else {q=p->right; while (q->left!=Null) q=q->left; } if(q->left!=Null) r=q->left; else r=q->right; if(r!=Null) r->parent=q->parent; if(q->parent==Null) t=r; else if(q==q->parent->left) q->parent->left=r; else q->parent->right=r; if(p!=q) p->key=q->key; return t; }

[color=&#35;DC143C]排序
数据定义
typedef struct
{int key;
elemty otheritem;
} recdtype;
recdtype R[n];

插入排序 直接插入排序的算法： insertsorting(R) {recdtype R[]; int i,j; for(i=2;i; j=i-1; while(R[0].key=1) {d=d%2; do{bool=True; for(i=1;i<=n-d;i++) {j=j+d; if(R.key>R[j].key) {x=R;R=R[j];R[j]=x; bool=False; } } } while(bool==true); } } 设监视哨的希尔排序： int d[m];/*存放增量序列*/ recdtype R[n+d[0]];/*前d[0]个为监视哨*/ shellsort(R,d) recdtype R[]; int d[]; {int i,j,k,t; recdtype temp; int maxint=32767; for(i=0;i.key=-maxint; /*设置监视哨*/ k=0; do {t=d[k]; for(i=t+d[0];i; j=i-t; while(temp.key;temp=R.key; s=1;j=i-1; while(s<=j) {m=(s+j)/2; if(x=j+1;k++) R[j+1]=R[0]; } binsort(R) recdtype R[n]; {int i; for(i=2;i<=n;i++) binsearch(R,i); } 共享栈插入排序： sharedinsertsort(R) recdtype R[n]; {int maxint=32767; int i,j,m; recdtype t; R[0]=-maxint;R[n+1]=maxint; if(R[1]>R[n]) {t=R[1];R[1]=R[n];R[n]=t;} i=2;j=n-1; do {t=R; if((t>=R[i-1])&&(t<=R[j+1])) i=i+1; else if(tt) k=k-1; for(m=i;m>=k+1;m--) R[m]=R[m-1]; R[k]=t; i=i+1; } else {k=j; while(R[k+1]j); }

交换排序 冒泡排序： bubblesort(R) recdtype R[n]; {int i,j,flag; recdtype temp; for(i=0;i=i;j++) if(R[j+1].key; while(i=temp.key)&&(ii) {R=R[j];i++;} while((R.key<=temp.key)&&(ii) {R[j]=R;} } R=temp; if(s<(i-1)) quicksort(R,s,i-1); if(t>(i+1)) quicksort(R,i+1,t); }

选择排序 直接选择排序： selectsort(R) recdtype R[]; {int i,j,m; recdtype temp; for(i=0;i<=n-2;i++) {m=i; for(j=i+1;j<=n-1;j++) if(R[j].key; R=R[m]; R[m]=temp; } } } 堆排序：(堆顶为最小值情况) 筛选算法： creatheap(R,i,m) recdtype R[]; int i,n; {int j; recdtype temp; temp=R; j=2*i; while(j<=n) {if((jR[j+1].key)) j++; if(temp.key>R[j].key) {R=R[j]; i=j; j=2*i; } else j=n+1; } R=temp; } 完整的堆排序算法： heapsort(R,n) recdtype R[]; int n; {recdtype temp; int i,j; for(i=n/2;i>=1;i--) creatheap(R,i,n); for(i=n;i>=1;i--) {temp=R[1]; R[1]=R; R=temp; cteatheap(R,1,i-1); } }

归并排序 二路归并算法： merge(R,A,s,m,t) /*R->R[m],R[m+1]->R[t]=>A->A[t]*/ int s,m,t; {int i,j,k; i=s; j=m+1; k=s; while((i<=m)&&(j<=t)) if(R.key<=R[j].key) {A[k]=R; i++; k++; } else {A[k]=R[j]; j++; k++; } while(i<=m) {A[k]=R; i++; k++; } while(j<=t) {A[k]=R[j]; j++; k++; } } 对数组R[n]做一趟归并，R[n]以长度c分段： mergepass(R,A,n,c) recdtype R[],A[]; int n,c; {int i,j; i=1; while(i+2*c-1<=n) {merge(R,A,i,i+c-1,i+2*c-1); i=i+2*c; } if(i+c-1